Terence Tao: The Erdős Discrepancy Problem

so I'll be speaking about somewhere on the discrepancy theory so this compensate theory roughly speaking is the study of how well balanced or distributed you can make various sequences of numbers or points things like that so for instance you can consider plus or minus one sequences so we give a sequence of numbers which are either minus one plus one so some some signs and you want to make this sequence sort of roughly so the rough question is of how balanced how well balanced can you make such a sequence okay like you want the minus one to plus one to be in very equally distributed in some sense now of course this is not a well-defined question because I haven't told you what were balanced means so for example is a very naive things that you can take consecutive values you can sum you know you can take partial sums from various blocks and you can ask can you make all the partial sums small and and this is very easy I can make all the partial sums in fact less than one simply by choosing the out naming sequence okay so this is a sequence where if you look at any interval the discrepancy is almost as small as it can be okay so this is much better by the way than a random sequence if you flip coins and you pick up plus/minus 1 sequence randomly then in any block event and you expect to be able to find some sub block with where the the sum is about root n I go up to a log factor but you can I get bounded okay so this is not an interesting question it's more interesting if you ask for stronger notions of discrepancy where you don't just ask that partial sums are small but also sums in AB major progressions and once you do that then it becomes a lot harder to make the discrepancy small so for example this classical is other than Nevadan I think in the 19th century that says that that you can find find arbitrarily long make progressions hey-hey plus r2 are up to say a plus K minus one are where there was no cancellation at all well where all these guys are the same pulse same okay so in other words if you sum the sequence if you look at it in this particular progression this oh yeah so given any have any sequence of us minus ones you can find arbitrarily long progressions where where the sum is as big as it can be there's there's no cancellation that all the that if I if I look in the example cage 100 I can find a progression on that 100 where all this in this progression you just get all plus or minus 1 so there's no so the discovers you can get arbitrarily big in particular okay very famously there was a strengthening of this field you December ready so this thing tells you that that you can find progressions where all the entries are either colored plus white or colored minus one but it doesn't tell you which one but szemeredi's theorem is a strengthening movement in 75 which is the osborne actually 2 which tells you sort of which side you can make so so maurice theorem says that if example if you know that that Plus Ones occurs fairly often if Plus Ones occur for a positive density strictly speaking positive upper density but nevermind what that means so like if if your sequence is plus one even point one percent of the time then then you can find progressions as before where now all the signs a plus one okay so that's the great theorem at least three fuels minerals when Hubble Prize came out with that but anyway okay but all right so we had that view another notable theorem is a vast discrepancy theorem which is a bit more quantitative what it tells you is that if you have a sequence but now a finite sequence I'll plus two minus ones okay then inside the sequence you can find an app Bank regression inside the sequence where on this one on the sequence there's discovered C is fairly large let's say a plus J so if you sum up jobs elements in the sequence that's why there was some as my progression where there's a lot of imbalance but this this this sum is a pretty big it's actually I think they find you get is then one quarter times a concept which you can take you one twentieth for instance plus and the constants not important but you can find a sequence somewhere where there was there was actually quite a bit of imbalance and one quarter and this enter one port is actually the optimal exponent although we don't have a explicit construction actually over all the sequence that does that we know that it can't be improved it's kind of a weird situation but yeah so if you if you allow all progressions if you want so what this is telling you is that is actually not possible to have a sequence a long sequence which is well balanced in every single ethnic progression there must be some arithmetic progression where the plus or minus ones are out of balance so there was some limit as to how low distributed you can you could make sequences if you allow all a thematic aggressions okay so way back in the 1930s Paul Irish was very interested in these questions for example he conjectures Emily's theorem which don't have to be true and so Newman Ross theorem that that you had that if you allow all progressions then somewhere you must get a very big sum so is it the question he asked was that suppose you you you you don't look at all progressions but you look at what are called homogeneous ethnic progressions which started which starts a zero was the over a is zero so let me face in this way okay so uh discrepancy problem okay select if you let me phrase it first for an infinite sequence you have an infinite sequence plus or minus ones other sounds let's call them a say Apple JD from J equals 1 to n are these sums of them in other words F of D plus F of 2 D plus NB always unbounded okay so last theorem or actually also the various theorem of El DeBarge them any of these theorems tell you that you can make if that you have a long enough sequence you can you can find some fact regression where the sum is large but now if you restrict to the homogeneous add my progressions the one that wants us that that started zero basically D to D up to up to n D can you make a can you can you make a this sequence of this is the sequence large so an equivalent way to phrase this question equivalently okay so given any C doesn't exist n okay so given any constant C just exist an N such that every sequence every finite sequence now f of 1 then plus ones and minus ones such that for every sequence there is now a homogeneous as my progression n2d up to md somewhere in this range such that if you sum up all these values you get bigger than C okay so okay there's a YouTube video of someone explaining this using a pit of snakes and a cliff real repeat this so the reformulations that you've been captured by some statistic torturer and and your place at the origin of this whole of some one-dimensional line and then there's a cliff here at some point see where your fall off and die and then there's this this also - see this okay well he put a pit of venomous snakes like a would you which would also kill you okay but whatever okay all right I can't draw a snake okay and you're here okay and what you have to submit to the torturer is is a sequence of moves you can either of left and right moves okay and you just submit a long list of left's and rights and then once you given that were torture they told you all then force you to move right all that according to to these structures you gave except that the the torture may not give thought the torturer gets to choose either he goes to to to to to give you the sequence all the other singers all yoke only give every second element sequence or every third ever sequence or in for Thermo 16 so he gets to pick a skip and then he will force you to move right or left according to a sequence and your task is is is to find a chain of lesson rights which will let you survive no matter what the torturous chooses for you okay so this is an equivalent formulation it's kind of quite colorful anyway so this is kind of it so one nice thing about this equivalent formulation is that is that you can attack in numeric you can pick specific eyes to see like one and two and three and so forth and then you can set you can see what happens so for instance see is one you're actually really bad shape if the you got a thick N equals one you'll die as soon as you submit a single step which is pretty clear if C is 2 then actually you can survive for quite a while there's a sequence of eleven steps that you can submit such data which I didn't write down but you can find it where in fact it's basically unique opportunity side which will that you live for no matter what what you pick it so that's the best if you have a width 2 margin but 11 sharp if you have 12 a key to a final exercise actually almost like serving a Sudoku puzzle to show that that that if you serve at 12 then the newer toast but so 11 is the sharp C equals 3 things already you can have survived for quite a long time so this Misaki worked out last year so those was amazing a computational work of kind of endless it's in last year who did this massive 3sat problem which is what this is basically and what they found was that was that the optimal and in this case was what 1161 so first of all they found a sequence of that 1161 with the property that no matter what skip size you pick you you can always survive in it for this particular choice of C which was really amazing but then even more amazing is that they showed but this massive 3sat combination at therefore that one was 62 you could not survive and the verification of that of the argument is a foetus I think what 13 gigabytes which which so the media picked up on resistors this is this is a Buddhist larger than Wikipedia and in some sense it is the largest proof known orbital top of the Bombers you know in a serious mathematical publication okay yeah okay now C equals four we don't know what exactly what the fair value of n is but it is at least 13,000 that the same authors did construct a sequence of than 13,000 which had discrepancy at most four which means that that all these partial sums I went most full okay so it's so you can see that this it goes quite slowly you know I mean yeah you have to pick your sequence quite carefully if you pick a random sequence of length n your description is going to go about root N and so you will not get anything nearly as good as this okay so anyway um yeah so about two three weeks ago maybe yeah okay so I prove this theorem so so the answer is yes that these sums are always unbounded or in other words for a point for every C there was a finite n for which for which the discrepancy must be big let's see okay so let me tell you about the time things that go into the proof so this problem has been attacked quite a lot from the past actually most recently was this computational attack but from our 2010 to 2012 there was also a serious attempt at proof by I was called the polymath project this was a key v polymer polymath project so it was called pulling my 5 it was won by Tim Gower's so a polymath project is a project run online using things like like blogs and wiki's and matobo's love actually where instead of had one or two people working sort of secretly or not that it's not publicly on these problems you you do everything on the open so so every thought that anyone has you just throw it out there even if it's half-baked especially this half-baked and then someone would will pick up with it so there was always numerical computations that people tried throwing out all these different ideas and they didn't solve the problem but they made a lot of progress in suggesting or they found various equivalent forms of the problem and they suggested various attack strategies to attack this problem and it was one of those strategies that so there were many that actually looked promising and one of them actually was one one that I used I saw every analytic approach which at the time looked hopeless because it reduced the problem to what at the time looked like an unsolvable problem in multiplicative number theory but then in January this year there was a big breakthrough in not the good number theory on and that actually took a while to realize but that combined with the previous thing was what was needed to finish off the problem plus the new idea which talked about later so one of the things they formalized was a reduction of the problem to multiplicative functions so actually I should say before I said let me say some another thing so this is a sequence about plus minus one sequence sequences you can ask about other sequences of course you need some lower bound on the sequence like this thing is all zeros of course he can make discrepancy zero so actually what I approve is a more general version so in fact what is known now but if you if you a sequence not just plus or minus one but you can live in the unit sphere of any cupboard space we look complex then all these sums are in bandwidth so so now these are vectors you take the normal place vector in your home put space you take a super baldie Len this is infinite okay so the original problem is just a special case when you think the rule over states are that you can take for example complex numbers in your circle or vectors or whatever so this is actually what I prove so already in when Irish formally the problem back in the 1930s he realized that there was a key special case of this problem so I wanted this home is it should be sort of easy because it it should be very difficult to create a low discrepancy sequence because there's lots and lots of different partial sums you can make this there's two parameters N and D and so most sequences that you write down will have large discrepancy whatever a random sequence or large discrepancy but there's a special class of sequences for which it should be a lot easier to make a low discrepancy sequence and hence those should be among the hardest cases and those are what are called the complete market of functions so just remind you a function the natural numbers to the let's say the the unit circle is simply completely more talkative nice complex numbers for general if F of M is equal F of n comes after them for K for example F of 15 is F of three thousand four five so examples of la película sequences so go through b1 is a sequel the all ones sequence and another important class in number so these shop a lot number theory an important class are arduously characters these are these are complete ma orthogonal function that are also periodic so I just give you one example now if you take this just the sequence which is plus 1 when n is 1 1 3 0 n is 2 mod K so ik minus 1 went into more 3 and 0 when n is 0 1 3 so the sequence 1 minus 1 0 1 minus 1 0 periodically this is a completely logical sequence another important example 2 across the lu lu b function land of m which is minus 1 of the number of prime factors I'll be in counting multiplicity so lambda of 6 is plus 1 lambda of 4 is plus 1 lambda of 12 is minus 1 and so forth that's also completely na+ these are some examples of probably not particular functions so one corollary of of this theorem is that it think if your function is also quickly more positive then this F of D can be factored out so one for all the weight set if half click advising us our code is completely more talkative then just the partial sums are unbounded so partial sums of a completely map look at a function taking values in the inner circle unbounded just because yeah f of G can be factored out of this sum in in that case so so Irish back 93 appeared 1958 but but even then so so this this special case was it was also open and it's not it's not trivial so for example the fact that the cv is on the lupo function plus minus 1 that the partial sums unbounded this was known but in order to do that you needed to know that there's at least one non-trivial 0 of women zeta function in the critical strip which is true is known but it's not an obvious thing okay in fact actually you can prove more because you have this arbitrary Hilbert space it's actually a slightly stronger corollary so that if f is not just a complete map well it's not a single mode or packet of the function but it is a random we monthly the function so it's it's a it's a random variable in the space of completely mopping approaches from entries to Z then if you take then if you take these partial sums which are now random variables they take their variance like you look at the second moment these guys aren't bounded - this is a generalization of this fact and and that is again as a consequence of this theorem but now the hilbert space you take is the space of square integrable random variables so alright okay i won't i won't go through it but there's a simple way to deduce this translation from of this ok so now i can tell you one of the reasons why it was realized this problem is hard okay so so as if he saw this discrepancy for me you must at some point be able to show that partial sums of molecular functions are bounded on the other hand we have these douche like characters whose partial sums are bounded okay like if you take this series of like one point minus 1 0 1 minus 1 0 1 minus V so that sequence is Kali multiplicative and it is the sums are bounded so that's almost a counter example to the additional scripts your problem there's this sequence the only reason that is not is that it's got some zeroes in it so you can try to get rid of these zeroes so this is an example or wine tycoons so you you define a function f of end to be okay well you find like this so if you any number and you factor to power three times a number which is not give us a point three and just pack of the three out and you you take the dish that character what's left so you take any number you factor our three and towards notice of our three and then you pick either plus or minus 1 depending on whether what's left is either plus 1 or minus 1 okay so this is a sequence net so now the sequence is like the delay character except that instead of being 0 or third of the time it is now always plus or minus one so I think the series looks like this plus 1 minus 1 again there you another plus 1 minus 1 plus 1 minus 1 make another plus 1 so forth okay as I see what looks something like this so this sequence has a very low discrepancy so it's completely my applicative take values minus 1 and fun to a computation if you some of the you have partial sum this is the number of ones in the base to expansion okay there's a cute little exercise so yeah okay so in particular it's always bounded by log 3 of n so this is a sequence plus minus ones which does have unbounded discrepancy it is not a counter example to the to the conjecture but the discrepancy goes very slowly it was log with likley which yeah you can play this example a little bit you can insert some random factor depending on a and if you do that you can make the sequence so there's a random sequence and then you can make the these the size of this sum not just log at the square root log in if you do it properly and so actually there's discrepancy in these Vitamix apples you can make go as slowly as log square root of log in which actually kind of fits a queue the numerical data that we getting as to how slowly the university is he hitting quiet so the thing is it's it's um yeah it only just barely true this this this conjecture that there are sequences we have very no discrepancy but not quite bounded and so there's a fine separation between between boundedness and unboundedness okay so one of the things so i told you about these qualities of the urge discrepancy theorem so what are they made of the first breakthrough was by polymath who show that Nonis as a quality of you on one basic unit of equivalent okay so this is quite amazing actually because this is a sequence this is a theory about arbitrary sequences of unit vectors and this is a about a very special type of sequence okay random but there's an ignorant the complete multiplicative sequence which we charge much very much more special type of sequence and so it's it's actually quite amazing that that this is all you need but actually what once you wants you you are inspired to look for this connection this is this a key not difficult to prove that this is the one page proof the basic idea is a Fourier expansion so it turns out that somewhat not every function is coming more purgative a complete of optical function is actually if you think of it correctly it's a character on the multiplicative group semi group of all of the year doctor numbers now that's not a group so you have to you have to truncate it and massage you into a group like that technicality there but but borrow the complete market morphling functions are like characters and you can you can decompose any function f into a linear combination in principle of complete market of functions as by some sort of Fourier decomposition and you apply plancherel theorem and you follow your nose and actually yeah so you you are you are not so any kind of function will not be a single complete molecule function but it'll be some sort of composition of completely molecule functions with some density which we square summable this list with this the squared is density this that's what gives you this random measure which defines for you a a random applicative function and if you just play on a plant rows theorem a little bit you will find that these are IQ equivalent so it is not difficult but I'm not going to give the details here so roughly speaking what the polymath project showed was that you basically roughly speaking all you had to do was supposed to understand completely multiplicative functions and then if you do that then then then you be done and it was at that point I would say very the event of the problem that we really did not understand completely molecular functions very well in 2010 and so they say tried several things which also didn't work it and by 2012 they had abandoned their project although they had some other very interesting approaches which maybe it will work one day but ok so proving something is proving me something unbounded is related to correlations because so it's closely related to the public understanding pair correlations between these functions so to illustrate this let me give you a proof of a simple fact which is alright so if you take a rational number rational number and you look at these partial sums equal to PI alpha J squared J equals 1 to N so sub discrete gal sums you're selling these these these these points on the unit circle going around quadratically in some W a tional rate here and you take this partial sums these guys aren't bounded okay that as you some they become at about it now this is kind of not surprising because so you expect these to be these the some to behave like and something n random things and get some inventors size once you get someone else iceberg we did but what stops there being a huge conspiracy that every time you you know this there's some really good cancellation so sub random behavior that makes us bounded now you could break out your view of you know high-tech and Link number theory and IQ try to computer something and in this case you can to some extent but this is this but if you just want shows unbounded you can argue as follows okay so I suppose not it suppose that these times are all somehow magically bounded so then what you do that you pick a pick a large H you know like a thousand and they're gay and then randomly pick a huge end like somewhere bit so if each si like a thousand pick in between a billion and a trillion or something I said some some really big value minimum okay now if all the partial sums are bounded I guess this is not a big it's not a fully detailed proof but what you do is you take a short some you you look at them so it's e to 2 pi I and plus J squared times alpha you take a short segment of our partial sum between N and n plus h so he just picks up at a random medium-size interval way out in the natural numbers and if these guys were bounded then these guys also have to be all bound because the difference of two of two partial sums okay so the thing is if you pick up so you think of h sx you pick a large run a number n you're adding n random things okay and each so we can because as the sum of n random variables they each will have magnitude 1 meter basically zero because alpha is a rational and you can show with some simple computation live alphas are rational so you can think of these as you can pick it as a sum X 1 plus n 2 XH with these are all different random variables it means you are variants one and they are they're decoupled with each other you can show that the correlation between each of these guys is small this small just this fall okay 30 V if you if you take this guy you multiply by the conjugate of another quadratic thing the quad comes can so you get a nice linear sum and because alpha is irrational you can easily show that the sum because is very small the average so you are summing n random variables of variance one with almost no correlation between them and therefore the variance of the sum is it something like H and so I can make this sum the variance of the sum as a random variable I can make as big as I like by making H as big as I like and so I can make these sums as pairs because as I please so there's a probabilistic argument I based on pair correlations that if you know that pair colleges are small then you can make then you can make you something bounded you can think this it in the contrapositive if these partial sums are bounded then there must be some correlation between the must be a conspiracy between adjacent elements your sequence something must've must be not random somehow to see some correlation if there is if you wanna make this sums bounded and so you can use that sort of argument using the sort of argument you can show if we have all these multiple sequences but if this sum is if this sum is bounded these things are bounded then there are large correlations like I said so then there exist some check H that you look at a correlation and sorry like this okay that if you look at how a tip and amendment in the sequence is call it with shift then this has to be large like bigger than some constant okay so normally when you take take a random looking sequence there should be no coalition which we never been in definitely this age so if you could show okay so if you could show that these coalition's are small then you'll be done to be able to improve the just discovery problem so the polymath project already got this far but then they got stuck because even the special case of the Louisville function for example if you wanted okay so so if you wanted to apply the strategy you would have to take let's have to work for any any mullick function so in particular the Louisville function and you would have to understand how the Louisville function call it with with n color of n plus 1 and you would want this distal go to 0 and this is conjectured to go to 0 there's a conductive chawla it's called a shallot conjecture and same with your place M plus 1 by other ships you can have many lambdas in here and so forth there's a conjecture as to what these collisions are there was 0 but this conjecture was considered extremely difficult it's it looks very similar to the twin prime conjecture right Jin prime conjecture - this is about how many times you come again it was to both prime this is mahogany NN n plus 1 both have even number prime factors automatron factors it was considered of equal difficulty to the to the prime number to do the trim prime conjecture which is still open so at this point I said oh you would need you know immense breakthroughs in number theory to transfer that and so the polymath vortex of stock at this point and working on other ways to attack the problem okay so in January of 2015 there was an amazing breakthrough by Matt Maki two young people - she's she's in Finland Caixa at Fanta Maki and Maxim vegetable like this so they didn't quite show the Chava conjecture what they showed was something that looked a little bit different to begin with okay let me freeze address so that if you take ancient medium style phrase it's somewhat somewhat roughly so if you click age somewhat large and really large or huge and random okay and you look at this partial sum you some example blue a function but it also works for other molecular functions crucially be some summer block above the louisville function from 1 to h some really large london block okay so this is clearly as this is this is clearly as big as h okay so you could this girl be plus 1 will be minus 1 so it's clear as big as h but what they showed is that usually it's a key lesson h okay that given any epsilon you can make the sum less than a small model of h4 for most n okay now there's a lot of quantifiers which are suppressing okay too many way to make it was a emphasize but basically they were able to show some cancellation in this sum so all right so yeah they they show this and then later i was able to to to work with them to improve this a little bit you can also stick in some some phases like this okay do some other play some other games like this using their method so yeah so I won't talk about how how they did this but they they use some they they used classical methods of Duty series complex hours is very cleverly and they can carefully but but this is a great way to so so I ah maybe in July or something no it's a number here so I was I was I was working with guys about marking and Maxim gradualness and I managed to use the theater booze and other things we had some joint papers and I put these joint papers on my blog and I talked about them and at one point I commented that that the type of argument we were using to how to exploit these these results reminded us of solving a Sudoku puzzle that there was the always thing that games of you know I want I want these plus plus one like I I don't want three plus ones in a row and so and so for like what kind of sign patterns can I can I have it with certain constraints and then someone on my blog who was active in the problem of five projects said you know what you're talking about sounds very much like the type of things we were discussing in polymer 5 is it any chance that that that these methods that could be used to attack the discovery problem and so I apply was saying no I don't think so yeah but naive each other thing is the matter back a matter what we're proving upper bounds on things so they're proving at least sums us up small and what you wanted to prove was a certain sum so big and so I need is thought so therefore the complete different problems so I said this film bearing is to comment is still there but but there's someone else I actually know I could ask repeated the question could you say more about the possible connection there so actually we look back at it and then it then I realize that actually there is something you can do because and so the original problem is up about but but phrasing of the correlations you need to move an upper bound on this correlation to prove a lower bound on the partial sums and so yucky it is much more plausible okay what you need to do somehow is to be able to leverage this up about on on the Louisville function to prove something like this up about to prove some upper bound on the solar cell now that looked hard but actually there's something that actually ok so Maxime and I were actually thinking about a little bit and we had an approach to this problem which we also gave up on but now that I was motivated to go look at a guy that sort of dusted at all so this looks hard because this is the thing is that it's very easy to think of a sequence for which the sum is very big you forgot with the letter K I which is I want NT plus 1 minus 1 plus 1 minus 1 and so forth and then the symbol root would be would be huge now that particular said I can't happen I keep because of a lot of people but I can vegetable this if there's a version in math make progressions that you can use but there are other scenarios like this this sum is somehow too too easy to make big but there was a trick that we already saw to turn the sum into a sum that was less easy to make big but it could still be we still couldn't stop it being big so the key observation is that yeah so the the enemy let's talk about the Louisville function but of course you have to do other functions as well eventually yeah so the enemy is is the case where lambda n plus 1 so we would lambda in for many n ok there you can have big stretches and by put big stretches of space where with the Louisville can exact exactly the same side now what mathematical ads will show is and what are the quantum is what they do is is that this can't happen say night nights in the time I think that but what we need actually is that is that this can't happen 51% of time and that was that was seemed a lot harder ok but if yeah so if if the Lu function had this sort of weird customers it always to be locally constant quite a lot then because it's also more placated you would also get that if you hit not by one but by a prime XI Phi Prime that should also be he should also be equal for many and divisible by prime okay so if n is visible by prime so if n is like P times M then lambda p.m. is just the same with minus lambda M and this is minus lambda k plus 1 and we assume that lambda first one and I've never equal for many M and so therefore lambda so what this suggests actually so then this is funny you can you can explore this graphically so this is certain graph on the laptop natural numbers you can do you can place where you connect any point n with n plus P whenever fused it was a we're happy okay so you connect everybody to their neighbor every even number gets connected to the guy two guys out two numbers down every more for three gets connected to it's not like that and so on and so forth is the same for the graph and so this is a flow graph G and basically what you can show using this through now is this roughly speaking and lying a little bit is that if this sum is large then okay we roughly speaking they be sum of all pairs in this graph I'm looking letter M this is also punch I could get to truncate the graph in a certain way and I'm not going to talk about you how you do that but you can sum the Lua function on this graph so you take all the edges of this graph preaching at the edge of the graph you've evaluate the manoeuvre function at the two end points more time together some that and you can relate this by linear sum to the show linear sort of sum because of the multiple Liberty so if this is large then this is large and so the the hope so was that so so then if you could show Ken if GE wasn't expanded be done Noli speaking that they're these grass cut expanders which I saw these these extremely connected graphs which are which are very mixing in some sense and one of the properties of expander graphs is that is that if you take any function of one row of one edge vertex and another another vertex and you some along you expand a graph you're basically the sum will basically factor into into the sum of the mean value of this guy times me like this guy that there's a they're very mixing and the mean value of this random job precisely what we now understand and so if you had some good expansion properties of this graph you could actually include actually finish to finish the job and and solve the problem so yeah so we had this sort of plan to attack the child a conjecture but then we got stopped because we had no clue how to put this would expand a graph it was a it was it was it was it's very thin and then and random walks on this graph and I'm not easy to understand but the easier and time for short times but not for long times in long terms of what you need so anyway we got stuck at this point but I started looking this problem again a few weeks ago and so what I what I discovered was that this this some so if you don't know that this is an expander graph it's still potentially possible that this um is large but but what you can show without too much trouble is that even if the Summers is is large it's um it's not um yeah so so being an expander graph so so being an expander I haven't defined exactly what expander means but roughly speaking being an expander graph means that as some like this factors into basically the plus a product of individual sums there's some decoupling for all choices of okay that's so roughly speaking what it means to be expanded there's a formal as a formal version is called exacts found a mixing limit but okay if you notice and then if you have that then you can just apply that to to this sort of sort of sum and you'll be done now so we have I still don't know what this is trust I think it's how I guess is true but I can't prove it but what what turns out to be a lot easier to prove and some idea I can't realize as well as waiting in the car for my son to finish his piano lesson I get nothing else to do so I detect this problem is that is that what you can prove very easily is that for this funny graph if you pick it so I don't know for whether for all choices of apps of these signs you can get a banneker's but for most choices that there's an exponentially small set of exceptions for which you can get a bound like this that there's a you get mixing for most choices of of inputs and all now this doesn't quite solve the problem because this sequence lambda could be could decide to - - did the the sine patterns of consecutive strings of lambda could decide to do to live in the exponentially small set of all the exceptions where this the son fails so but what I could then show because using this fact is that is that if if if this sum he was large okay then the sequence that the sequence lambda 1 and 2 and so forth experiences okay a sizable drop a significant drop in China and row Creek now I'm just going to tell you what I mean by this okay so for any given H we pick a medium-sized H like a thousand you can pick up a large random sub P pick a medium-sized H and a large random and and you can look at this sequence the six equals plus or minus ones and you can look at the sequence in in the block from n plus 1 to n plus h so if you take a tiny when you take a medium size window of the Louisville secret somewhere way out and the natural numbers that's some sequence of h plus or minus ones so you can think of as a random variable a random string of Plus Ones and minus ones taking values in mind taking values somewhere it's one it basically unit in the in having cube of the size H so that's about it variable which takes a discrete number of values to the H possible values so it has a Shannon entropy every time you're a random variable you can define a Shannon entropy to be sum over for all outcomes P Omega born with P Omega P Omega is so the probability that X is forming okay so you can talk about this random string and you can compute n is entropy so if so the conjecture is is that the the Louisville function is spread uniformly so that the sine pattern should be spread uniformly on the Hamming cube and so the the entropy here should actually be log the size of having Q okay so basically these log base two for example you should be H okay so you should take H bit H piece of information to to - to express a random block of H numbers in Louisville sequence but what you can show yes early sodium yeah so in particular particular normalized entropy you take entropy or a block event H divided by H this is somehow the compression rate how much you can compress this this big string L plus minus ones so so if there's a lot of structure in the sequence you so this is awesome this time between 0 and 1 it decreases as H gets bigger there's a subadditivity and so it passes to a limit which is what's which is 2 which is called the entropy or the sequence kimono of entropy of a sequence coming up soon I entropy but and it so measures our our structured the sequences but using this fact that this sum is is true for Obon exponentially smaller set of exceptions you can show that if this sum is bigger a lot of the time then there's a drop in entropy or what that means is is that if you take a block of length H and then you you go up to a block of let's say 10 H the entropy in principle could be 10 times as big for Bach about 10 H as it is for document H but it actually drops a little bit at the you can you can you can bounce something like like the intro video on welcome to 10 h by 10 times the block of age - something - - or - a little bit if this sum is large because the the set of fate is okay because Cygnus M is large means that means that lambda is living in it in a very small set of all possible sign patents and you can use that so every time that I can't prove my theorem the entropy drops and there's an upper bound on the entropy and so you can use the pigeonhole principle to say that eventually as I keep expanding my block to be bigger and bigger somewhere there is a sun block with it what I do not experience this drop in entropy and then that makes this sequence sort of mixing in some sense in that scale and then I can avoid this especially small set of signs that I don't understand and then that actually prove this theorem so to our knowledge is the first time where information theory the Shannon entropy inequalities were used to prove a human number theory so I make you quite excited about this technique I'm hoping we can you can prove other things in number theory yes as well and yeah and then of course is that the other part which which is which is yeah which was always really nice to to be by making it salt I think that is a good place to stop

Channel: Institute for Pure & Applied Mathematics (IPAM)

Views: 317,434

Rating: 4.915617 out of 5

Keywords: Terence Tao (Academic), Paul Erdős (Academic), ±1-sequence, Discrepancy Theory, Mathematics (Field Of Study), Terry Tao, IPAM, University Of California Los Angeles (College/University)

Id: QauoO0j9Y9Y

Length: 51min 49sec (3109 seconds)

Published: Fri Oct 09 2015