Picture a bizarre training exercise: A group of runners begin running around a circular track, with each runner maintaining a unique, constant pace. Will every runner be “alone” or relatively far away from everyone else at least once, regardless of their speed?
Mathematicians guess the answer is yes.
The “lone runner” problem may seem simple and unimportant, but it comes up in many forms throughout mathematics. This is the equivalent of number theory, geometry, graph theory, and other questions – about when it is possible to get a clear line of sight across a field of obstacles, or where billiard balls can move around on the table, or how to organize a network. “There are so many aspects to it. It touches so many different mathematical areas,” said Matthias Beck of San Francisco State University.
For only two or three runners, the proof of conjecture is rudimentary. Mathematicians had proven it in the 1970s for four runners, and by 2007, they had reached seven. But no one has been able to move forward in the last two decades.
Then last year, mathematician Matthew Rosenfeld of Montpellier’s Computer Science, Robotics and Microelectronics Laboratory solved the eight-runner conjecture. And within a few weeks, Tanupat (Paul) Trakulthongchai, a second-year undergraduate at Oxford University, built on Rosenfeld’s ideas to prove it for nine and 10 runners.
The sudden progress has revived 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 “increasingly difficult,” he said. “Going from seven runners to now 10 is amazing.”
initial dash
First of all, the problem of the lonely runner had nothing to do with running.
Instead, mathematicians were interested in an unrelated problem: how to use fractions to approximate irrational numbers like pi, a task that has a huge number of applications. In the 1960s, a graduate student named Jorge M. Wills speculated that a century-old method for doing this was optimal—that there was no way to improve it.
In 1998, a group of mathematicians rewrote that conjecture in the language of running. Tell n Runners start at the same location on a circular track that is 1 unit long, and each runs at a different constant speed. Wills’ conjecture is equivalent to saying that each runner will always be alone at some point, regardless of the speed of the other runners. More precisely, every runner will at some point find himself at a distance of at least 1/.n From another runner.
When Wills saw the Lonely Runner paper, he emailed one of the authors, Louis Godin of Simon Fraser University, to congratulate him on “this wonderful and poetic name.” (Godin’s reply: “Oh, you’re still alive.”)
Mathematicians also showed that the lone runner problem amounts to another question. Imagine an infinite sheet of graph paper. Place a small square in the middle 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 big can the small squares get before they hit the line?
As versions of the lone runner problem spread throughout mathematics, interest in the question grew. Mathematicians prove different cases of the conjecture using completely different techniques. Sometimes they relied on the tools of number theory; At other times they turned to geometry or graph theory.
<a href