🔢 mathematics

Dead ends in square-free digit walks

この論文は、平方フリーな桁のウォークにおける「行き止まり」の漸近密度が約 $1.317\times 10^{-9}$ であり、これは確率論的モデルによる予測よりもおよそ4万倍小さいことを証明し、さらにAxiomProverシステムによってLean/Mathlib内で完全に形式化された結果を用いて、あらゆる基数におけるこれらの密度の閉形式の表現を確立するものである。

原著者： Evan Chen, Chris Cummins, Ben Eltschig, Dejan Grubisic, Leopold Haller, Letong Hong, Andranik Kurghinyan, Kenny Lau, Hugh Leather, Seewoo Lee, Aram Markosyan, Ken Ono, Manooshree Patel, Gaurang Pendha

公開日 2026-02-09

📖 1 分で読めます🧠 じっくり読む

CC BY 4.0

原著者： Evan Chen, Chris Cummins, Ben Eltschig, Dejan Grubisic, Leopold Haller, Letong Hong, Andranik Kurghinyan, Kenny Lau, Hugh Leather, Seewoo Lee, Aram Markosyan, Ken Ono, Manooshree Patel, Gaurang Pendharkar, Vedant Rathi, Alex Schneidman, Volker Seeker, Shubho Sengupta, Ishan Sinha, Jimmy Xin, Jujian Zhang

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

このゲーム：「平方自由数による桁の散歩」

数字を使ったゲームをしていると想像してください。あなたはまず、**「平方自由（square-free）」**な数字からスタートします。

平方自由とは何か？ それは、その数字の中に（1を除いて）完全平方数が因数として隠れていない数字のことです。例えば、10は平方自由です（ $2 \times 5$ ）。しかし、12は違います（ $4 \times 3$ であり、4は平方数です）。
動き： あなたは、数字の末尾に1桁ずつ数字を付け足していくことで、無限へと「歩いて」いこうとします。もし手元の数字が5なら、50、51、52、..., 59へと進むことができます。
ルール： 新しく作るすべての数字も、必ず「平方自由」でなければなりません。もし平方自由ではない数字を作ってしまったら、そのルートは「行き止まり（デッドエンド）」となります。

大きな問い： あなたは永遠に歩き続けることができるでしょうか？ある開始数字と数字の並びを選べば、決して行き止まりにぶつかることなく、無限へと歩みを進めることは可能でしょうか？

旧来の仮説：「コイン投げ理論」

この論文が登場する前、数学者たち（具体的には Miller ら）は、この問題を「確率的」あるいはランダムなモデルを用いて考察していました。彼らは平方自由であることを、コイン投げのように扱いました。

すべての数字の約60%が平方自由です。
彼らは、一歩進むごとに、付け足すべき「安全な」数字が見つかる確率が60%であると考えました。
選択肢となる数字が10個あるため、彼らは行き止まり（デッドエンド）に遭遇する確率は非常に低いと計算しました。
彼らの予測： 彼らは、行き止まりは非常に稀であり、100万個の数字につき約52回程度しか発生しないと考えていました。つまり、無限への歩行はほぼ保証されていると考えていたのです。

新たな発見：「算術の罠」

この論文は、「コイン投げ理論」が間違っていることを証明しています。実際の数の世界は、ランダムなコイン投げよりもずっと頑固なのです。

著者たち（人間の数学者と、AxiomProver と呼ばれるAIツールの混合チーム）は、行き止まりは実際には極めて稀であり、およそ10億個に1回であることを発見しました。

なぜ違いが出るのか？
「コイン投げ」モデルは、失敗する理由が互いに独立していると想定していました。つまり、数字「0」のせいで失敗することと、数字「1」のせいで失敗することは無関係だと考えていたのです。

しかし現実には、算術のルールが厳格な罠を作り出しています。

比喩： 10種類の鍵を使ってドアに鍵をかける場面を想像してください。旧来の理論では、それぞれの鍵が独立して60%の確率で機能すると考えていました。
現実： 「鍵（$4, 9, 25, 49$ といった素数の平方）」は非常に好みが激しいものです。ある数字が10個の数字すべてに対して失敗するためには、多くの異なる素数を同時に満たすという、非常に特殊で複雑な条件を満たさなければなりません。
これらの条件は非常に特殊で相互依存しているため、あらゆる次の桁に対して失敗するような数字を見つけることは、信じられないほど困難なのです。そのため、ランダムなモデルは行き止まりの頻度を大幅に過大評価していました。

結果：新しい公式

この論文は、任意の基数（10進法に限らず）において、これらの行き止まりがどれほど稀であるかを正確に算出するための精密な数学的公式（「閉形式の式」）を提供しています。

10進法の場合、行き止まりの真の密度は約 $1.3 \times 10^{-9}$ です。
これは、旧来の予測よりも4万倍も小さい数値です。

「AI」のひねり：AxiomProver

この論文のユニークな点は、その数学が「どのように」行われたかという点にあります。

著者たちは単に手作業で証明を書いたのではありません。彼らは AxiomProver というAIツールを使用しました。
彼らはAIに、問題の平易な英語による説明を与えました：「平方自由数の桁の散歩における行き止まりの密度を見つけよ」。
AIは単に推測したのではなく、公式を導き出し、Lean と呼ばれるコンピュータ言語で形式的な証明を書き上げました。
その後、コンピュータがステップごとに証明を検証し、それが100%論理的に正しいことを確認しました。
その後、人間の著者たちが、このコンピュータ生成された証明をもとに、他の人間に説明するためのこの論文を執筆したのです。

歴史に関する注記（「アップデート」）

この論文には重要なアップデートが含まれています。彼らが研究を発表した後、Mirsky という数学者が、実はこれと全く同じ問題を1947年に解決していたことが判明しました。

Miller らによる2024年の論文（この「コイン投げ」論争の出発点となったもの）は、Mirsky の1947年の研究を引用し忘れていました。
したがって、この論文の数学自体は正しいですし、AIによる証明も素晴らしい成果ですが、結果そのものは数学の歴史において新しいものではありません。著者たちは、この答えがすでに知られているため、学術誌には投稿しないことに決めましたが、自分たちのAIツールがいかに既存の数学を再発見できるかを示すために、この内容を共有することにしました。

まとめ

ゲーム： 平方自由ではない数字にぶつかることなく、永遠に数字を付け足し続けることができるか？
旧来の見解： はい、ほぼ確実に可能です。行き止まりは稀です（2万個に1回）。
新しい見解： 行き止まりは極めて稀です（10億個に1回）。なぜなら、数学のルールはランダムな確率よりも厳しいからです。
手法： AxiomProver というAIツールが、正解となる公式を導き出し、それを証明しました。これにより、忘れ去られていた1947年の結果を再発見しました。

技術要約：平方フリーな数字ウォークにおけるデッドエンド（行き止まり）

問題の定義
本論文は、平方フリーな数字ウォークにおける「デッドエンド（行き止まり）」の存在と密度について調査している。底（基数） $b$ における「平方フリー・ウォーク」とは、平方フリーな整数 $N_0$ から始まり、各項 $N_{k+1} = bN_k + d$ （ここで $d \in \{0, \dots, b-1\}$ ）が平方フリーであり続けるように、数字 $d$ を末尾に付加して無限列 $N_0, N_1, N_2, \dots$ を構築しようとする試みである。

正の整数 $N$ が以下の条件を満たすとき、デッドエンドと定義される：

$N$ は平方フリーである。
底におけるすべての数字 $d$ に対して、拡張された $bN + d$ が平方フリーではない。

Millerら [5] によって提起された中心的な問いは、無限の平方フリー・ウォークが存在するかどうかである。確率的モデル（「ブラインド・アンリミテッド・モデル」）は、無限のウォークが存在する確率がほぼ1であることを示唆しており（これは、底10においてデッドエンドの漸近密度が $\approx 5.218 \times 10^{-5}$ であることを意味する）、デッドエンドは稀であると考えている。本論文は、この確率的予測が成立するかどうかを判断するために、デッドエンドの実際の算術的密度を厳密に分析するものである。

手法
著者らは、確率的仮定を回避し、初等的な乗法的数論と包含除外の原理を組み合わせた手法を用いている。

指示関数: 問題はメビウス関数 $\mu(n)$ を用いて再定式化される。 $\mu(n)^2$ は平方フリー整数であることを示す指示関数であるため、デッドエンド $N$ の指示関数は次のように表される：
$\mathbb{1}_{N \text{ is dead end}} = \mu(N)^2 \prod_{d \in D} (1 - \mu(bN + d)^2)$
ここで $D$ は数字の集合である。
包含除外: 積の項は、数字の集合のすべての部分集合 $S$ に関する和へと展開される。これにより、デッドエンドの計数関数 $D_b(X)$ （ $X$ 以下のデッドエンドの数）は、計数関数 $Q_S(X)$ の交互和へと変換される。ここで $Q_S(X)$ は、 $n$ とすべての拡張 $bn+d $（$ d \in S $）が平方フリーであるような$ n \le X$ を数える。
篩（ふるい）分析: 固定された部分集合 $S$ に対して、 $n$ と $bn+d $が共に平方フリーであるという条件は、素数ごとに分析される。著者らは、回避すべき「悪い」剰余類$ \pmod{p^2}$ を定義する。中国剰余定理を用いることで、これらの剰余類を避ける整数の密度を決定する。
- 大きな素数 $p$ （ $p \nmid b$ ）の場合、 $p^2 \mid (bn+d)$ という条件は、 $n$ を $\pmod{p^2}$ における単一の剰余類に強制する。極めて重要なことに、単一の素数の平方は、一度に高々一つの数字の拡張しか阻止できない。
- 密度は、局所因子の無限積（オイラー積） $(1 - \nu_{p,b}(S)/p^2)$ として表現される。ここで $\nu_{p,b}(S)$ は禁止された剰余類の数である。
誤差項の制御: 篩をパラメータ $z$ で打ち切ること、および大きな素数の寄与から生じる誤差項を注意深く境界付け、誤差項を $O(X/\sqrt{\log X})$ と確立する。

主要な結果

定理 1.1 (底 10): 底10におけるデッドエンドの漸近密度は存在し、次のように与えられる：
$c_{\text{dead}} = \sum_{S \subseteq \{0,\dots,9\}} (-1)^{|S|} \prod_{p \text{ prime}} \left( 1 - \frac{\nu_p(S)}{p^2} \right)$
ここで $\nu_p(S)$ は、 $p^2 \mid n$ または $p^2 \mid (10n+d)$ （ある $d \in S$ に対して）を満たす $n \pmod{p^2}$ の剰余類の数である。
計算された値は $c_{\text{dead}} \approx 1.317 \times 10^{-9}$ である。
定理 1.2 (一般の底 $b$ ): この結果は、任意の底 $b \ge 2$ に対して一般化される。密度 $c_{\text{dead}}(b)$ は、オイラー積の交互和を含む同様の閉形式の式で与えられる。論文では、素数である底 $b \in \{2, 3, 5, 7\}$ についての近似値も示されている。
確率的モデルとの乖離: 真の密度（ $\approx 1.3 \times 10^{-9}$ ）は、確率的予測（ $\approx 5.2 \times 10^{-5}$ ）よりも約4万倍小さい。本論文はこの原因を算術的依存性に求めている。素朴な確率的モデルは、数字の拡張間の独立性を仮定しているが、実際には、10個すべての拡張が同時に失敗するためには、多くの異なる素数の平方による同時的な阻止が必要であり、これは独立な確率モデルが示唆する条件よりもはるかに厳しい条件である。

意義および主張

予想の解決: 本論文は、確率的ヒューリスティックは無限のウォークがほぼ確実であることを予測する一方で、実際の算術構造によってデッドエンドは予測よりも大幅に稀であることを示している。しかし、無限のウォークの存在自体は依然として未解決の問題である。本論文は「障害」（デッドエンド）の稀少性を定量化しているが、無限のパスの存在を証明したわけではない。
定式化: 本論文の主要な主張は、主定理（定理 1.2）が Lean/Mathlib で完全に形式化され、その証明が AxiomProver という AI ツールによって 自動的に生成された ことである。このシステムには問題の自然言語による記述のみが提供され、閉形式の公式と証明を自律的に導出した。
歴史的背景（更新）: 著者らは、arXiv への最初の投稿後、主たる結果がすでに Mirsky によって 1947 年に得られていた [6] ことを Kannan Soundararajan から教えられたと述べている。論文は、2024 年の Miller ら [5] の研究がこの先行研究に言及できなかったことを認めている。したがって、Lean による形式化は有効な自動証明ではあるものの、著者らは、本稿は主要な研究貢献として学術誌に投稿するのではなく、自動定理証明のケーススタディとして扱うとしている。

結論
本論文は、平方フリーな数字ウォークにおけるデッドエンドの密度を、厳密な算術的導出によって明らかにし、算術的依存性によって確率的予測から大幅に乖離していることを示した。その最も斬新な貢献は、この結果を AxiomProver を用いてエンドツーエンドで自動的に形式化したことであり、解析数論における非自明な問題を扱う現在の AI システムの能力を示している。