The “lone runner” problem only seems simple

The original version to This story Featured in Quanta Magazine.

Imagine a bizarre training exercise: A group of runners start out running around a circular track, and each runner maintains a unique, constant pace. Will every runner end up “alone” or relatively far away from everyone, at least once, regardless of their speed?

Mathematicians believe the answer is yes.

The “lone runner” problem may seem simple and insignificant, but it appears in many forms throughout mathematics. They’re the equivalent of questions in number theory, geometry, graph theory, and more — about when it’s possible to have a clear line of sight in a field of obstacles, or where billiard balls can move on a table, or how a net is organized. “It has many facets. It touches on many different areas of sports,” he said. Matthias Beck From San Francisco State University.

For only two or three contestants, the guessing guide is preliminary. Mathematicians proved this on four runners in the 1970s, and by 2007, they had… As much as seven. But over the past two decades, no one has been able to advance further.

Then last year, Matthew Rosenfelda mathematician at the Computer Science, Robotics and Microelectronics Laboratory in Montpellier, settled the conjecture of Eight contestants. Within a few weeks, a second-year undergraduate student had been named to the University of Oxford Tanupat (Pol) Trakulthongchai Built on Rosenfeld’s ideas to prove this Nine and 10 Runners.

The surprising progress has led to renewed interest in the problem. “It’s really a paradigm shift,” said Beck, who was not involved in the work. Adding just one runner makes the task of proving the conjecture “significantly more difficult,” he said. “Going from seven contestants to 10 contestants now is amazing.”

Dash start

At first, the lone runner’s problem had nothing to do with running.

Instead, mathematicians were interested in a seemingly unrelated problem: how to use fractions to approximate irrational numbers like pi, a task that has a large number of applications. In the 1960s, a graduate student named Jörg M. Wales You guessed it A century-old way to do it It is optimized, and there is no way to improve it.

In 1998, a group of mathematicians Rewrite this guess In the language of running. He says n Runners start at the same place on a circular track of one unit length, and each runs at a different constant speed. Wells’ conjecture is equivalent to saying that every runner will always end up alone at some point, no matter how fast the other runners are. More precisely, every runner will find himself at some point at a distance of at least 1/n than any other hostility.

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

Jörg Wells made a conjecture in number theory, which decades later became known as the lone runner problem.

Courtesy of Jörg Wells/Quanta Magazine

Mathematicians have also shown that the lone runner problem is equivalent to another problem. Imagine an infinite sheet of graph paper. In the center of each grid, place a small square. Then start at one of the corners of the grid and draw a straight line. (The line can point in any direction other than strictly vertical or horizontal.) How big can the little squares get before the line reaches one?

As versions of the lone runner problem spread throughout mathematics, interest in the question increased. Mathematicians have proven different cases of conjecture using completely different techniques. Sometimes they relied on tools from number theory. Other times they turned to geometry or graph theory.