Extremal and additive combinatorics

MotivationH

Size forces structure

Four questions, each of the form "how large must an object be before some structure is unavoidable?"

Cliques. How many edges can a graph on $n$ vertices have without containing a triangle? Without a $K_4$ ? (Mantel, 1907; Turán, 1941.)
Homogeneous sets. How many people must be at a party before there are $k$ who all know each other or $k$ who are all strangers? For $k = 3$ the answer is $6$ ; for $k = 4$ it is $18$ ; for $k = 5$ nobody knows — it lies between $43$ and $46$ .
Progressions. How large can a subset of $\{1, \dots, N\}$ be with no three terms in arithmetic progression? Roth (1953) proved: $o(N)$ . Szemerédi (1975) proved the same for progressions of any length $k$ .
Primes. The primes have density zero, so Szemerédi's theorem does not apply to them. Yet Green and Tao (2004) proved that they contain arithmetic progressions of every finite length: $7, 37, 67, 97, 127, 157$ is one of length six.

Extremal combinatorics asks for the maximum size of an object avoiding a forbidden substructure (Turán numbers, Ramsey numbers); additive combinatorics studies the additive structure of sets of integers or of abelian groups (progressions, sumsets, sum–product phenomena). Szemerédi's theorem belongs to both, and the methods that grew around it — the regularity lemma, Fourier analysis and its higher-order generalisation, ergodic theory, the probabilistic method and the polynomial method — form one of the most active areas of modern mathematics. This lesson builds on graph theory (where $R(3,3) = 6$ , Mantel's theorem and the basic Ramsey bounds are proved), the probabilistic method and elementary number theory.

IntuitionH

Structure versus randomness

A useful slogan (popularised by Tao): every large object is a mixture of structure and randomness, and both parts force patterns. A random set of integers of density $\alpha$ contains about $\alpha^3 N^2/4$ three-term progressions in $\{1, \dots, N\}$ , simply by counting. A structured set — say all integers in a sub-progression, or all integers $x$ with $x\theta \bmod 1$ in a short interval — contains progressions for structural reasons. The proofs make this dichotomy precise:

Graphs. Szemerédi's regularity lemma splits any large graph into boundedly many pieces between which the edges look random. Counting then works as in a random graph.
Integers. Fourier analysis detects structure: if a set has few three-term progressions, its indicator function correlates with a character $x \mapsto e^{2\pi i r x/N}$ , so it is denser on some long sub-progression. Iterating this density increment proves Roth's theorem. Longer progressions need "higher-order" Fourier analysis (Gowers norms).
Lower bounds go the other way: random objects are unstructured. A random red–blue colouring of $K_n$ has no large monochromatic clique, which is why Ramsey numbers grow exponentially. Ironically, nobody can construct colourings explicitly that are as good as random ones.

DefinitionsH

Definitions

Definition— Turán number and Turán graph

The Turán number $\mathrm{ex}(n, H)$ is the maximum number of edges of an $n$ -vertex graph containing no copy of $H$ . The Turán graph $T(n, r)$ is the complete $r$ -partite graph on $n$ vertices with parts of sizes $\lfloor n/r \rfloor$ or $\lceil n/r \rceil$ ; it contains no $K_{r+1}$ , and has $t(n, r) \le \left(1 - \tfrac1r\right)\tfrac{n^2}{2}$ edges.

Definition— Ramsey number

The Ramsey number $R(s, t)$ is the least $n$ such that every red–blue colouring of the edges of $K_n$ contains a red $K_s$ or a blue $K_t$ . Equivalently: every graph on $n$ vertices contains a clique of size $s$ or an independent set of size $t$ .

Definition— density, progressions and Roth numbers

A set $A \subseteq \Z$ has positive upper density if $\limsup_{N \to \infty} |A \cap [1, N]|/N > 0$ . A $k$ -term arithmetic progression ( $k$ -AP) is $a, a + d, \dots, a + (k-1)d$ with $d \neq 0$ . The Roth number $r_k(N)$ is the largest size of a subset of $\{1, \dots, N\}$ with no $k$ -AP; we write $r_3(N)$ for three-term progressions.

Definition— sumsets and doubling

For finite sets $A, B$ in an abelian group, $A + B = \{a + b : a \in A, b \in B\}$ and $A \cdot B$ similarly. The doubling constant of $A$ is $|A + A|/|A|$ . A generalised arithmetic progression of dimension $d$ is a set $\{a_0 + x_1d_1 + \cdots + x_dd_d : 0 \le x_i \lt L_i\}$ .

Definition— ε-regular pairs and partitions

For disjoint vertex sets $X, Y$ of a graph, the density is $d(X, Y) = e(X, Y)/(|X||Y|)$ . The pair is $\varepsilon$ -regular if $|d(X', Y') - d(X, Y)| \le \varepsilon$ for all $X' \subseteq X$ , $Y' \subseteq Y$ with $|X'| \ge \varepsilon|X|$ , $|Y'| \ge \varepsilon|Y|$ . A partition $V = V_1 \cup \dots \cup V_k$ into parts of almost equal size is $\varepsilon$ -regular if all but at most $\varepsilon k^2$ of the pairs $(V_i, V_j)$ are $\varepsilon$ -regular.

Definition— Fourier transform on ℤ/Nℤ

For $f : \Z/N\Z \to \C$ put $\hat f(r) = \mathbb{E}_{x} f(x) e(-rx/N)$ , where $e(t) = e^{2\pi i t}$ and $\mathbb{E}_x = \frac1N\sum_x$ . Then $f(x) = \sum_r \hat f(r) e(rx/N)$ and Parseval's identity holds: $\sum_r |\hat f(r)|^2 = \mathbb{E}_x |f(x)|^2$ .

Definition— cap set

A cap set is a subset of $\mathbb{F}_3^n$ containing no three distinct points on a line, i.e. no $x, y, z$ , not all equal, with $x + y + z = 0$ — the $\mathbb{F}_3^n$ analogue of a 3-AP-free set.

Worked examplesH

Examples

Example— Turán graphs

$T(6, 2) = K_{3,3}$ has $9$ edges and no triangle; $T(6, 3) = K_{2,2,2}$ (the octahedron) has $12$ edges and no $K_4$ . The first experiment checks all $32768$ graphs on six vertices: these are the maxima, and the only graphs attaining them are copies of the Turán graphs ( $10$ labelled copies of $K_{3,3}$ , $15$ of $K_{2,2,2}$ ).

Example— The Paley graph and R(4, 4) > 17

Join $x, y \in \Z/17$ when $x - y$ is a non-zero square ( $\pm1, \pm2, \pm4, \pm8$ ). This graph is $8$ -regular, it is isomorphic to its complement (multiply by the non-square $3$ ), every adjacent pair has exactly $3$ common neighbours and every non-adjacent pair $4$ — a "pseudo-random" graph. It has no $K_4$ and, by self-complementarity, no independent set of size $4$ . So $R(4, 4) \ge 18$ ; Greenwood and Gleason (1955) showed $R(4, 4) = 18$ .

Example— Sets without three-term progressions

The integers whose base- $3$ digits are all $0$ or $1$ contain no 3-AP: if $a + c = 2b$ with such digits, then adding $a + c$ digit by digit produces no carries and neither does doubling $b$ , so the digits agree and $a = b = c$ . Below $3^m$ there are $2^m$ of them, about $N^{0.63}$ . Behrend (1946) did much better: lattice points on a sphere in a high-dimensional box, read as base- $b$ digits, give $r_3(N) \ge N e^{-c\sqrt{\log N}}$ . This is larger than $N^{1-\varepsilon}$ for every $\varepsilon$ , yet still $o(N)$ , as Roth's theorem requires. The squares, by contrast, contain many 3-APs ( $1, 25, 49$ ; in general $(a^2 - 2ab - b^2)^2$ , $(a^2 + b^2)^2$ , $(a^2 + 2ab - b^2)^2$ ), but no 4-term progression (Fermat, proved by Euler).

Example— Sums versus products

For $A = \{1, \dots, n\}$ , $|A + A| = 2n - 1$ but $|A \cdot A|$ is much larger (asymptotically $n^2/(\log n)^{c+o(1)}$ with $c = 1 - \frac{1 + \log\log 2}{\log 2}$ , by Ford's work on the multiplication table). For $A = \{1, 2, 4, \dots, 2^{n-1}\}$ , $|A \cdot A| = 2n - 1$ but $|A + A| = \binom{n+1}{2}$ . The second experiment computes both for $n = 20$ : in each case one of the two is large.

Example— Cap sets

In $\mathbb{F}_3^2$ the largest cap set has $4$ points (e.g. $(0,0), (0,1), (1,0), (1,1)$ ). The maximum sizes for $n = 1, \dots, 6$ are $2, 4, 9, 20, 45, 112$ , the last found by Potechin (2008). They are the maximum numbers of cards in the game SET (for $n = 4$ ) with no "set" among them.

ProofH

Extremal graph theory and Ramsey numbers

Theorem— Theorem 1 (Turán 1941)

Let $r \ge 1$ . Every graph on $n$ vertices with no $K_{r+1}$ has at most $t(n, r)$ edges, with equality only for $T(n, r)$ . In particular $\mathrm{ex}(n, K_{r+1}) \le \left(1 - \frac1r\right)\frac{n^2}{2}$ .

Proof

(Zykov symmetrisation.) Let $G$ be $K_{r+1}$ -free on $n$ vertices with the maximum number of edges. For a vertex $v$ , "replacing $u$ by a copy of $v$ " means deleting $u$ and adding a new vertex $v'$ adjacent exactly to $N(v)$ . The new graph is still $K_{r+1}$ -free: a clique cannot contain both $v$ and $v'$ (they are not adjacent), and a clique through $v'$ but not $v$ becomes a clique through $v$ when $v'$ is replaced by $v$ .

Step 1: non-adjacency is transitive. Suppose $u \not\sim v$ and $v \not\sim w$ but $u \sim w$ (so $u \neq w$ ). If $d(v) \lt d(u)$ , replace $v$ by a copy of $u$ : since $v \not\sim u$ , this changes the edge count by $d(u) - d(v) \gt 0$ , contradicting maximality; similarly if $d(v) \lt d(w)$ . Otherwise $d(v) \ge d(u)$ and $d(v) \ge d(w)$ ; replace both $u$ and $w$ by copies of $v$ (neither is a neighbour of $v$ , so $N(v)$ is unchanged). We lose $d(u) + d(w) - 1$ edges (the edge $uw$ is counted twice) and gain $2d(v)$ , a net gain of at least $1$ — again a contradiction.

So "equal or non-adjacent" is an equivalence relation, and $G$ is complete multipartite. It has at most $r$ parts, since one vertex from each of $r + 1$ parts would form a $K_{r+1}$ .

Step 2: the parts are balanced. A complete multipartite graph with parts of sizes $n_1, \dots, n_r$ has $\frac12\left(n^2 - \sum n_i^2\right)$ edges. If $n_i \ge n_j + 2$ , moving a vertex from part $i$ to part $j$ changes the edge count by $(n_i - 1) - n_j \gt 0$ . So in the extremal graph all parts differ in size by at most one: $G \cong T(n, r)$ . Finally $\sum n_i^2 \ge n^2/r$ by the Cauchy–Schwarz inequality, giving the bound $\left(1 - \frac1r\right)\frac{n^2}{2}$ .

∎

Mantel's theorem is the case $r = 2$ . Turán's theorem is the starting point of a large theory. The Erdős–Stone theorem (1946), in the form noted by Erdős and Simonovits (1966), says $\mathrm{ex}(n, H) = \left(1 - \frac{1}{\chi(H) - 1} + o(1)\right)\frac{n^2}{2}$ : the chromatic number of $H$ alone determines the asymptotics — except when $H$ is bipartite, where it only says $o(n^2)$ . Bipartite Turán problems are much harder: the Kővári–Sós–Turán theorem gives $\mathrm{ex}(n, K_{s,t}) = O(n^{2 - 1/s})$ , and $\mathrm{ex}(n, C_4) \sim \frac12 n^{3/2}$ , but even the order of magnitude of $\mathrm{ex}(n, C_8)$ is unknown.

Theorem— Theorem 2 (Ramsey 1930; Erdős–Szekeres 1935)

$R(s, t) \le R(s - 1, t) + R(s, t - 1)$ for $s, t \ge 2$ , and $R(s, t) \le \binom{s + t - 2}{s - 1}$ . In particular $R(k, k) \le \binom{2k - 2}{k - 1} \lt 4^{k-1}$ .

Proof

Colour $K_n$ with $n = R(s-1, t) + R(s, t-1)$ and pick a vertex $v$ . Its $n - 1$ other vertices split into red neighbours and blue neighbours, and by the pigeonhole principle there are at least $R(s - 1, t)$ of the first or at least $R(s, t - 1)$ of the second. In the first case they contain a blue $K_t$ (done) or a red $K_{s-1}$ , which with $v$ is a red $K_s$ ; the second case is symmetric. The binomial bound follows by induction on $s + t$ from $R(1, t) = R(s, 1) = 1$ and Pascal's rule. (The formal section proves exactly this in Lean, for graphs on any vertex type.)

∎

Theorem— Theorem 3 (Erdős 1947; Spencer 1975)

For $k \ge 3$ , $R(k, k) \gt 2^{k/2}$ . More precisely $R(k, k) \ge (1 + o(1))\frac{\sqrt 2}{e}\, k\, 2^{k/2}$ .

Proof

(First part.) Colour the edges of $K_n$ , $n = \lfloor 2^{k/2} \rfloor$ , independently at random. A fixed $k$ -set is monochromatic with probability $2^{1 - \binom k2}$ , so the expected number of monochromatic $K_k$ is $\binom nk 2^{1 - \binom k2} \lt \frac{n^k}{k!}2^{1 - \frac{k(k-1)}{2}} \le \frac{2^{1 + k/2}}{k!} \lt 1$ . Some colouring therefore has none. (Optimising $n$ in the same computation gives $R(k, k) \gt (1 + o(1))\frac{1}{e\sqrt 2}k2^{k/2}$ ; the deletion method — take $n$ larger, then delete one vertex from each monochromatic $K_k$ — improves the constant to $\frac1e$ , and Spencer's application of the Lovász local lemma to $\frac{\sqrt 2}{e}$ .)

∎

So $\sqrt2^{\,k} \lt R(k, k) \lt 4^k$ . The lower bound has not been improved exponentially since 1947, and no explicit construction comes close to it. On the upper side, Thomason (1988), Conlon (2009) and Sah (2020) improved the lower-order factors, but the exponential base $4$ stood for 88 years until Campos, Griffiths, Morris and Sahasrabudhe (2023) proved $R(k, k) \le (4 - \varepsilon)^k$ for some $\varepsilon \gt 0$ ; subsequent work by Gupta, Ndiaye, Norin and Wei (2024) brought the base down to about $3.8$ .

ProofH

Progressions: regularity, Fourier analysis and beyond

Theorem— Theorem 4 (Szemerédi's regularity lemma, 1975–78)

For every $\varepsilon \gt 0$ there is $M(\varepsilon)$ such that every graph has an $\varepsilon$ -regular partition into $k$ parts with $1/\varepsilon \le k \le M(\varepsilon)$ .

The proof refines partitions step by step, using an "energy" (mean square density) that is bounded by $1$ and increases by $\varepsilon^5$ at each refinement as long as the partition is not regular; the resulting $M(\varepsilon)$ is a tower of $2$ 's of height polynomial in $1/\varepsilon$ , and Gowers (1997) showed that tower-type growth is necessary. Its most famous consequence:

Theorem— Theorem 5 (triangle removal lemma; Ruzsa–Szemerédi 1978)

For every $\delta \gt 0$ there is $\varepsilon \gt 0$ such that every graph on $n$ vertices with at most $\varepsilon n^3$ triangles can be made triangle-free by deleting at most $\delta n^2$ edges.

(Apply the regularity lemma, delete the edges inside parts, between irregular pairs and between sparse pairs — at most $\delta n^2$ in all — and observe that a triangle surviving among three dense regular pairs would force, by the counting lemma, $\gt \varepsilon n^3$ triangles.)

Theorem— Theorem 6 (Roth 1953)

$r_3(N) = o(N)$ : for every $\delta \gt 0$ , every $A \subseteq \{1, \dots, N\}$ with $|A| \ge \delta N$ contains a three-term progression once $N$ is large enough.

Proof

(Via the removal lemma, Ruzsa–Szemerédi.) Let $A \subseteq \{1, \dots, N\}$ contain no 3-AP, and let $M = 2N + 1$ , so that $2$ is invertible in $\Z/M$ and no progression of elements of $\{1, \dots, N\}$ wraps around. Build a tripartite graph with parts $X, Y, Z$ , each a copy of $\Z/M$ , joining $x \in X$ to $y \in Y$ if $y - x \in A$ , $y \in Y$ to $z \in Z$ if $z - y \in A$ , and $x \in X$ to $z \in Z$ if $(z - x)/2 \in A$ . A triangle $(x, y, z)$ gives $a = y - x$ , $b = z - y$ , $c = (z - x)/2$ in $A$ with $a + b \equiv 2c \pmod M$ , hence $a + b = 2c$ (all three lie in $[1, N]$ and $2N \lt M$ ): this is the progression $a, c, b$ , which is trivial only if $a = b = c$ . So the only triangles are the $M|A|$ "trivial" ones $(x, x + a, x + 2a)$ , and they are edge-disjoint (each edge determines $x$ and $a$ ). Fix $\delta \gt 0$ and let $\varepsilon$ be as in the removal lemma. The graph has $n = 3M$ vertices and $M|A| \le M^2 \le \varepsilon(3M)^3$ triangles once $M \ge 1/(27\varepsilon)$ , so deleting at most $\delta(3M)^2 = 9\delta M^2$ edges destroys all of them. Each deleted edge destroys at most one of the edge-disjoint triangles, so $M|A| \le 9\delta M^2$ , i.e. $|A| \le 9\delta M \le 27\delta N$ . As $\delta$ was arbitrary, $|A| = o(N)$ .

∎

Roth's original proof was Fourier-analytic, and it gives quantitative bounds ( $r_3(N) \ll N/\log\log N$ ) that the removal lemma cannot. Its heart is the following lemma, which we prove in full.

Theorem— Lemma 7 (the key lemma of Roth's argument)

Let $N$ be odd and $A \subseteq \Z/N\Z$ have density $\alpha = |A|/N$ with $N \ge 2/\alpha^2$ . If $A$ contains no non-trivial 3-AP $x, x + d, x + 2d$ ( $d \neq 0$ ), then $|\hat{1}_A(r)| \ge \alpha^2/2$ for some $r \neq 0$ .

Proof

Let $f = 1_A$ and $\Lambda = \mathbb{E}_{x, d} f(x)f(x + d)f(x + 2d)$ . Substituting $y = x + d$ , $z = x + 2d$ (so $x + z = 2y$ ), and expanding each $f$ by Fourier inversion,

\Lambda = \frac{1}{N^2}\sum_{x + z = 2y} f(x)f(y)f(z) = \sum_{r} \hat f(r)^2\, \hat f(-2r),

because $\frac{1}{N^2}\sum_{x + z = 2y} e\big((r_1x + r_2y + r_3z)/N\big)$ is $1$ when $r_1 = r_3 = r$ and $r_2 = -2r$ , and $0$ otherwise. If $A$ has no non-trivial 3-AP, only $d = 0$ contributes to $\Lambda$ , so $\Lambda = \alpha/N \le \alpha^3/2$ . The $r = 0$ term is $\hat f(0)^3 = \alpha^3$ . Hence

\frac{\alpha^3}{2} \le \Big|\sum_{r \neq 0} \hat f(r)^2\, \hat f(-2r)\Big| \le \max_{s \neq 0}|\hat f(s)| \sum_r |\hat f(r)|^2 = \alpha \max_{s \neq 0}|\hat f(s)|,

using that $r \mapsto -2r$ is a bijection of the non-zero residues ( $N$ odd) and Parseval's identity $\sum_r |\hat f(r)|^2 = \mathbb{E}|f|^2 = \alpha$ . So some $|\hat f(s)| \ge \alpha^2/2$ .

∎

The density increment (outline). A large coefficient $\hat 1_A(s)$ means that $A$ correlates with the character $x \mapsto e(sx/N)$ . By Dirichlet's approximation theorem one can partition $\{1, \dots, N\}$ into progressions of length about $\sqrt N$ on each of which $sx/N$ is nearly constant modulo $1$ ; averaging, $A$ has density at least $\alpha + c\alpha^2$ on one of them, for an absolute constant $c \gt 0$ (after a standard reduction to avoid wrap-around). Restrict to that progression, rescale it to $\{1, \dots, N'\}$ with $N' \approx \sqrt N$ , and repeat. The density cannot exceed $1$ , so after $O(1/\alpha)$ steps the process must stop — which can only happen because $A$ contains a 3-AP or $N$ has become too small. This gives $r_3(N) \ll N/\log\log N$ .

Theorem— Theorem 8 (Szemerédi 1975)

Every subset of the integers with positive upper density contains arbitrarily long arithmetic progressions; equivalently $r_k(N) = o(N)$ for every $k$ .

There are four fundamentally different proofs: Szemerédi's combinatorial proof (which introduced the regularity lemma); Furstenberg's ergodic-theoretic proof (1977), via a multiple recurrence theorem for measure-preserving systems; Gowers's proof (1998–2001) by "higher-order Fourier analysis" with the norms $\|f\|_{U^k}$ , the first with reasonable bounds; and proofs via the hypergraph removal lemma (Gowers; Nagle, Rödl, Schacht and Skokan, 2004–07).

Theorem— Theorem 9 (Green–Tao 2004, published 2008)

The primes contain arbitrarily long arithmetic progressions.

The proof is a transference principle: Szemerédi's theorem holds not only for dense subsets of the integers but for dense subsets of suitably pseudorandom sparse sets. Green and Tao show that the primes are a dense subset of the "almost primes", weighted by a majorant built from the sieve weights of Goldston and Yıldırım, which is pseudorandom in the required sense. The theorem gives arbitrarily long finite progressions — the primes contain no infinite one (see the misconceptions). Tao and Ziegler (2008) extended it to polynomial progressions.

Theorem— Theorem 10 (Dvir 2008: finite-field Kakeya)

If $K \subseteq \mathbb{F}_q^n$ contains a line in every direction, then $|K| \ge \binom{q + n - 1}{n} \ge q^n/n!$ .

Proof

The polynomials of degree at most $q - 1$ in $n$ variables over $\mathbb{F}_q$ form a vector space of dimension $\binom{q - 1 + n}{n}$ . If $|K|$ were smaller, the $|K|$ linear conditions " $P(k) = 0$ for $k \in K$ " would have a non-zero solution: a polynomial $P \neq 0$ of degree $d \le q - 1$ vanishing on $K$ . Since $K \neq \emptyset$ , $P$ is not a non-zero constant, so $d \ge 1$ . Write $P = P_d + (\text{lower terms})$ with $P_d \neq 0$ homogeneous of degree $d$ . For every direction $v \neq 0$ , $K$ contains a line $\{x + tv : t \in \mathbb{F}_q\}$ , so $g(t) = P(x + tv)$ , a polynomial in $t$ of degree at most $d \le q - 1$ , has $q$ roots and is identically zero. Its coefficient of $t^d$ is $P_d(v)$ , so $P_d(v) = 0$ for all $v \neq 0$ , and $P_d(0) = 0$ by homogeneity. Thus $P_d$ vanishes on all of $\mathbb{F}_q^n$ although its degree in each variable is at most $q - 1$ , which forces $P_d = 0$ (induct on $n$ : a non-zero one-variable polynomial of degree $\le q - 1$ has fewer than $q$ roots). This contradiction proves $|K| \ge \binom{q + n - 1}{n}$ .

∎

The same philosophy — find a low-degree polynomial vanishing on the set, then exploit the structure — solved several famous problems: the cap set problem (Croot, Lev and Pach for $(\Z/4)^n$ ; Ellenberg and Gijswijt, 2016: every cap set in $\mathbb{F}_3^n$ has size at most $2.756^n$ for large $n$ , using what is now called the slice-rank method), and Guth and Katz's near-solution of Erdős's distinct distances problem (2010). Over $\R^n$ , the Kakeya conjecture is much harder; for $n = 3$ a proof was announced by Wang and Zahl in 2025.

Theorem— Theorem 11 (Freiman 1964–73; Ruzsa 1994)

If $A \subset \Z$ is finite with $|A + A| \le K|A|$ , then $A$ is contained in a generalised arithmetic progression of dimension at most $d(K)$ and size at most $C(K)|A|$ .

The simplest case is formalised below: $|A + A| \ge 2|A| - 1$ , with equality only for arithmetic progressions. The polynomial Freiman–Ruzsa conjecture asks for bounds polynomial in $K$ ; Gowers, Green, Manners and Tao proved it in $\mathbb{F}_2^n$ in November 2023 (over $\Z$ it remains open).

ExplanationH

The landscape: known and open

Recent theorems. Kelley and Meka (2023) proved $r_3(N) \le N\exp\left(-c(\log N)^{1/12}\right)$ , close in shape to Behrend's lower bound $N\exp(-c'\sqrt{\log N})$ (Bloom and Sisask improved $1/12$ to $1/9$ ); an earlier bound of Bloom and Sisask (2020) already settled the case $k = 3$ of the Erdős–Turán conjecture below. For longer progressions, Leng, Sah and Sawhney (2024) proved $r_k(N) \le N\exp\left(-(\log\log N)^{c_k}\right)$ . In Ramsey theory: $R(3, t) = \Theta(t^2/\log t)$ (Ajtai–Komlós–Szemerédi, 1980; Kim, 1995); Mattheus and Verstraete (2023) showed $R(4, t) \ge c\, t^3/\log^4 t$ , matching the upper bound up to logarithms; and the exponential improvement of the diagonal upper bound described above.

Open problems (well documented; consult recent surveys for progress):

Small Ramsey numbers. $R(5, 5)$ is unknown; it lies between $43$ (Exoo, 1989) and $46$ (Angeltveit and McKay, 2024).
Growth of $R(k, k)$ . Does $\lim_k R(k, k)^{1/k}$ exist, and what is it? It lies between $\sqrt 2$ and about $3.8$ . Erdős offered a prize for the existence of the limit.
Erdős–Turán. If $\sum_{a \in A} 1/a = \infty$ , must $A$ contain arbitrarily long progressions? Known for $k = 3$ ; open for $k \ge 4$ (it would imply Green–Tao).
Sum–product. Erdős and Szemerédi (1983) proved $\max(|A + A|, |A \cdot A|) \ge |A|^{1 + c}$ for finite $A \subset \Z$ and conjectured exponent $2 - \varepsilon$ . The best exponents known are $\tfrac43$ plus small explicit improvements (Solymosi, 2009; Konyagin–Shkredov; Rudnev–Stevens).
Cap sets. The largest cap set in $\mathbb{F}_3^n$ has size $c^n$ with $2.2 \lt c \le 2.756$ (roughly); the true base is unknown.
Bipartite Turán problems, such as the order of magnitude of $\mathrm{ex}(n, C_8)$ or $\mathrm{ex}(n, K_{4,4})$ ; and the polynomial Freiman–Ruzsa conjecture over $\Z$ .

Formal mathematicsF

Combinatorics in Lean and Mathlib

Additive combinatorics is one of the best-formalised parts of modern mathematics: Mathlib contains Szemerédi's regularity lemma, the triangle removal lemma, Roth's theorem, the Cauchy–Davenport theorem, Plünnecke–Ruzsa inequalities and Turán's theorem, much of it by Yaël Dillies and Bhavik Mehta. Moreover, the November 2023 proof of the polynomial Freiman–Ruzsa conjecture over $\mathbb{F}_2^n$ was completely formalised in Lean 4 with Mathlib about three weeks after it appeared, in an open collaborative project led by Terence Tao.

Turán's theorem, structural form:

turan_structureLean 4Applies a library theoremFormally verified

/-- **Turán's theorem**, structural form: for `r ≥ 1`, a graph on `n` vertices is
*Turán-maximal* (it has no `K_{r+1}` and as many edges as possible among such graphs) if and
only if it is isomorphic to the Turán graph `T(n, r)`, the complete `r`-partite graph with parts
as equal as possible. This applies Mathlib's `SimpleGraph.isTuranMaximal_iff_nonempty_iso_turanGraph`
(proved there by Zykov symmetrisation). -/
theorem turan_structure {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {r : ℕ}
    (hr : 0 < r) :
    G.IsTuranMaximal r ↔ Nonempty (G ≃g SimpleGraph.turanGraph (Fintype.card V) r) :=
  SimpleGraph.isTuranMaximal_iff_nonempty_iso_turanGraph hr