Terrence Tao - Structure and Randomness in the prime numbers, UCLA

this is ABC flora yeah so I'm going to talk actually not so much about my own work they'll come up a little bit but just about the theory of prime numbers in general the number theory which is when my favorite areas of mathematics is of course not the only area of mathematics but it's it's it's one of the major ones code malar for instance I did a lot of work in in number theory so I'm quite honored to be giving lectures in his name it's a very old topic it's a huge topic there's no way in a public lecture like this I can tell you everything that's going on I don't even know everything is going on so I'm going to give this this very very quick tour where I like to describe it is it's like visiting Paris and only seeing the Eiffel Tower in the active tree off you know it's not really the full story but it's it's something ok so but it's some other prime numbers and just remind you everybody what a prime number is a prime number is any natural number bigger than one which can't be factored into two smaller numbers and so over up there we have the first few prime numbers and they just go on and on and on and on the biggest one that we know of is is down there okay so we found a lot of primes they've been studied for a long long time in fact the ancient the ancient Greeks were the first people have cited him systematically Euclid even Euclid in his elements had a several thousand the prime numbers and they approved the first two really important theorems about the primes and there's a starting point for everything else so the first thing we know about the primes is what's called the fundamental theorem of arithmetic and it's it says that that every number every natural number bigger than one might not be prime but even was not prime you can always factor it into primes every number is either prime or the product of primes and there's only one way to write every number as a prime as a product of primes it's other than V arranging so 10 is 2 times 5 or 5 times 2 but that's the only way to split 10 into primes that's the fundamental theorem of arithmetic the other major theorem that they proved it's called Euclid's theorem so you could prove many theorems but this is the ukís theorem that the primes go on forever there are infinitely many prime numbers the times never stop ok so these are two basic theorems in greek prime number theory so the fundamental theorem that every number can be split up into primes one way to think about it is what it tells you is that the prime numbers are very important to integer multiplication they're they're likely atoms if integers like molecules then prime numbers are like atoms the atomic elements of of energy applications every molecule is made up of atoms you know carbon dioxide co2 and similar similarly every integer is made up of it's made up of primes in exactly one way and so here at couple numbers and their prime factorizations by the way one this is by the way the main reason why we don't consider one a prime number so of course one has no factors other than itself so we're saying why don't we call one prime well if we call one prime then there'd be more than one way to split up a number into primes like the number ten could be two times five but also two times five times one in two times five plus one times one and you wouldn't have a good unique prime decomposition and so you wouldn't have the fundamental theorem of arithmetic and we really like the fundamental theorem of arithmetic so we have demoted one because we do not consider the prime anymore okay so you're clear theorem is a theorem that they're infinitely many primes and I want to show you the proof of it because it's a beautiful proof it's one of the first proofs you know in mathematics but it's still a classic it's a real gem it's a it's what's called a proof it's a reductio ad absurdum proof a proof by contradiction you prove sign is true by proving it it's not false it's an indirect argument so I just show you how it works so you want to prove that they're infinitely many primes so okay so so you suppose the word okay suppose suppose that Euclid was was wrong suppose there only finitely many Prime's in the world but after a while they just stopped so if the sake of argument suppose that two three and five or prime then no further Prime's suppose that they were you can only find finitely many Prime's then what you can do is they can take all those Prime's and multiply them together so if two three and five or all the times in the world you multiply 2 times 3 times 5 you get 30 and then you add one you take the product of all these primes you add one more is your new number in this case 31 okay so you take all the primes in the world more plump together add one that gives you a new number now why do you do this you do this because this new number is 31 is bigger than one clearly and because it was it's one more than a multiple of all the primes in the world it's not divisible by it's not divisible by any prime okay it's not difficult by two three or five millimeter one okay so we have found a number which is bigger than one but it's not it can be divided into primes but the fundamental theorem of arithmetic tells you that every number can be divided into primes and so because we know the fundamental arithmetic we have each a contradiction so the copy finally many Prime's and hence there must be infinitely many Prime's that is Euclid's proof so that's an amazing proof I mean it's it's it's it's it's so way you know it it takes a while to get useless of indirect type of arguments there's a famous quote by the British mathematician G H Hardy about this you said that reductio ad absurdum which you could love so much is one of math additions for mathematicians finest weapons it is a far finer gambit than any chess gambit so in chess you may sacrifice a pawn or piece to gain some advantage but a mathematician offers the entire game and still wins so okay so it's it's it's a great technique okay so these are the two basic theorems okay so that's great but actually there's a lot more to these theorems than just the fact that they're true so for example at the fundamental human weapon dick tells you that every number can be factored into primes in principle so given any number you know 1237 given enough time you could figure out how to factor into primes but no one knows how to factor large numbers very quickly you had to take a really big number less 100 200 digits long eventually you know you could factor in the primes but it would take you an extremely long time if it's 100 digits long it may take you longer than the age of the universe before you finally factored it and this is actually very important because there are there are many algorithms there are many cryptographic protocols codes that are used daily you know and such the RSA algorithm which i think is used in ATM machines actually which which the reason why they can't be broken is because no one knows because the they use very very long numbers which no one knows how to factor into into enterprise if I didn't know how to factor these large numbers into primes you could break these algorithms but no one knows how to do that and so we believe these algorithms are secure at least for a moment so in fact the fact that we don't actually know how to to execute this fundamental theorem in practice is actually very important it's a similar story of Euclid's theorem we know that there are infinitely many Prime's but so in principle you know if if you wanted one trillion primes eventually you should be able to find one trillion Prime's you should but no one knows how to a queue just deliver all these prime numbers just so other than just very laborious ly counting them there's no recipe to find say the millionth prime the billion of prime trillion to prime other than basically by just by counting one by one it's it's not like other sequences like the square numbers ok the million square number I can tell you what it is it's a million squared but the millionth prime number is I can't tell you so quickly ok so in fact it's quite hard to find really big prime numbers the largest prime number that we actually know is this guy 2/3 43 million 112 thousand six hundred nine minus one it's a huge number almost 13 million digits long there's a Australian radio host actually Adam Spencer you may know him as a breakfast show and he once gave a talk and he had some mathematics in it actually and he showed this prime yeah he had some some students come up he had printed this prime on this printer papers all stop window pick which is all perforated and then they had the students unwrapped the entire the digital world off this primary event all around the room it's a huge number it was showing me that it was shown to be primed by a big internet search it's called game screen internet Mersenne prime so survey I said it was a it was a project that distributed the tasks among you know thousands and thousands of computers across the Internet okay so primes are to get a hold of you know as I said it's hard to find say the millionth prime number and because of probably doing something funny I mean it's a the kind of irregular as I said there's no good formula for the nth prime number and they tend to behave very randomly and we don't really know what patterns exist inside the motor patterns don't exist inside them because they look so much like like random noise and it's because of this that the primes have been much more difficult to study then was first and then one might think at first there's a lot of very simple questions about the prime numbers that even after thousands of years of work we still don't fully know how to answer so the one the simplest ones actually is what's called a twin prime conjecture so we know their infant many Prime's but we don't know whether the infinitely many twin primes so a twin prime is a concept invented by the ancient Greeks is is a pair of primes which differ only by two so a P P plus two like three and five are twin primes 11 the 13 open primes there are not as many twin primes as Prime's but the stool autocrine primes you're the first few twin primes and we think they also go on forever but we don't know the largest pair of twin primes ever found is is this pair down here sort of defined by a computer search a few years back but for all we know that's a cue the last one there may be normal we think they go on forever but we don't know actually how to prove that okay so there's a lot of things that are very simple about the primes very basic questions that we still can't answer and it's because they behave so randomly there's a quote by the Hungarian mathematician poor Irish about this so odisha so Einstein met a famous quote that God does not play - the universe he was talking about quantum mechanics support that I said well yeah ok God when I'll play - the universe but something strange is going on with the prime numbers now the prime numbers are not random I mean there's only one set of prime numbers in the world the you don't have to row any dice Oh flip any coins to create the prime numbers but nevertheless they do behave a lot the Prime Minister --have as if they were just some some random sequence of numbers in many ways ok yeah so we do believe the price behaved randomly in a number of ways and this is actually a very important belief for us because it it underpins us our confidence in a lot of a lot of capital graphic algorithms in particulars having good public key cryptography which is another complete graphic algorithm which is used everywhere if you're if you're buying something over the internet using your credit card you're correct and you and you're using a securing connection your credit card is being encrypted by a public key algorithm okay a lot of lots of things on the Internet these days are encrypted of course people can hack in and so forth but but when when the security of the Internet has been compromised it's never because of the codes is because of something else stop your programming or some human error or something but the mathematics is secure qaddafi is this complicated subject you know I mean you can be congest because you've a good code doesn't doesn't guarantee everything else is secure like you had a nice lock on your door if the window is open it doesn't help but anyway we do at least know that these locks are pretty strong ok so let me explain what public key cryptography is because it's a beautiful concept and one which which initially you might think doesn't you shouldn't work at all so I'll give you an analogy first a physical analogy to what to public key cryptography is suppose you have two friends in and in cryptography the two events are always called Alice and Bob I don't know why that's just the way they are this way this gave two friends Alice and Bob and Alice has a box of something very valuable and I'm going to called G for reasons that well it may become clearer later so she here's a box called G and he wants to send it to her friend Bob the defender was really far away maybe she lives in Australia Bob does in America or something so she has to mail it ok but she doesn't completely trust Australia Post and she's worried that so that someone handling this box is going to open it and take out what's inside ok so she wants to protect the box now of course what you can do is that you can lock the box okay so she could put say a padlock on the box and then now people can open the box let's assume the box is unbreakable just for simplicity so now you can you can send a lock box over to Bob but that doesn't help Bob because Bob would then receive a lock box and he doesn't have the key for that box okay so you could also try setting the key but Australia Post if they can pick up a box signal to pick up the key and so how would you so if yeah how would you be able to send something securely with Bob in such a way that no interest no no one who's interested intercepting can take out what what what's inside so this is basically the the public key Kakaako your problem so it's not really obvious you can even do this but you can there are many ways to do it in fact so I'll give you one solution so one solution is called a three-part protocol so suppose Alice wants to send box G to Bob so she does what I said before we lock the box we put a lock on it I'll go lock a and now we have a lock box which are called G to a so we have this lock box and we send we send it to Bob so Bob now receives a locked box Alice keeps the key okay oh this is the only one with the key a okay well that doesn't do Bob any good he has a he has a lock box so what he does is that he takes that lock box and locks it again okay so he picks up his own padlock puts another lock on the same box closet B and now we have a W lock box due to a B with Alice's lock and Bob's lock on on the box and he sends the W lock box back to Alice now why would you do that well so Alice of course can't do anything about Bob's lock right goes Bob keeps the key but she can do something about her own lock she could now take her own lock off okay so now she takes off her own lock from the box now there's only bulbs lock left and now she sends the box back okay and now Bob gets the box with his lock on it and then he can unlock it and get back the box okay so this is a three part protocol you have to send it back and forth three times but it works and it is secure okay if you have someone in the middle and in cryptography the eavesdropper always called Eve if you have an eavesdropper Eve or she ever sees his few locked boxes she never sees the unlock box okay so this is the this is the three-part protocol I've heard that this is actually used actually in by some by some military people to transfer state sensitive documents at least that's what I've heard I've no proof anyway this is this is the physical protocol but you can do the same thing with numbers okay suppose you want to send instead of a box you want to send a number you know a credit card number Swiss bank account number there are many numbers that you don't want us to you want to send securely okay so we have a number G and you want to send it Alice wants to send it to Bob C by email and she doesn't want anyone watching the email to get the code you can do it too and this is exactly the same protocol works and it's called the messiyah your crypto system so the way it works is that okay so first of all they they talked beforehand and they have to agree on a very large prime number and maybe they think one of the prime numbers I showed you before so you pick a very large prime number it doesn't really matter what number it is as long as it's large and prime okay now that's public so even the eavesdropper will know that this prime number P but this won't this this won't help that use dropper so you pick a large number P now you Alice has has has her secret number G so she locks it and the way you lock it is that you raise it to the power a so you HG uuuuu easily to the exponent a butt and then you and then you divide it by P and take the remainder so that kind of mixes up giclee a quite a bit if you don't and then she just sends that remainder G to be a modulo P the remainder modulo P that scrambled number to Bob it's important you take modulo P because we just take you to the a you can you can start taking roots and logarithms and recover G so you have to scramble it but by doing this modulus so it should sense two to eight to be to Bob so okay so Bob then can't unscramble G because Bob doesn't know what a is so then Bob locks the number again by taking G to a and raises it to another power you take pics it's only secret number B raises it to B now you have G for a b mod p and so that's another scrambled number sends that back to Alice Alice can't do anything about the B but Alice can take an eighth root there's a way to take an eighth root of a number of a remainder mod P which I won't talk about but Alice can take in the eighth root of keep the a B gets back you to the B sends it back to Bob and now Bob can take the beef route of of of you the being gets back gee okay so it's exactly the same algorithm as the physical algorithm just implemented numerically and people actually use this that there are actual cryptographic protocols out there you know used daily which used exact basically this type of algorithm so yeah so this is this is a very practical algorithm now we believe it's secure oh yeah okay yeah so the the set that already you need the prime otherwise you can use logarithms to correct to crack the code yeah so we believe but we can't prove yet we believe that these algorithms are secure that if you take okay if you take really big numbers G and P and so forth and you use this algorithm then an eavesdropper can't crack the code in any reasonable amount of time it turns out that the NewsChopper has like an infinite amount of time eventually she can crack the code by trying all the GS and A's and B's and eventually finding a match but that's got brute force but a brute force would take trillions of years we believe there's no practical way to to crack these these these these codes but we have no proof of this there is a very important problem in mathematics called the P equals NP problem which is again I could give a whole talk about P equals NP but peek was empty roughly speaking or P not equal to NP actually roughly speaking is the statement that there exist problems that are genuinely hard the easier state but hard to prove how hard to solve and and and cryptography is it should be an example of this codes that are easy to generate but hard to crack but we don't know how to prove this the claim a sincere which is one of our sponsors here actually I've made seven seven different prizes for seven major problems in mathematics each of a million dollar prize attached to it and the P equals NP problem is one of them so okay but no one has sold that only one of the 7s being sold so far ok but we do have some partial progress so just give you a taste of the type of thing that we can do as it was out of my friend John Gorgan so he showed that so in this protocol the East drop never sees gee the es over just sees these three scram numbers due to the age is the beach is a B and so what what my friend began showed is that is that these numbers that the East Java sees there was called uniformly distributed what I means is that Allegiant if you just look at the most significant digits forget about the lower the lower digits but just the biggest digits the biggest it just looked just like random bits random noise random digits and so that's all the you shoppers sees and so what that tells you is that the East dropper only sees the most significant digits of these numbers she can't she can't do anything with them because they just look at random noise and and the only thing you can do random noises generate more random noise you can't reconstruct anything so that that's evidence as partial evidence of this that the algorithms secure but it's not there's nowhere near a complete evidence because of course there's his least significant digits as well which are also important so we don't know that okay okay so alright so that was a demonstration of some sort of an honest connect to the crimes so the promise to behave randomly in many ways but in many other ways they don't actually so I told you before that I have no way to tell you no quick way to tell you exactly what the millionth prime is the billions primarily at the prime the entha prime number I have no quick simple formula to tell you what it is but and it's because the primes fluctuate so randomly but interestingly the primes do have a very important approximate formula for the nth prime one that's doesn't give you the N time exactly but gives you something very close so the something called a prime number theorem proven over a hundred years ago that says that the mmm number is not exactly equal to anything we know of but it is approximately equal to n times the natural log of n so that's so the millionth prime is roughly 1 million times the natural log of 1 million which i think is like 10 million or something so that's that's a remarkably good approximation in the background here we have three lines no so easy to see but the the dotted line I think is there is the pickiest the graph of the nth prime so this is n this is the nth prime and the solid solid line is the graph of n log N and they're pretty close you know if you look at at the millionth at the millionth prime number and you look at million log 1 million to take there within like two decimal places of each other this is this is that the prime number theorem there's a cure more a more precise formula for the nth prime which is more complicated than n log n which I won't write down here there's a more precise formula which should be even more accurate than the prime number theorem but we don't know that either so there's sign so one of the other seven millennium prize problems I mentioned it's or something called the Riemann hypothesis which I won't state here it's a but what it says is well what it's it's equivalent to the statement that there's a very precise formula enter prime which is accurate to really high accuracy if you take say the millionth prime number you plug in this formula you get accuracy two by six or so to four or five significant digits the then the formula that the Riemann hypothesis predicts is is this is the dashed line you can't really see it because it is lining up with the dotted line so well it's an extremely good prediction okay so that's another million-dollar price problem I don't actually recommend you go home and try these that they're quite hard but anyway okay so I show you so you can take a thing of the prime number theorem as a really souped-up version of Euclid's theorem Youkilis team tells you that there are the prime is gone forever the prime number theorem tells you sort of where they are not only they're infinite but sort of where they are and it's it's really an amazing theorem it's one of the it's a it's another landmark theorem in the subject and I want to show you the proof or not the whole details but just have an idea the proof in part to show you just how much mathematics has advanced from between forms so Euclid's day to you know say 1890s 1896 which is which one this being was proven it's advanced more since then but I just want to show you that this is this one theorem so it's proven by a much more modern method than then proof by contradiction so it works like this okay so what you do is that you want to understand the prime numbers 2 3 5 and so forth so the way you do this is that you actually create what I call you a sound wave or more precisely a function and the functions name as the name is called a mod Rheingold function and this is a wave it's a wave of sound and it's it's a mathematical wave and it's it's it's loud when time is a prime number and it's quiet when time is not a prime number so is it it's a sound wave that encodes the primes so a time one is quiet time - it's a noise time three is the noise four five six seven eight nine ten eleven so there there's just some some sound wave okay so you create this function and then what you do is that you you listen to this function now you listen to this function mathematically and what that means is that you analyze this function by taking what's called a Fourier transform which is one way of listening to a wave actually technically you take something closely related to a lot of Fourier transform Mellin transform but basically a Fourier transform much like the ear actually if it is a sound wave we will break it up into notes the ear actually has some organs in it which do things like Fourier transforms so you listen to this wave and you you you hear all these notes okay and there's actually a formula that that in fact tells you what these notes are these notes have a name the notes you get here in this music called the zeros of some code the Riemann zeta function which I want to find here so every zero of the Riemann zeta function is some patent this is an oscillation in in in in in the prime numbers on the back here the graphic here what this picture is plotting is the reciprocal of the zeta function so every time the zeta function is zero the reciprocal goes off to infinity so every spike here is one of the is one of the zeros with zeta function and they go on forever so this is music with all these notes so the problem is that is that if there's a really loud note in this music then what happens that there'll be a big fluctuation in the in the formula for the nth prime number and you would see that the you that the prime number theorem will not work there be a huge fluctuation so the certain loud notes which would destroy everything and so the whole hope the whole game is to show that certain really bad notes don't appear and this this is a bit tricky and I won't say how it's done but once you have that you then use some modern mathematics you have to use either for analysis or a tool from complex analysis called contour integration but once you you you know that certainty would not appear you have what's called a zero free region and you use some summer advanced analysis then you can prove this pan number theorem and if you had if you knew more about these notes then you could prove more than the prime number theorem and in fact the Riemann hypothesis is normally phrased as a statement about where where all these notes are these zeroes but I want to talk about that okay so so the prime numbers are really a funny thing I mean are they random are they not random the sort of a mix of both that's sort of what makes it so fascinating so on the one hand we have the prime number theorem which is that there they have large-scale structure so as you keep going on they fluctuate a little bit but but if they happen they have a fairly uniform distribution but if you look at small scales they look quite random so you can see this in this background picture here so what these black dots are prime numbers so what's going on is that we just have ordering numbers one two three or five just as pixels just all the way down down the screen is like 20,000 of these things and every black dots are prime so I don't know if you can see it but there is there are two black dots on the corner there that I Jason to each other those are two and three and then the next the next black dot next is five and seven and there's a gap to get to 11 and so on and so forth so you have all these black dots and you can see that you know they're just so strewn around randomly they get slightly sparsa as you go down there are fewer and fewer of I mean there's still quite a lot of them I mean take on forever but they get a little bit sparser as you go down this is comes in the prime number theorem the gaps between n log n the gaps between adjacent numbers in n log n thickly it goes a little bit so slowly they get sparser and sparser here there's quite a few down here is there sparse but otherwise they did they look kind of random you know there's this though suspect that they sort of go around in various patterns but no there's this they're not all that organized well unless you look at them a bit more closely because there are some patterns here that that you can see so example Prime's tend to be odd there's only one only one exception to and that shows up here so every other column in this picture is this all white this laser pen can show you but you know I mean only at the very top left corner can you get to adjacent crimes i otherwise you have these big white columns or the the primes only occupied every other column here so they're all odd there are other patterns like this they all they all happen to be adjacent to mobile of six every crime is either one less than up of six one bigger than mobile six but that's it or two exceptions two and three but every other number five seven eleven so what they're all next to multiple six is a good exercise to see why so that I think I'll respond to the fact that every so often you get these the thick white piece you get these thick white stripes which this laser pen is not able to to point out unfortunately but yeah so numbers which will remainder two three or four motor six can't be can't be Prime and those are these thick white stripes you see here and then there's couple other things like if you look at the last digit of a prime it's always either one three seven or nine with two exceptions two and five but other than two and five every other prime ends in one two three seven or nine and that corresponds to some other white lines here you can see know what but the Liesman can't show there's a there are these diagonal lines as well then goes across multiples of seven or eleven though there are certain there are certain always long lines and things which are which are free of crimes and that's it's just part what the prime is do so even while they're they look random that there are some some patterns within them but not enough to make them sort of really organized I just just just enough to sort of make things interesting so you've got this weird combination of large-scale structure like the prime number theorem you've got local structure like prime is being odd and next to em up of six and so forth and then other than that they seem to behave randomly so you have these three different features of the primes and over the years what we've learned to do is we've been able to understand these three features well enough to so put them together and we can't answer everything we know everything we want to by the primes but we can answer some things so there are some results we can do but just by combining these sort of phenomena making them more more MORE quantitative so just to give you some examples so one very famous theorem is the Nagato's theorem it's okay so the statement is that so that is that every large number every large odd number and of course it's not prime necessarily but you can always write every large number as the sum of three Prime's even if it's not a Q prime itself so he was trying to solve what's called go box conjecture so go back conjecture in fact Christian go back a few hundred years ago or 250 years ago conjecture that every odd number in fact bigger than 5 should be the sum of 3 or primes to 3 prime so like 11 should be what is it 7 plus 2 plus 2 every odd number should be the sum of 3 Prime's also every even number bigger than 5 should be the sum of two primes so there's the first two conjectures the odd go back injection the even go back injection so we don't have it with either of these but we were in some sense we've almost proved the odd one because vinegar said well maybe not every odd number is the sum of three Prime's but every sufficiently large odd number this is sum of three prime so if you go making them a big enough it's your guarantee to be sum of three are Prime's that's the great theorem actually uses it uses pick the kitchen sink actually but to prove but but of course there's a sufficiently large business of what a sufficiently large mean then a grad off in his when you prove this he didn't say but but later mathematicians went through has proven tried to work out exactly what's officially large meant and and they've been refining this over the years the most recent result in this direction is by these two Chinese mathematicians of Leo and Wang who showed that any large number any odd number bigger than tendril of 1346 is the sum of three are primes okay on the other hand using a lot of computer search basically it was also it's also known that any odd number between 5 and 10 to the 20 is somewhere for your primes so as far as a method is concerned this problem is basically solved there's only a finite number of cases left to check but unfortunately in practice that's not good enough yeah I mean everyone believes this conjecture is true we have still have to sum up close check it somehow for the last remaining cases and we can't just do a boost for searches this is just not possible with even with the best computers go by conjecture by the ways caps Li the only mathematical statement I know of a queue there has a has a popular novel of best-selling novel attached to it this is uncle Petrus and go box conjectures about so this crazy crazy uncle who's a love of mathematics and spends all his time trying to solve this conjecture he never does unfortunately but okay so that's that's one theorem that we know of here's another one so I told you about the twin prime conjecture that they were infinity twin primes we don't know whether it's true or not we believe it's true that there are many strong reasons why we believe it to be true but we can't prove it but we can we have partial results you have near misses and this is one of our best near misses on the twin prime conjecture it's got chen's theorem so this is a so chan proved not this information primes but there's infinitely many twin almost primes so numbers P where P is prime and then you add two and you get another number which could be prime if it was prime you get a trim crime it's either prime or the product of two primes it's what's gotten almost prime so Prime's have no factors other than themselves and one almost primes have very few factors if you have particle only two primes you only having four factors so this is close this is very close to two the twin prime conjecture you have two numbers one of which is prime one is almost a prime it's one of the best results we have it's the proof is quite complicated I'm not going to give it here but actually the basic idea is very simple it's one thing about mathematics you often you have very complicated arguments which are completely come from very simple ideas the the basic idea here is use what's called a sieve theory sift theory is a way to create primes by starting the images and so crossing out all the non primes before you get to the primes so in primary school you should have seen the silver.silver hasani's which is shown over here if you want to find all the primes up to say 64 what you can do is that well you don't think of one one is not prime you take two and you cross all the mobiles of two you take three quasi Marples of three five mobile kasam of the five and seven cross em up of seven and once you do that everything else anything that's left if you will be automatically Prime okay because you've crossed out all the primes less than the square root of 64 that's why it works so this is a cheap way to generate primes less than 64 you can also generate trim Prime's by a version of the sieve but you have to use a much fancier sieve before we can keep prove this theorem the Civitas is not good enough at all if he's a much fancier one but okay but that's how you prove that okay he's my theorem we've been green that I prove a few years back so said that the some patterns like twins we don't know how to how to to find in the price but there are some other patterns that we actually can do so for example a few years back I showed a Ben green that the primes do contain another type of pattern not twins but they can contain arithmetic progressions of any length so another progression is is a sequence of numbers that are equally spaced time so for example 3 5 & 7 is the sequence of primes including spaces facing is 2 as a professional of length 3 then the next one here 5 11 17 23 that's a progression of length 6 that's art of then 4 and spacing 6 and so on and so forth over here each row is I've shown the first progression that we know of that length so this is this a progression of prime numbers of length or than 5 and then 6 and 7 and so forth what you find quickly is that as you want if you demand longer longer progressions you have to go to bigger and bigger numbers and in fact even with the best computers the the longest progression that n is ever found is of 25 is this the progression of primes is this beast over here but what we showed is that actually this goes on forever if you we if you want to find a progression of length 100 which are primes it's out there somewhere we don't tell you where it's like Euclid's theorem you assume tells you the infinity Prime's doesn't tell you where they are unfortunately a lot of proofs in number theory like this there were they're not particular fact 'iv if tell you things exist but they don't tell you where they are and analogy is if you want to if you have a box and you want to show there something in the box okay you could look it you can open the box and look into it and you know if you touch something right then you found then you notice something in the box but a lot of things in mathematics are not like that we have a box and we can prove there's something in the box and without opening the box and we do things like we take the box and we weigh it okay and if the weight of the box is larger than the way of an empty box that tells you there's something something in the box but it doesn't tell you what it is and that's a key our proof to oversimplify quite a bit actually works like that we we look at all the aspects progressions of primes in more than numbers 1 to N that's like a big box and we count how many of them they are there's a formula for how many Prime's there are progressions of primes there are in Bach and that's like like weighing this box and we show that this weight is quite large and that tells you that there's lots of progressions of primes but it doesn't tell you where they are so anyway so that's the best part of the proof this there's no way I'm going to give the whole proof here it's about 50 pages long it's the but it does use very much these themes of the primes having both structure and randomness what we do is there's actually a way to split up the primes into a bit which is very structured like very periodic and then there's a bit that's just completely random completely random and there's a way to split it up we don't quite we don't really understand how this this decomposition works but we know that we can split it up and we know that that both the structured part of the primes very periodic sequences and also very random sequences they both contain lots lots of progressions and so no matter how the primes are split up into structured parts in random parts they're always going to create progressions and that's that's how how we solve this problem for you roughly speaking so that's what I mean so that's that's one thing that I did I'm still working on the kind of thing with several other people just to give you one example of the type of thing I do these days so a few years back I demonstrate something similar not for the price but for something called a Gaussian primes so primes are the integers which are not divisible by other by smaller integers Gaussian Prime's are the Gaussian images which are not divisible by smaller Gaussian images now Gaussian hinges are complete images the the numbers complex numbers in real part in the merging part they're both integer so 3 plus 4i is a Gaussian integer and some guys didn't use the prime sum or not in the background here what you see is is a plot of the Gaussian Prime's I think of magnitude less than 100 is the Cartesian plot but we haven't plotted the axes so is this nice pattern here I keep my friend Ben green gave me this linen cloth with this pattern for my birthday that's quite nice so what we showed so these degassing crimes go on forever just like just like the ordinary primes and what I showed is that the Gaussian Prime's so we know the primes contain ethical questions of any length you can also show the Gaussian Prime's contain constellations of any shape so what's the constellation so the way I like to explain this is that there's this movie called A Beautiful Mind study size Russell Crowe it's an Aussie and he plays a math edition and there's a scene there where where he's trying to impress his girlfriend and and they're looking at the night sky and so he asks his girlfriend to name a shape any shape and so she names a shape I think it's an umbrella and so he looks at the sky he thinks a little bit he finally points out like you know seven or eight stars in the sky and they make a shape of an umbrella okay and the girlfriend is impressed that's that's that scene so okay so my theorem here well it shows is that is that you could you could play off you could play the trick with the Gaussian Prime's with any shape basically you can pick an umbrella and somewhere in the Gaussian Prime's you can find seven or eight Gaussian Prime's which form the shape that you specify as long as the shape is concise of rational coordinates is like but okay but this but but basically you know so you can find big squares of op gusting Prime's you want you can find progressions yeah they're all out there somewhere and it's a variant of this type of thing so okay so this is a very very quick tour of prime number theories there's a lot more going on of course but this is just the highlights or some very few highlights of what's going what's going on okay thank you very much this is ABC fora

Channel: Archy Guo

Views: 77,062

Rating: 4.9173126 out of 5

Keywords: Terrence Tao, Terry Tao, prime, UCLA, math

Id: hYxBH1YY9z4

Length: 42min 12sec (2532 seconds)

Published: Sun May 22 2011