Now we're going to look at the development of saddle point bounds for
generating function coefficients using [INAUDIBLE] integration.
the basic idea is very simple. Now, we start with Cauchy's coefficient
formula, which says that given an analytic function G of z.
The coefficient of z to the N and G of z is one over two pi i integral over a
circle that contains the origin, G of z, dz over z to the N+1.
so, just to look at an example, let's look at the function post G of z is e to
the z and we're looking for coefficient z to the fifth.
So that means the function that we're integrating, the e to the z over z to the
sixth. that's a plot of that function.
it's got a pole at zero, and then as the real part gets large it starts to get
large and there's obvious saddle point in there.
now, this plot is actually scaled substantially.
I think that it's only a point, a thousand pi or something.
We'll see some of the numbers in a minute.
But still that's what it looks like. so, the idea of a saddle-point bound is
to find a saddle-point and we always use zeta the Greek letter zeta for the
saddle-point. and then, for our circle we use the
circle of radius zeta. and that, so this is what the integral
will be, be adding up, the height under that circle.
And as you can see, for most of the range it's very, very small.
but even so, if we just take the highest point of the circle, which is the
saddle-point the integrand is going to be less than the value of the function
evaluated at zeta everywhere on that circle.
So then the value of the integral is just going to be as if we had that constant
and that will give us a, a very strong bound.
Now what's zeta it's the solution to the derivative this function equals zero.
and that's just doing the math. it's G prime over z to the N+1 minus N+1,
G over z to the N+2 multiplied by z to the N+2, we get z G prime over G is N
plus 1. That's known as the saddle-point
equation. so that's the idea.
Find zeta and just use the bound of G of zeta over zeta to, to the N+1.
So let's take a, a look at a couple of well here's a formal statement of the
bound. so if G is analytic finite radius of
convergence R with non negative coefficients which are generating
functions from analytic combinatorics always do.
Then the coefficient of z to the N and G of z is less than or equal to G of zeta
over zeta to the N, where zeta is the saddle-point.
Now, that's just a formal statement of the equation.
and again, it just is by Cauchy coefficient formula you take z to be
circle of a radius zeta, and change to polar coordinates.
then we're getting an extra zeta and then if we integrate and everything is
constant then the two pi goes away, and all that's left is G of zeta over zeta to
the n. so, so that's a, of, effective bound that
we can use to at least understand something about the growth of generating
functions coefficients. so for example in our example we're
trying to find a coefficient z to the 5th in E of z so that's we're looking at e to
the z. what's the saddle point?
the saddle point is zeta equals 6. so saddle point equation is G prime over
G which comes out to be 1, leaves us zeta equals 6.
and so the saddle point bound says that we know that coefficient of z to the 50
is z is 1 over 5 factorial. The bounds says that that's going to be
less than or equal to e to the 6th over 6 to the 5th.
and if we just compute those down the left side, it's, you know, 0.008, and on
the right side, it's 0.009. Pretty good bound, even for just the
small value. Five.
So, in general, just doing that same calculation.
let's see how well the saddle point method works for estimating one over N
factorial. so that's coefficient of z to the N and e
to the z. E to the z is the generating function
with no singularities. We're trying to estimate coefficient of z
to the N and e to the z. so saddle point methods, we take G of z
equals z to the z. Solve the saddle point equation.
Saddle point equation is G prime over G times Z equals N plus one so it's going
to tell us that the saddle point is zeta equals N plus one.