The ‘Lonely Runner’ Problem Only Appears Simple | WIRED
CommentLoader-
Save StorySave this story
CommentLoader-
Save StorySave this story
The original version of this story appeared in Quanta Magazine.
Picture a bizarre training exercise: A group of runners starts jogging around a circular track, with each runner maintaining a unique, constant pace. Will every runner end up “lonely,” or relatively far from everyone else, at least once, no matter their speeds?
Mathematicians conjecture that the answer is yes.
The “lonely runner” problem might seem simple and inconsequential, but it crops up in many guises throughout math. It’s equivalent to questions in number theory, geometry, graph theory, and more—about when it’s possible to get a clear line of sight in a field of obstacles, or where billiard balls might move on a table, or how to organize a network. “It has so many facets. It touches so many different mathematical fields,” said Matthias Beck of San Francisco State University.
For just two or three runners, the conjecture’s proof is elementary. Mathematicians proved it for four runners in the 1970s, and by 2007, they’d gotten as far as seven. But for the past two decades, no one has been able to advance any further.
Then last year, Matthieu Rosenfeld, a mathematician at the Laboratory of Computer Science, Robotics, and Microelectronics of Montpellier, settled the conjecture for eight runners. And within a few weeks, a second-year undergraduate at the University of Oxford named Tanupat (Paul) Trakulthongchai built on Rosenfeld’s ideas to prove it for nine and 10 runners.
The sudden progress has renewed interest in the problem. “It’s really a quantum leap,” said Beck, who was not involved in the work. Adding just one runner makes the task of proving the conjecture “exponentially harder,” he said. “Going from seven runners to now 10 runners is amazing.”
The Starting Dash
At first, the lonely 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 vast number of applications. In the 1960s, a graduate student named Jörg M. Wills conjectured that a century-old method for doing so is optimal—that there’s no way to improve it.
In 1998, a group of mathematicians rewrote that conjecture in the language of running. Say N runners start from the same spot on a circular track that’s 1 unit in length, and each runs at a different constant speed. Wills’ conjecture is equivalent to saying that each runner will always end up lonely at some point, no matter what the other runners’ speeds 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 lonely runner paper, he emailed one of the authors, Luis Goddyn of Simon Fraser University, to congratulate him on “this wonderful and poetic name.” (Goddyn’s reply: “Oh, you are still alive.”)
Jörg Wills made a conjecture in number theory that, decades later, would come to be known as the lonely runner problem.
Courtesy of Jörg Wills/Quanta Magazine
Mathematicians also showed that the lonely runner problem is equivalent to yet another question. Imagine an infinite sheet of graph paper. In the center of every grid, place a small square. Then start at one of the grid corners and draw a straight line. (The line can point in any direction other than perfectly vertical or horizontal.) How big can the smaller squares get before the line must hit one?
As versions of the lonely runner problem proliferated throughout mathematics, interest in the question grew. Mathematicians proved different cases of the conjecture using completely different techniques. Sometimes they relied on tools from number theory; at other times they turned to geometry or graph theory.
But this meant that they didn’t have a general strategy for how to tackle the problem. Rather, they had a bunch of clever but ad hoc techniques that might work for four runners, say, but not five. With each additional runner, they had to go back to the starting line.
By the mid-2000s, mathematicians had proved that when there are seven or fewer runners sprinting around a track, each of them will eventually get lonely. They’d also found ways to simplify the problem. For instance, they realized that they didn’t need to prove the conjecture for all (infinitely many) combinations of speeds. Instead, if they could show that it was true for any combination of whole-number speeds, it would have to be true more generally; they could ignore fractions and irrationals.
This was a much easier task, but it still involved dealing with infinitely many possible speeds. Something more was needed.
Speed Limits
In 2015, Terence Tao of the University of California, Los Angeles planted the first seed. He showed that if the lonely runner conjecture held for relatively low speeds, it would also hold for high speeds. For any given number of runners, mathematicians