Expanding groups with large diameter

Sean Eberhard と Luca Sabatini による論文『EXPANDING GROUPS WITH LARGE DIAMETER（大直径を持つ拡大群）』の技術的な要約を以下に提示します。

1. 問題の背景と定式化

この論文は、有限群の Cayley グラフにおける**スペクトルギャップ（spectral gap）と直径（diameter）**の関係性、特にこれらが生成集合の選択にどのように依存するかを研究しています。

• 既知の事実: 無限群の場合、成長型、端の数、双曲性、アメンラビリティ、性質 (T) などの重要な性質は、有限生成集合の選び方に依存せず、群そのものの性質です。
• 有限群の文脈: Alon, Lubotzky, Wigderson [1] や Kassabov [8] などの先行研究により、ある有界な生成集合に対しては「拡大グラフ（expander graph）」となるが、別の有界な生成集合に対してはそうならない有限群の系列が存在することが示されています。
• Pyber と Szabó の問い (2013): 有限群の系列 $(G_n)$ において、ある有界な生成集合 $X_n$ に対して $Cay(G_n, X_n)$ が拡大グラフである場合、任意の有界な生成集合 $Y_n$ に対して、その直径が $|G_n|$ の多対数（polylogarithmic）、すなわち $diam(Cay(G_n, Y_n)) \le C(\log |G_n|)^C$ で抑えられるか？
  • 多くの有限単純群では、Babai の予想により直径が多対数であることが期待されています。
  • この問いは、「多対数の直径は群の性質（生成集合に依存しない）なのか？」という疑問を含んでいます。

本論文の目的:
Pyber と Szabó の問いに対して否定的に答えること。すなわち、ある生成集合では拡大グラフ（したがって直径は対数的）であるが、別の生成集合では直径が「超多対数的（super-polylogarithmic）」、具体的には $\exp(c\sqrt{\log |G|})$ 程度に巨大になるような有限群の系列を構成することです。

2. 主要な結果 (Theorem 1.2)

著者らは、定数 $\delta, \varepsilon > 0$ と、$|G_n| \to \infty$ となる有限群の系列 $(G_n)$、および有界な生成集合 $X_n, Y_n$ を構成し、以下の性質を満たすことを示しました。

1. 拡大性: $Cay(G_n, X_n)$ は $\varepsilon$-拡大グラフである（スペクトルギャップが正）。
2. 大直径: $Cay(G_n, Y_n)$ の直径は $diam(Cay(G_n, Y_n)) \ge \exp(\delta \sqrt{\log |G_n|})$ 以上である。

これは、直径が「多項式的に大きい（almost flat）」場合が群の性質であるのに対し、「多対数的か超多対数的か」は生成集合に強く依存することを示しています。

3. 構成と手法

3.1 群の構成

構成される群 $G$ は、半直積 $G = V_0 \rtimes S_n$ として定義されます。

• $V = \mathbb{F}_p^n$（$p$ は $n$ に対して指数関数的に大きい素数、$p \sim e^{cn}$）。
• $V_0 \subset V$ は、成分の和が 0 となる部分空間（削除された置換モジュール、次元 $n-1$）。
• $S_n$ は $n$ 次対称群。
• 群の位数は $|G| = p^{n-1} n! \approx \exp(cn^2)$ となります。

3.2 生成集合の選択

二つの生成集合 $X = \{v\} \cup T$ と $Y = \{v'\} \cup T'$ は、どちらも $V_0$ の要素と $S_n$ の部分集合の和集合の形をとります。

• 大直径を示す生成集合 $Y$:

  • $v' = (1, -1, 0, \dots, 0)$
  • $T' = \{(1, 2), (1, 2, \dots, n)\}$（$S_n$ の標準的な生成元）
  • この選択により、$V_0$ 内の移動に要するステップ数が $p$ に比例し、直径が $p \sim e^{cn}$ 程度になることが容易に示せます。

• 拡大グラフとなる生成集合 $X$:

  • $T$ は Kassabov の結果により、$S_n$ に対して有界な拡大生成集合として選択。
  • $v \in V_0$ は、特定の条件を満たすように選択（実際にはランダムに選べばよいことを示す）。
  • この $X$ に対して $Cay(G, X)$ が拡大グラフになることを証明するのが本論文の核心的な技術的課題です。

3.3 技術的アプローチ：Kazhdan 定数と指数和

拡大性の証明は、Kazhdan 定数 $\kappa(G, S)$ を用いて行われます。Proposition 3.4 により、半直積 $G = N \rtimes H$ における拡大性は、$N$ と $H$ のそれぞれの拡大性、および $N$ 上の作用に関する条件に帰着されます。

具体的には、$V_0$ 上の作用 $vS_n$ に関するスペクトルギャップを評価する必要があります。これは、以下の**「置換型指数和（permutational exponential sum）」**の評価問題に帰着されます。

Theorem 1.3 (主要な技術的定理):
任意の $n$ と $p \le e^{\delta n}$ に対して、ある $v \in V_0$ が存在し、すべての非定数ベクトル $w \in V$ について、
$$\left| \frac{1}{n!} \sum_{\sigma \in S_n} e_p(\langle v, w^\sigma \rangle) \right| \le 1 - \varepsilon$$
が成り立つ。
ここで $e_p(x) = \exp(2\pi i x / p)$ です。この不等式は、$v$ をランダムに選んだときに、すべての $w$ に対して指数和が 1 から十分に離れることを意味します。

3.4 証明の鍵となるアイデア

$p$ が $n$ に対して指数関数的に大きい場合、単純なユニオンバウンド（すべての $w$ に対して確率評価を足し合わせる）は失敗します（$w$ の数が多すぎるため）。

著者らは以下の二段階のアプローチを採用しました：

1. ランダムな $v$ に対する確率評価 (Lemma 4.1):
   $w$ が特定の形（例えば $(u, 0, \dots, 0)$）を持つ場合、Hoeffding の不等式を用いて、$v$ がランダムであれば指数和が小さくなる確率が高いことを示します。
2. 決定論的なスイッチング論法 (Lemma 4.2):
   任意の $w$ について、$w$ とその転置 $\tau$ を用いた Cauchy-Schwarz 不等式による「スイッチング」を行うことで、任意の $w$ に対する指数和の二乗を、特定の単純な形（$w=(u, 0, \dots, 0)$ のような形）の指数和の二乗で上から抑えることを示します。
   $$|\lambda_{v,w}|^2 \le \frac{1}{2} + \frac{1}{2} \max_{0 \neq u \in \mathbb{F}_p} |\lambda_{v}(u)|^2$$
   これにより、すべての $w$ に対する評価を、$p$ 個の単純なケース（$u$ に関するもの）に帰着させることに成功し、ユニオンバウンドが適用可能になります。

4. 意義と結論

• Pyber-Szabó 問いへの回答: 有限群の系列において、ある生成集合で拡大グラフであっても、別の生成集合では直径が超多対数的に巨大になり得ることを示し、Pyber と Szabó の問いに明確に「NO」と答えました。
• 群の性質の限界: 「多対数直径」は群の固有の性質ではなく、生成集合に依存する性質であることを実証しました。
• 手法の新規性: 指数関数的に大きい素数 $p$ を扱えるようにした点（$p$ が $n$ の多項式ではなく指数関数である場合）が画期的です。これは、すべてのベクトルに対するユニオンバウンドを避け、Cauchy-Schwarz 不等式を用いた決定論的なスイッチング論法によって、支持次元 1 のベクトルへの帰着を可能にしたことにあります。
• 今後の課題: 直径の最適な上界（$|G_n|^{o(1)}$ の中でどこまで小さくできるか）は未解決の問題として残されています。

この論文は、群論、組合せ論、解析学の手法を融合させ、Cayley グラフの幾何学的性質が生成集合にどの程度敏感であるかを深く理解するための重要な一歩となっています。