Aubrey de Grey, who is more widely known as a maverick biologist intent on extending the human lifespan, has taken the academic world by surprise after announcing a new solution to the so-called Hadwiger-Nelson problem.
The problem sounds deceptively simple, but despite some professionals spending years trying to crack it, progress has stalled since shortly after the puzzle was first posed in 1950.
“Literally, this is the first progress in more than 60 years,” said Gil Kalai, a mathematician at Hebrew University of Jerusalem.
The problem is as follows. Imagine a collection of dots connected by lines. The dots can be arranged any way at all, the only rule is that all the connecting lines must be of equal length. For instance, in a square the diagonal would not be joined up, but the outer edges would be. Now, colour in all the dots so that no two connected points have the same colour. How many colours are required?
For a square, the answer would be two. But the Hadwiger-Nelson problem asks what the minimum would be for any configuration – even one that extends across a plane of infinite size.
Shortly after the problem was first suggested, mathematicians established that the number of colours needed was somewhere between four and seven, but then progress came to a standstill. In a paper, entitled The Chromatic Number of the Plane is at least 5, posted to the arxiv website for scientific preprints, de Grey has narrowed the window.
The biologist said he was astonished to make the breakthrough after working on the problem for only a few weeks. “I’ve toyed with cool open maths problems all my adult life, but this is the first time I’ve made an advance and I’m 55,” he said. “It’ll very probably be the last time too.”
De Grey based his configuration on a shape called the Moser spindle, a pattern comprising just seven dots and 11 edges, that requires four colours to meet the conditions. When this was fused, along with another configuration, into a huge pattern of 20,425 dots, he showed that it could not be coloured using just four shades. Using a powerful computer search, he then replicated the finding with a smaller configuration of 1,581 dots.
Professor Timothy Gowers, a mathematician at the University of Cambridge, said the problem was very well-known in the field of combinatorics, an area of maths focussed on counting. “It is not often that an amateur mathematician solves a famous problem, and even less often that the amateur mathematician is well known to the general public for a completely different reason,” he said.
Kalai said that the advance had spurred on others in the field to attempt applying a similar strategy to close in on a full solution to the problem.
Aside from moving the puzzle closer to a solution, does the latest discovery have any applications in the real world, or in maths more broadly? “So far we don’t know of any important [ones],” said Kalai. “It’s an isolated pearl.”
More about: #MathProblem