Fifty Years Later Mathematicians Finally Solve a Fascinating Problem

Friday - July 28 2023, 23:34 UTC - 1 year ago

Máté Matolcsi and colleagues, tasked with reducing the percentage of an infinitely large plane to less than 25%, used AlphaFold, a machine learning algorithm, to come up with a model covering 24.95% of the plane.

For years, a simple question has haunted Máté Matolcsi, a professor at the Budapest University of Technology and Economics. How much of an infinite plane can you color in while making sure that no two colored points are exactly one unit of distance apart? .

The question was first posed by Leo Moser, a Canadian mathematician, in the early 1960s. In 1967, Hallard Croft at the University of Cambridge came up with a construction that seemed to do a pretty good job. His shape, now called "Croft’s tortoise," looks like a circle that met a hexagon-shaped cookie cutter. Every point inside each tortoise is less than one unit away from any other point in the same tortoise, and more than one unit away from the closest point of the neighboring tortoise.

In the half-century since, nobody has been able to find a shape that improves on the 22.936% of the plane that the tortoises cover. But could one exist, even in theory? In 1984, László Székely, a Hungarian mathematician, proved that it is impossible to find a shape that covers more than 27.91% of the plane. The next year, Paul Erdős, the prolific conjecturer (and fellow Hungarian), said he thought the upper bound was less than 25%. As with many Erdős conjectures, it attracted the attention of numerous ambitious mathematicians over the years.

Matolcsi began tackling it in the early 2010s. He was working in Fourier analysis — adding together sine functions taken from trigonometry to represent more complicated functions — and thought those techniques could be used to prove Erdős’ conjecture.

"I couldn’t do it," he said. "We got very close to 25% but not below. I was a bit disappointed; we put a lot of effort into it. I had a doctoral defense at the Hungarian Academy of Sciences, and I said to the committee, ‘Look, I’m not even sure whether this is true anymore. We’ve put so much effort into it, and this bloody number is just not going below 25.’" .

It would take almost a decade for him to prove himself wrong. Other mathematicians continued to chip away at the number. By 2010, Frank Vallentin, now at the University of Cologne, and Fernando Oliveira, now at the Delft University of Technology, pushed the bound below 27%. Matolcsi also kept at it, and in 2014, with colleagues, he passed 26%. By 2018, together with Gergely Ambrus, he got the bound down to 25.442% — tantalizingly close to Erdős’ 25% guess.

Then he gave up.

After the 2018 paper, Matolcsi remembered, "I said, ‘I’m never going to touch this problem again. Because it’s just not working.’ I did what I could do." .

Turns out he hadn’t. Matolcsi agreed to try solving the problem one final time after a few researchers approached him at a birthday party. Dániel Varga, Adrián Csiszárik and Pál Zsámboki, all at the Alfréd Rényi Institute of Mathematics, thought that machine learning models like AlphaGo and AlphaFold could help identify the complicated set of points necessary to solve the problem.

Ever since the 1984 result, one technique that had proved fruitful was to look at the amount of overlap a candidate set of points has with a shifted copy of itself, using something called an autocorrelation function. For a given shift 𝑥, this function looks at the ratio of the number of pairs of points of the candidate set that moved less than 𝑥 units after the shift, compared to the total number of pairs. Matolcsi thought this could be used to generate a pattern with an autocorrelation value of 0. This would minimize the interpoint distance while maximizing the area covered by the shape.

Matolcsi and his colleagues decided to use AlphaFold to generate a dataset. Instead of searching for the optimal points, the model generated a list of probabilities that a given point fit the pattern. Then using a so-called genetic algorithm, which starts with a random collection of candidate points and creates successive copies of the best-growing dataset, they were able to precisely match the autocorrelation pattern to zero. Finally, the total area turned out to be 24.95%.