Gowers norm

☆ Save On Wikipedia ↗

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

Definition

Let f {\displaystyle f} {\displaystyle f} be a complex-valued function on a finite abelian group G {\displaystyle G} {\displaystyle G} and let J {\displaystyle J} {\displaystyle J} denote complex conjugation. The Gowers d {\displaystyle d} {\displaystyle d}-norm is

‖ f ‖ U d ( G ) 2 d = ∑ x , h 1 , … , h d ∈ G ∏ ω 1 , … , ω d ∈ { 0 , 1 } J ω 1 + ⋯ + ω d f ( x + h 1 ω 1 + ⋯ + h d ω d )   . {\displaystyle \Vert f\Vert _{U^{d}(G)}^{2^{d}}=\sum _{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)\ .} {\displaystyle \Vert f\Vert _{U^{d}(G)}^{2^{d}}=\sum _{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 {\displaystyle [N]={0,1,2,...,N-1}} {\displaystyle [N]={0,1,2,...,N-1}}, where N is a positive integer. In this context, the uniformity norm is given as ‖ f ‖ U d [ N ] = ‖ f ~ ‖ U d ( Z / N ~ Z ) / ‖ 1 [ N ] ‖ U d ( Z / N ~ Z ) {\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} )}} {\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 N ~ {\displaystyle {\tilde {N}}} {\displaystyle {\tilde {N}}} is a large integer, 1 [ N ] {\displaystyle 1_{[N]}} {\displaystyle 1_{[N]}} denotes the indicator function of [N], and f ~ ( x ) {\displaystyle {\tilde {f}}(x)} {\displaystyle {\tilde {f}}(x)} is equal to f ( x ) {\displaystyle f(x)} {\displaystyle f(x)} for x ∈ [ N ] {\displaystyle x\in [N]} {\displaystyle x\in [N]} and 0 {\displaystyle 0} {\displaystyle 0} for all other x {\displaystyle x} {\displaystyle x}. This definition does not depend on N ~ {\displaystyle {\tilde {N}}} {\displaystyle {\tilde {N}}}, as long as N ~ > 2 d N {\displaystyle {\tilde {N}}>2^{d}N} {\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 F {\displaystyle \mathbb {F} } {\displaystyle \mathbb {F} } asserts that for any δ > 0 {\displaystyle \delta >0} {\displaystyle \delta >0} there exists a constant c > 0 {\displaystyle c>0} {\displaystyle c>0} such that for any finite-dimensional vector space V over F {\displaystyle \mathbb {F} } {\displaystyle \mathbb {F} } and any complex-valued function f {\displaystyle f} {\displaystyle f} on V {\displaystyle V} {\displaystyle V}, bounded by 1, such that ‖ f ‖ U d [ V ] ≥ δ {\displaystyle \Vert f\Vert _{U^{d}[V]}\geq \delta } {\displaystyle \Vert f\Vert _{U^{d}[V]}\geq \delta }, there exists a polynomial sequence P : V → R / Z {\displaystyle P\colon V\to \mathbb {R} /\mathbb {Z} } {\displaystyle P\colon V\to \mathbb {R} /\mathbb {Z} } such that

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

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

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

| 1 N ∑ n = 0 N − 1 f ( n ) F ( g n x ¯ ) | ≥ c . {\displaystyle \left|{\frac {1}{N}}\sum _{n=0}^{N-1}f(n){\overline {F(g^{n}x}})\right|\geq c.} {\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.[6][7] 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. Hartnett, Kevin (25 November 2019). "Mathematicians Catch a Pattern by Figuring Out How to Avoid It". Quanta Magazine. Retrieved 2019-11-26.
  2. Gowers, Timothy (2001). "A new proof of Szemerédi's theorem". Geometric & Functional Analysis. 11 (3): 465–588. doi:10.1007/s00039-001-0332-9. MR 1844079. S2CID 124324198.
  3. Bergelson, Vitaly; Tao, Terence; Ziegler, Tamar (2010). "An inverse theorem for the uniformity seminorms associated with the action of F p ∞ {\displaystyle \mathbb {F} _{p}^{\infty }} {\displaystyle \mathbb {F} _{p}^{\infty }}". Geometric & Functional Analysis. 19 (6): 1539–1596. arXiv:0901.2602. doi:10.1007/s00039-010-0051-1. MR 2594614. S2CID 10875469.
  4. 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. arXiv:0810.5527. doi:10.2140/apde.2010.3.1. MR 2663409. S2CID 16850505.
  5. Tao, Terence; Ziegler, Tamar (2011). "The Inverse Conjecture for the Gowers Norm over Finite Fields in Low Characteristic". Annals of Combinatorics. 16: 121–188. arXiv:1101.1469. doi:10.1007/s00026-011-0124-3. MR 2948765. S2CID 253591592.
  6. Green, Ben; Tao, Terence; Ziegler, Tamar (2011). "An inverse theorem for the Gowers U s + 1 [ N ] {\displaystyle U^{s+1}[N]} {\displaystyle 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.
  7. Green, Ben; Tao, Terence; Ziegler, Tamar (2012). "An inverse theorem for the Gowers U s + 1 [ N ] {\displaystyle U^{s+1}[N]} {\displaystyle 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. S2CID 119588323.