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]
Definition
Let be a complex-valued function on a finite abelian group and let denote complex conjugation. The Gowers -norm is
Gowers norms are also defined for complex-valued functions f on a segment , 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 .
![{\displaystyle [N]={0,1,2,...,N-1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/75940aea8f124adb388d1a31bd89eb1a7d36303b)
![{\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} )}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b6cd15f8dc7945616268af6cecc3ab2faef640ec)
![{\displaystyle 1_{[N]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ec318d1f8ac1498f3210258a16e6a10f55b91653)
![{\displaystyle x\in [N]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/84b65f9d66d19fbfca3d4b143e6e5cfaf8da81b0)
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 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
![{\displaystyle \Vert f\Vert _{U^{d}[V]}\geq \delta }](https://wikimedia.org/api/rest_v1/media/math/render/svg/d63474d408ea09584d3d55214ab87086ba9b3357)
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:
![{\displaystyle U^{d}[N]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b690a44c49dc548a5d4975f3085f7a7a64a6ff1f)
![{\displaystyle f\colon [N]\to \mathbb {C} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/2f1c14c0f266f525fd7eb8b1bdc7ed19702e5779)
![{\displaystyle \Vert f\Vert _{U^{d}[N]}\geq \delta }](https://wikimedia.org/api/rest_v1/media/math/render/svg/7e5b476f9d536fdd68a1c58788ef37f3078ed888)
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
- ^ Hartnett, Kevin (25 November 2019). "Mathematicians Catch a Pattern by Figuring Out How to Avoid It". Quanta Magazine. Retrieved 2019-11-26.
- ^ 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.
- ^ Bergelson, Vitaly; Tao, Terence; Ziegler, Tamar (2010). "An inverse theorem for the uniformity seminorms associated with the action of ". Geometric & Functional Analysis. 19 (6): 1539–1596. arXiv:0901.2602. doi:10.1007/s00039-010-0051-1. MR 2594614. S2CID 10875469.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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. S2CID 119588323.
![{\displaystyle U^{s+1}[N]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7cc69afe2ed4d76706b582f8032485c276c11a74)
- Tao, Terence (2012). Higher order Fourier analysis. Graduate Studies in Mathematics. Vol. 142. Providence, RI: American Mathematical Society. ISBN 978-0-8218-8986-2. MR 2931680. Zbl 1277.11010.