以前書いた記事「競プロerのための群論 (swapと順列と対称群)」は、競技プログラミングと関係ある部分をメインに、群論について解説しました。思った以上に色々な人に読まれて嬉しくなりました。
そこで今回は、以前の記事では取り上げなかった群論の話題について解説していこうと思います。競技プログラミングに役立つ部分は前回の記事で大部分説明したため、役立つ部分は少ないかもしれません。
共役類
群 $G$ の元をグループ分けすることを考えます。競技プログラミング的には、友達関係が与えられたときに UnionFind で友達グループを作るのと似たような感覚です。そこで、群 $G$ に「友達関係」を定めます (正確には同値関係と呼ばれます)。今回は次のような関係を定めてみます。
- $g,h\in G$ に対し、$g\sim h$ を、ある $x\in G$ が存在して $g=x^{-1}hx$ となることと定める。
$g\sim h$ となるとき、$g,h$ は共役であるといいます。共役である元を集めてグループを作ったとき、そのグループを共役類といいます。
対称群の共役類
例として、4 次対称群 $S_4$ の共役類を調べてみましょう。
と
は共役です。なぜなら
となるからです。一方で
と
は共役ではありません。このように分類することで、$S_4$ には 5 つの共役類が存在することがわかります。これらは次のようになっています (巡回置換を用いて表します)。
- $\{\mathrm{id}\}$
- $\{(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)\}$
- $\{(1,2,3),(1,2,4),(1,3,2),(1,3,4),(1,4,2),(1,4,3),(2,3,4),(2,4,3)\}$
- $\{(1,2)(3,4),(1,3)(2,4),(1,4)(2,3)\}$
- $\{(1,2,3,4),(1,2,4,3),(1,3,2,4),(1,3,4,2),(1,4,2,3),(1,4,3,2)\}$
これを見ると、同じ共役類に属する2つの元は、同じ長さの巡回置換からなるように見えます。これは実際に正しいです。置換を共通文字を含まない巡回置換の積として表したとき (表せることは前回の記事で説明しました)、巡回置換の長さからなる multiset を、巡回置換型 (あるいは単に型) と呼びます。各共役類の元の型は次のようになります。
- $\{1,1,1,1\}$
- $\{2,1,1\}$
- $\{3,1\}$
- $\{2,2\}$
- $\{4\}$
対称群の共役類は、対称群の元の型と一対一に対応します。そして、対称群の元の型は自然数の分割と一対一に対応します。上の例では
- $1+1+1+1$
- $2+1+1$
- $3+1$
- $2+2$
- $4$
は $4$ の分割となっています。さらにこれらはヤング図形とも一対一に対応します。
分割数 $P_N$ を求めればよいことになります。蟻本の 66 ページに $O(N ^ 2)$ で計算する方法が載っています。また、$O(N\sqrt{N})$ で求めることもできるようです。(分割数のDPをO(Nsqrt(N))でやる - DEGwerのブログ)
ヤング図形に数を書き込むことで、標準ヤング盤と呼ばれるものができます。標準ヤング盤は対称群の表現論とも関わっています。また、競技プログラミングにおいてもヤング盤を用いて解ける問題があるようです。以下の記事で解説されています。
交代群の共役類
$S_N$ を $N$ 次対称群、$A_N$ を $N$ 次交代群とします。$g,h\in A_N$ が $A_N$ において共役であるということは、ある $x\in A_N$ が存在して $g=x^{-1}hx$ となることです。当然 $A_N \subseteq S_N$ なので、$A_N$ で共役ならば $S_N$ でも共役です。よって、$g,h$ が $A_N$ で共役ならば型が一致します。しかし逆は一般に成り立ちません。では $A_N$ で共役であるための条件は何でしょうか。
この部分を問う問題を yukicoder で出題しました。詳しい解説は yukicoder の方に書いたので、ここでは結果だけ書きます。$A_N$ の共役類は次のようになります。
- 型が相異なる奇数からなるとき、2 つの共役類と対応する。($N=1$ の場合を除く)
- そうでないとき、1 つの共役類と対応する。
例として $A_4$ を考えます。型は
- $\{1,1,1,1\}$
- $\{2,2\}$
- $\{3,1\}$
の 3 種類ですが、このうち $\{3,1\}$ のみ相異なる奇数からなるので 2 つの共役類と対応します。よって $A_4$ には 4 つの共役類が存在します。
剰余群
$H$ を $G$ の部分群とします。このとき、別の同値関係を定めることができます。今回は次のような同値関係を定義します。
$g,h\in G$ に対し、$g\sim h$ を、$g^{-1}h\in H$ となることと定める。
この同値関係による同値類を (左)剰余類 といいます。
例として、$G$ を整数からなる加法群 $\mathbb{Z}$、$H$ を 10 の倍数からなる部分群 $10\mathbb{Z}$ とします。すると
$g\sim h \iff -g+h\in 10\mathbb{Z} \iff g\equiv h\pmod{10}$
となります。つまり 10 で割った余りが等しいとき同じ剰余類に属します。「剰余」類という名前の理由がわかったかもしれません。
左剰余類からなる集合を $G/H$ と表します。この例では
となります。$g$ を含む同値類を $\bar{g}$ と表すことにすれば
$$ \mathbb{Z}/10\mathbb{Z}=\{\bar{0},\bar{1},\bar{2},\bar{3},\bar{4},\bar{5},\bar{6},\bar{7},\bar{8},\bar{9}\} $$
となります。
ご存じのように、$\mathbb{Z}/10\mathbb{Z}$ は加法について群となります。そこで、一般に $G/H$ 上の群演算を $\bar{g}\cdot \bar{h}=\overline{g\cdot h}$ と定めたくなります。
しかし、残念ながらこの定義はうまくいくとは限りません。なぜなら $\bar{g}=\bar{g'}, \bar{h}=\bar{h'}$ でも、$\overline{g\cdot h}=\overline{g'\cdot h'}$ となるとは限らないからです。そのため、$H$ に次のような条件を課します。
- $G$ の部分群 $H$ が正規部分群であるとは、任意の $g\in G, h\in H$ に対し、$g^{-1}hg\in H$ となることをいう。
$H$ が $G$ の正規部分群であるとき、$G/H$ は $\bar{g}\cdot \bar{h}=\overline{g\cdot h}$ により群となります。これを剰余群といいます。
$H$ が $G$ の部分群であることを $H\le G$、正規部分群であることを $H\unlhd G$ と表すこともあります。
単純群
$\{\mathrm{id}\}$ と $G$ は常に $G$ の正規部分群です。$\{\mathrm{id}\}$ と $G$ 以外に正規部分群をもたないような群 $G$ のことを、単純群といいます。
$\mathbb{Z}/10\mathbb{Z}$ は、$\{\bar{0},\bar{5}\}$ を正規部分群にもつので単純群ではありません。一方、$\mathbb{Z}/5\mathbb{Z}$ は単純群です。実は、$\mathbb{Z}/n\mathbb{Z}$ が単純群であるための必要十分条件は、$n$ が素数であることです。
なんとなく単純群と素数は似たものであるような雰囲気を感じます。次の定理を見るとより強く実感できるのではないでしょうか。
群 $G$ に対し、部分群の列 $\{\mathrm{id}\}=G_1\le G_2\le\cdots\le G_n=G$ であって、$G_i$ が $G _ {i+1}$ の正規部分群かつ、$G _ {i+1}/G_i$ が単純群になるようなものを組成列といいます。次の定理が成り立ちます。
ジョルダン・ヘルダーの定理: multiset $\{G_{i+1}/G_i\}$ は組成列によらず一意である。
例えば $G=\mathbb{Z}/10\mathbb{Z}$ には 2 つの組成列 $\{\bar{0}\}\le \{\bar{0},\bar{5}\}\le G$ と、$\{\bar{0}\}\le \{\bar{0},\bar{2},\bar{4},\bar{6},\bar{8}\}\le G$ がありますが、前者の場合 $(G_2/G_1,G_3/G_2)=(\mathbb{Z}/2\mathbb{Z}, \mathbb{Z}/5\mathbb{Z})$、後者の場合 $(G_2/G_1,G_3/G_2)=(\mathbb{Z}/5\mathbb{Z}, \mathbb{Z}/2\mathbb{Z})$ で、順番の違いを除いて一致しています。素因数分解の類似物といえます。
任意の群は単純群を積み重ねて得られるものとみることができます。整数論において素数を調べることが重要であったように、群論においては単純群を調べることが重要になります。そのため、多くの数学者が単純群の研究を行ってきました。偉大な結果の 1 つが有限単純群の分類定理です。証明が完了したのは 2004 年で、証明は 10000 ページ以上にも及ぶと言われています。この定理によると、有限単純群は以下のリストのいずれかの群と同型です。
5 次以上の交代群が単純群であるということは、5 次以上の方程式が代数的な解の公式をもたないことと関連します。詳しくはガロア理論で検索！
注目を集めているのが散在型単純群です。なぜ有限単純群を分類するとどの系列にも属さないような単純群が 26 個も出てくるのか、その不思議な性質が注目を集めています。特に散在型単純群の中で最も位数の大きいモンスター群は、モンストラス・ムーンシャインと呼ばれる不思議な現象を起こしています。
GAP
趣味に走りすぎてプログラミングと関係なくなってしまったので、ここでプログラミングと関係ある話題をします。やはり群の計算もプログラミングでしたいですよね？そこで、GAP を紹介します。
GAP は数式処理システムで、群をはじめとして様々な代数を扱うことができます。以下が公式サイトです。
導入を済ませたら、実際に計算してみましょう。上で扱った4 次交代群の共役類を求めるには
g:=AlternatingGroup(4); cl:=ConjugacyClasses(g);
と入力します。すると
[ ()^G, (1,2)(3,4)^G, (1,2,3)^G, (1,2,4)^G ]
と出力されました。共役類が 4 つで、代表元がそれぞれ $\mathrm{id},(1,2)(3,4),(1,2,3),(1,2,4)$ であることがわかります。普通のプログラミング言語と同様に if 文や for 文もあります。例えば、各共役類の大きさを知りたいときは
for c in cl do
Print(Size(c), ",");
od;
と入力することで、1,3,4,4 が出力されます。
この GAP を使って競技群論みたいなことできませんか？あったら楽しそうと妄想しています。
おわりに
競技プログラミングと数学の関連というと、整数論・数え上げ・グラフ理論が取り上げられがちですが、群論も関わりがあるぞということを伝える記事でした。
参考文献など
前回の記事で挙げたものは省略します。
- 鈴木通夫, 有限単純群, 紀伊国屋数学叢書, 1987
- 読みたいんですが、結構高いので購入をためらっています。
- Wilson, The Finite Simple Groups, Graduate Texts in Mathematics, Vol. 251 (Springer, London, 2009).
- 有限単純群辞典のような本です。行間は広め。いつかちゃんと読みたいです。
- 数え上げテクニック集
- DEGwerさんのPDFです。群の話題もあります。
- 整数論テクニック集
- 夕叢霧香さんのPDFです。群の話題もあります。
