Gowers norm

From Wikipedia, the free encyclopedia
Jump to: navigation, search
"Uniformity norm" redirects here. For the function field norm, see uniform norm. For unformity 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]


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[edit]

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 i x} . 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^nx) 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^nx}) \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.


  1. ^ 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. 
  2. ^ 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. 
  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. doi:10.2140/apde.2010.3.1. MR 2663409. 
  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. doi:10.1007/s00026-011-0124-3. MR 2948765. 
  5. ^ 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. 
  6. ^ 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.