Structure is everywhere. So is chaos.

Pick 45 numbers between 1 and 100. Try to avoid creating pairs whose difference is the square of some number and you will fail. Always.

Hungarian mathematician Paul Erdős was famous for making bold conjectures: precise mathematical statements that have not yet been proved but which are believed to be true. Among his personal favorites is a conjecture that implies that there should exist extremely long, super regular patterns among the prime numbers: whole numbers divisible only by themselves and 1. These patterns, called arithmetic progressions, are collections of increasingly large numbers that keep growing by the same 'step'. For example

$5, 11, 17, 23, 29.$

"A mathematician is a device for turning coffee into theorems." Paul Erdős

This is a five-term arithmetic progression with step 6 consisting entirely of prime numbers. The full collection of prime numbers, however, seems to refuse to behave in any reasonably predictable way, as if they were selected from the natural numbers (1, 2, 3, 4, etc.) based on the outcomes of random coin tosses. And so it could at first sight seem surprising that they should contain such regular patters. But a moment's reflection can evaporate some of the contradictory feel of these statements.

Suppose you have a coin that lands on heads with 10% chance and tails with 90% chance. For each number between 1 and 1000, flip the coin, pick the number on heads and ignore it on tails. The result is a randomly chosen set, or random set. Some characteristics will be extremely likely: It will most probably have about 100 numbers. It typically has roughly equal parts even and odd numbers. But it will also likely have fairly long arithmetic progressions!

Why? Take the 3-term arithmetic progression 3, 5, 7 (with step 2). Each of these three numbers is picked with 10% chance independently from the others. This means that the whole triple is picked with 0.1% chance. Not much, but not negligible. Because this is true for every one of the 3-term arithmetic progressions, the chance that the random set contains no 3-term arithmetic progression will be absolutely tiny. Random sets therefore typically have long arithmetic progressions (even many).

Back to the primes. The famous Riemann hypothesis is a (still open) conjecture that roughly says that the set of primes numbers resembles a random set in a certain way. This may therefore be interpreted as an 'indication' that the primes indeed do contain long arithmetic progressions.

Erdős seems to have first voiced his conjecture somewhere in the early 1940's or mid 1950's, though it appeared in print only much later.

"God may not play dice with the universe, but something strange is going on with the prime numbers."
Paul Erdős

Mathematician Ben Green.

This conjecture, which was likely already pondered by mathematicians as early as the 18th century, was more general and did not concern only the prime numbers. It states that any increasing sequence $a_1, a_2, a_3,\dots$ of whole numbers that has the property that the sequence of partial sums of reciprocals $\frac{1}{a_1}, \frac{1}{a_1} + \frac{1}{a_2},$ $\frac{1}{a_1} + \frac{1}{a_2} + \frac{1}{a_3}, \dots$ goes off to infinity, contains long arithmetic progressions. The primes are an example of such a sequence.

For the case of the prime numbers the conjecture was finally proved to be true many decades later in a now celebrated 2004 paper of Ben Green and Terence Tao. The more general conjecture is still wide open and was only confirmed very recently for 3-term arithmetic progressions in breakthrough work of Thomas Bloom and Olof Sisask.

Erdős Conjecture

Suppose an increasing sequence of whole numbers $a_1, a_2, a_3, \dots$ has the pro- perty that the sequence of partial sums of reciprocals $\frac{1}{a_1},$ $\frac{1}{a_1}+\frac{1}{a_2},$ $\frac{1}{a_1}+\frac{1}{a_2}+\frac{1}{a_3},\dots$ goes off to infinity. Then this sequence contains arbitrarily long arithmetic progressions.

Green-Tao Theorem

The prime numbers contain contain arbitrarily long arithmetic progressions. Settles the conjecture for the sequence of prime numbers $2, 3, 5, 7,\dots.$ .

We know that $\frac{1}{2} + \frac{1}{3} + \frac{1}{5} +\dots = \sum_{p \text{ is prime}} \frac{1}{p} = \infty.$

Result of Bloom - Sisask

Any sequence $a_1, a_2, a_3,\dots$ satisfying the condition must contain an arithmetic progression of length 3. This result was proved in 2020. Some exciting quantitative improvements of this result were proved early this year.

The Green-Tao theorem is one of the centerpieces of a relatively new and thriving area of mathematics called additive combinatorics. Characteristic of this field is that it brings together basic ideas and techniques from a large variety of more classical areas such as analysis, probability theory, number theory, in addition to the newish area of combinatorics. A particularly attractive feature of this field is that it does not require years of study to even understand the statements of the main results or the ideas behind their proofs. Yet it has attracted some of the greatest mathematicians of our time.

Mathematician Terence Tao.

Somehow over the last century, the relatively small country of Hungary cultivated a disproportionate number of superb mathematicians, including Pál Turán and Endre Szemerédi and of course Paul Erdős. Exactly how this happened is a matter of ongoing spirited debate and speculation.

Mathematician Endre Szemerédi.

The Green-Tao theorem might not have been proved in our lifetime were it not for a pivotal precursor of their result: Szemerédi's theorem. In 1975 Endre Szemerédi proved that for any progression length $k$ , there is a number $N$ so that not just random sets, but any collection containing 0,01% of the numbers between 1 and $N$ will have a $k$ -term arithmetic progression. Try to collect 0,01% of the numbers between 1 and $N$ explicitly so as to avoid long arithmetic progressions and you will fail. Always! Szemerédi's theorem settled a conjecture posed by Erdős and Pál Turán sometime in the 1930's.

Szemerédi's original proof applied the intuition gained from the example of random sets. If there is some way to 'massage' a given 0,01%-sized set to look somewhat like a random set, then we would seem to be in good shape to show that it, like a truly random set, contains at least one long arithmetic progression. A highly innovative step in Szemerédi's work was to find a way to knead out some randomness from any arbitrarily assembled set of integers.

To study 3-term arithmetic progressions, there is a natural translation from a set of whole numbers to a graph. A graph is nothing more than a collection of points, some of which are connected by a line, or edge. A graph can thus represent a social network, indicating who is friends with whom, for example. A big set of whole numbers will result in a graph with many edges.

Szemerédi showed that as long as there are many edges, then any graph can be broken up into a very small number of pieces so that the connections between most of those pieces look as though they were randomly chosen. They may not have been, but they will have some properties that are typically expected if they had been. Properties that precisely allow you to argue that the original set of integers has about as many 3-term arithmetic progressions as one would expect from a random set.

In the following animation we show how Szemerédi's result works on a certain graph.

A visualization of Szemerédi's result developed by Martijn Gösgens. The graph can be broken up into pieces so that the connections between most of those pieces look as though they were randomly chosen.

Szemerédi's theorem serves as a "Rosetta stone" connecting various fields.
Terence Tao

Although Szemerédi's proof for 3-term arithmetic progressions was elegant and clean, generalizing his ideas to suit longer progressions turned out to be very complicated and messy. For this reason, he himself advocated the search for a different proof. His wish was granted and then some. Two other arguments were found from vastly different areas of mathematics. One from ergodic theory (by Hillel Furstenberg), an area originating from the theory of dynamical systems (describing for instance the choreography of celestial bodies) and another from Fourier analysis (by Timothy Gowers), used to decompose complicated signals into sums basic wave components (like a musical chord into the individual notes). With Szemerédi's theorem as their focal point, surprising commonalities were found in the combinatorial, ergodic and Fourier analytic proofs. In turn, this allowed for a translation of various techniques between these areas.

Mathematicians Hillel Furstenberg and Timothy Gowers.

Aside from the open problem mentioned above, there are many other tantalizing problems posed by Erdős that remain unsolved today, many with cash rewards for their resolution. A website keeping track of solved and unsolved Erdős problems was recently created by Thomas Bloom and Sang-il Oum. There is still so much to discover!

Would you like to stay up to date when a new post appears on the Network Pages?

Subscribe to our mailing list