Unit Distance

主張: AI は科学的なブレイクスルーを起こせる。

証明: OpenAI の内部モデルが、離散幾何学における最も有名な予想、すなわち単位距離問題における格子の最適性（またはその欠如）を解決しました。この予想は、多くの関心が寄せられていたにもかかわらず、80 年前の提唱以来、全く進展が見られていませんでした（ただし、その周辺では多くの活動と進展がありました！）。

このスレッドでは、具体的に何が起こったのかを説明します。また、様々な難易度の説明が、私たちのブログ記事、世界的に著名な数学者によって執筆された付随論文（本日後日 arxiv に掲載予定）、元の AI による証明が記載されたレポート、そしてモデルが問題を解く際の（書き直された）思考の連鎖であるCoTでもご覧いただけます。

さて、何について話しているのか：問題は驚くほど単純です。平面上に n 個の点を置いたとき、それらの点間の距離のうち、同じ長さになるものはいくつあるでしょうか？（スケールを変えれば、それらの距離のうちいくつが 1 になり得るか、と問うこともでき、これが「単位距離問題」の名前の由来です）。もちろん、1 つの点を円の中心に置き、残りの全ての点をその点を中心とする円周上に置けば、n-1 個の距離が等しくなります。そして、距離の総数が最大でも n^2/2 であることは明らかです。では、真実はどうなのでしょうか？最良の結果は n のオーダーなのか、それとも n^2 のオーダーなのか？

Erdos が 1946 年にこの問題を紹介した際、彼はこの問題に対する最も自然な構成、すなわち単純な格子に点を配置する方法を分析しました。さて、格子状の点は 4 つの隣接点を持ちます。したがって、少なくとも約 2
個の距離が等しくなります（2n であって 4n ではないのは、二重カウントを避けるためです）。しかし、もう少し賢くなって、距離 1 の頂点（格子の辺の長さが 1 だとします）を見る代わりに、距離 sqrt(5) = sqrt(1+2^2) にある頂点を見てみましょう。小さな図を描けば、その距離に 8 個の点があることがわかります！実際、L 字型に沿ってあらゆる方向に移動することを考えれば（8 通りの方法があります）、そうなります。Erdos が証明したこと（そして以下でその証明を示します）は、このように 2 の累乗で、約 u(n) = 2^{log(n)/loglog(n)} まで進められるということです。つまり、格子には少なくとも約 u(n)
個の等しい距離が存在し、実際、この計算は格子にとって最適です。u(n)*n = n^{1+o(1)}（具体的には n^{1+cst/loglog(n)}）であることに注意してください。

Erdos が予想したのは、格子が本質的に最適である、つまり、任意の点の配置において、等しい距離は最大でも n^{1+o(1)} 個しかないだろうということです。これが、過去 80 年間全く進展がなかった問題であり、繰り返しますが、この問題がどれほど基本的で自然な疑問であるかという点で、多くの関心が寄せられていたにもかかわらずです。私の理解では、Erdos は格子が最適であると強く信じており、実際、密接に関連する問題（同じ 1946 年の論文で紹介されました！）である異なる距離の問題では、彼の考えは正しいことが証明されました。異なる距離の問題は、単にこの質問の逆のバージョンであり、n 個の点が作り得る異なる距離の最小数はいくつか、と問うものです。格子は n/sqrt(log(n)) 個の異なる距離を与え、10 年前の Guth と Katz による画期的な論文は、n/log(n) という下限を用いて、これが本質的に最適であることを示しました。言い換えれば、全てが格子が単位距離問題においても最適な候補であることを示唆していました。

ここで OpenAI の内部モデルが登場します。それは実際に、この長年信じられてきた信念を強く反証し、ある delta>0 に対して、等しい距離の数が n^{1+delta} のオーダーとなる、新しく（驚くべき）構成を発見しました。このブレイクスルーがどのようにしてモデルによって達成されたかについて少し述べる前に、まず Erdos の証明と、2^{log(n)/loglog(n)} がどこから来るのかについてもう少し詳しく説明する必要があります。そこには素数が潜んでいるのです！

素数について 2 つのことを仮定します。1 つ目は素数定理で、n 以下の素数は約 n/log(n) 個存在するというものです（実際にはもう少し精密なバージョンが必要ですが、この説明のレベルでは問題ありません）。2 つ目は、素数が 4 で割って 1 余る場合、それはガウス整数（a+ib の形で、a と b は整数）上で分解できる、つまり p = z bar{z} と表せるということです。例えば 5=(1+2i)(1-2i) であり、これは先ほど距離 sqrt(5) = sqrt(1+2^2) にある 8 個の頂点を数えたことを思い出させます。さて、4 で割って 1 余る最初の k 個の素数 p_1, …, p_k を取り、数 R=p_1…p_k = z_1 bar{z_1} … z_k \bar{z_k} を考えます。重要な点は、各素数 p_i に対して z_i または bar{z_i} のいずれかを選び、それらの積を取ることで、これから 2^k 個のガウス整数が得られ、その絶対値は sqrt{R} に等しいということです（ここで重要なのは、絶対値が乗法的であり、共役が絶対値を保存するという事実を用いていることです）。言い換えれば、格子の原点から距離 sqrt{R} の位置に 2^k 個の点を見つけたことになります！（正確には、これらの点が異なることも証明する必要があり、ここで Z[i] における一意分解が重要になります。これは新しい証明でも鍵となるものですが、ここでは無視しましょう。）あとは、sqrt{R}<sqrt{n}（後者は n 個の点を持つ格子の辺の長さ）を保ちながら、k をどれだけ大きく取れるかを計算するだけです。log(R) = sum_{i=1}^k log(p_i) であり、素数定理によりこれはおおよそ sum_{i=1}^k log(ilog(i)) となり、基本的に klog(k) です。したがって、klog(k) が log(n) より小さくなければならないので、k は log(n)/loglog(n) のようになり、主張された 2^k = 2^{log(n)/loglog(n)} が得られます。

上記の 1 段落の議論（賢い議論であることは認めます）は、80 年間最先端のままでした。今回 AI がやったことは、私の意見では非常にクレイジーです。まず第一に、CoT からわかるように、AI はほとんど即座に格子構成の改良を試みることを決定しました。これは、これまでほとんどの数学者が試みてきたこととは逆のことです。私の限られた理解では、AI が思いついた戦略（そしてそれを完璧に実行しました）は、おおよそ次のようなものです：素数を分割する方法がもっとあれば素晴らしいのではないか？おそらく、Q とは異なる、より高次の体を考えれば、整数 Z をその体の整数環で置き換えることでうまくいくのではないか？おそらく 2^k の代わりに 2^{f k} が得られるかもしれない。ここで f は体の次数である？最初の推測は円分拡大を見ることでしょうが、モデルは CoT で最初にそれを試み、すぐにこれではうまくいかないと気づきます。モデルは懸命に作業を続け、最終的にイデアルの言語を持ち出します。そこでは、類群によって処理される非一意分解が存在し得ます。ここから、全てのパラメータを制御しながら高次体を構築する方法を考え始める必要があります（まず類数ですが、これは高次元の格子でもあり、複素平面に射影し直す必要があり、この射影は制御が必要なある種の潰れを引き起こします、などなど）。そこでモデルは、類体論からの強力な道具、Golod-Shafarevich による無限タワーを使用します。この時点で、詳細については、この主題の実際の専門家による付随論文を参照するのが良いでしょう。

さて、少し立ち止まりましょう：基本的に AI がやったことは、数学の広大な知識を活用して、離散幾何学と代数的整数論の間の関連性を見出し、そして決定的に重要なことに、各ステップで専門家レベルの計算を行いながら、議論を見事に連鎖させることができたということです。これは真に画期的な結果ですが、同時に、モデルが「新しい数学」を「発明」したわけではないということも事実です（例えば、代替の類体論を発明したわけではありません。それが何を意味するにせよ）。しかし、ここが重要な点です：科学分野の全ての結果を深く知り、既知の議論を専門家として、そして適切なパラメータの選択とともに巧みに使用できる能力だけで、多くのブレイクスルーを生み出すことができ、これは数学に限らず、この種の（極めて）堅実な専門家の実行は、多くの科学の進歩の基盤なのです。

最後に、これが今後の数学にとって何を意味するかについて一言。付随論文には、その点に関する第一線の数学者による多くの考察が含まれているので、彼らの言葉を直接読むのが良いでしょう。しかし、注目すべき興味深い点の 1 つは、私たちはモデルの証明を arxiv に投稿しないということです。実際、伝統的な意味で貢献したと主張できる人間の著者はいないからです（もちろん、この素晴らしいモデルを生み出した OpenAI の全ての研究者、そして数千年にわたって数学を発展させてきた人類全体の成果ではありますが…）。一方、人間による付随論文は、この瞬間の重要性についての考察を超えて、証明を消化し、より広い文脈に位置づけ、さらにはそれを少し簡略化しています。コミュニティがこれらの新しい発展に完全に適応するにはまだ多くの作業が必要ですが、AI による証明と人間によるその理解を分離するというこの原則が、パズルの重要なピースになると私たちは信じています。