プログラミング言語Egisonによるガロア理論入門 (2) ―対称群と正規部分群

群とは？

数に対して定義されたかけ算を一般化して、色々な集合の上にかけ算のような演算を定義して生まれた概念が群です。

正確な定義を述べると、ある集合Gとその元の間の演算*が以下の3つの条件を満たすとき、(G, *)は群であると定義されます。

1. 結合則 : 任意のx,y,z∈Gについて、(x * y) * z = x * (y * z)が成り立つ。
2. 単位元の存在 : 任意のa∈Gについてあるe∈Gが存在し、x * e = e * x = xが成り立つ。
   eは単位元と呼ばれる。
3. 逆元の存在 : 任意のx∈Gについてあるr∈Gが存在し、x * r = r * x = eが成り立つ。
   rは逆元と呼ばれる。

例えば、有理数全体の集合をQ、有理数上の乗算を*としたとき、(Q, *)は群です。
整数全体の集合をZとしたとき、(Z, *)は逆元の存在の条件を満たさないので群ではないです。

対称群

対称群とはどのような群なのか具体例を示しながら説明します。

n個の元からなる順列の集合を考えます。
例えば、3個の元からなる順列は{1 2 3}、{2 1 3}、{1 3 2}、{3 1 2}、{2 3 1}、{3 1 2}の6通りあります。
この順列の集合の上で、前節の条件を満たす2項演算*を定義することを考えます。
1つめの順列を2つめの順列で置換する演算*を定義すると群となります。
例えば、以下のような感じです。

{1 2 3} * {3 1 2} = {3 1 2}
{2 1 3} * {3 1 2} = {3 2 1}

このように並び替え操作について作られる群は対称群と呼ばれています。

ところで、対称群の2項演算*は可換とは限りません。
例えば、

{2 1 3} * {3 1 2} = {3 2 1}
{3 1 2} * {2 1 3} = {1 3 2}

となります。

2項演算*が任意の元に対して可換である群は可換群と呼ばれています。
逆に、可換でない元の組み合わせのある群は非可換群と呼ばれています。
対称群は一般に非可換群です。

一般的に、n個の元からなる集合の並び替えについての対称群はn次対称群と呼ばれています。
その元の個数はn!です。

n次対称群はSnと表記されます。
群に含まれる元の個数は位数と呼ばれています。
Snの位数がn!であること記すのに、order(Sn)=n!のように表記します。

また、対称群の部分群は置換群となります。

Egisonで対称群の計算

以下のコマンドにより、対称群について計算するためのライブラリをロードしたEgisonインタプリタを立ち上げることができます。

$ git clone https://github.com/egison-libs/galois-theory.git
$ cd galois-theory
$ egison -l lib/math/algebra/symmetric-group.egi

このライブラリのマニュアルは、GitHub上にあるこのライブラリのリポジトリにあります。

例えば、対称群の元の積は、G.*関数により計算することができます。

> (G.* {2 1 3} {3 1 2})
{3 2 1}

> (G.* {3 1 2} {2 1 3})
{1 3 2}

また、変数s3、s4、s5にはそれぞれ対称群S3、S4、S5の元が束縛されています。

> s3
{{1 2 3} {1 3 2} {2 1 3} {2 3 1} {3 1 2} {3 2 1}}

群の内部構造

群に含まれている群、部分群を通して群は観察されます。
例えば({2 1 3}, {1 2 3})や({3 1 2}, {2 3 1}, {1 2 3})はS_3の部分群です。
また、この2つの部分群のように、ある1つの元から生成される群は巡回群と呼ばれています。

部分群は、自然数の素因数分解のアナロジーで考えることができます。
例えば、巡回部分群は対称群にとって、自然数にとっての素数のようなものと考えることができます。

Egisonで巡回群の計算

gen-cyclic-groupは、引数として与えられた置換により生成される巡回群を返す関数です。

> (gen-cyclic-group {2 1 3})
{{2 1 3} {1 2 3}}

> (gen-cyclic-group {2 3 1})
{{2 3 1} {3 1 2} {1 2 3}}

引数として与えられた群の巡回部分群すべてを列挙する関数も用意されています。

> (cyclic-subgroups s3)
{{{1 2 3}}
 {{1 3 2} {1 2 3}}
 {{2 1 3} {1 2 3}}
 {{2 3 1} {3 1 2} {1 2 3}}
 {{3 2 1} {1 2 3}}}

正規部分群

代数方程式の解法について考察する際に、もっとも重要な役割を果たすのは正規部分群と呼ばれる部分群の概念です。
群Gの部分群Hについて、「任意のg∈GについてgH = Hgが成り立つ」とき、HはGの正規部分群であると定義されます。
gHとは、Hの元それぞれに左からgを掛けた結果の集合です。
その逆に、Hgとは、Hの元それぞれに右からgを掛けた結果の集合です。
また、G * HとはGのそれぞれの元にHのそれぞれの元を右から掛けた結果を集めた集合とします。
ある群が正規部分群であるということは、その群による左剰余類の集合と右剰余類の集合が一致することと言い換えることができます。
ここで、群Gの部分群HのGに対する左剰余類の集合とは以下の条件を満たすL_1、L_2、…、L_mのことを指します。

L_1 * H = L_1
L_2 * H = L_2
...
L_m * H = L_m                             - (A)

m = order(G) / order(H)
order(L_i) = order(H)     (1 ≦ i ≦ m)

また、群Gの部分群HのGに対する右剰余類の集合とは以下の条件を満たすR_1、R_2、…、R_mのことを指します。

H * R_1 = R_1
H * R_2 = R_2
...
H * R_m = R_m                             - (B)

m = order(G) / order(H)
order(R_i) = order(H)     (1 ≦ i ≦ m)

例えば、({1 2 3}, {2 3 1}, {3 1 2})についてその剰余類を求めると以下のようになります。
以下、A_3 = ({1 2 3}, {2 3 1}, {3 1 2})とおきます。
A_3については左剰余類と右剰余類の集合が一致しており、正規部分群であることがわかります。

({1 2 3}, {2 3 1}, {3 1 2}) * A_3 = ({1 2 3}, {2 3 1}, {3 1 2}) = L_1
({2 1 3}, {1 3 2}, {3 2 1}) * A_3 = ({2 1 3}, {1 3 2}, {3 2 1}) = L_2

A_3 * ({1 2 3}, {2 3 1}, {3 1 2}) = ({1 2 3}, {2 3 1}, {3 1 2}) = R_1 = L_1
A_3 * ({2 1 3}, {1 3 2}, {3 2 1}) = ({2 1 3}, {1 3 2}, {3 2 1}) = R_2 = L_2

次に、正規部分群でない部分群の例として、({1 2 3}, {2 1 3})についてその剰余類を求めると以下のようになります。
以下、P_3 = ({1 2 3}, {2 1 3})とおきます。
P_3については左剰余類と右剰余類の集合にずれが生じます。

({1 2 3}, {2 1 3}) * P_3 = ({1 2 3}, {2 1 3}) = L_1
({2 3 1}, {3 2 1}) * P_3 = ({2 3 1}, {3 2 1}) = L_2
({3 1 2}, {1 3 2}) * P_3 = ({3 1 2}, {1 3 2}) = L_3

P_3 * ({1 2 3}, {2 1 3}) = ({1 2 3}, {2 1 3}) = R_1 = L_1
P_3 * ({2 3 1}, {1 3 2}) = ({2 3 1}, {1 3 2}) = R_2 ≠ L_2
P_3 * ({3 1 2}, {3 2 1}) = ({3 1 2}, {3 2 1}) = R_3 ≠ L_3

交換子部分群

正規部分群と関連する重要な概念に交換子部分群があります。
群Gの交換子部分群とは、{(1/g) * (1/h) * g * h | g,h ∈ G} (ただし、(1/g)、(1/h)はそれぞれg、hの逆元)のことをいいます。
群Gの交換子部分群は、Gとそれとによる商群が可換群となるような正規部分群のうちで最小のものであるという性質があります。

後に続く節で、S3とS5の交換子部分群を実際に計算してみます。

交換子群列

H_(k+1)がH_kの交換子部分群であるような部分群の列

G = H_0 ≧ H_1 ≧ ... ≧ H_k = {e}

は、交換子群列と呼ばれています。

実は、n次代数方程式に代数的な解法があるということは、n次対称群について交換子群列あることと言い換えることができると知られています。
交換子群列を持つ群は可解群と呼ばれます。
交換子部分群が正規部分群であること、それによる商群が可換群であることが、この対応について大きな役割を果たします。
次回の記事でこの対応について紹介できたらと考えています。

S3、S4は可解群であるがS5は可解群でないことが知られています。
以下、このことをEgisonを使って確かめてみます。

S2の交換子群列

S2自身が位数が素数2の巡回群であり、可換群です。

S3の交換子群列

S3の交換子群列をEgisonを使って求めてみましょう。

> (commutator-subgroup s3)
{{1 2 3} {2 3 1} {3 1 2}}
> (commutator-subgroup (commutator-subgroup s3))
{{1 2 3}}

つまり、S3は、以下のように長さ3の交換子群列を持っています。

s3 = H_0 ≧ {{2 3 1} {3 1 2} {1 2 3}} = H_1 ≧ {{1 2 3}} = H_2 = {e}

H_1がH_0の正規部分群であること、H_2がH_1の正規部分群であることは以下のように確かめれれます。

> (normal-subgroup? (commutator-subgroup s3) s3)
#t
> (normal-subgroup? (commutator-subgroup s3) s3)
#t

また、H_0/H_1が可換群であることは以下のように確かめられます。
H_1/H_2については、 H_1/H_2 = H_1でありH_1は可換群であるので、こちらも可換群です。

> (G.// s3 (commutator-subgroup s3))
{{1 3 2} {1 2 3}}

ここで、H_0、H_1、H_2の位数の関係を調べると、以下のようになっています。

order(H_0)/order(H_1) = 2
order(H_1)/order(H_2) = 3

実は、これは、3次方程式の解の公式において、3乗根の中に2乗根が現れる箇所があることに対応しています。

S5の交換子群列

S5には、交換子群列がないことが知られています。
このことは、5次方程式に解法がないことと対応しています。
このことをEgisonを使って確かめてみましょう。

> (commutator-subgroup s5)
{{1 2 3 4 5} {1 2 4 5 3} {1 2 5 3 4} {1 3 2 5 4} {1 3 4 2 5} {1 3 5 4 2} {1 4 2 3 5} {1 4 3 5 2} {1 4 5 2 3} {1 5 2 4 3} {1 5 3 2 4} {1 5 4 3 2} {2 1 3 5 4} {2 1 4 3 5} {2 1 5 4 3} {2 3 1 4 5} {2 3 4 5 1} {2 3 5 1 4} {2 4 1 5 3} {2 4 3 1 5} {2 4 5 3 1} {2 5 1 3 4} {2 5 3 4 1} {2 5 4 1 3} {3 1 2 4 5} {3 1 4 5 2} {3 1 5 2 4} {3 2 1 5 4} {3 2 4 1 5} {3 2 5 4 1} {3 4 1 2 5} {3 4 2 5 1} {3 4 5 1 2} {3 5 1 4 2} {3 5 2 1 4} {3 5 4 2 1} {4 1 2 5 3} {4 1 3 2 5} {4 1 5 3 2} {4 2 1 3 5} {4 2 3 5 1} {4 2 5 1 3} {4 3 1 5 2} {4 3 2 1 5} {4 3 5 2 1} {4 5 1 2 3} {4 5 2 3 1} {4 5 3 1 2} {5 1 2 3 4} {5 1 3 4 2} {5 1 4 2 3} {5 2 1 4 3} {5 2 3 1 4} {5 2 4 3 1} {5 3 1 2 4} {5 3 2 4 1} {5 3 4 1 2} {5 4 1 3 2} {5 4 2 1 3} {5 4 3 2 1}}
> (commutator-subgroup (commutator-subgroup s5))
{{1 2 3 4 5} {1 2 4 5 3} {1 2 5 3 4} {1 3 2 5 4} {1 3 4 2 5} {1 3 5 4 2} {1 4 2 3 5} {1 4 3 5 2} {1 4 5 2 3} {1 5 2 4 3} {1 5 3 2 4} {1 5 4 3 2} {2 1 3 5 4} {2 1 4 3 5} {2 1 5 4 3} {2 3 1 4 5} {2 3 4 5 1} {2 3 5 1 4} {2 4 1 5 3} {2 4 3 1 5} {2 4 5 3 1} {2 5 1 3 4} {2 5 3 4 1} {2 5 4 1 3} {3 1 2 4 5} {3 1 4 5 2} {3 1 5 2 4} {3 2 1 5 4} {3 2 4 1 5} {3 2 5 4 1} {3 4 1 2 5} {3 4 2 5 1} {3 4 5 1 2} {3 5 1 4 2} {3 5 2 1 4} {3 5 4 2 1} {4 1 2 5 3} {4 1 3 2 5} {4 1 5 3 2} {4 2 1 3 5} {4 2 3 5 1} {4 2 5 1 3} {4 3 1 5 2} {4 3 2 1 5} {4 3 5 2 1} {4 5 1 2 3} {4 5 2 3 1} {4 5 3 1 2} {5 1 2 3 4} {5 1 3 4 2} {5 1 4 2 3} {5 2 1 4 3} {5 2 3 1 4} {5 2 4 3 1} {5 3 1 2 4} {5 3 2 4 1} {5 3 4 1 2} {5 4 1 3 2} {5 4 2 1 3} {5 4 3 2 1}}

上記のように、S5の交換子部分群はA5とおくと、A5の交換子部分群もA5です。
それゆえ、S5の交換子群列は存在しません。

参考文献

• 桂利行(2004)「代数学1　群と環」東京大学出版会

• 0
• 0
• 1

8,568通り、あなたはどのタイプ？

グッドポイント診断で、あなたの隠れた強みを診断してみましょう。

診断結果は8,568通り。あなたはどのタイプ？

グッドポイント診断

あなたの新しい可能性が見つかるかも

リクナビNEXTにログインすると、あなたの志向に合った特別な求人一覧を見ることができます。

予想外の求人が、あなたの世界を広げるかもしれません。

会員登録（無料）

タグ

• #プログラミング
• #Egison
• #パターンマッチ
• #数学