A breakthrough result shows the power of “almost”

Terry Tao has done it again. In two beautiful papers with modest titles, he has evidently proved the famous Discrepancy Conjecture (DC) of Paul Erdős. This emerged from discussion of his two earlier posts this month on his blog. They and his 9/18 announcement post re-create much of the content of the papers.

Today we wish to present just the statement of his new result in a vivid manner and some meta-observations on how he arrived at it.

Erdős originally offered a $500 prize for a solution. If we date that offer to an article he wrote in 1957, then it would be about $4,250 in today’s money, still a lot from one person. In 2013 we mused on whether a solution could be applied to win higher prizes. Last year there was an exhaustive proof of a partial case, but it was by computer brute force.

What worked now were the twin insights that DC follows from another conjecture and that proving an “almost” case of that conjecture could be enough to prove DC. We wonder whether finding new “almost” cases of our big conjectures in complexity theory will help win big prizes—or at least “almost” prizes.

Frogs And Lily Pads

A frog named Gorf sits on the shore of a large pond. Before him in the water are a stretch of lily pads. On or above each pad is a beetle or a fly. Gorf is hungry.

Gorf doesn’t worry about reaching the lily pads. He is a powerful jumper—he can jump any number of pads at once. Gorf’s problem is that once he starts jumping he can’t stop: he will keep jumping to every -th pad.

Gorf needs a balanced diet. If he keeps eating more bugs than flies he will get a tummyache; if he eats too many flies, well those wings—you know what happens if you eat too much fiber. He needs there to be a constant so that as he eats and eats, the absolute difference between the numbers of beetles and flies consumed never exceeds .

Finally, Gorf is a worrywort. He is afraid the wrong choice of jumping distance could cause indigestion. So unless the sequence is such that every initial jump will lead to a -balanced diet, he will stay on the shore and starve. Stated as a problem, what Erdős asked was this:

Does there exist an infinite sequence of beetles and flies so that Gorf won’t starve?

Erdős conjectured that there isn’t. Well OK, Erdős didn’t talk about frogs and bugs and flies. But he could have. Anyway he was right. Here is how he thought of it.

By the Numbers

Each lily pad contains a number. Each fly is and each beetle is . Or it could be the opposite; the problem is symmetric. Let be the number on lily pad . Given the sequence , what we care about is whether there is a such that for all and ,

So as the frog jumps to every -th pad and eats he is adding to his running total . The question is: Can he jump from lily pad to lily pad and keep the number bounded—that is, keep it always between and , for some and all ? If he can, then say the sequence is good.

Which sequences are good? Of course the answer depends on the sequence. If the pads are labeled

then clearly he will always get a larger and larger number. Note, this will happen no matter what jump he does.

Next, consider the sequence of lily pads

In this case Gorf can just jump one pad at a time () and keep his count at or . However, if he jumps 2, he only eats beetles. Since Gorf is worried that he would overhop the first lily pad and never be able to stop jumping two-by-two, he won’t budge. So this is still not good for all , which is what Gorf needs.

Almost Good?

Gorf reads a book on the Probabilistic Method. He wonders if he can trust that Nature is random—that the sequence of bugs and flies he encounters will conform to a normal distribution as grows, no matter what he chooses. So he should just take a random initial leap of faith and eat and be merry. But he realizes that the discrepancy—the difference between and zero—will expect to vary as , not constant. This is the wrong way around for the method to imply the existence of a good sequence. Just the thought of this gives Gorf indigestion.

Hope comes from the fact that we can construct sequences that give vastly lower discrepancy than random ones. Given , divide out all factors of 3. The resulting number will either be congruent to 1 mod 3, in which case , or congruent to 2, whereupon . Then with the absolute partial sums stay within . But this is not bounded by a constant, so not good enough for Gorf.

This last sequence is also multiplicative: . Until Tao’s result, no one had even ruled out the existence of a good sequence that is multiplicative. Multiplicative sequences can also be generalized by allowing values on—or at least within—the complex unit circle. For instance, let be on the circle and let be a function giving , such as the number of prime factors of including multiplicity (and ). Then the sequence is multiplicative and stays on the circle. Notions related to discrepancy can be extended to these sequences, perhaps summing just the real parts.

Almost False

There is an easy way to make a sequence for Gorf that any diet doctor would approve: Leave some of the lily pads empty. That is, allow as a sequence value.

In fact, just repeat “beetle-fly-empty” over and over again: (regarding as ). If the initial jump is or or etc., Gorf eats beetle-fly-beetle-fly…, as balanced as can be. If it is or or , Gorf is equally happy: it’s fly-beetle-fly-beetle…

The problem for Gorf is that if is a multiple of 3 then he never eats. The problem for us is that the balancing is trivial. If you try filling in the zeros, you just have DC back again for cases where is a multiple of 3; if you do this balancing recursively, you get the sequence in the last section which doesn’t quite work.

Still, this showed that if the DC is true, it is true because Gorf is being “force-fed” at every pad. Exactly why that detail should matter may still be unclear.

DC is also true in a uniform sense: for every there exists such that for every sequence of length , some jump makes Gorf’s absolute partial sums exceed before reaching lily pad . This follows from a famous lemma of Dénes Kőnig: if every branch of a subtree of the infinite binary tree is finite, then the whole subtree is finite. This does not, however, prevent the existence of an infinite sequence such that for every there exists making for all . Such a sequence is discussed in Remark 1.13 of Tao’s paper and is defined recursively by and for , , and , by

Another delicate point is that if Gorf were allowed to start jumping at any initial pad —say with relatively prime to —then it was known that no sequence can meet the requirement of being good for all and all . That is, any sequence has arithmetical progressions of unbounded discrepancy. Starting at zero—on the shore—is important to the problem.

Tao listed basically the same two mod-3 examples in his first post just before reporting the first bombshell of his breakthrough, which is that DC is implied by another conjecture.

Quanta Magazine src1, Wired src2

Almost True

The other conjecture only needs the idea of a Dirichlet character to state. This is a completely multiplicative function that has some integer period , for which is relatively prime to . The jumping-off point was a conjecture of Sarvadaman Chowla that for the sequence above and all , the magnitude of

is asymptotically . Peter Elliott generalized it to include Dirichlet characters but used an asymptotic condition that was initially too strong. Building on work earlier this year with Kaisa Matomaki and Maksim Radziwill, Tao first repaired Elliott’s conjecture and then made it concrete. We’ll call it TEC for Tao’s Elliott conjecture; we have changed his variable names to try to connect it more to the uniform version of DC above:

Conjecture (TEC). For all there is such that for all there is such that for all , and all multiplicative sequences into the unit complex disk: if all Dirichlet characters of period at most give that the real part of

has absolute value for all with , then for all ,

There are differences in the connection, most notably that the conclusion bounds a sum over all rather than show it to be unbounded. However, what shakes out in the analysis is that keeping bounded this kind of sum of products over all possible -jumps between lily pads (which can have complex life forms not just beetles and flies) enables you to avoid losing a handle on the imbalances from the jumping that Gorf actually does. The two kinds of jumping are set up to be related by a Fourier transform, which characteristically relates constancy in one signal to waviness and periodicity in the other. The connection with products of the form is analyzed by an old trick which Tao once discussed here. There is finally an important use of Andrew Granville’s notion of pretending, which we once briefly covered in connection with EDC here, and which became a focal point in much public PolyMath work credited liberally by Tao.

Well we think this is what happens when one looks at the details—we always say read the papers for the details, though this time we haven’t had time to absorb them ourselves. But we will say one final thing: Tao does not prove TEC. No. What he does instead is come up with a way to say it holds “on average” with respect to a separate quantity such that the sum limits to a range where is unbounded, is put in the denominator of the summand, and the right-hand side’s is replaced by as . It takes a lifetime of experience with the relevant tools of analysis to recognize when to apply this kind of transformation. But its success might stimulate us to think of more creative ways to use averaging arguments and average-case analysis in our field.

Open Problems

There is still much to do and digest after this breakthrough. Is any nice constructive bound on in terms of implied by the analysis? Recall that gave last year. Gil Kalai and Tao have exchanged some further ideas beginning here.

One thing for sure, the problem of Erdős discrepancy is still a problem. Yogi Berra who passed away yesterday said “it ain’t over ’til it’s over,” and it isn’t over.

[fixed EDC statement with before , added example to uniformity statement]