Gowers norms
Generated by GPT-5-miniExpansion Funnel Raw 1 → Dedup 0 → NER 0 → Enqueued 0
| Gowers norms | |
|---|---|
| Name | Gowers norms |
| Field | Additive combinatorics, Harmonic analysis, Theoretical computer science |
| Introduced | 1998 |
| Introduced by | Timothy Gowers |
| Notation | U^k |
Gowers norms are a family of functional seminorms introduced to quantify higher-order uniformity of functions on finite abelian groups and intervals. They play a central role in the study of arithmetic progressions, quantitative versions of Szemerédi's theorem, and structural decomposition problems in additive combinatorics. Their definition, algebraic properties, and inverse theorems link deep work by Timothy Gowers with developments associated to Ben Green, Terence Tao, Jean Bourgain, Imre Ruzsa, Endre Szemerédi, and others.
Definition
For an integer k ≥ 2 and a function f on a finite abelian group G or on an interval [N], the U^k-seminorm is defined by averaging 2^k-fold multiplicative derivatives. In the group setting this uses the Haar measure on G and iterated differences; in the interval setting one passes to cyclic groups or uses cutoff functions as in the approaches of Green and Tao. The definition generalizes notions that appeared in work of Szemerédi and Roth and refines earlier uses of exponential sums in the work of Hardy, Littlewood, Weyl, and Vinogradov. The U^2-case coincides with a quantity controlled by Fourier analysis as in the theorems of Parseval and Plancherel and as used by Kátai, Davenport, and Heilbronn.
Properties
Gowers norms satisfy several algebraic and analytic properties that mirror those of L^p-norms but are tailored to additive structure. They are seminorms for k ≥ 2, obey a generalized Cauchy–Schwarz inequality that underpins iterative energy-increment arguments used by Gowers and Szemerédi, and are monotone in k. The U^2-norm is equivalent to the L^4-norm of the Fourier transform, connecting to results of Bochner, Wiener, and Kolmogorov on spectral concentration. The inverse theory for U^k connects to nilmanifolds and ergodic-theoretic structures appearing in the works of Host, Kra, Ziegler, Furstenberg, and Bergelson. Stability and regularity lemmas using these norms echo themes from Szemerédi's regularity lemma and structural decompositions employed by Green, Ruzsa, Sanders, and Tao.
Examples and Computations
Basic examples include characters and polynomial phases: additive characters over finite fields have maximal U^k-norm, while random functions exhibit small U^k-norm with high probability as in probabilistic method arguments of Erdős and Rényi. Polynomial phase functions over Z/NZ of degree < k have large U^k and small U^{k+1}, reflecting classical polynomial-exponential sum estimates by Weyl and Van der Corput. Concrete computations often use discrete Fourier analysis as in work of Ingham and Hardy–Littlewood or combinatorial counting methods reminiscent of those in Roth's theorem and Behrend constructions. Explicit bounds and algorithmic estimations were developed further in papers by Green, Tao, Gowers, and Lovett.
Connections to Uniformity and Arithmetic Progressions
Small U^k-norms quantify lack of structure and imply counting lemmas for linear configurations, generalizing Roth's theorem and Szemerédi's theorem on arithmetic progressions addressed by Szemerédi, van der Waerden, and Furstenberg. Gowers used these norms to give a new proof of Szemerédi's theorem, linking uniformity to the count of k-term arithmetic progressions via energy increment strategies related to work by Roth, Behrend, and Bloom. The link to ergodic theory via the Host–Kra and Ziegler structure theorems shows how nilmanifolds and nilsequences discovered in the ergodic context by Leibman, Bergelson, and Lesigne arise naturally as obstructions to uniformity measured by U^k.
Inverse Theorems
Inverse theorems characterize functions with large U^k-norms: for U^2 this is classical Fourier structure described by characters and large Fourier coefficients as in Wiener’s and Rudin’s results; for higher k the structure is given by correlations with nilsequences and polynomial phases, a view developed in landmark inverse theorems by Green, Tao, and Ziegler building on ideas from Host, Kra, and Bergelson. These theorems connect to the theory of nilmanifolds by Mal'cev and to quantitative equidistribution results of Leibman and Green–Tao–Ziegler, and have parallels to structural dichotomies used in the work of Szemerédi, Balog, Szemerédi, and Freiman.
Applications in Additive Combinatorics and Theoretical Computer Science
Gowers norms underpin quantitative bounds in additive combinatorics, including new proofs and bounds for Szemerédi-type theorems by Gowers, Green, and Tao, and inform results on sum-product phenomena studied by Erdős, Szemerédi, Bourgain, and Garaev. In theoretical computer science they appear in analyses of property testing, pseudorandomness, and probabilistically checkable proofs where notions of uniformity and low-degree tests connect to PCP theorems by Arora, Lund, Safra, and Sudan. Algorithmic consequences include deterministic and randomized algorithms for detecting structured patterns, drawing on spectral methods from Goldreich, Goldwasser, Levin, and hardness results related to complexity classes studied by Cook, Karp, and Arora.
Variants and Generalizations
Variants include weighted and localized Gowers norms adapted to finite fields and intervals, cube norm formulations used in ergodic theory by Host and Kra, and continuous analogues on nilmanifolds and compact abelian groups linked to Pontryagin duality and Haar measures as in the work of Weil. Generalizations interact with higher-order Fourier analysis developed by Green, Tao, Ziegler, and by Lovett, Meshulam, and Samorodnitsky, and with algebraic notions in models studied by Hrushovski and model-theoretic approaches to additive combinatorics inspired by work of Pillay and Zilber.