2025-11-10T03:09:09.120069

Geometry of Random Cayley Graphs of Abelian Groups

Hermon, Olesker-Taylor

Consider the random Cayley graph of a finite Abelian group $G$ with respect to $k$ generators chosen uniformly at random, with $1 \ll \log k \ll \log |G|$. Draw a vertex $U \sim \operatorname{Unif}(G)$. We show that the graph distance $\operatorname{dist}(\mathsf{id},U)$ from the identity to $U$ concentrates at a particular value $M$, which is the minimal radius of a ball in $\mathbb Z^k$ of cardinality at least $|G|$, under mild conditions. In other words, the distance from the identity for all but $o(|G|)$ of the elements of $G$ lies in the interval $[M - o(M), M + o(M)]$. In the regime $k \gtrsim \log |G|$, we show that the diameter of the graph is also asymptotically $M$. In the spirit of a conjecture of Aldous and Diaconis (1985), this $M$ depends only on $k$ and $|G|$, not on the algebraic structure of $G$. Write $d(G)$ for the minimal size of a generating subset of $G$. We prove that the order of the spectral gap is $|G|^{-2/k}$ when $k - d(G) \asymp k$ and $|G|$ lies in a density-$1$ subset of $\mathbb N$ or when $k - 2 d(G) \asymp k$. This extends, for Abelian groups, a celebrated result of Alon and Roichman (1994). The aforementioned results all hold with high probability over the random Cayley graph.

academic

アーベル群のランダムケーリーグラフの幾何学

基本情報

論文ID: 2102.02801
タイトル: Geometry of Random Cayley Graphs of Abelian Groups
著者: Jonathan Hermon (ブリティッシュコロンビア大学)、Sam Olesker-Taylor (バース大学)
分類: math.PR (確率論)、math.CO (組合論)
発表時期: 2021年2月 (arXiv v2: 2025年10月)
論文リンク: https://arxiv.org/abs/2102.02801

要旨

本論文は、有限アーベル群 $G$ のランダムケーリーグラフの幾何学的性質を研究する。ここで $k$ 個の生成元は均一にランダムに選択され、 $1 \ll \log k \ll \log |G|$ を満たす。著者らは、単位元から無作為頂点 $U \sim \operatorname{Unif}(G)$ までのグラフ距離 $\operatorname{dist}(\mathsf{id},U)$ が特定の値 $M$ の周辺に集中することを証明した。この値 $M$ は、 $\mathbb{Z}^k$ 内で基数が少なくとも $|G|$ である球の最小半径である。 $k \gtrsim \log |G|$ の場合、グラフの直径も漸近的に $M$ に等しい。Aldous-Diaconis予想の精神に合致して、 $M$ は $k$ と $|G|$ にのみ依存し、 $G$ の代数構造には依存しない。さらに著者らは、 $k - d(G) \asymp k$ のときスペクトルギャップの位数が $|G|^{-2/k}$ であることを証明し、Alon-Roichmanの古典的結果を拡張した。

研究背景と動機

問題背景

ランダムケーリーグラフモデル: Aldousとdiaconis は1985年にランダムケーリーグラフモデルを導入した。群 $G$ から独立に均一に $k$ 個の生成元を選択することでケーリーグラフを構成する。このモデルは、群上の「典型的な」ランダムウォークの振る舞いを研究することを目的としている。
幾何学的性質の研究: 従来の研究は固定 $k$ の場合に主に焦点を当てていたが、本論文は $k$ が $|G|$ とともに増大する場合を考察する。これにより、特に $d(G)$ が $|G|$ とともに増大する群を含む、より広範な群クラスの研究が可能になる。
普遍性の問題: Aldous-Diaconis予想は、ある統計量が「群の代数構造に独立」であること、すなわち $k$ と $|G|$ にのみ依存することを予測している。

研究動機

典型距離の集中性: ランダムケーリーグラフにおける単位元から無作為頂点までの距離分布の理解
直径推定: グラフ直径の漸近的振る舞いの決定
スペクトル性質: ランダムウォークのスペクトルギャップの分析（混合時間と密接に関連）
普遍性の検証: これらの幾何学的量が本当に $k$ と $|G|$ にのみ依存するかどうかの検証

核心的貢献

典型距離集中定理: 3つの異なる $k$ の範囲（ $1 \ll k \ll \log |G|$ 、 $k \asymp \log |G|$ 、 $k \gg \log |G|$ ）において、典型距離が明確な値の周辺に集中することを証明した。
直径の集中性: $k \gtrsim \log |G|$ に対して、直径が典型距離と漸近的に等しいことを証明した。
スペクトルギャップの精密推定: Alon-Roichman定理をアーベル群の場合に拡張し、スペクトルギャップの精密な位数 $|G|^{-2/k}$ を与えた。
冪零群への拡張: 部分的な結果を冪零群に拡張し、アーベル化の支配的役割を証明した。
普遍性結果: $k - \log^2 |G| \asymp k$ の場合、 $\mathbb{Z}_2^d$ が最大直径を与えることを証明した。

方法論の詳細

問題設定

ランダムケーリーグラフ $G_k$ の幾何学的性質を研究する。ここで：

$G$ は有限アーベル群
$Z_1, \ldots, Z_k \sim \text{Unif}(G)$ は独立同分布
典型距離は $D_{G_k}(\beta) := \min\{R \geq 0 : |B_{G_k}(R)| \geq \beta|G|\}$ と定義される

核心的技術方法

1. 逆向き方法論 (§2.2)

従来の方法とは異なり、本論文は混合技術を使用して幾何学的結果を証明する：

補助ランダム変数の混合性質の分析
$L^2$ 距離推定を使用した典型距離の上界の証明

2. 格球推定 (§2.3, §3.3, §4.3)

異なる $k$ の範囲に対して、 $\mathbb{Z}^k$ 内の $L^1$ 球のサイズを精密に推定：

$1 \ll k \ll \log |G|$ : 幾何分布を球面分布の代理として使用
$k \asymp \log |G|$ : 球面上の均一分布を直接使用
$k \gg \log |G|$ : 二項係数の漸近性を利用

3. 最大公約数分析

ベクトル差 $V = W - W'$ の最大公約数の分析が重要な技術： $g = \gcd(V_1, \ldots, V_k, n)$ $\mathbb{E}(g^{d(G)} \mathbf{1}(V \neq 0))$ を制御することで混合性を証明する。

4. 典型性条件

「良い」サンプルを処理するために典型性集合 $\mathcal{W}$ を導入： $\mathcal{W} = \{w \in \mathbb{Z}^k : L_0 + 1 \leq \|w\|_1/k \leq L, \max_i w_i \leq 3L \log k\}$

技術的革新点

統一的枠組み: 3つの異なる $k$ の範囲に対して統一的な分析枠組みを提供
混合方法: ランダムウォーク混合理論を創新的に使用して幾何学的性質を証明
精密な定数: 漸近的位数だけでなく明確な集中値を提供
条件の緩和: 密度-1部分集合の技巧を通じて群構造に対する制限を緩和

主要定理

定理A (典型距離)

$G$ をアーベル群とすると、以下の収束が成立する（確率収束）：

ケース1: $1 \ll k \ll \log |G|$ 、 $k - d(G) \asymp k$ $D_{G_k^\pm}(\beta) / D^\pm \to_P 1$ ここで $D^+ = |G|^{1/k}/(2e)$ 、 $D^- = |G|^{1/k}/e$
ケース2: $k \asymp \lambda \log |G|$ $D_{G_k^\pm}(\beta) / (\alpha_\lambda^\pm k) \to_P 1$
ケース3: $k \gg \log |G|$ $D_{G_k^\pm}(\beta) / \left(\frac{\rho}{\rho-1} \log_k |G|\right) \to_P 1$

定理E (スペクトルギャップ)

すべてのアーベル群 $G$ と生成元多重集合 $z$ に対して、定数 $c > 0$ が存在して： $t_{\text{rel}}(G^-(z)) \geq c|G|^{2/k}$

$k \geq (2+\delta)d(G)$ のとき、高確率で： $t_{\text{rel}}^*(G_k^-) \leq C_\delta |G|^{2/k}$

実験的検証

本論文は純粋な理論的研究であり、主に数学的証明を通じて結果を検証する。主要な検証は以下を含む：

1. 下界の普遍性

典型距離とスペクトルギャップの下界がすべてのアーベル群とすべての生成元選択に対して成立することを証明。

2. 上界の確率性

上界が高確率で成立し、失敗確率が $O(2^{-k})$ であることを証明。

3. 条件の必要性

条件 $1 \ll \log k \ll \log |G|$ は集中性に必要
条件 $k - d(G) \asymp k$ は多くの場合に必要

結論と議論

主要な結論

適切な条件下で、ランダムケーリーグラフの典型距離と直径は $k$ と $|G|$ にのみ依存する値に集中する
スペクトルギャップの位数は $|G|^{-2/k}$ であり、Alon-Roichman定理を拡張する
アーベル化は冪零群の幾何学において支配的な役割を果たす

制限事項

条件の制限: $k - d(G) \asymp k$ などの技術的条件が必要
アーベル性の制限: 主要な結果はアーベル群にのみ適用可能
密度条件: ある結果は $|G|$ が密度-1部分集合に属することを必要とする

今後の方向性

著者らは§8で複数の未解決問題を提示している：

群構造に対する条件制限の緩和
等周定数の精密推定
より一般的な非アーベル群への拡張

深い評価

利点

理論的深さ: 確率論、組合論、群論を結びつける深い数学的洞察を提供
技術的革新: 混合理論を逆向きに使用して幾何学的性質を証明する方法は創意的
結果の精密性: 漸近的位数だけでなく明確な定数を提供
枠組みの統一性: 異なるパラメータ範囲に対する統一的分析枠組み

技術的貢献

方法論: ランダムケーリーグラフの幾何学を分析する新しい技術を開発
最大公約数分析: gcd分析を創新的に使用して混合性を制御
格球理論: 高次元格球の組合論を深く発展させた

影響力

理論的意義: Aldous-Diaconis予想に対する強力な支持を提供
応用の可能性: 暗号学、ネットワーク理論などの分野への応用可能性
方法的啓発: 技術方法は他のランダムグラフモデルに一般化可能

適用場面

理論研究: ランダムウォーク理論、展開グラフ構成
応用数学: ネットワーク分析、符号理論
計算機科学: アルゴリズム分析、複雑性理論

参考文献

本論文は36篇の重要な文献を引用しており、ランダムケーリーグラフ、スペクトルグラフ理論、確率論など複数の分野の古典的および最先端の研究をカバーしている。特にAldous-Diaconis、Alon-Roichmanなどの基礎的研究との関連性は注目に値する。

要約: これはランダムケーリーグラフの幾何学理論において重要な貢献を持つ論文である。著者らは創新的な技術方法を通じて、3つの異なるパラメータ範囲において典型距離、直径、スペクトルギャップの精密な結果を確立し、Aldous-Diaconis予想に対する強力な理論的支持を提供した。論文の技術的深さと理論的意義は顕著であり、この分野における重要な進展である。