On the satisfaction frequency of spectral characterization conditions

1. 問題設定 (Problem)

• 背景: 1950 年代以来、非同型なグラフが同じ特性多項式（スペクトル）を持つ「共スペクトルグラフ（cospectral mates）」が存在することは知られています。
• Haemers の予想: Haemers は、「$n$ 頂点のグラフを一様にランダムに選んだとき、$n \to \infty$ で共スペクトルである確率は 0 に収束する（つまり、ほとんどのグラフはスペクトルで一意に同定される）」という予想を立てています。しかし、この予想は未解決です。
• 既存の限界: 現在、スペクトル同定を保証する「十分条件」は複数知られています（Wang や Xu などの研究）。しかし、これらがランダムグラフに対してどの程度の頻度で満たされるかについての理論的な理解は限られており、数値シミュレーションによる概算しかありませんでした。特に、極限値が何になるかという具体的な予測は存在しませんでした。
• 目的: 本研究は、スペクトル同定条件が満たされる頻度の極限値を理論的に導き出し、具体的な数値予測（予想）を提示することを目的としています。

2. 手法 (Methodology)

本研究は、**「抽象代数的ランダム行列統計（abstract-algebraic random matrix statistics）」**に基づく新しい 2 段階のアプローチを採用しています。

1. 代数的対象への再定式化:

   • グラフの隣接行列 $M$ と関連するベクトル $\zeta$ に対して、スペクトル同定の十分条件を、$\mathbb{Z}[x]$-加群の構造として再定式化します。
   • 具体的には、ウォーク行列（walk matrix）の行列式の無平方性（square-freeness）や、特性多項式の判別式（discriminant）の条件を、隣接行列 $M$ によって誘導される $\mathbb{Z}[x]$-加群 $\text{coker}(M - xI)$ の構造（特にその商加群や局所化された構造）の条件に変換します。
   • これにより、行列の具体的な数値計算から、代数的な構造の分布問題へと問題を転換します。

2. プロ有限ランダム行列アンサンブルの導入:

   • 上記の加群の分布を解析的に扱いやすいモデルで研究します。
   • 離散集合 $\{0, 1\}$ ではなく、$\mathbb{Z}[x]$ のプロ有限完備（profinite completion）$\widehat{\mathbb{Z}[x]}$ 上のハール測度（Haar measure）に従って行列要素が分布するランダム行列モデル（SymHaar）を導入します。
   • このモデルは、グラフの無向性（対称行列）という制約を保持しつつ、解析的な取り扱いを可能にします。
   • 対称性の利用: このモデルは、ハール測度の不変性（$G M G^\top$ の分布が $M$ と同じ）という強力な性質を持っています。これを利用して、$n \times n$ 行列に関する加群の事象を、有限次元の行列に関する事象に還元する定理（Proposition 4.5）を証明し、確率計算を有限の計算に帰着させます。

3. 主要な貢献と結果 (Key Contributions & Results)

本研究は、2 つの異なる十分条件に対して、極限での充足頻度に関する具体的な予想（Conjecture）を導出しました。

A. ウォーク行列に関する条件 (Conjecture 1.4)

• 条件: Wang らの研究に基づく、ウォーク行列 $W$ の行列式 $\det(W)$ が「無平方（square-free）」であるという条件。
• 結果: $n \to \infty$ における $\det(W)$ が無平方である確率は、素数 $p$ ごとに独立に振る舞い、その極限値は以下の式で与えられます。
  $$\lim_{n\to\infty} \mathbb{P}(\det(W) \text{ is square-free}) = \prod_{p} \left( 1 - \frac{1}{p^2} - \frac{1}{p^3} + \frac{1}{p^4} \right) \prod_{k=1}^{\infty} \left( 1 - \frac{1}{p^{2k}} \right) \approx 0.2943$$
• 検証: 数値シミュレーション（$n$ まで 100）との比較において、この理論値は非常に高い精度で一致することが確認されました。従来の単純な整数の無平方性の確率（$1 - 1/p^2$）とは異なり、対称行列特有の補正項（$1/p^3, 1/p^4$ など）が含まれている点が重要です。

B. 判別式に関する条件 (Conjecture 1.7)

• 条件: Wang と Yu の研究に基づく、特性多項式の判別式 $\Delta_M$ が「奇数かつ無平方」であるという条件。
• 結果: 同様に、$\Delta_M$ が奇数かつ無平方である確率の極限値を導出しました。
  $$\lim_{n\to\infty} \mathbb{P}(\Delta_M \text{ is odd and square-free}) = \frac{6}{7} \prod_{p} \left( 1 - \frac{1}{p^2} \frac{3p-1}{p+1} \right) \prod_{k=1}^{\infty} \left( 1 - \frac{1}{p^{2k}} \right) \approx 0.1686$$
• 特徴: 素数 2 に関する振る舞い（奇数であること）と、他の奇素数に関する振る舞いが異なる構造を持ち、これも数値シミュレーションとよく一致します。

C. 普遍性 (Universality)

• 導出された確率分布は、行列要素の具体的な分布（$\{0, 1\}$ かどうか）に依存せず、対称性という構造さえ保たれていれば普遍的（universal）であると考えられています。これは、砂山群（sandpile groups）などの他のランダムグラフモデルにおける普遍性の結果と類似しています。

4. 意義 (Significance)

1. 理論的予測の初提供: これまで数値的な推測に留まっていたスペクトル同定条件の充足頻度について、初めて具体的な理論的予測値を提供しました。
2. 手法の革新: スペクトルグラフ理論の問題を、抽象代数学（$\mathbb{Z}[x]$-加群）と確率論（プロ有限ハール測度）の枠組みで統一的に扱う新しい手法を開拓しました。この手法は、他の十分条件や、より複雑なグラフクラスへの応用が期待されます。
3. Haemers 予想への示唆: 導出された確率（約 29% や 17%）は 0 ではありませんが、1 よりも十分に小さい値です。これは「スペクトル同定条件が満たされるグラフは存在するが、すべてのグラフのなかでは希少である可能性」を示唆しており、Haemers 予想（共スペクトルグラフが非典型的である）の理解を深める重要な一歩となります。
4. 対称性の重要性: 対称行列（無向グラフ）と非対称行列（有向グラフ）では、加群の分布が本質的に異なることを示し、対称性制約を正しくモデル化することの重要性を強調しました。

結論

この論文は、スペクトルグラフ理論における長年の未解決問題に対し、代数的統計力学の手法を応用することで、定量的かつ理論的な答えを提示した画期的な研究です。導出された予想は、今後の数値実験や、普遍性の証明に向けた理論的基盤として重要な役割を果たすでしょう。