The Erdős discrepancy problem

Introduction and statement of problem

The Erdős discrepancy problem is a problem that has been around since the 1930s and has resisted attack ever since. 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.

To state the problem, we first define a homogeneous arithmetic progression to be a set of positive integers of the form {d,2d,3d,...,nd}. (It is also reasonable to define it to be a set of non-negative integers of the form {0,d,2d,3d,...,nd}: at the time of writing it is not clear what the "official" definition should be.) Suppose that we have a sequence [math]\displaystyle{ x_1,x_2,x_3,\dots }[/math] of elements of the set [math]\displaystyle{ \{-1,1\} }[/math] (henceforth to be referred to as a [math]\displaystyle{ \pm 1 }[/math] sequence). We say that the discrepancy of the sequence [math]\displaystyle{ (x_n) }[/math] with respect to a set A of positive integers is [math]\displaystyle{ |\sum_{n\in A}x_n| }[/math]. The reason for this name is that we can think of the sequence as a red/blue-colouring of the positive integers, and the discrepancy with respect to A is then the difference between the number of red elements of A and the number of blue elements of A. The Erdős discrepancy problem is the following question.

Problem. Let [math]\displaystyle{ (x_n) }[/math] be a [math]\displaystyle{ \pm 1 }[/math] sequence. Must it be the case that for every constant C there exists a homogeneous arithmetic progression P such that the discrepancy of the sequence [math]\displaystyle{ (x_n) }[/math] with respect to P is at least C?

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.

• 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.

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 a sequence of length 1124 with discrepancy 2. See this page for more details about this and for further links.