New Strides Made on Deceptively Simple ‘Lonely Runner’ Problem

Is every runner sometimes far from all the others?

每个跑步者有时都会远离其他人吗？

For a few runners, the answer is yes.

对于一些跑步者来说，答案是肯定的。

Adding more runners makes the problem exponentially harder.

添加更多的跑步者会使问题变得更加困难。

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 .

数学家在 20 世纪 70 年代为 4 名跑步者证明了这一点，到 2007 年，他们的成绩已达到 7 名。

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 .

去年，蒙彼利埃计算机科学、机器人和微电子实验室的数学家马蒂厄·罗森菲尔德（Matthieu Rosenfeld）为八名跑步者解决了这个猜想。

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.

几周之内，牛津大学二年级本科生 Tanupat (Paul) Trakulthongchai 在罗森菲尔德的想法的基础上，为 9 名和 10 名跑步者证明了这一点。

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.”

“从 7 名跑步者到现在 10 名跑步者真是太棒了。”

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.

相反，数学家们对一个看似无关的问题感兴趣：如何使用分数来近似无理数，例如 pi，这是一项具有大量应用的任务。

In the 1960s, a graduate student named Jörg M.

20 世纪 60 年代，一位名叫 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.

1998年，一群数学家用跑步的语言重写了这个猜想。

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.

假设 N 名跑步者从长度为 1 单位的圆形跑道上的同一位置出发，每个人以不同的恒定速度跑步。

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.

更准确地说，每个跑步者在某个时刻都会发现自己与任何其他跑步者的距离至少为 1/N。

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.”)

当威尔斯看到这篇孤独跑步者的论文时，他给作者之一、西蒙·弗雷泽大学的路易斯·戈丁发了电子邮件，祝贺他获得“这个美妙而富有诗意的名字”。 （戈丁的回答：“哦，你还活着。”）

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?

（这条线可以指向除完全垂直或水平之外的任何方向。）在这条线必须击中较小的方块之前，较小的方块可以达到多大？

Jörg Wills made a conjecture in number theory that, decades later, would come to be known as the lonely runner problem.

约尔格·威尔斯在数论中提出了一个猜想，几十年后，这个猜想被称为“孤独跑步者问题”。

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.

有时他们依赖数论工具；有时他们依赖数论工具。有时他们转向几何或图论。

But this meant that they didn’t have a general strategy for how to tackle the problem.

但这意味着他们没有解决问题的总体策略。

Rather, they had a bunch of clever but ad hoc techniques that might work for four runners, say, but not five.

相反，他们有一堆聪明但临时的技术，可能适用于四名跑步者，但不适用于五名跑步者。

With each additional runner, they had to go back to the starting line.

每增加一名参赛者，他们就必须回到起跑线。

By the mid-2000s, mathematicians had proved that when there are seven or fewer runners sprinting around a track, each of them will eventually get lonely.

到 2000 年代中期，数学家已经证明，当有 7 名或更少的跑步者在跑道上冲刺时，每个人最终都会感到孤独。

They’d also found ways to simplify the problem.

他们还找到了简化问题的方法。

For instance, they realized that they didn’t need to prove the conjecture for all (infinitely many) combinations of speeds.

例如，他们意识到他们不需要证明所有（无限多个）速度组合的猜想。

Instead, if they could show that it was true for any combination of whole-number speeds , it would have to be true more generally; they could ignore fractions and irrationals.

相反，如果他们能够证明对于任何整数速度的组合都是正确的，那么它在更普遍的情况下也必须是正确的；他们可以忽略分数和无理数。

This was a much easier task, but it still involved dealing with infinitely many possible speeds.

这是一项容易得多的任务，但它仍然涉及处理无限多种可能的速度。

Something more was needed.

还需要更多的东西。

In 2015, Terence Tao of the University of California, Los Angeles planted the first seed.

2015年，加州大学洛杉矶分校的陶哲轩播下了第一颗种子。

He showed that if the lonely runner conjecture held for relatively low speeds, it would also hold for high speeds.

他证明，如果孤独跑步者猜想适用于相对较低的速度，那么它也适用于较高的速度。

For any given number of runners, mathematicians would only have to consider whole-number speeds up to a particular threshold .

对于任何给定数量的跑步者，数学家只需考虑达到特定阈值的整数速度。

This reduced the problem to a finite number of calculations — at least in theory.

这将问题减少到有限数量的计算——至少在理论上是这样。

In practice, even when you’re dealing with only a few runners, the number of combinations of speeds you have to check is still “astronomical and completely impractical,” said Noah Kravitz of the University of Oxford.

牛津大学的诺亚·克拉维茨 (Noah Kravitz) 表示，在实践中，即使你只面对少数跑步者，你必须检查的速度组合数量仍然是“天文数字，完全不切实际”。

Tao’s advance would eventually catch the eye of Rosenfeld, who was interested in proofs that use a computer to check many examples.

陶的进步最终引起了罗森菲尔德的注意，他对使用计算机检查许多例子的证明很感兴趣。

He reframed the problem by considering possible counterexamples to the conjecture: What features would the runners’ speeds have to have so that at least one runner would never end up alone?

他通过考虑该猜想的可能反例来重新构建问题：跑步者的速度必须具备哪些特征，才能至少有一名跑步者永远不会孤独终老？

Matthieu Rosenfeld was drawn to the lonely runner problem because it gave him the opportunity to explore his interest in computer-assisted proofs.

马修·罗森菲尔德（Matthieu Rosenfeld）被孤独跑步者问题所吸引，因为这让他有机会探索自己对计算机辅助证明的兴趣。

It turned out that their speeds would need to be highly constrained.

事实证明，他们的速度需要受到高度限制。

Rosenfeld used a computer program, along with ideas from number theory, to show that if he multiplied all the speeds together, their product would have to be divisible by certain prime numbers.

罗森菲尔德使用计算机程序以及数论中的思想来证明，如果他将所有速度相乘，它们的乘积必须能被某些素数整除。

Now all he needed to do was prove that no combination of speeds could satisfy this condition.

现在他需要做的就是证明没有任何速度组合可以满足这个条件。

To do so, he returned to a modified version of Tao’s threshold.

为此，他回到了陶氏阈值的修改版本。

He then rewrote it in terms of the product of speeds: If the lonely runner conjecture was true for products up to a given size, it had to be true in general.

然后，他用速度的乘积重写了它：如果孤独跑步者猜想对于给定尺寸的产品是正确的，那么它在一般情况下也必须是正确的。

This implied that if the conjecture was false, it would be possible to find a counterexample with a product below the threshold.

这意味着如果猜想是错误的，则有可能找到产品低于阈值的反例。

But Rosenfeld had already shown that in any counterexample, the product would have to be divisible by all those primes.

但罗森菲尔德已经证明，在任何反例中，乘积都必须能被所有这些素数整除。

Such a product would have to be massive.

这样的产品必须是巨大的。

So massive, in fact, that it would far exceed the threshold.

事实上，它的规模如此之大，以至于远远超出了阈值。

In other words, a counterexample to the lonely runner conjecture couldn’t exist — at least, not for eight runners.

换句话说，孤独跑步者猜想的反例是不存在的——至少对于八个跑步者来说不存在。

The conjecture was true .

猜想是真的。

Rosenfeld started thinking about how to extend his proof to nine runners.

罗森菲尔德开始考虑如何将他的证明扩展到九名跑步者。

In the meantime, Kravitz saw Rosenfeld’s paper and showed it to a promising undergraduate he’d been mentoring at Oxford, Paul Trakulthongchai.

与此同时，克拉维茨看到了罗森菲尔德的论文，并将其展示给他在牛津大学指导的一位有前途的本科生保罗·特拉库尔通柴 (Paul Trakulthongchai)。

He advised Trakulthongchai to work on the conjecture for nine runners.

他建议 Trakulthongchai 针对 9 名跑步者研究这个猜想。

Trakulthongchai used Rosenfeld’s overall approach, but he developed a more efficient computational technique for pinpointing the prime divisors that a counterexample would have to have.

Trakulthongchai 使用了罗森菲尔德的整体方法，但他开发了一种更有效的计算技术来精确定位反例必须具有的素因数。

This allowed him to more quickly rule out all counterexamples for both nine and 10 runners: The conjecture was true in both cases.

这使他能够更快地排除 9 名和 10 名跑步者的所有反例：在这两种情况下，猜想都是正确的。

(Rosenfeld independently proved the conjecture for nine runners as well, just a few days after Trakulthongchai did.

（罗森菲尔德也独立地为九名跑步者证明了这个猜想，就在 Trakulthongchai 证明后几天。

He was happy to see the other mathematician’s burst of progress.

他很高兴看到另一位数学家的突飞猛进。

But “at the same time, I was a bit bummed out,” he said with a laugh.)

但“与此同时，我有点沮丧，”他笑着说。）

Tanupat (Paul) Trakulthongchai solved two new cases of the lonely runner problem as an undergraduate.

Tanupat (Paul) Trakulthongchai 在本科时解决了两个新的孤独跑步者问题。

Both Rosenfeld’s and Trakulthongchai’s methods are too computationally expensive to work for more runners, leaving them stuck on the problem’s next case.

Rosenfeld 和 Trakulthongchai 的方法计算成本都太高，无法适用于更多的跑步者，导致他们陷入了问题的下一个案例。

“In order to achieve 11, I think you need an entirely new sort of way of looking at things,” Trakulthongchai said.

“为了实现 11，我认为你需要一种全新的看待事物的方式，”Trakulthongchai 说。

But mathematicians are excited by these recent advances — and by the fact that a single approach solved three cases at once, when previously each new case had required an entirely new proof.

但数学家们对这些最新进展感到兴奋，而且因为一种方法可以同时解决三个案例，而以前每个新案例都需要一个全新的证明。

“I really see a new way of getting a hold on the whole conjecture by this new idea,” said Matthias Schymura of the University of Rostock in Germany.

德国罗斯托克大学的马蒂亚斯·席穆拉 (Matthias Schymura) 表示：“我确实看到了通过这个新想法来掌握整个猜想的新方法。”

Although a proof of the whole conjecture still feels far off — and mathematicians don’t yet agree on whether it will hold true for any N runners — “things are starting to move after not moving for a while,” Kravitz said.

虽然整个猜想的证明还很遥远——数学家们还没有就它是否适用于任何 N 名跑步者达成一致——“事情在静止了一段时间后开始移动，”克拉维茨说。

Inspired by the new results, Schymura and others are organizing a workshop on the lonely runner conjecture , to be held in Rostock this October.

受到新结果的启发，Schymura 和其他人正在组织一个关于孤独跑步者猜想的研讨会，将于今年 10 月在罗斯托克举行。

It will bring together researchers from the different fields in which the conjecture appears.

它将汇集来自该猜想出现的不同领域的研究人员。

The hope is that they’ll approach the problem from various angles and “communicate and bridge the different areas,” Schymura said, to find a potential proof or counterexample.

希穆拉说，希望他们能从不同角度解决问题，并“在不同领域进行沟通和架起桥梁”，以找到潜在的证据或反例。

“I’m convinced the problem will be solved,” Wills said.

“我相信问题将会得到解决，”威尔斯说。

“But it might be some 20, 30 more years.”

“但这可能还需要大约20年、30年。”

Get highlights of the most important news delivered to your email inbox

获取发送到您的电子邮件收件箱的最重要新闻的摘要

Quanta Magazine moderates comments to facilitate an informed, substantive, civil conversation.

《Quanta》杂志对评论进行审核，以促进知情、实质性、文明的对话。

Abusive, profane, self-promotional, misleading, incoherent or off-topic comments will be rejected.

辱骂、亵渎、自我推销、误导、语无伦次或偏离主题的评论将被拒绝。

Moderators are staffed during regular business hours (New York time) and can only accept comments written in English.

版主在正常工作时间（纽约时间）有工作人员，并且只能接受英文评论。