Gowers norm

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]

DefinitionEdit

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

 

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  , where   is a large integer,   denotes the indicator function of [N], and   is equal to   for   and   for all other  . This definition does not depend on  , as long as  .

Inverse conjecturesEdit

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   asserts that for any   there exists a constant   such that for any finite-dimensional vector space V over   and any complex-valued function   on  , bounded by 1, such that  , there exists a polynomial sequence   such that

 

where  . This conjecture was proved to be true by Bergelson, Tao, and Ziegler.[3][4][5]

The Inverse Conjecture for Gowers   norm asserts that for any  , a finite collection of (d − 1)-step nilmanifolds   and constants   can be found, so that the following is true. If   is a positive integer and   is bounded in absolute value by 1 and  , then there exists a nilmanifold   and a nilsequence   where   and   bounded by 1 in absolute value and with Lipschitz constant bounded by   such that:

 

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.

ReferencesEdit

  1. ^ Hartnett, Kevin. "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". Geom. Funct. Anal. 11 (3): 465–588. doi:10.1007/s00039-001-0332-9. MR 1844079. CS1 maint: discouraged parameter (link)
  3. ^ Bergelson, Vitaly; Tao, Terence; Ziegler, Tamar (2010). "An inverse theorem for the uniformity seminorms associated with the action of  ". Geom. Funct. Anal. 19 (6): 1539–1596. arXiv:0901.2602. doi:10.1007/s00039-010-0051-1. MR 2594614.
  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.
  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.
  6. ^ Green, Ben; Tao, Terence; Ziegler, Tamar (2011). "An inverse theorem for the Gowers  -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  -norm". Annals of Mathematics. 176 (2): 1231–1372. arXiv:1009.3998. doi:10.4007/annals.2012.176.2.11. MR 2950773.