Partial Summation Formula and Its Applications | Analytic Number Theory

[00:00:04]okay so the um jna has asked me to give some informal lectures on analytic number Theory by way of introduction for self study now I've written this book problems in analytic number Theory so that students such as yourselves could study on your own um and I would recommend that you do that um I think you can probably there are some creative meth methods of getting hold of the book which I will not spell out because this is being videotaped now um let's see what can we say uh firstly analytic let me say a few words about analytic number Theory um generally analytic number theory is to use analysis to study uh problems in number Theory so uses analysis to study questions in number Theory now what kind of analysis um it can be real analysis it can be complex analysis or it could be ptic analysis so it could be any one of these uh types of analysis um padic is a a recent entry into the methodology in analytic number Theory and I have a book on um uh ptic analytic number Theory but if you're interested in studying that you can do that independently of of both these things but in this um kind of informal talk we will um focus only on real and later on perhaps complex analysis okay now generally speaking um we we will look at um methods rather than theorems so we'll pay attention to um methods rather than results okay so this is a just a definition of working definition of what analytic number theory is now the the focus of [Music] study in number Theory are arithmetical functions arithmetical functions are by definition functions complex valued functions defined on the natural numbers those are arithmetical functions and generally speaking we would be interested in interested in a variety of questions um growth of these functions growth of f n as n varies sometimes we may be interested in uh finding out the behavior of these partial sums and try and understand these sums um asymptotics for such for such functions and so that's basically the the the U focus of study uh in the class class of arithmetical functions of course there are several types of functions uh the most common perhaps that we will be looking get uh are multiplicative functions and these functions are if I have if they have the property that F of MN equals F of M * F of n whenever M and N are relatively prime we say the function is multiplicative okay we say the function is completely multiplicative if F of m n is equal to F of n * F of M for all MN whether whether whether they are co-prime or not it doesn't matter so we those those things are completely multiplicative functions we say a function is an additive function additive if we say if F MN is equal to F of M plus F of n uh whenever M and N are relatively prime and we say something is completely additive if we remove that restriction F of MN is f of M plus f ofn for all MN okay so these are several categories of functions let's have a look at some examples um is there eraser um here or okay oh there is here is there an eraser here let see oh yeah there is okay thank you yeah okay thank you all right let's look at some examples [Music] um the divisor function so D of n is the number of divisors okay so for example D of two is one and two two divisors right d of 2 is two D of3 is also two D of 5 is two um D of six though is 1 2 3 and six so four right it's four um Etc so this is the divisor function so clearly if I was given a number now you know that every number every natural number can be written as a product of prime Powers uniquely unique factorization theorem unique factorization so you can see that any divisor any divisor Delta of n will then have to look like P1 to the beta 1 PK to the beta K right with these beta I is less than Alpha I right 0 less than beta I less than Alpha I any divisor looks like this conversely if I pick any such number with this restriction it'll be a divisor so there's a one to one correspondence between divisors of N and all numbers of this type therefore how many choices of beta I do I have say it loudly Alpha I + 1 exactly so they're Alpha I + 1 choices for each of them therefore we have an exact formula for D of n right that's the that's the number of divisors so the question uh is is this a multiplicative function and completely multiplicative function an additive function or completely additive function or none of them what kind of a function is it any guesses it clearly depends only on the factorization and if M and N are relatively prime the divisors of M * n can be obtained by taking a divisor of M and a divisor of N and then clumping them together they seem to be independent right therefore it's multiplicative so this is a multiplicative function D of N is a multiplicative function question is is it a completely multiplicative function is it completely multiplicative all you all you need to do is you have to come up with an example correct okay well let's look at um D of um 8 how many divisors does 8 have that's 2 cubed right so four but this is not equal to D of 2 cubed right all you need to do is come up with an example to show it's not the case so it's not completely right actually we could have taken D of four also D of four is D of4 is what three right and it's not uh certainly okay so it's not completely multiplicative it's a multiplicative function and so this is our first example of an arithmetical function we may want to study several things so here's a so this is what number theorists do once you give me an arithmetical function you try to study this function now from many many different angles and one of them is how does how fast does this grow what is the growth rate of D of n we kind of try try and figure out how fast is it growing um second is um things like uh how does the sum D of n behave n less than x do we have any asymptotic behavior of these partial sum these partial sums of the divis function that gives us some sort of uh also some other information on how the thing is growing as a function and sometimes we can be more in Innovative and perhaps study what are called moments and take powers of the divisor function and try and study moment so called moments of the divisor function this kind of stuff is gets harder and harder it sounds very easy to formulate but it actually leads to some very interesting stuff very very interesting stuff and the story is not over yet and I'll explain that in a second so this is one good example of an arithmetical function oops so what do you do when things like that happen you just um I guess you'll edit the film right for all these bloopers what they're called right all right um yeah so this is one example of a device so let me give you another example um the oiler fi function which you probably so 5n is the number of JS less than n which are relatively prime to n correct that's the oilery function and um a question is is this a multiplicative function or not and um so is this multiplicative okay so well you um have to ask this question and answer this question by you can answer this question easily by um trying to First find a formula for 5n so here's a simple way of finding a formula for 5n so here I have all the numbers 1 2 3 dot dot dot up to n okay all the numbers I'm going to determine the probability that a random element between 1 and N is co-prime to n okay I'm going to do that so how how many elements are co-prime to n from 1 to n by my definition 5 n so the probability that a random number J less than n is co-prime to n is the number of such numbers divided by n right it's 5 n / n so that's the probability on the other hand what does it mean to say some number is co-prime to n it means it's not divisible by any Prime dividing n okay what's the probability that a random number is divisible by a prime P 1 over P right that's the probability and you want it to be not divisible by P so it's 1 minus 1 / p and you want this to happen for every Prime dividing n you don't want it to so each factor here represents the probability that a random number is not divisible by P and you want this to happen for every Prime dividing n therefore the two probabilities must be the same okay so this gives us a formula for five of n very quickly right and we see that fi of any Prime power p p is a prime okay p is a prime if I take five of P the J I see immediately it's 5 P the J / P J is equal to 1 - 1 / P so I immediately see it's p the J P minus one J minus one sorry j minus one thank you yeah right right p jus1 p minus1 that's what you get so now the question is is this function a multiplicative function yeah that's clear from here right it only depends on the um prime factorization and they independent so this is is multi is multiplicative and I'll leave it to you to check that it's not completely multiplicative okay it is not completely multiplicative that's easy to check because 5 p ^ 2 is p * P -1 it's not equal to 5 of P which is p - 1^ 2ar so it's a multiplicative function but not completely multiplicative so we seem to be meeting a lot of nice multiplicative functions but not completely multiplicative functions all right this is a very useful function to study it appears all over the place in mathematics not just number Theory and I I'm sure that most of you know the famous Oilers theorem if uh A and N are relatively prime then a ^ 5n is always is congruent to one mod n right I mean you must have seen this theorem somewhere sometime in life and uh it's very useful to uh know that fact uh okay let's take uh a third example um let's count the number of prime factors of n Prime div of okay number of prime divisors of n so for example Omega of 6 is 2 because it's divisible by two primes Omega of 12 is also two because it's only divisible by two primes etc etc Omega of any Prime power is just one p Prime so um I think it's pretty clear that if M and N are relatively prime the number of prime factors of MN is equal to the number of prime factors of M plus the number of prime factors of n right so this is an additive function and the question is is it completely additive answer is it completely additive no why H yeah exactly p p * p^ 2 Omega of p^ 2 is only one but Omega of p plus Omega of p is 2 right yeah no okay so it's a additive function but not completely additive and again here one would like like to know study how the function Omega of n behaves n less than x and see how it's growing and more generally we would like to take powers of the function and study what are called moments these are all things called moments h so we'd like to study things like that and the this is an important chapter the study of these things is an important chapter in what's called prob uh probabilistic number Theory so it's another offshoot of analytic number Theory let me give a an example of a completely additive function What's called the Louisville function Omega of n is the number of prime pow prime prime divisors counted with multiplicity or prime prime um divisors counted with multiplicity well what I mean here is if n is equal to P1 to the alpha 1 PK to the alpha k then Omega n is going to be equal to Alpha 1 plus Alpha 2 plus Alpha K okay so that's the counted with multiplicity I'm going to count before we only counted 1 + 1 + 1 for this Omega of n but now this Capital Omega of n will be I'm counting it with multiplicity so I plug that thing in okay so this is a completely uh multiplicative function uh completely additive function sorry completely additive okay so this is is completely additive it's clear because it doesn't it's counting the multiplicity now it's okay completely additive and again one could ask questions about the behavior of this function and how does these sums and moments behave and that takes you again into another chapter of probabilistic number Theory so I'm asking all these questions about the behavior of these things and so it might be interesting to come up with some technique as to how to approach all such questions but before I do that I should give you one more example give you one more example uh I guess it's number five this example is called the one mongold function the after the person who discovered it um very useful notation I suppose this function is defined as follows Lambda of n is equal to log P if N is a prime power P the alpha P Prime and it's zero otherwise because this function is in some sense it detects Prime powers and every time it's a Prime power it'll only pick up the prime though it won't pick up the power and here's the interesting thing about Lambda of n uh it is firstly is it a multiplicative function no is it an addtive function no right it's neither multiplicative nor additive however it's going to be an important function in in number Theory so we'll look at it so there are functions which are neither this nor that which are nevertheless important and we should we should study them too okay now the interesting thing is we notice that every number can be written as a product of prime Powers uniquely unique factorization so log of n is equal to Alpha 1 log P1 Alpha K log PK so that's obvious right I just took logs but now I can rewrite this very neatly as a summation over the divisors of n Lambda of D because this guy is going to be zero unless D is a prime power and whenever D is a prime power it's going to spit out log P but it'll spit out log P how many times as many times as alpha 1 times so this is the how it's but writing log n in this fashion it's like uh it's it's it's it's tant amount to like um uh writing a function as a Fier Transformer something like that so this is some you're writing log n as summation d of some function so if you think in terms of some integration this analogous to some integration and some function this is um some sort of transform of log n and this might this point of view will be useful in trying in in general in trying to understand ASM totic of summatory functions okay as we'll see in a second are there any questions so far I mean it's pretty straightforward so you got so the whole chapter one is um about arithmetic functions so I I I gave you a very quick introduction to chapter one and you can study a little bit more in detail at your own rate at your own speed okay so uh so that's summary of arithmetical functions uh let me say a few words about um what are called summation techniques and um the most important um technique is What's called the method of partial summation sometimes called OB summation after OB who discovered it okay so this basically it says let uh let a subn be a sequence of be a sequence of numbers complex numbers and F of t a differentiable function on um you know for for T bigger than equal T bigger thanal Z doesn't it doesn't you can restrict and relax these conditions but it's not um terribly important set a of x to be the partial sums of a sub B then the sum n less than x a subn f of n is equal to a of x f ofx minus the integral from 1 to x a of T fime of T DT so this is the first tool I am putting into your hands for the purpose of studying an an uh analytic number Theory so what is the tool the tool is it's telling you how to change a sum into an integral that's the amazing thing and you know integration is very easy you've got lots of methods calculus and so on so forth so this is the first powerful um tool that you have available as long as you know something about the behavior of the partial sums summation a n you can change a sum like this into an integral and you will see in a second how powerful this idea is in fact it's more or less animates all of analytic number Theory let's try and prove this proof is not terribly hard so um notice that a subn is a of capital N minus a of capital N minus one right I mean you some A1 to a n minus A1 to a nus one okay so it's clear so what we do is we will take this sum and replace a n by a of capital A of nus capital A of n this is this is obal's proof okay I mean he didn't write it like this I'll tell you his motivation later on U but that's this is his starting point so he starts out like this a of n minus a of nus one like so like that and now you do what you think you do you um you just write it like this fair enough now what I'm going to do is I'm going to change variables here and I'm going to let so as n is running up to X N -1 will run up to x -1 so I'll just change n minus1 to n again and this will be F of n + 1 and then I'm moving only up to x - one and now that I have that I combine this sum is going up to X this sum is going up to x - one so I um now there's a small issue about X being an integer or not so let's just assume for moment that X is a natural number okay so maybe I should have said first suppose X is a natural number so that we don't need to worry both these small idiosyncrasies okay so this sum is going up to X and this sum is going up to x - one the new term here is the X term and then I can combine both of these sums going up to x - one like so okay then I write this as the integral from n to n + 1 of fime of tdt well there's a oh sorry here's a m so here yeah it's a minus no that's a plus okay so this is a minus yeah you're right yeah uh so it's a minus that's right okay now make making the observation that in the interval n to n + 1 a of n is actually the same as a of t for T except at the end points but you know in the remon integral if if I fudge the end points it doesn't really matter so this whole thing then can be Rewritten as a of x f ofx minus the integral well the some these integrals are going from n to n + 1 and N is going up to 1 to x -1 so the whole thing is going up to 1 to X and here I have AF of T frime of T DT everybody okay with this proof and now you can I'll leave it as a small exercise for you to figure out that when X is not a natural number this is still valid you just have to do a small one more line of calculation okay so this is still valid still valid if x is is not a natural number so you get the this is the proof so the proof of this changing a sum into an integral is a very very important tool in analytic number theory in fact it I would say it animates a good chunk of it so having this in hand we are now um in a very good position to answer some of the questions I was asking about what is the behavior of those sum of arithmetical functions things like that so let's try and see what we can do with it is it okay now I'll rub out this proof here so let's look at a few examples let's look at for example um the following question summation and less less than x 1 / n what is the asmic behavior of this function let's look at that now I want to apply this LMA or this partial summation LMA and this is what I'm saying you know in in mathematics not just number Theory alone mathematics in general and probably in science as a whole um what you have to learn is you have to learn how to use the tools and if you just know one tool and you really know how to use it you can probably make a career out of it okay so this is one tool if you know how to use it you can probably make a care I'm no joking you know so um that way you look at this thing and you now try and figure out I want to find the asmic behavior of that I want to use this and change it into an integration so this is telling you somehow what am I going to pick for a subn what am I going to pick for f of n okay if you picked a subn to be 1 / n you will need some information on part that's exactly what I'm trying to do so why would you put pick that right so you should pick as subn to be something you already know so probably I should pick as subn to be one and F of n to be 1 / n so in trying to do this pick a of n to be 1 and F of f of T to be 1 / T in A's LMA okay then what happens summation n less than x 1 / n is well first thing what is AF x a of X is n less than x 1 right in this case so that's just the greatest integer function right everybody knows about this greatest integer function right so this is a of X which is the greatest in of x times f of x which is 1 /x minus the integral from 1 to X AF of X AF of T which is greater than Z of T times the derivative of 1/ T which is - 1 / t^ 2 right so this becomes plus t² DT so this is an interesting theorem in itself it tells me that summation what I was interested in all of a sudden got changed to integrals now the greatest in function X and the number X differ by at most one okay so um let me this a good time to introduce a notation also so let me just do that this is an important notation in in mathematics uh the Big O notation we say uh a function f ofx is Big O of G of x if there exists a constant Kappa okay such that f of x is bounded by K * G of X usually G of X is positive anyway okay but we'll we'll keep it like this for all X as X tends to Infinity for all for all X um sufficiently large or for all X good notation to have it's a very nice notation it might look like well you know you don't need this notation you can keep inequalities but you know sometimes in actually all the time in mathematics notation can be everything for example the idea of zero as a symbol of nothing is a very profound notation and that changed the world right created the decimal system change the world so notation it can be everything so here I'm going to introduce this big old notation um and this notation is going to help in not worrying about inequalities so that way I'm going to write X the greatest nature function X as essentially I'd like to think of it as pretty close to X but the difference is it's bounded by one so biger of one means it's actually bounded right biger of one that's the notation okay so X plus something bounded by one all right so if I write that for this greater than your X here then that's X+ something o one so now we can rewrite this as summation n l than x 1 / n equals well the numerator is now x + O of 1 / X plus the integral is now 1 to x t + o 1 / T ^2 DT H fair enough and now X is just one there plus o of 1 / X is O of 1 /x okay nice notation plus integral T / T ^2 DT that's just log T so it's just log X and then integral 1 to x o of 1 DT over T ^2 okay and so this is something bounded this is a convergent integral so this whole thing is O of one bounded so in other words I've shown that summation n less than or equal to x 1 / n is equal to this is the main term but everything else is bounded okay so I can write that down so this is this theorem is very nice because it gives me immediately without any difficulty um asmic information without too much work I just have to know how to use this opma so thus summation n less than x 1 / n is log X + o1 okay now if you look at this proof you can actually do better than this uh because you wasted a few things so we go back and check what it is that we wasted now I wrote my um function greatest than x as x +1 what I'm going to do now is I'm going to write this as x minus What's called the fractional part of X so this is my notation this is the definition um xus greater of X okay so this is what's called the fractional part of X so in this uh calculation we of course were able to get the ASM totic Behavior very quickly however um if we take a little bit of care and shove this in here so here now we will say x minus fractional part of x t minus fractional part of T and then let's just do this calculation one more time then what happens well the first one is one the second one is fractional part of x divided by X but that's still plus o of 1 /x so there was no problem there in the prev it matches the previous calculation but this time time this is T / t^2 that's still in log X but this time I get 1 to X of fractional part of T / T ^2 DT as a term and and before I just sloppily put o of one there and said this whole thing is bounded but now you can see that this is actually a convergent integral so so I'm going to rewrite this well I'm hoping you memorize this now so keep this here um so notice that so a little with a little bit more care with some care we see summation n less than x 1 / n is equal to what that I can't see on the board okay 1 + O of 1 /x plus log x minus the integral 1 tox fractional part of T DT over T ^2 okay and then I'm going to write this guy here as equal to the integral from 1 to Infinity fractional part of t DT over T ^2 and subtract what I added from X to Infinity fractional part DT DT s okay the advantage of doing that is this is a number now it doesn't depend on X anymore okay so this is some sort of constant C call it and now this guy here is an integral which goes from X to Infinity but the numerator is bounded by one the denominator is T ^2 therefore I can just bound it by the integral from X to Infinity DT / T ^2 which is 1 /x right so this is all 1 /x therefore this Compares with this error term here and so the final result here is that you get log X plus 1us some constant plus o of 1 /x now you may ask me well I've got an O of 1 /x here and I have an o 1 /x here isn't it 2 * o 1/x and the answer is of course it is but you don't care because this o means to constant so it doesn't you don't have to do that you don't have to put it twice that's a convenient notation again it's notation okay so this is better than before this number here is often denoted gamma and it's called Oilers constant if you go back to your work so what we have now is using ob's summation method we actually have a very interesting theorem the the behavior of this function is log X plus a constant plus something that goes to in zero very fast which is a very good theorem you'll see that it's very useful to have this particular theorem oh okay this is first example let's do another example um determine the asmic behavior of summation n less than x log M okay so again but for the able LMA you know we want to try and see what to pick is what a n is what what is f ofn so on so forth well again we will pick up a subn to be one and F of T to be log t fair enough H then apply oble sometimes you know in the literature people just say by partial summation that's what they're doing they're applying this LMA but then you have to figure out what was a subn what was the function because they won't tell you should be uh this is when you Fe read that phrase in the literature that's what you have to check so now we we know how to do these things you just go log n so a of X is greater than of X log x minus the integral 1 to X greater than Z of T times the derivative of log T which is 1 / T right okay so this time we're going to do the same trick as we did before greater than Z of X is equal to x + o1 something bounded so if I do that what do I get I get x + of 1 log x minus the integral 1 to 1 to x t + O of 1 DT over t^2 Okay so this time you're going to get X log X pardon me oh what do I have oh just T sorry yeah not t^ squ sorry yeah correct thank you so X log X Plus o of log X right minus the integral of well t/ T is just 1 and the integral of 1 is x - 1 right and then um I have an integral big of 1 DT by T which is Big of log X okay now keep in mind that so what I have is here x log X - x + 1 plus o of log X Plus another all of log X but that's all of log X again and log X is bigger than one and so this term is irrelevant now see how this old buiness works there's no point keeping that silly one there because that silly one is bounded by log I mean it doesn't make any sense for you to carried it anyway so you have this plus o of log X so you have a nice formula again here which I will write here as summation n less than x log n is X log X - x + O of log X and you may ask hey maybe you could do better like we did there and the answer is yes you can and that's called the oiler mclen Su formula you kind of kind of keep on refining the thing a little bit more and more and you can do better than that but for the for the purpose of this initiation into analytic number Theory maybe this is good enough H any questions so far on this stuff okay now these might look boring to you but but uh Believe It or Not uh these are actually um quite important results in um number Theory and uh it has to we have to credit The Genius of chich Chev who recognized that these simple silly results can give you information about the distribution of prime numbers so let me say a few words about that now um practically all of number theory is preoccupied with the distribution of prime numbers prime numbers as you know are the building blocks of all natural numbers and just as physicists St study the atomic structure uh of nature because the the atoms protons neutrons and so on so forth are the building blocks of all of nature similarly prime numbers are the building blocks of all of mathematics so if we want to study mathematics it makes perfectly good sense to be studying prime numbers because they're the building blocks of all the numbers and in order to understand prime numbers we'd like to ask various questions about them that's why number theory is is preoccupied with that so uh one of the first uh questions about prime numbers is um is um how are they distributed so let let Pi of X be the number of primes less than x now I think most of you know that there are infinitely many primes you know this usual ukian proof you if there were only finite menu you multiply them all together add one and then it can't be um you know it has to be divisible by one of the primes that you started with but can't be because it means it divides one and there's a contradiction right this is the proof that goes back to ukp um okay in a second I'll give you another proof of that and then you may ask me why do you give another proof of that well it's because uh as I said at the beginning it's not results per se that we're interested we're interested in methods so if you give me a new proof of something else that's very valuable because that means you've stumbled on a new method that's why these are important okay so we now look at Pi of X number of primes up to X and I believe it was G who first conjectured that Pi of X is essentially asmic to X over log X I mean he made a a more precise conjecture but I don't want to talk about that now but so this was the conjecture that Gus made apparently as a teenager okay so so um this is what uh the story is the question is whether or not um we can prove this so this is a conjecture of G and um chbf in the 1850s I think I might be wrong on the dates but roughly around that time uh showed that there exist constants A and B positive such that such that Pi of X is less than BX over logx and is bigger than ax over log X so at least it grows like that whether you know whether or not we can prove a ofx is ASM totic to that is another question but it grows like this and he also he he struggled very hard to prove this he kept getting better and better numbers this these numbers he started making them closer and closer to one and then he proved the remarkable theorem if the limit exists oops X over log X if this limit exists then the limit is one so he managed to show that the the key idea or the key part of the problem is to show the existence of the limit and all of these two results both of these results he proved using nothing more than Abel's Lama okay so it's probably a good idea to show you that and maybe stop for today and then continue on Friday H so how does this work how do you how do you do that well the the secret is here the secret is here apparently um so let's go back let's recall the W mongold function let's recall that H remember Lambda D again Lambda D spits out log P whenever D is a prime power and zero otherwise right so so we know that so this is somehow a not quite but somehow like a characteristic function of prime Powers except it's weighting the Prime with the log P it's a weighted fun characteristic function so on one hand we know sum n less than x log n from this so we know that on the other hand we know that log n is this therefore we put that in here this equals summation n less than x summation D Ides n Lambda D put it in there and now we interchange summation natural thing to do in in mathematics when we two two sums right if they're absolutely convergent you can interchange so D is dividing n and n is less than x therefore D is less than x and inside I'm counting n less than x d ID n 1 right that is how many numbers are there less than x which are divisible by D well they have to look like d * T and D * T has to be less than x so T has to be less than x over D therefore this number is nothing but the greatest integer of x overd right therefore this is equal to summation D less than x Lambda d x over D so you have this very remarkable connection between the two now something we're getting very close to some information about primes here okay now you'd like to do the obvious of removing the square brackets like to do that and so so actually at this Point Chev got a bit stuck he knew he knew that this identity on one hand you have this silly thing coming from just calculus and on the other hand you have this connection to number Theory and somehow you should be able to get some information on Primes from this identity it's too good to be true therefore you have to be able to get some more information from this thing so um the problem is of course he needed some information on need a Bound for this function what he call S of X which is just D less than x Lambda D so this is his definition of s of X it's just the partial sums of the Lambda DS if I can so he wants to know how to prove how how to how this grows Okay so let me just say a few words about that and what he did order to talk about this so it's it's actually you know when you have a good idea uh and it works at least a little bit and then you get stuck it's probably worth the effort to push it forward a little bit because it was a good idea so now um we have here uh we suspect that if the number of primes or number of prime powers in general is about o x over log X and we are waiting each prime by log of D most likely this is like o of X Perhaps Perhaps this is the the case let us suppose so for a moment I'll come back to it in a second and if that's the case then it allows me to handle this error term then summation D less than x x Lambda D / D um plus o of x equals this guy X log X plus uh sorry minus x + log X so we get an equality okay and now what would you like to do we would like to divide the whole mess by X so if I divide this by X I get o1 this by X I get log X this by X I get minus one but minus1 is all one you've already you haven't told me what that thing is so what's the point of carrying the minus one there right it's one and then divide by X that's log X overx but log X overx goes to zero or one is the larger error term so you just put o1 okay so you end up getting this remarkable result okay from that so the only question is what about this because I assume this in order to get here and let's see what chubby ch how he did that he very clever idea so chbf in the early days of this whole question recognized that s of X which is D less than x lamb D is an important function to study instead of the Prime Counting function Pi of X is more natural than Pi of X which is the prime counting function and I'm I'm going to leave these as exercises Now using AAL LMA one more thing before I do this and you also Define Theta of X which is just the prim is less than x log P okay so what's the difference between Theta of X and S of X well when p is a prime you're going to this is going to spit out log P so that's Theta of X is in there so clearly clearly Theta of X is less than or equal to S of X all the Primes are in there but on the other hand what's the difference between the to well it's going to this is also counting Prime Powers so it's counting squares of primes cubes of primes and so on so forth and how many squares of primes are there up to X at most root X and what's the contribution of each of those things at most rootx log X how many cubes are there at most x x to the 1/3 and what is it going to contribute log X so it's X the 1/3 log X so you just keep on Counting how many power there could possibly be and it isn't very difficult to show that um s of X and Theta of X are pretty close to each other and they only differ by something like that okay so it's a small exercise for you to do so s of X and Theta of X are very close together and the error term is X half log X because those are the prime Powers Prime Powers cubes and so on so forth right okay so you get that um so what um Chev proved was um Pi of X being asmic to X over log X is completely equivalent to Theta of X being asmic to X which is completely equivalent to to S of X being ASM totic to X and this these this these assertions are all exercises in alal LMA you just have to see how we put it together it's it's very straightforward so exercises in ob's Lama so that same all LMA that he used so if I want to prove this it suffices to prove this or it suffices to prove this so this is what he was after once he got that now um let's go back and see how he actually proved this well um it's a very brilliant idea he made the following observation if I look at the binomial coefficient 2 N choose n this binomial coefficient you can see that if I take the binomial expansion of 1 + 1 ^ 2N this is one of the terms in the expansion therefore it's clear that this is less than 2 2N okay so you get this inequality and what is so great about this particular middle binomial coefficient well it is divisible by all the Primes that lie between n and 2 N because all the Primes that lie between n and 2 N appear in the numerator but they're not cancelled by the thing in the denominator clever huh so this is the kind of this is the kind of um observational skills that you must acquire in if you want to call yourself a scientist or a mathematician right you have to kind of make these everybody just looks at these things and just says yeah it's interesting it moves on but the the real scientist will say hold on this of course it's obvious but there's something interesting going on to see something interesting going on in the obvious is what we have to cultivate okay so here we have all the Primes between n and 2 N as divisors of this thing and therefore if I take log so this number is less than this number so I take logs summation log P between n and 2 N okay this strict inequality is less than 2 N log 2 just take logs whatever this binomial coefficient is less than 2 2N this is a divisor of that binomial coefficient therefore this number has to be less than this take logs and you get this and in this in his notation with this Theta thing so this says Theta 2 N minus Theta of n is less than 2 N log 2 iterate this one more time Theta nus Theta n / 2 is less than and log to and then keep on going add them up they cancel telescoping sum and so low and behold you'll get Theta 2N is less than 4N log 2 in other words uh he's managed to show that Theta of X is O of x okay Theta of X is o x so using that he says well s of X and Theta of X don't differ by very much they differ by root X therefore root X is much smaller than x so if I got Theta of X is O of X so is s of x o of X because x to the half is much smaller than x Okay so so this is now done okay now if you have this you can see that um this first half of the inequality comes through so having yeah well Theta of X is all of X means this right for some it's that so in other words and I can split this up into into um P less than rootx log p and p bigger than root X log p and recognize that this guy is all of rootx log X and then this guy is now Pi uh so uh summation log p rootx p x is bounded by KX + O of X2 log X and now here we have a a lower bound U so this each of these terms here is at least log of rootx so 12 log X times the number of primes from X number of primes of to root X is bounded by KX plus o of X2 log X okay and now keeping in mind that Pi of rootx is the number of primes that up to root X and that it's O of root X it's a stupid estimate but let's put it in any way you see that Pi of X now is less than some other constant b x over log X I hope this is all clear you can see the power of the O method the Big O symbol is very convenient and you don't get bogged down by trying to keep track of constants when it's not necessary of course sometimes it might be necessary but in this case it's not it's it's to your advantage so essentially this is irrelevant you get Pi of X log x * a half is bounded by some KX this is also smaller than this therefore it's okay so therefore Pi of X is less than BX over log X so he manages to prove the first estimate you in this fashion using only that little trick with the binomial coefficient okay and then the other part is done using this with the other part for the lower bound we have the following so we have summation log p over p p less than x so from here I want to go to only primes there are prime Powers also here but the Prime power contribution is very small compared to uh in fact the Prime power contribution by the way is a convergence series because every time see when D is a prime it's a log p over P but D is a prime power it's going to be p^ s p Cub so so forth but summation log p over p^2 converges log p over P CU converges so all that stuff is a convergent Series so it isn't difficult to see that this from Star we have this equality ASM totic and therefore if I this what is this o of one it's a certain constant isn't it this this this thing so if I pick choose um some Delta sufficiently small so that or if you like actually it's this is the way you do it um choose a sufficiently large choose a large so that if I take X over a so up to X it's log X + o1 up to X over a it's log of x over a + o1 take the difference plus1 right so what have I done keep in mind that this o one is a fixed quantity here I'm going to choose my a really gargantuan so that this is bigger than that thing so that I can say it's bigger than some constant c0 so the sum here in between these two intervals is bigger than some c0 here and then what do I say I say that this is a decreasing sequence the largest term is really at the at this lower end so the and and the and the sorry the smallest term um yeah the larger term is is is is at the other end so now you can see that um log of x a / x a times the number of primes between x - x/ A is bigger than some constant c0 and so from from here you can see that Pi of x - PK of x a is bigger than a constant x / a / log x/ a and therefore since this is a lower Bound for the number of primes up to X you end up getting the lower bound there okay so you end up getting the chbby CHF theorems by just using two ingredients one is ob's Lemma and the other is that binomial coefficient trick but putting all of these things very cleverly together okay so I think this is enough for the first day um especially I think it's quite a bit of stuff uh gives you an introduction of how to use the thing so make next time we meet which is Friday I guess I will try to uh give you more um details uh and how to use these techniques and um understand more about prime numbers and other functions are there any questions or anything like that you would ask okay um if you have any questions you can always ask them privately to me um or bring them along for next time okay