[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. now there's poles. We've already talked about poles. a pole is a point where the function behaves live a constant over z minus z-zero. So, it has, Z gets close to z zero, it blows up. so that's a typical pole. One over one minus z. And around the pole one, again, it's going to be the same for all theta. So it looks like this chimney. And you can, if you cut a cross section of that, then. You get a cross section of what we saw with a hyperbola in 2D absolute value land. and again by definition, all poles have the same local behavior, so that's a function with three poles, four and so forth but this is just one over one minus Z cubed, and so forth. One minus Z to the 25th. so again, inetersting contours, tying together poles. But locally, they all behave the same. 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. 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.
