You're reading: News, Phil. Trans. Aperiodic.

Terence Tao has solved the Erdős discrepancy problem!

Terence Tao has just uploaded a preprint to the arXiv with a claimed proof of the Erdős discrepancy problem.


Here’s his abstract to the paper, which is titled “The Erdős discrepancy problem”.

We show that for any sequence $f: {\bf N} \to \{-1,+1\}$ taking values in $\{-1,+1\}$, the discrepancy $$ \sup_{n,d \in {\bf N}} \left|\sum_{j=1}^n f(jd)\right| $$ of $f$ is infinite. This answers a question of Erdős. In fact the argument also applies to sequences $f$ taking values in the unit sphere of a real or complex Hilbert space.

The argument uses three ingredients. The first is a Fourier-analytic reduction, obtained as part of the Polymath5 project on this problem, which reduces the problem to the case when $f$ is replaced by a (stochastic) completely multiplicative function ${\bf g}$. The second is a logarithmically averaged version of the Elliott conjecture, established recently by the author, which effectively reduces to the case when ${\bf g}$ usually pretends to be a modulated Dirichlet character. The final ingredient is (an extension of) a further argument obtained by the Polymath5 project which shows unbounded discrepancy in this case.

As Terence mentioned in the abstract, his proof builds on the work of the collaborative Polymath5 project, which took place on Timothy Gowers’s blog.

We last talked about this problem in February 2014, when Boris Konev and Alexei Lisitsa made the news with an attack through the SAT problem (that post contains a good video by James Grime explaining the problem, by the way). Tao refers to this work in an example, which seems to have guided his thinking about the proof.

The comments field on Tao’s arXiv submission mentions that he’s submitted it to the newly-created arXiv overlay journal Discrete Analysis, which was only announced last week. What a coup for open access mathematics!

More information

The Erdős discrepancy problem by Terence Tao, on the arXiv

The Erdos discrepancy problem via the Elliott conjecture on Tao’s blog a week ago, which seems to have been the big breakthrough.

Explanation and notes on the Erdős discrepancy problem, on the Polymath wiki.

3 Responses to “Terence Tao has solved the Erdős discrepancy problem!”

(will not be published)

$\LaTeX$: You can use LaTeX in your comments. e.g. $ e^{\pi i} $ for inline maths; \[ e^{\pi i} \] for display-mode (on its own line) maths.

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>