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.
