The Erdős discrepancy problem

(Difference between revisions)
 Revision as of 03:25, 24 January 2010 (view source)m (→Introduction and statement of problem: added $500 status and other references)← Older edit Current revision (18:29, 20 July 2010) (view source)m (→General proof strategies) (31 intermediate revisions not shown.) Line 3: Line 3: ==Introduction and statement of problem== ==Introduction and statement of problem== - Is there a $\scriptstyle \pm 1$ sequence $(x_n)$ and constant $C$, such that for all positive integers $d,k$ + Let $(x_n)$ be a $\scriptstyle \pm 1$ sequence and let $C$ be a constant. Must there exist positive integers $d,k$ such that - :$\left| \sum_{i=1}^k x_{id} \right| \leq C$? + :$\left| \sum_{i=1}^k x_{id} \right| > C$? Known colloquially as "The Erdős discrepancy problem", this question has remained unanswered since the 1930s (Erdős, 1957) and Erdős offered$500 for an answer. It was also asked by Chudakov (1956). It is extremely easy to state, and a very appealing problem, so perhaps Polymath can succeed where individual mathematicians have failed. If so, then, given the notoriety of the problem, it would be a significant coup for the multiply collaborative approach to mathematics. But even if a full solution is not reached, preliminary investigations have already thrown up some interesting ideas which could perhaps be developed into publishable results. Known colloquially as "The Erdős discrepancy problem", this question has remained unanswered since the 1930s (Erdős, 1957) and Erdős offered $500 for an answer. It was also asked by Chudakov (1956). It is extremely easy to state, and a very appealing problem, so perhaps Polymath can succeed where individual mathematicians have failed. If so, then, given the notoriety of the problem, it would be a significant coup for the multiply collaborative approach to mathematics. But even if a full solution is not reached, preliminary investigations have already thrown up some interesting ideas which could perhaps be developed into publishable results. - Anticipating a negative answer to Erdős's question, we now quantify the problem. For any finite set $A$ of integers, we define the error on $A$ by + It seems likely that the answer to Erdős's question is yes. If it is, then an easy compactness argument tells us that for every $C$ there exists $n$ such that for every $\scriptstyle \pm 1$ sequence of length $n$ there exist $d,k$ with $dk\leq n$ such that $\left| \sum_{i=1}^k x_{id} \right| > C$. In view of this, we make some definitions that allow one to talk about the dependence between $C$ and $n$. For any finite set $A$ of integers, we define the error on $A$ by :$E(A) := \sum_{a\in A} x_a$, :$E(A) := \sum_{a\in A} x_a$, - and for a set $\mathcal{A}$ of finite sets of integers, we define the discrepancy + and for a set $\mathcal{A}$ of finite sets of integers, we define the discrepancy :$\delta(\mathcal{A},x) := \sup_{A\in \mathcal{A}} |E(A)|.$ :$\delta(\mathcal{A},x) := \sup_{A\in \mathcal{A}} |E(A)|.$ We can think of the values taken by the sequence $(x_n)$ as a red/blue colouring of the integers that tries to make the number of reds and blues in each $\scriptstyle A\in\mathcal{A}$ as equal as possible. The discrepancy measures the extent to which the sequence fails in this attempt. Taking $\scriptstyle \mathcal{HAP}(N)$ to be the set of homogeneous arithmetic progressions $\{d, 2d, 3d, ..., nd\}$ contained in $\{1, 2, ..., N\}$, we can restate the question as whether $\scriptstyle \delta(\mathcal{HAP}(N),x) \to \infty$ for every sequence $x$. We can think of the values taken by the sequence $(x_n)$ as a red/blue colouring of the integers that tries to make the number of reds and blues in each $\scriptstyle A\in\mathcal{A}$ as equal as possible. The discrepancy measures the extent to which the sequence fails in this attempt. Taking $\scriptstyle \mathcal{HAP}(N)$ to be the set of homogeneous arithmetic progressions $\{d, 2d, 3d, ..., nd\}$ contained in $\{1, 2, ..., N\}$, we can restate the question as whether $\scriptstyle \delta(\mathcal{HAP}(N),x) \to \infty$ for every sequence $x$. Line 29: Line 29: The EDP is the Erdős discrepancy problem. (This may conceivably be changed if enough people don't like it.) The EDP is the Erdős discrepancy problem. (This may conceivably be changed if enough people don't like it.) - A sequence $(x_n)$ is completely multiplicative if $x_{mn}=x_mx_n$ for any two positive integers m and n. We shall sometimes abbreviate this to "multiplicative", but the reader should be aware that the word "multiplicative" normally refers to the more general class of sequences such that $x_{mn}=x_mx_n$ whenever m and n are coprime. A completely multiplicative function is determined by the values it takes at primes. The Liouville function λ is the unique completely multiplicative function that takes the value -1 at every prime: if the prime factorization of n is $\prod p_i^{a_i}$ then λ(n) equals $(-1)^{\sum a_i}$. + A sequence $(x_n)$ is completely multiplicative if $x_{mn}=x_mx_n$ for any two positive integers m and n. We shall sometimes abbreviate this to "multiplicative", but the reader should be aware that the word "multiplicative" normally refers to the more general class of sequences such that $x_{mn}=x_mx_n$ whenever m and n are coprime. A completely multiplicative function is determined by the values it takes at primes. The Liouville function λ is the unique completely multiplicative function that takes the value -1 at every prime: if the prime factorization of n is $\prod p_i^{a_i}$ then λ(n) equals $(-1)^{\sum a_i}$. Another important multiplicative function is $\mu_3$, the multiplicative function that’s -1 at 3, 1 at numbers that are 1 mod 3 and -1 at numbers that are 2 mod 3. This function has mean-square partial sums which grow logarithmically, [http://gowers.wordpress.com/2010/01/26/edp3-a-very-brief-report-on-where-we-are/#comment-5585 see this calculation]. A HAP-subsequence of a sequence $(x_n)$ is a subsequence of the form $x_d,x_{2d},x_{3d},...$ for some d. If $(x_n)$ is a multiplicative $\pm 1$ sequence, then every HAP-subsequence is equal to either $(x_n)$ or $(-x_n)$. We shall call a sequence weakly multiplicative if it has only finitely many distinct HAP-subsequences. Let us also call a $\pm 1$ sequence quasi-multiplicative if it is a composition of a completely multiplicative function from $\mathbb{N}$ to an Abelian group G with a function from G to {-1,1} (This definition is too general. See [http://gowers.wordpress.com/2010/01/09/erds-discrepancy-problem-continued/#comment-4843 this and the next comment]). [http://gowers.wordpress.com/2009/12/17/erdoss-discrepancy-problem/#comment-4705 It can be shown] that if $(x_n)$ is a weakly multiplicative sequence, then it has an HAP-subsequence that is quasi-multiplicative. A HAP-subsequence of a sequence $(x_n)$ is a subsequence of the form $x_d,x_{2d},x_{3d},...$ for some d. If $(x_n)$ is a multiplicative $\pm 1$ sequence, then every HAP-subsequence is equal to either $(x_n)$ or $(-x_n)$. We shall call a sequence weakly multiplicative if it has only finitely many distinct HAP-subsequences. Let us also call a $\pm 1$ sequence quasi-multiplicative if it is a composition of a completely multiplicative function from $\mathbb{N}$ to an Abelian group G with a function from G to {-1,1} (This definition is too general. See [http://gowers.wordpress.com/2010/01/09/erds-discrepancy-problem-continued/#comment-4843 this and the next comment]). [http://gowers.wordpress.com/2009/12/17/erdoss-discrepancy-problem/#comment-4705 It can be shown] that if $(x_n)$ is a weakly multiplicative sequence, then it has an HAP-subsequence that is quasi-multiplicative. Line 39: Line 39: *To answer the problem negatively, it is sufficient to find a completely multiplicative sequence (that is, a sequence $(x_n)$ such that $x_{mn}=x_mx_n$ for every m,n) such that its partial sums $x_1+\dots+x_n$ are bounded. First mentioned in the proof of the theorem in [http://gowers.wordpress.com/2009/12/17/erdoss-discrepancy-problem/ this] post. *To answer the problem negatively, it is sufficient to find a completely multiplicative sequence (that is, a sequence $(x_n)$ such that $x_{mn}=x_mx_n$ for every m,n) such that its partial sums $x_1+\dots+x_n$ are bounded. First mentioned in the proof of the theorem in [http://gowers.wordpress.com/2009/12/17/erdoss-discrepancy-problem/ this] post. - *The function that takes n to 1 if the last non-zero digit of n in its ternary representation is 1 and -1 if the last non-zero digit is 2 is completely multiplicative and the partial sum up to n is easily shown to be at most $\log_3n +1$. Therefore, the rate at which the worst discrepancy grows, as a function of the length of the homogeneous progression, can be as slow as logarithmic. [http://gowers.wordpress.com/2009/12/17/erdoss-discrepancy-problem/] [http://gowers.wordpress.com/2009/12/17/erdoss-discrepancy-problem/#comment-4553 It turns out] that the base can be made significantly higher than 3, so this example is not best possible. [http://gowers.wordpress.com/2010/01/06/erdss-discrepancy-problem-as-a-forthcoming-polymath-project/#comment-4757 Correction] + *The function that takes n to 1 if the last non-zero digit of n in its ternary representation is 1 and -1 if the last non-zero digit is 2 is completely multiplicative and the partial sum up to n is easily shown to be at most $\log_3n +1$. Therefore, the rate at which the worst discrepancy grows, as a function of the length of the homogeneous progression, can be as slow as logarithmic. [[Matryoshka_Sequences|More examples of this sort are here.]] [http://gowers.wordpress.com/2009/12/17/erdoss-discrepancy-problem/] [http://gowers.wordpress.com/2009/12/17/erdoss-discrepancy-problem/#comment-4553 It turns out] that the base can be made significantly higher than 3, so this example is not best possible. [http://gowers.wordpress.com/2010/01/06/erdss-discrepancy-problem-as-a-forthcoming-polymath-project/#comment-4757 Correction] *To answer the problem negatively, it is also sufficient to find a completely multiplicative function f from $\mathbb{N}$ to a finite Abelian group G (meaning that f(mn)=f(m)+f(n) for every m,n) and a function h from G to {-1,1} such that for each g in G there exists d with f(d)=g and with the partial sums hf(d)+hf(2d)+...+hf(nd) bounded. In that case, one can set $x_n=hf(n)$. (Though this observation is simple with the benefit of hindsight, it might not have been made had it not been for the fact that this sort of structure was identified in a long sequence that had been produced experimentally). First mentioned [http://gowers.wordpress.com/2009/12/17/erdoss-discrepancy-problem/#comment-4696 here]. Se also [http://gowers.wordpress.com/2010/01/06/erdss-discrepancy-problem-as-a-forthcoming-polymath-project/ this post] and [http://gowers.wordpress.com/2010/01/06/erdss-discrepancy-problem-as-a-forthcoming-polymath-project/#comment-4717 this comment]. *To answer the problem negatively, it is also sufficient to find a completely multiplicative function f from $\mathbb{N}$ to a finite Abelian group G (meaning that f(mn)=f(m)+f(n) for every m,n) and a function h from G to {-1,1} such that for each g in G there exists d with f(d)=g and with the partial sums hf(d)+hf(2d)+...+hf(nd) bounded. In that case, one can set $x_n=hf(n)$. (Though this observation is simple with the benefit of hindsight, it might not have been made had it not been for the fact that this sort of structure was identified in a long sequence that had been produced experimentally). First mentioned [http://gowers.wordpress.com/2009/12/17/erdoss-discrepancy-problem/#comment-4696 here]. Se also [http://gowers.wordpress.com/2010/01/06/erdss-discrepancy-problem-as-a-forthcoming-polymath-project/ this post] and [http://gowers.wordpress.com/2010/01/06/erdss-discrepancy-problem-as-a-forthcoming-polymath-project/#comment-4717 this comment]. Line 47: Line 47: *The problem for the positive integers is equivalent to the problem for the positive rationals. [http://gowers.wordpress.com/2009/12/17/erdoss-discrepancy-problem/#comment-4676](Sketch proof: if you have a function f from the positive integers to {-1,1} that works, then define $f_q(x)$ to be f(q!x) whenever q!x is an integer. Then take a pointwise limit of a subsequence of the functions $f_q$. [[Limits with better properties|Click here for a more detailed discussion of this construction and what it is good for]]. *The problem for the positive integers is equivalent to the problem for the positive rationals. [http://gowers.wordpress.com/2009/12/17/erdoss-discrepancy-problem/#comment-4676](Sketch proof: if you have a function f from the positive integers to {-1,1} that works, then define $f_q(x)$ to be f(q!x) whenever q!x is an integer. Then take a pointwise limit of a subsequence of the functions $f_q$. [[Limits with better properties|Click here for a more detailed discussion of this construction and what it is good for]]. - *Define the [[drift]] of a sequence to be the maximal value of |f(md)+...+f(nd)|. The discrepancy problem is equivalent to showing that the drift is always infinite. It is obvious that it is at least 2 (because |f(2)+f(4)|, |f(2)+f(3)|, |f(3)+f(4)| cannot all be at most 1); it seems hopeful that one can show that [[drift|it is at least 3]]. + *Define the [[drift]] of a sequence to be the maximal value of |f(md)+...+f(nd)|. The discrepancy problem is equivalent to showing that the drift is always infinite. It is obvious that it is at least 2 (because |f(2)+f(4)|, |f(2)+f(3)|, |f(3)+f(4)| cannot all be at most 1); one can show that [[drift|it is at least 3]] (which implies as a corollary that the discrepancy is at least 2). One can also show that the [[upper and lower discrepancy]] are each at least 2. *One can [[topological dynamics formulation|formulate the problem using topological dynamics]]. *One can [[topological dynamics formulation|formulate the problem using topological dynamics]]. + + *Using Fourier analysis, one can [[Fourier reduction|reduce the problem to one about completely multiplicative functions]]. + + *Here is an [[algorithm for finding multiplicative sequences with bounded discrepancy]]. + + *Here is a page whose aim is to record a [[human proof that completely multiplicative sequences have discrepancy at least 2]]. + + *Here is an argument that shows that [[bounded discrepancy multiplicative functions do not correlate with characters]]. + + * The answer to a [[function field version]] of the problem seems to be negative. + + * The problem can be generalized to [[pseudointegers]]. Here we have found [[EDP on pseudointegers|problems similar to EDP]] with a negative answer. ==Experimental evidence== ==Experimental evidence== + + ''Main page: [[Experimental results]]'' A nice feature of the problem is that it lends itself well to investigation on a computer. Although the number of $\pm 1$ sequences grows exponentially, the constraints on these sequences are such that depth-first searches can lead quite quickly to interesting examples. For instance, at the time of writing they have yielded several examples of sequences of length 1124 with discrepancy 2. (This is the current record.) See [[Experimental results|this page]] for more details and further links. A nice feature of the problem is that it lends itself well to investigation on a computer. Although the number of $\pm 1$ sequences grows exponentially, the constraints on these sequences are such that depth-first searches can lead quite quickly to interesting examples. For instance, at the time of writing they have yielded several examples of sequences of length 1124 with discrepancy 2. (This is the current record.) See [[Experimental results|this page]] for more details and further links. Line 61: Line 75: for sufficiently large $N$. Currently, this is the record-holder for slow growing discrepancy. for sufficiently large $N$. Currently, this is the record-holder for slow growing discrepancy. - The Thue-Morse sequence has discrepancy $\delta(N) \gg \sqrt{N}$. (See the discussion following [http://gowers.wordpress.com/2010/01/06/erdss-discrepancy-problem-as-a-forthcoming-polymath-project/#comment-4775 this comment] and the next one.) + The [[Thue-Morse-Hedlund Sequence|Thue-Morse sequence]] has discrepancy $\delta(N) \gg N^{\log_4(3)}$. A random sequence (each $x_i$ chosen independently) has discrepancy at least (asymptotically) $\sqrt{2N \log\log N}$ by the law of the iterated logarithm. A random sequence (each $x_i$ chosen independently) has discrepancy at least (asymptotically) $\sqrt{2N \log\log N}$ by the law of the iterated logarithm. Line 96: Line 110: [[Prove the result for shifted HAPs instead of HAPs]] [[Prove the result for shifted HAPs instead of HAPs]] + + [[Find a good configuration of HAPs]] + + [[Generalize to a graph-theoretic formulation]] + + [[Representation of the diagonal]] + + [[Bounding the discrepancy in terms of the common difference]] ==Annotated Bibliography== ==Annotated Bibliography== Line 107: Line 129: **[http://gowers.wordpress.com/2010/01/16/the-erds-discrepancy-problem-v/ Fifth Post] (Jan 16-19). **[http://gowers.wordpress.com/2010/01/16/the-erds-discrepancy-problem-v/ Fifth Post] (Jan 16-19). **[http://gowers.wordpress.com/2010/01/19/edp1-the-official-start-of-polymath5/ First Theoretical Post] (Jan 19-21) **[http://gowers.wordpress.com/2010/01/19/edp1-the-official-start-of-polymath5/ First Theoretical Post] (Jan 19-21) - **[http://gowers.wordpress.com/2010/01/21/edp2-a-few-lessons-from-edp1/ Second Theoretical Post] (Jan 21-?) + **[http://gowers.wordpress.com/2010/01/21/edp2-a-few-lessons-from-edp1/ Second Theoretical Post] (Jan 21-26) + **[http://gowers.wordpress.com/2010/01/26/edp3-a-very-brief-report-on-where-we-are/ Third Theoretical Post] (Jan 26 -?) + **[http://gowers.wordpress.com/2010/01/30/edp4-focusing-on-multiplicative-functions/ Fourth Theoretical Post] (Jan 30- Feb 2) + **[http://gowers.wordpress.com/2010/02/02/edp5-another-very-brief-summary/ Fifth Theoretical Post] (Feb 2 - Feb 5) + **[http://gowers.wordpress.com/2010/02/05/edp6-what-are-the-chances-of-success/ Sixth Theoretical Post] (Feb 5- Feb 8) + **[http://gowers.wordpress.com/2010/02/08/edp7-emergency-post/ Seventh Theoretical Post] (Feb 8 - 19) + **[http://gowers.wordpress.com/2010/02/19/edp8-what-next/ Eighth Theoretical Post] (Feb 19-Feb 24) + **[http://gowers.wordpress.com/2010/02/24/edp9-a-change-of-focus/ Ninth Theoretical Most] (Feb 24-Mar 2) + **[http://gowers.wordpress.com/2010/03/02/edp10-a-new-and-very-promising-approach/ Tenth Theoretical Post] (Mar 2-Mar 7) + **[http://gowers.wordpress.com/2010/03/07/edp11-the-search-continues/ Eleventh Theoretical Post] (Mar 7-Mar 12) + **[http://gowers.wordpress.com/2010/03/13/edp12-representing-diagonal-maps/ Twelfth Theoretical Post] (Mar 13-Mar 22) + **[http://gowers.wordpress.com/2010/03/23/edp13-quick-summary/ Thirteenth Theoretical Post] (Mar 23-Apr 24) + **[http://gowers.wordpress.com/2010/04/25/edp14-strategic-questions/ Fourteenth Theoretical Post] (Apr 25-?) + + *[http://mathoverflow.net/questions/tagged/polymath5 Several questions on MathOverflow have been given the `polymath5' tag.] *Mathias, A. R. D. [http://www.dpmms.cam.ac.uk/~ardm/erdoschu.pdf On a conjecture of Erdős and Čudakov]. Combinatorics, geometry and probability (Cambridge, 1993). *Mathias, A. R. D. [http://www.dpmms.cam.ac.uk/~ardm/erdoschu.pdf On a conjecture of Erdős and Čudakov]. Combinatorics, geometry and probability (Cambridge, 1993). - This is a short paper establishing the maximal length of sequence for the case where C=1 is 11, and is the starting point for our experimental studies. + This one page paper establishes that the maximal length of sequence for the case where C=1 is 11, and is the starting point for our experimental studies. + + *Tchudakoff, N. G. Theory of the characters of number semigroups. J. Indian Math. Soc. (N.S.) 20 (1956), 11--15. MR0083515 (18,719e) + + The Mathias paper states that one of Erdős's problem lists states that this paper "studies related questions". The Math Review for this paper states that it summarizes results from seven other papers that are in Russian. The Math Review leaves the impression that the topic concerns characters of modulus 1. *Borwein, Peter, and Choi, Stephen. [http://www.cecm.sfu.ca/personal/pborwein/PAPERS/P204.pdf A variant of Liouville's lambda function: some surprizing formulae]. *Borwein, Peter, and Choi, Stephen. [http://www.cecm.sfu.ca/personal/pborwein/PAPERS/P204.pdf A variant of Liouville's lambda function: some surprizing formulae]. Line 123: Line 163: In this [http://gowers.wordpress.com/2010/01/06/erdss-discrepancy-problem-as-a-forthcoming-polymath-project/#comment-4729 blog post] Terry Tao wrote: "Granville and Soundararajan have made some study of the discrepancy of bounded multiplicative functions. The situation is remarkably delicate and number-theoretical (and is closely tied with the Granville-Soundararajan theory of pretentious characters)." In this [http://gowers.wordpress.com/2010/01/06/erdss-discrepancy-problem-as-a-forthcoming-polymath-project/#comment-4729 blog post] Terry Tao wrote: "Granville and Soundararajan have made some study of the discrepancy of bounded multiplicative functions. The situation is remarkably delicate and number-theoretical (and is closely tied with the Granville-Soundararajan theory of pretentious characters)." + *Wirsing, E. Das asymptotische Verhalten von Summen über multiplikative Funktionen. II. (German) [The asymptotic behavior of sums of multiplicative functions. II.] Acta Math. Acad. Sci. Hungar. 18 1967 411--467. MR0223318 (36 #6366) [http://michaelnielsen.org/polymath1/index.php?title=Wirsing_translation (partial) English translation] + + *Newman, D. J. [http://www.jstor.org/stable/2036455 On the number of binary digits in a multiple of three]. Proc Amer Math Soc. 21(1969): 719--721. + Proves that the Thue-Morse sequence has discrepancy $\gg N^{\log_4(3)}$ + + *Halász, G. [http://gowers.wordpress.com/2010/02/02/edp5-another-very-brief-summary/#comment-5806 On random multiplicative functions]. Hubert Delange colloquium (Orsay, 1982), 74–96, Publ. Math. Orsay, 83-4, Univ. Paris XI, Orsay, 1983. + + The discrepancy of a random multiplicative function is close to$\sqrt{N}$. === Problem lists on which this problem appears === === Problem lists on which this problem appears === Line 130: Line 178: Our problem is mentioned at the bottom of page 331, where they indicate knowledge of a coloring with logarithmic discrepancy. On pages 330-1, they review work on the non-homogeneous problem. Our problem is mentioned at the bottom of page 331, where they indicate knowledge of a coloring with logarithmic discrepancy. On pages 330-1, they review work on the non-homogeneous problem. - *As [http://www.math.niu.edu/~rusin/known-math/93_back/prizes.erd this web page] reveals, the Erdős discrepancy problem was a$500-dollar problem of Erdős, so it is clear that he regarded it as pretty hard. + *Erdős, Paul, Some of my favourite unsolved problems. A tribute to Paul Erdős, 467--478, Cambridge Univ. Press, Cambridge, 1990. MR1117038 (92f:11003) + + "Let $f(n)=\pm1. Is it true that for every [itex]c there is a [itex]d and an [itex]m so that + :[itex] \left| \sum_{k=1}^m f(kd) \right| > c? + I will pay 500 for an answer. Let [itex]f(n)=\pm1$ and $f(ab)=f(a)f(b)$. Is it then true that $\left| \sum_{k=1}^m f(kd) \right|$ cannot be bounded?" *P. Erdős. [http://www.renyi.hu/~p_erdos/1957-13.pdf Some unsolved problems], Michigan Math. J. 4 (1957), 291--300 MR20 #5157; Zentralblatt 81,1. *P. Erdős. [http://www.renyi.hu/~p_erdos/1957-13.pdf Some unsolved problems], Michigan Math. J. 4 (1957), 291--300 MR20 #5157; Zentralblatt 81,1. Line 159: Line 211: by proving $disc(H) = \Theta�(N^{d/4})$ for every fixed positive integer d. This extends the famous by proving $disc(H) = \Theta�(N^{d/4})$ for every fixed positive integer d. This extends the famous lower bound of $\Omega(N^{1/4})$ of Roth (1964) and the matching upper bound $O(N^{1/4})$ lower bound of $\Omega(N^{1/4})$ of Roth (1964) and the matching upper bound $O(N^{1/4})$ - of Matouˇsek and Spencer (1996) from d = 1 to arbitrary, fixed d. To establish + of Matoušek and Spencer (1996) from d = 1 to arbitrary, fixed d. To establish the lower bound we use harmonic analysis on locally compact abelian groups. For the lower bound we use harmonic analysis on locally compact abelian groups. For - the upper bound a product coloring arising from the theorem of Matouˇsek and + the upper bound a product coloring arising from the theorem of Matoušek and Spencer is sufficient. We also regard some special cases, e.g., symmetric arithmetic Spencer is sufficient. We also regard some special cases, e.g., symmetric arithmetic progressions and infinite arithmetic progressions. progressions and infinite arithmetic progressions.

Current revision

If you want to you can jump straight to the main experimental results page.

Introduction and statement of problem

Let (xn) be a $\scriptstyle \pm 1$ sequence and let C be a constant. Must there exist positive integers d,k such that

$\left| \sum_{i=1}^k x_{id} \right| > C$?

Known colloquially as "The Erdős discrepancy problem", this question has remained unanswered since the 1930s (Erdős, 1957) and Erdős offered $500 for an answer. It was also asked by Chudakov (1956). It is extremely easy to state, and a very appealing problem, so perhaps Polymath can succeed where individual mathematicians have failed. If so, then, given the notoriety of the problem, it would be a significant coup for the multiply collaborative approach to mathematics. But even if a full solution is not reached, preliminary investigations have already thrown up some interesting ideas which could perhaps be developed into publishable results. It seems likely that the answer to Erdős's question is yes. If it is, then an easy compactness argument tells us that for every C there exists n such that for every $\scriptstyle \pm 1$ sequence of length n there exist d,k with $dk\leq n$ such that $\left| \sum_{i=1}^k x_{id} \right| > C$. In view of this, we make some definitions that allow one to talk about the dependence between C and n. For any finite set A of integers, we define the error on A by $E(A) := \sum_{a\in A} x_a$, and for a set $\mathcal{A}$ of finite sets of integers, we define the discrepancy $\delta(\mathcal{A},x) := \sup_{A\in \mathcal{A}} |E(A)|.$ We can think of the values taken by the sequence (xn) as a red/blue colouring of the integers that tries to make the number of reds and blues in each $\scriptstyle A\in\mathcal{A}$ as equal as possible. The discrepancy measures the extent to which the sequence fails in this attempt. Taking $\scriptstyle \mathcal{HAP}(N)$ to be the set of homogeneous arithmetic progressions {d,2d,3d,...,nd} contained in {1,2,...,N}, we can restate the question as whether $\scriptstyle \delta(\mathcal{HAP}(N),x) \to \infty$ for every sequence x. Two related questions have already been solved in the literature. Letting $\scriptstyle \mathcal{AP}(N)$ be the collection of all (not necessarily homogeneous) arithmetic progressions in {1,2,...,N}, Roth (1964) proved that $\scriptstyle \delta(\mathcal{AP}(N),x) \geq c n^{1/4}$, independent of the sequence x. Letting $\scriptstyle \mathcal{HQAP}(N)$ be the collection of all homogeneous quasi-arithmetic progressions $\scriptstyle\{\lfloor \alpha \rfloor,\lfloor 2\alpha \rfloor,\dots,\lfloor k\alpha \rfloor\}$ contained in {1,2,...,N}, Vijay (2008) proved that $\scriptstyle \delta(\mathcal{HQAP}(N),x) \geq 0.02 n^{1/6}$, independent of the sequence x. Some definitions and notational conventions A homogeneous arithmetic progression, or HAP, is an arithmetic progression of the form {d,2d,3d,...,nd}. When x is clear from context, we write δ(N) in place of $\delta(\mathcal{HAP}(N),x)$. The discrepancy of a sequence (xn) is the supremum of $|\sum_{n\in P}x_n|$ over all homogeneous arithmetic progressions P. (Strictly speaking, we should call this something like the HAP-discrepancy, but since we will almost always be talking about HAPs, we adopt the convention that "discrepancy" always means "HAP-discrepancy" unless it is stated otherwise.) Insertformulahere A sequence (xn) has discrepancy at most φ(n) if for every natural number N the maximum value of $|\sum_{n\in P}x_n|$ over all homogeneous arithmetic progressions P that are subsets of {1,2,...,N} is at most φ(N). The EDP is the Erdős discrepancy problem. (This may conceivably be changed if enough people don't like it.) A sequence (xn) is completely multiplicative if xmn = xmxn for any two positive integers m and n. We shall sometimes abbreviate this to "multiplicative", but the reader should be aware that the word "multiplicative" normally refers to the more general class of sequences such that xmn = xmxn whenever m and n are coprime. A completely multiplicative function is determined by the values it takes at primes. The Liouville function λ is the unique completely multiplicative function that takes the value -1 at every prime: if the prime factorization of n is $\prod p_i^{a_i}$ then λ(n) equals $(-1)^{\sum a_i}$. Another important multiplicative function is μ3, the multiplicative function that’s -1 at 3, 1 at numbers that are 1 mod 3 and -1 at numbers that are 2 mod 3. This function has mean-square partial sums which grow logarithmically, see this calculation. A HAP-subsequence of a sequence (xn) is a subsequence of the form xd,x2d,x3d,... for some d. If (xn) is a multiplicative $\pm 1$ sequence, then every HAP-subsequence is equal to either (xn) or ( − xn). We shall call a sequence weakly multiplicative if it has only finitely many distinct HAP-subsequences. Let us also call a $\pm 1$ sequence quasi-multiplicative if it is a composition of a completely multiplicative function from $\mathbb{N}$ to an Abelian group G with a function from G to {-1,1} (This definition is too general. See this and the next comment). It can be shown that if (xn) is a weakly multiplicative sequence, then it has an HAP-subsequence that is quasi-multiplicative. It is convenient to define the maps Tk for $k \geq 1$ by Tk(x)n = xkn, where x = (x1,x2,...) is a sequence. Simple observations • To answer the problem negatively, it is sufficient to find a completely multiplicative sequence (that is, a sequence (xn) such that xmn = xmxn for every m,n) such that its partial sums $x_1+\dots+x_n$ are bounded. First mentioned in the proof of the theorem in this post. • The function that takes n to 1 if the last non-zero digit of n in its ternary representation is 1 and -1 if the last non-zero digit is 2 is completely multiplicative and the partial sum up to n is easily shown to be at most log3n + 1. Therefore, the rate at which the worst discrepancy grows, as a function of the length of the homogeneous progression, can be as slow as logarithmic. More examples of this sort are here. [1] It turns out that the base can be made significantly higher than 3, so this example is not best possible. Correction • To answer the problem negatively, it is also sufficient to find a completely multiplicative function f from $\mathbb{N}$ to a finite Abelian group G (meaning that f(mn)=f(m)+f(n) for every m,n) and a function h from G to {-1,1} such that for each g in G there exists d with f(d)=g and with the partial sums hf(d)+hf(2d)+...+hf(nd) bounded. In that case, one can set xn = hf(n). (Though this observation is simple with the benefit of hindsight, it might not have been made had it not been for the fact that this sort of structure was identified in a long sequence that had been produced experimentally). First mentioned here. Se also this post and this comment. • It can be shown that if a $\pm 1$ sequence (xn) starts with 1 and has only finitely many distinct subsequences of the form $(x_d,x_{2d},x_{3d},\dots)$, then it must have a subsequence that arises in the above way. (This was mentioned just above in the terminology section.) • Define the drift of a sequence to be the maximal value of |f(md)+...+f(nd)|. The discrepancy problem is equivalent to showing that the drift is always infinite. It is obvious that it is at least 2 (because |f(2)+f(4)|, |f(2)+f(3)|, |f(3)+f(4)| cannot all be at most 1); one can show that it is at least 3 (which implies as a corollary that the discrepancy is at least 2). One can also show that the upper and lower discrepancy are each at least 2. Experimental evidence Main page: Experimental results A nice feature of the problem is that it lends itself well to investigation on a computer. Although the number of $\pm 1$ sequences grows exponentially, the constraints on these sequences are such that depth-first searches can lead quite quickly to interesting examples. For instance, at the time of writing they have yielded several examples of sequences of length 1124 with discrepancy 2. (This is the current record.) See this page for more details and further links. Another sort of evidence is to bound the discrepancy for specific sequences. For example, setting x1 = − x2 = 1 and xn = − xn / 3 or xn = xn − 3 according to whether n is a multiple of 3 or not, yields a sequence with $\delta(N) \leq \log_9(N)+1$ for sufficiently large N. Currently, this is the record-holder for slow growing discrepancy. The Thue-Morse sequence has discrepancy $\delta(N) \gg N^{\log_4(3)}$. A random sequence (each xi chosen independently) has discrepancy at least (asymptotically) $\sqrt{2N \log\log N}$ by the law of the iterated logarithm. Determining if the discrepancy of Liouville's lambda function is O(n1 / 2 + ε) is equivalent to solving the Riemann hypothesis. However, this growth cannot be bounded above by n1 / 2 − ε for any positive ε. Interesting subquestions Given the length of time that the Erdős discrepancy problem has been open, the chances that it will be solved by Polymath5 are necessarily small. However, there are a number of interesting questions that we do not know the answers to, several of which have arisen naturally from the experimental evidence. Good answers to some of these would certainly constitute publishable results. Here is a partial list -- further additions are very welcome. (When the more theoretical part of the project starts, this section will probably grow substantially and become a separate page.) • Is there an infinite sequence of discrepancy 2? (Given how long a finite sequence can be, it seems unlikely that we could answer this question just by a clever search of all possibilities on a computer.) • The long sequences of low discrepancy discovered by computer all have some kind of approximate weak multiplicativity. If we take a hypothetical counterexample (xn) (which we could even assume has discrepancy 2), can we prove that it, or some other counterexample derived from it by passing to HAP-subsequences and taking pointwise limits, has some kind of interesting multiplicative structure? • Closely related to the previous question. If (xn) is a hypothetical counterexample, must it satisfy a compactness property of the following kind: for every positive c there exists M such that if you take any M HAP-subsequences, then there must be two of them, (yn) and (zn), such that $\lim\inf N^{-1}\sum_{n=1}^Ny_nz_n\geq 1-c$? • An even weaker question. If (xn) is a hypothetical counterexample, must it have two HAP-subsequences (yn) and (zn) such that the lim inf of $N^{-1}\sum_{n=1}^N y_nz_n$ is greater than 0? • A similar question, perhaps equivalent to the previous one (this should be fairly easy to check). Given a sequence (xn) define f(N) to be the average of xaxbxcxd over all quadruples (a,b,c,d) such that ab=cd and $a,b,c,d\leq N$. If (xn) is a counterexample, does that imply that $\lim\inf f(N)$ is greater than 0? See here for a computation of this average for the first 1124 sequence. • Is there any completely multiplicative counterexample? (This may turn out to be a very hard question. If so, then answering the previous questions could turn out to be the best we can hope for without making a substantial breakthrough in analytic number theory.) • Does there exist a $\pm 1$ sequence such that the corresponding discrepancy function grows at a rate that is slower than clogn for any positive c? • Does the number of sequences of length n and discrepancy at most C grow exponentially with n or more slowly than exponentially? (Obviously if the conjecture is true then it must be zero for large enough n, but the hope is that this question is a more realistic initial target.) General proof strategies This section contains links to other pages in which potential approaches to solving the problem are described. Annotated Bibliography This one page paper establishes that the maximal length of sequence for the case where C=1 is 11, and is the starting point for our experimental studies. • Tchudakoff, N. G. Theory of the characters of number semigroups. J. Indian Math. Soc. (N.S.) 20 (1956), 11--15. MR0083515 (18,719e) The Mathias paper states that one of Erdős's problem lists states that this paper "studies related questions". The Math Review for this paper states that it summarizes results from seven other papers that are in Russian. The Math Review leaves the impression that the topic concerns characters of modulus 1. Explicit formulas for the discrepancy of some completely multiplicative functions whose discrepancy is logarithmic. A typical example is: Let $\lambda_3(n) = (-1)^{\omega_3(n)}$ where ω3(n) is the number of distinct prime factors congruent to − 1mod 3 in n (with multiple factors counted multiply). Then the discrepancy of the λ3 sequence up to N is exactly the number of 1's in the base three expansion of N. (This turns out not to be so surprising after all, since λ3(n) is precisely the same as the ternary function defined in the second item of the Simple Observations section.) In this blog post Terry Tao wrote: "Granville and Soundararajan have made some study of the discrepancy of bounded multiplicative functions. The situation is remarkably delicate and number-theoretical (and is closely tied with the Granville-Soundararajan theory of pretentious characters)." • Wirsing, E. Das asymptotische Verhalten von Summen über multiplikative Funktionen. II. (German) [The asymptotic behavior of sums of multiplicative functions. II.] Acta Math. Acad. Sci. Hungar. 18 1967 411--467. MR0223318 (36 #6366) (partial) English translation Proves that the Thue-Morse sequence has discrepancy $\gg N^{\log_4(3)}$ The discrepancy of a random multiplicative function is close to$\sqrt{N}$. Problem lists on which this problem appears Our problem is mentioned at the bottom of page 331, where they indicate knowledge of a coloring with logarithmic discrepancy. On pages 330-1, they review work on the non-homogeneous problem. • Erdős, Paul, Some of my favourite unsolved problems. A tribute to Paul Erdős, 467--478, Cambridge Univ. Press, Cambridge, 1990. MR1117038 (92f:11003) "Let $f(n)=\pm1$. Is it true that for every c there is a d and an m so that $\left| \sum_{k=1}^m f(kd) \right| > c$? I will pay$500 for an answer. Let $f(n)=\pm1$ and f(ab) = f(a)f(b). Is it then true that $\left| \sum_{k=1}^m f(kd) \right|$ cannot be bounded?"

Problem 9 of this paper is ours. Erdős dates the problem to around 1932, and notes what we know about Liouville's function (lower and upper bound).

Summarizes knowledge of discrepancy of two colorings when the discrepancy is restricted to homogeneous progressions, nonhomogeneous progressions, and homogeneous quasi-progressions. Contains bibliography with 17 entries, including most of those above.

non-homogeneous AP, quasi-AP, and other related discrepancy papers

Roth's method for the n1 / 4 lower bound on nonhomogeneous AP discrepancy is adapted to give a lower bound for homogeneous quasi-AP discrepancy. This result is weaker than the Vijay result, but uses a different method.

A quasi-progression is a sequence of the form $\lfloor k \alpha \rfloor$, with $1\leq k \leq K$ for some K. The main theorem of interest is: If the integers from 0 to n are 2-coloured, there exists a quasi-progression that has discrepancy at least (1 / 50)n1 / 6.

Abstract: We determine the combinatorial discrepancy of the hypergraph H of cartesian products of d arithmetic progressions in the [N]d –lattice. The study of such higher dimensional arithmetic progressions is motivated by a multi-dimensional version of van derWaerden’s theorem, namely the Gallai-theorem (1933). We solve the discrepancy problem for d–dimensional arithmetic progressions by proving disc(H) = Θ(Nd / 4) for every fixed positive integer d. This extends the famous lower bound of Ω(N1 / 4) of Roth (1964) and the matching upper bound O(N1 / 4) of Matoušek and Spencer (1996) from d = 1 to arbitrary, fixed d. To establish the lower bound we use harmonic analysis on locally compact abelian groups. For the upper bound a product coloring arising from the theorem of Matoušek and Spencer is sufficient. We also regard some special cases, e.g., symmetric arithmetic progressions and infinite arithmetic progressions.

• Valkó, Benedek. [Discrepancy of arithmetic progressions in higher dimensions]. (English summary)

J. Number Theory 92 (2002), no. 1, 117--130. MR1880588 (2003b:11071)

Abstract: K. F. Roth (1964, Acta. Arith.9, 257–260) proved that the discrepancy of arithmetic progressions contained in [N] is at least cN1 / 4, and later it was proved that this result is sharp. We consider the d-dimensional version of this problem. We give a lower estimate for the discrepancy of arithmetic progressions on [N]d and prove that this result is nearly sharp. We use our results to give an upper estimate for the discrepancy of lines on an N×N lattice, and we also give an estimate for the discrepancy of a related random hypergraph.

• Roth, K. F., Remark concerning integer sequences. Acta Arith. 9 1964 257--260. MR0168545 (29 #5806)

Shows that the discrepancy on APs is at least cN1 / 4.