The ‘Lonely Runner’ Problem Only Appears Simple

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.