First-Year Graduate Student Finds Paradoxical Set
Maggie Chiang for Quanta Magazine
Introduction
Mathematicians rejoice when they prove that seemingly impossible things exist. Such is the case with a new proof posted online in March by Cédric Pilatte, a first-year graduate student at the University of Oxford.
Pilatte proved that it is possible to create a set — a collection of numbers — that satisfies two apparently incompatible properties. The first is that no two pairs of numbers in the set add up to the same total. For example, add together any two numbers in {1, 3, 5, 11} and you’ll always get a unique number. It’s easy to construct small “Sidon” sets like this one, but as the number of elements increases, so too does the likelihood that the sums will coincide, destroying the Sidon-ness of the set.
The second requirement is that the set must be very large. It must be infinite, and you should be able to generate any sufficiently large number by adding together at most three numbers in the set. This property, which makes the set an “asymptotic basis of order 3,” requires a large, dense set of numbers. “They’re pulling in opposite directions,” Pilatte said. “Sidon sets are constrained to be small, and an asymptotic basis is constrained to be large. It was not obvious that it could work.”
The question of whether such a set exists has lingered for decades, ever since it was posed by the prolific Hungarian mathematician Paul Erdős and two collaborators in 1993. Erdős’ fascination with Sidon sets can be traced to a conversation he had in 1932 with their inventor Simon Sidon, who at the time was interested in understanding the growth rate of these sets. (Erdős would later describe Sidon as “crazier than the average mathematician,” which he almost certainly meant as a compliment.)
Sidon sets arise in a variety of mathematical contexts including number theory, combinatorics, harmonic analysis and cryptography, but the simple question of how big they can get has been an enduring mystery that Erdős pondered for much of his career. Erdős realized early on that Sidon sets are extremely hard to scale. In 1941 he and another mathematician proved that the largest possible Sidon set whose members are all less than some integer N has to be smaller than the square root of N plus a term that grows in proportion to the fourth root of N. (By 1969, Bernt Lindström would show that it is smaller than $latex \sqrt{N}+\sqrt[4]{N}+1$, and in 2021 another group of mathematicians tightened the bound to $latex \sqrt{N}+0.998 \times \sqrt[4]{N}$.) Sidon sets, in other words, have to be sparse.
It has long been known that a Sidon set cannot be an asymptotic basis of order 2, where any integer can be expressed as the sum of at most two numbers. (The odd numbers, for example, form a basis of order 2.) As Pilatte explained, this is so simple to show that mathematicians didn’t bother to write it down: “That order 2 is impossible was probably known much earlier than it was explicitly written in the literature.” He explained that this is because “Sidon sequences cannot exceed a certain density, while asymptotic bases of order 2 are always denser than that threshold, so the two properties cannot hold at once.”
It was generally believed that an asymptotic basis of order 3 could be constructed from a Sidon set, but proving this was another matter. “People believed this should be true,” said Pilatte’s adviser James Maynard. “But there was a difficulty with the techniques we were using.”
Some progress had been made before Pilatte took up the challenge. In 2010, the Hungarian mathematician Sándor Kiss showed that a Sidon set can be an asymptotic basis of order 5 —meaning that any sufficiently large integer can be written as the sum of at most five elements of the set — and in 2013 Kiss and two of his colleagues proved the conjecture for an asymptotic basis of order 4. Two years later, the Spanish mathematician Javier Cilleruelo took these results a step further by proving that it is possible to construct a Sidon set that is an asymptotic basis of order 3 + ε, meaning that any sufficiently large integer N can be written as the sum of four members of the Sidon set, with one of them smaller than Nε for arbitrarily small positive ε.
“You would need an understanding of prime numbers that goes beyond anything we have,” said Cédric Pilatte, a first-year graduate student who proved a long-standing conjecture of Erdős. “So that was not good.”
Evan Nedyalkov
These findings were obtained using variations of a probabilistic method pioneered by Erdős that involves generating a random set of integers and tweaking it slightly to create a set that satisfies both properties.
Pilatte realized that the probabilistic method had been pushed as far as it could go. “You can get a basis of order 4 by using probabilistic methods, but you can’t get a basis of order 3,” he said. “It just fails.”
So Pilatte took a different tack, turning instead to a procedure that uses the logarithms of prime numbers as the building blocks of Sidon sets. Developed by the Hungarian number theorist Imre Ruzsa and Cilleruelo, this approach yields bigger, denser Sidon sets than the probabilistic method, which Pilatte needed to create a basis of low order that also obeyed the Sidon property. But the method required a facility with prime numbers that even the world’s foremost experts lacked. “You would need an understanding of prime numbers that goes beyond anything we have,” Pilatte said. “So that was not good.”
The search for a solution took Pilatte in an unexpected direction, away from additive number theory and into the world of algebraic geometry, a branch of mathematics that studies the relationship between geometric shapes, like curves and surfaces, and the equations that define them. Employing an idea of Cilleruelo’s, Pilatte began by replacing numbers with polynomials, which immediately made the problem more tractable.
A polynomial is an algebraic expression made up of a sum of terms, each of which is a product of a constant coefficient and one or more variables raised to nonnegative integer powers. The terms can be combined using addition, subtraction and multiplication. For example, 3x2 + 22x + 35 is a polynomial with three terms. Factoring a polynomial means breaking it up into a product of other, simpler polynomials. In this example, 3x2 + 22x + 35 = (x + 5)(3x + 7). An irreducible polynomial — one that can’t be factored — is the analogue of a prime number.
Swapping integers for variables and coefficients might sound strange, but they have more in common than you might think. “It turns out that polynomials behave very similarly to the integers,” said Pilatte’s Oxford colleague Thomas Bloom. “I can add them, subtract them, multiply them, divide them.” And in some respects mathematicians understand polynomials far better than they do numbers. “All these things that, with primes, sound like science fiction to us are known in the polynomial world,” Maynard said.
Using a recent result by the Columbia University mathematician Will Sawin on the distribution of irreducible polynomials in arithmetic progressions, Pilatte was able to construct a set that possessed just the right amount of randomness and just the right density of numbers to satisfy Erdős’ constraints.
“I was extremely happy,” Pilatte said. “I’m joining the group of people here that have solved an Erdős problem, and it’s fun.”
But what delights him most is the surprising way he arrived at the solution. “It’s cool that these very deep techniques from algebraic geometry can also be used for this simple and concrete question about sets of numbers,” he said.
Erdős problems have an uncanny knack for unearthing connections between supposedly unrelated branches of math, and the discoveries mathematicians make while trying to answer them are often more meaningful than the answers themselves. “They’re deceptive in how deep they are, and Cédric’s solution is a great example of this,” Bloom said. “I’m sure Erdős would have been thrilled.”
Correction: June 5, 2023
This article originally gave an example of a Sidon set that is not actually a Sidon set. That example has been removed.
