🔢 mathematics

The lonely runner conjecture holds for nine runners

本文通过改进此前用于证明八名跑者结论的方法，证明了孤独跑者猜想对九名跑者成立。

原作者： Matthieu Rosenfeld

发布于 2026-01-28

📖 1 分钟阅读🧠 深度阅读

原作者： Matthieu Rosenfeld

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一个环形跑道。在跑道上，有若干名跑步者，每位跑步者的速度各不相同。有的跑得快，有的跑得慢，且没有任何两人的速度完全相同。

孤独跑者猜想（Lonely Runner Conjecture） 是一个关于这些跑步者的数学问题。它问道：是否总能在某个时刻，让每一位跑步者都处于“孤独”状态？

在这种语境下，“孤独”意味着每位跑步者都远离其他所有人。具体来说，如果你将跑道视为周长为 1 的圆，那么当一名跑步者与所有其他跑步者的距离都至少为 $1/(k+1)$ 时（其中 $k$ 是跑步者的总数），该跑步者就是孤独的。该猜想声称，无论你如何选择速度，总会有一个特定的时刻，使所有人同时达到这种状态。

长期以来，数学家已经证明了对于 3、4、5、6、7 和 8 名跑步者，这一猜想是成立的。但对于 9 名跑步者，这仍然是一个谜。

突破：解决 9 名跑步者的案例

在这篇论文中，作者 Matthieu Rosenfeld 证明了该猜想对于 9 名跑步者 确实成立。

以下是他实现这一目标的逻辑，通过一个简单的类比来解释：

1. “不可能”的情景

为了证明这个猜想，作者使用了一种经典的逻辑技巧：反证法（Proof by Contradiction）。
他首先假设相反的情况成立：假设存在一组拥有特定速度的 9 名跑步者，使得他们永远无法同时处于孤独状态。

如果这样一组“糟糕”的跑步者真的存在，他们的速度必须是非常特殊的数字。论文使用了一个数学“围栏”（公式）来表明，如果这组糟糕的跑步者存在，那么他们速度的乘积不能太大。它设定了一个关于这些数字能有多大的上限。

2. “整除性”侦探工作

接下来，作者扮演起一名寻找线索的侦探。他问道：如果这组“糟糕”的跑步者存在，他们的速度必须能被哪些数字整除？

他利用一系列逻辑规则（引理）发现，这些假设中的跑步者的速度必须能被一长串特定的数字整除（例如 17, 19, 23, 29 等，甚至是像 64 和 81 这样的数的幂）。

你可以这样理解：如果你有一个秘密代码（速度的乘积），作者证明了这个代码必须包含 17 的“钥匙”、19 的“钥匙”、23 的“钥匙”等等。

3. 矛盾产生

奇迹就在这里发生。

上限： 来自第 1 步的“围栏”说，速度的总乘积必须小于某个巨大的数字（我们称之为 $X$ ）。
下限： 来自第 2 步的“侦探工作”说，乘积必须能被一组如此庞大的数字整除，以至于这些数字的组合乘积大于 $X$ 。

这就像是在说：“这个罐子只能装下 100 个弹珠，”但随后又证明了“里面的弹珠重量足以填满一个能装下 200 个弹珠的罐子。”

由于乘积不可能同时既小于 $X$ 又大于 $X$ ，因此最初的假设是错误的。不存在这样一组“糟糕”的 9 名跑步者。 因此，孤独跑者猜想对于 9 名跑步者是成立的。

计算机的角色

你可能会问：“他是如何检查那么多数字的？”
论文承认，仅靠手工检查所有可能的各种速度组合是不可能的。作者编写了一个专门的计算机程序来承担这项繁重的工作。

问题： 计算机必须检查某些复杂的数字模式是否能在不留下间隙（即“孤独”点）的情况下“覆盖”整个跑道。
创新： 作者并没有仅仅使用标准的计算机求解器（这就像是用大锤去砸坚果）。他构建了一个定制的、高效的“回溯算法”（backtracking algorithm）。
- 想象一下尝试寻找迷宫中的路径。他的程序非常聪明，它不会走完每一条路，而是能够意识到：“如果我在这里向左转，我会在 10 步之后撞到死胡同，所以我甚至不需要走那么远。”
- 这种优化使计算机的运行速度比以往的尝试快得多，将处理类似问题的时长从 32 小时缩短到了 50 分钟。

那 10 名跑步者呢？

论文简要提到，虽然这种方法在理论上可以适用于 10 名跑步者，但数学难度会变得极其巨大。“围栏”会变得更高，计算机需要检查的数字也会大到需要一个计算机核心运行大约两年才能完成任务。

作者指出，另一位研究人员使用一种略微不同的、更快的“筛法”（sieving method）独立解决了 10 名跑步者的案例，但本论文专注于针对 9 名跑步者的证明过程，以及为达到这一目标而在逻辑和代码方面所做的具体改进。

总结

简而言之，这篇论文通过以下步骤解决了困扰数十年的 9 名跑步者难题：

假设存在一组“糟糕”的跑步者。
证明这样一组跑步者所需的数字在数学上是不可能的（太大而无法放入允许的空间内）。
使用一个巧妙的、定制的计算机程序来验证导致这一矛盾的数学规则。

结果证实，在任何拥有 9 名不同速度跑步者的跑道上，总会有一个时刻，每个人都是完美的孤独者。

技术摘要：九个跑步者的孤独跑步者猜想

问题陈述
本文探讨了由 Wills 于 1967 年首次提出的组合数论中的长期开放问题——孤独跑步者猜想（Lonely Runner Conjecture）。该猜想指出，对于任何整数 $k \ge 1$ 以及任何由 $k$ 个不同整数组成的集合（代表跑步者的速度） $v_1, \dots, v_k$ ，都存在一个实数时间 $t$ ，使得每个跑步者都是“孤独的”。从数学上讲，这意味着存在一个 $t$ ，使得每个跑步者距离原点的距离在单位圆上至少为 $1/(k+1)$ ，即 $\|t v_i\| \ge 1/(k+1)$ 对所有 $i$ 均成立。

虽然该猜想已在小规模 $k$ 值的情况下得到验证（最高至 $k=7$ ），但在一般情况下仍是一个开放问题。本文专门针对九个跑步者（ $k=9$ ）的情况。

研究方法
本证明策略建立在作者此前建立八个跑步者情形证明的基础之上。核心论证依赖于一种针对假设的“最小反例”属性的矛盾证明法。

转化为整除约束：
证明利用了由 Malikiosis, Santos, 和 Schymura 导出的界限（定理 1），该界限表明：如果猜想对 $k$ 成立，则只要任何最小反例中速度的乘积超过特定阈值，猜想对 $k+1$ 也成立。因此，要证明猜想对 $k+1$ 成立，只需证明不存在满足上述界限所施加的整除约束的、且违反“孤独跑步者性质”（LR 性质）的 $k$ 个速度集合。
约数的广义引理：
作者引入了引理 6，这是对先前引理（引理 3）的加强和泛化版本。该引理确立了在何种条件下，特定的整数 $d$ 必须整除任何不具备 LR 性质的 8 个整数的速度乘积。
- 该引理引入了一个系数 $c$ ，并考虑模 $9cd$ 的速度。
- 它结合了关于能被 3 和 9 整除的速度数量的特定整除条件（源自引理 5）。
- 该条件要求验证：对于任何满足特定 GCD（最大公约数）和整除约束的 8 个速度集合，是否存在一个满足 LR 性质的时间 $t$ 。
计算机辅助验证（集合覆盖重构）：
验证引理 6 的条件具有极高的计算强度。作者将该问题重构为一个**集合覆盖（set cover）**问题（引理 7）。
- 整数 $v$ “覆盖”整数 $j$ ，当且仅当 $\| \frac{jv}{9cd} \| < 1/8$ 。
- 目标是验证是否存在不存在任何“坏”的 8 元组，能够覆盖所有必要的整数并同时满足整除约束。
- 作者实现了一个带有显著优化（较其之前针对 $k=7$ $k = 7$ 的工作）的回溯算法：
  - 预计算了覆盖位置的位集（bitsets）。
  - 基于候选元素能覆盖的最大新整数数量的剪枝策略。
  - 通过记忆化消除冗余搜索路径。
- 作者还测试了 SAT 求解器方法（使用 Cardinality-CDCL 和 Minicard），但发现对于此类特定问题结构，这些方法明显慢于其自定义的回溯实现。

主要贡献与结果

九个跑步者的证明： 本文提供了一个完整的证明，证明了孤独跑步者猜想对于 $k=9$ 成立。
识别约数： 通过应用引理 6 及计算机程序，作者确定了一个整数集合 $S$ （包括素数幂如 $64, 81, 25$ 以及直到 191 的素数），这些整数必须整除九个跑步者任何最小反例的速度乘积。
矛盾： 集合 $S$ 中元素的乘积（这些元素两两互素）约为 $9.09 \times 10^{79}$ 。然而，根据推论 2，最小反例中速度乘积的理论上限约为 $8.47 \times 10^{79}$ 。由于所需的约数乘积超过了速度可能的最大乘积，因此不存在这样的反例。
算法改进： 文中详细介绍了实现上的改进，这些改进将 $k=7$ 验证情况的运行时间从 32 小时缩短至 50 分钟，从而使更复杂的 $k=9$ 验证成为可能。

意义与声明
作者指出，这一结果将已知满足孤独跑步者猜说的跑步者范围从 7 个扩展到了 9 个。他们指出，所使用的技术在理论上适用于任何特定数量的跑步者，尽管计算成本会迅速增长。

独立性： 作者承认，Trakulthongchai 在本文提交前不久，独立宣布了对 $k=9$ 和 $k=10$ 的证明。Trakulthongchai 的工作同样构建在 $k=7$ 的证明之上，并采用了一种“巧妙的筛法”，其速度似乎比本文所提方法快约 100 倍。
未来展望： 本文讨论了将此方法扩展到 $k=10$ 的可行性。虽然该方法具有适应性，但验证直到约 263 的素数预计在单核上需要花费两年时间。作者建议，将他们的改进方法（例如考虑小素数的幂）与 Trakulthongchai 的筛法相结合，可以使 $k=10$ 的情况变得更易处理，但他们并未声称自己已经解决了这个问题。

综上所述，本文通过精炼的理论引理和高度优化的计算机验证，成功解决了 $k=9$ 的情况，同时也谦逊地将这项工作定位为为解决更高 $k$ 值问题的整体努力中所做出的贡献和进步。