Fourier reduction

From Polymath1Wiki

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

$F(a_1,\ldots,a_d) := f( p_1^{a_1} \ldots p_d^{a_d} ).$

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

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

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

$\pi(p_1^{a_1} \ldots p_d^{a_d}) := (a_1,\ldots,a_d)$

then by hypothesis one has

$|F(x+\pi(1)) + \ldots + F(x+\pi(n))| \leq C$

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

$\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$

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

$\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.$

Comparing this with (1) and using the pigeonhole principle, we conclude that there exists $ξ$ such that

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

If we let $g: {\Bbb N} \to S^1$ be a completely multiplicative function such that $g (p i) = e (ξ i / M)$ for all i=1,...,d, we have

$e( \xi \cdot \pi(j) / M ) = g(j)$

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

$\frac{1}{N} \sum_{n=1}^N |\sum_{j=1}^n g(j)|^2 \ll C$ .

So, if one can show a uniform bound

$\frac{1}{N} \sum_{n=1}^N |\sum_{j=1}^n g(j)|^2 \geq \omega(N)$

where $ω(N)$ goes to infinity as $N \to \infty$ , for arbitrary $S 1$ -valued multiplicative functions, one is done!

Actually, one can do a little better than this. From (1) we see that $|\hat F(\xi)|^2$ induces a probability measure (depending on N,M) on completely multiplicative functions $g: {\Bbb Q} \to S^1$ (strictly speaking, this function is only defined on rationals that involve the primes $p_1,\ldots,p_d$ , 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

${\Bbb E} |g(1)+\ldots+g(n)|^2 \ll C$

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

$\sup_n {\Bbb E} |g(1)+\ldots+g(n)|^2 = \infty$ (*)

for all probabilistic completely multiplicative functions taking values in $S 1$ . 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 $f (q 2 x) = f (x)$ for all rational q) then we can restrict g to be {-1,+1} valued (basically because $({\Bbb Z}/M{\Bbb Z})^d$ can now be replaced with $({\Bbb Z}/2{\Bbb Z})^d$ in the above analysis.

Actually, (*) is equivalent to the following Hilbert-space version of EDP: if $f: {\Bbb N} \to S$ 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 $μ$ 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 $L 2 (d μ)$ and let $f(n) \in L^2(d\mu)$ be the evaluation map $g \mapsto g(n)$ for each n, we see that f has bounded discrepancy.

Fourier reduction

From Polymath1Wiki

Views

Personal tools

Navigation

Search

Toolbox