by Jonathan Kujawa
One of my favorite areas of mathematics is Ramsey theory. In fact, my first 3QD essay was about F. P. Ramsey and his marvelous result which launched the field. It is one of those rare parts of mathematics where the results are often easy to understand, hard to prove, and yet delightfully surprising. Just last week came a breakthrough in Ramsey theory which I’d like to tell you about.
Meta-mathematically, Ramsey theory tells us that order unavoidably emerges whenever something is sufficiently large. Even if the structure is completely random or, worse, fiendishly crafted by a nefarious opponent, order cannot help but be found.
Ramsey theory is almost philosophical. How is it that consciousness emerges from our complicated neural network? Or that life appeared from the rich soup of prebiotic molecules in the Earth’s ancient waters? Once you know about Ramsey theory, such things seem more inevitable than miraculous. As Ian Malcolm said, “life finds a way”.
Ramsey theory comes in numerous flavors. Once you know to look for order inside large scale structures, you start finding it everywhere. In Ramsey’s original theorem, he showed that any group of six or more must have three people who are all friends or all strangers [1].
This corner of Ramsey theory is about structures within networks, where the mathematical structure consists of nodes and some of the nodes are connected. This could be people connected by friendship, computers connected by the internet, or items in a grocery store connected because they are frequently bought together. Ramsey’s original theorem says whatever the nodes represent, whatever rules determine which nodes are connected, and however many types of connections you allow (friends, strangers, enemies, frenemies, …), if the network is large enough, you can always find highly ordered sub-networks.
In a later 3QD essay, I wrote about a geometric flavor of Ramsey theory. In that essay we talked about the problem of coloring the points of the xy-plane in such a way that you can avoid having two points of the same color exactly one unit apart. It’s known that if you allow eight colors, then I can color the points of the plane in a way so that no two of the same color are exactly one unit apart. It’s also known that if you only use three colors, then it is impossible to find such a coloring. To this day it is unknown which of 4, 5, 6, and 7 is the moment which it switches from impossible to possible.
If instead, you wanted to color the corners of a square, cube, or higher dimensional cube, you can ask a similar question: if you have an n-dimensional cube, it has 2n corners, and if you were to color all the edges of the cube, including diagonals, will you inevitably find a square whose edges are all the same color? In 1971, Ron Graham and Bruce Rothschild showed that if n is large enough, the answer is yes! Once again, structure emerges once an object is large enough.
How large? That is the rub. Typically a result in Ramsey theory tell you that the structure must be “large enough”, but quantifying what that means can be tricky. If you’re lucky, you get an explicit bound (like Ramsey’s original six people) or some reasonable range (like for coloring the points of the plane). In the case of coloring the vertices of a cube, the answer is somewhere between six and Graham’s number. The good news is that Graham’s number is an honest-to-goodness, actual, computable number like 12 or 137. The bad news is that Graham’s Number is larger than all the particles in the observable universe!
There is yet another flavor of Ramsey theory which comes from number theory. In this case, we are looking for structure within the counting numbers:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …
An early example of this is Schur’s Theorem. It tells us that if you sort these numbers into a finite collection of groups, then one of those groups must contain three numbers, two of which sum up to the third. In fact, if you tell me how many groups you plan to use, I can already find those three numbers in the collection:
1, 2, 3, 4, 5, 6, 7, …., N-1, N,
where, of course, how size of N depends on how many groups you use. It was only in 2017 that we finally computed that if you use five groups, then N=161. For six or more groups, we know there is such an N, but have no idea what it is!
Another sort of structure in the counting number is an arithmetic progression. This is a sequence of numbers that are equal distance apart on the number line. For example, 3, 5, 7, 9, 11 is a length four arithmetic progression of distance 2. Similarly, 7, 32, 57 is a length three arithmetic progression of distance 25. Arithmetic progressions are one of the simplest structures you could study in the counting numbers. For example, if you’re interested in addition, then you naturally end up caring about arithmetic progressions as they are what you get from adding the same number over and over.
Inspired by the cube problem, you can ask about coloring the counting numbers and when that leads to arithmetic progressions where all the numbers have the same color. Nearly a century ago, Van der Waerden proved that if you are looking for an arithmetic progression of length k and allow yourself some number of colors, then there is always a number M so, no matter how you choose to color the numbers
1,2, 3, 4, 5, 6, 7, …, M-1, M
you will always find a monochromatic arithmetic progression of length k. As with Schur’s Theorem, the number M depends on k and on the number of colors you choose to use. Once again, computing M is devilishly difficult!
Fifteen years ago, Ben Green and Terry Tao proved a now-famous theorem which has a similar flavor. Instead of looking at all counting numbers, they looked at only the primes:
2, 3, 5, 7, 11, 13, 17, 19, ….
The Green-Tao Theorem tells us that you can find arithmetic progressions in the prime numbers of any length you like. This was one of the results which led to Tao receiving the Fields medal.
There is a famous conjecture by Paul Erdős along these lines. Paul Erdős was arguably the most famous mathematician of the twentieth century. He was particularly well known for posing insightful problems in Ramsey theory and other areas of discrete mathematics and for offering cash prizes for their solution. Ernst Strauss once described Erdős as “the prince of problem solvers and the absolute monarch of problem posers”. We ran into Erdős here at 3QD when we discussed Terry Tao’s solution of the Erdős discrepancy problem (a $500 Erdős problem which went unsolved for 80+ years).
The Erdős conjecture on arithmetic progressions is a $5000 problem. Say you have a list of counting numbers:
a1, a2, a3, a4, a5, ….
And say the list satisfies
That is, if you add more and more of the reciprocals of the numbers from the list, the sum grows larger and larger without bound. An example of such a list is the prime numbers, but there are many more. Importantly, not every infinite list has this property! For example, the powers of two (2, 4, 8, 16, 32, …) fails to satisfy this requirement. You should think that this property somehow captures the fact that the list of numbers is not too sparse. While both the primes and the powers of two are infinite lists, the powers of two are very sparse compared to the primes.
Erdős conjectured that every such list of numbers has arithmetic progressions of every possible length. Once again we learn that if your structure is sufficiently large, order inevitably emerges.
The conjecture is generally believed to be true but seems out of reach of even our best techniques. It’s going to require a real breakthrough. Erdős agreed. After all, he offered $5000 for the solution!
However! Last Tuesday Thomas Bloom and Olof Sisak posted a preprint on the arXiv where they announce the first real progress on the Erdős conjecture for arithmetic progressions [2]. They proved that any such sequence of numbers has an arithmetic progression of length three.
This may sound unimpressive. After all, they are simply saying that the infinite list contains three numbers that are equal distance apart on the number line. But that is order, and it appears in any list of numbers which isn’t too sparse. Also keep in mind this is the first result on an 80 year-old conjecture which many brilliant people have worked hard to prove. I’m sure Terry Tao has spent more than a few afternoons wrestling with Erdős’s conjecture.
Because it’s 2020, no good news can arrive without some bad news. The day before Bloom and Sisak’s paper was announced, Ron Graham passed away. He was the Graham of Graham Number fame. Graham was a good friend and collaborator of Paul Erdős and one of the giants of Ramsey theory. He would have loved to learn of the breakthrough by Bloom and Sisak. I hope he had a chance to hear about it.
The trouble with integers is that we have examined only the very small ones. Maybe all the exciting stuff happens at really big numbers, ones we can’t even begin to think about in any very definite way. Our brains have evolved to get us out of the rain, find where the berries are, and keep us from getting killed. Our brains did not evolve to help us grasp really large numbers or to look at things in a hundred thousand dimensions.
— Ron Graham
Graham was widely known to not only be brilliant, but also a friendly and kind soul who was widely liked across mathematics. He published over 350 papers in Ramsey theory, combinatorics, number theory, probability, and many other areas of discrete math. He was instrumental in both developing math for math’s sake and for finding connections to real-world problems. His work could fill years’ worth of 3QD essays. We will surely return to his work in the future.
For now, let me recommend this very nice 20-minute video about Ron Graham. It will give you a real appreciation of him as a mathematician and as a person.
[1] Groups of six or more? Obviously, this is pre-Covid-19,
[2] The usual caveat applies: this paper is a preprint and it remains to be seen if it holds up to scrutiny. But the methods used in the paper are in the mainstream and experts seem optimistic that it’ll check out.