体験を伝える―『ガジェット通信』の考え方

面白いものを探しにいこう 本物を体験し体感しよう 会いたい人に会いに行こう 見たことのないものを見に行こう そしてそれをやわらかくみんなに伝えよう [→ガジェ通についてもっと詳しく] [→ガジェット通信フロアについて]

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

群とは?

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

正確な定義を述べると、ある集合Gとその元の間の演算*が以下の3つの条件を満たすとき、(G, *)は群であると定義されます。
結合則 : 任意のx,y,z∈Gについて、(x * y) * z = x * (y * z)が成り立つ。
単位元の存在 : 任意のa∈Gについてあるe∈Gが存在し、x * e = e * x = xが成り立つ。
eは単位元と呼ばれる。
逆元の存在 : 任意の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

1 2次のページ
CodeIQ MAGAZINEの記事一覧をみる
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。