## The Problem

In 1932, Erdős conjectured:

**Erdős Discrepancy Conjecture (EDC) **[Problem 9 here] For any constant , there is an such that the following holds. For any function , there exists an and a such that

For any , the set is an arithmetic progression containing ; we call such a set, a *Homogenous Arithmetic Progression* (HAP). The conjecture above says that for any red blue coloring of the* [n] (={1,2,…,n})*, there is some HAP which has a lot more of red than blue (or vice versa). Given C*,* we let *n(C)* to be the minimum value of *n* for which the assertion of EDC holds, and given *n* we write *D(n)* as the minimum value of *C* for which* n(C) ≤ n.*

EDC was a well-known conjecture and it was the subject of the fifth polymath project (making it even more well-known,) that took place in the first half of 2010. (With a few additional threads in August-September 2012.) That *D(n) > 3* for* n > 1160* (and that *D(1160)=3* ) was proved in a 2014 paper by Boris Konev and Alexei Lisitsa.

## The solution

The two defining moments in the life of a mathematical problem is the time it is born and the time it is solved. As you must have heard by now the Erdős discrepancy conjecture has recently (mid September, 2015) been proved by Terry Tao. I was very happy with the news, congratulations Terry!!

## Reading material

**(Video:)** Terence Tao, The Erdős Discrepancy Problem, UCLA Math Colloquium, video by IPAM, Oct 8, 2015. (Thanks to Igor Pak)

**(Papers:)** The proof of the conjecture was done in two recent papers. The first The logarithmically averaged Chowla and Elliott conjectures for two-point correlations, proves a necessary analytic number theory result related to a classical conjecture of Chowla. The second paper – The Erdős discrepancy problem, shows the derivation of EDC from the number theory result. The number theoretic paper is based on a new recent breakthrough technique in analytic number theory initiated by Matomaki and Radziwill and further studied by Matomaki, Radzwill, and Tao. I also recommend a very interesting paper Erdős and arithmetic progressions from about a year ago by Gowers: where Tim tells side-by-side the story of Erdős-Turàn problem (leading to Roth-Szemeredi’s theorem), and that of EDP.

**(Blog posts:)** The proof is described in this blog post by Tao. A similar (somewhat simpler) argument proving EDC based on a number-theoretic conjecture (The Eliott Conjecture) can be found in this very readable blog post by Tao. In 2010 Tim Gowers ran a polymath project devoted to the Erdős discrepancy problem (EDP). A concluding post following Tao’s proof on Gowers’s blog is EDP28. You can also read about the problem and its solution on Lipton and Regan’s blog and in various other places.

**(Popular scientific writings:) **Quanta magazine (Erica Klarreich) : Nature (Chris Cesare), and various other places.

## Erdős’s 1957 Problem paper** **

Erdős’s 1957 paper on open problems in number theory, geometry, and analysis is especially interesting. (It is linked above but the link here might be more stable.) It has 15 problems in number theory, 5 problems in Geometry, and 9 problems in analysis. Some of the problems are famous, and quite a few of them were settled, but some were new to me. It would be nice to go over them and see what their status is.

We will come back to Erdős’s 57 paper at the end.

## Our celebration

To celebrate to solution here are a few things I would like to tell you (including something about the **Erdős-Szusz discrepancy problem** and its solution), as well as more things and problems related to EDP that I am curious about (the red items):

**The proof;****Other proofs? Other applications of the methods?****The value:**What is the behavior of*D(n)?*a) Does the proof give ? What will it take to get ? b) Find a multiplicative sequence of of length*n*of +1 and -1 with discrepancy . (Even better, find an infinite sequence with this property for every n.)**Sequences with diminishing correlation to Dirichlet characters.**Find a sequence orthogonal to all characters with small discrepancy. Prove a stronger version of the conjecture for such sequences.**The hereditary discrepancy of HAP’s****Variants:**Random subsets; square free integers;**Pseudointegers**Can we understand softly and under greater generality why EDC is true?**Pseudo HAP**: A toy problem proposed by several people in polymath5 is to replace the kth HAP by a random set of integers of density 1/k. The EDC and even the $\latex {\sqrt {\log n}$ prediction should still work.**Restricted gaps**a) prime powers gaps, b) powers of two and primes gaps; c) small gaps**Modular versions****What is the strongest version of a statement saying:**Functions with values 0, 1, -1 with diminishing correlations to Dirichlet characters have large discrepancy.**Erdős-Szüsz discrepancy problem**and the question about basis. (This I heard from Gadi Kozma).-
**What is the RH-strength analog of Chowla’s conjecture?**

## The proof

A few words about the proof. Continue reading