The Erdős discrepancy problem

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

Introduction and statement of problem

Is there a [math]\displaystyle{ \pm 1 }[/math] sequence [math]\displaystyle{ (x_n) }[/math] and constant [math]\displaystyle{ C }[/math], such that for all positive integers [math]\displaystyle{ d,k }[/math]

[math]\displaystyle{ \left| \sum_{i=1}^k x_{id} \right| \leq C }[/math]?

Known colloquially as "The Erdős discrepancy problem", this question has remained unanswered since the 1930s [citation needed]. It was also asked by Chudakov [again a citation needed]. 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 [math]\displaystyle{ A }[/math] of integers, we define the error [math]\displaystyle{ A }[/math] by

[math]\displaystyle{ E(A) := \sum_{a\in A} x_a }[/math],

and for a set [math]\displaystyle{ \mathcal{A} }[/math] of finite sets of integers, we define the discrepancy

[math]\displaystyle{ \delta(\mathcal{A},x) := \sup_{A\in \mathcal{A}} |E(A)|. }[/math]

Taking [math]\displaystyle{ \mathcal{HAP}(N) }[/math] to be the set of homogeneous arithmetic progressions [math]\displaystyle{ \{d,2d,3d,\dots,nd\} }[/math] contained in [math]\displaystyle{ \{1,2,\dots,N\} }[/math], we can restate the question as whether [math]\displaystyle{ \delta(\mathcal{HAP}(N),x) \to \infty }[/math] for every sequence [math]\displaystyle{ x }[/math].

Two related questions have already been solved in the literature. Letting [math]\displaystyle{ \mathcal{AP}(N) }[/math] be the collection of all (not necessarily homogeneous) arithmetic progressions in [math]\displaystyle{ \{1,2,\dots,N\} }[/math], Roth [citation needed] proved that [math]\displaystyle{ \delta(\mathcal{AP}(N),x) \geq c n^{1/4} }[/math], independent of the sequence [math]\displaystyle{ x }[/math]. Letting [math]\displaystyle{ \mathcal{HQAP}(N) }[/math] be the collection of all homogeneous quasi-arithmetic progressions [math]\displaystyle{ \{\lfloor \alpha \rfloor,\lfloor 2\alpha \rfloor,\dots,\lfloor k\alpha \rfloor\} }[/math] contained in [math]\displaystyle{ \{1,2,\dots,N\} }[/math], Vijay [citation needed] proved that [math]\displaystyle{ \delta(\mathcal{HQAP}(N),x) \geq 0.02 n^{1/6} }[/math], independent of the sequence [math]\displaystyle{ x }[/math].

Some definitions and notational conventions

A homogeneous arithmetic progression, or HAP, is an arithmetic progression of the form {d,2d,3d,...,nd}.

When [math]\displaystyle{ x }[/math] is clear from context, we write [math]\displaystyle{ \delta(N) }[/math] in place of [math]\displaystyle{ \delta(\mathcal{HAP}(N),x) }[/math].

The discrepancy of a sequence [math]\displaystyle{ (x_n) }[/math] is the supremum of [math]\displaystyle{ |\sum_{n\in P}x_n| }[/math] 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.) [math]\displaystyle{ Insert formula here }[/math] A sequence [math]\displaystyle{ (x_n) }[/math] has discrepancy at most φ(n) if for every natural number N the maximum value of [math]\displaystyle{ |\sum_{n\in P}x_n| }[/math] 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 [math]\displaystyle{ (x_n) }[/math] is completely multiplicative if [math]\displaystyle{ x_{mn}=x_mx_n }[/math] 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 [math]\displaystyle{ x_{mn}=x_mx_n }[/math] 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 [math]\displaystyle{ \prod p_i^{a_i} }[/math] then λ(n) equals [math]\displaystyle{ (-1)^{\sum a_i} }[/math].

A HAP-subsequence of a sequence [math]\displaystyle{ (x_n) }[/math] is a subsequence of the form [math]\displaystyle{ x_d,x_{2d},x_{3d},\dots }[/math] for some d. If [math]\displaystyle{ (x_n) }[/math] is a multiplicative [math]\displaystyle{ \pm 1 }[/math] sequence, then every HAP-subsequence is equal to either [math]\displaystyle{ (x_n) }[/math] or [math]\displaystyle{ (-x_n) }[/math]. We shall call a sequence weakly multiplicative if it has only finitely many distinct HAP-subsequences. Let us also call a [math]\displaystyle{ \pm 1 }[/math] sequence quasi-multiplicative if it is a composition of a completely multiplicative function from [math]\displaystyle{ \mathbb{N} }[/math] 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 [math]\displaystyle{ (x_n) }[/math] is a weakly multiplicative sequence, then it has an HAP-subsequence that is quasi-multiplicative.

It is convenient to define the maps [math]\displaystyle{ T_k }[/math] for [math]\displaystyle{ k \geq 1 }[/math] by [math]\displaystyle{ T_k(x)_n = x_{kn} }[/math], where [math]\displaystyle{ x = (x_1, x_2, \ldots) }[/math] is a sequence.

Simple observations

• To answer the problem negatively, it is sufficient to find a completely multiplicative sequence (that is, a sequence [math]\displaystyle{ (x_n) }[/math] such that [math]\displaystyle{ x_{mn}=x_mx_n }[/math] for every m,n) such that its partial sums [math]\displaystyle{ x_1+\dots+x_n }[/math] 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 [math]\displaystyle{ \log_3n +1 }[/math]. 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. [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 [math]\displaystyle{ \mathbb{N} }[/math] 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 [math]\displaystyle{ x_n=hf(n) }[/math]. (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 [math]\displaystyle{ \pm 1 }[/math] sequence [math]\displaystyle{ (x_n) }[/math] starts with 1 and has only finitely many distinct subsequences of the form [math]\displaystyle{ (x_d,x_{2d},x_{3d},\dots) }[/math], then it must have a subsequence that arises in the above way. (This was mentioned just above in the terminology section.)

• The problem for the positive integers is equivalent to the problem for the positive rationals. [2](Sketch proof: if you have a function f from the positive integers to {-1,1} that works, then define [math]\displaystyle{ f_q(x) }[/math] to be f(q!x) whenever q!x is an integer. Then take a pointwise limit of a subsequence of the functions [math]\displaystyle{ f_q }[/math].)

Experimental evidence

A nice feature of the problem is that it lends itself well to investigation on a computer. Although the number of [math]\displaystyle{ \pm 1 }[/math] 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 [math]\displaystyle{ x_1=-x_2=1 }[/math] and [math]\displaystyle{ x_n=-x_{n/3} }[/math] or [math]\displaystyle{ x_n=x_{n-3} }[/math] according to whether [math]\displaystyle{ n }[/math] is a multiple of 3 or not, yields a sequence with

[math]\displaystyle{ \delta(N) \leq \log_9(N)+1 }[/math]

for sufficiently large [math]\displaystyle{ N }[/math]. Currently, this is the record-holder for slow growing discrepancy.

The Thue-Morse sequence has discrepancy [math]\displaystyle{ \delta(N) \gg \sqrt{N} }[/math] [citation needed].

A random sequence (each [math]\displaystyle{ x_i }[/math] chosen independently) has discrepancy at least [math]\displaystyle{ \sqrt{2N \log\log N} }[/math] by the iterated logarithm.

Determining the growth of the discrepancy of Liouville's lambda function is equivalent to solving the Riemann hypothesis. However, this growth cannot be bounded above by [math]\displaystyle{ n^{1/2-\epsilon} }[/math] 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 [math]\displaystyle{ (x_n) }[/math] (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?

• Is there any completely multiplicative counterexample? (This may turn out to be a very hard question. If so, then answering the previous question could turn out to be the best we can hope for without making a substantial breakthrough in analytic number theory.)

Annotated Bibliography

• Mathias, A. R. D. 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.

• Borwein, Peter, and Choi, Stephen. A variant of Liouville's lambda function: some surprizing formulae.

Explicit formulas for the discrepancy of some completely multiplicative functions whose discrepancy is logarithmic. A typical example is: Let [math]\displaystyle{ \lambda_3(n) = (-1)^{\omega_3(n)} }[/math] where [math]\displaystyle{ \omega_3(n) }[/math] is the number of distinct prime factors congruent to [math]\displaystyle{ -1 \bmod 3 }[/math] in [math]\displaystyle{ n }[/math] (with multiple factors counted multiply). Then the discrepancy of the [math]\displaystyle{ \lambda_3 }[/math] sequence up to [math]\displaystyle{ N }[/math] is exactly the number of 1's in the base three expansion of [math]\displaystyle{ N }[/math].

• Vijay, Sujith. On the discrepancy of quasi-progressions. Electronic Journal of Combinatorics, R104 of Volume 15(1), 2008.

A quasi-progression is a sequence of the form [math]\displaystyle{ \lfloor k \alpha \rfloor }[/math], with [math]\displaystyle{ 1\leq k \leq K }[/math] 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 [math]\displaystyle{ (1/50)n^{1/6} }[/math].

• Granville and Soundararajan. Multiplicative functions in arithmetic progressions

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)."

• As 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, P. and Graham, R. Old and New Problems and Results in Combinatorial Number Theory: van der Waerden's Theorem and Related Topics, L'Enseignement Math. 25 (1979), 325-344.

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.

• Hochberg, Robert. Large Discrepancy In Homogenous Quasi-Arithmetic Progressions. Combinatorica, Volume 26 (2006), Number 1.

Roth's method for the [math]\displaystyle{ n^{1/4} }[/math] 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.

• Finch, S. Two colorings of positive integers. Dated May 27, 2008.

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.