Today we're going to talk about singularity analysis. This is one of the crown jewels of analytic combinotorics. It's a general approach that really gives confidence that we can handle a broad variety of the generating function equations. That arrives from the symbolic method. we're well into complex a asentotics and we're talking about methods that can handle a generating functions that are not not meremorphic. now I, I have to, even I have to give a warning here, that we're starting to enter deep water. in terms of mathematical sophistication required for these results. we went from the symbolic method, to rational asymptotics which is really not much more than partial fractions. and then we looked at meromorphic asymptotics, which requires complex analysis and residues. and now we're going to look at singularity analysis. but again, even though we're getting into deep walk water, I promise as, at the end of lecture on meromorphic asymptotics. that our end result is a set of very broadly applicable schema, that are really not all that difficult to apply. To a big fraction of the kinds of generating function equations that arise. So, the end result is linear and not necessarily all that complicated. But in order to prove this result to be valid sometimes there is some technical skill needed. So, what we're going to do in this lecture is give an overview of the approach. And then and we're going to discuss in several basic and broadly applicable transfer theorems. and again full details are, are in the book, but this introduction. I think will persuade people that there's a basis for this kind of analysis getting us to good asymptotic results in many, many cases. now I'm going to start with prelude that will help put the characterization of the kinds of functions that we're talking about into context. now again the general form of combinatorial generated functions is, that we're always going to have an exponential growth factor. And some subexponential factor. and our first principal is that the location of the singularities are going to dictate the exponential growth. And the nature of the singularaties are going to dictate the subex, sub-exponential factor. Now, in the past two lectures, we looked at meromorphic functions, irrational functions. And saw that the smallest real root in the denominator gives the exponential growth factor. and then if it's a pole of order M then the sub-exponential factor is proportional to n to the m minus one. in this lecture, we're going to talk about singularities that are not poles. I have to talk about what I mean by that and how that impacts the sub-exponential factor. [COUGH] so what it, what it means is not poles. If you go back and look at the definition of an analytic function, or a meromorphic function. It's one that can be expanded except for a finite number of poles. And in, in the end what it means is that there's if you can't multiply by 1 minus AZ to the n, and get something that's analytic. and you can go back and look at the series representation to to try to check that. And we'll look right now at such a function. And the first idea is how do we extend the square root function to the complex plane? so that one thing you can do is use polar coordinates and write a complex number z as re to the i theta, or cosine theta plus i sine theta. And then you might as well define square root of z to be square root of r times e to the i theta over 2. And that seems to make sense because if you square the square root of z, then you get r. e to the i theta over 2 squared is just e to the i theta. You get z back. So, that seems like a good definition of the square root in the complex plane. but there's a problem called the multi, multiple values problem, and that is that there's actually infinitely many values of z. For which square root of z squared equals z because if you take add the integer multiple of pi i, to r squared [INAUDIBLE] theta over two. And then you square that then you get an extra factor of e to the two pi i which is one. So, for any integer K, we've got, a number that if you square it gives us back RE to the I theta. so, that's the so called multiple values problem. so what we do is, we want to have just one value that if you square gives z back. so we just restrict theta to be in the range minus pi to pi. so that's the standard definition of the complex square root. It's square root of RE the i theta over 2, where theta's between minus pi and pi. And there's only one value for every z in that range, that if you square it, it gives back z. so now, square root of z is uniquely defined and square root of z squared is equal to z, so that's good. and this gives us a basis now, say, for writing code to compute the square root. so, this is straightforward code to go ahead and compute the square root. and it uses, so there's a function that gives the absolute value of complex number. And remember, these are methods in our complex data type they have the real and the imaginary part. So javas method and hypoth function returns the square root of squares of two arguments. Which is exactly what we want for the absolute value of the complex number. and to get the angle it's the RE tangent and method eighteen and two and that gives the angle between minus pie and pie. And just what we want it turns out. so to compute the square root we take the square root of the absolute value of our number. and then we take the angle and divide by two. and then convert those over to X plus I Y, in the standard way, and then return a complex with those vakues. So, that's simple code to compute the square root. And so now, we can add square root to our blots for example. so the question is, "Does this square root function have singularities"? And if we look at our typical plot. Of the magnitude of square root of z it seems it seems fine, it seems very smooth. but actually that's misleading actually there's singularities but they don't show up on this plot. and also, they're not poles., they're not isolateduh, so, and we'll see what that looks like on the next slide. So, the reason that there's singularities shows up if we plot the angle, or the argument. There's a discontinuity in the argument on the negative real axis. and that has to do with this restriction to of the data to minus pi and pi. So, here's just an example of how we can show there's a discontinuity. So, let's take two points and one, just above the negative real axis and the other one just below the negative real axis. so now, by the definition if we take the square root of those two points the key thing is that this one down here, well the, the, so let's do the first one. the square root of z plus so that's at pi over 2 minus a little bit. and so, the square root of that is going to be to the i, pi over 2 minus a little bit. But the other one, it's it's not pi over 2 plus a little bit, because that's not in the right range, it's actually minus pi over 2 plus a little bit. And what that means is that if you take these things arbitrarily close. Epsilon arbitrarily small, these things [INAUDIBLE] arbitrarily close, but their arguments differ by i pi. so that means that they, they don't get close together. The functions don't get close together when the values get close together. And if you go back and look at the defere-, definition of deferentiability, that means that it's not going to be differentiable. And not differentiable means it's not analytic, it means it's a singularity. and the thing is that it works for any neg-, and z on a negative real line it's not differentiable. and they're all, there's an infinite number of points the're all clustered together. So, they're not isolated. A pole is something that's isolated multiply by 1 over 1 minus z, times the order of the pole and get rid of it. With these, you can't do that, there'll always be another one right next to it. So, that's called an essential singularity and square root, complex square root function has an infinite number of essential singularities. that's the key to understanding that we're going to need different methods than we used for [INAUDIBLE] function. Where we're just working with power series and isolated poles. so that's an example of essential singularities, and that's a key example and worth studying. so and the other thing is that where ever you use square root this is going to show up. So, this is square root of 1 minus 4z so now you always you're going to have an infinite number of essential sigularities on, on some line. okay, what about logarithm, that's another fine example and actually these two examples are critical ones. so we can do the same sort of thing. If we have z, equals re to the i theta We can define log of z equals log r plus i theta. and that seems to be good, because if you take e to the log z, then you get re to the i theta, you get z back. which seems to be what we'd want. but you still have the multiple values problem because you can again add a multiple of,, of 2 pi i. and still have e to the that number equals z. So, again, we want to restrict define log z where theta is restricted to b in the interval from minus pi to pi. and the, that, and again, gives us a definition of the log function such that log z is uniquely defined and e to the log z equals z, which is what we want. And again, this leads to a simple code, to, get the log, and, it's just a two liner. Just take the log of the absolute value, and then, use the same angle as the imaginary part. and then the, that's what we can use to do plots. with log, there's, there's other problems not just the singularity problem, which we'll talk about in the next slide. but you know, there's things that you might expect should hold true, but they only hold true. when the angles in the right range like log of e to the z equal to z only when the thetas in the right range. Or you can't even do things like log of w z equals log w plus log z unless the angle's in the right range. So the more restictive things we can do with calculating with the log function but again in the present context the question is, what about singularities? And again, if you plot the magnitude, it looks pretty smooth like other things that we've seen. but if you do the angle plot of the argument, you get the same kind of problem. And I'll skip that argument because it's very similar to the Square root example. There's a discontinuity on negative reline actually starting at one. and again so it works for any Z less than one in the real line. and so the log function also has an infinite number of essential singularities. they're not isolated. they're going to have to be dealt with differently than poles which we can just work with polynomers and po-, power series for mirrormorphic functions. and again, if you have, any time you use the log, you're going to run into this problem. so that's the complex logarithm. So, those are two functions that play a key role in trying to deal with uh, [COUGH] generating functions, equations that are not meromorphic. And usually they're not meromorphic because they involve one of these two functions. now there's another famous function on the complex plane, called the Gamma function. and we can spend a whole lecture, a whole course on the gamma function so I'll just quickly summarize it on this slide. And it comes from the idea of trying to extend the factorial function to the complex plane. so Euler in the 18th century came up with an integral res representation that works on the, on the reals/g. and actually continues to the whole complex plane except for the negative integers. so it's a, that's an integral representation zero for, and think of s as real just for a moment integral zero to infinity e to the minus t, t to the s minus 1 ds. so why does that work? Why does that extend the factorial function to the say non-integral reals? well, use integration by parts to get the key identity, but first of all, if you take gamma 1, that's just 1, it's e to -t from 0 to infinity, it's just 1. But if you do integration by parts then it's very easy to show that gamma of S plus 1 equals S times gamma of S. and so, that means then from those two things you can prove that in the argument is an integer. gamma of n plus 1 where n's a non-negative integer is equal to n factorial. so it matches n factorial on the integers that's clearly what we want. But it's defined for all reals. So, that's the key idea behind the gamma function. It's like for example, a very important value of the gamma function, is gamma of one half. Which is e to the -t over square root of tdt, which by change of variable, is e to the -x squared dx. and that's well-known definite integral related to the normal distribution is the square root of pi. Gamma of one-half is a square root of pi. And that's a key fact that actually plays a very important role in this lecture. and in the asymptotic analysis of many, many combinatorial classes gamma of one half is square root of pi. once you have gamma of one half being square root of pi. Then you can use the gamma of S plus1 equals S gamma of S to get gamma of other values like minus one half or three halfs. That's a very simple computation, using gamma of s plus 1 equals s gamma of s. and these, some of these values will come up in this lecture as well. but so far this is a pretty elementary real analyses that it shows this. Now, but there's way more to the gamma function as I said in a couple of forms of the gammic function. Which I'll, which I'll present without, without proof, but was known to mathematicians a century, a good centuries ago. one famous one is the wire strass form 1 over gamma of s equals se to the small gamma of s. And small gamma is Euler's constant, that's the same constant that comes up in the asymptotic approximation of the harmonic numbers. times product for n from 1 to infinity of 1 plus s over n times e to the minus s over n. That's the wire stress form of the gamma function. And again, centuries ago, mathemeticians worked with these product forms of many functions. Another famous one due to Euler is for sine of s equals product from 1 to infinity 1 minus S squared over p squared n squared. And these forms were interesting to these mathemac-, mathematicians at this time because they actually gave a good way to compute these values. they, because as you know, n gets bigger, these things get closer to 1 so you can get approximations to them. And actually, we're going to use it that way. but anyway we'll state those without proof for now and so you can do things from these forms. like prove that m of s times m of minus s equals s pi over sin s sin pi of s. kind of amazing kind of identities that you wouldn't think that there'd be such a relationship but boom there, there it is. Or another famous one is so-called reflection formula, gamma of s times gamma of 1 minus s equals pi over sine of pi s. those derive pretty easily from the product forms. and amazing identities and they play a essential role in all kinds of applied mathematics. and so again I don't have time in this lecture to do much more than, than just state em but they do play a key role in singularity analyses. in particular there's a representation of the gamma function known as the Hankel representation. and what that one says is it has to do with complex integration, and it says that 1 over gamma of s is 1 over 2 pi i. An integral around this contour that circles around the positive real axis, and it circles around the origin and then goes back out [INAUDIBLE]. Of minus T to the minus SE, to the minus TDT. it's a Hankel representation of the gamma function. and that looks a little strange, but actually given the product forms it It's actually not hard to prove. because what you can do is just take the two lines, and it comes out to be e to the i pi s minus e to the minus i pi s over 2 pi i times that integral. and that integral is gamma of one minus s, and the other one, that's the definition of sine pi s over pi. and so, now from the reflection formula you get back one over gamma of s. now it's not my point to prove all of these things but this, this is a key formula that we use in singularity analysis so that's what I pointed out. and this is all class, classical analysis and again with many, many applications in applied mathematics. So, Hankel representation, the basic identities and the values of gamma of one half. Those are the ones that you're, you're going to want to know, that's the basic properties of the square root function. And the large functions and the gamma function in a complex plane and that's a prelude to what we're going to need to know. Now, what about the singularities of the gamma function? Well, we can use that Weierstrass representation to just compute gamma function. And we can then develop a plot and that's the plot of gamma of z. And from the plot it's clear that there's singularities and there's other ways to show it. so actually, a gamma function has simple pulls at the non-positive integers. So with all those basic properties now we're prepared to start to take a look at singularity analysis. that's a prelude to square root log and gamma functions. [BLANK_AUDIO].
