数酸

数学に関して書き留めておこうと思ったものを気まぐれに。

バーンサイドの補題

代数

バーンサイドの補題

有限群 ${ G }$ が有限集合 ${ X }$ に作用しているとき ${ G }$ による軌道の数 ${ |X/G| }$ は以下で与えられる。

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

但し ${ X^g=\{x \in X; gx=x\}}$

まず ${ G }$ が推移的な作用である場合に示します。すなわち

補題の補題

${ G }$ が推移的に作用しているとき(軌道がたった一つのとき)

$|G|=\sum_{g \in G} |X^g|$

群 ${ G }$ は軌道ごとに別々に作用していると考えても問題ないので、この場合がバーンサイドの補題の本質的な部分です。

証明

${\displaystyle \sum_{g \in G} |X^g| }$

$=\sum_{g \in G} \sum_{x \in X} \chi_{\{gx=x\}}(g,x)$

$=\sum_{x \in X}\sum_{g \in G} \chi_{\{gx=x\}}(g,x)$

${ G_x }$ を ${ x }$ の固定部分群として

${\displaystyle =\sum_{x \in X} G_x }$

${\displaystyle =\sum_{x \in X} \frac{|G|}{|X|} }$

${\displaystyle =|G| }$ 　□

なんだかよく分からないのでコトバでもう一度追っていきましょう。

各 ${ g \in G }$ に対して ${ g }$ の作用で不変な ${ X }$ の元の数を集計する。しかし ${ g }$ ごとに集計するとその数はバラバラで数えるのが大変。なので ${ x \in X }$ の元ごとに集計することにしてみる(二重和の交換)。すると、同じ軌道上では固定部分群の位数はどれも等しく ${ \frac{|G|}{|X|} }$ であることから。 ${ x \in X }$ 全体で和をとれば ${ \frac{|G|}{|X|}\times |X|=|G| }$ となる。

バーンサイドの補題の証明

${ G }$ の作用を各軌道に制限すれば各々では推移的に作用していることに注意する。

$|X/G||G|$

$=\sum_{Y \in X/G} |G|$

補題の補題より

$=\sum_{Y \in X/G} \sum_{g \in G} |Y^g|$

$=\sum_{g \in G} \sum_{Y \in X/G} |Y^g|$

$=\sum_{g \in G} |X^g|$ □

これもコトバでもう一度(終わりの式から逆走します)。

各 ${ g \in G }$ に対して ${ g }$ の作用で不変な ${ X }$ の元の数を集計する。 ${ X }$ の各軌道ごとに集計してから全軌道で足し合わせることにする。すると補題の補題から、各軌道についてはどれも ${ |G| }$ となる。だからもちろん、全軌道での和は ${ |G|\times|G/X| }$ である。

結局、証明はほとんど部分集計の手順を変えることしかしていませんね。ですがこの補題は回転させたり順序を変えたりして一致するものを同一視する場合の数え上げにおいて非常に便利な式であり、憶えておいて損はないでしょう。