Before we go on to the next kind of function that we'll be able to treat, we need some more fundamental ideas from complex analysis. it doesn't seem like it should be related at all, but we're going to talk about complex integration. and to do that, we're going to go back to the idea of an analytic function. remember, an analytic function is one that we can represent as a power series and a singularity is a point where a function is not analytic any more. So, for example, 1 over 1 minus z. in a small neighborhood of 0, we can write that as some N greater than 0, z to the n. So, 1 over 1 minus z is analytic at 0. Actually, with a little algebra, you can show that 1 over 1 minus z is analytic everywhere but at z equals 1. so, but the idea is representable by a power series expansion. and if we look at all the generating functions that we talked about they're analytic almost everywhere. There's just a few points where they're not analytic. and so and those are the points where the denominator blows up when it's a ratio where [COUGH] the square root is a special case that we'll talk about later on. but generally there analytic lots of places. So, that the it's that's why it's important to us. now as an aside I want to start talking about computing with complex functions. because we can do plots that actually are quite illuminating and we're going to start with that. it's not really an aside. It really is the way we're going to talk about the functions. and for computer scientists if we reinforces the idea of abstraction that we can write programs that manipulate complex numbers. Some programming languages have, have it built in. but even if it's not it's very easy to do. if you're not familiar with object oriented programming you can look at one of our introductory textbooks. in this example, we talked about this example in detail exactly this example because it's such a good example of object-oriented programming. So, we can define with code like this what a complex number is. The first two lines say that a complex number is a real part and an imaginary part. And the next line define how you create a complex number. If you take a real part and an imaginary part and you set those values. And if you have those values, you can define the functions to compute with complex numbers just according to the basic definitions that I gave. so, if I'm a complex and I want to add a complex number another complex number b to my value, then I think I could take my value as a. That's what that complex a of this means. and I can compute the real part by adding a's real part and b's real part and the imaginary part by adding a's imaginary part and b's imaginary part. and then, make a new complex number, with that real imaginary part, that's the result of the plus operation. and times has to cross multiply exactly as defined, and we can go ahead and write code for other the other operations. and that code will be posted with the website. If you don't do programming fine, but it's maybe just as easy for you to learn the programming as it is for the programmers to learn the complex. So I hope everybody works with the code as well as with the mathematical abstraction. and so we can talk about the idea of what is a complex function. it's just something that given a complex number evaluates and returns a complex number. And so, this is an example of code that implements the complex function, 1 over 1 plus z cubed. 1 is a new complex number that's got a real part of 1, imaginary part of 0. and then the denominator is going to be we're going to take that number 1 and add a number to it. That's what the dot plus means. What I'm going to add to it, we're going to add z times z times z. So, that's 1 plus z cubed. and then, we're going to take the reciprocal of that, that's the complex number that we're going to return, 1 over 1 plus z cubed. now it takes a little while to get used to this kind, kind of syntax, but not that much. and I think again most people will find it easy to look at the code and do simple things with it. and so that's fine, so we can write programs that compute with complex numbers. I just want to mention there's a design choice here, and that is that we treat complex numbers as mutable. that is, every complex number that we wind up computing with is different. in computers nowadays that just seems to be a reasonable the way to go. It's the same approach that with programming languages like Java use for strings. and what's the point of all this is not just to write code. what's the interesting and why, and why I want to do it is that it's also pretty easy to plot complex functions. Then, we're going to do a particular kind of plot where we do an image. And all an image is, is a square array of pixels like everything you see on the screen is an image. And we're just going to take a 512x512 square of pixels. Now, we're going to give, that's points in the plane. Then, we're going to give, for a quart, for a particular complex function, we're going to give every pixel a grayscale value according to the magnitude of the value of the function. If the function has got a high value, it's going to be black. If it's got a low value, it's going to be white. And the gray says how big it is. So that's what this [COUGH] code in here is doing. so it's going to give an x and y which are scaled the x-y coordinates in the image. It's going to create a new complex number. And then it's going to evaluate a function, a given function at that complex number, compute the absolute value, and actually, we multiply by ten to really emphasize the growth. That's an arbitrary factor. and then we're going to convert that to a number between 0 and 255 to get the grayscale, and then we'll set the color of the pixel. And we'll do that for every one of the 200 and 512x512 pixels or whatever size that we set it to. but that's the key, every point has a color, which is black if the function is high and white, if it's low. And this is it's a really simple code any program would have no trouble trouble with this. and if you're not a programmer go to our book sites for introductory courses and you can work with this code and it's, it's not difficult. so, then what we can do is so this an example where we implement 1 over 1 plus z cubed. and all we have to do is call this function. a new version of that function 1 over 1 plus z cubed and we get a plot like this. this is for 1 over 1 plus z cubed. now our convention is we'll always draw a 2.5x2.5 square. so that's minus 1 over there. and this is square over 3 over 2 and so forth. So, the darkness of the pixel is proportional to absolute value of 1 over 1 minus 1 plus z cubed. So, most of the time it's pretty small. It, unless you get close to a [COUGH] something who's cube is minus 1 like minus 1 or these are whats called the roots of unity. and that's a wonderful part of the lore of complex numbers that I haven't talked about much, you know, just for the purpose of [UNKNOWN]. But those are the numbers that if you cube them, you get a minus 1. So that's what that plot looks like anyway. so very easy to get a visual representation of a complex function. And what we're really interested in is that this visual representation shows us the singularities that is the points where it blows up and you can't represent it with the power series. The points where it's not analytical the, where the function goes to infinity. so there's all kinds of functions these are just some examples. So, this is what 1 plus z plus z to the 5th looks like. and this is a little bit bigger square. If we're not going to be showing the 2.5x2.5 square we'll show that one in the white, because sometimes interesting things happen outside of that square. Now, in a surprising amount of time, interesting stuff happens right within that square. this is what e to the z plus z squared over 2 looks like. So when z gets positive it starts to get big. When z gets negative at a certain point, it starts to get big, otherwise, it's small, that's kind of what these things are saying. but those values are those functions are analytic everywhere that they're going to infinity, but at a reasonable rate. so, let's look at the rational functions we've looked at. So, 1 over 1 minus z has a pole at 1. 1 over 1 plus z squared has poles at plus and minus i. 1 over 1 minus z to the 5th, those are the 5th roots of unity. this is what the generating function for the number of binary strings with no occurrences of four zeros in a row, looks like. it's got four poles, they're kind of spread out like that. and so, we, we get a feeling for, at least, how big the function is from these kinds of plots. and then, this is that, that other one for set partitions. And we'll, we'll look at the properties of these later on. So, the ideas that we can with these plots, we can characterize the functions. And we'll, we'll be doing that for a purpose later on. but now, let's talk about complex integration. and this is another very fascinating part of complex analysis. and it's a simple idea. You just want to define a line in the plane and you want to integrate along that line. and so like a straight line it's pretty easy. You just change variables to convert to real integrals, like if you're, integrate along that line at x equals 2 and then you can pull the 2 out and just do y as it changes, change to x plus iy. And another i comes out. so the 2 comes out with, with an i because of, we're changing along the y-axis. and then y squared over 2 from 3 to minus the 1, because we're going down. so that's a complex number that's the value of that integral. so that's a, a natural starting point. now there's, but we can add to that an integral that goes in a different direction and make a close contour. we can do around a circle. we have a lot of variability in terms of trying to define an integral. and some amazing facts is that if you have an analytic function in a region and you have any path of integration that's a loop the integral is going to be 0. and not only that relevant for analytic combinatorics, you can get the coefficients of a complex function by complex integration. So, that's what we're going to look at next. this is due to Cauchy. and it, you know, these facts are, are again, part of the foundation of a deep and beautiful theory that we're going to take advantage of. so for analytic combinatorics what we're going to use this for is to get exponential growth for this bigger set of generating functions then, then a rational called meromorphic. but let's look in more detail at some examples of integration. So, let's say, we want to integrate f of z equals z on a rectangle. So, we'll just integrate along the four lines just as I did before. so if you're inte, integrating on x then you can just leave the y part alone and just integrate. In this case, it's minus 6 plus 3i. this next one is the one I did before, which is 2i plus 4. this next one goes the other way. it it happens to be at i, so it's 6 minus i. and this, this other one goes up the other way. It turns out to be 4i minus 4. So, if we want the integral all the way around that rectangle, we just to add those four things up together. and so just add those, these four. And what's amazing is that we get 0. we had lots of different values, they just you can check my arithmetic, they all add up to 0. here's another example. we're going to integrate f of z equals z on a circle centered at 0. So now, we're going to hold the radius fixed, and we're going to change theta. So, we write our complex numbers in a polar coordinate, z equals re to the i theta, so then dz equals ir e to i theta d theta. we plug that in, then we have zdz so we have ir squared. We get e to the 2i theta e theta. so the integral of that is either the 2i theta over 2i, same sorts of rules as with the real, reals. evaluated from 0 to 2 pi, but 2 e to the 2 pi i equals 1. e to the 0 equals 1. and that, that's from Euler's formula. e to the 0 equals 1, so it's 0. the integral of f of z equals z on a circle centered at the origin is 0. it doesn't matter what the radius of the circle is. so that's interesting. let's look at another one. What about 1 over z on a circle centered at 0? So, integral of 1 over z, again applying so, you know, substituting re to the i theta, z over dz is just d theta. and then i comes out, so it's just now, dz over z here, all that's left is id theta. And so, that integral is just going to be 2 pi i. Integral of 1 over z in circle centered at 0 is 2 pi i. So, that's the examples of integration. so here's another one. let's say, it's z to a power not a circle centered at 0. so again, same substitutions z equal to re to the i theta, dz equals i re to the i theta. so z to the m is r to the me to the m theta. multiply it out, now we have e to the i m plus 1 theta would be theta. and now, there is two cases if M equals minus 1 then we get 0, I'm sorry, if M equals minus 1, we get 2 pi i the same as before because all that's left is 0, 0 2 pi b theta. If M is not equal to minus 1 and [COUGH] we're going to have the same 1 minus 1 situation that we had before and we're going to get 0. and, you know, even if it's a circle centered somewhere else, say, integral of f is equal to z minus s to the M at a circle centered at s it's going to be and I'm not going to go through all the steps. It's almost the same as before. it's going to depend only on whether M equals minus 1 or not. so z minus s to the 10th is always going to be 0. but 1 over z minus s is always going to be 2 pi i. these two are going to turn out to be important for integrating analytic function. so that's a couple of more examples of integration. so now the null integral property. so, what that says is if you have an analytic function in a region omega in the plane and you integrate that around any closed loop in that region then you're going to get 0. and again for the purposes this lecture, we're not going to prove this where this is, this is going to be an axiom. And, and I'll talk about then why we say it that way in just a minute. so this is what we saw. if we had f of z equals z, which is analytic we integrate around a rectangle, we get 0. Integrate around a circle, we get a 0. whatever shape you want to make, go ahead and calculate the the in integrals, which you can do you're always going to get 0 . another equivalent way to look at this is if you have one path alpha and another path beta and they're homotopic. That just means you can deform one to the other. then the integrals are going to be equal. so that is, there's alpha and there's beta. So, they start at the same point in, same starting and ending point, but you can deform one into the other. and the, the integral around is going to be 0, but if you switch the direction on beta, it's a proof that the integral on alpha is equal to integral on beta. So from the null integral property complex integration is quite a different thing than in for real functions. because you have this property that in a lot of cases, it doesn't matter what the path is you're still going to get the same value. and that's is certainly fascinating and, and key property. in fact I've mentioned the, really, the basis of complex analysis that I just glossed over by stating these things as axioms. If you want to see a proof that these things are all equivalent that's in appendix of the blue book or a a course in complex analysis really is, is about this. The, the idea that a function can be expanded in a power series, the idea that it's differentiable because the limit that defines differentiation exists no matter what the direction you go. And, and the idea that the integral around a closed loop should be 0 those are equivalent ideas and we actually, in the the book actually proves that with the, with the circle of implication. but now, what we're going to do is we're going to take that null integral property and we're going to use that to help us extract coefficients from an important class of generating functions. and that'll be our next topic. but to do, before we do that, we're going to talk about Cauchy's coefficient formula, which is an application of a null integral theorem. It does exactly what we want. if we have an analytic function we want to extract the coefficient of z to the n in that function. and the formula says, that what you do is you take the function, divide by z to the n plus 1, and integrate over any closed loop that now contains the origin. and it's, it's not difficult to prove. so our condition is that the function has to be analytic in in this region omega that contains the origin. So, therefore, the function is analytic at the origin. So therefore, we can express it as a power series at the origin or just f0 plus f1z plus f2z squared, and so forth. So, that's the first thing. Now what were going to do is take the loop and deform it to a small circle centered at zero or circle. And as long as the circle is within omega, were fine. and then, just integrate. and then, the integral is we can integrate term by term. so we're dividing by z to the n plus 1. So, it's f0z to the n plus 1 and so forth. Then fn over z, fn plus 1 times z to the n plus 1, and z to the n plus 1 cancels out fn plus 2z and so forth, like that. so that's the integral. now if we look at integration example 4, those things are going to be all 0 because we did an integral set. If you integrate z to the n around a circle containing the origin, it's going to be 0 unless the exponent is minus 1. So, the only thing that's left in the, and if exponent is minus 1, the value of the integral is going to be 2pi i. So, the only thing that's left is f sub n times 2pi i, that proves Cauchy, Cauchy's coefficient formula. just a consequence of the low integral of, of, you know, complex integration. So, in the context of analytic combinatorics this is going to lead to the transfer theorems for a much broader class of functions called the meromorphic functions. and that's what we're going to look at next. the idea of complex integration is a deep and powerful idea that's going to be very helpful to us in the analytic combinatorics.
