Cayleyグラフ - 群の幾何学的な見方

群は代数的な対象ですが、適切なグラフを対応させることで幾何学的に「見る」ことができます。Cayley グラフは群の元を頂点、生成元による積を辺として描いたもので、群の構造を視覚的に捉える基本的な道具です。幾何学的群論と呼ばれる分野はこの視点を出発点としています。

Cayley グラフの定義

群 $G$ と生成集合 $S$（$e\notin S$ かつ $S=S^{-1}$、すなわち $s\in S$ ならば $s^{-1}\in S$）に対して、Cayley グラフ $\mathrm{Cay}(G,S)$ は次のように定義される有向グラフです。

生成集合の選び方によって Cayley グラフの見た目は変わりますが、群の本質的な性質の多くは生成集合の選び方によりません（後述する擬等長の概念がこれを正当化します）。

具体例：巡回群

巡回群 $C_n=⟨r\mid r^n=e⟩$ の Cayley グラフを $S=\{r,r^{-1}\}$ で構成すると、$n$ 個の頂点が環状に並んだグラフ、すなわち $n$ 角形（サイクルグラフ $C_n$）になります。$e\to r\to r^2\to \cdots \to r^{n-1}\to e$ と一周して戻ってくる構造です。

無限巡回群 $\mathbb{Z}=⟨1⟩$ の場合は $S=\{1,-1\}$ として、整数が一列に並んだ無限の直線グラフになります。$\cdots \to -2\to -1\to 0\to 1\to 2\to \cdots$ という構造で、各頂点の次数は 2 です。

具体例：${\mathbb{Z}}^2$

${\mathbb{Z}}^2$ を $S=\{(\pm 1,0),(0,\pm 1)\}$ で生成すると、Cayley グラフは平面上の格子グラフになります。各頂点 $(a,b)$ から上下左右の 4 方向に辺が伸びる構造で、各頂点の次数は 4 です。この格子は日常的にも馴染みのある形ですが、群論的には ${\mathbb{Z}}^2$ の代数的構造が平面の離散的な対称性として現れたものと見ることができます。

具体例：対称群 $S_3$

$S_3$ を生成集合 $S=\{(12),(123),(132)\}$ で生成した場合の Cayley グラフを考えます。$S_3$ は位数 6 なので頂点は 6 個です。$(12)$ は自身が逆元なので $S$ に含め、$(123)$ と $(132)$ は互いに逆元なのでともに $S$ に入ります。

各頂点から 3 本の辺が出るので次数 3 の正則グラフになります。このグラフを描くと、正三角形を 2 つ重ねたような構造が現れ、$S_3$ が $C_3$ と $C_2$ の半直積であるという代数的事実が幾何的に見えてきます。

具体例：自由群

2 元生成自由群 $F_2=⟨a,b⟩$ の Cayley グラフは $S=\{a,a^{-1},b,b^{-1}\}$ で生成され、各頂点の次数が 4 の無限正則木（4 正則木）になります。自由群には非自明な関係式がないので、どの方向に進んでも「行き止まり」や「ループ」が生じません。

自由群の Cayley グラフが木になるという事実は、逆方向にも使えます。群がある木に「うまく」作用するならば、その群の構造について強い制約が得られるという Bass-Serre 理論の出発点がここにあります。

語距離

Cayley グラフに自然な距離を導入できます。$g,h\in G$ に対して、$\mathrm{Cay}(G,S)$ における $g$ から $h$ への最短パスの長さを $d_S(g,h)$ と書きます。これは

$$d_S(g,h)=\min \{n\mid g^{-1}h=s_1{s}_2\cdots s_n,s_i\in S\}$$

すなわち $g^{-1}h$ を $S$ の元の積として書いたときの最短の長さに等しくなります。特に $d_S(e,g)$ は $g$ の語長（word length）と呼ばれ、$g$ を生成元で表すのに最低何個必要かを表します。

語距離は左不変です。すなわち任意の $f,g,h\in G$ に対して $d_S(fg,fh)=d_S(g,h)$ が成り立ちます。これは $G$ が Cayley グラフに左からの積で作用し、この作用がグラフの同型を与えることから従います。

擬等長

幾何学的群論の中心概念である擬等長（quasi-isometry）を導入します。2 つの距離空間 $(X,d_X)$ と $(Y,d_Y)$ が擬等長であるとは、写像 $f:X\to Y$ と定数 $\lambda \ge 1$、$C\ge 0$ が存在して

$$\frac{1}{\lambda }{d}_X(x_1,x_2)-C\le d_Y(f(x_1),f(x_2))\le \lambda d_X(x_1,x_2)+C$$

がすべての $x_1,x_2\in X$ に対して成り立ち、さらに $Y$ の各点が $f$ の像から有界距離内にあるものが存在することです。

Cayley グラフの幾何にとって擬等長が重要な理由は、次の基本的な事実にあります。同じ群 $G$ の異なる有限生成集合 $S$ と $S^{\prime }$ に対して、$\mathrm{Cay}(G,S)$ と $\mathrm{Cay}(G,S^{\prime })$ は擬等長です。したがって、「群 $G$ の大域的幾何」は生成集合の選び方によらず well-defined に定まります。

さらに、Švarc-Milnor の補題は次のことを主張します。群 $G$ が測地的距離空間 $X$ に固有かつ余コンパクトに等長的に作用するならば、$G$（任意の有限生成集合に関する Cayley グラフ）と $X$ は擬等長です。この結果により、群の大域的幾何と群が作用する空間の幾何が同一視されます。

成長関数

Cayley グラフの幾何的性質の中で、最も基本的なものの一つが成長関数です。群 $G$ の生成集合 $S$ に対して

$${\beta }_S(n)=|\{g\in G\mid d_S(e,g)\le n\}|$$

すなわち単位元を中心とする半径 $n$ の球に含まれる元の個数を成長関数と呼びます。

成長の型は擬等長不変量です。多項式成長か指数的成長かは生成集合の選び方によりません。

Gromov の多項式成長定理

1981 年、Gromov は次の画期的な定理を証明しました。

有限生成群が多項式成長を持つならば、その群は冪零群を有限指数部分群として含む（仮想冪零である）。

Gromov の証明は、群を「遠くから眺める」操作（漸近錐の構成）を行い、得られた極限空間に Montgomery-Zippin の Hilbert 第 5 問題の解を適用するという、代数と幾何と解析を横断するものでした。

Grigorchuk の群

1984 年に Grigorchuk が構成した群は、幾何学的群論における最も驚くべき例の一つです。この群は 2 元で生成され、すべての元が有限位数（ねじれ群）であり、かつ無限群です。つまり一般 Burnside 問題の反例になっています。

Grigorchuk 群の成長関数は

$$e^{n^{\alpha }}⪯\beta (n)⪯e^{n^{\beta }}$$

の形で評価され、多項式成長でも指数的成長でもない中間的成長を示します。Milnor が 1968 年に「中間的成長を持つ群は存在するか」と問うた問題の最初の解決例でもあります。

Cayley グラフは群を幾何学的対象として扱う入り口であり、ここから双曲群、CAT(0) 群、自動群といった豊かな理論が展開されます。群の代数的性質と幾何的性質の相互作用は、現代の群論において最も活発に研究されている分野の一つです。