Original version With this story appeared in Quanta Magazine.
Imagine a bizarre training exercise: a group of runners start running on a circular track, each maintaining a unique, constant pace. Will every runner finish “alone” or relatively far from others at least once, regardless of speed?
Mathematicians guess the answer is yes.
The “lone runner” problem may seem basic and inconsequential, but it appears in many forms in mathematics. This is the equivalent of questions in number theory, geometry, graph theory, and more – about when you can get clear visibility in a field of obstacles, where billiard balls can move across a table, or how to organize a network. “It has so many facets. It touches on so many different areas of mathematics,” he said Maciej Beck San Francisco State University.
With just two or three runners, the evidence for this hypothesis is rudimentary. Mathematicians proved this with four runners in the 1970s, and by 2007. up to seven. However, over the past two decades, no one has been able to go further.
Then last year Matthieu Rosenfeldmathematician from the Laboratory of Computer Science, Robotics and Microelectronics in Montpellier, resolved the conjecture eight runners. And within a few weeks, a second-year student from Oxford University named Tanupat (Paul) Trakulthongchai built on Rosenfeld’s ideas to prove it nine and 10 runners.
The sudden progress has sparked renewed interest in the problem. “It’s a real milestone,” said Beck, who was not involved in the work. Adding just one factor makes proving this hypothesis “exponentially more difficult,” he said. “To go from seven runners to now 10 runners is amazing.”
Starting jump
In the beginning, the lone runner problem had nothing to do with running.
Instead, mathematicians were interested in a seemingly unrelated problem: how to utilize fractions to approximate irrational numbers like pi, a task that has a huge number of applications. In the 1960s, a graduate of Jörg M. Wills he guessed that there is a hundred-year-old method for this is optimal – that there is no way to improve it.
In 1998, a group of mathematicians he rewrote this supposition in the language of running. To talk N runners start from the same place on a circular track 1 unit long and each runs at a different constant speed. Wills’ hypothesis is equivalent to saying that every runner will always be lonely at some point, regardless of the speed of the other runners. More specifically, each runner will at some point be at least 1/N from another runner.
When Wills saw the article about the lone runner, he emailed one of the authors: Luis Goddyn Simon Fraser University to congratulate him on “this wonderful and poetic name.” (Goddyn’s response: “Oh, you’re still alive.”)
Mathematicians have also shown that the lone runner problem is equivalent to yet another question. Imagine an endless sheet of graph paper. Place a miniature square in the center of each grid. 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 substantial can the smaller squares be before the line must hit one?
As versions of the lone runner problem spread throughout mathematics, interest in the question increased. Mathematicians have proven different cases of the conjecture using completely different techniques. Sometimes they relied on the tools of number theory; other times they turned to geometry or graph theory.