孤独なランナーの推測

数論、特にディオファントス近似の研究において、孤独なランナー予想は、円形のトラックを走るランナーの長期的な行動に関する予想です。これは、一定の速度で走る単位長さのトラックを走るランナーは、それぞれが互いに異なるため、ある時点ではそれぞれが孤独になる、つまり他のランナーから少なくとも単位は離れるという予想です。 ${\displaystyle n}$${\displaystyle 1/n}$

この予想は、1967年にドイツの数学者イェルク・M・ウィルスによって純粋に数論的な観点から初めて提唱され、1974年にはTW・カジックによって独立に提唱された。その説明的かつ現在広く普及している定式化は1998年にさかのぼる。この予想はランナーが7人以下の場合に成り立つことが知られているが、一般の場合は未解決のままである。この予想の含意には、視界障害問題の解決や、特定のグラフの 彩色数に関連する特性の境界などがある。

単位長さの円形トラック上のランナーについて考えます。初期時刻 では、すべてのランナーが同じ位置にいて走り始めます。ランナーの速度は一定で、すべて異なり、負の場合もあります。ランナーが他のすべてのランナーから少なくとも の距離 (円に沿って測定) にいる場合、そのランナーは時刻 に孤独であると言われます。孤独ランナー予想は、速度の選択に関係なく、各ランナーがある時刻に孤独であると述べています。^[1]${\displaystyle n}$${\displaystyle t=0}$${\displaystyle t}$${\displaystyle 1/n}$

この予想の視覚的定式化は、1998 年に初めて発表されました。^[2] Jörg M. Wills によるオリジナルの定式化を含む多くの定式化では、^{[3] [4]}いくつかの簡略化が行われています。孤独になるランナーは 0 で静止しているため (速度がゼロ)、速度がゼロでない他のランナーが考慮されます。^{[a]移動するランナーは、}正の速度のみにさらに制限される場合があります。対称性により、速度がおよびのランナーは常に 0 から同じ距離にあるため、本質的に同等です。静止しているランナーの結果を証明すると、すべてのランナーに対する一般的な結果が示されます。これは、すべてのランナーからそのランナーの速度を減算して速度を 0 にすることでランナーを静止させることができるためです。次に、この予想は、正の異なる速度の任意の集合について、 となる時間が存在することを 述べています。 ここで、 はの小数部を表します。^[6]視覚的に解釈すると、ランナーが反時計回りに走っている場合、不等式の中間の項は、反時計回りに測った、時刻における原点から 番目のランナーまでの距離です。 ^[b]この規則は、この記事の残りの部分で使用されます。ウィルズの予想は、分数が無理数をどの程度正確に近似できるかを研究するディオファントス近似^[7]の研究の一部でした。 ${\displaystyle n-1}$${\displaystyle x}$${\displaystyle -x}$${\displaystyle v_{1},v_{2},...,v_{n-1}}$${\displaystyle t>0}$$${\displaystyle {\frac {1}{n}}\leq \operatorname {frac} (v_{i}t)\leq 1-{\frac {1}{n}}\qquad (i=1,...,n-1),}$$${\displaystyle \operatorname {frac} (x)}$${\displaystyle x}$${\displaystyle i}$${\displaystyle t}$

がn次元空間 ( )にある一辺の長さのn超立方体であるとする。半整数座標を持つすべての点に の中心コピーを配置する。原点からの光線は のすべてのコピーを避ける可能性があり、その場合は (無限小の) 隙間があるが、少なくとも 1 つのコピーに当たる。Cusick (1973) はこの文脈で孤独なランナー予想の独自の定式化を行った。この予想は、座標超平面の 1 つにある光線を無視して、 の場合にのみ隙間があることを示唆している。^[8]たとえば、2 次元空間に配置すると、一辺の長さが よりも小さい正方形は図のように隙間を残し、一辺の長さが 以上の正方形は軸に平行でないすべての光線を遮る。この予想は、この観察を任意の数の次元に一般化している。 ${\displaystyle C}$${\displaystyle s}$${\displaystyle n\geq 2}$${\displaystyle C}$${\displaystyle C}$${\displaystyle s<(n-1)/(n+1)}$${\displaystyle 1/3}$${\displaystyle 1/3}$

グラフ理論では、整数の集合上の距離グラフで、正の整数距離の有限集合がいくつか使用されており、 の間に辺が存在するのは の場合であり、 の場合に限ります。たとえば、 の場合、偶数および奇数の連続するすべてのペアは隣接しており、すべてを合わせて 2 つの連結成分を形成します。ステップ による整数のk正則彩色では、を法とする剰余に基づいて各整数に色のいずれか 1 つを割り当てます。たとえば、 の場合、彩色はすべての整数を繰り返し、各整数のペアは同じ色です。 を取ると、孤独なランナー予想により、あるステップ値に対して適切なk正則彩色（つまり、各ノードは隣接ノードとは異なる色に彩色される）が認められることになります。^[9]たとえば、は によって生成される距離グラフ上に適切な彩色を生成します。（は の正則彩色数として知られています。） ${\displaystyle G}$${\displaystyle D}$${\displaystyle x,y}$${\displaystyle |xy|\in D}$${\displaystyle D=\{2\}}$${\displaystyle \lambda \in \mathbb {R} }$${\displaystyle n}$${\displaystyle k}$${\displaystyle \lfloor \lambda n\rfloor }$${\displaystyle k}$${\displaystyle \lambda =0.5}$${\displaystyle 2k}$${\displaystyle 2m,2m+1}$${\displaystyle k=|D|+1}$${\displaystyle G}$${\displaystyle (k,\lambda )=(2,0.5)}$${\displaystyle D=\{2\}}$${\displaystyle k}$${\displaystyle D}$

有向グラフ が与えられたとき、上のnowhere-zero フローは各エッジ に正の値を関連付け、各ノードからの外向きのフローが内向きのフローと等しくなるようにします。孤独なランナー予想は、 が最大で異なる整数値を持つ nowhere-zero フローを持つ場合、 はのみ の値を持つ nowhere-zero フローを持つことを意味します( のいくつかのアークの方向を反転した後でも可能です)。この結果は別の方法で に対して証明され、孤独なランナー予想のより小さなケースは解決されているため、完全な定理が証明されています。^[10]${\displaystyle G}$${\displaystyle G}$${\displaystyle f(e)}$${\displaystyle e}$${\displaystyle G}$${\displaystyle k}$${\displaystyle G}$${\displaystyle \{1,2,\ldots ,k\}}$${\displaystyle G}$${\displaystyle k\geq 5}$

ランナーの配置が与えられた場合、 はランナーの孤独の最大距離の最小値を表し、孤独のギャップ^[11]はランナーがいるすべての配置における最小値を表します。この表記法では、予想は を主張しており、この境界は正しい場合、改善できません。たとえば、孤独になるランナーが静止していて、速度が選択されている場合、それらが他のすべてのランナーから 単位以上離れている時間は存在しないため、 となります。^{[c]あるいは、この結論は}ディリクレ近似定理から簡単に導き出すことができます。 の単純な下限は、確率の議論によって取得できます。^[12]${\displaystyle \delta}$ ${\displaystyle \delta_{n}}$${\displaystyle \delta}$${\displaystyle n}$${\displaystyle \delta _{n}\geq 1/n}$${\displaystyle v_{i}=i}$${\displaystyle 1/n}$${\displaystyle \delta_{n}\leq 1/n}$${\displaystyle n\geq 2}$${\displaystyle \delta _{n}\geq 1/(2n-2)}$

この予想は、ランナーの速度を正の整数に制限することに帰着します。つまり、この予想が整数速度のランナーに当てはまるなら、実数速度のランナーにも当てはまります。 ^[13]${\displaystyle n}$${\displaystyle n}$

下限については若干の改善が知られている。Chen & Cusick (1999)は、が素数であれば、が素数であれば であることを示した。Perarnau & Serra (2016)は、十分に大きい に対して無条件に であること を示した。${\displaystyle 1/(2n-2)}$${\displaystyle n\geq 5}$${\displaystyle 2n-5}$${\displaystyle \delta _{n}\geq {\tfrac {1}{2n-5}}}$${\displaystyle 4n-9}$${\displaystyle \delta _{n}\geq {\tfrac {2}{4n-9}}}$${\displaystyle n}$$${\displaystyle \delta _{n}\geq {\frac {1}{2n-4+o(1)}}.}$$

タオ（2018）は、現在最もよく知られている漸近的結果である、十分に大きい に対して、 ある定数 に対してを証明しました。彼はまた、整数速度のサイズ（ビッグオー記法を参照）に対する予想を証明することで、完全な予想が暗示されることも示しました。この含意により、理論的には、有限のケースセットをチェックすることで、与えられた に対する予想を証明することができますが、ケースの数があまりにも急速に増加するため、実用的ではありません。^[14]${\displaystyle n}$$${\displaystyle \delta _{n}\geq {\frac {1}{2n-2}}+{\frac {c\log n}{n^{2}(\log \log n)^{2}}}}$$${\displaystyle c>0}$${\displaystyle n^{O(n^{2})}}$${\displaystyle n}$

この予想は、ランナーの速度に関する特定の仮定の下で証明されています。 が十分に大きい場合、 で あれば が成り立ちます。言い換えれば、が十分に大きい場合、 が成り立ちます。定数 22 を 33 に置き換えると、 が成り立ちます。^[15]が十分に大きい場合の同様の結果を得るには、について同様の仮定が必要です。^{[14] が}無条件に である場合、すべての について であれば、この予想は真です。^[16]${\displaystyle n}$$${\displaystyle {\frac {v_{i+1}}{v_{i}}}\geq 1+{\frac {22\log(n-1)}{n-1}}\qquad (i=1) ,...,n-2).}$$${\displaystyle n}$${\displaystyle n\geq 16343}$${\displaystyle n}$${\displaystyle i=\lfloor n/22\rfloor -1,...,n-2}$${\displaystyle n}$${\displaystyle v_{i+1}/v_{i}\geq 2}$${\displaystyle i}$

この予想はランナーに対しては正しい。 の証明は初歩的であり、この事例は 1972 年に確立された。 ^[17]、、の事例はそれぞれ 1984 年、2001 年、2008 年に解決された。 の最初の証明はコンピュータ支援によるものであったが、それ以降のすべての事例は初歩的な方法で証明されている。^[18]${\displaystyle n\leq 7}$${\displaystyle n\leq 3}$${\displaystyle n=4}$${\displaystyle n=5}$${\displaystyle n=6}$${\displaystyle n=7}$${\displaystyle n=5}$

いくつかの に対して、最大分離が である散発的な例が、上記のの例の他に存在します。 ^[6]に対して、（シフトとスケーリングを除いて）唯一知られている例は です。 に対して、唯一知られている例は です。 に対して、既知の例はとです。^[19]このような散発的なケースの明示的な無限族が存在します。^[20]${\displaystyle n}$${\displaystyle 1/n}$${\displaystyle v_{i}=i}$${\displaystyle n=5}$${\displaystyle \{0,1,3,4,7\}}$${\displaystyle n=6}$${\displaystyle \{0,1,3,4,5,9\}}$${\displaystyle n=8}$${\displaystyle \{0,1,4,5,6,7,11,13\}}$${\displaystyle \{0,1,2,3,4,5,7,12\}}$

Kravitz (2021) は、ほぼ等しいケースを扱う、より明確な予想を定式化しました。より具体的には、彼は、与えられた速度のセット に対して、ある正の整数、^[d]または のいずれかに対して、そのセットアップの孤独のギャップであると予想しています。彼は、およびいくつかの特殊なケース に対してこの予想を確認しました。${\displaystyle v_{i}}$${\displaystyle \delta =s/(s(n-1)+1)}$${\displaystyle s}$${\displaystyle \delta \geq 1/(n-1)}$${\displaystyle \delta}$${\displaystyle n\leq 4}$

Rifford (2022) は、ランナーが孤独になるまでの時間の大きさの問題に取り組みました。彼は、すべての整数に対して、任意の正の異なる速度の集合に対して、に対して となる時間が存在するような正の整数が存在するという、より強い予想を立てました。Rifford は、に対して この予想を確認し、それぞれの場合の最小値はに対して、に対してで与えられることを示しました。後者の結果 (に対して) は、で 一定速度で かつ が異なり正である状態で時間 に からスタートする 6 人のランナーを考えると、最も遅い非静的ランナーの最初の 2 ラウンドでは、静止したランナーは他のランナーから少なくとも一定の距離だけ離れている(ただし、最初のラウンドではそうである必要はない) ことを示しています。 ${\displaystyle n\geq 3}$${\displaystyle N}$${\displaystyle v_{1},v_{2},...,v_{n-1}}$${\displaystyle t>0}$${\displaystyle \operatorname {frac} (v_{i}t)\in [1/n,1-1/n]}$${\displaystyle i=1,...n-1}$$${\displaystyle t\leq {\frac {N}{\operatorname {min} (v_{1},...,v_{n-1})}}.}$$${\displaystyle n=3,4,5,6}$${\displaystyle N}$${\displaystyle N=1}$${\displaystyle n=3,4,5}$${\displaystyle N=2}$${\displaystyle n=6}$${\displaystyle N=2}$${\displaystyle n=6}$${\displaystyle 0}$${\displaystyle t=0}$${\displaystyle v_{0},v_{1},...,v_{5}}$${\displaystyle v_{0}=0}$${\displaystyle v_{1},...,v_{5}}$${\displaystyle 1/6}$

ランダムに選ばれた速度については、より強い結果が得られる。すなわち、定常ランナーの慣例を用いると、と が固定され、 から非ゼロ速度のランナーが一様にランダムに選ばれる場合、 となる。言い換えれば、ランダム速度のランナーは、ある時点で「非常に孤独」になる可能性が高い。つまり、最も近い他のランナーからほぼ 単位離れているということである。 ^[21]「孤独」を「ほぼ孤独」に置き換えると、つまり、あるランナーの周囲には最大で 1 人の他のランナーしかいない場合、完全な予想が成り立つ。^{[22]この予想は、}代数関数体における類似物に一般化されている。^[23]${\displaystyle n}$${\displaystyle \varepsilon >0}$${\displaystyle n-1}$${\displaystyle \{1,2,\ldots ,k\}}$${\displaystyle P(\delta \geq 1/2-\varepsilon )\to 1}$${\displaystyle k\to \infty }$${\displaystyle 1/2}$${\displaystyle 1/n}$

• Open Problem Garden第4号551-562ページの記事。