Amateur Solves Part of Decades-Old Math Problem

Back in 1950, a then-University of Chicago graduate student named Edward Nelson — who later went on to become famous for his application of probability to quantum field theory — came up with an intriguing math problem. If you have a graph of points connected by lines of identical length on a plane, how many colors do you need to color the points so that any two points connected by a line have different colors?

That question intrigued Swiss mathematician Hugo Hadwiger, who wrote about it in the early 1960s. The Hadwiger-Nelson problem, as it became known, doesn't have a lot of real-world applications. "But it's still a fascinating test case for what we can understand," Henry Cohn, an adjunct professor of mathematics at Massachusetts Institute of Technology, explains. "You can think of this as a special case of constraint satisfaction problems, the sort where you're given a bunch of constraints, and the question is, can you meet all of them?"

The Problem Stalled for Decades

Hadwiger-Nelson has been an intriguingly tough nut to crack. As this Quanta magazine article notes, after mathematicians quickly narrowed down the answer to between four and seven, they didn't make much more progress for decades.

But then, a math amateur named Aubrey de Grey, who does problems in his spare time for relaxation, decided to give Hadwiger-Nelson a try. He created a sensation with this paper published at ArXiv.org, in which he presented a family of graphs on a plane that couldn't meet Hadwiger-Nelson's requirements with four colors, thus showing that the lower boundary of the answer is five.

"As for this particular problem, well, as far as I can tell pretty much everyone who comes across it is captivated by it — it is so simple and elegant, and since it's graph theory, one doesn't necessarily need to know a slew of prior theory to work on it," de Grey explains in an email.

Though de Grey isn't a professional mathematician, he's got a pretty impressive resume. He holds a doctorate in biology from the University of Cambridge and is the chief science officer and co-founder of the SENS Research Foundation. He has become well known as an advocate of the paradigm-shifting view that aging isn't an inevitability, but rather a curable condition that could be treated by preventing or reducing metabolic-induced damage to cells. ("I work in aging, and I'm not in favor of it," he explained in this 2015 talk at TEDxMünchen. "I'm trying to fix it.")

Advertisement

Aubrey de Grey Explains

His scientific background and unconventional approach may have come in handy for de Grey. "I suppose that when I look back at the steps that got me there, several of them were motivated by noticing surprising features of failed attempts," he says in the email. "In that sense I suppose I used my science skills, since in science one is always looking for the aspects of data that in some way are surprising, i.e. contrary to the line of thinking one started with."

For non-mathematicians who might be daunted by his paper, de Grey offers this simpler explanation of how he came up with his breakthrough result. "Suppose you have a piece of paper and two pens, red and green ink, and your task is to place dots on the paper in such a way that no pair of dots of the same color are exactly one inch apart. But the catch is, it's a game, and your opponent also has a piece of paper but only one pen, and he puts his dots wherever he likes, and you have to put your dots in the exact same places that he did. Is there any way that he can win, i.e. place his dots in such a way that the no-monochromatic-pair rule prevents you from placing your dots in the same places as his?"

"Answer: yes, he can place three dots in an equilateral triangle so that each pair is an inch apart. So now, suppose you have three pens, red blue green, can he still win? Answer: it turns out that yes, but it's harder, and he needs seven dots. So the obvious next question is what if you have four pens? And I found a way that he can place his dots so that he still wins, but the simplest solution I found needs 1,581 dots."

Think of it this way: It's the math equivalent of some basketball fan running onto the court, grabbing the ball from LeBron James' hands, and hitting a buzzer beater. "Considering the problem is so hard, it's surprising that anyone came up with this," Dustin G. Mixon, an assistant professor of mathematics at Ohio State University and author of the Short, Fat Matrices math blog, says in an email. "But in hindsight, this problem exhibits features that make it amenable to progress by amateur mathematicians."

As Mixon explained, Hadwiger-Nelson "involves planar geometry, the state of the art could be easily reproduced, and any possible improvement to the lower bound could be obtained by an explicit drawing in the plane (much like how the Moser spindle produced the lower bound of 4). These conditions are reminiscent of the problem of pentagonal tilings of the plane, in which the amateur mathematician Marjorie Rice famously discovered four new tessellating pentagons in the [19]70s."

"The key distinction with the Hadwiger-Nelson problem is that it's extremely difficult to verify that your drawing in the plane produces a new lower bound," Mixon wrote. "To remedy this, de Grey leaned on a computer algebra system called Mathematica, which is rather user-friendly (and apparently amateur-friendly). Given the modern availability of computational resources, it seems that the conditions were right for this breakthrough to be made by an amateur mathematician — again, in hindsight."

Though de Grey modestly offered that his first time cracking a classic math problem might also be the last time, his breakthrough could well encourage other amateurs to discover the joys of math. "It's easy to become addicted to trying various solutions," University of Richmond mathematics professor Della Dumbaugh explained in an email. "Before long, you start to recognize patterns, and, in time, you start to propose theory to support your observations. That's the essence of being a mathematician."