A proof of the cyclotomic conjecture and the non-existence of almost Moore digraphs

あなたは、最も効率的な都市を築こうとしている熟練の建築家であると想像してください。あなたには厳格なルールがあります。すべての建物（「ノード」）は、限られた数の隣人（「次数」）にのみメッセージを送ることができ、かつ、メッセージが都市内の他の建物に到達するのにあまり多くのステップ（「直径」）を要してはなりません。数学の世界、特にグラフ理論と呼ばれる分野では、これは「次数・直径問題」として知られています。それは、全員がわずかな数の握手しかできない状況で、最大限の人数を部屋に詰め込み、かつ、全員が数回の紹介を経て全員に挨拶できるような状況を作ることに似ています。

数学者たちは、これらの方則の下で構築できる「完璧な」都市のサイズに関する理論的な最大値、「ムーア境界」を古くから知っています。しかし、これらの完璧な都市は極めて稀であり、非常に単純で退屈なシナ起においてのみ存在します。このことは、数学者たちに、ある魅力的な問いを投げかけました。もし、これらが複雑で大規模な都市であった場合、一体どうなるのか？ という問いです。これらは「ほぼムーア・ダイグラフ（almost Moore digraphs）」と呼ばれます。

ジャスカラン・カウルとヒテシュ・クマールによるこの論文は、そのケースを締めくくる最終的な探偵報告書としての役割を果たしています。著者たちは、建物が1つ以上の出力接続を持ち、経路長が2より大きいあらゆる複雑なシナリオにおいて、これらの「ほぼ完璧な」都市は存在しないことを証明しました。これを解決するために、彼らは単に都市の地図を見たのではありません。彼らは、「円分多項式」という深く抽象的な世界へと潜り込む必要がありました。これらの多項式は、都市の構造の「秘密のDNA」あるいは「根底にある音楽のスコア」のようなものです。この論文は、この数学的DNAが複雑な都市においてどのように振る舞うかについての長年の推測（「円分予想」）を証明しています。彼らは、この数学的DNAが複雑化すると特定の 방식으로分解されることを示すことで、「ほぼ完璧な」都市を構築することは数学的に不可能であることを証明したのです。

失われた都市の謎

有向ネットワーク（接続に方向があるもの、例えば一方通行の道）の世界では、数学者たちは、各建物からの出口の数（$d$）と最大移動時間（$k$）が与えられたときに構築できる最大の都市に関する公式を持っています。この公式、$M_{d,k} = 1 + d + \dots + d^k$ は、「ムーア境界」と呼ばれる理論的な天井です。

私たちは、この天井に正確に達する都市がほとんど存在しないことを知っています。それらは、単純なループや完全に接続されたハブのような、些細なケースにおいてのみ現れます。したがって、大きな疑問は、これらよりもわずか一歩分だけ小さい都市についてはどうなのか？ ということでした。これらの「ほぼムーア・ダイグラフ」は、聖杯（究極の目標）でした。もしそれらが存在すれば、それらは複雑なシステムのための最も効率的なネットワークとなるはずでした。

長年、数学者たちは小さなケースを検証してきました。特定の、ごく小さなセットアップについてはいくつか発見されましたが、より大きく、より興味深い数値においては、探索は空振りに終わりました。なぜなら、これらが存在しないことを証明するには、円分多項式に関する非常にトリッキーなパズルを解く必要があったからです。これらは、1のべき根（円の基本周波数のようなもの）に関連する特別な数学的表現です。

鍵となるのは：円分予想

本論文の著者たちは、これらの「ほぼ完璧な」都市の存在が、$F_{n,k}(x)$ と呼ばれる多項式の特定の特性に完全に依存していることに気づきました。この多項式は、円分多項式（$\Phi_n$）に単純な和（$1 + x + \dots + x^k$）を代入することによって構築されます。

1999年、ある数学者が、この多項式 $F_{n,k}(x)$ がいつ「既約（分解されない）」であり、いつ「可約（分解される）」であるかを正確に記述する「円分予想」を提唱しました。

• もし多項式が既約であれば、それは固く、壊れないブロックとして機能します。
• もし多項式が可約であれば、それはより小さな断片へと分裂します。

この接続は極めて重要です。もし多項式が特定の形で分解されるならば、それは「ほぼムーア」な都市が存在できることを意味します。もし多項式がそのままの形で維持されるならば、その都市は不可能です。以前の研究者たちは、小さな数字についてはこれを証明してきましたが、一般的なケースは謎のままでした。

突破口：予想の証明

カウルとクマールは、小さな数字だけでなく、すべての 数字に対してこの予想を証明するために介入しました。彼らは、多項式 $F_{n,k}(x)$ を、その歯車（根と係数）がどのように相互作用するかを見るための複雑な機械として扱いました。

彼らは、補助的な多項式 $q(x)$ を定義しました。これは、ひねりを加えた円分多項式のようなものです。次に、彼らは $q(x)$ とその鏡像である $q^\#(x)$ の間の「最大公約数」を分析しました。このステップは、機械がバラバラにならないように、緩んだネジがないかチェックするようなものでした。

彼らの分析は、厳格なルールを明らかにしました：

1. $k$ が偶数の場合： 多項式は、$n$ が $k+2$ を割り切る場合にのみ分解されます。
2. $k$ が奇数の場合： 多項式は、$n$ が偶数であり、かつ $2(k+2)$ を割り切る場合にのみ分解されます。

その他のすべてのケースにおいて、多項式は既約（分解されない状態）のままです。

最終判決：存在する「ほぼ完璧な」都市はない

予想が証明されたことで、著者たちはこの論理を都市建設の問題に適用しました。彼らは、各建物につき1つ以上の出口を持つ（$d > 1$）かつ、移動時間が2ステップを超える（$k > 2$）あらゆる都市について、「ほぼムーア」な都市が存在するために必要な数学的条件が満たされないことを示しました。

多項式 $F_{n,k}(x)$ は、都市の形成を妨げるまさにその方法で既約のままとなります。その結果、著者たちはそのようなダイグラフは存在しないことを証明しました。

これは、これらのルールに基づいて構築しようとするいかなる複雑なネットワークにおいても、理論上の最大サイズまであと1つのノードにさえ到達できないことを意味します。最高のネットワークと理論的限界との差は、少なくとも2つのノードです。「ほぼ完璧な」都市は、数学的な神話なのです。

論文は、有向次数・直径問題がこれらのパラメータに対して決定的な答えを持っていることを確認して締めくくられています。すなわち、最大のネットワークは常にムーア境界よりも少なくとも2ステップ小さくなります。「ほぼムーア」ダイグラフの探索は終了しました。そもそも、それは存在していなかったのです。