Fourier reduction

From Polymath Wiki
Revision as of 07:15, 27 January 2010 by Teorth (Talk | contribs)

Jump to: navigation, search

Let f be an arbitrary function from [math]{\Bbb Z}[/math] to {-1,+1} of discrepancy at most C. Let N be a moderately large integer, let [math]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]F: ({\Bbb Z}/M{\Bbb Z})^d \to \{-1,+1\}[/math] by the formula

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

whenever [math]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]\sum_{\xi \in ({\Bbb Z}/M{\Bbb Z})^d} |\hat F(\xi)|^2 = 1.[/math] (1)

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

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

then by hypothesis one has

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

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

[math] \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] \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]\xi[/math] such that

[math]\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]g: {\Bbb N} \to S^1[/math] be a completely multiplicative function such that [math]g(p_j) = e(\xi_j/M)[/math] for all j=1,...,d, we have

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

and thus

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

So, if one can show a uniform bound

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

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