CodeIQ MAGAZINECodeIQ MAGAZINE

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

2018.01.25 Category:技術コラム Tag: , , ,

  • 19
  • このエントリーをはてなブックマークに追加

前回の記事では、2次方程式の解法をプログラムで記述しました。
本記事では、3次以上の方程式の解法を説明するために、その準備として対称群と呼ばれる群の構造をプログラムで調べます。
対称群の構造と、代数方程式の解法の間には対応関係があるため、対称群の構造を調べると、代数方程式の解法を知ることができます。
by 江木聡志(楽天技術研究所・Egison作者)

群とは?

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

正確な定義を述べると、ある集合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}

また、変数s3s4s5にはそれぞれ対称群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 群と環」東京大学出版会
  • 19
  • このエントリーをはてなブックマークに追加

■この記事を書いた人

avatar

江木聡志(楽天技術研究所・Egison作者)

楽天技術研究所 研究員 1986年生まれ。2010年、東京大学理学部情報科学科卒業。2012年、同大学院情報理工学系研究科修士(コンピュータ科学)。2010年、プログラミング言語Egisonの設計・開発を開始。2011年度未踏IT人材発掘・育成事業スーパークリエータ受賞。2013年11月に楽天技術研究所に入所し現職。2015年2月、ソフトウェアジャパンアワード受賞。2015年10月、日本OSS奨励賞受賞。

■関連記事

プログラミング言語Egisonによるガロア理論入門 (1) ―2次方程式の解の導出... プログラムで代数方程式を解く 数式処理システムの機能を持つプログラミング言語Egisonでは、√2や√3のような数を浮動小数点数として近似することなくプログラム上で扱うことができます。 この機能を用いると、2次方程式、3次方程式、4次方程式を始めとする代数方程式の解を求めるプログラムを記述するこ...
数式処理システムとしてのプログラミング言語Egisonの紹介... シンボリックな計算とは シンボリックな計算とは、x + x = 2xや(x + y)^2 = x^2 + 2 x y + y^2のようにxやyといったシンボルをプログラム上で数と同様に扱い計算することをいいます。 シンボリックな計算をサポートしている既存の数式処理システムとしては、Mathema...
エンジニアにこそ求められる?「ビジネス数学」を学んでみよう!... 学校の数学と何が違う? 学生生活でたくさん勉強したはずの数学。でも仕事をする上で役に立っていないと感じている人も多いのではないでしょうか。 高校生の頃から文系に進み、受験勉強や大学でも数学を避けてきた人も多くいます。実際、多くの会社員にとって、仕事で三角形の合同を証明することはありませんし、微分...
アドテクの裏側で暗躍!?ユーザーの嗜好を紐解くベイジアンネットワークとは... ベイジアンネットワーク -「因果」のモデリング ベイズの定理を説明した前編では、以下のような問いを設定していました。 患者Aは咳が出て節々が痛く、喉が腫れている。病名は何? プリンターが不調。縦線のノイズが入る。どこが故障している? それぞれ、医師やカスタマーサポートであれば解決できる...
「機械学習クラスタのベイズって何?」という人へ──まずは『ベイズの定理』を学んでみよう... 「ベイズ」や「ベイジアン」を聞き流し続けているあなたへ この記事では分かりやすく、ベイズ統計の基本中の基本である「ベイズの定理」の使い方について説明していきます。 実例で分かるベイズの定理 – 感染検査薬の実用性を測る あなたは某大手製薬会社で、ある伝染病の検査薬開発に関わる研究開発社員だ...
Egison独自の機能の紹介──パターンマッチ指向プログラミング言語Egison紹介(第3回)... パターンマッチとは パターンマッチは、複雑なデータの操作を簡潔な記述で扱うための機能です。 パターンマッチにより、複数の何重にもネストするアクセサー関数やループ、条件分岐を記述せずに、簡潔なパターンを記述するだけで、複雑なデータ型の操作をプログラマは記述できるようになります。 図1. パタ...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

CodeIQ(コードアイキュー)とは、自分の実力を知りたいITエンジニア向けの、実務スキル評価サービスです。

CodeIQご利用にあたって
関連サイト
codeiq

リクルートグループサイトへ