Now we're ready to t-, take a look at the basic approach of using singularity

analysis to develop asymptotic estimates coefficients from generating functions

and equations. so just to review the transfer theorems

that we've taken a look at if we have meromorphic function, we saw in the last

couple of lectures, then we've got an easy way, based on the theorem based on

contouring integration residues. But easy-to-apply theorem that gives us

the an approximation of the coefficient Z to the n, the ratio of two analytic

functions. by simply evaluating the derivative at

the closest pole to the origin. standard function scale lots of functions

fall in that range. then we can just immediately use the the

transfer theorem that I just gave for the standard function scale and that's based

on the gamma function. but if it's not either one of the those,

that, that's when we're going to talk about singularity analysis.

And here's the example of a type of function that might that that is neither

meromorphic nor falls in the standard function scale.

it's got a square root, but it's got a product of that a ratio that of some

other function. so, what we're going to do,the basic idea

is to, get an approximation of this function to functions in the standard

scale and then do the transfer. and the next lecture, by the way, we'll

look at what happens when there's no singularities at all.

So, but, now we're going to talk about Singularity Analysis.

Now, just a quick review of one of the keys to singularity analysis is our

ability to use the Taylor theorem to approximate functions at points that

aren't singular. That's a definition of an analytic

function is it's differentiable everywhere if it's analytic at a point,

it's differential everywhere at the point.

and that means you can expand it at the point just using Taylor's theorem.

So say if we have this function that I show before e to the minus z squared over

2 minus z squared over 4. And we want to expand it at z equals 1.

then we can just go ahead and compute the derivatives and evaluate them at 1.

So f of the function evaluated at 1 is e to the minus three quarters.

the derivative evaluated at 1 is plus e to the minus three quarters because 1

plus 1 is two, and then there's a minus that cancels out.

the second derivative evaluated at 1 you can get either minus three quarters over

4 and so forth. And just use Taylor's Theorem to develop

an expansion of the function at any point that it's not singular.

and that's a fine method that's been known for centuries and that's.

what we're going to do for singularity analysis is to exploit this ability to

approximate functions at non-singular points in terms of a po-, a power series

and that's what's going to take us to the standard scale as, as we'll see.

now nowadays we know people don't compute derivatives so much by hand anymore.

you can just use a computer and for a symbolic package and so this is Wolfram

Alpha, type in so say I want to know the series representation of square root of 1

minus 1 plus z over 2z at z equals one third.

I can just put it in that function at z equals one third and how many terms I

want and it'll tell me exactly the expansion.

So I don't have to compute that by hand. So people don't compute those things by

hand so much anymore. if you need to do it figure out how to

get a computer to do it, it's a much faster way to proceed.

actually, we're going to use these kinds of approximations in this lecture, only

early on to demonstrate the method. In practice, a great many of the

applications of singularity analysis are based on general schema, where we don't

have to do the expansion. it's all hidden underneath the covers in

terms of general schema. but still it's important to remind

ourselves what it's all based on. And Taylor theorem is definitely it.

okay, so here's an overview of the general approach to coefficient

asymptotics, for non-member functions. So again always we gotta locate the

singularities; in particular, we gotta find the one closest to the origin.

and that's what's going to give the exponential growth factor.

that's no different even when there's essential singularities.

There's one of them that's closest to the origin.

So, just running example, we'll use unary binary trees, so that's trees where all

nodes have degrees zero, one, or two. we develop this generating function for

it using the symbolic method. closest uh, [COUGH] singularity of the

origin is z equals one third. There's another one further out at minus

1, but that, that's the one that matters. So the exponential growth factor is

going to be 1 over that, which is 3 to the n.

so, that's the first thing. so then the next thing is to figure out

where the function is analytic near the dominant singularity, basically, where's

that slit? And then we're going to use functions

from the standard functions scale to approximated, near that dominant

singularity using Taylor theorem and we approximations that extend, in principal.

so, uh, [COUGH] we'll look at how to develop for, for this function an

approximation like this. and we can, can, carry it out like this.

as many terms, as we wanted. so that's, first key is, we have to know

where it's analytic. and, well we'll see how that comes out in

the proof. and then, the, the other basic idea in

singularity analysis is, Now we've got the thing expressed as

approximation using the standard scale. we can do term by term transfer and

immediately transfer this using the standard scale to the result.

And even transfer the big O to the corresponding result.

that's another key to the method, is term-by-term transfer is valid.

That has to be proved and that's one of the keys to the method.

and as I said, in the overview lectures, this paper was a real watershed in

analytic cognitorics. before that, people knew things kind of

like this. But after that, this is the scientific

basis for we can mathematically prove that we can do these kinds of

manipulations. and that's what led to the devlopment of

general schema and many other things that we won't have time to get to in this

course. So the whole idea of singularity analysis

depends on the function being analytic, in a region near its singularities.

in, so again for square root and log, usually talking about a slit and the key

idea is a thing called a delta domain. And they call it a delta analytic

function so that's one that's analytic in this particular shape where we take the

slit and we carve out a little v near the slit and then the other way other wise

it's a circle. so it's, it's a little bit weaker than

what the Hankle contour had which was a little circle cut out here and but that

that little difference makes a huge difference in allowing the transfers of,

of the type that we're going to consider. it may not not, people may not be able to

understand these kind of distinctions without really studying this derivation

in the book. but these, these distinctions are there.

and we'll look at just a sketch of that proof in just a minute.

just as a sideline, you might wonder why that particular shape what this is, is a,

a map of Paris And [INAUDIBLE] worked at in [INAUDIBLE]

which is in a suburb of Paris this is a blowup of the area a bit to the west of

Paris. Actually this is the palace of Versailles

down here. It's at the other end of the of the the

pool for the palace of, of Versailles. The, the big pool

And so there's an autoroute and this little area here is Rocquencourt, which

is where the Inrea research office was. And everybody working in this field, over

the 70's, 80's, 90's, and 2000's, would visit Rocquencourt for various periods of

times. And Philippe's office was centrally

located there. a little bit down the road there was a

place called corner bar. and maybe, many of you are too remember,

too young to remember the 80's people would go, we often would go to corner bar

for a quick beer. and at corner bar, there was a Pacman

machine, and and at that time that was quite a novelty.

And people spent many hours on the Pacman machine.

At corner bar having a beer and a smoke. and now Andrew Liska who's the co-author

of this paper denies that, that's where the shape came from.

But I know Phillip too well. Uh, [LAUGH] so I'm sure he was

persuasive. alright so back to the math.

let's look, take a look at how that, that domain shape matters.

now the key i, one of the key ideas is this idea that we can do transfers turn

by turn. even for big O, and little o terms.

And, there's a lot, a lot, of words here, but really this little table tells the

whole story. If you've got something in the standard,

function scale, so you have a big o term, You can transfer that function give that

approximation to that function from the standard function scale.

You can do the transfer for the coefficient asymptotics.

So, big O of 1 over [INAUDIBLE] c to the beta gives o of n to the alpha minus 1

log n of beta and so forth. So those

As long as it's delta, delta analytic within its delta dom, name, domain, you

can carry those transfers through. and it, this is just a really very be,

brief proof sketch just for big O-transfer, and again, you can spend some

time studying the, the details in the book.

But again, it's based on integration around an appropriately chosen contour.

So, if you know it's analytic in the Pacman region, then you can define this

more complicated region, which has a big circle and a little circle, and two

little lines connecting those circles. and in terms of re to the i theta, it's

technical, but not so difficult to characterize these curves.

This little circle, big circle, and two lines.

And then the question is to go 'head and do the estimate for each one of those

lines. and, half a page in the book for each one

of these showing that the line segments and the small segments are the ones that

really give the contribution. Again, starting from Cauchy's coefficient

formula and then the big circle becomes exponentially small, and so eventually

can prove that result. And again, Flageolet and [UNKNOWN] proved

that result it's a very. General result the rest of us can can use

it. so understanding the proof is not nearly

as important as understanding the application in, in the context of

analytic combinatorics. So then that gives us the three steps

that we need for coefficient asymptotics. we have to figure out where the

singularities are. we gotta establish that it's analytic and

a delta domain, a pacman domain. then [COUGH] we're going to do, we're

going to expand the function in this area, and then approximate it using the

standard function scale. And then do the transfer

Now, in this lecture we're just using the sim transfer, but it's very important to

understand, that the method enables an arbitrary asymptotic accuracy.

Uh, [COUGH], and then so turn by turn transfer, means taking each term in the

function expansion, to a term in the asymptotic expansion of the coefficients.

that's the Flajolet, Odlyzko singularity analysis paper where it's a great paper

to read if you're into reading classic math papers.

so we'll just take one example and sketch how singularity analysis.

Gives us coefficient asymptotics for this example, so that's unary, binary trees.

Every node has zero, one, or two children.

So, combinatorial construction is, it's a node and a sequence of zero, one, or two

nodes. trees.

which immediately translates to that generating function equation.

and if we solve that equation, just use the quadratic theorem, then we get this

explicit form. that is not meromorphic, that's the

square root of a polynomial. so it needs singularity analysis.

So, what we're going to do is well you can plot that function and figure out

that there's room for a pacman region. where it's analytic

[COUGH]. And so that singularity's at z equals 1

3rd, remember. and so, then, at z equals 1 3rd, the 1

minus 3z part is the the dominant singularity.

We're going to take the rest of the function, say 1 plus z over 2z that's the

one that I used the computer to expand so its square root of 3 plus uh,big O of 1

minus 3z or we could add more terms if we want at z equals one third.

then that's square root of three. and so then if you multiply that

expansion times square root of 1 minus 3z and then take care of this is z equals

one third. It's just 1 minus z over 2 z is 1 is

equal to one third. Then you have the square root of 3 times

square root of 1 minus 3 z. And then every term in the expansion has

another square root of 1 minus 3 z multiplied in.

So we have an asymptotic expansion in terms of n to the 1 minus 3 halves 5

halves 7 halves and so forth. All by the fact that it's n over this

part is analytic. And we can expand it in powers of 1 minus

3z, then we multiply by the square root of 1 minus 3z, and we have a term in the

half-power. But those half-powers are standard

function scale. So now we can do a term by term transfer

using the standard function scale, to take, well, you I'm going to change

variables to 3z to z to get to 3 at the end and then the rest of it comes out,

right from the table. Standard function scale, 1 over square to

4 pie over 3 turns into minus 3 halves. And then the next term is three to the n,

n to the minus five half, or you can get an asymptotic approximation.

Now, the next term is not exponentially smaller, it's just the factor of n

smaller, and that's why we need the ability to take more terms if we need

'em. but that's the basic process of

singularity analysis for unary-binary trees.

And it's a very general process that's going to work for a great many of the

functions that arise in analytic [UNKNOWN].

now one reason that we have confidence that singularity analysis is going to be

useful is that the set of functions that are immutable to singularity analysis is

closed. That is, if you have a couple of

functions and you add 'em or multiply 'em or compose 'em, differentiate or

integrate. Well, there's certain technical

conditions all the time. but it's easy to show that, so for

example, if f and z and g of z are delta analytic, then so is their product.

Well because you can approximate f say with in terms of one minus z to the alpha

and you approximate z in terms one minus g in terms of one minus e to the beta and

then you can pull out the approximations of their coefficients.

If you multiply those two functions together then you can immediately pull

out the coefficients of the product. It says if you can do f of z and g of z,

you can do the product. And you can show that for multiplication,

differentiation, other things like that. Well, the kinds of operations that we

perform on functions in the symbolic method are these kinds of things.

We add them, we multiply, we compose them, we differentiate.

Differentiate and integrate them, so we, we think that if you get your functions

in this way, then you're going to be able to use singularity analysis.

so that's a just a general observation. actually we can do even better and

develop a general schema that will free us from a lot of the details even of

singularity analysis for wide classes of functions.

that's just notice you don't multiply this way, you multiply that way.

You might think it's n to the alpha plus beta minus 2, but it's worth noticing

that it's not. that's for product and you can try doing

some or other things to prove that if two functions are amenable to singularity

analysis, their sum is also a composition.

so, the consequence is that the generate function's produced by the symbolic

method are generally going to be amenable to singularity analysis.

so that's a, introduction to singularity analysis and next we'll go on to schemas

and transfer theories.

Singularity Analysis

Analytic Combinatorics

Meet the Instructors