In 1950 Edward Nelson, then a student at the University of Chicago, asked the kind of deceptively simple question that can give mathematicians fits for decades. Imagine, he said, a graph — a collection of points connected by lines. Ensure that all of the lines are exactly the same length, and that everything lies on the plane. Now color all the points, ensuring that no two connected points have the same color. Nelson asked: What is the smallest number of colors that you’d need to color any such graph, even one formed by linking an infinite number of vertices?
The problem, now known as the Hadwiger-Nelson problem or the problem of finding the chromatic number of the plane, has piqued the interest of many mathematicians, including the famously prolific Paul Erdős. Researchers quickly narrowed the possibilities down, finding that the infinite graph can be colored by no fewer than four and no more than seven colors. Other researchers went on to prove a few partial results in the decades that followed, but no one was able to change these bounds.
Then last week, Aubrey de Grey, a biologist known for his claims that people alive today will live to the age of 1,000, posted a paper to the scientific preprint site arxiv.org with the title “The Chromatic Number of the Plane Is at Least 5.” In it, he describes the construction of a planar unit-distance graph that can’t be colored with only four colors. The finding represents the first major advance in solving the problem since shortly after it was introduced. “I got extraordinarily lucky,” de Grey said. “It’s not every day that somebody comes up with the solution to a 60-year-old problem.”
De Grey appears to be an unlikely mathematical trailblazer. He is the co-founder and chief science officer of an organization that aims to develop technologies for “reversing the negative effects of aging.” He found his way to the chromatic number of the plane problem through a board game. Decades ago, de Grey was a competitive Othello player, and he fell in with some mathematicians who were also enthusiasts of the game. They introduced him to graph theory, and he comes back to it now and then. “Occasionally, when I need a rest from my real job, I’ll think about math,” he said. Over Christmas last year, he had a chance to do that.
It is unusual, but not unheard of, for an amateur mathematician to make significant progress on a long-standing open problem. In the 1970s, Marjorie Rice, a homemaker with no mathematical background, ran across a Scientific American column about pentagons that tile the plane. She eventually added four new pentagons to the list. Gil Kalai, a mathematician at the Hebrew University of Jerusalem, said it is gratifying to see a nonprofessional mathematician make a major breakthrough. “It really adds to the many facets of the mathematical experience,” he said.
Perhaps the most famous graph coloring question is the four-color theorem. It states that, assuming every country is one continuous lump, any map can be colored using only four colors so that no two adjacent countries have the same color. The exact sizes and shapes of the countries don’t matter, so mathematicians can translate the problem into the world of graph theory by representing every country as a vertex and connecting two vertices with an edge if the corresponding countries share a border.
The Hadwiger-Nelson problem is a bit different. Instead of considering a finite number of vertices, as there would be on a map, it considers infinitely many vertices, one for each point in the plane. Two points are connected by an edge if they are exactly one unit apart. To find a lower bound for the chromatic number, it suffices to create a graph with a finite number of vertices that requires a particular number of colors. That’s what de Grey did.
De Grey based his graph on a gadget called the Moser spindle, named after mathematical brothers Leo and William Moser. It is a configuration of just seven points and 11 edges that has a chromatic number of four. Through a delicate process, and with minimal computer assistance, de Grey fused copies of the Moser spindle and another small assembly of points into a 20,425-vertex monstrosity that could not be colored using four colors. He was later able to shrink the graph to 1,581 vertices and do a computer check to verify that it was not four-colorable.