2025-11-16T21:01:12.667436

The lonely runner conjecture holds for eight runners

Rosenfeld

We prove that the lonely runner conjecture holds for eight runners. Our proof relies on a computer verification and on recent results that allow bounding the size of a minimal counterexample. We note that our approach also applies to the known cases with 4, 5, 6, and 7 runners. We expect that minor improvements to our approach could be enough to solve the cases of 9 or 10 runners.

academic

孤独なランナー予想は8人のランナーに対して成立する

基本情報

論文ID: 2509.14111
タイトル: The lonely runner conjecture holds for eight runners
著者: Matthieu Rosenfeld (LIRMM, Univ Montpellier, CNRS, Montpellier, France)
分類: math.CO cs.DM math.NT
発表日: 2025年10月17日
論文リンク: https://arxiv.org/abs/2509.14111

要約

本論文は、孤独なランナー予想が8人のランナーの場合に成立することを証明している。証明は計算機検証と、最小反例のサイズを制限することを可能にする最近の結果に依存している。著者は、この方法が既知の4人、5人、6人、7人のランナーの場合にも同様に適用可能であることを指摘し、この方法の小さな改善により9人または10人のランナーの場合を解決するのに十分であることを期待している。

研究背景と動機

問題の定義

孤独なランナー予想は、組合せ数論とディオファントス近似における著名な未解決問題であり、1965年にWillsによって純粋な数論的形式で最初に提案された。ランナーの解釈は以下の通りである：単位長の円形トラック上で異なる一定速度を持つk+1人のランナーが走っている場合、孤独なランナー予想は、任意のランナーに対して、そのランナーと他のすべてのランナーとの距離が少なくとも1/(k+1)である時刻が存在することを主張している。

数学的表現

予想1（孤独なランナー予想）: すべての整数k≥1に対して、異なる整数の集合v₁,...,vₖ₊₁のそれぞれについて、すべてのiに対して、すべてのjに対して以下を満たす実数tが存在する： $\|tv_i - tv_j\| \geq \frac{1}{k+1}$

ここで‖x‖はxから最も近い整数までの距離を表す。

研究の重要性

理論的意義: この予想は、組合せ数論、ディオファントス近似、視線遮蔽問題など複数の数学分野を結びつけている
計算上の課題: ランナー数の増加に伴い、検証の難度は指数関数的に増加する
応用価値: グラフ理論、数論、組合せ最適化において重要な応用がある

既存研究の進展

k=2: 自明な場合
k=3: BetkeとWills、Cusickにより解決
k=4: 最初は計算機補助証明により、後に簡略化
k=5: Bohman、Holzman、Kleitmanにより証明
k=6: BarajasとSerraにより確立
k=7: 本論文で証明される場合

核心的貢献

主要結果: 孤独なランナー予想が8人のランナー（k=7）の場合に成立することを証明
統一的方法: k=4,5,6,7のすべての場合に適用可能な統一的証明フレームワークを提案
計算技術: バックトラッキングと枝刈り技術を使用した効率的な計算検証アルゴリズムを開発
理論的ツール: 反例における素因数を見つけるための体系的方法を提供する重要な補題6を確立
拡張性: k=8,9の場合を解決するための実行可能な技術的経路を提供

方法の詳細

核心戦略

証明は反証法と計算検証を組み合わせている：

k=7の反例が存在すると仮定
Malikiosis等の結果を利用して反例における速度の積の上界を制限
計算検証により反例の速度の積が特定の素数で割り切れることを証明
これらの素数の積が上界を超えることを証明し、矛盾を導出

主要な理論的結果

定理2（Malikiosis-Santos-Schymura界）: 孤独なランナー予想がkに対して成立する場合、gcd(v₁,...,vₖ)=1を満たし $\sum_{S\subseteq\{1,...,k\}} \gcd(\{v_i : i \in S\}) > \binom{k+1}{2}^{k-1}$ を満たすすべてのk元組に対して、予想はk+1に対しても成立する。

系3: 孤独なランナー予想がkに対して成立する場合、gcd(v₁,...,vₖ)=1を満たし $\prod_{i\in\{1,...,k\}} v_i \geq \left[\frac{\binom{k+1}{2}^{k-1}}{k}\right]^k$ を満たすすべてのk元組に対して、予想はk+1に対しても成立する。

素因数を見つける方法

補題4: {v₁,...,vₖ}がLR性質を持たない場合、lcm(2,...,k+1)は∏vᵢを整除する。

補題6（核心的ツール）: k≥3とし、孤独なランナー予想がk-1に対して成立するとする。p∈ℕを正整数とする。すべてのv₁,...,vₖ∈{0,...,(k+1)p-1}が特定の条件を満たす場合に適切なtが存在するなら、LR性質を持たないすべてのk元組{v₁,...,vₖ}に対して、pは∏vᵢを整除する。

計算検証アルゴリズム

問題の変換: 補題6の検証を集合被覆問題に変換：

「被覆」関係の定義：vがjを被覆する ⟺ ‖jv/((k+1)p)‖ < 1/(k+1)
補題6の条件に違反する「悪い」被覆が存在するかどうかを探索

最適化技術:

被覆関係を事前計算し、ビットベクトルで保存
バックトラッキングアルゴリズムでk元組を構築し、早期に枝刈り
対称性を利用して探索空間を削減
最も被覆が難しい要素を優先的に処理

実験設定

計算検証パラメータ

k=7の場合：

上界：P ≤ 7.4×10⁵⁴
検証素数集合S = {31, 37, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163}
最大素数p=163の検証には約32時間の計算時間が必要

実装の詳細

プログラミング言語：C++
主要データ構造：効率的なビット演算のためのビットセット(bitsets)
アルゴリズム：枝刈り付きバックトラッキング探索
計算プラットフォーム：単一プロセッサコア

実験結果

主要結果

定理1: サイズ7のすべての整数集合{v₁,...,v₇}に対して、すべてのiについて‖tvᵢ‖ ≥ 1/8を満たす実数tが存在する。

証明過程

上界の計算: 系3からP < 7.4×10⁵⁴を得る
下界の構築:
- 補題4より：Pはlcm({2,3,4,5,6,7,8})で割り切れる
- 計算検証より：Pは集合S内のすべての素数で割り切れる
- したがってPはlcm({2,3,4,5,6,7,8}∪S) ≈ 1.82×10⁵⁵で割り切れる
矛盾: 下界が上界を超えるため、反例は存在しない