Upper and lower discrepancy

Define the lower discrepancy of a sequence [math]\displaystyle{ f: {\Bbb Q} \to \{-1,+1\} }[/math] to be the infimal value of f(x)+f(2x)+...+f(nx). Similarly define the upper discrepancy.

Proposition 1. There is a sequence of bounded discrepancy and lower discrepancy 1. Then there exists a sequence with both upper and lower discrepancy 1, which implies drift 2, contradicting the results on drift (or on the lack of discrepancy 1 sequences).

This result was first shown by Mathias.

Proof 1 (ergodic theory). By the topological dynamics formulation, one can find a measure-preserving action T of [math]\displaystyle{ {\Bbb Q} }[/math] on a probability space [math]\displaystyle{ (X,\mu) }[/math] and a function [math]\displaystyle{ f: X \to \{-1,+1\} }[/math] such that the functions [math]\displaystyle{ f + T_2 f + T_3 f + \ldots + T_n f }[/math] are bounded below by 1 and bounded above by a constant.

Integrating and taking averages as n goes to infinity, we conclude that f has mean zero with respect to [math]\displaystyle{ \mu }[/math]. Thus the set [math]\displaystyle{ E := f^{-1}(\{1\}) }[/math] has measure 1/2.

On the other hand, since f(x)+f(T_2 x) is always at least -1, E and T_2 E must cover the whole space, which means that E and T_2 E must be complements of each other up to measure zero errors. In other words, f(T_2 x) = -f(x) for almost everywhere.

Since [math]\displaystyle{ f + T_2 f + T_3 f + \ldots + T_n f }[/math] is bounded below everywhere by -1, we may now shift by T_2 and conclude that [math]\displaystyle{ f + T_2 f + T_3 f + \ldots + T_n f }[/math] is bounded above by +1 almost everywhere. Picking a generic point x and looking at the sequence [math]\displaystyle{ q \mapsto T_q f(x) }[/math] we obtain the claim.

Proof 2 (combinatorics). We start with a sequence [math]\displaystyle{ f: {\Bbb Q} \to \{-1,+1\} }[/math] of bounded discrepancy and lower discrepancy 1. The first goal is to ensure that f has "mean 0" in some sense. Here we have to use the amenability of the rationals. Pick a threshold w, and then an extremely large integer M (much larger than w), and consider the box B of rationals of the form [math]\displaystyle{ \prod_{p\lt =w} p^{m_p} }[/math] where p ranges over primes less than w and [math]\displaystyle{ m_p }[/math] ranges over integers between -M and M. The point of introducing this box is that it is stable with respect to multiplication by rationals q of height at most w (i.e. a/b where a,b are at most w); indeed, the symmetric difference between B and qB is a negligible fraction of B in the limit as M goes to infinity. (What I'm doing here is basically constructing a Folner sequence for the rationals).

Using the boundedness of f(x)+...+f(wx) and the first moment method we see that the average of f on B is o(1) in the limit as w goes to infinity slowly and M goes to infinity much more quickly. So the sets E = {x in B: f(x) = 1} has density 1/2+o(1). But since f(x)+f(2x) is never equal to -2, E and 2E must cover almost all of B, and so the intersection of E with 2E has density o(1) in B.

So if one shifts by a random point in x, we will have f(2x)=-f(x) with probability 1-o(1), and similarly with x replaced by qx for q of bounded height. Since f has lower discrepancy 1, it thus has upper discrepancy 1 "near x" with probability 1-o(1) in some sense; taking a subsequence limit as usual we obtain genuine upper discrepancy 1.

Remark Here is a short proof that a sequence cannot have both upper and lower discrepancy 1, that does not use the full complexity of the "no drift 2" result. With discrepancy 1, one must have f(2x) = -f(x) for all x, and similarly f(4x) = -f(3x), f(6x) = -f(5x), and f(10x) = -f(9x). This forces

f(10x) = -f(5x) = f(6x)

but also

f(10x) = -f(9x) = f(12x) = -f(6x)

a contradiction.