# Difference between revisions of "Fourier reduction"

(New page: 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], a...) |
m (math mode) |
||

(6 intermediate revisions by 2 users not shown) | |||

Line 14: | Line 14: | ||

:<math>|F(x+\pi(1)) + \ldots + F(x+\pi(n))| \leq C</math> | :<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 | + | for all <math>(1-O_N(1/M))</math> 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> | :<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> | ||

Line 26: | Line 26: | ||

:<math>\frac{1}{N} \sum_{n=1}^N |\sum_{j=1}^n e( \xi \cdot \pi(j) / M )|^2 \ll C</math>. | :<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( | + | 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> | :<math> e( \xi \cdot \pi(j) / M ) = g(j)</math> | ||

− | and thus | + | for all j=1,...,N, and thus |

− | :<math>\frac{1}{N} \sum_{n=1}^N |g(j)|^2 \ll C</math>. | + | :<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 | So, if one can show a uniform bound | ||

− | :<math>\frac{1}{N} \sum_{n=1}^N |g(j)|^2 \geq \omega(N)</math> | + | :<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! | 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. |

## Latest revision as of 00:46, 13 May 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 [math](1-O_N(1/M))[/math] 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.