0:05

[BLANK_AUDIO] Today we're going to talk about saddle-point asymptotics, which is

where we turn to estimate coefficients for generating functions that have no

singularity. This is the final step in complex

asymptotics. It's the last way to get a quick

asymptotic estimate of generating function coeffients according to our

standard overview. to understand Saddle point we need to

talk about modulus surfaces. and this is a a three dimensional

extension of what we've been using in two dimensions.

and to warm up I, I just want to look at two dimensional plots of functions where

we plot x versus the absolute value of some function of x, in a Cartesian plot.

So for example the function 2x is just a line, but absolute value of 2x is a v

when it hits zero it bounces back up again.

or one over x is a familiar hyperbola. but absolute value of one over x, is a a

little inverted funnel. sign x goes up and down.

absolute value of sign x keeps bouncing off the origin.

one minus x squared is the parabola. but absolute value of one minus x squared

starts to look a bit like batman. and as we get to more complicated

functions we get more interesting shapes so this is a cubic for example.

and I just bring these up in two dimensions so that the shapes that we see

in three dimensions can be, are not quite so jarring and can be interpreted.

in terms of shapes like this. So now what we want to do is look at

three dimensional versions of the plots of analytic functions that we've been

working with. And that those things are called modular

surfaces, which is a plot of x y and absolute value of some function.

whereas somewhere points in the, in the Cartesian plane will correspond to x plus

yi. And we've been using plots like this to

help us identify poles and understand the topography of the, of the poles in

complex functions already. For example, here's a plot of 1 plus 4z

squared over 1 minus 4z squared. where black corresponds, the blacker a

point is, the higher the absolute value of the function.

And so, with a plot like this, we can see c equals plus a half and minus a half

where the denominator vanishes, as we get closer to those points.

The value of absolute value of f of z gets bigger and bigger.

we're the near 2I, I over 2 and minus I over 2 where the numerator goes to zero

then it gets to be white. but now in three-dimensions, this plot

has a much more fascinating shape. so, this is the same plot in, in 3D.

now, we'll be looking at properties of plots like this called modulus surface

ah, [COUGH] to help understand the saddle, saddle point method.

so one of the first questions come up is, can we get any shape this way?

and one interesting aspect of these kind of plots, is that no, actually the shapes

that we get are very highly constrained by by the situation.

in fact, there's only four different types of points.

on these kinds of surfaces. there's zeros where the thing actually

does get to zero the absolute value of the function actually gets to zero.

so in, in this case it's either [UNKNOWN] there's ordinary points which is pretty

much of everything else, where these things are, are very smooth and it's not

surprising they're smooth because. Analytic functions are smooth.

They're infinitely differential where, where they're defined.

And then there's poles, which we've already talked about.

and then there's a fourth type of point, called the saddle point, and that's what

we're going to focus on in this lecture. okay, so let's go through these types of

points one at a time. So the first one is, zeroes.

and, we'll first talk about simple zeroes.

So that's where the function's zero, and the derivative's, not zero.

so this is a, a typical example of a modular plot of a function, a simple

function showing off a zero. So this function is f of z equals 2z.

So in polar coordinates that's two r e to the i theta.

but the modulus is always two r. So it doesn't depend on theta.

So that means if we go out a distance r, then we're going to go up two r.

and then we'll have a circle so its a cone.

so its the same for all theta and then it comes down to a point right where at zero

zero where f of z equals zero. so that's a typical zero.

Now what's interesting is that all zeroes kind of look like this.

they have the same local behavior. that's because in analytic function we

can expand using Taylor's theorem in terms of its derivatives.

so we can write at any point f of z equals f of z 0, plus f prime of z 0

times z minus z 0 an so forth. and then if we, if its a zero then the

first term is zero and the second one is a constant that's not zero and then after

that as we get closer to, as z gets closer to z zero then it behaves just

like that constant times z minus z zero. Just a linear function.

So just like this. And they all have the same local

behavior. And that also doesn't depend on theta.

So for example, here's the function that has two zeros, 1 minus Z squared.

so you can see looking at the profile of it, it looks kind of like our batman

parable where it bounces off the axis and goes up but around the zeros it's little

points like this because it has the same local behavior as a simple zero at the

two points plus and minus one. so that's just doing the math.

So the functions that it behaves like locally.

and then so if we take one minus z q then we have three roots over 1 minus z to the

8th, we have 8 routes, and so forth. And these surfaces look quite intricate

and complicated, but, actually, all they are is collections of these points that

go down to the zeros. So now that's a so called simple zero if

you have a point where the derivatives are zero for a while and then finally

there's a place where some derivative is non-zero.

That's called a zero of order p. so like z cubed has a zero of order

three, so the point is curved a little bit more down at those at, at those

zeros. and so for typical functions you might

have multiple types of zeros. So this is a function z squared plus z

cubed and then you can see the little profile of the cubic function there.

one of the zero's is of order one, the other one is of order two.

So, it's fairly easy to understand what zero's are.

Those are the points where it touches. and if it's of order one, it's always

going to be a point. Otherwise, it'll have a, more rounded

contour where it touches. so that's what zeros are like.

9:29

And also you can have poles of order P as we know where the function grows like a

constant over Z minus Z zero to the P. And those are just chimneys that are not

tighter and grow faster. So that's what poles look like in the

module surface. So here's just a quick exercise, what

function is this?Now so this is a function its got one zero.

and one pole. Well this is a really function.

Its z over one minus z. so there's pole at one and a zero at

zero. and then the rest of the surface is just

integrating that together. Z over 1 minus Z and the thing about the

2D analog to that if you want to think about what the cross-section is like.

and so we're going to see variations on this kind of surface for all different

types of functions. But now there's the two other types of

points. Well, the first one is or, ordinary

points. So that's a point where the, the

function's not zero and the derivative's not zero.

so neither one of them is zero. And that's just places where the function

is smooth. And again, all ordinary points have the

same local per behavior. if you, look at the expansion, as z

approaches z-zero, around, around any point in z-zero, then what's going to

dominate is just the constants f of z-zero.

and the rest of the terms will go away, as we get closer and closer to z-zero,

and it's just an indication that it's smooth.

but now we come to saddle points, and that's the, the, kind of, new idea.

And so a saddle point is a point where the functions are not zero but the

derivative is zero. so here's a, a plot of a, of a function 1

over 1 minus z times 2 minus z, so it's got poles at at 1 and at 2.

now sadd, all saddle points have the same local behavior just as for poles and

zeroes. and again if we write up the Taylor

expansion. Now in this case the function f of z is

non-zero, but the derivative of 0 so what that leaves is a, quadratic term and

thats the term, that's going to dominate. so the idea of a saddle point is that,

its parabolas, and it does depend on the angle.

Alright so at one angle there's going to be a downward pointed parabola.

And at another angle there's going to be, perpendicular to that, actually there's

going to be an upward pointed parabola. And if you take cross sections, all

around, it, converts from one to the other.

But the behavior is always, quadratic, it's, it's got a parabola.

That's the basic characteristic of, saddle points.

And that's just like a saddle. That's where the name comes from.

You've go a downward parabola and, and upward parabola.

and we're going to take advantage of that key characteristic of saddle points to

estimate coefficients in generating functions.

12:45

so here's a here's a quick summary. This is a modular surface and we talked

about the four different types of points. So, there's simple zeros, where the

function is zero, but the first derivative is not zero.

and this one's got its simple zeros as indicated.

then there's zeros of order p bigger than one.

We don't have one of those and that's where the curve goes down.

then there's the saddle point, where the function is not zero, but the derivative

is zero, and it behaves like, a quadratic function.

and then there's ordinary points, where neither the function or it's derivative,

are at zero, And that's most points in the surface.

and then there's poles, where it blows up and is proportional to a constant over z

minus z0. But the key thing to note about this

table is, and that's where the function's derivatives are not defined.

the key things to note about this table is, that that covers all the

possibilities, either they're both 0 or the function 0 derivative's not, or the

derivative function is not 0, and the derivative is, or neither one of them is

0. That's all the possibilities.

Those are the four types of points. and indeed, there's a what's called the

maximum, that's an expression of what's called the maximum modulus principle and

there's all kinds of implications from that.

For example, there's no local maxima in a modulus surface.

There's nothing that looks like an upside down parabolic mountain.

Everything either blows up or it touches down you know, the thing where the men

move saddle points, which are in between these, but that's the characteristic of

these surfaces. So just to that summary, we just

finished, I, I, taking a look at, but first of all, how do you find the saddle

points? So here' s asimple example: one plus z

plus z squared plus zq. Where are the saddle points in this

module surface? It's easy to know where the zeros are.

That's where the thing equals zero, where it's the saddle point .The definition of

where the saddle point is is where the derivative is equal to zero.

So the derivative of that is one plus 2z plus 3z squared, you set that equal to

zero and solve it. And you find that the saddle points are

at, minus 1 third plus or minus I square root of 2 over 3.

Hm, I kind of, minus 1 third N and then square root of 2 over 3, on, on either

side of the axis. if you look at a bottom, view of the

surface and turn it upside down, you can see that, that's where those points,

points are. and that's the downward parabola, well in

this case it's it's the upper parabola upside down in the downward parabola.

Parabola upside down. So the zeroes, or minus 1 or plus or

minus i in the saddle points are minus 1 3rd or plus or minus i squared of 2 over

3. It's easy to find saddle points, set the

derivative to 0 and the points at which the derivative is equal to 0 is where the

saddle points are. so that's one of the important things

that we're going to need to do in order to analyze generate functions and those

singularities. so just to finish here's some of the

generating functions from analytic combinatorics that we've already looked

at so this is the type of generating function that we looked at for finding

odd strings with no sequences of K consecutive zeroes and this is four

consecutive zeroes. and we were looking at plots showing us

where the poles are and if you look at the, at the modular surface you get both

the poles and the zeros and that's the kind of shape that you get for a function

like this. this is the one for generalized

arrangements where we have this kind of plot and and it showed that this lonely

pole is the one that's closest to the origin, and determining the asymptotic

behavior on the modulus surface has a, a more striking characteristic, even more

striking characteristic. this one is 1 over 2 minus e of z and

that's for generalized surjections. and that one's got poles kind of next to

the imaginary axis and again, the surface plot tells us that it's the same

information just presented in a different way.

now, all of these have singularities, and we were able to analyze behavior of

coefficients because of the singularities.

what we're going to do next is look at the functions that have no singularities

and how we're going to estimate coefficients for those functions.