A major breakthrough in solving the 60-year-old hypothesis sheds light on how order begins to appear in them with the growth of random systems
A team of mathematicians and computer scientists finally demonstrated progress in solving, at first glance, a simple task that tormented researchers for almost six decades.
This task, set by mathematicians Pal Erdös and Richard Rado in 1960, concerns how often one can expect the appearance of patterns resembling a sunflower in large sets of objects - for example, in a large number of points scattered on a plane. Although the new result does not completely solve the Erdös and Rado hypothesis, it promotes the understanding of mathematicians in the appearance of surprisingly complex structures in random clusters. For this purpose, the task was reformulated in terms of a computer function, taking advantage of the growing relationship between theoretical computer science and pure mathematics.
“In this work, a mathematical idea manifests itself in a new way, which will become the main idea of our time. The result itself is amazing, ”said Gil Kalai of Hebrew University in Jerusalem.
The sunflower hypothesis refers to sets, or sets of objects. It is easiest to imagine using the example of a set of points on the xy plane. First, select a fixed number of points that will be included in each set. Then draw random loops so that each loop, or set, includes the selected number of points. The loops can intersect, and some points can fall into several sets, resembling a Venn diagram.
If you draw a lot of loops containing a large number of points, most of them will intersect and will resemble the intricacies of vines. But Erdös and Rado predicted that a refined structure would also result: three or more sets would intersect with each other, leaving the same subset of points at the intersection, while none of these sets would intersect with any other sets.
If you remove this common subset of points, then the three sets will be located around the void, and will be completely separated from each other - like petals around the dark middle of the sunflower. The simplest sunflower is considered to have three sets that do not intersect with any other; such islands are called disjoint sets.
Erdös and Rado suggested that as the number of loops increases, such sunflowers will inevitably appear, either in the form of disjoint sets, or in the form of sets superimposed on each other in the indicated way. This sunflower hypothesis is part of a more general area of mathematics called the Ramsey theory, which studies how order begins to appear in them with increasing size of random systems.
“If you have a sufficiently large mathematical object, a structure must be hidden in it,” said Shachar Lovet from the University of California at San Diego, co-author of a new work on which Ryan Alweis from Princeton University also worked, Keven Wu from Peking University and Jiapeng Zhang of Harvard University.
Erdös and Rado wanted to know exactly how many sets and what exactly size is needed to guarantee a sunflower. They took the first modest step toward solving the problem by defining the parameter w, denoting the number of points in each of the sets. Then they proved that it takes about w w of sets of size w to guarantee that a sunflower consisting of three sets appears in them. So, if you want to use sets of 100 points, then you will need 100,100 sets to guarantee the appearance of a sunflower.
At the same time, Erdös and Rado suggested that in fact the number of sets guaranteeing a sunflower is much less than w w - and more like a constant in degree w (for example, 3 w or 80 w or 5 000 000 w ). However, they could not find a way to prove their guess.
“They said that the task seemed extremely simple, and were surprised that they could not achieve progress in it,” Alveys said.
And they were not alone. In the period from their first result and this new work, which appeared 60 years later, only two mathematicians made at least some progress on this issue - and then they went gradually, taking one step in 1997, and the second this year .
“Everyone has already tried all the ideas that people feel comfortable with,” said Anup Rao of the University of Washington, who has published additional work simplifying the methods obtained in the new result. “And no one was able to improve the base line set by Erds and Rado.”
But the new evidence made a major breakthrough.
Four researchers, including mathematicians and computer scientists, were able to do this by breaking the task into two different scenarios. In the first, easier one, they looked at what would happen when the sets intersect significantly with each other, making it much easier to understand when a sunflower should appear there.
“When you have a set of elements that belong to a larger set of sets, you can use this structure,” to search for a sunflower, Lovet said.
At first, the researchers wondered if there exist a set of points belonging to a sufficiently large part of all the sets in the system. Having found such points, in their search for a sunflower, they limited themselves to only that part of the sets that contain this set of points. Then they continued to do the same, refining the search, including in it less and less number of system sets that have more and more common points. This pruning continued until they found their sunflower.
In a second, more complex scenario, they analyze what will happen if the sets do not intersect much. In this case, the most likely way to get a sunflower is to take three disjoint sets. However, to prove that three separate sets are hiding in more slightly intersecting sets is not easy.
This is where computer science comes into play. Two co-authors, Lovet and Zhang, have been trying for several years to analyze the sunflower problem using the same tools that computer scientists use to study Boolean functions. These functions perform operations on a sequence of bits — ones and zeros — and produce a single bit in the end, corresponding to whether a computational statement is true or false. For example, a Boolean function can be programmed to return 1 if at least one of the input bits is 1, and 0 if none of the input bits is 1.
Three years ago, Lovet and Zhang realized that the same question could be posed as to whether there are three disjoint sets among a set of not strongly intersecting sets. First, assign a label to each point in the set: 1 if it is contained only in this set, and 0 in another case. A Boolean function returns 1 (true) if each point at the input is 1 - that is, each point of the set exists exclusively in this set, which makes this set disjoint. The true result suggests that there are suitable conditions for finding a sunflower.
Strictly proving this correspondence, the researchers used extensive knowledge regarding Boolean functions to attack the sunflower problem, which previously lacked resources. They proved that (log w) w sets are sufficient to obtain a sunflower. Such a result is not enough to prove the hypothesis that a certain constant in degree w is enough to obtain a sunflower. But this is an order of magnitude better result than w w obtained by Erdös and Rado, and it roughly coincides with the number of sets that they predicted.
After half a century of setbacks, the new work suggests that we will soon see a complete solution. It also improves understanding of how special forms inevitably arise in the wild mathematical nature of chance.