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 [math]\displaystyle{ f }[/math] be a complex-valued function on a finite abelian group [math]\displaystyle{ G }[/math] and let [math]\displaystyle{ J }[/math] denote complex conjugation. The Gowers [math]\displaystyle{ d }[/math]-norm is
- [math]\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) \ . }[/math]
Gowers norms are also defined for complex-valued functions f on a segment [math]\displaystyle{ [N] = {0, 1, 2, ..., N - 1} }[/math], where N is a positive integer. In this context, the uniformity norm is given as [math]\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})} }[/math], where [math]\displaystyle{ \tilde N }[/math] is a large integer, [math]\displaystyle{ 1_{[N]} }[/math] denotes the indicator function of [N], and [math]\displaystyle{ \tilde f(x) }[/math] is equal to [math]\displaystyle{ f(x) }[/math] for [math]\displaystyle{ x \in [N] }[/math] and [math]\displaystyle{ 0 }[/math] for all other [math]\displaystyle{ x }[/math]. This definition does not depend on [math]\displaystyle{ \tilde N }[/math], as long as [math]\displaystyle{ \tilde N \gt 2^d N }[/math].
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 [math]\displaystyle{ \mathbb F }[/math] asserts that for any [math]\displaystyle{ \delta \gt 0 }[/math] there exists a constant [math]\displaystyle{ c \gt 0 }[/math] such that for any finite-dimensional vector space V over [math]\displaystyle{ \mathbb F }[/math] and any complex-valued function [math]\displaystyle{ f }[/math] on [math]\displaystyle{ V }[/math], bounded by 1, such that [math]\displaystyle{ \Vert f \Vert_{U^{d}[V]} \geq \delta }[/math], there exists a polynomial sequence [math]\displaystyle{ P \colon V \to \mathbb{R}/\mathbb{Z} }[/math] such that
- [math]\displaystyle{ \left| \frac{1}{|V|} \sum_{x \in V} f(x) e \left( -P(x) \right) \right| \geq c , }[/math]
where [math]\displaystyle{ e(x) := e^{2 \pi i x} }[/math]. This conjecture was proved to be true by Bergelson, Tao, and Ziegler.[3][4][5]
The Inverse Conjecture for Gowers [math]\displaystyle{ U^{d}[N] }[/math] norm asserts that for any [math]\displaystyle{ \delta \gt 0 }[/math], a finite collection of (d − 1)-step nilmanifolds [math]\displaystyle{ \mathcal{M}_\delta }[/math] and constants [math]\displaystyle{ c, C }[/math] can be found, so that the following is true. If [math]\displaystyle{ N }[/math] is a positive integer and [math]\displaystyle{ f\colon [N]\to \mathbb{C} }[/math] is bounded in absolute value by 1 and [math]\displaystyle{ \Vert f \Vert_{U^{d}[N]} \geq \delta }[/math], then there exists a nilmanifold [math]\displaystyle{ G/\Gamma \in \mathcal{M}_\delta }[/math] and a nilsequence [math]\displaystyle{ F(g^nx) }[/math] where [math]\displaystyle{ g \in G,\ x \in G/\Gamma }[/math] and [math]\displaystyle{ F\colon G/\Gamma \to \mathbb{C} }[/math] bounded by 1 in absolute value and with Lipschitz constant bounded by [math]\displaystyle{ C }[/math] such that:
- [math]\displaystyle{ \left| \frac{1}{N} \sum_{n =0}^{N-1} f(n) \overline{ F(g^nx}) \right| \geq c . }[/math]
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. "Mathematicians Catch a Pattern by Figuring Out How to Avoid It". https://www.quantamagazine.org/mathematicians-catch-a-pattern-by-figuring-out-how-to-avoid-it-20191125/.
- ↑ 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. http://www.dpmms.cam.ac.uk/~wtg10/sz898.dvi.
- ↑ Bergelson, Vitaly; Tao, Terence; Ziegler, Tamar (2010). "An inverse theorem for the uniformity seminorms associated with the action of [math]\displaystyle{ \mathbb{F}_p^\infty }[/math]". Geometric & Functional Analysis 19 (6): 1539–1596. doi:10.1007/s00039-010-0051-1.
- ↑ 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.
- ↑ "The Inverse Conjecture for the Gowers Norm over Finite Fields in Low Characteristic". Annals of Combinatorics 16: 121–188. 2011. doi:10.1007/s00026-011-0124-3.
- ↑ Green, Ben (2011). "An inverse theorem for the Gowers [math]\displaystyle{ U^{s+1}[N] }[/math]-norm". Electron. Res. Announc. Math. Sci. 18: 69–90. doi:10.3934/era.2011.18.69.
- ↑ "An inverse theorem for the Gowers [math]\displaystyle{ U^{s+1}[N] }[/math]-norm". Annals of Mathematics 176 (2): 1231–1372. 2012. doi:10.4007/annals.2012.176.2.11.
- Tao, Terence (2012). Higher order Fourier analysis. Graduate Studies in Mathematics. 142. Providence, RI: American Mathematical Society. ISBN 978-0-8218-8986-2. http://terrytao.wordpress.com/books/higher-order-fourier-analysis/.
![]() | Original source: https://en.wikipedia.org/wiki/Gowers norm.
Read more |