The answer to the problem of packing flowers in an infinite grid turned out to be the number 15

Video

The packing coloring problem asks how many numbers are needed to fill an infinite grid so that identical numbers are never too close together. And a new arithmetic experiment using a computer gives a surprisingly simple answer.

How many numbers will it take to fill an infinite grid so that the distance between occurrences of one number is greater than that number itself?

Note. per.: there is some uncertainty about the correctness of the term “packing”, although in graph theory it is quite used. I would be grateful if knowledgeable readers could tell me how to put it more correctly.

As a final year student at the University of Chile, Bernardo Subercaso looked down on the use of computers to perform mathematical calculations. In his opinion, this contradicted real intellectual research.

Bernardo put it this way: “There is an instinctive reluctance to use computers to solve problems, as if it goes against the ideal beauty or elegance of fantastic proof.”

But then in 2020, he fell in love and, as is often the case, his priorities changed. The object of his obsession was a question he saw on an online forum. Most of the tasks he looked over and forgot, but this one hooked him firmly.

“The first thing I did was like this post in the Facebook group in the hope of being notified later when the decision was published,” he said.

The task required filling an infinite grid with numbers and, as it turned out, was not entertaining. To solve it, Subercaso had to leave Chile and enroll in graduate school at Carnegie Mellon University (CMU).

Then, in August 2021, he happened to meet Marein Höhl, a computer scientist who used extensive computing power to solve complex mathematical problems. Subercaso asked Hyul if he would like to try to solve his problem as well, resulting in a collaboration between them, culminating in January of that year in solutionwhich can be generalized to a single number: 15.

▍ All possible ways

In 2002

Wayne Goddard

from Clemson University and his fellow mathematicians were sorting out problems of combinatorics, trying to find new ideas in the field of fundamental questions about coloring maps under certain restrictions.

They eventually arrived at a problem that starts with a grid like checkered paper and continues indefinitely. The goal was to fill this grid with numbers, with just one constraint: the distance between all occurrences of the same number must be greater than that number itself. This distance was measured by adding the vertical and horizontal separation of the positions of numbers, that is, using the “Manhattan metric”. A pair of 1s cannot occupy adjacent squares separated by a Manhattan distance of 1, but they can be placed in diagonally adjacent squares separated by a Manhattan distance of 2.

A friend of Bernard Subercaso’s developed a Miner-like game that allowed him to quickly test possible solutions. Edward Chen

Initially, Goddard and his colleagues wanted to see if it would be possible to fill an infinite grid with a finite set of numbers. But by the time they published this “graph color packing” problem in the journal Ars Combinatorica in 2008 they already proved that it can be solved using 22 numbers. They also knew that it couldn’t be solved with just five numbers. This meant that the actual answer – the minimum number of numbers required – lay somewhere in between.

In reality, the researchers did not fill in an infinite grid. They didn’t need it. It was enough to take a small part of it – for example, a 10×10 square – fill it with numbers and then demonstrate which copies of this filled subset can be placed next to each other, like laying out floor tiles.

When Subercaso first learned about this challenge, he began to sort through different variations of the tiles using pen and paper. He drew grids of numbers, crossed out, tried again… Soon, this approach exhausted him, and he asked a friend to develop an online tool that would resemble the Miner game and allow him to quickly test different combinations. After a few more weeks of work, he became convinced that there was no way to pack the grid using eight numbers, but he could not get any further – there were too many potential shapes that could form tiles, and too many ways in which they could be filled with numbers.

The problem, as it became clear later, was that it is much more difficult to demonstrate the impossibility of filling the grid with a certain set of numbers than it is possible.

“It shows not just that one way doesn’t work, but that every possible way doesn’t work,” Goddard said.

After Subercaso started his studies at CMU and convinced Hoehl to work together, they quickly figured out a way to fill in the grid with 15 numbers. They were also able to eliminate the possibility of solving the problem using only 12 numbers. But their sense of triumph did not last long, as they found themselves simply recreating long-standing results. Back in 2017, researchers already knew that the answer would be no less than 13 and no more than 15.

Marein Hoehl specializes in using the potential of computers to solve complex mathematical problems. Carnegie Mellon University

For a freshman who coaxed his professor to work with him on his hobby problem, the discovery came as a shock. Subercaso, summarizing in his post their work, was expressed as follows: “I was horrified. In fact, I spent several months working on the problem without realizing it, and even worse, because of me, Marain wasted his time on it!”

However, Hoehl himself found the discovery of previously known results inspiring. This indicated that other researchers considered the problem important enough to work on, and confirmed for him that the only result worth obtaining was its complete solution.

“When we found out that they had been working on this task for 20 years, it completely changed the picture,” he said.

▍ “Unworthy” approach

Over the years, Hoehl has built a career by finding effective ways to search among a huge number of possible combinations. His approach was called the SAT solution, short for satisfiability. It consists of constructing a long formula, called a boolean, which can have two possible outcomes: 0 or 1. If the result is 1, then the formula is correct and the requirements of the problem are satisfied.

For the problem of filling the grid in question, the variable in this formula can represent whether a certain cell is occupied by a number. The computer looks for ways to assign variables so that the formula is correct. If the computer succeeds, then you know that it is possible to populate the grid under the conditions you set.

Unfortunately, simply coding this problem as a Boolean formula can stretch over many millions of terms – a computer, or even a network of them, can run indefinitely, testing all possible ways to assign variables.

“A naive attempt to do this by brute force would drag on until the end of the universe,” Goddard said. “Therefore, effective simplifications are needed to bring this undertaking at least within the scope of the possible.”

Moreover, each time a new number is added to the algorithm, due to the increase in possible calculation options, the task becomes more complicated by about 100 times. That is, if a network of computers working in parallel can eliminate 12 per day of computation as an answer, then it will take them 100 days to eliminate 13.

Hoehl and Subercaso recognized the brute-force scaling of the computational approach as “undignified” in a sense. “We had several promising ideas, so we were determined to “optimize our approach until we can solve the problem within 48 hours of computing by a cluster of computers,” Subercaso said.

To do this, they had to come up with a way to limit the number of combinations that the computing cluster must go through.

“They want to not just solve it, but solve it in an impressive way,” said Alexander Soifer from the University of Colorado.

Hoehl and Subercaso understood that many of the combinations were essentially the same. If you’re trying to fill a diamond-shaped tile with eight different numbers, it doesn’t matter if you place the first number one square above and to the right of center, or one square below and to the left of it. These two positions will be symmetrical with respect to each other and will limit the next action in the same way, so there is no point in checking them both.

If every packing problem could be solved using a checkerboard pattern, where a diagonal grid of units covers the entire space (for example, black cells on the board), then the calculations would be greatly simplified. Yes, this is not always the case, as in this example of a final tile packed with 14 numbers. The chess pattern needs to be broken in some places closer to the upper left corner. – Bernardo Subercaso and Marein Hoehl.

Hoehl and Subercaso added rules that allowed the computer to treat symmetrical combinations as equals, reducing the overall search time by a factor of eight. They also used a technique called “cube and conquer” (triple and conquer), which Höl developed as part of his last project. This technique allowed them to test more combinations in parallel. If you know that a given cell contains 3, 5, or 7, then you can split the task and test each of these three possibilities simultaneously on different computer clusters.

By January 2022, these refinements allowed the researchers to eliminate 13 as the answer, which took two days of computing time. So they were left with two possible answers: 14 or 15.

▍ Big plus

To eliminate 14 and thus solve the problem, Hoehl and Subercaso had to look for additional ways to speed up the computer search.

Initially, they wrote a Boolean formula that assigned variables to each individual grid cell. But in September 2022, it became clear to them that it was not necessary to continue the calculations, sorting through the cells one by one. They found that it would be much more efficient to look at small areas consisting of five cells in the shape of a + symbol.

The researchers then rewrote their formula so that several variables represented questions like: “Is there a number 7 somewhere in this +-shaped area?” The computer didn’t have to figure out exactly where 7 might be in that area. It was enough for it to find out if that number was there at all, which required significantly less computational effort.

“Using variables that reflect only positives rather than specific arrangements of numbers has proven to be much more effective than looking at those numbers in specific cells,” Hoehl said.

Using a new approach using the plus analysis technique, the researchers eliminated 14 as an answer in the November 2022 experiment in less time than eliminating 13. Over the next four months, they additionally checked the correctness of the results – this almost as long as it took them to help the computer come to that conclusion in the first place.

“It was very inspiring to think that some seemingly side question we posed in some random magazine caused entire groups of people to spend, as it turned out, months of their time searching for its solution.” Goddard said.

For Subercaso, this was the first real triumph of his research career. And while it may not have been the kind of “ideal” discovery that the young scientist initially imagined while working in the field of mathematics, in the end it still brought him a separate intellectual reward.

“It’s a misunderstanding of structure when you give me a board and I can show you why the answer is 15,” he said. “But we were able to figure out how the task constraints work, how much better it is to use 6 here or 7 there. We have developed a deep intuitive understanding.”