Three in a row on the number line

Every version of Ramsey’s phenomenon so far has coloured pairs: an edge between two people, joined or not, one colour or the other. The structure forced is a set of points all of whose pairs agree.

There is a second family in which the thing coloured is a number — and in which the pigeonhole step is still the engine, applied to a different kind of box, and the structure forced is arithmetic. It is not the same theorem in different notation — the proofs share nothing, the bounds are of a completely different size, and one of the two is among the fastest-growing functions in mathematics.

Three equally spaced #

An arithmetic progression of length three is $a$, $a+d$, $a+2d$. Van der Waerden’s theorem says that for any number of colours $r$ and any length $k$, there is an $N$ such that every $r$-colouring of $1, \ldots, N$ contains a monochromatic progression of length $k$.

The smallest such $N$ is $W(r, k)$, and the case drawn above is $W(2,3) = 9$.

The colouring drawn is one of exactly six that survive at eight — and the six are three colourings and their colour-swaps, so really three. Each has a block structure rather than a random look, which is characteristic: the extremal colourings for these problems are arithmetic, and the search finds them because there is nothing else to find.

The figure runs the search rather than reporting it. For each length from 3 to 10 it enumerates every one of the $2^n$ colourings, tests each against every progression it could contain, and counts the survivors — and then verifies the threshold from both sides, that the last surviving length is one below the first failing one and that nothing survives above.

Adding one number #

The mechanism at the threshold is visible in the figure and is worth spelling out.

Take the surviving colouring of 1 to 8 and try to extend it to 9. Colouring 9 with the first colour makes some progression in that colour; colouring it with the second makes one in the other. Neither is available, so the extension fails, and since every one of the six survivors at eight fails the same way, $W(2,3) = 9$.

That is a verification of the threshold rather than a proof of the theorem. Van der Waerden’s theorem is about every $r$ and every $k$, and its proof is a double induction of remarkable ferocity.

The proof, in outline #

The double induction is worth sketching, because its shape explains the size of its answer.

Prove the statement for progressions of length $k$ in $r$ colours by assuming it for length $k-1$ in every number of colours. Take a long run of numbers and chop it into blocks. Each block has a colouring of its own, and if there are enough blocks then two blocks are coloured identically — a pigeonhole step, with the “colours” being whole block-colourings, of which there are $r^{\text{block length}}$.

Two identically coloured blocks, suitably placed, let a progression of length $k-1$ inside a block be extended by one term in the next block, giving length $k$. Making that precise requires the blocks themselves to be arranged in a progression, which is the inductive hypothesis applied at a coarser scale.

The cost is now visible. To get length $k$ in $r$ colours, the argument needs length $k-1$ in $r^{\text{something enormous}}$ colours, and that colour count is what compounds. Each step down in $k$ raises the number of colours to a tower, and the bound is the tower iterated $k$ times.

How fast the bound grows #

The original proof’s bound is not merely large; it is a member of a class of functions that arithmetic does not usually reach.

Van der Waerden’s induction produces a bound growing like the Ackermann function — faster than any tower of exponentials, faster than any function definable by a bounded number of recursions. For $W(2,5)$ the original argument gives a bound with more digits than there are particles in anything.

Shelah improved this in 1988 to a tower of exponentials, which was a substantial event, and Gowers improved it in 2001 to a bound that is merely enormous:

$$W(r, k) \leq 2^{2^{r^{2^{2^{k+9}}}}}.$$

That is now the best known, and the truth is believed to be far smaller. The known exact values are $W(2,3) = 9$, $W(2,4) = 35$, $W(2,5) = 178$, $W(2,6) = 1{,}132$, and $W(3,3) = 27$ and $W(4,3) = 76$. That is the complete list.

Schur’s theorem, which is older and easier #

The other classical arithmetic Ramsey result colours the numbers and forbids a monochromatic solution of $x + y = z$.

The Schur number $S(2) = 4$, and the sequence continues $S(3) = 13$, $S(4) = 44$, $S(5) = 160$. That last was settled in 2017 by a computer search producing a proof two hundred terabytes long, which is an exhaustion of a familiar kind at an unfamiliar scale.

Schur’s theorem is easy to prove from Ramsey’s, which is the one place where the two families genuinely touch. Colour the pairs $\{i, j\}$ by the colour of $|i - j|$. Ramsey’s theorem gives three numbers $a < b < c$ whose three pairs all get the same colour, and then $x = b - a$, $y = c - b$, $z = c - a$ satisfy $x + y = z$ with all three the same colour.

That derivation is the reason Schur’s theorem sits in this ladder rather than in a number-theory one. Everything else here is genuinely separate from the graph version.

Why Schur cared #

The theorem was proved in 1917 for a reason that has nothing to do with combinatorics.

Fermat’s last theorem — that $x^n + y^n = z^n$ has no whole-number solutions with $n > 2$ — was open. Schur showed that the congruence version is false: for every $n$, and for all sufficiently large primes $p$, the equation $x^n + y^n \equiv z^n \pmod p$ has a solution with none of them divisible by $p$.

The proof is his theorem. The non-zero residues modulo $p$ split into $n$ classes by $n$-th power residues — the classes of Fermat’s little theorem — which is a colouring in $n$ colours. For $p$ large enough, Schur’s theorem gives a monochromatic solution of $x + y = z$, and elements of one class are $n$-th powers times a fixed constant, so dividing through gives the congruence.

So the first arithmetic Ramsey theorem was proved to establish that a certain natural attack on Fermat’s last theorem could not work. It is a nice illustration of the subject’s origins being entirely instrumental.

The two families do not resemble one another #

It is worth putting the numbers side by side, because they are the clearest evidence that these are different theorems.

The graph Ramsey numbers grow exponentially: $R(k,k)$ is between $2^{k/2}$ and $4^k$, and every improvement has been to the constants. That is fast, and it is a rate that can be written down.

Van der Waerden’s numbers are not known to grow at any such rate. The best upper bound is a tower of exponentials of height depending on $k$, the best lower bound is roughly $2^k/k$, and the gap between them is not a gap between constants — it is a gap between one class of function and another.

The reason is that the two proofs do different amounts of work. The graph induction reduces a problem on $n$ points to two problems on fewer points, so the bound is a sum of two smaller bounds and the recursion is tame. Van der Waerden’s induction reduces a problem with $k$-term progressions in $r$ colours to a problem with $(k-1)$-term progressions in far more colours, and the number of colours explodes at each stage. A recursion that increases one parameter to decrease another is exactly the shape that produces Ackermann-like growth.

That is the honest answer to why arithmetic Ramsey theory is a separate subject: not because the objects differ but because the induction has a different shape, and the shape of an induction decides the size of its conclusion.

What the search is worth #

Exhaustive verification at eight numbers is a small thing to have, and it is worth being precise about what it does establish, because it is more than an illustration.

It establishes the value of $W(2,3)$ outright. Nine is not an estimate, a bound or an example: every colouring of eight was tried and six survive; every colouring of nine was tried and none does. The theorem’s general proof gives an upper bound on $W(2,3)$ of astronomical size and does not give the value; the exhaustion gives the value and nothing about any other case.

Those are complementary and neither substitutes for the other. It is the same division as in the previous rung: general arguments give the shape and specific searches give the numbers, and every exactly known value in the whole of Ramsey theory came from a search.

What makes the searches so limited is that they scale with $2^n$ and the thresholds grow far faster. Eight numbers is 256 colourings; thirty-five, which is $W(2,4)$, is thirty-four billion, and that is the last one an unstructured exhaustion reaches.

The shape of the whole family #

Once the pattern is visible, the family is large.

Van der Waerden. Any finite colouring of the integers has monochromatic arithmetic progressions of every length. It follows from the finite statement by a compactness argument, and implies it by the same route — the two are equivalent, and which is proved first is a matter of taste.

Schur. Any finite colouring has a monochromatic solution of $x + y = z$.

Rado. A general theorem saying exactly which systems of linear equations have this property, in terms of a condition on the coefficient matrix — so Schur’s is one case of a complete classification.

Hindman. Any finite colouring has an infinite set all of whose finite sums are the same colour — an infinite conclusion from a finite hypothesis, of the kind an infinite path in a tree also delivers. This is much stronger than Schur and its proof is a genuine shock, using an algebraic structure on ultrafilters.

Szemerédi. A colouring is not needed: any set of integers with positive upper density contains arbitrarily long arithmetic progressions — a strengthening of the same shape as replacing a counting argument by a density one in extremal graph theory. Van der Waerden follows immediately, since one colour class of a finite colouring must have positive density.

Green–Tao. The primes contain arbitrarily long arithmetic progressions — which does not follow from Szemerédi, since the primes have density zero, and the proof’s achievement is a transference argument that makes a Szemerédi-type theorem apply to a sparse set.

That last chain is worth noticing as a direction of travel. The subject started with colourings, moved to densities — which is strictly stronger and removes the colours entirely — and then to sets that are too sparse for densities to see.

What the picture cannot show #

The figures verify thresholds at eight and four, and the theorems they illustrate are about every length and every number of colours. That gap is larger here than anywhere else in this ladder: $W(2,4) = 35$ needs $2^{35}$ colourings and is beyond what a figure can enumerate, and $W(2,6) = 1{,}132$ was found by a search using structure rather than exhaustion.

So what the exhaustive search establishes is the smallest case and no more, and the general theorem is entirely a matter of proof. What the search does establish, which is worth having, is that the small case is genuinely exhausted: every colouring was tried, so the count of survivors is a fact rather than an estimate, and the threshold is where it is because nothing else exists.

There is also nothing here about the rate, which is the interesting quantity. The picture shows a count falling to zero and cannot show that the length at which it does so grows faster than any tower of exponentials.

Why the exhaustion is believable #

A count produced by a program is a claim about the program as much as about the mathematics, and it is worth saying what makes this one trustworthy.

The search is over every bit pattern of the right length, so there is no cleverness in the enumeration to get wrong — no symmetry reduction, no pruning, no ordering heuristic. Each pattern is tested against every progression it could contain, and the progressions are generated by two nested loops over the start and the common difference.

The results are then checked against each other rather than against a table. The last surviving length must be exactly one below the first failing one; nothing may survive above the threshold; and the colouring drawn must be verified once more, directly, to contain no pattern — and both of its one-step extensions verified to contain one.

Those cross-checks are what distinguish an exhaustion from an assertion. A program with an off-by-one in its progression generator would report a threshold, and would fail the check that the drawn colouring’s extensions both break.

The ladder from here #

Rungs above: Rado’s classification of which equations are partition-regular. Szemerédi’s theorem, and the three proofs of it that share nothing. The Hales–Jewett theorem, which is the combinatorial core underneath van der Waerden’s. Hindman’s theorem and the ultrafilter proof. Green and Tao on primes. And the compactness argument by which every one of these has an infinite version equivalent to its finite one.

Two subjects wearing one name #

The point worth carrying is that “Ramsey theory” names a phenomenon rather than a technique.

The phenomenon is that complete disorder is impossible: any sufficiently large structure, however it is divided, contains a large orderly piece. That statement is true of graphs, of the integers, of sequences, of geometric configurations and of much else.

The techniques share nothing. The graph version is a pigeonhole induction; van der Waerden’s is a double induction on colours and lengths; Szemerédi’s has an ergodic proof, a Fourier proof and a combinatorial one, none of which resembles the others. What unites the subject is the shape of its conclusions, and it is unusual for a field to be organised that way — most are organised around a method.