1:28

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.

Â 6:02

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.

Â 19:10

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].

Â