Difference between revisions of "Fourier reduction"

From Polymath Wiki
Jump to: navigation, search
m (S^1: text --> TeX)
Line 46: Line 46:
 
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
 
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> \sup_n {\Bbb E} |g(1)+\ldots+g(n)|^2 = \infty</math>
+
:<math> \sup_n {\Bbb E} |g(1)+\ldots+g(n)|^2 = \infty</math> (*)
  
 
for all probabilistic completely multiplicative functions taking values in <math>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.
 
for all probabilistic completely multiplicative functions taking values in <math>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>f(q^2 x) = f(x)</math> for all rational q) then we can restrict g to be {-1,+1} valued (basically because <math>({\Bbb Z}/M{\Bbb Z})^d</math> can now be replaced with <math>({\Bbb Z}/2{\Bbb Z})^d</math> in the above analysis.
 
If one is interested in square-invariant functions only (so <math>f(q^2 x) = f(x)</math> for all rational q) then we can restrict g to be {-1,+1} valued (basically because <math>({\Bbb Z}/M{\Bbb Z})^d</math> can now be replaced with <math>({\Bbb Z}/2{\Bbb Z})^d</math> in the above analysis.
 +
 +
Actually, (*) is equivalent to the following Hilbert-space version of EDP: if <math>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>\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>L^2(d\mu)</math> and let <math>f(n) \in L^2(d\mu)</math> be the evaluation map <math>g \mapsto g(n)</math> for each n, we see that f has bounded discrepancy.

Revision as of 18:26, 28 January 2010

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_i) = e(\xi_i/M)[/math] for all i=1,...,d, we have

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

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

[math]\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]\frac{1}{N} \sum_{n=1}^N |\sum_{j=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!

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

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

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