Facebook
Twitter
Pocket
Reddit
Email
A team of mathematicians and computer scientists has finally made progress on a seemingly simple problem that has bedeviled researchers for nearly six decades.
Posed by the mathematicians Paul Erdős and Richard Rado in 1960, the problem concerns how often you would expect to find patterns resembling sunflowers in large collections of objects, such as a large scattering of points in the plane. While the new result doesn’t fully solve Erdős and Rado’s sunflower conjecture, it advances the mathematical understanding of how surprisingly intricate structures emerge out of randomness. To do so, it reimagined the problem in terms of a computer function—taking advantage of the increasingly rich interplay between theoretical computer science and pure mathematics.
“The paper is a new manifestation of a mathematical idea that’s going to be a central idea of our time. The result itself is spectacular,” said Gil Kalai of the Hebrew University of Jerusalem.
The sunflower conjecture is about sets, which are collections of objects. The conjecture is easiest to visualize if you think of sets of points in the flat xy-plane. First decide on a fixed number of points you want to include in each set. Then draw loops at random so that each loop, or set, encompasses that number of points. It’s OK if the loops overlap, so some points may end up inside more than one set, like the intersections in a Venn diagram.
If you draw many loops containing a large number of points, most of the loops will overlap and tangle like a snarl of brambles. But Erdős and Rado predicted that a delicate structure would invariably arise: Three or more sets would all partly overlap each other at exactly the same subset of points, and none of them would overlap any other sets.
If you were to delete that common subset of points, the three sets would be arrayed around a void, completely separate from each other—like petals around the dark center of a sunflower. For the purposes of the problem, the simplest kind of sunflower is considered to be one with three sets that don’t overlap each other or any other sets; these islands are called “disjoint” sets.
Erdős and Rado conjectured that as you draw more loops, a sunflower inevitably emerges, either as disjoint sets or as sets that overlap in just the right way. Their sunflower conjecture is part of a broader area of mathematics called Ramsey theory, which studies how order begins to appear as random systems grow larger.
“If you have a large enough mathematical object of some nature, there has to be some hidden structure inside it,” said Shachar Lovett of the University of California, San Diego, a co-author of the new work along with Ryan Alweiss of Princeton University, Kewen Wu of Peking University, and Jiapeng Zhang of Harvard University.
Erdős and Rado wanted to know precisely how many sets—of precisely what size—you need in order to be guaranteed a sunflower. They made a modest first step toward solving the problem by establishing a parameter, w, that stood for the number of points in each set. The pair then proved you need about ww sets of size w to be sure to find a sunflower made of three sets. So, if you want each set to contain 100 points, they proved you need on the order of 100100 sets to be guaranteed a sunflower.
“The paper is a new manifestation of a mathematical idea that’s going to be a central idea of our time. The result itself is spectacular,” says Gil Kalai of Hebrew University of Jerusalem.
At the same time, Erdős and Rado conjectured that the actual number of sets required to guarantee a sunflower is much smaller than ww—it’s more like a constant number to the w power (so 3w or 80w or 5,000,000w). Yet they couldn’t find a way to prove their intuition was correct.
“They said this problem looks extremely simple and were wondering why they couldn’t make progress on it,” Alweiss said.
They weren’t the only ones. Between Erdős and Rado’s first result and this new proof 60 years later, only two mathematicians made any progress on the question at all—and they only made incremental advances, one in 1997 and the other earlier this year.
“Everyone had tried all the ideas that people were comfortable with,” said Anup Rao of the University of Washington, who published a follow-up paper that simplified the methods behind this new result. “None of them seemed able to improve the basic bound Erdős and Rado proved.”
By contrast, the new proof is a major advance.
The four researchers—a mix of mathematicians and computer scientists—managed the feat by breaking the problem down into two distinct scenarios. In the first and easier scenario, they considered what happens when the sets have substantial overlap, which makes it relatively easy to understand when a sunflower has to appear.
“When you have a collection of elements that all belong to a large collection of sets, there is a structure you can exploit” to find a sunflower, Lovett said.
The researchers first ask whether there is a set of points that’s common to some large fraction of the total sets in the system. Once they’ve identified such a set of points, they restrict their search for a sunflower to the fraction of the total sets that contain this set of points. They proceed in this fashion, refining their search to include a smaller and smaller fraction of the total sets in the system that have more and more points in common. This pruning continues until they find a sunflower.
In the second and more difficult scenario, they analyze what happens when the sets don’t overlap much. In that case, the most likely way to produce a sunflower is to have three disjoint sets. But proving that three entirely separate sets hide among a large number of lightly overlapping ones isn’t easy.
That’s where the connection with computer science comes in. For several years, two of the co-authors—Lovett and Zhang—had been trying to analyze the sunflower problem using the same tools that computer scientists use to study a type of program called a Boolean function. These functions perform operations on a series of bits—1s and 0s—and output a single bit at the end, corresponding to whether the computational statement is true (1) or false (0). For example, a Boolean function might be programmed to output 1 if at least one of its input bits is a 1, and to output a 0 if none of the inputs is a 1.
Three years ago, Lovett and Zhang realized that the question of whether or not three disjoint sets are present among a collection of lightly overlapping sets could be considered in the same way. First, you assign each point in a particular set a label: 1 if it’s contained only in that one set, and 0 if it’s not. The Boolean function will then output a 1 (true) if every input point is a 1—meaning that every point in the set is exclusively in that set, making the set disjoint. A “true” result therefore indicates that the right conditions are present for you to find a sunflower.
By rigorously proving this correspondence, the researchers brought extensive knowledge about Boolean functions to bear on the under-resourced sunflower problem. They proved that (log w)w sets are enough to yield a sunflower. Their new result doesn’t get all the way to proving that the conjectured number of sets (some constant number to the w power) is sufficient to guarantee a sunflower. But it is an order of magnitude better than Erdős and Rado’s ww result, and it’s around the number of sets the two predicted should be required to produce a sunflower.
After a half-century of failure, the new work suggests that a full solution is in sight. It also further explains the inevitability with which special shapes take root in the random mathematical wild.
Lead image: HelloRF Zcool
Get the Nautilus newsletter
Cutting-edge science, unraveled by the very brightest living thinkers.
