Paul Erdős made many conjectures about numbers in his life
Oliver Helbig/Getty Images
Just a week after an AI disproved an 80-year-old conjecture and astonished mathematicians, another conjecture that had stood for half a century has fallen, inspired by the same techniques, but this time written entirely by humans.
Last week, an unreleased AI model from OpenAI disproved an important conjecture first posed by Hungarian mathematician Paul Erdős, called the unit distance problem. The puzzle, which Erdős considered his “most striking contribution to geometry” and which many mathematicians had failed to unravel, concerns the number of similar-sized connections you can make between dots arranged on a flat surface.
Erdős had set an upper ceiling on this number, which many experts had assumed was correct. But the AI model showed that this number could in fact be much larger, using an obscure trick from algebraic number theory to make complex structures with extremely high dimensions, which could then be used to arrange the dots in a very different arrangement than humans had considered. The result took mathematicians by surprise, with some not expecting to see Erdős’s conjecture disproved in their lifetimes.
Now, less than a week later, Thomas Bloom at the University of Manchester in the UK and his colleagues have used a similar argument to disprove another famous claim, which Erdős had first posed in 1976, called the sum-product conjecture.
“It was a surprise because I had thought about the problem quite a bit,” says Bloom. After seeing the trick used by OpenAI’s AI, which used number theory to solve a geometric problem, Bloom and his team realised that they could try the same thing for the sum-product conjecture. “Once you know that something might be possible, you’re willing to try a bit harder to actually get it to work,” he says.
Erdős’s sum-product conjecture concerns collections of numbers, or sets. It says that if you either add or multiply all the numbers together in this set, one pair at a time, to create a further two sets, then at least one of these sets must be much larger than the original set – you can’t have both sets similarly small. For instance, if you multiply all the numbers from 1 through 5, you will have a larger set than if you add them all, because there will be duplicate results, such as 2+3 and 1+4. Considering a different set, such as 1, 2, 4, 8 and 16, the added set will instead be larger, because the multiplied set just contains various powers of two.
Erdős set a bar for how small the larger of the two added and multiplied sets could be, and conjectured this should hold for any set of numbers. But Bloom and his colleagues used the same high-dimensional trick to find a set where both its sum and multiplied are smaller than Erdős thought possible. Instead of using a geometric progression of numbers, like powers of two, you can create a progression of numbers in many different dimensions at the same time, which they found produces a set where the number of different sums you can make is much smaller.
“The real surprise for me was that it was so simple,” says Bloom. “The construction is so simple to describe and we do genuinely understand now why [Erdős’s conjecture] fails, which should help us with lots of other related problems as well.”
“This is typical for maths as a competitive sport,” says Misha Rudnev at the University of Bristol, UK. “As soon as a new idea kicks in, some people are ready to work twenty-four hours to find more applications to it, and these people are usually very good and quick.”
Rudnev says that Erdős’s original intuition was that this conjecture should mainly be true for integers, or whole numbers, and that still appears to be true, because the set found by Bloom and his team used exotic number systems that get ever more complicated as their sets grow larger. Bloom agrees that the conjecture still holds for integers, and that “there’s still a huge amount of work to be done; we don’t really understand what’s going on.”
The main insight from the proof is that problems that seem geometric, such as sets of square powers of two, can actually be tackled with tools from number theory, says Bloom. “It really opens these problems to a whole new community as well. People in algebraic number theory weren’t really engaging with these questions.”
Topics:
