The “lone runner” problem seems simple

original version of this story Appear in Quanta Magazine.

Picture a strange workout: A group of runners start jogging around a circular track, each maintaining a unique, constant pace. Does every runner end up “alone,” or relatively far away from everyone else, at least once, regardless of their speed?

Mathematicians speculate that the answer is yes.

The “lone runner” problem may seem simple and inconsequential, but it appears in many forms in mathematics. It amounts to problems in number theory, geometry, graph theory, and so on—like when a clear line of sight can be obtained in an area of ​​obstructions, or where a pool ball might move on a table, or how to organize a network. “It has a lot of facets. It touches a lot of different areas of mathematics,” said Matthias Beck San Francisco State University.

For two or three runners, the proof of this conjecture is rudimentary. Mathematicians proved this for four runners in the 2007s, and by 2007, they got up to seven. But for nearly two decades, no one has been able to get any further.

Then last year, Mathieu RosenfeldMathematicians from the Laboratory of Computer Science, Robotics and Microelectronics in Montpellier solved this conjecture eight runners. Within weeks, a second-year undergraduate at Oxford University named Tanupat (Paul) Trakutonchai Build on Rosenfeld’s ideas to prove it nine and ten runner.

The sudden development has revived interest in the problem. “It’s really a huge leap,” said Baker, who was not involved in the work. Adding just one more runner would make the task of proving the conjecture “much more difficult,” he said. “It’s awesome to go from seven runners to now 10 runners.”

starting sprint

Initially, 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 with numerous applications. In the 1960s, a graduate student named Jörg M. Wells Speculate A century-old method is optimal – there is no way to improve it.

In 1998, a group of mathematicians rewrote this conjecture Use the language of running. explain nitrogen Runners start from the same position on a circular track of length 1 unit, each running at a different constant speed. Wells’ conjecture amounts to saying that every runner will feel lonely at some point, no matter how fast other runners are. More precisely, every runner will at some point find himself at least 1/nitrogen from any other runner.

When Wells saw the Lone Runner paper, he emailed one of the authors, Louis Godin Professors from Simon Fraser University congratulated him on “this wonderful and poetic name.” (Godin’s response: “Oh, you’re still alive.”)

Jörg Wells proposed a conjecture in number theory that decades later became known as the “lone runner problem.”

Courtesy of Jörg Wills/Quanta Magazine

Mathematicians have also shown that the lone runner problem is equivalent to another problem. Imagine an infinite piece of graph paper. Place a small square in the center of each grid. Then draw a straight line starting from one corner of the grid. (The line can point in any direction except perfectly vertical or horizontal.) How big can the smaller square get before the line has to hit it?

As versions of the lone runner problem proliferated in mathematics, so did interest in the problem. Mathematicians have proved different versions of this conjecture using completely different techniques. Sometimes they rely on number theory tools; sometimes they rely on number theory tools. Sometimes they turn to geometry or graph theory.