The ‘Lonely Runner’ Problem Only Appears Simple
The original version of this story appeared in Quanta Magazine.
Imagine a bizarre training exercise: a group of runners begin running around a circular track, with each runner maintaining a single, consistent pace. Will every runner end up finding themselves “alone” or relatively far from others, at least once, regardless of their speed?
Mathematicians assume the answer is yes.
The “lone runner” problem may seem simple and inconsequential, but it appears in many forms in mathematics. This is equivalent to questions in number theory, geometry, graph theory, etc. : when it is possible to have a clear line of sight in a field of obstacles, where billiard balls can move on a table, or how to organize a network. “It’s so multifaceted. It touches so many different areas of mathematics,” said Matthias Beck of San Francisco State University.
For just two or three runners, the proof of the conjecture is elementary. Mathematicians proved it for four runners in the 1970s, and by 2007 they had reached seven. But in the past two decades, no one has been able to advance further.
Then last year, Matthieu Rosenfeld, mathematician at the Computer Science, Robotics and Microelectronics Laboratory in Montpellier, settled the conjecture for eight runners. And within weeks, Tanupat (Paul) Trakulthongchai, a second-year student at Oxford University, built on Rosenfeld’s ideas to prove it to nine and ten runners.
This sudden progress has renewed interest in the problem. “It’s really a giant step,” said Beck, who was not involved in the work. Adding just one runner makes the task of proving the conjecture “exponentially more difficult,” he said. “To go from seven riders to now 10 riders is incredible.”
The starting sprint
At first, the lone runner problem had nothing to do with running.
Instead, mathematicians were interested in a seemingly unrelated problem: how to use fractions to approximate irrational numbers such as pi, a task that has a large number of applications. In the 1960s, a graduate student named Jörg M. Wills hypothesized that a century-old method was optimal and that there was no way to improve it.
In 1998, a group of mathematicians rewrote this conjecture in the language of running. Say N the runners start from the same place on a circular track of 1 unit length and each runs at a different constant speed. Wills’ conjecture is equivalent to saying that every runner will always end up feeling alone at some point, no matter how fast other runners are. More precisely, each runner will at some point find themselves at a distance of at least 1/N from any other runner.
When Wills saw the lone runner article, he emailed one of the authors, Luis Goddyn of Simon Fraser University, to congratulate him on “this wonderful, poetic name.” (Goddyn’s response: “Oh, you’re still alive.”)
Mathematicians have also shown that the lone runner problem is equivalent to another question. Imagine an infinite sheet of graph paper. In the center of each grid, place a small square. Then start at one of the corners of the grid and draw a straight line. (The line can point in any direction other than perfectly vertical or horizontal.) How big can the small squares get before the line touches one?
As versions of the lone runner problem proliferated in mathematics, interest in the question grew. Mathematicians have proven different cases of conjectures using completely different techniques. Sometimes they relied on tools from number theory; at other times, they turned to geometry or graph theory.
