Drift

The drift of a sequence [math]\displaystyle{ f: {\Bbb Q}^+ \to \{ -1, +1 \} }[/math] is the maximal value of [math]\displaystyle{ |f(mx)+\ldots+f(nx)| }[/math] for all rational x and all natural numbers m<n. The Erdos discrepancy problem is equivalent to showing that the drift is unbounded.

It seems likely that one can show that the drift is at least 3. Here are some preliminary results in this direction:

Proposition 1 If f has drift at most 2, and f(x) = f(2x), then f(3x/2) = f(3x) = -f(x).

Proof If f has drift at most 2, then |f(x)+f(2x)+f(3x)| and |f(x)+f(3x/2)+f(2x)| <= 2, and the claim follows.

Corollary 2 If f has drift at most 2, and the function [math]\displaystyle{ f_2(x) := f(x)f(2x) }[/math] equals 1 for some x, then it equals 1 for [math]\displaystyle{ (3/2)^j x }[/math] for any [math]\displaystyle{ j=0,1,2,\ldots }[/math].

Corollary 3 If there exists a function of drift at most 2, then there exists a function f of drift at most 2 such that [math]\displaystyle{ f_2(x) = f_2(3x/2) }[/math] for all x.

Proof For any fixed [math]\displaystyle{ x_0 }[/math], we look at the functions [math]\displaystyle{ f_j(x) := x \mapsto f((3/2)^{-j} x) }[/math] as [math]\displaystyle{ j \to \infty }[/math]. By Corollary 2, the quantity [math]\displaystyle{ f_j(x_0) f_j(2x_0) }[/math] is eventually constant in j. Taking a subsequence limit as j goes to infinity, we can ensure that [math]\displaystyle{ f_2((3/2)^j x_0) }[/math] is independent of j. We then vary [math]\displaystyle{ x_0 }[/math] over the rationals and use a diagonalisation argument to obtain the result. (Note that the property that [math]\displaystyle{ f_2((3/2)^j x_0) }[/math] is independent of j is preserved under these sorts of scaling limits in the 3/2 direction.)

Define a 23-slice to be any set of the form [math]\displaystyle{ \{ 2^a 3^b x: a,b \in {\Bbb Z} \} }[/math] for some rational x.

Corollary 4 If there exists a function of drift at most 2, then there exists a function f of drift at most 2 such that on each 23-slice S, we either have [math]\displaystyle{ f(2x)=-f(x) }[/math] for all x in S, or [math]\displaystyle{ f(3x)=-f(2x) }[/math] for all x in S.

Proof We begin with a function f as given by Corollary 3. Pick a slice, and suppose that the first claim fails on this slice, thus f(2x)=f(x) for some x in S. By Proposition 1, we see that f(3x/2)=-f(x). By Corollary 3, we conclude that [math]\displaystyle{ f(2^j (3/2) x) = - f(2^j x) }[/math] for all integers j. In particular, f(2(3/2) x) = f(3/2 x). Iterating this, we see that f( 2^j (3/2)^{i+1} x) = - f(2^j (3/2)^i x) for all integers j and natural numbers i. Taking a scaling limit along 3/2 as in Corollary 3, we may then assume that f(3y)=-2f(y) for all y in this slice S. Repeating this argument once for each slice and diagonalising we obtain the claim.

NB: This is the maximum one can say just by looking at the 23-smooth numbers 1,2,3,4; if f has the structure of Corollary 4, then the drift inside 1,2,3,4 is automatically at most 2.

We call a slice S Type I if f(2x)=-f(x) for all x in S, and Type II if f(3x)=-f(2x) for all x in S.

Lemma 5 Let f have drift 2. For any rational x, we either have f((n+1)x) = -f(n x) for all odd n, or for all even n.

Proof By hypothesis, for any fixed x that the partial sums f(x)+f(2x)+...+f(nx) range in an interval of length at most 2. Since f only the values +1 and -1, we conclude that these partial sums must return to the same point either for all odd n, or for all even n. The claim follows.

Henceforth we assume f is as in Corollary 4.

We call an x of Type A if f((n+1)x) = -f(nx) for all odd n, and Type B if f((n+1)x) = -f(nx) for all even n.

Lemma 6 In a Type I slice, all elements are of Type B.

Proof Suppose for contradiction that we have a type A element x of a Type I slice S. Without loss of generality we may assume that x=1 and f(x)=1. We then have

f(2) = -f(1) = -1    (Type A or Type I property)
f(4) = -f(2) = 1     (Type I property)
f(3) = -f(4) = -1    (Type A property)
f(6) = -f(3) = 1     (Type I property)
f(5) = -f(6) = -1    (Type A property)
f(8) = -f(4) = -1    (Type I property)
f(7) = -f(8) = 1     (Type A property)
f(12)= -f(6) = -1    (Type I property)
f(9) = 1             (|f(6)+f(9)+f(12)| <= 2)
f(16) = -f(8) = -1   (Type A property)
f(15) = -f(16)= 1    (Type I property)
f(18) = -f(9) = 1    (Type A property) 

But then f(6)+f(9)+f(12)+f(15)+f(18)=3, a contradiction.

Corollary 7 All slices are of Type II. In other words, f(3x)=f(-2x) for all x.

Proof If x is of type B, then f(3x)=-f(2x). Thus by Lemma 6, all Type I slices are of Type II.

Lemma 8 If x is of Type B, then so is 2x.

Proof Suppose that 1 (say) was of Type B; we may normalise f(2)=1. Then

f(3) = -f(2) = -1    (Type B or Type II property)
f(6) = -f(4)         (Type II property)
f(9) = -f(6) = f(4)  (Type II property)
f(8) = -f(9) = -f(4) (Type B property)

Since f(6)=f(8), 2 cannot be of Type A, and is hence of Type B.

Corollary 9 No x is of Type B.

Proof Suppose that 1 (say) was of Type B; again we normalise f(2)=1. By Lemma 8, 2 is also of Type B. We continue the calculations from Lemma 8:

f(12) = -f(8) = f(4)    (Type II property)
f(13) = -f(12) = -f(4)  (Type B property)
f(14) = -f(12) = -f(4)  (Type B property for 2)
f(15) = -f(14) = f(4)   (Type B property)

But then f(9)+f(12)+f(15) = 3f(4), contradiction.

Thus all x are of type A, thus for all x

f(2x) = -f(x)          (Type A property)
f(3x) = -f(2x) = f(x)  (Type II property)
f(4x) = -f(2x) = f(x)  (Type A property)

But then f(x)+f(2x)+f(3x)+f(4x) = 3f(x), contradiction. So there are no f of drift 2.