Two mathematicians prove the first stage of Erds' favorite conjecture about patterns in sequences of numbers
A couple of mathematicians proved the first part of one of the most famous hypotheses concerning the additive properties of integers. It was proposed more than 60 years ago by the legendary Hungarian mathematician Pal Erdos . It sounds like this: at what point in an infinite list of integers are guaranteed patterns of at least three numbers spaced at the same distance from each other - for example, 26, 29 and 32.
Erdos has formulated thousands of problems during his career, but the question is, which list of numbers contains numbers that are equidistant from each other (what mathematicians call arithmetic progressions) was one of his favorites. “I think a lot of people saw this as Erds' main concern,” said Timothy Gowers of the University of Cambridge. Gowers, who receivedFields Prize in 1998, spent many hours trying to solve this problem. “Virtually all fairly ambitious additive combinatorics have tried to solve it,” he said, referring to the branch of mathematics to which this hypothesis belongs.
Denser lists of numbers are generally more likely to contain an arithmetic progression than sparse ones. Therefore, Erdos suggested a simple check for the density of a list: add the inverse values of those in the list. If there are enough numbers to make this sum infinite, then, according to Erdos' assumption, the list should contain an infinite number of arithmetic progressions of any finite length - three, four, etc. numbers in a row.
In a paper published online on 7 July by Thomas Bloom of Cambridge and Olaf Sisaskfrom Stockholm University proved this hypothesis in the case of evenly spaced triplets of numbers - such as 5, 7 and 9. This pair showed that when the sum of reciprocals to the numbers in a list is infinite, there must be infinitely many triples of equally spaced numbers in it.
Thomas Bloom of Cambridge
“This is the most remarkable result in many years,” said Nets Katz of California Institute of Technology. "This is a significant event."
One of the sets, the sum of reciprocal numbers to which tends to infinity, are prime numbers - those that are divisible only by 1 and themselves. In the 1930s Johannes van der Corputused a special structure of primes to show that in them indeed you can find an infinite number of equally spaced triplets (for example, 17, 23 and 29).
However, Bloom and Sisask's new discovery means that one does not need to deeply understand the unique structure of primes in order to prove that they contain an infinite number of triples. It is enough to know only that there are enough primes for the sum of their reciprocal values to be infinite - and this has been known to mathematicians for many centuries. “The result of Thomas and Olaf tells us that even if their structure was completely different from what they actually have, the mere fact of having a large number of them would guarantee infinity of arithmetic progressions,” Tom Sanders wrote to usfrom Oxford University.
The new work is 77 pages long, and it will take some time for mathematicians to thoroughly check it. However, many are optimistic about it. “It really looks like the proof of this claim should look like,” said Katz, whose early work formed the basis for this.
Bloom and Sisask's theorem says that if the list of numbers is dense enough, certain patterns should appear in it. This discovery is consistent with the fundamental motto of mathematics, as Sarah Pillus of Oxford calls it , first formulated by Theodore Motzkin: "There is no absolute disorder."
Disguised density
It's pretty easy to create an infinite list without arithmetic progressions if you make it sparse enough. For example, consider the sequence 1, 10, 100, 1,000, 10,000, ... The reciprocals add up to 1.111 (1). The distance between these numbers grows so quickly that not a single triplet of numbers located at an equal distance from each other can be found.
However, you may be wondering if there is a denser list of numbers that still doesn't have arithmetic progressions. You can, for example, walk along a number line and leave every number that is not included in arithmetic progressions. We get the sequence 1, 2, 4, 5, 10, 11, 13, 14, ... which at first glance looks rather dense. However, over time, it becomes more and more sparse - for example, when we get to 20-digit numbers, we will take only 0.000009% of all integers from the number line. In 1946, Felix Berend came up with denser examples, but they also become sparse very quickly - the Berend set, reaching 20-digit numbers, contains only 0.001% of all integers.
On the other hand, if your set contains almost all integers, then it will definitely contain arithmetic sequences. But between these two extremes lies a vast, almost unmarked middle territory. How sparse can a set be, mathematicians speculated, so that arithmetic progressions could still be guaranteed there?
Olaf Sisask from Stockholm University
Erdos (as they say, possibly in conjunction with the Hungarian mathematician Pal Turan) gave one possible answer. Its condition for the sum of reciprocals is the masked density. It turns out that this is the same as saying that the density of a list up to the number N is not less than one divided by the number of digits in N. In other words, your list may become more and more sparse as you move along the number line, but only if it happens very slowly. On 5-digit numbers, the density of your list should be at least 1/5; on 20 digits - at least 1/20, and so on. And if this condition is met, then, as Erdos suggested, your list should contain an infinite number of arithmetic progressions of any length.
In 1953, Klaus Roth set mathematicians on the path leading to the proof of Erds' conjecture. In a paper that earned him a Fields Prize that year, he defined a density function that guarantees equidistant triplets of numbers. The density was not as low as that of Erds, but nevertheless it approached zero as we moved along the number line. Roth's theorem meant that in the list of numbers whose density ultimately drops below 1%, and then below 0.1%, and then below 0.01%, and so on, there must be arithmetic progressions, if only its density drops enough slow.
Pal Erds lecture “60 Years in Mathematics” at the University of Cambridge in June 1991.
First of all, Roth's approach was based on the fact that most of the lists with the density he chose "want" to have arithmetic progressions - they have enough different pairs of numbers so that almost certainly some of the midpoints between these pairs also appear on this list, which would lead to the appearance of equally spaced triplets. The trick is how to go from a list of “almost all” numbers to a list of “all” numbers, even though the entire structure could have been specially designed to avoid arithmetic progressions.
Having received such a list, Roth figured out how to "distill" its structure by marking up its "frequency spectrum" using the Fourier transform... It shows which of the emerging patterns are most pronounced - the same mathematics underlies technologies such as X-ray crystallography and radiospectroscopy.
Some frequencies appear stronger than others, and these variations emphasize existing patterns - for example, frequency may indicate that the list contains more odd numbers than even ones. If so, then you can concentrate only on odd numbers, and get a denser list compared to a list of only odd numbers. Roth was able to show that after several such distillations, a list would be so dense that arithmetic progressions would have to be present in it.
Roth's approach has inspired many papers in analytical number theory over the past fifty years, says Jacob Fox of Stanford University. "His ideas were very influential."
Game, set, match
However, Roth's method worked only for those sets of numbers that were already quite dense from the beginning - otherwise, constant distillations would simply evaporate all the numbers. Other mathematicians constantly found ways to use this method more and more effectively, but they could not come close to the density described in the Erds hypothesis. “This obstacle looked very difficult,” Fox said.
Then in 2011, Katz and Michael Bateman figured out how to overcome this obstacle in simpler terms: in the card game Seth, where players search for sets of three cards marked with different symbols. Three from the Set game can be defined as an arithmetic progression, and, as in the case of a list of integers, you can ask how much of all cards you need to lay on the table in order to find at least one three for sure.
Game Set
The object of the game is to find special triplets of cards, or "sets", in a deck of 81 cards. Each card has its own drawing with four properties - color (red, purple, green), shape (oval, rhombus, wave), shading (outline, stripes, completely filled in) and the number of shapes (one, two or three). In normal play, 12 cards are dealt face up on the table, and players look for sets of three cards in which each of the four attributes is either the same for all cards or different for all cards. If there are no such sets among the 12 cards, more cards are added.
Whole deck
, –
| ? |  |
 |
 |
 |
An easy way to collect a large enough set of cards without triplets is to only take cards that have only two or three choices for each attribute. The size of this collection will be (2/3) n of the entire deck, where n is the number of attributes.
This question (related not only to the standard Set game, but also to its larger versions) is a natural model for studying the corresponding question regarding integers. Therefore, mathematicians hoped that the breakthrough of Bateman and Katz could open the way to a proof of Erds conjecture, especially when combined with other recent breakthroughs . Soon after the release of Bateman and Katz's work, Gowers launched the " polymath project"- a massive joint collaboration was designed to make the attempt.
However, the project quickly stalled" In it gathered a huge amount of technical arguments, - he said Gowers -. This project is more suitable for one or two people, for a long time and slowly working on it. ".
By Fortunately, a couple of mathematicians were just getting ready for this. Bloom and Sisask, at first separately, already began to ponder the Erds hypothesis, captivated by the beauty of the techniques used in it. "This was one of the first research problems that I faced," - said Sisask , who, like Bloom, is now about 35 years old.
Bloom and Sisask joined forces in 2014, and by 2016 they decided they were close to a solution. Bloom even announced this in his lecture, and only after that he discovered that some of the workarounds they found turned out to be wrong. The couple continued to work, diving into the method of Bateman and Katz, and eventually realized what new ideas would allow them to transfer this method from the world of Seth to the world of integers.
The new work appears to be correct from every angle, Katz said. “I didn’t believe their previous statements, but I do believe this.”
Bloom and Sisask's work is "a tremendous achievement," Fox said. They and other mathematicians are anxious to find out if the techniques from the new work apply to other problems. “I think these methods will have a huge impact on mathematics,” Fox said.
As for Erds' hypothesis as a whole, work on it is still far from complete. Bloom and Sisask proved this hypothesis only for equally spaced triplets of numbers, but not for longer arithmetic progressions - this task is still out of reach.
And even the question with threes, which Bloom and Sisask have already closed, in the opinion of many mathematicians, does not particularly help. As difficult as it is to prove that Erds density guarantees equidistant triplets of numbers, mathematicians suspect that the actual density at which this guarantee stops working is much lower - perhaps slightly higher than the density of the sets that Berend designed.
“This is not to say that we have completely solved this problem, - said Bloom. "We shed a little more light on her."
Bloom and Sisask have probably squeezed the best out of current methods, Fox said. “There should be some completely new tools that will allow us to move much further and get a dramatically better result,” he said. However, "this is probably not the end of the story."