Credit: Corey Brickley for Quanta Magazine.
In 1983 the prolific conjecturer Paul Erdős posed a math problem: Take any set of numbers you like. These could be the whole numbers from 1 to 12, the first 10,000 prime numbers, or the dates of every birthday in your extended family. Arrange these numbers in a square grid, with your list of numbers arranged both across the bottom and up one side. Then fill in the grid with either the sums or the products of the crosswise pairs.
Erdős and his collaborator on the problem, Endre Szemerédi, were interested in the number of distinct entries in such a grid. (By “distinct,” they meant that if a number appears twice — for instance, if the number 4 appears as a product of both 1 × 4 and 2 × 2 — you only count it once.) They conjectured that the number of distinct entries in either the sum or the product grid (or both) must be at least a certain value. They even established an exact threshold that the number of distinct sums or distinct products always had to meet.
Put more generally, the conjecture says that the additive and multiplicative properties of a set of numbers somehow force each other to behave in a certain way. If we flip the problem around and look at the number of duplicate entries, it says the following: If there are a lot of duplicates in the sum grid, then there cannot be that many duplicates in the product grid (and vice versa). It’s as if the sum and product sets are magnetically charged to repel each other.
And like magnetism, the phenomenon is easy to observe but much harder to explain. “It somehow delves into the deep structure of the integers, meaning the interplay between multiplication and addition,” said Kevin Ford, a mathematician at the University of Illinois, Urbana-Champaign, who has worked on the problem.
Over the last few decades, mathematicians have clawed their way toward proving Erdős and Szemerédi’s threshold. In a 2018 paper, a graduate student at Urbana-Champaign named George Shakan came the closest yet.
Decoding a Progression
The most familiar grid in arithmetic is the times table. Write out the numbers 1 to 12 along the bottom and up the side and fill out the grid accordingly. If you compare the grid of products with the grid of sums, you might notice that there are many more distinct products than distinct sums.
Erdős and Szemerédi certainly did. At the same time they proposed their conjecture, they solved a special case of the problem. They showed that whenever the numbers used to generate the grid are consecutive (such as 1 through 12), the number of distinct sums will be 2N − 1, where N stands for the number of numbers used to generate the grid. The number of distinct products, however, will be much larger — more on the order of a constant value times N2.
But Erdős and Szemerédi’s “sum-product” problem went far beyond the case of consecutive numbers. They proposed that no matter what set of numbers you use to generate your grid — whether the numbers are consecutive or nonconsecutive, powers of 2 or county-by-county vote totals — either the number of distinct sums, the number of distinct products, or both has to be close to N2.
This basic observation has significant implications. In the field of number theory, mathematicians study different types of sequences of numbers. One is the sequence you construct by starting with a number and repeatedly adding to it multiples of some second number. So if your starting number is 2, and your second number is 3, you’d construct your sequence as: 2, 2 + (3 × 1), 2 + (3 × 2), 2 + (3 × 3), 2 + (3 × 4), and so on. Or: 2, 5, 8, 11, 14, etc.
This kind of sequence is called an arithmetic progression. It figures in many important conjectures in number theory and can arise through far more complicated procedures than the one described above. Sometimes mathematicians confront a sequence of numbers and are unable to tell straightaway whether it’s an arithmetic progression.
Yet if you use numbers from an arithmetic progression to generate a grid, the number of distinct sums is always small. And that means that if you’re handed numbers whose sum grid has few distinct entries, it’s a good bet those numbers are closely related to an arithmetic progression.
“There’s a sort of expectation that any time you have a set whose sum set is not much larger than itself, there’s an arithmetic progression around,” said Nets Katz, a mathematician at the California Institute of Technology who has worked on the sum-product problem.
Another type of numerical sequence is made by taking two numbers and repeatedly multiplying the first number by powers of the second number. So if your numbers are 2 and 3, you’d construct your sequence as: 2 × 30, 2 × 31, 2 × 32, 2 × 33, 2 × 34, and so on. Or: 2, 6, 18, 54, 162, etc. This kind of sequence is called a geometric progression.
In general, grids produced from geometric progressions have few distinct products, but many distinct sums, whereas grids produced from arithmetic progressions will have the opposite property: few distinct sums, but many distinct products. (For grids produced by sets of numbers chosen at random, you’d expect many distinct sums and many distinct products.)
So the sum-product conjecture, which says that no set of numbers can produce a grid with simultaneously few distinct sums and few distinct products, is really making a statement about the relationship between arithmetic and geometric progressions.
“What the conjecture is really about is asking, ‘Can a set look both like an arithmetic progression and a geometric progression at the same time?’ And the answer is, ‘No, it can’t, because these are very different objects,’” Ford said.
And one way to prove that they’re very different objects is to prove that Erdős and Szemerédi’s threshold holds for any set of numbers.
Translating the Problem
A complete solution to the sum-product problem would establish that the number of distinct sums or products is always very close to N2. So far, mathematicians have not succeeded in proving this. Instead, they have engaged in a Lilliputian race over the last several decades: In 1997 György Elekes proved that the number of distinct products or sums must be at least N5/4; in 2009 Jozsef Solymosi proved it must be at least N4/3; seven years later Misha Rudnev, Ilya Shkredov and Sophie Stevens improved the exponent to 4/3 plus a little bit more. (A very little bit. Their exponent was 4/3 + 1/1509.)
But it was the Elekes result that really defined how mathematicians approach the problem. In that 1997 paper he developed a strategy that’s been followed by most everyone since. Using techniques from a field called incidence geometry, Elekes showed how the question of sums and products can be translated into a question about how lines intersect points on the plane.
The strategy has you convert the sum and product grids into grids in the plane. Take the distinct sums in your sum grid and mark them along the x-axis. Take the distinct products in your product grid and mark them along the y-axis. Then mark the points where every x-axis value intersects with every y-axis value. If your set is {1, 2, 3}, you’ll plot 30 points in a 5-by-6 grid.
Next, draw lines in the plane. The lines will be of the form y = a × (x − c), where a and c come from the original numbers used to produce the grids (in our case, the numbers 1, 2 and 3). This process will yield nine distinct lines, which traverse the space in the plane where you’ve plotted the 30 points.
The question of interest is how often those nine lines intersect the 30 points. Elekes showed that the number of distinct sums or products in a grid is inversely related to the number of intersections yielded by the point-line procedure. Therefore, if you can show that there are few intersection points, you’ve proved that the underlying set has many distinct products or sums or both.
“You’re thinking about sums and products and all of a sudden you’re drawing points and lines,” Shakan said. “It’s not obvious there should be any connection, but there is.”
In his 2018 paper, Shakan elaborated the point-line approach to wring an
even larger exponent from Elekes’ method, proving that the number of
distinct sums or products (or both) must be at least
Almost a year later [this article was written in 2019], Shakan’s record still stands, though a full solution to the sum-product conjecture is as far away as ever. Using Elekes’ method, mathematicians have been making progress at an incremental pace that seems unlikely ever to get them all the way there. For that, wholly new ideas are called for.
“Addition and multiplication are two of the most basic operations in math,” Shakan said. “It shows how ignorant we are, because we can’t say everything about this problem.”
Kevin Hartnett is a senior writer at Quanta Magazine covering mathematics and computer science.