Gowers (2001) — explicit tower-type upper bound on van der Waerden numbers W(k), via a new Fourier-analytic proof of Szemerédi's theorem

Statement

Van der Waerden's theorem (1927): for every $r,k\in\mathbb N$ there is a least $N=W(r,k)$ such that every $r$-colouring of $\{1,\dots,N\}$ contains a monochromatic $k$-term arithmetic progression. Write $W(k):=W(2,k)$ for the diagonal 2-colour case. Van der Waerden's original double-induction proof ("van der Waerden's trick") shows $W(r,k)$ exists but gives a bound so weak it is not primitive recursive — it grows faster than any fixed-height tower of exponentials, indeed faster than the Ackermann function.

The problem this page is about: replace that non-elementary bound with an *explicit, tower-of-fixed-height* upper bound on $W(k)$ — equivalently, prove a fully quantitative (effective, explicit-bound) version of Szemerédi's theorem, the density statement that subsumes van der Waerden's theorem:

$$\text{for every } k\in\mathbb N,\ \delta\in(0,1],\ \exists\, N(k,\delta):\ \text{every } A\subseteq\{1,\dots,N\},\ N\ge N(k,\delta),\ |A|\ge\delta N \text{ contains a } k\text{-AP}.$$

Since a 2-colouring of $\{1,\dots,N\}$ always has a colour class of density $\ge 1/2$, any explicit bound $N(k,1/2)$ on the Szemerédi threshold *immediately* yields an explicit bound $W(k)\le N(k,1/2)$ on the van der Waerden number by the pigeonhole principle — so "give an explicit quantitative Szemerédi theorem" and "give an explicit tower-type upper bound on $W(k)$" are the same problem.

Facts

- Origin of the underlying difficulty: van der Waerden's 1927 proof (B. L. van der Waerden, "Beweis einer Baudetschen Vermutung," *Nieuw Arch. Wisk.* 15 (1927), 212–216) is a nested multiple induction whose bound is not primitive recursive in $k$ (Wikipedia, "Van der Waerden number," fetched). - First primitive-recursive bound: Saharon Shelah, "Primitive recursive bounds for van der Waerden numbers," *J. Amer. Math. Soc.* 1 (1988), 683–697 — a genuinely different combinatorial argument (via a primitive-recursive bound on the Hales–Jewett numbers) that puts $W(r,k)$ into the Grzegorczyk class $E^5$. This was a landmark complexity-class improvement, but it is *not* an explicit tower-of-fixed-height formula — the function is still astronomically larger than any bound of the shape "tower of $O(1)$ exponentials with $k$ only at the very top" (Wikipedia, "Van der Waerden number," fetched). - Furstenberg's 1977 ergodic-theoretic proof of Szemerédi's theorem (via the Furstenberg multiple-recurrence theorem) reproves the qualitative statement but is completely ineffective — it gives no bound on $N(k,\delta)$ at all (Wikipedia, "Szemerédi's theorem," fetched). - The theorem solved here: W. T. Gowers, "A new proof of Szemerédi's theorem," *Geometric and Functional Analysis (GAFA)* 11(3) (2001), 465–588, doi:10.1007/s00039-001-0332-9. Gowers gives the first genuinely *explicit* bound for every $k$ (previous explicit bounds existed only for $k=3$, Roth 1953, and $k=4$, Gowers's own earlier 1998 GAFA paper). The resulting van der Waerden bound, quoted directly by this wiki's sibling page on the still-open Erdős #138 (erdosproblems.com/138, direct fetch 2026-07-02): $$W(k) \;\le\; 2^{2^{2^{2^{2^{k+9}}}}}$$ and, in the general $r$-colour form (Wikipedia, "Van der Waerden number," fetched): $$W(r,k) \;\le\; 2^{2^{r^{2^{2^{k+9}}}}}.$$ This is a tower of fixed height (six exponentials, independent of $k$) with $k$ (or $r$) appearing only near the top — qualitatively far more explicit and dramatically more concrete than Shelah's $E^5$ bound, even though both are, in the crudest complexity-class sense, "tower-type." - Equivalent statement in density form: Gowers proves $r_k(N)\le CN/(\log\log N)^{c_k}$ where $r_k(N)$ is the largest size of a $k$-AP-free subset of $\{1,\dots,N\}$ and $c_k$ is doubly-exponentially small in $k$ (specifically of shape $2^{-2^{k+9}}$) — Wikipedia, "Szemerédi's theorem," fetched, quoting this exact bound shape. - Status today (2026): Gowers's bound remains the best known general upper bound on $W(k)$ — unimproved for 25 years, per this wiki's own directly-fetched erdosproblems.com/138 page (fetched 2026-07-02): "This has not been improved for the general diagonal $W(k)$ since 2001." The matching lower bound is only $W(k)\gg 2^k$ (Kozik–Shabanov 2016, arXiv:1409.6921, refining Szabó 1990 and Berlekamp 1968), so an enormous gap — exponential vs. tower-of-six — separates what's known, and closing any part of that gap is precisely the content of the still-open, \$500 Erdős problem Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers? ($W(k)^{1/k}\to\infty$?). - Partial refinement since 2001, but not to the $k$-dependence: James Leng, Ashwin Sah, Mehtaab Sawhney, "Improved Bounds for Szemerédi's Theorem," arXiv:2402.17995 (2024), prove $r_k(N)\ll_k N\exp(-(\log\log N)^{c_k})$ for every fixed $k\ge5$ — the first improvement to the *shape* (in $N$) of Gowers's bound since 2001, via quasipolynomial inverse theorems for the Gowers $U^{s+1}[N]$-norm (companion paper arXiv:2402.17994). This sharpens the double-logarithmic decay rate for each fixed $k$ but does not (per available sourcing) improve the *tower height in $k$* that determines $W(k)$ itself — Gowers's 2001 formula remains the citation for the actual van der Waerden bound. - Do not conflate with Gowers's later, separate proof: Gowers also gave an independent hypergraph-regularity proof of the (harder, multidimensional) Szemerédi theorem — "Hypergraph regularity and the multidimensional Szemerédi theorem," *Ann. of Math.* 166 (2007), 897–946 (independently, Nagle–Rödl–Schacht–Skokan and Rödl–Skokan gave essentially the same hypergraph-regularity route around the same time). That 2007 route is a *different* technique (regularity/counting lemmas for hypergraphs, not uniformity norms) and gives *much worse*, non-tower-of-fixed-height bounds (regularity-lemma-type, closer to Ackermannian) — it is not the source of the good $W(k)$ bound. The tower bound documented on this page comes specifically from the 2001 Fourier-analytic paper.

Solution

Answer: YES — Szemerédi's theorem admits an explicit, tower-of-fixed-height (six exponentials) bound, giving $W(k)\le 2^{2^{2^{2^{2^{k+9}}}}}$, still the best known general upper bound on the van der Waerden numbers as of 2026 (Gowers, GAFA 2001).

The transferable technique — attack a density/Ramsey statement not by direct combinatorics but by (1) defining a norm that certifies pseudorandomness, (2) proving a "counting" theorem that random-like sets have the expected number of patterns, (3) proving an inverse theorem that non-random-like sets must correlate with algebraic structure, and (4) iterating a density-increment argument on that structure until either the pattern is found or the density is pushed above 1:

1. Introduce a norm that measures "how random-like" a set/function is with respect to the target pattern. Gowers defines the uniformity norms $U^d$ on functions $f:\mathbb Z_N\to\mathbb C$ (or on $\{1,\dots,N\}$), designed so that $\|f\|_{U^d}$ being small is exactly the right notion of "pseudorandom enough to contain the expected count of $(d{+}1)$-term APs." This reframes "does $A$ contain a $k$-AP" as a question about a single scalar quantity attached to $1_A$, rather than a direct search.

2. Prove a generalized von Neumann theorem: low uniformity norm $\Rightarrow$ correct AP-count. If $\|1_A-\delta\|_{U^{k-1}}$ is small, the number of $k$-APs inside $A$ is (up to lower-order error) the same as in a random set of density $\delta$ — i.e. essentially $\delta^k N^2$, which is positive for $N$ large. This is the "easy half": pseudorandom sets automatically contain the pattern.

3. Prove an inverse theorem for the uniformity norms: large uniformity norm $\Rightarrow$ structure. This is the hard, technical heart of the paper. If $A$ has *no* $k$-AP, then $1_A-\delta$ must have large $U^{k-1}$ norm (else step 2 would find one) — and Gowers shows a function with large $U^{k-1}$ norm must *correlate* with a lower-degree structured object (for the base case, a linear/Fourier phase; in general, built up inductively). Extracting this correlation quantitatively is where Gowers proves and uses a sharpened, quantitative Balog–Szemerédi–Gowers theorem (his own strengthening of a prior qualitative result of Balog–Szemerédi) together with Freiman's theorem on sets of small doubling, to pass from "many additive quadruples agree" to "genuine coset/generalized-arithmetic-progression structure," with explicit polynomial-type bounds rather than qualitative existence.

4. Density increment on Bohr sets. Once $A$ is known to correlate with a structured object (a Bohr set / generalized AP), Gowers restricts attention to that structured piece and shows $A$'s density has provably increased on it, by a definite quantitative amount. Iterating — restrict, find correlation, increment density, repeat — cannot continue forever because density is capped at $1$; the number of iterations before contradiction is what produces the explicit (if enormous) tower-type bound. This is the same density-increment skeleton as Roth's 1953 proof for $k=3$, generalized from Fourier coefficients (which suffice for 3-APs) to the full hierarchy of uniformity norms (needed once $k\ge4$, since 4-APs are not controlled by Fourier analysis alone — a fact later understood via the inverse theorem for Gowers norms research program of Green–Tao–Ziegler).

5. Collapse Szemerédi to van der Waerden by pigeonhole, for free. No new argument is needed here: a 2-colouring of $\{1,\dots,N\}$ has some colour class of density $\ge 1/2$, so plugging $\delta=1/2$ into the explicit $N(k,\delta)$ bound from steps 1–4 immediately gives $W(k)\le N(k,1/2)$, the tower-of-six formula above.

Why this is the reusable part. The recipe — *(a) define a norm certifying pseudorandomness for the exact pattern at hand; (b) prove a counting/von-Neumann theorem that pseudorandom objects contain the expected count; (c) prove an inverse theorem that non-pseudorandom objects must correlate with lower-complexity algebraic structure (Freiman-type structure theorems, Balog–Szemerédi–Gowers-type "many collisions ⇒ real structure" lemmas); (d) iterate a density increment on the structured piece until density exceeds 1* — is now the standard template for effective bounds throughout additive combinatorics. It is the direct ancestor of: the inverse-Gowers-norm program (Green–Tao–Ziegler, nilsequence correlates), the polynomial Freiman–Ruzsa-flavored proofs used in Green–Tao's proof of the $k=4$ polynomial bound, Sanders'/Bloom's near-optimal Roth-theorem bounds (arXiv, 2010s–2020s) which replace Freiman's theorem with sharper Fourier-analytic covering lemmas at the structure step, and the 2024 Leng–Sah–Sawhney improvement (arXiv:2402.17995) which reruns exactly this density-increment skeleton but plugs in *quasipolynomial* inverse-theorem bounds for the $U^{s+1}$ norm instead of Gowers's original (much weaker, iterated-tower) inverse-theorem bounds — improving the shape of the final bound in $N$ without discarding any part of the four-step scaffold. Portable lesson for downstream open problems (e.g. Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers?'s fixed-2-colour $W(k)^{1/k}\to\infty$ question): the *upper*-bound side of this family is governed entirely by how good an "inverse theorem + structure-correlation" step one can prove; the *lower*-bound side (still stuck at $\Theta(2^k)$) has never used this machinery at all (it comes from Lovász Local Lemma constructions instead) — meaning genuine progress on #138 most plausibly requires either sharpening the inverse-theorem step further (upper-bound side, already the most active research direction) or importing a completely different structural idea into the lower-bound (colouring-construction) side, since no density-increment-style technique is known to produce *lower* bounds at all.

Related

- Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers? — open \$500 sibling: does $W(k)^{1/k}\to\infty$? This page's Gowers bound is the entire current upper-bound side of that problem (unimproved since 2001); the lower-bound side sits at only $\Theta(2^k)$ (Kozik–Shabanov 2016), leaving the enormous tower-vs-exponential gap that #138 asks about. - Erdős #190 — canonical Ramsey growth rate H(k)^{1/k}/k → ∞ (SOLVED) — the "canonical Ramsey" sibling (SOLVED 2026), which uses the *lower*-bound ($W(r,k)\gg r^{k-1}/k$, Lovász Local Lemma) side of the same $W(r,k)$ family that this page's bound occupies the *upper*-bound side of — an instructive contrast in which half of the same numerical quantity is tractable by which technique. - concept/gowers-uniformity-norms — the $U^d$ norms defined and exploited in this proof; the seed of the entire inverse-theorem research program (Green–Tao–Ziegler et al.) that followed. - concept/density-increment-argument — the Roth/Gowers iterative-restriction skeleton (steps 2–4 above) that this proof generalizes from Fourier coefficients ($k=3$) to full uniformity norms (general $k$); the same skeleton reappears in Leng–Sah–Sawhney (2024) and in Sanders'/Bloom's near-optimal $k=3$ bounds. - Lovász Local Lemma (symmetric, general/asymmetric, and algorithmic/random-recoloring variants) — probabilistic existence when bad events are individually non-negligible but sparsely dependent — the technique on the *lower*-bound side of $W(r,k)$ (Szabó 1990, Kozik–Shabanov 2016, and the Erdős–Lovász bound used in Erdős #190 — canonical Ramsey growth rate H(k)^{1/k}/k → ∞ (SOLVED)'s resolution); structurally unrelated to the uniformity-norm machinery on this page, which is the reason the upper and lower bounds on $W(k)$ have never met. - solved/roth-theorem-density-increment *(if present in this wiki)* — the $k=3$ special case (Roth 1953) that supplies the density-increment skeleton this proof generalizes; Gowers's own 1998 GAFA paper is the analogous $k=4$ special case immediately preceding this one.