Gowers norm explained

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 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 ^{2 ^{d}} _{U ^{d(G)}} = \sum _{x,h _{1,\ldots,h} _{d} \in G} \prod _{\omega _{1,\ldots,\omega} _{d} \in \{ 0 , 1 \} } J^ f\left(\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(Z/\tilde{N}} Z )}/\Vert 1 _{[N]} \Vert _{U ^{d(Z/\tilde{N}} 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.

F asserts that for any \delta > 0 there exists a constant c > 0 such that for any finite-dimensional vector space V over 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 R / Z such that \left| (1)/(|V|) \sum _{x} f(x) e \left( - P(x) \right) \right| \geq c ,

where

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

The Inverse Conjecture for Gowers

U ^{d} [N] norm asserts that for any \delta > 0 , a finite collection of (d − 1)-step nilmanifolds l{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 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 l{M} _{\delta} and a nilsequence F(g ^{nx)} where g \in G, x \in G/\Gamma and F\colon G/\Gamma \to C bounded by 1 in absolute value and with Lipschitz constant bounded by C such that:\left| (1)/(N) \sum ^{N -1} _{n =0} f(n) \overline{ F(g ^{nx})} \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

• Book: Tao, Terence . Terence Tao

. 1277.11010 . Terence Tao . Higher order Fourier analysis . . 142 . Providence, RI . . 2012 . 978-0-8218-8986-2 . 2931680 .

Notes and References

1. Web site: Mathematicians Catch a Pattern by Figuring Out How to Avoid It. Hartnett. Kevin. Quanta Magazine. 2019-11-26.
2. Timothy Gowers. Timothy. Gowers. A new proof of Szemerédi's theorem. Geometric & Functional Analysis. 11. 3. 465–588. 2001. 1844079. 10.1007/s00039-001-0332-9. 124324198 .
3. Bergelson . Vitaly . Tao . Terence . Terence Tao . Ziegler . Tamar . Tamar Ziegler . An inverse theorem for the uniformity seminorms associated with the action of F ^{inf ty} _{p} . 2594614 . . 2010 . 19 . 6 . 1539–1596 . 10.1007/s00039-010-0051-1. 0901.2602 . 10875469 .
4. Tao . Terence . Terence Tao . Ziegler . Tamar . Tamar Ziegler . The inverse conjecture for the Gowers norm over finite fields via the correspondence principle . 2010 . Analysis & PDE . 3 . 1 . 1–20 . 10.2140/apde.2010.3.1 . 2663409. 0810.5527 . 16850505 .
5. 10.1007/s00026-011-0124-3. The Inverse Conjecture for the Gowers Norm over Finite Fields in Low Characteristic. Annals of Combinatorics. 16. 121–188. 2011. Tao . Terence . Terence Tao. Ziegler . Tamar . Tamar Ziegler. 2948765. 1101.1469. 253591592.
6. Green . Ben . Ben Green (mathematician). Tao . Terence . Terence Tao. Ziegler . Tamar . Tamar Ziegler. An inverse theorem for the Gowers U ^{s+1} [N] -norm. Electron. Res. Announc. Math. Sci.. 18. 2011. 69–90. 10.3934/era.2011.18.69. 2817840. 1006.0205.
7. 10.4007/annals.2012.176.2.11. An inverse theorem for the Gowers U ^{s+1} [N] -norm. Annals of Mathematics. 176. 2. 1231–1372. 2012. Green . Ben . Ben Green (mathematician). Tao . Terence . Terence Tao. Ziegler . Tamar . Tamar Ziegler. 2950773. 1009.3998. 119588323.