# Gowers norm

Jump to: navigation, search

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

${\displaystyle \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 ${\displaystyle \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 ${\displaystyle {\tilde {N}}}$ is a large integer, ${\displaystyle 1_{[N]}}$ denotes the indicator function of [N], and ${\displaystyle {\tilde {f}}(x)}$ is equal to ${\displaystyle f(x)}$ for ${\displaystyle x\in [N]}$ and ${\displaystyle 0}$ for all other ${\displaystyle x}$. This definition does not depend on ${\displaystyle {\tilde {N}}}$, as long as ${\displaystyle {\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 ${\displaystyle \mathbb {F} }$ asserts that for any ${\displaystyle \delta >0}$ there exists a constant ${\displaystyle c>0}$ such that for any finite dimensional vector space V over ${\displaystyle \mathbb {F} }$ and any complex valued function ${\displaystyle f}$ on ${\displaystyle V}$, bounded by 1, such that ${\displaystyle \Vert f\Vert _{U^{d}[V]}\geq \delta }$, there exists a polynomial sequence ${\displaystyle P\colon V\to \mathbb {R} /\mathbb {Z} }$ such that

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

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

${\displaystyle \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

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