Solving 'Packing Coloring' with 15 Numbers - Bernardo Subercaseaux's quest for the perfect equation

Sunday - April 30 2023, 17:39 UTC - 1 year ago

Bernardo Subercaseaux, an undergraduate student at the University of Chile, ventured off to graduate school in Carnegie Mellon University to explore a combinatorics problem posed by Wayne Goddard and his collaborators in 2008. With the help of Marijn Heule, a computer scientist, their collaboration culminated in a proof that the problem can be solved with 15 numbers.

As an undergraduate at the University of Chile, Bernardo Subercaseaux took a dim view of using computers to do math. It seemed antithetical to real intellectual discovery.

"There’s some instinct or gut reaction against using computers to solve your problems, like it goes against the ideal beauty or elegance of a fantastic argument," he said.

But then in 2020 Subercaseaux fell in love, and as often happens, his priorities changed. The object of his obsession was a question he saw on an online forum. Most problems he scanned and forgot, but this one caught his eye. He swiped right.

"The first thing I did was to like the post in the Facebook group, hoping to get a notification later when somebody else posted a solution," he said.

The question was about filling an infinite grid with numbers. It was not, as it turned out, the kind of problem one solves on a lark. In order to do it, Subercaseaux had to leave Chile for graduate school at Carnegie Mellon University.

There, in August 2021, he had a fortuitous encounter with Marijn Heule, a computer scientist who uses massive computing power to solve hard math questions. Subercaseaux asked Heule if he wanted to attempt the problem, kicking off a collaboration that culminated this January in a proof that can be summed up with a single number: 15.

Every Possible Way .

In 2002, Wayne Goddard of Clemson University and some like-minded mathematicians were spitballing problems in combinatorics, trying to come up with new twists on the field’s mainstay questions about coloring maps given certain constraints.

Eventually they landed on a problem that starts with a grid, like a sheet of graph paper that goes on forever. The goal is to fill it with numbers. There’s just one constraint: The distance between each occurrence of the same number must be greater than the number itself. (Distance is measured by adding together the vertical and horizontal separation, a metric known as "taxicab" distance for the way it resembles moving on gridded urban streets.) A pair of 1s cannot occupy adjoining cells, which have a taxicab distance of 1, but they can be placed in directly diagonal cells, which have a distance of 2.

Initially, Goddard and his collaborators wanted to know whether it was even possible to fill an infinite grid with a finite set of numbers. But by the time he and his four collaborators published this "packing coloring" problem in the journal Ars Combinatoria in 2008, they had proved that it can be solved using 22 numbers. They also knew that there was no way it could be solved with only five numbers. That meant the actual answer to the problem — the minimum number of numbers needed — lay somewhere in between.

The researchers didn’t actually fill an infinite grid. They didn’t have to. Instead, it’s enough to take a small subset of the grid — say a 10-by-10 square — fill that with numbers, then show that copies of the filled subset can be placed next to each other, the way you’d cover a floor with copies of a tile.

When Subercaseaux first learned of the problem, he started looking for tiles using pen and paper. He would sketch grids of numbers, cross them out, try again. He soon tired of that approach, and he asked a friend to design a web-based tool that resembled the game Minesweeper and allowed him to test combinations fast. He found a few solutions with 16 numbers but none with 15.

In order to find the magic number, Subercaseaux and Heule developed a computer program that demonstrates different versions of the puzzle. The program was an "oracles"; it checks whether a grid with a certain configuration of numbers can be solved, but it offers no advice on how to arrive at the optimal solution. It’s only by trial and error that the correct number of numbers can be found.

It took the pair eight months to come up with the magic combination of 15 numbers and to prove that it was the answer. Subercaseaux was without a doubt the instigator of the project, but Heule said that without his help, the program the duo used would have been far less efficient.

"I had honed my skills to solve structured tasks like this one, but I had never experienced a student who was so ambitious and willing to take risks," Heule said.

The proof Subercaseaux and Heule wrote up was published in January in the journal Journal of Combinatorial Theory, Series A. They hope it will spark interest from mathematicians, as well as inspire future generations to have the same faith in computers that Suberycaseaux had.

"I think having a computer as an assistant is essential to doing these kinds of problems," he said. "Some people are skeptical of it, so it did not come easily to me. But it is something that I am absolutely sure we should embrace." .