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

Category Science

tldr #

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.

content #

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 packing coloring problem was first proposed by Wayne Goddard and his collaborators in 2008

"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.

The goal of the problem was to fill a infinite grid with finite set of numbers

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.

In order to solve the problem, computers were used to help explore the limits of number combinations

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.

Carnegie Mellon University is located in Pittsburgh, Pennsylvania

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.

Marijn Heule is an associate professor of computer science at CMU

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.

The original paper to the problem was published in the journal Ars Combinatoria

"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." .

hashtags #
worddensity #