Colour the whole number line and arithmetic patterns survive anyway
Ramsey theory did not begin with graphs. In 1916, fourteen years before Frank Ramsey wrote his paper, Issai Schur proved that however you split the numbers 1, 2, 3, … into finitely many classes, one class contains a solution of x + y = z. He needed it as a lemma about Fermat’s equation modulo a prime. Eleven years after that, Bartel van der Waerden proved that one class always contains an arithmetic progression of any length you care to name.
These are the same statement as the party problem in different clothing. You have a structure, you chop it into pieces however you like, and past a certain size one piece contains an intact copy of the pattern you were trying to break. On the number line you can do the chopping yourself, one integer at a time, and watch it fail.
Give each number a colour, and try to make sure that no colour class ever contains two of its members together with their sum. With two colours you can manage 1 to 4: put 1 and 4 in one class, 2 and 3 in the other, and check every sum. Add a fifth number and no split survives. The largest n that works is the Schur number S(k), and the known list is four entries long before a supercomputer is required.
No violations yet — 5 numbers still uncoloured.
x and y are allowed to be equal, so 3 + 3 = 6 counts: no colour class may contain a number together with its double. Press S(2) or S(3) to jump one past that Schur number and watch the solver exhaust every possibility and report that nothing works. Press S(4) and it will find a four-colouring of 1 to 44 — but ruling out 45 is beyond what a browser should be asked to do in a click.
Try it: Start where it opens — five numbers, two colours — and convince yourself by hand that nothing works. Then take three colours and thirteen numbers, which is possible but genuinely fiddly, and fourteen, which is not. The pattern in the values is brutal: 1, 4, 13, 44, 160. Each one costs vastly more to establish than the last, and S(5) took a SAT solver in 2017.
Now the pattern to avoid is three numbers evenly spaced — 4, 9, 14 or 2, 3, 4 or 1, 5, 9. Two colours will get you to eight: rose, rose, sky, sky, rose, rose, sky, sky avoids every three-term progression. At nine it is over, so W(2,3) = 9. Three colours reach 26, and progressions of length four with two colours reach 34.
No violations yet — 8 numbers still uncoloured.
W(k, r) is the first n at which every k-colouring of 1 to n contains a monochromatic progression of length r, so the escapable range is 1 to W − 1. Fewer than ten of these numbers have ever been determined, and the largest, W(2,6) = 1132, took a specialised parallel search. Van der Waerden’s proof gives no usable bound at all — the function it produces grows faster than any tower of exponentials, and it took until 1988 for Shelah to bring it down to something merely astronomical.
Try it: Press W(3,3) = 27 and then Solve it for me. The search exhausts every three-colouring of 1 to 27 in about 110,000 steps and reports that none escapes. Then press W(4,3) = 76 and watch the same search run out of budget entirely — one extra colour, and the problem leaves the reach of a browser.
Sums and progressions are two choices out of many. Fix any family of finite patterns with enough arithmetic structure and the same question appears: how far up the number line can you colour before one pattern is forced into a single colour? The answers differ wildly, and the difference is roughly how sparse the family is. Sum triples are dense and collapse at 5. Pythagorean triples are sparse, and hold out for 7,824.
Pick a pattern and a number of colours, then let the search walk up the number line until it cannot go further.
The integers 1 to 7,824 can be two-coloured so that no Pythagorean triple is monochromatic. At 7,825 it becomes impossible. There is no argument for this, no structure, no proof a person could read: in 2016 Heule, Kullmann and Marek settled it with a SAT solver, and the certificate it produced runs to 200 terabytes — the largest mathematical proof ever produced at the time. Set this demo to Pythagorean triples and two colours and it will cheerfully colour every n it is allowed to try, because failure does not begin until roughly forty times further out than it can see.
The searches here are exhaustive, not heuristic: when the result says a value is exact, every colouring of the next size up has been ruled out. Notice how differently the three families behave. Sum triples fall apart almost at once — four integers with two colours. Progressions last a little longer. Pythagorean triples are so sparse that they hold out for thousands of steps, which is precisely why nobody could settle them without a machine.
Try it: Run each family in turn and read the status line as carefully as the number. Sum triples and short progressions are settled exhaustively in a fraction of a second. Longer progressions blow the step budget and the demo says so rather than guessing. Pythagorean triples simply never fail inside the range it is allowed to look — the wall is at 7,825, about forty times further out.
Read across the rows below and the theorems stop looking like separate results. Graphs, integers, Pythagorean triples, points in the plane and high-dimensional tic-tac-toe all say the identical thing: complete disorder is impossible, and the only question is how much room you need before order reappears.
Five people can be arranged so that no three are mutual friends and no three mutual strangers — the friendships form a pentagon and the non-friendships a pentagram, and neither shape holds a triangle. Add a sixth person and all 32,768 arrangements fail. Ramsey proved in 1930 that the same thing happens for every clique size, not just triangles. The party problem is this row.
Read the first three columns downward and every row says the same sentence. The fourth column is where all the difficulty lives: the theorems are one paragraph each, and the numbers they promise have almost never been found.
Try it: Open each row and compare the last column with the first. Every one of these theorems has a proof of a page or two. Not one of them tells you the number, and in most cases nobody knows it — the existence and the value are separated by the whole difficulty of the subject.
Van der Waerden’s original proof produces a bound that grows faster than any tower of exponentials — a genuinely non-primitive-recursive function. Shelah brought it down to something merely enormous in 1988, and Gowers to a tower of fixed height in 2001. None of that helps with the actual values, which is why fewer than ten van der Waerden numbers and five Schur numbers are known after a century of effort, and why the last few arrived as certificates rather than arguments. See also: the machine age, where proofs stopped being things people read, and small Ramsey numbers, which are unknown for exactly the same reason.