Fourier reduction

Let f be an arbitrary function from [math]\displaystyle{ {\Bbb Z} }[/math] to {-1,+1} of discrepancy at most C. Let N be a moderately large integer, let [math]\displaystyle{ p_1,\ldots,p_d }[/math] be the primes in [N], and let M be a huge integer (much larger than N). Then we can define a function [math]\displaystyle{ F: ({\Bbb Z}/M{\Bbb Z})^d \to \{-1,+1\} }[/math] by the formula

[math]\displaystyle{ F(a_1,\ldots,a_d) := f( p_1^{a_1} \ldots p_d^{a_d} ). }[/math]

whenever [math]\displaystyle{ a_1,\ldots,a_d \in [M] }[/math]. Note that F has a normalised L^2 norm of 1, so by the Plancherel identity

[math]\displaystyle{ \sum_{\xi \in ({\Bbb Z}/M{\Bbb Z})^d} |\hat F(\xi)|^2 = 1. }[/math] (1)

Let [math]\displaystyle{ \pi: [N] \to {\Bbb Z}^d }[/math] be the map

[math]\displaystyle{ \pi(p_1^{a_1} \ldots p_d^{a_d}) := (a_1,\ldots,a_d) }[/math]

then by hypothesis one has

[math]\displaystyle{ |F(x+\pi(1)) + \ldots + F(x+\pi(n))| \leq C }[/math]

for all (1-O_N(1/M)) of the x in [math]\displaystyle{ ({\Bbb Z}/M{\Bbb Z})^d }[/math], and all [math]\displaystyle{ 1 \leq n \leq N }[/math]. Applying Plancherel to this, we obtain

[math]\displaystyle{ \sum_{\xi \in ({\Bbb Z}/M{\Bbb Z})^d} |\hat F(\xi)|^2 |\sum_{j=1}^n e( \xi \cdot \pi(j) / M ) |^2 \ll C }[/math]

for each such n, and so on averaging in n we have

[math]\displaystyle{ \sum_{\xi \in ({\Bbb Z}/M{\Bbb Z})^d} |\hat F(\xi)|^2 \frac{1}{N} \sum_{n=1}^N |\sum_{j=1}^n e( \xi \cdot \pi(j) / M )|^2 \ll C. }[/math]

Comparing this with (1) and using the pigeonhole principle, we conclude that there exists [math]\displaystyle{ \xi }[/math] such that

[math]\displaystyle{ \frac{1}{N} \sum_{n=1}^N |\sum_{j=1}^n e( \xi \cdot \pi(j) / M )|^2 \ll C }[/math].

If we let [math]\displaystyle{ g: {\Bbb N} \to S^1 }[/math] be a completely multiplicative function such that [math]\displaystyle{ g(p_i) = e(\xi_i/M) }[/math] for all i=1,...,d, we have

[math]\displaystyle{ e( \xi \cdot \pi(j) / M ) = g(j) }[/math]

for all j=1,...,N, and thus

[math]\displaystyle{ \frac{1}{N} \sum_{n=1}^N |\sum_{j=1}^n g(j)|^2 \ll C }[/math].

So, if one can show a uniform bound

[math]\displaystyle{ \frac{1}{N} \sum_{n=1}^N |\sum_{j=1}^n g(j)|^2 \geq \omega(N) }[/math]

where [math]\displaystyle{ \omega(N) }[/math] goes to infinity as [math]\displaystyle{ N \to \infty }[/math], for arbitrary [math]\displaystyle{ S^1 }[/math]-valued multiplicative functions, one is done!

Actually, one can do a little better than this. From (1) we see that [math]\displaystyle{ |\hat F(\xi)|^2 }[/math] induces a probability measure (depending on N,M) on completely multiplicative functions [math]\displaystyle{ g: {\Bbb Q} \to S^1 }[/math] (strictly speaking, this function is only defined on rationals that involve the primes [math]\displaystyle{ p_1,\ldots,p_d }[/math], but one can extend to the rationals by setting g to equal 1 on all other primes), and for g drawn from this probability measure the above arguments in fact show that

[math]\displaystyle{ {\Bbb E} |g(1)+\ldots+g(n)|^2 \ll C }[/math]

for all n up to N. Taking a weak limit of these probability measures (using Prokhorov's theorem) we can in fact get this for all n. So to solve EDP, it in fact suffices to show that

[math]\displaystyle{ \sup_n {\Bbb E} |g(1)+\ldots+g(n)|^2 = \infty }[/math] (*)

for all probabilistic completely multiplicative functions taking values in [math]\displaystyle{ S^1 }[/math]. This should be compared to the completely multiplicative special case of EDP, in which g takes values in {-1,+1} and is deterministic.

If one is interested in square-invariant functions only (so [math]\displaystyle{ f(q^2 x) = f(x) }[/math] for all rational q) then we can restrict g to be {-1,+1} valued (basically because [math]\displaystyle{ ({\Bbb Z}/M{\Bbb Z})^d }[/math] can now be replaced with [math]\displaystyle{ ({\Bbb Z}/2{\Bbb Z})^d }[/math] in the above analysis.

Actually, (*) is equivalent to the following Hilbert-space version of EDP: if [math]\displaystyle{ f: {\Bbb N} \to S }[/math] takes values in the unit sphere of a (real or complex) Hilbert space, then the discrepancy of f is unbounded (note that discrepancy can be defined in arbitrary normed vector spaces). The derivation of Hilbert-space EDP from (*) follows the argument above (f is now vector-valued instead of scalar, but Plancherel's theorem and all the other tools used above go through without difficulty).

Conversely, if (*) failed, then we have a probability distribution [math]\displaystyle{ \mu }[/math] on the space of completely multiplicative functions for which the left-hand side of (*) is bounded. If we then set H to be the complex Hilbert space [math]\displaystyle{ L^2(d\mu) }[/math] and let [math]\displaystyle{ f(n) \in L^2(d\mu) }[/math] be the evaluation map [math]\displaystyle{ g \mapsto g(n) }[/math] for each n, we see that f has bounded discrepancy.