0:04

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.

5:05

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.

16:36

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.

19:41

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.