线性指数级检验足以解决孤独跑者猜想及其变体：基于Zonotope几何的有限性证明

《Forum of Mathematics, Sigma》：Linearly exponential checking is enough for the lonely runner conjecture and some of its variants

为解决著名的“孤独跑者猜想”（Lonely Runner Conjecture, LRC）及其“平移变体”（shifted LRC, sLRC），研究人员开展了一项关于“孤独跑者Zonotope”几何性质的研究。他们通过将问题重新表述为Zonotope的覆盖半径问题，证明了对于n+1个跑者，只需检验速度不超过n2n的有限种情况，这极大地改进了陶哲轩（Tao）之前nO(n2)的界。该研究不仅为LRC和sLRC提供了更有效的有限性检验方法，还通过引入“共简单Zonotope”（cosimple zonotope）的概念，将问题推广到更一般的几何框架中，并利用低维（二维和三维）的精确分类结果，为最终通过计算机验证sLRC铺平了道路。

　　

想象一下，有n+1个跑者在一圈为单位长度的环形跑道上以不同的恒定速度奔跑。他们从同一点出发，但速度各不相同。著名的“孤独跑者猜想”（Lonely Runner Conjecture, LRC）断言：在某个时刻，每个跑者都会感到“孤独”，即他与其他所有跑者的距离都至少是1/(n+1)。这个看似简单的组合问题，自1968年由Wills提出以来，一直是组合数学和数论领域的一个著名难题，目前仅对不超过7个跑者的情形得到证明。

更棘手的是其“平移变体”（shifted Lonely Runner Conjecture, sLRC），它允许每个跑者有不同的起点。这个版本在跑者速度可以相同的情况下是平凡的，因此通常要求速度互不相同。sLRC的难度在于，它要求对于跑者起点的任意选择，都存在一个时刻使得所有跑者都感到孤独。这相当于一个更强的几何条件。

为了攻克这些难题，数学家们一直在寻找将问题“有限化”的途径。陶哲轩（Tao）在2018年取得了一项突破性进展，他证明了为了验证LRC对于n+1个跑者是否成立，只需检验速度不超过n^O(n2)的有限种情况。虽然这从理论上将问题转化为有限次计算，但这个上界是“双指数级”的，对于实际计算来说仍然过于巨大。

为了回答“我们能否将检验范围缩小到更易于处理的规模？”这一问题，Romanos Diogenes Malikiosis、Francisco Santos和Matthias Schymura在《Forum of Mathematics, Sigma》上发表了一项研究。他们通过将问题重新表述为一种称为“Zonotope”的几何对象的性质，极大地改进了陶哲轩的结果，将检验范围从双指数级降低到了“线性指数级”（即n²ⁿ），并证明了对于sLRC，只需检验速度之和不超过195的有限种情况，这为最终通过计算机验证sLRC铺平了道路。

为了开展这项研究，作者们主要运用了以下关键技术方法：

1. 1.
   Zonotope几何重述：将孤独跑者问题等价地转化为关于“孤独跑者Zonotope”（Lonely Runner Zonotope, LRZ）的几何问题。具体来说，跑者的速度向量对应一个高维Zonotope，而跑者感到孤独的时刻存在性等价于该Zonotope的“覆盖半径”（covering radius）不超过(n-1)/(n+1)。
2. 2.
   几何数论方法：利用Minkowski第一定理、覆盖半径与体积的关系等几何数论中的经典工具，建立Zonotope的几何不变量（如体积、格点数量）与其覆盖半径之间的定量联系。
3. 3.
   归纳法与投影技巧：通过将高维Zonotope投影到低维空间，利用归纳假设来推导高维情形的性质。为了处理sLRC，作者引入了“共简单Zonotope”（cosimple zonotope）的概念，其性质在投影下保持良好。
4. 4.
   低维分类与体积界：对二维和三维Zonotope进行详尽的分类和体积计算，特别是对“格宽”（lattice-width）至少为3的Zonotope进行精确刻画，从而为高维情形的有限性检验提供具体的数值上界。

研究结果

1. 孤独跑者猜想的有限性检验

作者证明了，如果LRC对n个跑者成立，那么对于n+1个跑者，只需检验那些速度满足特定和式大于((n+1)/2)^n-1的有限种情况。这个上界大约是n²ⁿ，相比陶哲轩的n^O(n2)有了巨大的改进。这一结果是通过分析Zonotope的投影和格点数量得出的。

2. 平移孤独跑者猜想的有限性检验

对于更难的sLRC，作者也证明了一个类似的有限性检验结果，但该结果的成立依赖于一个被称为“孤独向量问题”（Lonely Vector Problem, LVP）的中间结论。他们证明了LVP在n≤4时成立，从而将sLRC的检验范围缩小到速度之和不超过195的有限种情况。

3. 共简单Zonotope的推广

为了克服sLRC在投影下性质不佳的困难，作者引入了“共简单Zonotope”（cosimple zonotope）这一更一般的概念。他们证明了，对于共简单Zonotope，其覆盖半径的有限性检验结果不依赖于LVP，并且检验范围可以缩小到((d+2)/2)^d个格点以内。

4. 二维情形的证明与分类

作者完全证明了sLRC在二维（即4个跑者）的情形。他们通过分类所有格宽至少为3的二维Zonotope，发现除了一个面积为5的平行四边形（P_2,5）外，所有其他Zonotope的覆盖半径都不超过1/2，从而验证了sLRC。

5. 三维情形的体积界

对于三维（即5个跑者）的情形，作者证明了任何潜在的反例Zonotope，如果其格宽至少为3且体积大于195，则其覆盖半径必然小于3/5。这意味着，要寻找sLRC在5个跑者情形下的反例，只需检验体积不超过195的有限个Zonotope。

结论与讨论

这项研究在孤独跑者猜想的研究中取得了重大进展。其核心贡献在于，通过深刻的几何洞察，将检验范围从陶哲轩的双指数级上界大幅降低到了线性指数级，这不仅是理论上的巨大改进，也为最终通过计算机验证猜想提供了现实可能性。

研究的重要意义体现在以下几个方面：

1. 1.
   理论突破：证明了LRC和sLRC的“有限性”，即只需检验有限种情况即可判断猜想的真伪，这是解决此类无限问题的关键一步。
2. 2.
   方法创新：通过引入“共简单Zonotope”的概念，为处理sLRC提供了一个更强大且性质更优美的几何框架，这一推广可能在其他问题中也有应用。
3. 3.
   计算可行性：将sLRC在5个跑者情形下的检验范围缩小到体积不超过195的Zonotope，这是一个可计算的有限集。事实上，在本文的预印本发布后，Alcántara等人已经利用这一结果，通过计算机验证了sLRC在5个跑者情形下成立，从而彻底解决了这一难题。

总之，这项研究不仅极大地推进了我们对孤独跑者猜想的理解，更重要的是，它展示了如何通过巧妙的几何方法将复杂的组合问题转化为可计算的有限问题，为数学中其他类似难题的解决提供了新的范式和希望。