Topological dynamics formulation

Define a topological dynamical system over the rationals to be a pair (X,T), where X is a compact metrisable space, and [math]\displaystyle{ T = (T_q)_{q \in {\Bbb Q}^+} }[/math] is a continuous action of the positive rationals (as a multiplicative group) on X. In other words, for each positive rational q, [math]\displaystyle{ T_q: X \to X }[/math] is a homeomorphism such that [math]\displaystyle{ T_{qr} = T_q T_r }[/math] for all positive rationals q, r. In particular, the [math]\displaystyle{ T_q }[/math] all commute. For any function [math]\displaystyle{ f: X \to {\Bbb C} }[/math], we write [math]\displaystyle{ T_q f }[/math] for [math]\displaystyle{ f \circ T_q }[/math].

The Erdos discrepancy problem is then equivalent to

Conjecture 1. Let (X,T) be a topological dynamical system over the positive rationals, and let [math]\displaystyle{ f: X \to \{-1,+1\} }[/math] be a continuous function. Then the quantity [math]\displaystyle{ \sum_{i=1}^n T_i f(x) }[/math] is unbounded as x ranges over X and n ranges over the natural numbers.

Proof of Conjecture 1 assuming EDP Suppose for contradiction that [math]\displaystyle{ |\sum_{i=1}^n T_i f(x)| \leq C }[/math] for some C and all x, n. Pick a point [math]\displaystyle{ x_0 }[/math] in X, and consider the function [math]\displaystyle{ \tilde f: {\Bbb N} \to \{-1,1\} }[/math] defined by

[math]\displaystyle{ \tilde f(i) := T_i f(x_0). }[/math] (1)

Then [math]\displaystyle{ \tilde f }[/math] has discrepancy at most C, contradicting EDP. QED

Proof of EDP assuming Conjecture 1 It suffices to show EDP for the positive rationals. Suppose for contradiction that this failed, then there exists [math]\displaystyle{ f: {\Bbb Q}^+ \to \{-1,1\} }[/math] with discrepancy bounded by some finite C. Let [math]\displaystyle{ \Omega }[/math] be the compact metrisable space [math]\displaystyle{ \Omega = \{-1,1\}^{{\Bbb Q}^+} }[/math] with shift :[math]\displaystyle{ T_q ( (a_r)_{r \in {\Bbb Q}^+} ) := (a_{qr})_{r \in {\Bbb Q}^+} }[/math]; observe that this is a continuous action of the rationals. Let [math]\displaystyle{ x_0 \in \Omega }[/math] be the point

[math]\displaystyle{ x_0 := (f(r))_{r \in {\Bbb Q}^+} }[/math]

and let X be the orbit closure of [math]\displaystyle{ x_0 }[/math], i.e. the topological closure of [math]\displaystyle{ \{ T_q(x_0): q \in {\Bbb Q}^+ \} }[/math]. This is a compact metrisable space, and T restricts to a continuous action on this space.

Set [math]\displaystyle{ \tilde f: X \to \{-1,+1\} }[/math] to be the function

[math]\displaystyle{ \tilde f( (a_r)_{r \in {\Bbb Q}^+} ) := a_1 }[/math];

observe that this is a continuous function. By Conjecture 1, we can find [math]\displaystyle{ x = (a_r)_{r \in {\Bbb Q}^+} }[/math] and n such that [math]\displaystyle{ |\sum_{i=1}^n T_i \tilde f(x)| \gt C }[/math]. But x can be approximated to arbitrary accuracy by a shift of [math]\displaystyle{ x_0 }[/math]. Unpacking all the definitions, we conclude that f has discrepancy greater than C, a contradiction. QED.

We say that a topological system X is minimal if it contains no proper non-empty compact shift-invariant subset. An easy application of Zorn's lemma shows that every topological system contains a minimal system. Thus, to prove Conjecture 1, it suffices to do so for minimal systems.

Given a non-empty open set in a minimal system, one must be able to cover that system by the shifts of the open set, since otherwise the complement of that cover would be a proper compact shift-invariant subset, contradicting minimality. By compactness, this implies that a minimal system can be covered by finitely many translates of the open set.

In terms of sequences, this means that the sequences [math]\displaystyle{ f: {\Bbb Q}^+ \to \{-1,+1\} }[/math] associated to a minimal system (by (1)) have the following almost periodicity property: given any finite set of equations of the form

[math]\displaystyle{ f(q_1 x) = a_1, \ldots, f(q_k x) = a_k }[/math] (*)

for some positive rationals [math]\displaystyle{ q_1,\ldots,q_k }[/math] and [math]\displaystyle{ a_1,\ldots,a_k\in \{-1,+1\} }[/math], the set of solutions x to (*) is either empty or syndetic, which means that there is a finite set of positive rationals [math]\displaystyle{ r_1,\ldots,r_m }[/math] such that for every positive rational x, at least one of [math]\displaystyle{ xr_1,\ldots,xr_m }[/math] solves (*).

The Krylov-Bogolubov theorem asserts that X supports a probability measure that is shift-invariant. The reason for this is that the positive rationals are amenable, and thus admit a Folner sequence F_n. Now start with your favourite probability measure (e.g. a Dirac mass) and average it over the Folner sequences. Then use Prokhorov's theorem to take a weak limit, which will be automatically invariant by construction.

Once we have a shift-invariant measure, ergodic theory comes into play. For instance, the Birkhoff ergodic theorem will assert that for all rationals, and all continuous functions F, the limit [math]\displaystyle{ \lim_{N\to\infty} \frac{1}{N} \sum_{n=1}^n T_{q^n} F(x) }[/math] exists for almost every x in X (with respect to the invariant measure). Because there are only countably many rationals, and the space of continuous functions is separable, we can thus find an x which is generic, in the sense that the above limits exist for all F and all q. In particular, this implies that if EDP fails, we can find a minimal sequence f of bounded discrepancy such that the limit

[math]\displaystyle{ \lim_{N \to \infty} \frac{1}{N} \sum_{n=1}^n F(f( q^n r_1 ), \ldots, f(q^n r_m)) }[/math]

exists for all positive rationals [math]\displaystyle{ q, r_1,\ldots,r_m }[/math] and all functions [math]\displaystyle{ F: \{-1,+1\}^m \to {\Bbb C} }[/math].

Note also that if [math]\displaystyle{ f: X \to \{-1,+1\} }[/math] has bounded discrepancy on a measure preserving system, then its mean must be zero, as can be seen by averaging [math]\displaystyle{ \frac{1}{n} (f(x)+\ldots+f(T_n x)) }[/math] with respect to x, and then sending n to infinity. Thus, f equals 1 exactly half of the time, and -1 half the time.