Gowers norm

"Uniformity norm" redirects here. For the function field norm, see uniform norm. For uniformity in topology, see uniform space.

In mathematics, in the field of additive combinatorics, a Gowers norm or uniformity norm is a class of norm on functions on a finite group or group-like object which are used in the study of arithmetic progressions in the group. It is named after Timothy Gowers, who introduced it in his work on Szemerédi's theorem.^[1]

Definition

Let f be a complex-valued function on a finite Abelian group G and let J denote complex conjugation. The Gowers d-norm is

\Vert f\Vert _{{U^{d}(G)}}^{{2^{d}}}={\mathbf {E}}_{{x,h_{1},\ldots ,h_{d}\in G}}\prod _{{\omega _{1},\ldots ,\omega _{d}\in \{0,1\}}}J^{{\omega _{1}+\cdots +\omega _{d}}}f\left({x+h_{1}\omega _{1}+\cdots +h_{d}\omega _{d}}\right)\ .

Gowers norms are also defined for complex valued functions f on a segment [N]={0,1,2,...,N-1}, where N is a positive integer. In this context, the uniformity norm is given as $\Vert f\Vert _{{U^{d}[N]}}=\Vert {\tilde {f}}\Vert _{{U^{d}({\mathbb {Z}}/{\tilde {N}}{\mathbb {Z}})}}/\Vert 1_{{[N]}}\Vert _{{U^{d}({\mathbb {Z}}/{\tilde {N}}{\mathbb {Z}})}}$ , where ${\tilde N}$ is a large integer, $1_{{[N]}}$ denotes the indicator function of [N], and ${\tilde f}(x)$ is equal to $f(x)$ for $x\in [N]$ and $0$ for all other $x$ . This definition does not depend on ${\tilde N}$ , as long as ${\tilde N}>2^{d}N$ .

Inverse conjectures

An inverse conjecture for these norms is a statement asserting that if a bounded function f has a large Gowers d-norm then f correlates with a polynomial phase of degree d-1 or other object with polynomial behaviour (e.g. a (d-1)-step nilsequence). The precise statement depends on the Gowers norm under consideration.

The Inverse Conjecture for vector spaces over a finite field ${\mathbb F}$ asserts that for any $\delta > 0$ there exists a constant $c > 0$ such that for any finite dimensional vector space V over ${\mathbb F}$ and any complex valued function $f$ on $V$ , bounded by 1, such that $\Vert f\Vert _{{U^{{d}}[V]}}\geq \delta$ , there exists a polynomial sequence $P\colon V\to {\mathbb {R}}/{\mathbb {Z}}$ such that

\left|{\frac {1}{|V|}}\sum _{{x\in V}}f(x)e(-P(x))\right|\geq c,

where $e(x):=e^{{2\pi ix}}$ . This conjecture was proved to be true by Bergelson, Tao, and Ziegler.^[2]^[3]^[4]

The Inverse Conjecture for Gowers $U^{{d}}[N]$ norm asserts that for any $\delta > 0$ , a finite collection of (d-1)-step nilmanifolds ${\mathcal {M}}_{\delta }$ and constants $c,C$ can be found, so that the following is true. If $N$ is a positive integer and $f\colon [N]\to {\mathbb {C}}$ is bounded in absolute value by 1 and $\Vert f\Vert _{{U^{{d}}[N]}}\geq \delta$ , then there exists a nilmanifold $G/\Gamma \in {\mathcal {M}}_{\delta }$ and a nilsequence $F(g^{n}x)$ where $g\in G,\ x\in G/\Gamma$ and $F\colon G/\Gamma \to {\mathbb {C}}$ bounded by 1 in absolute value and with Lipschitz constant bounded by $C$ such that:

\left|{\frac {1}{N}}\sum _{{n=0}}^{{N-1}}f(n)\overline {F(g^{n}x})\right|\geq c.

This conjecture was proved to be true by Green, Tao, and Ziegler.^[5]^[6] It should be stressed that the appearance of nilsequences in the above statement is necessary. The statement is no longer true if we only consider polynomial phases.

References

↑ Gowers, Timothy (2001). "A new proof of Szemerédi's theorem". Geom. Funct. Anal. 11 (3): 465–588. doi:10.1007/s00039-001-0332-9. MR 1844079.
↑ Bergelson, Vitaly; Tao, Terence; Ziegler, Tamar (2010). "An inverse theorem for the uniformity seminorms associated with the action of ${\mathbb {F}}_{p}^{\infty }$ ". Geom. Funct. Anal. 19 (6): 1539–1596. doi:10.1007/s00039-010-0051-1. MR 2594614.
↑ Tao, Terence; Ziegler, Tamar (2010). "The inverse conjecture for the Gowers norm over finite fields via the correspondence principle". Analysis & PDE. 3 (1): 1–20. doi:10.2140/apde.2010.3.1. MR 2663409.
↑ Tao, Terence; Ziegler, Tamar (2011). "The Inverse Conjecture for the Gowers Norm over Finite Fields in Low Characteristic". Annals of Combinatorics. 16: 121–188. doi:10.1007/s00026-011-0124-3. MR 2948765.
↑ Green, Ben; Tao, Terence; Ziegler, Tamar (2011). "An inverse theorem for the Gowers $U^{{s+1}}[N]$ -norm". Electron. Res. Announc. Math. Sci. 18: 69–90. arXiv:1006.0205. doi:10.3934/era.2011.18.69. MR 2817840.
↑ Green, Ben; Tao, Terence; Ziegler, Tamar (2012). "An inverse theorem for the Gowers $U^{{s+1}}[N]$ -norm". Annals of Mathematics. 176 (2): 1231–1372. arXiv:1009.3998. doi:10.4007/annals.2012.176.2.11. MR 2950773.

Tao, Terence (2012). Higher order Fourier analysis. Graduate Studies in Mathematics. 142. Providence, RI: American Mathematical Society. ISBN 978-0-8218-8986-2. MR 2931680. Zbl 1277.11010.

This article is issued from Wikipedia - version of the 6/30/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.