Terence Tao - Large and Small Gaps in the Primes [2015]

okay so it's good to be here this is a wonderful one who diverse conference in in all senses of the term so I'm gonna be representing number theory here it's a completely different from most other talks actually in this in this conference and so there's been a lot of recent progress in some very classical problems the number theory and that's what I'm gonna talk about particularly involving gaps between the prime numbers so so you'll note the prime numbers are of course two three five seven eleven and so forth yeah okay so some of the oldest questions in number theory concern the gaps between prime numbers so if you call PN the nth prime number you can look at the prime gaps between consecutive prime numbers so the first prime gap is just 3 minus 2 which is 1 and then 5 minus 3 which is 2 and so forth and so these all the first few prime gaps so they're just a sort of random looking sequence and two of the very oldest questions in a number theory a very basic very roughly basically as you keep going along the sequence how small can the prime gaps be and how large can be prime you have to be yeah I saw that sort of those are sort of imprecise questions but these are two very basic questions and what's what's exciting is in the last few years there's been breakthroughs on both of these for these basic questions after many years of being stuck basically actually the the weirdest thing is that actually progress on the small gap problem has led to progress and a large gap prob which is not not intuitive at all but I try to explain how that happened ok so let's have a small gaps oh no yeah this has more small gaps first so of course the first thing you observe in local sequence is that all the gaps are even apart from the first one and that's because all the primes are odd about them the first one ok so that's not so difficult so the the prime gaps after the first one they have to be at least two and one of the oldest questions in number theory dating back at least to the Pontiac in the 19th century some people say that that you could consider this but there's no actual record of this so the private cast of you at least two and it's believed and it's called the twin prime conjecture that in fact that the that the prime gap to actually infinitely often that there are infinitely many pairs of primes that are distance too apart so of course there's there's many of them three and five eleven and thirteen and so forth but we don't know if they go on forever we know the privates going forever but we don't know whether the twin primes go on forever so we can't we can't solve this even after all this progress actually that there are good reasons for why we can't there there is a very there's a very solid obstruction to all our methods for proving the TransAm conjecture something called a parody problem which unfortunately I won't be have time to talk about in this talk but even though we can't solve this conjecture we've been making progress towards this conjecture in many different ways and one way to make progress on the twin prime conjecture is to show that while we can't show that the that the prime cap is too infinitely often we can at least get upper bounds on the prime gap which hopefully get closer and closer to two even if we can't reach to yet so we have always partial results so the first thing you can do is you can use most basic theorem a number theory which is the the part number theorem so here's what we do okay so let's have a lesson have a look at it at a big interval of primes so let's pick a large number X you say a trillion and look at all the primes inside say the interval between X and 2x you could pick other intervals if you like but let's just take X into X and then you look at all the prime gaps inside this big interval so you look at adjacent Prime's in this big interval and you look at these prime gaps now the prime number theorem is from the most basic theorems a number theory tells you how many Prime's there are in a big interval so one thing it tells you is that if you look at it at a big interval X 2 to X the number of primes in a big interval like that is roughly x over log X so about 1 in log X of all the numbers in this interval of crime up to an error which goes to 0 as X goes infinity so there's always little ones here which you should basically ignore for this talk but basically the number of primes in this interval is about x over log X so the number of prime gaps in this interval is also about X for log X and the interval is X so just from the pigeonhole principle this tells you that one of the guys has to be small so you just divide the length of the interval by the number of prime gaps you have and so the pitch no principle tells you that one of the has to be at least log X so I had most log X because that's just the ratio between the length of the interval with the number of primes so just without any effort really how from the prime number theorem you can say that you can at least get a gap which is of size log X okay but you want to get to in log X is bigger than two for big X so okay so people have tried to improve this over the years so it's a napkin was remarkably hard so this is a very easy bound but to to improve it took a long time and the first few bounds but not all that terribly impressive although very impressive both editions worked on them so the first viewers out basically improved that one x log X to a constant times log X you know so for example hiding little wooden 19:26 work quite hard using in fact a very powerful additional hypothesis that the generalize women hypothesis and all they could do even after all those work was to improve there's one log X up prime cap to two-thirds log X and then this was slowly improved over the years so so so rank in a bit later I got 3/5 log X but I still needed the Riemann hypothesis that the generalized Riemann hypothesis I'm in fact and then Arish had it had had a breakthrough in which he didn't need the Riemann hypothesis but then he could only improve one by a tiny C which he didn't even say what it was they can get almost as the smallest possible improvement to the result and then that number slowly got here so then Ricci was the first to actually give explicit improvement 215 16th and then it got slowly improved over the years yeah but but I think I see progress was not incredibly fast but yeah but then in the last 10 years in particular there was there was a lot of breakthrough so so until like 2004 the only improvement was to improve the constant what you know like number theories is is is there's not terribly impressive it as far as improvements go but then there was there was a big breakthrough in 2005 sorry by goats and Pinson euro room who showed for the first time that you can get prime gaps that are actually which grow at a rate smaller than the more gex so log X times something that goes to 0 as X goes infinity so and I was saying it is that this call steadily shrinking in the previous slide can be made as small as you wish then they worked a bit harder and said actually it's tortoise log X he can I keep a square root log X at times at additional small factor after a few more years of work and then this got to improve a little bit two to two cubed of log X and then finally in a quite famous breakthrough actually you tank Yang who was actually just a lecturer in verse New Hampshire at the time stunned basically the community who had thought that basically you couldn't do this actually with the methods we had but found quite an ingenious argument that managed for the first time to get a bound a gap so you can enjoy what he showed was that there were infinitely many prime gaps which aren't too I would was what we would love to have but you can get me if I mean if I'm gaps that are bounded and the bound he got was 70 million so that there's infinitely many prime gaps which are bound about 70 million okay so that was that was a big breakthrough almost as soon as his paper came out so I'm happy came out 23rd of May or two years ago people look at his paper okay and so seventy million was it was just something that came up with calculations and and he was he was rounding up at all various places and he said in his paper that this was not the best result you could get this was just sort of the cleanest number that just that he was going to write down and so almost immediately people started started improving it so you can see on the archive for example the paper saying I can improve 70 million to 62 million to 58 million whatever and so people and then so on blogs and varies over the Internet various websites people was just started tinkering away at there's bound because it was a it was very cheap way to get put at least very temporarily the world record on a major mathematical is out and so this is much a good got coalesced into a single project what we now call a polymath project so polymath projects were started by Tim Gower's who's a mathematician Cambridge about 10 years ago now and the idea of a polymath project is that unlike traditional method research in pure math which is usually one or two people working in isolation and not sharing what they've done until they say they've almost finished they release their preprints a polymath approach a polymath is just a partner it just needs many mathematicians okay a polymath project is where you have many many meth addictions collaborate over the Internet in an open environment anyone can sign up and and and and comment usually on blogs we also use wiki's and Dropbox and things like that and and you just work on a common goal which in this case was to it was to improve this number it may make it as small as possible and people just toss out ideas other people try to carry them further maybe someone wants to a calculation done someone else has a big computer and go to programming in fact he does the calculation and so forth and everything's done so openly so you know so people make mistakes they backtrack and so forth and so though those very chaotic process yeah I was like one of the moderators for this this project which took basically a whole you of my life actually to to deal with but but within a few months we had managed to optimize pretty much every single step in in Young's argument and and and squeeze this never down took two to four thousand or so which we were very very happy with and we were writing it us up and about to publish it when we got another surprise because there's another method is a young postdoc then at Montreal James Maine out who was working independently of us I said we were about you know 20 people you know working on different parts of Jack's paper may not found a different argument simplifying a lot of what you Tom did actually bypassing some of the most difficult parts of eating's argument and getting a much better bound a key so he he leapfrogged our bound to 600 but then what happened was that we decided to combine forces mean I joined our polymath project and we we combined all that all our tricks and we eventually got a bound out 2:246 which is the current world record and and and we're out of tricks at this point we were to get any further is gonna need something new but but this is probably not ways that's not with that's not the best possible without this is the best possible is that we can get with with the tools we have okay so that's that's the that's a brief history of progress now oh yeah so this is just a it's not a very good resolution slide but you know so this is just a an illustration of how fast the barons were progressing at one point so the pilot project had this wiki page and one of the most popular pages on the wiki was this timeline where we would we would describe what the band was doing at any given point so he said the Zhang proved 70,000 as the bound for the time gap I can back in May and then this ban was dropping on a daily basis at various points so you know people would which would would would you know wake up in the morning and just checking don't what but the bound was that day is like a stock market or something again it was well maybe not like stock my goods it was going down but yeah so it was it was it was a fun it was it's not often you get to see massive done in real time like this so that was fun but I'm kind of glad is over because it was really quite time-consuming okay so let me kind of explain why I'm sorry how we we prove theorems like this so all the so the first breakthrough after the first breakthrough by by goats and pits in your room we all we all use what's called the gorson principle or method and we've just become very very good at it so to explain how this method works it did it let me go back to the trivial bound of 1 x log X so this is the pitch and opens to argument that I gave at the beginning and let me prove it in a different way and and the purpose of doing this is to motivate the better way the more advanced way of proving gaps so okay so let me there let me reprint within the interval X 2 to X of size bounded by log X so you can prove this by sort of a probe listing method what you do is that you pick any number at random any integer at random from the next situation see we just pick a number at random from say a trillion to 2 trillion this number will probably not be prime but the prime number theorem tells you how likely it is to be Prime and so one way to think about the prime number theorem is as a public statement that if you pick a random number from X 2 to X then this number n will be prime probability about 1 in log X 1 in log is log X the time will be will be prime which is not very much but it's positive and then if you add 1 to it n plus 1 that's also pretty much another random number between X into X may be shifted by 1 so that guy will also be primed with probability about 1 in log X and n plus 2 who every prime with probably one in log X and so forth so if you add so each of these probabilities is individually very small but they add they start adding up and so if you add a K of them and if K is just little bit bigger than log X if you add up K all these events together so each of these numbers and n plus 1 n plus 2 K up to influence plus K each of them are only prime a very small probability 1 log X but if you put them all together the sum of all the probabilities that these guys are prime will eventually add up to more than 1 and the moment that happens then the pigeonhole principle for probability tells you that there must be somewhere in your event event space where two of these guys are prime together simultaneously and then that will give you a prime gap which is smaller than than K which is log X ok so that's just a repackaging of the pigeon opens for argument in a pro plastic language ok so the idea of goats and Pinta new room which is so obvious in retrospect but people missed it but for 70 years was that you run this argument where you don't pick and uniformly random but you pick it non uniformly at random you pick a biased ad so the yeah so the modern way to find prime gaps is that you pick a number and using some biased distribution from in 2 X 2 to X and the whole art is choosing the right bias distribution okay but you choose a clever distribution a probability distribution on XE to ik and you pick n using this this this whoa chosen distribution and you want to choose it in such a way that that various shifts of in line maybe no n plus 1 n plus 2 n plus 3 but maybe n plus h 1 n plus h 2 and and you have to pick H to let me not talk about these shifts but if you pick some shifts h1 to h2 up to HK and you how to choose your published distribution so that each of these shifts has a large chance of being crime so so better than one of the log X something like say 1 over 100 would be great and then if you can all you have to do is that you need to make these probabilities of the that each of these numbers is prime if you can make them add up to more than one then again the pigeonhole principle will tell you that somewhere in your event space - these guys are prime at the same time and that will give you a gap which is bounded by the diameter of this set of shifts and so yeah so part of this these 70 million numbers and so forth they come come from trying to find good sets of Al Queda boys with small diameter but let me not talk about that part of the project okay so it's it's especially this the same argument as the pitch no argument but the the main trick is to is to find a clever non-uniform distribution in which you you enhance the probability that each of these guys is prime and so what you want to do is you want to have somehow remove or sieve out all the numbers where these guys are composite well at least it's about a lot of them so that you keep the primes and maybe if a few non primes but you try to remove as many composites as you can from your from your polarity space and so there's a host area of number theory which is devoted to doing exactly that course if theory and so you have to choose a good probability density function to so you basically want a probability distribution on your numbers set of numbers n such that each of these shifts n plus h 1 FS H 2 and so forth you want them each to have a good chance of being prime so that the total probability sums to more than one and so what Gore simpkinson Yoram did was that to make each of these guys likely to be prime they decided to call these in fact all these linear factors and multiple more together to get as big polynomial and try to to to force this polynomial to have very few prime factors we what's gotten almost prime because if this number has very few prime factors then that increases the chance that each of these guys will be prime and there's a standard way of doing that it's cool so big sieve so okay so there's a probability density which which will enhance the probability of this has a few prime factors okay and it's given by a certain formula but maybe I'll not talk about the form of exactly but so that they they they they chose this sieve they they there's a parameter in accord F and you optimize an F there's a calculus of variations problem yet to solve and then this gives you there was out okay alright and okay so yeah and you have to use a bunch of number theory not just the prime number theorem you have to use more advanced form the part number theorem called the bump wave in regard of theorem which counts not just Prime's in interval with primes and ethnic questions and what you talking yang did what his big breakthrough was i he didn't improve the SIP theory part or he made us he made some improvement to to this if 30 publishes his principal improvement was he improved this bomb behaved in a God of theorem that that he found he found him a more refined estimate for how many primes there are in certain ethnic progressions that went beyond what what people knew before and this was quite a difficult piece of work just to give you one example of what goes into it it used P Adaline's proof of the Riemann hypothesis over finite fields which is what gave him both fuels medal in the Apple prize and that's that's an essential ingredient in Jiang's work and so but okay but because he improved this part of the argument he was able he was actually able to get a bound a gap which we later improved to about four thousand okay but what may not did lucky I came up the same idea the same time actually by coincidence was that may not instead improved the sift theory part of the argument and then bypassed the need to use all those fancies work of Deline so as I said before what goats and pins in your room did was that they they chose us with this probability probability distribution by multiplying all your your linear factors together to form as polynomial and then tested the devices it was polynomial to create the safety mode you want to remove all those values where the Deponia was even it was a boy 3 and so forth so main ours idea was it rather than then do this sieve which is what's go to a dimension sieve you you you do a multi-directional sip so so rather than put all your factors together into one big number and then try to study that big number as an aggregate you look at each of the numbers separately and you factor each of the numbers separately and you you run a sieve based on the factors of each other of the D separate numbers but but you so yeah there's multi-dimensional sieve which which you coupled together by a certain color function which is based on the sizes of all the factors of all these numbers so it's a more complicated sieve but the point is that whether the original sieve had a parameter which was this one-dimensional function and this new sieve has if has a parameter which is a multi-dimensional function and then you have to optimize this sieve and you have to now solve this calculus of variations problem involving a multi-dimensional function which looked really complicated and it is really complicated and and and no one really attempted to optimize this before because it just looked look look too scary but actually James Accu found a way to get a good choice of effort actually we work quite well in this multi-dimensional variational problem and this is how you can you can get these these these really good prime caps which currently is 246 okay so that's that's more prime gaps and that's like you all I want to say about small prime gaps so I want to talk about the more recent developments from last year on Logic prime gaps I can only go oh no hang on before I do that I have to mention one thing sorry so it so this argument may not actually it's so efficient so I said before the the the moment you can get these probabilities that this is prime mrs. prime mister prime of the moment you have them add up to more than 1 then the pijl principle tells you that you can get two primes two of these guys gonna be prime at some point but actually main argument is so efficient that not only can you get these problems to be bigger than one but if you make a big enough you can make these probably somebody bigger than two or bigger than three they come before and so as a consequence of his work not only can you get two of these numbers to be prime you can actually get three of them or for them or five of them to be prime if you want so not only can you can we now bound prime gaps but we can keep brown sums of consecutive prime gaps so we can take two Jefferson put them together like PN plus two minus PN and we can make those guys bounded as well so I mention this because this would be important for the large prime cap theory okay so now back to large gaps okay so all right so now we're looking the opposite problem we pick a large number X and this time we'll take all the prime gaps from 1 to X and now we look at the largest prime gap we call G of X and take all the gaps that you can find for one to say truly and what is the largest gap that you can find so this should get bigger as X gets bigger because there's more more prime gaps but but how does it grow okay so you can again use the pigeonhole principle and if you run the picture prefer just the other way you can find you can show that the average gap is log X so somewhere in this in your interval you must have a prime gap bigger than log X so the prime caps do grow and they must grow by at least log X now that's the lower bound how fast can they grow well I mean they think they copied incredibly huge example for example they must be less than x trivially okay but you can you can do better than X in 1920 Kramer showed that if you assume the Riemann hypothesis again which is a very useful hypothesis a number theory you can get basically root X you can get up on root X and in 36 he had made a very influential problem stick model for the primes called the Kramer random model which predicted action the predictor but not he proved that the gap should actually grow like log squared X because that's what the gap would be if the primes were just like a completely random set with with that density so log squared X is what we believe to be the answer actually there's a slight tweak we actually believe it to be nowadays we actually believe it to be about 20% larger than log X but there's a slight defect in this model that you have to you have to tweak but we believe that the the truth that the true gap should be about log squared X okay so we need a lower bound of log X and on the women I thought this is being an upper bound without root log root X without the Rena Riemann hypothesis it's harder but you can get close to it we the best bound we know currently for without the Riemann hypothesis on the best upper bound on the large gap is X to the point 5 to 5 so basically ruled X yeah so there's a there's a huge gap between the upper bound and what we think is the truth which is log squared X but there's not that much of a gap between the lower bound which is the trivial lobe on log X and what we believe to the truth of log squared X so you know you think that this is not such a big gap log X naught squared X isn't that far apart so but it was quite a journey to what we haven't we haven't got it yet but so can you improve upon upon this log X so we solve the small gaps that there was this long period of slight improvement until we got this big breakthrough and there's a sort of similar story for large gaps yeah so as I said you can get a gap of 1 x log X ok and so again people starting improving the constant in Twentynine backlinko 2 plus log 2 times log X 4 times log X and then we're cynthia's sure that you can actually get log x times something that they grew a little bit not very fast a log log log x over log log log log X which does grow to infinity but not very not very quickly and then ok and then so then Irish came and improved the logs a little bit now it's log log x over log on top of x squared and then man can improve edges by a log log log log X and so ok so he showed that you can get a prime gap from 1 to X of size log x times log log X log log log log x over log log X squid this is Joker you know what what did the drowning number theorists say well globe look okay yeah we like our logs okay so you know these are all kind of random so you know we try and get log squared X so okay and this is 1938 okay so so that was like 70 years ago 75 70 or years ago so you think that that we should still ki know we should be able to do to prove this but for the next 70 years the only activity that happened was with this sea so yes I said G of X is bigger than a constant C times x it's this whole mess of logs and the only thing that happened for 60 years was there you could you can improve the see a little bit so it's a Rankine açúcar sees a third and then the the receives flow increasing but we couldn't budge these logs you know I mean this this is this is not what should be the truth right so this log squared X but this funny mess of logs which would no one no one could could shift there so it yeah I mean you could only improve the constant a little bit and so it got so frustrating that that Kurdish who is occupied for who was quite fond of while giving cash prizes for problems offered quite a big cash prize actually for for anyone who could get off of this for this weird factor so in 79 he offered this price we took you the biggest prize he ever offered actually before for anyone who could show that that this constant can be made arbitrarily large or coupling that you could you could attach some extra factor maybe note 10 more logs or something on the on this end could you get off of all this all this of this weird weird factor and that was finally done so Kevin Ford Ben green surgical noggin and I in 20th of August last year finally forget our way to do this and just amazing coincidence the next day on completely independently Kings may not find a different way to do it to I think sometimes the times just rightful for progress you know even if 70 years as there was basically nothing event two separate breakthroughs okay in fact and then we joined forces so the five of us actually to figure out exactly how much we could improve rankings bound so bakken's Brown was log X log log X log log log log X double log log log x squared and then what we can actually do be push put if we do we optimize everything in our methods is that we can get rid of a square so we can we can improve one log log log X it was it wasn't that spectacular of a game but it did it was it was some game still we're quite far from box squared x which is what we really want and unfortunately none of our methods work you get log squared X this this appears actually to be the limit of all of our methods currently and so I think we'll be stuck here for quite a long time so I actually I decided to in the spirit of alysha's price to actually offer $10,000 anyone who can improve on this not not just on the sea but I could do to actually make to a place it's by something that goes faster but this seems to be the limit of what we can do now okay oh it's alright so how do we how do we actually find large gaps so they all use the same idea it's just sort of executed more and more efficiently so to find a large prime gap is the same thing as finding a big long string of composite numbers become out a big long string it comes the numbers in the two primes on the end of on either side of a string will be a large prime cap so really you want to find a big long string of numbers where everybody copies it so the easiest way to do this and sometimes you even see this taught in high school is just to take a factorial n factorial and shift it by the numbers 2 3 4 up to n so in fact take a large number n n factor where + 2 + 3 and this would be a long string of composite numbers because n square plus 2 is divisible by 2 n square plus 3 it was worth 3 so in factorial plus 3 2 3 and so forth so this big long string of composite numbers and you can work out what this what this tells you for the largest prime gap you plug in Sterling's formula which tells you how big and Victoria is and what you find is that this this simple argument gives you a lower bound which is pretty lousy it gives you log x over log log X which is worse than the Pertino principal arguments log X but just because magma is worse it doesn't mean that is useless it means that it should be improved so you can be smarter than n factorial so if you don't use the factorial you use something smaller called the prime Oriole so the the factorial of a number is the product of all the numbers up to n the prime Morial of an of a number n is the product of all the primes up there that's a smaller number and actually it turns out that you can just replace n factorial by n prime oil if you take n prime oil + 2 and primarily opposite we update and primer oil + n those are still a stream of composite numbers because every number between to the N is divisible by subprime less than N and that prime also divides the primal so you will still get a big long stream of composite numbers and if you work out what that gives you with the prime number theorem that will give you that you recover at least the trivial bound so you get back to log expound that the division of argument gives you ok so then basically you have to do better than this so can you do any better than then then then what I just told you so the the key thing that made that previous construction work was that if you took all the numbers from 2 to n all of them were divisible by a small prime that each of the numbers Matilda end was divisible by some prime real estate less than n that's what made the previous argument work another way saying that is that if you take the rest new classes 0 more to 0 mod 3 0 or 5 you take the investor classes 0 mod p for all the primes up to n those rest new classes those sets of integers they cover this beginner book that you see you can cover the interval from 2 to n by all these residue classes that's just a fancy way of saying that every number up to n is divisible by prime up to here and it's this covering property which is what's important more generally whenever you can cover any intervals I say the interval from under why if you can cover any interval by residue classes if you pick one ways to cost more - one is close mod three one who is too close not 5 and it doesn't be 0 you can pick anyways do class mod - mostly mod 5 if you can find with new classes you take all the pumps up to some X and if you can make these versity classes if you can shift them in such a way that they cover this entire interval 1 to Y then a very similar argument to what I had on the previous slide yeah you know what you need want to check which is the Chinese remainder theorem if if you can cover this interval by by residue classes then you can slide this in about somewhere so that you can make them all composite you just slide this in a boat until it's covered by the 0 mod p classes and and this will give you some lower bound on the on the on the largest panel gap so basically for example if you want to prove rankings without this this funny log log the thing of all the logs in it what you need to do is that you need to be able to cover the univ of wonder why by residue classes mod primes up to X and why does this be a little bit bigger than X ok so ticket man cancels out y has to be X log X log log log x over log log x squared and the ticket otherwise else you need other funny factors in front of this but why it's just a little bit bigger than X so with this idea you have transformed the problem from sort of a number 3 problem to more of our covering problem you have this interval and you want to cover it as efficiently as you can using as few residue classes as possible so the way I could think of is it's like you know shooting ducks at at fair so you know there's this interval from 1 to why you think it's a big row of ducks ok and and what you have is that is that you you have all these rifles ok you have a more to rifle and a more 3 by 4 and what 5 by 4 and so forth there's now a little bit for stupid ok so what the right foot Oh what the more to rifle does for you is it shoots out one ways you cost more to so you can shoot all even ducks while the odd ducks okay but you only should at once okay and then you have the more three rifle which can shoot out one of the risk is more threes you're more three one more three two more three but you can only shoot it once and so forth and so you have one rifle for heavy prime up to X and your job is to is to is to aim his wife was in such way that you can you can shoot all the ducks with the ammunition that you have okay so that's a sort of way I like to think about the problem i I find that that instead of working math problems it helps to anthropomorphize the enemy somehow something to shoot at in particular okay but okay at least makes it more fun to think about okay okay so it's so so now basically the whole game is is to find so efficient shooting strategies that that that sort of covers as you know you want to cover as many of these ducks as you can so there's a lot of tricks and basically you put all the tricks together and this is what gives you the best results so the first thing is that you know like you need to shoot all the ducks if you can choose most of the ducks using most your ammunition then then you can finish the job because each one of your residue classes can can always move at least one what one of your survivors if you have one duck left over and you have one you have one residue class P but you can choose you just pick the P whose basic last hits that hit that that that duck so so basically for example if instead of using all the primes from 1 to X use all the times from 1 to X over 2 and you shoot many of the ducks in this there's some survivors if the number of survivors surviving ducks is fewer than the number of remaining Prime's then you just use each of the remaining crimes to eliminate one duck and then you could you could you can solve everything so so basically you don't need this to to cover 100% of of you love your space you just need to cover 99% basically and that that's a much easier problem mathematically you know once you once you allow yourself to there's error tolerance okay so that's the first observation the second operation is that above that yeah this we have already have this pretty good strategy which already removes a lot of ducks which is you just keep shooting zero all the time okay so if you do more tunes you want three is you want five this is the Civitas today's this already removes most numbers from you from your set it doesn't remove everybody and but it was a fair number so like if you if you shoot out 0 mod p for MVP up to say x0 4 then you eliminate every number which is divisible by prime up to x over 4 and the only numbers that are left well first of all 1 because 1 is them to supply anything one is left and all the numbers all the primes between X 2 4 and y so basically the old the Civitas tonie's choose out everybody except crimes unfortunately too many Prime's so this this by itself doesn't solve the problem but so what you wanna do is what you want to modify the cypriot Rosten used to be a bit more efficient than than this okay so alright so then the next observation is that there's a little bit inefficiency in the severe tostones you don't actually need so the silver trust me subtitles you want P for every single P up to some threshold X before but actually most of those peers are not needed because if a number is divisible by one prime position to visit by another prime as well and so yeah there's a lot of redundancy so you can you can remove you can save you know you can keep something pop you can keep you can reserve some of some of your ammunition if you like for doing something else so rather than remove rather than remove zoom what people all P if you removes you more people or P okay you move all small primes a less than Y over X okay and all large Prime's between some fish or Z and X over 4 but you you don't remove zoom or P for that for the medium for medium Prime's so if you take up this if you take out some medium involve primes between Y over X and and and some Z and you don't remove those and you only remove zoom or piece for all the remaining times P that's still a pretty good sieve that's still so if you if you if you if you do that save you will still keep one and you'll keep all the numbers that are prime but you'll get some extra you'll get some extra numbers now because because which one which were not removed because if you don't shoot out the primes less than Z then you will keep some new numbers and you keep the numbers which are called Z smooth so as if smooth number is a number where all the prime factors are less than Z so these are all the fact these are all the numbers which would survive if you are not shooting up multiples of primes less than Z so if you if you don't if you remove these if you if you if you don't you remove these residue classes from the cipro trostenets you get some additional numbers these these smooth numbers but if Z is small enough then the number of these of these d'ysquith onwards is pretty small so number of years I've worked out exactly how many smooth numbers there are up to X which has Z smooth and there's a formula which is moderately complicated and you can optimize the formula and it turns out that that the biggest you can you can hope to make Z and still not take on too many extra numbers is this is this funny power of X it's a if it makes the PX the log-dog eggs that's how many that's how many sort of more peas you can remove and still not increase too much the number of our crimes of number of survivors that you have and this is it's this funny exponent this is what leads to all the weird exponents in the Rankine parents it's because of this guy okay so you yeah so you take out some of some of the veg to causes from from the c-4 hasani's and so what do you do with them well the best thing we know how to do with with with these residue classes that we that we salvaged that we saved it's just to shoot randomly which is so so for all day at the price between Y or Z and Y of X and Z you just pick up as you class at random and that that cuts down the number of of surviving ducks by a certain factor which you can compute and when when you when you work it all out this this is this is basically a rankings method and then and this this is what gets you this is what gets you this weird ranking bounder Frank and water water logs in it okay so that's the bankers method and it uses all the primes up to about x over 4 and between x over 2 and x and you just have one sort of round of ammunition left which is all the price between x over 2 x over 4 and x over 2 and so the yeah so so all the remaining advances past the 1938 was out of Rankin which is how to how to use these large primes how to how to shoot using these these large Prime's P as efficiently as possible and so what Rankin did was they just used each of these what large 5s of shoot one duck okay and and that's that's how he got his his his vision about and the the over the next 67 years this the constant see that got improved basically came from the idea that maybe he can use these these primes to shoot two ducks at a time rather than one and so that's that's basically how how the constant slowly got improved but it was not a very great improvement but if you want to do better than that so I mean the obvious thing to do once you see that is you want to find new classes a mod P where P is pretty large now so very sparse ethnic progressions which are not just capturing one duck two ducks so it's not just kept in one or two primes but it captioned many primes so you want to find an athame progression of large spacing which captures many parts three or four or five Prime's at a time so we now know of two ways to do this so so Kevin Ford and circuit canyon were working on this problem and they realized that what they needed one thing that was solved the problem was that if he could find ethnic progressions that consists entirely of primes that that's like a residue class that can use lots of crimes and by coincidence Ben green myself that I keep working on this problem many years ago we actually had a method for finding progressions with foster Prime's in them and so that's how we got an importance project so yeah so in 2004 Ben and I were able to find lots and lots of I think progressions of them valent you wished where where every number was prime this wasn't quite what Kevin and so he needed because not only do they need the entries the progression be prime they needed the spacing are to basically also be a prime as well so we had to modify our arguments but it turns out this is possible with a bit of work do you also make our IQs not quite a prime bit about a multiple of a big prime and this turns out to be enough to improve Mankins result and you can make the seed arbitrarily big so that's that's how we did it and then the next day case may not had a different argument where instead of using what Ben and I did on progressions and primes we used what James did on on in his work on small gaps so as I said before one spin-off of what James did and his work on small gaps was that he could find many n for which so given any a 20 HK he could add 4 K big enough you could find many n for which n + H 1 and position K contained many many Prime's let's say 10 of these guys apart at a time so he could find many tuples where many of these numbers are prime and it turns out that you can there's a very similar argument where you take all these shifts you move on by large prime P and for any large prime P you can also find a lots of n for which n plus 81 times P and position 2 times P just this this dilated shifted to pop you can you can make sure that this set has got lost not surprising let's say 10 primes in this set and then and so that would imply that there are certain residue class mod P contains for samosa primes and so that so by using that actually that gives you a different way to make this bound large ok his ways a key better than ours that gives a better bound actually if you the computation ok so this that almost so that solves the original poem / - of getting the constant opportunity large the final thing we did was to optimize everything and get rid of the square and so we have this final bound where we only have log log X rather than log x squared the previous argument said it's just said don't quite give you this bound they're off by a log log log log X ok tiny amount the reason is because sort of a lot of the original classes that we were removing they sort of they're not coordinated with each other so you know we were sort of shooting a whole bunch of ducks and we shouldn't go / to other ducks but but many nice expecting a shot twice ok that we waste some of our ammunition by removing primes that were already removed by a previous stage of the sieve and so we do that because it's easier to analyze if you just randomly it's much easier to compute how many survivors there are but what you would like to do is is to do things much more efficiently and to to to choose your your aim somehow - so that there's no more tool for that nor to waste and this turns out to be a special case of a problem that coma toilets have studied for quite a while which is something called a hyper graph covering problem where so a hyper graph so a graph is a bunch of edges right and edges are pairs of pairs of vertices so so a graph is a collection of sets of offset abilities of size two a hyper graph is a collection of sets of vertices where the number of vertices no more elements in secondly more than two like three or four or five and so forth it's got a hyper graph how did you draw the graph server the same and and in our case the vertices are the primes and the hyper graph consists of like a residue classes intersecting the primes in in various ways okay and what we have is is covering problem you know given a hope this hyper graph is clicking subsets what is the most efficient way to cover your whole set or most of you set by these the subsets so that so that this is a little over up as possible and you get as much coverage as possible so but as a general comment or a problem so if you randomly there's some overlap is but a waste but okay but there are smarter ways than random to do this and so back in 89 that was developed something which we now call the the semi semi random method or the roto nibble develop in particular by pivot here and Spencer and so the idea is that if you go back to the shooting analogy so so rather than just of shoot randomly and get all this overlap you shoot randomly for for a small amount of time so you you take a small out of primes and you shoot randomly but only for us as a small set of primes and as long as you take a small set there's no much overlap like the other that when he comes when you shoot a lot so you you shoot a little bit at random and then you remove all the the ducks that you that that got hit by that process and then for the next set up so that's one nibble then for the next nibble the next set of primes you choose randomly among all this new classes that don't hit any of the ducks that were removed already so you rather than just pick you hate your vest class a random you pick only those residue classes which avoid the elements that you that they really go hit you do that randomly for a while then you remove some new docs and then you take another nibble where you you you only you only shoot among all the veg to classes that avoid everything that has been removed and so this intuitively is is a better strategy the hard part is to analyze it actually actually like he still works but it this actually can be done after a lot of effort and he gives them how the maximally efficient way to run it to run all these arguments and that's what gives us this final bound and that's where we are and as I said that seems to be the complete limit of our methods and I'm offering $10,000 you can do better than that okay thank you very much

Channel: Graduate Mathematics

Views: 2,205

Rating: 4.8888888 out of 5

Keywords: Terence Tao, Primes, Small Gaps, Latinos in the Mathematical Sciences

Id: LikuKTZzgoU

Length: 49min 18sec (2958 seconds)

Published: Fri Dec 15 2017