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