バーンサイドの補題について

はじめに

ABC198-F でバーンサイドの補題を知ったので、自分なりにまとめた記事です。

一応、群論の知識を仮定せずに読めるようにしてあるはずです。

はじめに
用いる記法など
群について
- 代表的な群
同値関係
- 同値関係の例
剰余類
- 剰余類による同値関係
  - 剰余類による同値関係の例
- 剰余集合
群の作用
群の軌道 / 安定化群と不動点集合
- 群作用による同値関係
バーンサイドの補題
参考文献

用いる記法など

$\mathbb{Z}$ : 整数全体の集合のこと。
$\mathbb{R}$ : 実数全体の集合のこと。
$|X|$ : 集合 $X$ の要素数のこと。
$A \cap B$ : 集合 $A$ と集合 $B$ の共通部分のこと。
$x \in X$ : $x$ が集合 $X$ の要素であるということ。
$G \times X$ : 基本的に $G$ と $X$ の積、 $G,X$ が集合である場合には集合 $\{(g,x) | g \in G,x \in X\}$ のこと。
$\emptyset$ : 空集合のこと。

群について

ある集合 $G$ があって、その集合の中の要素だけで行う二項演算 $\star$ を考えます。 (つまり、任意の $a, b\in G$ に対して $a \star b \in G$ を満たしています。)

この時、 $G$ が以下のすべての条件

任意の $a,b,c \in G$ に対し $(a \star b) \star c = a \star (b \star c)$ が成り立つ。 (結合法則)
ある $e \in G$ が存在して、すべての $a \in G$ に対して $e \star a = a \star e = a$ となる。(単位元の存在)
任意の $a \in G$ に対し、 $a \star a^{-1} = a^{-1} \star a = e$ となるような $a^{-1} \in G$ が存在する。 (逆元の存在)

を満たすとき、 $G$ を群と呼び、 $G$ は演算 $\star$ に関して群をなすと言います。

競プロer が知っていそうな代数的構造ナンバーワンのモノイド (セグ木に乗るやつです) に逆元の存在を付け加えた形になります。

代表的な群

★ 実数全体の集合 (加法について)

$\mathbb{R}$ は加法について群をなします。群の定義を満たすか確認してみると、

結合法則: 任意の実数 $a,b,c$ に対し $(a+b)+c = a+(b+c)$ より、結合法則が成り立っていると分かります。
単位元の存在: 任意の実数 $a$ に対し、 $e + a = a + e = a$ ですからこれを解いて $e = 0$ を得て、単位元が存在していることがわかります。
逆元の存在: 任意の実数 $a$ に対し、 $a + (-a) = (-a) + a = e$ で、単位元 $e$ が $0$ であることからこれを解いて $a^{-1} = -a$ を得て、逆元が存在していることがわかります。

以上より、 $\mathbb{R}$ は加法に対して群をなすことが分かりました。この群のことを $\mathbb{R}^{+}$ と書くこともあります。

加法に関して、実数全体の集合は上の三つ以外に大切な性質として交換法則 $a+b = b+a$ が成り立っています。

このように交換法則が成り立っている群のことを、アーベル群や可換群と呼びます。

★ 実数全体の集合から $0$ を除いたもの (乗法について)

$\mathbb{R}$ は加法について群をなしますが、乗法についてだとそうはいきません。 $0$ を含めた場合に定義を満たすか確認してみましょう。

結合法則: 任意の実数 $a,b,c$ に対し $(a \times b) \times c = a \times (b \times c)$ より、結合法則が成り立っていると分かります。
単位元の存在: 任意の実数 $a$ に対し $a \times e = e \times a = a$ であるから、これを解いて $e = 1$ を得て、単位元が存在していることがわかります。
逆元の存在: 任意の実数 $a$ に対し、 $aa^{-1} = a^{-1}a = 1$ となるような $a^{-1}$ を考えると、一見 $a^{-1} = \frac{1}{a}$ とすればよさそうに見えますが $a=0$ において $\frac{1}{a}$ は定義できません。

以上のことから、 $\mathbb{R}$ は乗法について群をなしませんが、 $\mathbb{R}$ から $0$ を除いた集合は乗法について群をなすことが分かりました。この群のことを $\mathbb{R}^{\times}$ と書くこともあります。

★ $n$ 次の置換の全体集合 (関数の合成について)

全単射 *1 であるような関数 $\sigma: \{1,2,3, \cdots, n\} \to \{1,2,3, \cdots, n\}$ *2　を考えます。

$1,2,3,\cdots,n$ を順に代入していくとそれぞれ $\sigma(1),\sigma(2),\sigma(3),\cdots,\sigma(n)$ となりますが、 $\sigma$ が全単射であったことを思い出すと、これは $1,2,3,\cdots, n$ をそれぞれ異なる数字(元の数字と行き先の数字は同じでもよい)に置換しています。

このことから、上の条件を満たすような写像 $\sigma$ のことを $n$ 次の置換と呼びます。

また、このような置換を

$\displaystyle \begin{pmatrix} 1 & 2 & 3 & \cdots & n \\ \sigma(1) & \sigma(2) & \sigma(3) & \cdots & \sigma(n) \\ \end{pmatrix} \\$

と書くこともあります。

例えば、 $3$ 次の置換 $\sigma$ を $\sigma(1) = 2, \sigma(2) = 1, \sigma(3) = 3$ とすると、この置換は

$\displaystyle \begin{pmatrix} 1 & 2 & 3\\ 2 & 1 & 3\\ \end{pmatrix} \\$

と書くことができます。

ここで、 $n$ 次の置換全体の集合を関数の合成に対して考えます。置換に対する関数の合成は例えば、

$\sigma _1 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}, \sigma _2 = \begin{pmatrix} 1 & 2 & 3\\ 3 & 2 & 1\\ \end{pmatrix}$

と定めたとき、

$\sigma_1 \circ \sigma_2 = \begin{pmatrix} 1 & 2 & 3\\ \sigma_2(\sigma_1(1)) & \sigma_2(\sigma_1(2)) & \sigma_2(\sigma_1(3)) \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3\\ 2 & 3 & 1 \end{pmatrix} \\$

$\sigma_2 \circ \sigma_1 = \begin{pmatrix} 1 & 2 & 3\\ \sigma_1(\sigma_2(1)) & \sigma_1(\sigma_2(2)) & \sigma_1(\sigma_2(3)) \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3\\ 3 & 1 & 2 \end{pmatrix} \\$

のように計算できます。上の二つの例と異なり、交換法則が成り立たない点に注意しましょう。

ここで、

結合法則: $n$ 次の置換 $\sigma_1, \sigma_2, \sigma_3$ に対して、 $(\sigma_1 \circ \sigma_2)(\sigma_3) = \sigma_1(\sigma_2(\sigma_3)) = \sigma_1 \circ (\sigma_2 \circ \sigma_3)$ であることより、結合法則が成り立つと分かります。
単位元の存在: $n$ 次の置換 $e: \{1,2,3, \cdots, n \} \to \{1,2,3,\cdots, n\}$ を、 $e(1) = 1, e(2) = 2, \cdots, e(n) = n$ とすれば、任意の $n$ 次の置換 $\sigma$ に対し、 $e \circ \sigma = \sigma \circ e = \sigma$ が成り立つため、単位元が存在しているとがわかります。
逆元の存在: 任意の $n$ 次の置換 $\sigma$ について、 $\sigma ^{-1}$ を $1 \leq i \leq n$ を満たすすべての $i$ に対し、 $\sigma^{-1}(\sigma(i)) = i$ となるように定めると、 $\sigma$ が全単射であることから $\sigma^{-1}$ も全単射であり、 $n$ 次の置換です。これより、逆元が存在していると分かります。

より、 $n$ 次の置換全体の集合は関数の合成について群をなすことが分かりました。

このような群のことを $\mathfrak{S}_n$ と書き、 $n$ 次対称群と呼びます。

同値関係

突然ですが、バーンサイドの補題への準備として、同値関係を扱います。

ある集合 $X$ 上において、任意の $X$ の二つの要素同士についてある関係 $\sim$ が定義されているとき、

任意の $x \in X$ に対して、 $x \sim x$ (反射律)
任意の $x,y,z \in X$ に対して、 $x \sim y$ かつ $y \sim z$ ならば $x \sim z$ (推移律)
任意の $x,y \in X$ に対して、 $x \sim y$ ならば $y \sim x$ (対称律)

がすべて成り立つのならば、このような関係を同値関係と呼びます。

同値関係という名前の通り、ある視点から見た際にその要素を同一視してもよいようなもの同士の関係であることが主です。

今後、群上で同値関係を定めたりします。

同値関係の例

★ 余りによる同値関係

$m$ を $1$ より大きい整数としたとき、整数全体の集合の要素に対して $m$ で割った余りが等しいような関係は同値関係です。このような同値関係を $\equiv (\mathrm{mod} \ m)$ などと書きます。

皆さん $m = 998244353$ などでお馴染みなのではないのでしょうか？実際に同値関係か確認してみましょう。

反射律: 任意の整数 $x$ に対して、 $x \equiv x \ (\mathrm{mod} \ m)$ ですから、反射律は成り立っています。
推移律: 任意の整数 $x,y,z$ に対して、 $x \equiv y \ (\mathrm{mod} \ m)$ かつ $y \equiv z \ (\mathrm{mod} \ m)$ であるとき、 $x \equiv z \ (\mathrm{mod} \ m)$ ですから、推移律は成り立っています。
対称律: 任意の整数 $x,y$ に対して、 $x \equiv y \ (\mathrm{mod} \ m)$ ならば $y \equiv x \ (\mathrm{mod} \ m)$ ですから、対称律は成り立っています。

よって $\equiv (\mathrm{mod} \ m)$ が同値関係であると分かりました。

剰余類

$G$ を演算 $\star$ に関して群をなし、 $H$ を $G$ の部分集合であって $\star$ に関して群をなすとします。*3このとき任意の $g \in G$ に対して、

$gH = \{g\star h \ | \ h \in H \}$

を $g$ による $H$ の左剰余類と呼び、

$Hg = \{h \star g \ | \ h \in H \}$

を $g$ による $H$ の右剰余類と呼びます。

剰余類による同値関係

$G,H$ には上の仮定が成り立っているとします。このとき以下が成り立つことが知られています。(証明略)

任意の $a, b \in G$ に対し、 $aH = bH$ もしくは $aH \cap bH = \emptyset$
任意の $a, b \in G$ に対し、 $Ha = Hb$ もしくは $Ha \cap Hb = \emptyset$
任意の $a, b \in G$ に対し、 $aH = bH \Leftrightarrow a^{-1} \star b \in H$
任意の $a, b \in G$ に対し、 $Ha = Hb \Leftrightarrow a \star b^{-1} \in H$

ここで、任意の $a, b \in G$ に対し関係 $a \sim b$ を $aH = bH$ であることと定めると、これは同値関係です。 $a \sim b$ を $Ha = Hb$ であることとしても、同様に同値関係になります。

このことから、剰余類による同値関係は $G$ の要素に対してある種の分類を与えているとわかります。

剰余類による同値関係の例

★ 整数全体の集合と $3$ の倍数全体の集合からなる部分群による同値関係 (加法について)

$\mathbb{Z}$ は加法について群をなします。(実数の場合と同様です)

ここで、 $H$ を $H = \{0, \pm 3, \pm 6, \cdots \}$ と定めると、これは $\mathbb{Z}$ の部分群になっています。

$H$ に対して上のような同値関係を考えましょう。加法は交換法則が成り立つので、左剰余類と右剰余類のどちらを考えてもよいです。ここでは左剰余類を考えます。

少し考えると、 $x,y \in \mathbb{Z}$ に対して $x \sim y$ であることと $x \equiv y \ (\mathrm{mod} \ 3)$ であることは同値です。 $x \equiv y \ (\mathrm{mod} \ 3) \Rightarrow x \sim y$ を示します。

適当に選んできた $x \in \mathbb{Z}$ が $x \equiv n \ (\mathrm{mod} \ 3) \ (0 \leq n \leq 2)$ であったとき、任意の $a \in H$ について $a+x \equiv n \ (\mathrm{mod} \ 3)$ であるため、 $aH = \{3m + n \ | \ m \in \mathbb{Z}\}$ と分かります。

したがって $x \equiv y \ (\mathrm{mod} \ 3) \Rightarrow x \sim y$ です。逆も仮定を $aH = \{3m + n \ | \ m \in \mathbb{Z}\}$ から始めることで容易に示せます。

これより、 $\mathbb{Z}$ の $H$ による同値関係は上で考えた $a \equiv b \ (\mathrm{mod} \ 3)$ と同値と分かります。

また、この同値関係によって $\mathbb{Z}$ は三種類の集合に分けることができます*4。

このような剰余類による同値関係での分類の個数を $|G : H|$ と書き、部分群 $H$ の指数と呼びます。左剰余類と右剰余類による分類の個数は等しいことが知られており(後に証明します)、どちらか区別できなくてもよい記法になっています。

剰余集合

$G$ を群、 $H$ を $G$ の部分群とします。この時、

$G/H = \{gH \ | \ g \in G \}\\$

を左剰余集合、

$H \backslash G = \{Hg \ | \ g \in G \}\\$

を右剰余集合と呼びます。これは先ほど $\mathbb{Z}$ を $H = \{0, \pm 3, \pm 6, \cdots \}$ で分類していたのと同じことをしています。

実際、この定義において $G = \mathbb{Z}, H = \{0, \pm 3, \pm 6, \cdots \}$ と置けば、 $G/H = H \backslash G = \{\{3m+n \ | \ m \in \mathbb{Z}\} \ | \ n \in \mathbb{Z} \} = \{\{3m+n \ | \ m \in \mathbb{Z}\} \ | \ 0 \leq n \leq 2 \}$ となって先ほどの分類と一致します。

ここで証明を保留した「左剰余類と右剰余類による分類の個数は等しい」、つまり $|G/H| = |H \backslash G|$ を示しましょう。

▼ 証明 (長めなので折り畳み) / クリックで展開

これと同じような方法によって示せるものとして、 $|gH| = |Hg| = |H|$ があります。概略としては、 $f: H \to gH$ を任意の $h \in H$ に対して $f(h) = gh$ と定めて、これが全単射であることを示せばよいです。

ここで、 $f(h_1) = f(h_2) \Leftrightarrow gh_1 = gh_2 \Leftrightarrow h_1 = h_2$ より、 $f$ は単射です。全射性は定義より明らかなので、 $f$ の全単射性が示せました。

また、剰余集合における基本的な定理として、以下があります。

ラグランジュの定理

上の状況で

$|G| = |G:H| |H| \\$

が成り立つ。特に $G$ の要素数が有限であるとき、部分群の要素数は $|G|$ の約数だとだとわかる。

証明

$|G| = \infty$ のとき主張は明らかであるため、そうでないときのみを示せばよいです。

$G/H = \{g_1H, g_2H, \cdots, g_{|G:H|} H\}$ となるように $g_1, g_2, \cdots, g_{|G:H|} \in G$ を取ると、 $\displaystyle |G| = \sum_{i=1}^{|G:H|} |g_i H|$ です。

ここで $|gH| = |H|$ より、 $\displaystyle \sum_{i=1}^{|G:H|} |g_i H| = \sum_{i=1}^{|G:H|} |H| = |G:H| |H|$ ですから、 $|G| = |G:H| |H|$ と分かりました。

群の作用

ここから対称性を考える数え上げっぽい話になってきます。

突然ですが、以下のような問題を考えましょう。

問題 (ABC198-F Cube の弱体化 ver.) 正整数 $S$ が与えられます。
正三角形の三つの頂点上に正整数を書き込む方法のうち、その三つの頂点に書かれた数の和がちょうど $S$ となるような書き込み方はいくつあるでしょうか？
ただし回転/反転によって一致するようなものは区別しないとします。

もちろんこれは対称性を考えずに一度全列挙してから、重複を除く処理をして数え上げることもできます。

しかし、もっと効率的な解法が欲しいとなった場合どうすればよいでしょうか。

ここで回転と反転という操作に着目してみると

上の六つの操作が回転や反転を行う方法すべてであると分かります。

これらの操作は、実は $3$ 次の置換全体の集合 (つまり三次対称群) と同一視することができます。

なぜならば、これらの操作は ある点をほかの点へ置換する 操作と言い換えることができ、これはまさに置換の定義と同様だからです。

したがって、三角形の回転と反転による操作は、ある $3$ 次の置換 $\sigma \in \mathfrak{S}_3$ があって、 $\{1,2,3\}$ の順列 $A$ を $\{\sigma(A_1),\sigma(A_2),\sigma(A_3)\}$ へと置き換えるような操作へ言い換えることができます。このようにある群の要素によって集合に行う操作を、 群作用と呼びます。

より形式的な定義をします。

$G$ を $\star$ に対して群、 $e$ を $G$ の単位元、 $X$ を集合とすると、関数 $f_1: G \times X \to X$ が以下の条件

全ての $x \in X$ に対して、 $f_1(e,x) = x$
全ての $g_1 , g_2 \in G , x \in X$ に対して、 $f_1(g_1, f_1(g_2,x)) = f_1(g_1 \star g_2,x)$

を満たすとき、 $f_1$ を $G$ の $X$ への左作用と呼び、

また、関数 $f_2: X \times G \to X$ が以下の条件

全ての $x \in X$ に対して、 $f_2(x,e) = x$
全ての $g_1, g_2 \in G, x \in X$ に対して、 $f_2(f_2(x,g_1),g_2) = f_2(x,g_1 \star g_2)$

を満たすとき、 $f_2$ を $G$ の $X$ への右作用と呼びます。

$G$ から $X$ への右作用もしくは左作用が存在するならば、 $G$ は $X$ に作用するといいます。

この記事ではこれ以降、断りのない限り左作用であるとし $f(x,g)$ を単に $xg$ と書きます。

先ほどの例では、 $G = \mathfrak{S}_3,X =(\{1,2,3\}$ の順列の全体集合 $)$ とすると、

$f: G \times X \to X$ を任意の $g \in G, x \in X$ に対して $f(x,g) = \{g(x_1),g(x_2),g(x_3)\}$ と定めればよいです。

群の軌道 / 安定化群と不動点集合

群 $G$ が集合 $X$ に対して作用しているとします。このとき、 $x \in X$ に対して

$Gx = \{gx \ | \ g \in G\}$

を $x$ の $G$ による軌道と呼び、

$G_x = \{g \in G \ | \ gx = x\}$

を $x$ の安定化群と呼びます。

また、 $g \in G$ に対して

$X^g = \{x \in X \ | \ gx = x\}$

を $g$ の不動点集合と呼びます。

それぞれのお気持ちとしては、

軌道: $x$ に対して操作を繰り返したときにできるパターンの集合
安定化群: $x$ を変化させないような操作の集合
不動点集合: 操作 $g$ に対して不変であるようなパターンの集合

のような感じです。

安定化群に対して、以下の定理は基本的です。

軌道安定化群定理

任意の $x \in X$ について、上の状況で

$|G/G_x| = |Gx|$

が成り立つ。

証明

関数 $f: G/G_x$ を任意の $gG_x \in G/G_x$ に対して $f(gG_x) = gx$ と定めます。この関数が well-defined であることを確認しましょう。

$g_1, g_2 \in G$ が $g_1 G_x = g_2 G_x$ を満たすとします。この時

$g_1 G_x = g_2 G_x \Leftrightarrow g_2 ^{-1} g_1 G_x = G_x \Leftrightarrow g_2^{-1} g_1 \in G_x \Leftrightarrow g_2^{-1} g_1x = x \Leftrightarrow g_1x = g_2x$

であるため、 $f$ は well-defined です。さらにこれらはすべて同値であることから、 $f$ が全単射であることも従います。

したがって $G/G_x$ の要素と $Gx$ の要素は一対一対応し、 $|G/G_x| = |Gx|$ が示せました。

群作用による同値関係

剰余類を考えたときと同じような関係を定義します。

群 $G$ が集合 $X$ に対して作用しているとしたとき、 $x, y \in X$ に対して、関係 $x \sim y$ を $Gx = Gy$ であることと定めます。このとき関係 $\sim$ は同値関係です。

ここで $Gx = Gy$ であることの意味を考えてみると、これは対称性を考慮したとき $x$ と $y$ を同一視してもよいととらえることができます。ここで、

$X/G = \{Gx \ | \ x \in X\}$

と定めれば、本質的には $|X/G|$ を求めることによって対称性を考慮した数え上げができると分かります。

バーンサイドの補題

いよいよ本題(補題ですが)です。まずは主張を確認してみましょう。

バーンサイドの補題

有限群 $G$ が有限集合 $X$ に作用しているとする。このとき

$\displaystyle |X/G| = \frac{1}{|G|} \sum_{g \in G} |X^g|$

が成り立つ。

砕けた言葉で言いかえれば「対称性を考えたときの数え上げの答えは各操作に対して不変なものに対する答えの総和を操作の種類数で割ったものに等しい」となります。

これを用いて先ほどの問題を解いてみましょう。

問題正整数 $S$ が与えられます。
正三角形の三つの頂点上に正整数を書き込む方法のうち、その三つの頂点に書かれた数の和がちょうど $S$ となるような書き込み方はいくつあるでしょうか？
ただし回転/反転によって一致するようなものは区別しないとします。

解法

先ほど行った議論から、回転に関しては $G = \mathfrak{S}_3$ とすればよいです。

また、 $X = (三つの正整数からなる総和が \ S \ である順序集合全体の集合)$ とし、 $f: G \times X \to X$ を任意の $g \in G, x \in X$ に対して $f(g,x) = (x_{g(1)},x_{g(2)},x_{g(3)})$ とすると、 $f$ は左作用です。