so I'll be speaking about some work I did a few weeks ago actually uh on the U on in discrepancy Theory um so discrepancy Theory roughly speaking is a study of how well balanced or well distributed uh you can make various sequences or of numbers or points uh things like that uh so for instance you can consider plus one minus one sequences suppose you have a sequence of numbers which are either minus one or plus one so um some some signs um and you want to make the 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 ones and plus ones to be in very um equally distributed in in in some sense now of course this is not a world defined question because I haven't told you what World Balance means um so for example a very naive thing is 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 um um all the partial sums um small and and this is very easy um I can make all the partial sums in fact less than one simply by choosing the outting sequence okay so this here's a sequence where if if you look at any interval um the discrepancy is is is almost as small as it can be um okay so this is much better by the way than a random sequence if you flip coins and you pick a plus minus one sequence randomly then um in any block of length n you expect um to be able to find some subblock where where the the sum is about root n maybe up to a log Factor but you can make it bounded okay so this is not an interesting question um it's more interesting if you ask for stronger Notions of of discrepancy where you don't just um ask that partial sums are small but also sums in arth progressions um and once you do that then uh it becomes um a lot harder uh to make the discrepancy small uh so for example this class goes out of Arden um I think from the 19th century um that uh says that um that you can find okay find arbitrary long athic progressions a A plus r 2 R up to say A+ K - 1 R where there is no uh cancellation at all where where all these guys are the same are the same okay so in other words if you sum uh the sequence if you look at it in this particular progression yes so yeah so uh given any infinite sequence of plusus 1 you can find arbitrarily long progressions where um uh where the sum is as big as it can be there was there was no cancellation that that all that if I if I look for example if K is 100 I can find a progression on the 100 where all the um in this progression you just get all plus ones or minus ones so there's no so the discrepancy can get arbit really big in particular um okay uh very famously there was a strengthening of this the judism already so this them tells you that uh that you can find progressions where um all the entries are either colored plus one or color minus one but it doesn't tell you which one uh but Z theorems is a strengthening proven in 75 um which I was born actually um to um um um uh which tells you sort of which sign that you can make so um Z theorem says that if for example if you know that that plus on occurs fairly often if plus ones occur for a positive density uh strictly speaking positive um upper density but never mind what that means so like if if if your sequence is plus one even .1% of the time um then uh then you can find uh progressions as before where now all the signs are plus one okay um so that's a great theorem um at Le three fuel Metals one Al priz came out of that but anyway um okay but um all right so we have that theorem um another notable theorem is a Roth discrepancy theorem which is a bit more quantitative um what it tells you is that if you have a sequence but now a finite sequence of plus and minus 1es okay then inside the sequence you can find an arithmetic progression inside the sequence where um on this on on the sequence the discrepancy is fairly large let's say A Plus Jr so if you sum up your elements in the sequence um uh Kus one there was some AR progression where there's a lot of imbalance that this this this sum is actually pretty big it's actually um I think the B you get one quar time the constant which you can take to 12th for instance it's not the constant is not important but uh you can find a sequence somewhere where there is there was actually quite a bit of imbalance ental one quarter um and this ental one quarter is actually the optimal exponent although we don't have a an explicit construction actually of uh of the sequence that does that but we know that it can't be improved it's kind of a weird situation but yeah so if you if you um if you allow all progressions if if you want so what this is telling you is that it is actually not possible to have a um a sequence a long sequence which is well balanced in every single arthic progression there must be some arthic progression where the plus ones and minus ones are out of balance so there's some limit as to how well distributed uh you can you can make sequences if you allow all arithmetic progressions okay so way back in the 1930s um Paul erish was very interested in these questions um for example he conjectured zus theem um which turned out to be true um and so um you knew about Ross theorem um uh that that you had to um that if you allow all progressions um then somewhere you you must get um a very big sum um so his the question he asked was that suppose you you you you um you don't look at all progressions but you look at what are called homogeneous arthic progressions which start which starts say zero or um where a is zero um so let me phrase it this way okay so U the erish discrepancy problem okay so that if uh let's phrase it first for an infinite sequence if you have an infinite sequence plus minus ones um uh are the sums let's call them let's say F of JD from J = 1 to n are these sums in other words F of D plus F of 2D plus F of n d always unbounded okay so Ross theorem or actually also theorem or V the any of these theorems tell you that you you can make if um that if you have a long enough sequence you can you can find um some arithmetic progression where the sum is large but now if you restrict to the homogeneous arithmetic progressions the ones that that start at zero basically D 2D up to up to ND can you make um uh can can you make this sequence this sequence large um so an equivalent way to phrase this question um equivalently okay so given any c uh does there exist an N okay so given any constant C does there exist an N such that every sequence every finite sequence now F of one F of n of plus oneus one on just that for every sequence um there is uh now homogeneous arithmetic progression n2d up to uh ND somewhere in this range uh such that if you sum up all these values you get bigger than c um okay okay so uh actually there's a YouTube video of someone explaining uh this using a pit of snakes and a cliff um I'll repeat this um so the uh the reformulation is that you've been captured by some statistic torturer and um and you're placed at the origin of this uh uh of of of of of some onedimensional line uh and then there's a cliff here at some at at some point C where you you fall off and die uh and then there's there there's also at minus C there okay well he put a a pit of venomous snakes okay which in which will also kill you okay but whatever okay all right I can't draw a snake Okay um and you're here okay and what you have to submit to the torture is is is a sequence of of of moves you can of of left and right moves okay and you just submit a long list of lefts and rights um and then once you give them um thatal torture the torture will then force you to move right or left according to to the instructions you gave except that the uh the the torture may not give um um the Tor the torture gets to choose either he he gets to to uh to to um to give you the sequence um um all the element of the sequence or he'll only give every second element of the sequence or every third element of the sequence or every fourth ele of the sequence so he gets to pick a skip um and then he will force you to move right or left according to the sequence and uh your task is is is to find a a uh um a chain of uh of less and rides which will let you survive no matter what the torturous um chooses for you okay so this is an equivalent formulation it's quite colorful um anyway so um um this is kind of so one nice thing about this equivalent formulation is that is that you can attack it numerically you can pick specific guys of C like one and two and three and so forth and then you can you can see what happens so for instance um if C is one uh you're actually really bad shape um the uh um uh you got to uh yeah you can take n equal one you you'll die as soon as you submit a single step which is pretty clear um if C is two um then actually you can survive for quite a while um there was a sequence of 11 steps uh that you can submit such that uh uh which I I didn't write down but you can find it uh where in fact it's basically unique up up to sign uh which will let you live for um um no matter what what you pick here so that's that's if you have a a width two margin but 11's sharp if you have 12 actually a fun little exercise actually almost like soing a PSE Sudoku puzzle um to show that that uh that if you submit 12 uh then then then you're a toast um but uh yeah so so so 11 is the Shar um Cal 3 uh things already uh you can not survive for quite a long time so uh this was actually worked out last year uh so uh those um there's this amazing uh computational work of K of andit in last year who did this massive threet problem uh which is what this is basically um and what they found uh was that uh was it the optimal and in this case was 1161 so first of all they found a sequence of L 1161 with a property that that no matter what skip size you pick you you can always survive for for this particular choice of C which is already amazing but even more amazing is that they show by this massive thre side compation that that that 11 162 you you could not uh survive um and the verification uh of of that uh of the argument is is a file which is I think what 13 gigabytes uh which which uh so the the the media picked up on this is this is this is a proof that's larger than Wikipedia U and in some sense it is the largest proof known of of uh uh of of of a you know in a serious mathematical uh publication okay um yeah okay now Cal 4 uh we don't know what exactly what the the Shar value of n is but it is at least 13,000 that uh the same authors did construct a sequence of 13,000 which had discrepancy at most four which means that all these partial sums are at most four um okay so it's um so you can see that this it goes quite slowly um you know I mean and you have to pick your sequence quite carefully if you pick a random sequence um of length n your discrepancy is going to be about root n and so you will not get anything nearly as good as this okay so anyway um yeah so about uh two three weeks ago maybe uh yeah okay so uh I prove this theem so so the answer is yes um that that these sums are always unbounded or in other words for for for every C there is a finite n um uh for which uh for which the discrepancy must be bigger than SI okay so let me tell you about the type of things that go into the proof so this problem has been attacked quite a lot in the past actually um most recently well there's this competitional attack but um from about 2010 to 2012 uh there was also a serious attempt uh at at proof by uh what's called the polymath project this was actually the fifth poly polymath project so was called polymath 5 um it was run by Tim goers so a polymath project is a project Run online using things like like blogs and wikis and math W actually um where um instead of having one or two people working sort of secretly or you not at least not publicly on these problems you you do everything out in the open so so you know um every thought that anyone has you just throw it out there even if it's Half Baked actually especially if it's Half Baked and then someone will will pick up on it so there was always numerical computations and people tried throwing out all these different ideas um and they didn't solve the problem um but they made um a lot of progress in suggesting uh they found various equivalent forms of the problem and uh they suggested various attack strategies um to to attack this problem um and and it was one of those strategies that uh so there were many that that actually looked promising um and one of them actually uh was one one that I used uh a sort ofor analytic approach um which at the time uh looked hopeless because it reduced the problem to what at the time looked like an unsolvable problem in multiplicative number Theory um but then in January this year there was a big breakthrough in multiplicative number Theory uh on um and that actually uh it took a while to realize but that combined with the previous thing was what was needed to to finish off the problem uh plus a new idea which I talk about later so um one of the things uh they formalized uh was a reduction of the problem to uh multiplicative functions so actually uh I should say before I say that let me say one other thing so um this is a sequence about plus minus one sequence sequences um you can ask about other sequences of course you need some lower bound on the sequence like a sequence La is zero of course you can make discrepancy um zero um so actually what I prove is is a more General version so in fact what is known now if you have if uh you have a sequence not just plus minus one but but you can live in the unit sphere of any hit space real or complex then all these sums are unbounded so so now these are vectors you take the normal of this Vector in your hit space you take a super for all d and n this is infinite okay so the original problem is just a special case when you take the real h space r but you can take for example complex numbers in your circle or vectors or whatever um so this is actually what I prove um so already in when erish formulated the problem back in the 1930s he realized that there was a key special case of this problem so um on one hand this problem is should be sort of easy because it's it it 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 for example random sequence will have large discrepancy um but um there's a special class of sequences for which um it should be a lot easier to make a l discrepency sequence and hence um those should be among the hardest cases and those are what I called the completely multiplicative functions so just to remind you a function the natural numbers to the let's say the uh um the unit circle is that be completely mulative actually complex numbers for General if F of n m is equal F of n * F of M for o n m okay for example F of 15 is f of 3 * F of 5 um so examples of multiplicative sequences the tri one is the o1 sequence um and um another important class in number so so these shop a lot in number Theory um an important class Ur characters these are these are complet multiplic functions that are also periodic so I just give you one example if you take this this the sequence which is plus one when n is 1 3 0 when n is 2 3 sorry minus one when n is 2 3 um and 0o when n is 0 3 so the sequence 1 - 1 0 1 - 1 0 periodically this is a complet sequence um another important example What's called the L Lou function Lambda of n which is minus one of the number of prime factors of n counting multiplicity so Lambda of 6 is + one Lambda of 4 is + one Lambda of 12 is minus one so so forth that's also completely multiplicative these are some examples of completely multiplicative functions so um one coroller of uh of this theorem is that it uh see if your function is also completely multiplicative then this F of D can be factored out so one corer that if F uh taking place in un circle is completely multiplicative then just the partial sums unbounded okay so partial sums of a completely multiplicative function taking values on the UN Circle are unbounded um just because uh yeah F of D can be facted out of of of this Su in that case um so so ear back in 1930 actually it appeared 1950 but uh but uh even then so so this this special case was was also open um and it's not it's not trivial so for example the fact that this if you some the lvo function plusus one that the 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 zero OFA function in the critical strip uh which is true it's known but that's not an obvious thing um okay um in fact actually uh you can prove more because you have this arbitary HT space uh there actually a slightly stronger corer um so if f is not just a complete M well if is not a single multiplicative um function but it is a random M function so it's it's a it's a random variable in the space of completely mul functions from n to Z um then uh if you take uh then if you take these partial sums which are now vandom variables and take their their variance actually their second moment um these guys are round two uh this is a a a generalization of this fact um and and that is again a consequence of this theorem but now the HT space you take is the space of square inable random variables um so uh okay I won't I won't go through it but but there's there's a simple way to deduce this terization from from from this um okay so now I can tell you one of the reasons why it was realized this problem is hard okay so um so as a if you solve the discrepancy problem you must at some point be able to show that partial sums of multiplicative functions are unbounded um on the other hand we have these dis characters whose partial sums are bounded okay like if you take this series of like 1 - one 0 1 - one 0 1 so that sequence is completely multiplicative and it is the sums are bounded so that's that's almost a counter example to the erish discrepency problem this sequence the only reason that it's not is that it's got some zeros in it um so you can try um to get rid of these Zer um so there's an example of Bine CH Coons so you you um you define a function f of n to be um okay well you define it like this so if any number n you factor to a power three times a number which is not divisible by three and you just Factor the three out and you you take the differ character what's left so you take any number you factor three until it's not divisible by three and then you pick either plus or minus one depending on on whether what left is either plus one or minus one okay so this is a sequence so now this sequence is like the Der character except that instead of being zero 1/3 of the time it is now always plus orus one um so I think the sequence looks like this plus one minus one again then you got another plus one minus one plus oneus one you get another plus one so forth okay this a sequence look something like this um so this sequence has a very low discrepancy so it's completely multiplicative takes Val in plusus one and I found computation if you if you sum of the the artal sum uh this is the number of ones in the base three expansion okay so this a cute little exercise um so uh yeah um okay so in particular it's always bounded by log 3 of n um so this is a sequence of plus minus 1es which does have unbounded discrepancy it is not a counter example to the um uh to the conjecture but the discrepancy goes very slowly it goes logarithmically which um yeah um you can play this example a little bit um um you can insert some random Factor depending on a and if if you do that you can make the sequence uh so there random sequence and then you can make the uh these um the size of the sum not just login but square root login if if you do it properly um and so actually there's discrepancy in these random examples you can make grow as slowly as as log square root of login which actually kind of fits actually with the numerical data that we've been getting as to how slowly the uh the numeric C has been growing so the thing is it's it's it's um yeah it's only just barely um true this this uh this conjecture that there are are sequences which have very low discrepancy but not quite bounded and so there's a fine uh separation between between boundedness and unboundedness okay so one of the things so I told you about these corollaries of the discrepancy theorem um so one of the amaz the first breakthrough was by polymath um who shows that not only is this a cery of theum one but it's actually equivalent okay so this is quite amazing actually because um this is a sequence this is a the about arbitrary sequences of unit vectors and this is a a the about a very special type of sequence okay random ignore random okay complet mulative sequence which which are much rarer much more special type of sequence um and so it's it's actually quite amazing that um that this is all you need um but actually once once you you are inspired to look for this connection this is actually not difficult to prove it's a onepage proof the um the basic idea is is a FAL expansion so it turns out that so why not every function is is completely multiplicative a complet multiplicative function is actually if you think of it correctly it's a character on the multiplicative semi- group of of of theb now that's not a group so you have to you have to truncate it and and and massage it into a group a technicality there but but morally complet M mul functions are like characters and you can uh you can decompose any function f into a linear combination in principle of complete multiplicative functions as by some sort of f decomposition um and uh you apply PL R theorem and you follow your nose uh and actually um yeah so you you are not so any given function will not be a single um uh complet mular function but it will be some sort of superposition of complet mular functions with some density which would be square summable um this this um this the square this density that's that's what um gives you this random measure which defines for you a a a random applicative function and if you just play on PL Rose theorem a little bit you will find that that these are actually equivalent um so it's not difficult but I'm going to to to the details here so roughly speaking what the poly project showed was that um you basically roughly speaking all you had to do was was to understand completely mulli functions and then if you do that then then uh then you'd be done um and it was at that point that they they ran into the problem that we really did not understand completely M functions very well in 2010 um and so they they tried several other things which also didn't work and and by 2012 they had abandoned the the project um although they had some other very interesting approaches which Maybe it will work one day but um okay um so proving something is proving these sums unbounded is related to correlations so it's closely related to the problem understanding pair correlations between these functions so uh to illustrate this let me give you um a proof of a simple fact which is uh uh the following so if you take a irrational number rational real number and you look at these partial sums e 2 pi I Alpha j^ 2 = 1 to n so sort of discrete GA sums you're summing these these these these um points in the unit circle going around quadratically in some at some irrational rate here um and you take these partial sums these guys are unbounded okay that as you sum they become unbounded now this is kind of um not surprising because uh you expect these to be these the sum to behave like n something n random things and if you add some n random things to size one you get something of about Ro n but what stops there being a huge conspiracy that every time you you know there there's some really good cancellations some sort of sub random behavior um that makes this bounded um now you could break out your your your you know high-tech analytic number Theory and actually try to compute the sum and in this case you actually can uh to some extent um but there's there's but if you just want to show it's unbounded um uh you can argue as follows okay so suppose not okay suppose that these sums are all somehow magically B rounded um so then what you do is that you you pick a pick a large H you know like a thousand and then okay and then randomly pick a huge n like somewhere so H is like a thousand Pick N between a billion and a trillion or something some some really big random number okay now um if all the partial systems are bounded okay this this is not a this is not a fully detailed proof but what you do is you take a short uh you you you look at um um okay so it's e to 2 pi i n plus b^ 2 um time Alpha you take a short segment of of a partial sum between n and n plus h so just pick a a random medium siiz interval way out in the natural numbers and if if these guys are all bounded then these guys also have to be all bounded because the difference of of two partial Subs okay so the thing is if you pick a so you think of is fix you pick a large random number n you're adding n random things okay and and each so you can think this the sum of N random variables um they they each have magnitude one and I mean it basically zero because Alpha is irrational um and you can show with some simple computation if Alpha is irrational so you can you can think of this as as you can think of this as a sum X1 plus up to xh where these are all different random variables um they all have mean zero um variance one and they are um they're decoupled with each other um you can show that the correlation between any two of these guys is small is small just say small okay that if you if you if you take this guy you multiply by the conjugate of another quadratic thing the Quadra cancel you get nice linear sum and because Alpha is IR rational you can easily show that the sum is very small in 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 something like H and so I can make this sum the variance of the sum as 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 big as as I please so there's a publicistic argument based on pair correlations um that if you know that pair correlations are small then you can make um then you can think these some's unbounded um you can think of this in the contrapositive if these partial Syms are bounded then there must be some correlation between there must be a conspiracy between adjacent um elements of your sequence something must um must be non-random somehow to um must be some correlation if there is uh if you want to make these sums bounded and so you can use that sort of argument um using the sort of argument uh you can show if we have one of these multiplicative sequences that if if if this sum is if this sum is bounded if these SS are bounded then there are large correlations okay so so then there exists some shift H so that if you look at a correlation sorry like this okay that if you look at at at how um a a random element in the sequence is is correlated with with shift then this has to be large like bigger than some constant okay so normally when you take a random looking sequence there should be no correlation between f ofn and f plus h um so if you could show okay so if you could show that that these Coalition are small um then you be done you'd be able to to prove the discrepency problem so the polymath project already got this far um but then they got stuck because um even in the special case of the louvo function for example if you wanted okay so um so if you wanted to apply the strategy you would have to take this work for any any mulp function in particular the Lou function and you you would have to understand how the Lou function correlated with with of n n plus one and you would want this to somehow go to zero um and this is conjecture to go to zero there's a conjecture of chowa it's called a chowa conjecture and same if you replace M plus one by other shifts you even have many lambas in here and so forth there's a there's a conjecture as to what these coions are they were zero um but this conjecture was considered extremely difficult it it's it looks very similar to the twin Prime conjecture right twin Prime conjecture is about how many times you can make n and n plus two both Prime this is about how you can make n and n plus one um both have even number of prime factors or odd number prime factors it was considered of equal difficulty to the um uh to the prime number to to the TR Prim conjecture which is still open um so at this point they said oh you would need you know immense breakthroughs in in number Theory to to advance further and so the poly projects stopped at this point and worked on other ways to attack the problem okay um so in January of 2015 uh there was an amazing Breakthrough by mataki two young people she's she's in Finland kaisa at Mamaki and Maxim Ral at vus um so um uh they didn't quite show the TR conjecture um what they showed was something that looked a little bit different to begin with um uh okay uh let me phrase that like this so that if you take h of medium I phrase it somewhat somewhat um uh roughly so if you take H somewhat large and N um really large or huge and random okay and you look at this partial sum you sum for example the L function but it also works for other mulc function functions crucially U you sum you sum a block of the of the louo function from 1 to H some really large B Block okay so um this is clearly as as this is this is clearly as big as H okay so you could this this could all be plus one be minus one so it it's clearly as big as H but what they showed is that usually it's actually a bit less than H okay okay that that given any Epsilon you can make the sum less than a small multiple of H for uh for most n okay now there's a lot of quantifiers which I'm suppressing okay to to make result precise but basically they're able to show some cancellation in this sum um so um right so yeah they they showed 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 um so yeah so I won't talk about how how they did this but they they used some they they they used classical methods of dur ser and complex analysis very very cleverly um and carefully but um but this is a great breakthrough um so um so I maybe in July or something um no September yeah so I was I was I was working with with with kais matak and maxing r on this and I I I managed to use the the to prove some other things we had some joint papers and I I put these joint papers on my blog and I talked about them um and at one point I commented that um uh that uh um the type of arguments we were using to to try to exploit these these results reminded us of solving a Sudoku puzzle the that that those we were always playing these games of you know I want I want these plus plus one like I don't want three plus ones in a row and so and so like what kind of sign patterns can I can I have there certain constraints um and then someone on my blog who was active in the poly 5 projects said you know what you're talking about sound is very much like the type of things we were discussing in po 5 is there any chance that that uh that that these methods could be used to attack the the discrepancy problem um and so I applied saying no I don't think so um yeah so the thing is the um m m were proving upper bounds on things they're proving at least some us up up up small and what you wanted to prove was that certain sums were big and so un thought you know so therefore they're completely different problems so I said this B embarrassing it's the comment is still there um but um then someone else asked actually know you know asked repeated the question could you say more about the possible connection so I actually look back at it and then then I realized that actually there was something you can do because um um yeah so the original problem is an upper bound but but phras in terms of correlations um you need to prove an upper bound on this correlation to prove a lower bound on on on the partial sums and so you actually it's much more plausible what what you need to do somehow is to be able to leverage this upper bound on on the L function to prove something like this upper bound to prove some upper bound on on on this sort of something um now um that looked hard but actually this was something that actually qu and Maxim and I were actually thinking about a little bit and we had an approach to this problem which we also gave up on um but now that I was motivated to go look at it I sort of dusted it off um so um this looks hard um because the thing is that um it's very easy to think of a sequence for which this is is very big if for example lamb is out plus oneus one plus one minus one and so forth um and then the sum would would be huge um now that particular scenario can't happen actually because of of of of of few well there's a there's a version in AIC progressions that you can use but um there are other scenarios like this this sum is somehow too um too easy to make big um but there was a trick that we already saw to turn the sum into a sum that was less easy to make big um but it could still be we still couldn't stop it being big um so um the key observation is that uh yeah so the the the the enemy let's just talk about the louo function but of course you have to do other functions as well eventually um yeah so so the enemy uh is is the case where Lambda n + 1 so equal lamb n for many n okay that you can have big stretches and by but uh yeah big stretches of of space where where the exactly the same sign um now um what M will show is um one of the consequences of what they do is that this can't happen say 99% of the time um but uh what we need actually is that is that this can't happen 51% of the time um and that that that that was that was seemed a lot harder okay but if um yeah so if if if if the L function had this sort of weird conspiracy to always to be locally constant quite a lot um then because it's also multiplicative you would also get um that if you shift not by one but by a prime if you shift by a prime this should also be the should also be equal for many and divisible by Prime okay so if n isible by Prime um so if n is like P * m then Lambda p m is just the same Asus Lambda of M and this isus Lambda of m + 1 and we assuming that Lambda plus one and Lambda M are equal for many M so therefore Lambda um so um what this suggests actually so then this is funny um you can you can explore this graphically so there's a certain graph on the natural numbers you can do you can place where you connect any point n with n plus P whenever p is divisible by n p okay so you connect everybody to the neighbor every even number gets connected to the guy two guys down uh two numbers down every mulle three gets connected to um something like that and so on and so forth so this this infinite graph and um so this infinite graph G um and basically uh what you can show using this sort of analysis roughly speaking and lying a little bit is that if this sum is large then um okay roughly speaking that if you sum of all pairs in this graph lamb of M lamb M this thing is also large okay you have to truncate the graph in a certain way and I'm not going to talk about how how you do that but um um you can you can sum the L function on this graph so you you take all the edges of this graph uh for each edge of the graph you evaluate the L function at the two end points sum that and you can relate this bilinear sum to this s linear sort of sum because of the multiplicativity so if this is large then this is large and so the um the hope so uh what's that so um so then if you could show okay if G was an expander you'd be done morally speaking um that there these graphs called expanders um which uh so these these extremely connected graphs which are which are very mixing in some sense um and one of the properties of of expander graphs is that is that uh if you take um any function of the of one ver of one Ed vertex and any function another vertex and and you Sum along your expander graph you will basically the sum will basically factor into into the sum of the mean value of this guy times the me of this guy that there a they're very mixing and the mean value of of this Lambda fun precisely What We Now understand um and so if you had um some good expansion properties of this graph um you could actually um you could actually finish finish the job and and solve the problem um so uh yeah so so we had this sort of plan to attack the cha conjecture but then we got stuck because we had no clue how to put this an expand a graph uh it was uh it was it was was it's very thin and and and and random walks on this graph are not easy to understand uh well they're easy to understand for short times but not for long times and long times of what you need um so anyway we got stuck at this point um but I started looking at this problem again a few weeks ago and um so uh what I what I discovered was that this this sum um so if if you don't know that this is an xan graph it's still potentially possible that this sum is large but um but what you can show without too much trouble is that even if the sum is is is large it's um it's not okay um yeah so so being an expander graph uh yeah so so being an expander I haven't defined exactly what expander means but roughly speaking um being an expand a graph means that a sum like this factors into basically the um a product of the individual sums there some decoupling for all choices of okay that's so roughly speaking what it means to an expander um there's a formal there's a formal version was called expanded mixing limit but okay um if you know what that is um and then if you have that then you can just apply that to to this sort of uh this sort of sum and and and you'll be done now um so we can't I still don't know whether this is true I think something like this is true but I I can't prove it um but what uh what turns out to be um a lot easier to prove um and something okay I realize this while I was waiting in the car for my my son to finish his piano uh lesson I get nothing else to do so I attack this problem um is that um is that what you can prove fairly easily is that um for this funny graph if you pick um so I don't know for whether for all choices of of of of these signs you can get a bound like this but for most choices in fact there's an exponentially small set of exceptions for which um you can get a bound like this that there's a uh you get mixing for most choices of of of uh of of of inputs but not all now this doesn't quite solve the problem because this sequence Lambda could be um could decide to to to the the sign patterns of consecutive strings of Lambda could decide to to to live in the exponentially small set of of exceptions where this the sum fails um so um but um what I could then show um using this fact is that is that if um if uh uh if this sum here was large okay then um the sequence uh the sequence Lambda one and two and so forth uh experiences um okay a sizeable drop significant drop in chanon entropy now I have to tell you what I mean by this okay so um for any given H you pick a medium siiz H like a thousand you can pick up a large random so you pick a medium siiz H okay a large random n and you can look at this sequence this sequence plus or minus 1 and you can look at the sequence in in in the block from n plus1 to n plus h so you take a tiny you take a mediumsized window of the Lal sequence somewhere way out in the natural numbers and that's some sequence of h plus 1 or minus ones so you can think as a random variable a random string of plus ones and minus ones taking values in minus taking values from minus one um basically the in the in the hming cube of of of size H so um that's a random variable uh which takes a discrete number of values two H possible values so it it has a Shannon entropy every time you have a random variable um you can define a Shannon entropy to be a sum of for all um outcomes P Omega log one p Omega P Omega is the the probability that that X is equal to Omega okay so you can talk about this random string and you can compute his [Applause] entropy so um If U so the conjecture is is that the the the Lal function is spread uniformly so that the sign pattern should should be spread uniformly on the Hamming Cube and so the um the entropy here should actually be log of the size of the Hamming Cube okay so basically you use log base 2 for example it should be H okay so um it should take bit H bits of information to um to um um to to express a a random block of of of H numbers in in in the in the Lal sequence um but what you can show yeah so so yeah so in particular if you take the normalized entropy you take entropy of a block of l h divid by H this is somehow the uh the compression rate how much you can compress this this big string of plus and minus ones so um so if there's a lot of structure in a sequence um so this is always some between Z and one it it decreases as H gets bigger this sub additivity um and so it it passes to a limit which is what which is which is called the entropy of of the sequence common of entropy or the sequence common of siai entropy um but uh and it so measures how how structured the sequence is um but using this fact that this sum is is true for all but an exponentially small set of exceptions you can show that if the sum is biger um a lot of the time then there's a drop in entropy what that means is is that if you take a a block of length H and then you you go up to a block of length say 10 H um the entropy in principle could be 10 times as big for block of l 10 H as it is for block of l h but it actually drops a little bit the you can you can you can bound something like the entropy of of of the block of the 10 H by 10 times the block of H minus something minus minus minus a little bit um if the sum is large because the the set of failures okay um because saying that sum is large means that means that Lambda is living in a in a in a very exponentially small set of all possible sign patterns and and you can use that um so every time that I can't prove my theorem um the entropy drops um and the there's a certain upper bound on the entropy and so you can use the pigal principle to say that eventually as I keep expanding my blocks to be bigger and bigger somewhere there is a there is some block where where I do not experience this drop in entropy um and then that makes the sequence sort of uh um mixing in some sense at that that scale and then I can avoid this exponentially small set of of of signs that I don't understand and then that actually proves this theorem um so to my knowledge it's the first time where information Theory the Shannon entropy inequalities were used to prove a the in number Theory uh U so I'm actually quite excited about this technique I'm hoping we can you can prove other things in uh in number Theory as well um and yeah and then of course there the the which which is which is uh uh yeah which was was really nice to to finally get solved um I think that is uh good place to stop thank you [Applause]