# Difference between revisions of "Fourier reduction"

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 $\xi$ 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_j) = e(\xi_j/M)$ for all j=1,...,d, we have

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

and thus

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

So, if one can show a uniform bound

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

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