Mathematicians Solve Long-Standing Coloring Problem

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 — say, a unit up and a unit to the right — the function gives a number that is a measure of the size of the overlap. If a set is “unit-distance-avoiding,” then its autocorrelation function will be zero whenever it is shifted — in any direction — by one unit.

Matolcsi, Ambrus and their new collaborators looked at the Fourier transform of the function, which translates it into a giant sum of sine waves. The requirement that the function be zero for all unit-length shifts restricts the possible values of the elements of the Fourier sum. They figured out how to express that requirement as a linear optimization problem, building on techniques that Vallentin and Oliveira had devised.

“We have to find the set of points with a very delicate, very rare set of properties, and we don’t know how to do that. So we ask the computer to search for these objects,” Varga said.

This process was more straightforward than they had anticipated. While Varga and Csiszárik experimented with more complicated artificial intelligence models to try to identify the points — and struggled more than they expected — Zsámboki used older search strategies developed in the 1980s.

“It was very weird that the advanced stuff didn’t work so well. I decided to use older methods,” said Zsámboki,“and that just happened to work way better.” (Zsámboki added that Varga suggested using a particular technique called tree search.)

Once they had settled on the algorithms to use, they had a large problem to solve: 25,552 variables with 6,099 constraints on them. They ran the search for a week on 128 CPUs. At the end of the week, they had their result.

In October 2022, the team posted a paper showing that no more than 24.7% of the plane can be colored in with no unit-distance pairs, finally breaking Erdős’ bound.

“It really was, I have to say, a very satisfying moment,” Matolcsi said. “It’s just a very neat and nice result.”

“I’m very happy that they did this now, because I already thought that going below 25% would not be possible with current computer power,” Vallentin said.

Still, nobody has come up with a more complete coloring than Croft’s 1967 tortoises, which cover just under 23% of the plane. But rather than try to continue to lower the upper bound toward the tortoises, several of the authors are now focused on a related problem: figuring out how many colors are needed to completely cover the plane while making sure that every color is unit-distance-avoiding.

This number is called the chromatic number of the plane. In 2018, the amateur mathematician (and longevity evangelist) Aubrey de Grey proved that it must be at least 5. It’s known to be less than or equal to 7. The new paper implies, using different methods than de Grey, that at least five colors are needed. “Can we prove that it is at least 6?” Ambrus asked. “That is something that might have a chance. We are working on it now, and it might have a chance with our method.”

Correction: July 26, 2023

This article originally misstated when Máté Matolcsi first began working on the unit-distance coloring problem. It was in the early 2010s. It also implied that the Alfréd Rényi Institute of Mathematics is part of the Hungarian Academy of Sciences. It used to be, but isn’t anymore. The article has been revised.