CayleyPy Growth: Efficient growth computations and hundreds of new conjectures on Cayley graphs (Brief version)

この論文は、群論におけるケイリーグラフの効率的な成長計算と直径推定を実現するオープンソースライブラリ「CayleyPy」の公開を報告し、これを用いて対称群や零乗群などに関する 200 件以上の新たな予想や、NP 困難な問題に対する効率的な解法、および 1968 年のグシュコフの問題への回答などを導き出したことを述べています。

要約

1. この研究の正体：巨大な迷路の地図作り

まず、この研究の舞台は**「ケイリーグラフ（Cayley graph）」というものです。
これを「巨大な迷路」**と想像してください。

• 迷路の入り口： 整然と並んだ状態（例えば、1, 2, 3, 4... と並んだカード）。
• 迷路の出口： 全く別の状態（例えば、4, 1, 3, 2... とバラバラになったカード）。
• 移動ルール（生成元）： 「カードを 2 枚入れ替える」「3 枚連続で回す」といった、決まった操作だけができる。
• ゴール： 「入り口から出口まで、最短で何歩で辿り着けるか？」という**「直径（ダイアメーター）」**を見つけること。

この迷路は、ルビークのキューブやパズル、さらには DNA の並び替え（進化の距離）など、現実世界の多くの問題と似ています。しかし、この迷路は**「あまりにも広大」です。
例えば、15 個のカードを並べるパズルの場合、迷路の広さは「100 京（10000 兆）」**を超えます。従来のコンピュータ（GAP や Sage という有名な道具）では、この迷路の全貌を調べるのに何十年もかかり、あるいは計算が追いつきませんでした。

2. 新しい武器：CayleyPy（ケイリー・パイ）

そこで登場したのが、この論文の主役である**「CayleyPy」**です。

• どんなもの？ 人工知能（AI）と高速な計算機（GPU）を駆使して作られた、新しい「迷路探査ツール」です。
• 何がすごい？ 従来の道具よりも**「1000 倍速く」、そして「1000 倍大きな迷路」**を処理できます。
  • 例え話：従来の道具が「徒歩で山を登る」なら、CayleyPy は「ヘリコプターで空から一瞬で全体を把握する」ようなものです。

このツールを使って、研究チームは**「数百個の新しい数学的な予想（仮説）」**を見つけ出しました。

3. 発見された驚きの法則たち

CayleyPy で膨大なデータを解析したところ、以下のような面白いパターンが見つかりました。

① 「迷路の広さ」は実は簡単？（準多項式予想）

通常、迷路の最短距離（直径）を見つけるのは「超難問（NP 困難）」とされています。しかし、CayleyPy のデータを見ると、**「迷路の広さは、n（カードの数）によって決まる、とても単純な公式（多項式）」**で表せるようです。

• 例え話： 「迷路が広くなるにつれて、その広さは『n の 2 乗』のような、きれいな曲線を描いて増えている」という発見です。これなら、巨大な迷路でも公式を当てはめるだけで、広さを推測できます。

② 「最悪のケース」の形（正方形とひげ）

「最も遠くまで行くには、どんな操作を組み合わせればいいか？」という「最悪のケース（アンチポッド）」を探したところ、ある特定の**「パターン」**が見つかりました。

• 発見： 多くの場合、最も遠くへ行くための操作は、**「正方形（4 つのループ）」と、そこから伸びる「ひげ（2 つの枝）」**のような形をしています。
• 意味： 数学的に複雑に見える問題も、実は「正方形とひげ」というシンプルで美しいルールに従っている可能性があります。

③ 1968 年の難問に回答（グルシュコフの問題）

ソ連の cybernetics（制御工学）の父と言われるグルシュコフが 1968 年に投げかけた「ある特定の操作で並べ替える場合、何歩かかるか？」という 50 年以上の懸案事項について、CayleyPy のデータから**「答えの公式」**を提案しました。

• 結果： 「奇数のときは A、偶数のときは B」という、きれいな数式で表せることがわかりました。

④ 分布は「ベル型」？（正規分布）

迷路のどの位置に人がいるか（距離の分布）を調べると、**「ベル型の曲線（正規分布）」**に似ていることがわかりました。

• 例え話： 迷路の中心から離れるにつれて、人が集まる場所が「山の頂上」のように分布し、両端では人がいなくなる。これは、確率論の有名な法則（中心極限定理）が、この迷路の世界でも成り立っていることを示しています。

4. 未来への挑戦：AI と数学の共演

この論文の面白い点は、**「AI が数学の研究者を助ける」**という新しいスタイルを示していることです。

• LLM（大規模言語モデル）のテスト：
  研究チームは、この迷路問題を「ソート（並び替え）問題」として AI に解かせようと試みました。しかし、現在の AI は「教科書にあるような簡単な並び替え」はできますが、「教科書に載っていない新しいルール」で並び替えるアルゴリズムをゼロから発明するのは、まだ苦手なようです。
• Kaggle（ Kaggle 大会）への挑戦：
  彼らは、この迷路問題を「Kaggle（データサイエンスの競技大会）」の課題として公開しました。世界中の AI 開発者に「この迷路を最短で解くプログラムを作って！」と挑戦を投げかけています。

まとめ：なぜこれが重要なのか？

この研究は、単にパズルの解き方を増やしたわけではありません。

1. AI の可能性： 人工知能が、人間には計算しきれない「巨大な数学の迷路」を探索し、新しい法則を見つけ出すことができることを実証しました。
2. 効率化： 従来の方法では何年もかかった計算が、数秒で終わるようになりました。これにより、DNA の進化距離の計算や、通信ネットワークの設計など、実社会の問題解決が加速するでしょう。
3. 美しさ： 一見複雑で無秩序に見える数学の世界に、「正方形とひげ」や「きれいな数式」といった、驚くほどシンプルで美しい秩序が潜んでいることを教えてくれました。

つまり、「AI という新しい望遠鏡」を使って、数学という宇宙の奥深くにある「星の並び（法則）」を初めて見つけたというのが、この論文の物語です。

技術概要

CayleyPy: 成長計算の効率化と Cayley グラフに関する数百の新しい予想

技術的サマリー（日本語）

1. 概要

本論文は、群論における Cayley グラフ（および Schreier グラフ）の解析に人工知能（AI）と深層学習を応用する「CayleyPy プロジェクト」の第 3 報です。著者らは、CayleyPy というオープンソースの Python ライブラリを公開し、従来の計算代数システム（GAP, Sage など）に比べて桁違いに高速かつ大規模なグラフの成長（growth）計算と直径（diameter）推定を可能にしました。これを用いて、対称群 $S_n$ や零次群などに関する約 200 の新しい数学的予想を導出しました。

2. 背景と問題定義

Cayley グラフは、群の生成元を辺、群の要素を頂点とするグラフであり、群論、組み合わせ論、バイオインフォマティクス（ゲノム再編成）、量子計算など広範な分野で重要です。
主要な研究課題として以下のものが挙げられます：

• 直径（Diameter）: グラフ上の任意の 2 点間の最大距離（「神の数」）。一般的には NP 困難問題であり、大規模な群では計算が極めて困難です。
• 成長（Growth）: 特定の頂点からの距離 $k$ にある頂点の数のベクトル。
• 経路探索（Path-finding）: 群の要素を生成元の積に分解する最短経路の発見。

従来の手法（Schreier-Sims 法など）は、群のサイズが大きくなる（例：$10^{40}$ 以上）と計算コストが指数関数的に増大し、実用的ではありませんでした。

3. 手法とツール：CayleyPy

CayleyPy は、AI 技術と GPU 加速を活用した Python ライブラリです。

• 高性能な成長計算: 幅優先探索（BFS）の効率的な実装（ビットマスク法など）を採用し、GPU を利用することで、GAP や Sage に対する最大 1000 倍の高速化を実現しました。これにより、$S_{15}$（約 $1.3 \times 10^{12}$ 要素）のような巨大な群でも成長計算が可能になりました。
• AI 経路探索: 深層学習（拡散モデルやビームサーチなど）を用いて、最適または準最適の経路分解を行います。GAP が解を見つけられないサイズ（$S_{100}$ 以上）でも、AI 手法は有効な解を生成できます。
• 可視化とベンチマーク: 生成元のパターンを視覚化し、Kaggle 上で 10 以上のベンチマーク課題（CayleyBench）を提供することで、コミュニティ全体での手法比較を促進しています。

4. 主要な貢献と結果

4.1. 直径の準多項式性予想（Diameter Quasi-polynomiality）

多くの Cayley グラフ（特に $S_n$）において、直径が $n$ に関する**準多項式（quasi-polynomial）**で記述されるという強力な予想を提示しました。

• 内容: 直径 $D(n)$ は、$n \pmod s$ の値に応じて異なる多項式（主に二次または一次）で表される。
• 意義: 直径計算は一般的に NP 困難ですが、この性質が真であれば、小さな $n$ での計算結果から多項式フィッティングを行うことで、効率的に大規模な $n$ での直径を推定できます。

4.2. $S_n$ の直径に関する Babai 予想の精緻化

L. Babai の予想（単純群の直径は $\log^c |G|$ で抑えられる）の対称群 $S_n$ 版について、より具体的な上限を提案しました。

• 新予想: 標準的な無向 Cayley グラフにおいて、直径は $\frac{1}{2}n^2 + 4n$ で抑えられる。
• 背景: 従来の予想は $O(n^2)$ 程度でしたが、著者らは $n \le 15$ までの exhaustive search（全探索）および AI 探索により、最大直径を与える生成元の族（「正方形とひげ」パターンと呼ばれる対合の集合）を発見し、その挙動から上記の係数 $1/2$ を導き出しました。

4.3. 具体的な生成元と直径の公式

• Glushkov 問題（1968 年）: 左巡回シフトと最初の 2 要素の転置で生成される有向 Cayley グラフの直径について、以下の公式を予想しました。
  • $n$ が奇数: $(3n^2 - 8n + 9)/4$
  • $n$ が偶数: $(3n^2 - 8n + 12)/4$
• 最大直径を与える生成元: $n \le 15$ において、対合（involution）からなる「正方形とひげ（square-with-whiskers）」という幾何学的パターンを持つ生成元が最大直径を与えることが確認されました。これらは「Sheveleva2」や「Koltsov3involutions」として新しい生成元族として提案されました。

4.4. 零次群（Nilpotent Groups）と成長分布

• 単位三角行列群: 有限体上の単位三角行列群の直径について、Ellenberg の結果を改善し、法 $p$ に対して線形に依存する現象を指摘しました。
• 成長分布: 零次群における距離の分布が、P. Diaconis が対称群で示したようなガウス分布（中心極限定理）に従うことを予想しました。

4.5. LLM 研究用ベンチマーク（CayleyBench）

Cayley グラフ上の経路探索問題は、ソート問題として定式化できるため、大規模言語モデル（LLM）の推論能力を評価する理想的なテストベッドとなります。

• LLM-Friendly 予想: 生成元が与えられた場合のソートアルゴリズム（コード）を LLM に生成させるタスクを定義しました。
• 現状: 既存の LLM は既知のソートアルゴリズム（バブルソート等）は生成できますが、新しい生成元に対するアルゴリズムの発見には失敗しており、研究課題としての可能性を示唆しています。

5. 生物学的応用

ゲノム再編成（逆転や転位）を Cayley グラフの経路探索としてモデル化し、Schreier グラフ（二値ベクトル上の作用）における成長と直径を解析しました。逆転と転位（transposons）の両者において、二値 coset 上の成長が一致し、ガウス分布に従うという新たな知見を得ました。

6. 意義と結論

本論文は、以下の点で画期的です：

1. 計算能力の飛躍的向上: AI と GPU を活用することで、従来不可能だった大規模 Cayley グラフの解析を可能にし、数学的発見のスピードを劇的に加速しました。
2. 新しい数学的洞察: 直径の準多項式性や、最大直径を与える生成元の幾何学的パターンなど、純粋数学における未解決問題への新たな視点を提供しました。
3. AI と数学の融合: 計算実験→パターン発見→予想→証明（または検証）というパイプラインが、純粋数学の進展に有効であることを実証しました。
4. オープンサイエンス: CayleyPy ライブラリ、Kaggle ベンチマーク、250 以上のノートブックを公開し、コミュニティ全体での研究を促進しています。

CayleyPy は、群論における「God's number」の決定や、AI による数学的推論の限界を探るための強力なプラットフォームとして確立されつつあります。