Hypergraph regularity / Gowers uniformity norms and density-increment arguments: quasirandom decomposition + counting/removal lemmas, and the iterative-density-increase route to Szemerédi-type theorems

Statement

This page covers two historically distinct but mechanistically entangled proof strategies, both due substantially to Gowers, for finding/counting structured configurations (arithmetic progressions, "corners," and more general linear patterns) inside dense sets. They are grouped on one page because Gowers's own route into the hypergraph regularity method *is* a hypergraph generalization of his Gowers-uniformity-norm machinery — the two strands share both a name and, in his hands, a single paper.

Strand 1 — Density increment via Gowers uniformity norms (Roth 1953; Gowers 1998/2001). For $f:\mathbb Z_N\to\mathbb C$, the Gowers $U^d$ norm is $$\|f\|_{U^d(G)}^{2^d} \;=\; \sum_{x,h_1,\dots,h_d\in G}\ \prod_{\omega\in\{0,1\}^d} \mathcal C^{|\omega|} f(x+\omega\cdot h),$$ where $\omega\cdot h=\sum_i \omega_ih_i$ and $\mathcal C$ is complex conjugation applied when $|\omega|$ is odd (Wikipedia, "Gowers norm," fetched 2026-07-02). If $A\subseteq\mathbb Z_N$ has density $\delta=|A|/N$ and $\|\mathbb 1_A-\delta\|_{U^{k-1}}$ is small, a generalized von Neumann theorem shows the count of $k$-term arithmetic progressions in $A$ is close to the count in a random set of density $\delta$ — i.e. $A$ is "Gowers-uniform" and behaves pseudorandomly with respect to $k$-APs. The density-increment strategy (Roth's original argument for $k=3$, generalized by Gowers to all $k$, and reformulated cleanly by Green-Tao) is the contrapositive dichotomy: either $A$ is Gowers-uniform enough that the generalized-von-Neumann count is positive (so $A$ *does* contain a $k$-AP, done), or $A$ has large $U^{k-1}$ norm, which (via the inverse theorem for the Gowers norms) forces $A$ to correlate with a structured object (a low-degree polynomial phase, or — in the sharp integer-segment form — a $(d-1)$-step nilsequence; Green-Tao-Ziegler), which in turn can be used to locate a long sub-progression on which $A$'s density has provably *increased* by an amount depending only on $k$ and $\delta$. Since density is bounded above by $1$, this increment can only happen boundedly many times before the first branch (found a $k$-AP) must fire — this termination-by-bounded-density-increase is the entire proof.

Strand 2 — Hypergraph regularity / counting / removal lemma (Frankl-Rödl; Rödl-Skokan 2004; Nagle-Rödl-Schacht 2006; Gowers 2007; Tao 2006). A $k$-uniform hypergraph regularity lemma generalizes Szemerédi's graph regularity lemma: instead of one flat partition of vertices into quasirandom blocks, one builds a *hierarchical* system of partitions — of vertices, then of pairs (relative to the vertex partition), then of triples (relative to the pair partition), and so on up to $(k-1)$-tuples — such that at every level the parts are regular (edge density is uniform across sub-configurations) relative to the coarser structure below it. Paired with this is a counting lemma: if a $k$-uniform hypergraph is built from such a regular hierarchical partition and the top-level densities are all positive, then it contains (close to) the "expected," pseudorandom number of copies of any fixed small $k$-uniform hypergraph $H$. Regularity lemma + counting lemma together give the hypergraph removal lemma: for a $k$-uniform $h$-vertex hypergraph $H$, for every $\varepsilon>0$ there is $\delta>0$ such that any $k$-uniform $n$-vertex hypergraph $G$ with fewer than $\delta n^h$ copies of $H$ can be made $H$-free by deleting at most $\varepsilon n^k$ hyperedges (Wikipedia, "Hypergraph removal lemma," fetched 2026-07-02; the ordinary graph removal lemma is the $r=2$ special case). This was first proved by Nagle, Rödl, Schacht and Skokan and independently by Gowers (Gowers, arXiv:0710.3032, abstract: "We prove analogues for hypergraphs of Szemerédi's regularity lemma and the associated counting lemma for graphs. As an application, we give the first combinatorial proof of the multidimensional Szemerédi theorem of Furstenberg and Katznelson, and the first proof that provides an explicit bound"). Tao gave a third, self-contained proof (arXiv:math/0503572, "A variant of the hypergraph removal lemma"), and later an information-theoretic/entropy-based route (arXiv:math/0501314).

The bridge from removal lemma to Szemerédi-type theorems. To prove Szemerédi's theorem (no long-AP-free dense subset of $[N]$) or its multidimensional generalization (the corners theorem of Ajtai-Szemerédi is the case $S=\{(0,0),(0,1),(1,0)\}$; the general multidimensional Szemerédi theorem of Furstenberg-Katznelson says any $\delta n^r$-dense subset of $[n]^r$ contains a translated, dilated copy of any fixed finite $S\subset\mathbb Z^r$), one encodes the arithmetic hypothesis as a $(k-1)$-partite, $(k-1)$-uniform hypergraph whose edges record which coordinates lie in $A$; a $k$-term AP in $A$ (or a copy of $S$) becomes a copy of a specific small sub-hypergraph, and "few copies of that sub-hypergraph" (density-$o(1)$ or $o(n^r)$-many, by hypothesis) forces, via the removal lemma, that almost all of $G$ can be deleted with few edges — a contradiction with $A$ being dense, once made precise. This route is purely combinatorial (no ergodic theory), and Gowers's 2007 paper gives it the added feature of an explicit (if astronomically large) quantitative bound, matching but not superseding his own earlier Strand-1 bound for the one-dimensional case.

Facts

- These are two related but non-identical routes to the same family of theorems. Strand 1 (Gowers-norm density increment) is what actually proves the *sharpest known quantitative* one-dimensional Szemerédi bounds (see below); Strand 2 (hypergraph regularity/removal lemma) is the tool of choice for multidimensional and more general linear-pattern statements (corners theorem, multidimensional Szemerédi, systems of linear equations), where it gives the first fully combinatorial (non-ergodic) proofs, but historically with much worse (tower/Ackermann-type) quantitative bounds than Strand 1 achieves in one dimension. - Gowers's own unification. Gowers's route into the hypergraph regularity method (arXiv:0710.3032) explicitly defines "a hypergraph version of the [Gowers uniformity] norm" and builds the hypergraph regularity/counting lemmas on top of it — i.e. in Gowers's hands Strand 2 is literally built as a generalization of Strand 1's machinery, which is why the two are conventionally discussed together (WebSearch-aggregated summary of the Gowers/Nagle-Rödl-Schacht-Skokan history, corroborated by the arXiv:0710.3032 abstract). - Explicit numeric example: van der Waerden numbers. Gowers, "A new proof of Szemerédi's theorem," *Geom. Funct. Anal.* 11 (2001), 465-588, gives (via the Strand-1 density-increment/Gowers-uniformity-norm proof of Szemerédi's theorem) the explicit tower-type bound $$W(k)\ \le\ 2^{2^{2^{2^{2^{k+9}}}}}$$ on the classical van der Waerden number, cited in this wiki's own Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers? page as the current (2026) best known upper bound, unimproved since 2001, and standing against a merely-exponential $\Theta(2^k)$ best known lower bound (Kozik-Shabanov 2016) — i.e. the truth of Erdős's \$500 question ($W(k)^{1/k}\to\infty$?) remains open precisely in the enormous gap this method's tower-type bound leaves open. the exact tower height (5 exponentials before $k+9$) is a direct artifact of how many nested "density increment on a sub-progression, iterate" layers the $U^{k-1}$-norm inverse theorem forces for general $k$. - Bounds have historically been tower/Ackermann-type, and this is intrinsic to the naive hypergraph-regularity route, not an artifact of a specific proof. The hypergraph regularity lemma (like Szemerédi's original graph regularity lemma) requires partitions whose size is bounded only by an iterated-exponential (tower) function of $1/\varepsilon$; for hypergraph regularity at uniformity $\ge 3$ this iteration compounds into genuinely Ackermann-function-type dependence in the removal lemma's $\delta(\varepsilon)$ (Wikipedia, "Hypergraph removal lemma," directly fetched: "The removal lemma involves the inverse Ackermann function in its constants, yielding tower-type bounds"). - 2024 improvement (Strand 1, not Strand 2): quasipolynomial bounds for $k\ge5$. James Leng, Ashwin Sah, Mehtaab Sawhney, "Improved Bounds for Szemerédi's Theorem," arXiv:2402.17995 (28 Feb 2024), prove that for $k\ge5$ there is $c_k>0$ with $$r_k(N)\ \ll\ N\exp(-(\log\log N)^{c_k})$$ (where $r_k(N)$ is the largest size of a $k$-AP-free subset of $[N]$), explicitly "a consequence of recent quasipolynomial bounds on the inverse theorem for the Gowers $U^k$-norm as well as the density increment strategy of Heath-Brown and Szemerédi as reformulated by Green and Tao" (abstract, directly quoted) — i.e. this is a Strand-1 (Gowers-norm/density-increment), not Strand-2, advance, and per Wikipedia's "Hypergraph removal lemma" page it is "the best bound for $k\ge5$ so far," replacing the older Ackermann-type dependence with a merely iterated-logarithmic loss — but this improvement is specific to the *one-dimensional* Szemerédi setting where sharp Gowers-inverse-theorems are available; it has not been ported into the hypergraph-regularity route's tower-type bounds for multidimensional/corners-type statements. - Furstenberg's original 1977 ergodic-theoretic proof of Szemerédi's theorem (and Furstenberg-Katznelson's 1978 multidimensional extension) gives no quantitative bound at all (a standard limitation of ergodic/compactness arguments); the entire point of both Strand 1 (Gowers, 1998 Annals for $k=4$, 2001 GAFA for general $k$) and Strand 2 (Nagle-Rödl-Schacht-Skokan, Gowers 2007) was to give the *first* combinatorial, explicitly-bounded alternatives — Strand 2's stated headline contribution (per the arXiv:0710.3032 abstract) is specifically "the first combinatorial proof of the multidimensional Szemerédi theorem... and the first proof that provides an explicit bound" for that multidimensional case, which Furstenberg-Katznelson's ergodic proof could not supply. - Tao's alternative entropy/information-theoretic proof route (arXiv:math/0501314, search-snippet-sourced title/abstract only) replaces the combinatorial hierarchical-partition bookkeeping of the Rödl-Skokan/Nagle-Rödl-Schacht regularity lemma with Shannon-entropy inequalities, structurally analogous in spirit to the Katz-Tardos entropy-inequality method documented on this wiki's Entropy-inequality method (Katz–Tardos): Shannon-entropy linear programming for the sums-and-entries / distinct-distances problem page (a *different* application of the same general "replace combinatorial counting with entropy of an auxiliary random variable" idea, see Entropy method — Shannon-entropy / coding-theoretic proof technique (Rao, Tao)) — flagged as a genuine, independently-useful alternative derivation of the same removal lemma, not merely an expository variant. - A separate, non-regularity-based technique now dominates the closely-related cap-set problem. For 3-term progressions in $\mathbb F_3^n$ (a finite-field, bounded-uniformity analogue of Roth's theorem), the 2016 Croot-Lev-Pach/Ellenberg-Gijswijt polynomial method / slice rank technique (this wiki's Cap-set problem — max progression-free subset of F_3^n) gave exponentially-better bounds than any regularity-based approach could reach, and is explicitly a *different* proof strategy from both strands on this page — illustrating that hypergraph regularity/Gowers norms, while extremely general, are not always the sharpest available tool once a problem's specific algebraic structure (here, the $\mathbb F_3^n$ vector-space structure) admits a more specialized method.

Technique

WHEN it applies. - Strand 1 (density increment via Gowers norms) applies whenever the target statement has the shape "a subset of an abelian group of density $\ge\delta$ (or, in the coloring form, some color class) must contain a copy of a fixed linear pattern (a $k$-AP, or more generally a system of linear forms satisfying the right non-degeneracy conditions)" and one wants an explicit, ideally good, quantitative bound, not just qualitative existence. It also underlies the Green-Tao theorem on arithmetic progressions in the primes (via a transference principle relative to a pseudorandom majorant) and, per this wiki's Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers?, the current best known upper bound on van der Waerden numbers. - Strand 2 (hypergraph regularity/counting/removal lemma) applies whenever the target statement can be phrased as "few copies of a small pattern $\Rightarrow$ can delete few edges to kill them all," most naturally for multidimensional or higher-uniformity generalizations (corners theorem, multidimensional Szemerédi, systems of linear equations over finite fields — see arXiv:0809.1846 — Ramsey-type hypergraph statements) where a direct one-dimensional Fourier/Gowers-norm argument does not obviously generalize, and where a fully combinatorial (non-ergodic) proof or an explicit-if-poor bound is wanted. - Neither strand is the right tool when a problem's structure admits a sharper specialized method (e.g. the polynomial method for cap sets, Cap-set problem — max progression-free subset of F_3^n) or when only a qualitative/non-quantitative existence statement is needed and ergodic-theoretic compactness arguments (Furstenberg's route) are more economical to invoke.

WHY it works (the mechanism). - *Density increment (Strand 1)*: the generalized von Neumann theorem reduces "count copies of the pattern" to a multilinear average controlled by a Gowers uniformity norm; the inverse theorem for the Gowers norms is the crucial structural fact that large $U^{d}$-norm is not merely "some" obstruction but is *equivalent to* correlation with a specific, structured class of objects (polynomial phases in finite fields, or nilsequences over $[N]$) — this converts "no progressions found" into "found exploitable structure," and that structure is exactly what lets you locate a sub-progression with strictly higher density. The proof terminates because density $\in[0,1]$ is bounded, so only finitely many increments (each losing a controlled amount in progression length, gaining a controlled amount in density) are possible — a compactness-by-discretization argument, quantified. - *Hypergraph regularity (Strand 2)*: the counting lemma is the higher-uniformity analogue of the graph fact "quasirandom bipartite graphs of positive density contain the expected number of any fixed small subgraph." Building the hierarchical regular partition (vertices, then pairs relative to vertices, then triples relative to pairs, ...) is what makes "quasirandom" a meaningful, checkable, *inductively achievable* notion at each higher uniformity level — each level's regularity is defined and exploited relative to the coarser structure below it, which is precisely the technical innovation Rödl-Skokan/Nagle-Rödl-Schacht needed beyond a naive flat generalization of Szemerédi's original (graph, $k=2$) regularity lemma (this hierarchical relativization is, per available sources, "the first correct definition" of hypergraph regularity — earlier attempts by Frankl-Rödl and Chung on 3-uniform hypergraphs did not fully generalize). Once the counting lemma holds, the removal lemma is an immediate consequence: too few copies of $H$ forces every part of the regular partition supporting a copy of $H$ to itself be sparse or irregular, and both sparse and irregular parts can be removed while touching only $o(n^k)$ edges. - How the two strands connect to Szemerédi/Erdős-type problems in practice: (1) reduce the arithmetic/combinatorial hypothesis to either (a) a statement about the $U^{k-1}$-norm of an indicator function (Strand 1) or (b) a statement about copy-counts in an auxiliary $(k-1)$-uniform hypergraph (Strand 2); (2) invoke the relevant inverse/counting theorem to convert "no structure found" into either a density increment (Strand 1) or a removable-sparse-hypergraph conclusion (Strand 2); (3) iterate/conclude. The choice between strands is largely dictated by dimensionality (one-dimensional AP statements favor Strand 1 for sharper bounds; multidimensional/general-linear-pattern statements favor Strand 2 for combinatorial tractability) and by how much one cares about the quantitative bound (Strand 1's bounds are far better where both apply, as the $k\ge5$ Leng-Sah-Sawhney quasipolynomial bound versus Strand 2's still-Ackermann-type bounds illustrates).

Related

- Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers? — Erdős's \$500 question on whether $W(k)^{1/k}\to\infty$ for van der Waerden numbers; the current (2026) best known upper bound $W(k)\le2^{2^{2^{2^{2^{k+9}}}}}$ is exactly Gowers's 2001 Strand-1 density-increment/Gowers-uniformity-norm proof of Szemerédi's theorem, unimproved since 2001 and the direct source of this page's headline numeric example. - Erdős #500 — Turán density of the tetrahedron $K_4^{3}$ — the Turán density of the tetrahedron $K_4^{(3)}$, a 3-uniform hypergraph extremal problem living in the same technical universe (dense hypergraph structure, quasirandomness) as this page's Strand 2, but the hypergraph regularity method's counting/removal lemmas give only *qualitative* consequences here (e.g. stability-type statements), not the *exact* Turán density itself — the sharpest partial progress on that problem instead comes from flag algebras, a different (semidefinite-programming-based) technique; included to flag the boundary of what hypergraph regularity can and cannot resolve. - Cap-set problem — max progression-free subset of F_3^n — 3-term progressions in $\mathbb F_3^n$; solved not by this page's techniques but by the unrelated 2016 polynomial method/slice rank, illustrating a case where a more specialized algebraic technique beat any regularity-based bound. - Fox–Hunter (2026) — three-color van der Waerden numbers $w(k;3)$ grow super-exponentially in $k$ — Fox-Hunter's 2026 super-exponential lower bound for $w(k;3)$ uses a different technique lineage (sparse Behrend-type hitting sets plus the Lovász local lemma, iterated), but sits in the same broader Ramsey/van-der-Waerden landscape whose current *upper* bound is supplied by this page's Strand 1. - Entropy-inequality method (Katz–Tardos): Shannon-entropy linear programming for the sums-and-entries / distinct-distances problem and Entropy method — Shannon-entropy / coding-theoretic proof technique (Rao, Tao) — Tao's alternative entropy-based proof of the hypergraph removal lemma (arXiv:math/0501314) replaces this page's combinatorial hierarchical-partition machinery with Shannon-entropy inequalities, the same general "entropy in place of counting" idea documented on those pages in a different application (the Katz-Tardos distinct-distances bound). - Polynomial method / slice rank (Croot-Lev-Pach, Ellenberg-Gijswijt) — the general family of algebraic (non-regularity) techniques, of which the cap-set-problem's slice-rank method is one instance, that can outperform hypergraph regularity on problems with enough algebraic structure.