■因数分解の算法(その5)

 
 代数学の教えるところによれば,n元の体(加減乗除の演算が定義された集合)が存在するための必要十分条件は,nが素数(のベキ乗)になっていることで,位数2,3,4=2^2,5の体は存在するが,位数6=2×3の体は存在しない.そして,位数7,8=2^3,9=3^2の体は存在して,位数10=2×5のものは存在しない.コラム「因数分解の算法(その3)」は,このことを示すのに絶好のテーマになっていたと思う.
 
 今回のコラムでは位数nの群を扱うことにするが,任意のnに対してn元の群は存在し,位数2の群は1つ,位数3の群は1つ,位数4の群は2つある.すると,位数5の群は?,位数6の群は?,・・・という疑問が湧いてくるのは自然な成り行きであろう.そこで,
  硲文夫「論理と代数の基礎」培風館
の助けを借りて,これを埋めていくのが今回のコラムの課題である.
 
===================================
 
【1】群の公理と位数2の群
 
 群とは,単なる集まりではなく,2項演算※が定義された集合Gで,次の条件が満たされているとき,Gを群と呼びます.
 
 群の公理(ケイリー,1878年)
  (1)単位元eをもつ(恒等変換)
  (2)逆元a^(-1)をもつ
  (3)結合法則a※(b※c)=(a※b)※cが成立する
 
 このような抽象代数系が群であり,その構造が問題にされるようになったのは19世紀末近くになってからのことです.交換法則を満たすことは仮定されていませんが,さらに,群Gの2項演算に交換法則が成立するとき,可換群(アーベル群)と呼ばれます.また,群Gが有限集合のときが有限群で,その元の個数は|G|と書かれ,Gの位数と呼ばれます.
 
 ところで,コンピュータはたくさんのスイッチ(ON/OFF素子)からできているわけですが,
  ON=1,OFF=0
という2つの元からなる数体系を対応させることができます.そして,演算規則
  +  0  1     ×  0  1
  0  0  1     0  0  0
  1  1  1     1  0  1
がそれぞれOR回路,AND回路に相当します.
 
 単位元の行(列)には,演算表の欄外の元がまったく同じ順序で並んでいるわけですから,論理和+は単位元として0を,論理積×は1をもつことがわかります.
  +  0  1     ×  0  1
  0  0  1★    0  0  0
  1  1  1     1  0  1★
     ★              ★
 
 しかし,論理和では単位元0の逆元は0ですが,非単位元1の逆元は存在しません.同様に,論理積では単位元1の逆元は1ですが,非単位元0の逆元は存在しません.
 
 B={0,1}上の2項演算※
  ※  0  1   (a,b,c,d=0または1)
  0  a  b
  1  c  d
は全部で2^4=16通りあるのですが,結局,単位元とどの元も逆元をもつようなものは,
  ※  0  1     ※  0  1
  0  0  1     0  1  0
  1  1  0     1  0  1
の2つしかないことがわかります.
 
 このうち,
  ※  0  1
  0  0  1
  1  1  0
は2を法とする加法,すなわち,整数には奇数と偶数がありますが,
  ODD=1,EVEN=0
として,加法を定義した
  +  0  1
  0  0  1
  1  1  0
と一致します.この群を記号でZ2とかくことにします.Z2は最も単純な群の例となっています.
 
  ※  0  1
  0  1  0
  1  0  1
はZ2の否定,すなわち,0→1,1→0と置き換えたもので,本質的にZ2と同型です.
 
 以上より,
  「2個の元よりなる群は,すべてZ2と同型である」
とまとめられます.
 
===================================
 
【2】位数3の群
 
 偶数か奇数かは2で割ったときの余りで識別できますが,同様に3で割ったときの余りで分類した数体系を考えます.余りは0,1,2のどれかですから,
  +  0  1  2
  0  0  1  2
  1  1  2  0
  2  2  0  1
のような演算を定義することができるわけです.
 
 これが群Z3ですが,位数3の群は同型のものを除けばZ3しかありません.次に,このことを証明しましょう.
 
 G={e,a,b}とおき,その単位元をeとします.すると演算表は
  ※  e  a  b
  e  e  a  b
  a  a  (1)  (2)
  b  b  (3)  (4)
までは自然に決まりますから,あとは(1),(2)(3),(4)の欄を埋めればよいことになります.
 
 逆元が存在するためには,1つの行(列)には同じ元は現れませんから,(1)にはeかbが入りますが,(1)にe,(2)にbを入れると
  ※  e  a  b
  e  e  a  b
  a  a  e  b
  b  b  (3)  (4)
となって,bの列にbが2回現れてしまいます.
 
 したがって,(1)にはb,(2)にはeが入ります.
  ※  e  a  b
  e  e  a  b
  a  a  b  e
  b  b  (3)  (4)
すると,(3)にはe,(2)にはaが入ることになり,
  ※  e  a  b
  e  e  a  b
  a  a  b  e
  b  b  e  a
となって,演算表は完成です.
 
 このことから1通りしかないことが示されますが,この表で,
  e→0,a→1,b→2
とおけば,Z3と同型になることがわかります.
 
===================================
 
【3】位数4の群
 
 位数2の群,位数3の群はそれぞれ1通りしかないことをみてきましたが,引き続き,位数4の群について調べてみましょう.
 
  ※  e  a  b  c
  e  e  a  b  c
  a  a  (1)  (2)  (3)
  b  b  (4)  (5)  (6)
  c  c  (7)  (8)  (9)
 
 (1)に入るのはeかbかcですが,場合分けして考えると,
  ※  e  a  b  c     ※  e  a  b  c
  e  e  a  b  c     e  e  a  b  c
  a  a  b  c  e     a  a  c  e  b
  b  b  c  e  a     b  b  e  c  a
  c  c  e  a  b     c  c  b  a  e
 
  ※  e  a  b  c     ※  e  a  b  c
  e  e  a  b  c     e  e  a  b  c
  a  a  e  c  b     a  a  e  c  b
  b  b  c  a  e     b  b  c  e  a
  c  c  b  e  a     c  c  b  a  e
の4通りが得られます.
 
 1番目の
  ※  e  a  b  c
  e  e  a  b  c
  a  a  b  c  e
  b  b  c  e  a
  c  c  e  a  b
は元が巡回しているのでZ4,すなわち,
  +  0  1  2  3
  0  0  1  2  3
  1  1  2  3  0
  2  2  3  0  1
  3  3  0  1  2
と同型(e→0,a→1,b→2,c→3).
 
 2番目は
  e→0,a→1,b→3,c→2
3番目は
  e→0,a→2,b→1,c→2
とおけばZ4と同型です.
 
 しかし,4番目の
  ※  e  a  b  c
  e  e  a  b  c
  a  a  e  c  b
  b  b  c  e  a
  c  c  b  a  e
は,どのように名前を付け替えてもZ4と同型にはなりません.
 
 実は4番目は直積Z2×Z2と同型になっているのですが,直積G1×G2とは順序のある組(g1,g2)の全体で与えられる集合で,群G1(演算※1)と群G2(演算※2)のとき,直積上で,演算※が
  (a1,a2)※(b1,b2)=(a1※1b1,a2※2b2)
で定義された群を指します.また,直積の位数については,
  |G1×G2|=|G1||G2|
が成り立ちます.
 
 ここで,
  G1=G2=Z2,※1=※2=(mod2での加法)
とすると,
  (1,0)※(0,1)=(1,1)
  (1,0)※(1,1)=(0,1)
のようになり,直積Z2×Z2の演算表は
  ※   (0,0)  (0,1)  (1,0)  (1,1)
 (0,0)  (0,0)  (0,1)  (1,0)  (1,1)
 (0,1)  (0,1)  (0,0)  (1,1)  (1,0)
 (1,0)  (1,0)  (1,1)  (0,0)  (0,1)
 (1,1)  (1,1)  (1,0)  (0,1)  (0,0)
で表されます.
 
 ここで,
  (0,0)→e,(0,1)→a,(1,0)→b,(1,1)→c
と置き換えれば4番目と一致します.
 
===================================
 
 次に,Z4とZ2×Z2が同型かどうかを調べてみましょう.群Gの元gについて,g^k=eとなる自然数kが存在するとき,kの中で最小のものを元gの位数と呼びます.元の位数と群の位数|G|と紛らわしいので,混同しないで下さい.
 
 すると,Z4(単位元0)
  +  0  1  2  3
  0  0  1  2  3
  1  1  2  3  0
  2  2  3  0  1
  3  3  0  1  2
において,演算はmod4での加法ですから,
  g^(i+1)=g^i※g=g^i+g  (mod4)
より,
  1の位数は4(1+1=2,2+1=3,3+1=0)
  2の位数は2(2+2=0)
  3の位数は4(3+3=2,2+3=1,1+3=0)
  0の位数は1
となります.
 
 一方,Z2×Z2(単位元(0,0))
  ※   (0,0)  (0,1)  (1,0)  (1,1)
 (0,0)  (0,0)  (0,1)  (1,0)  (1,1)
 (0,1)  (0,1)  (0,0)  (1,1)  (1,0)
 (1,0)  (1,0)  (1,1)  (0,0)  (0,1)
 (1,1)  (1,1)  (1,0)  (0,1)  (0,0)
では,
  (0,0)の位数は1
  (0,1)の位数は2((0,1)+(0,1)=(0,0))
  (1,0)の位数は2((1,0)+(1,0)=(0,0))
  (1,1)の位数は2((1,1)+(1,1)=(0,0))
ですから,Z4と同型ではありません.
 
 以上により,
  「位数4の群は,同型であるものを除いて,Z4とZ2×Z2の2つしかない」
ことがわかります.これで位数4までの群はすべて決定されました.
 
===================================
 
【4】位数5の群
 
  ※  e  a  b  c  d
  e  e  a  b  c  d
  a  a  (1)  (2)  (3)  (4)
  b  b  (5)  (6)  (7)  (8)
  c  c  (9) (10) (11) (12)
  d  d (13) (14) (15) (16)
とおくのも,もはや限界でしょう.
 
 そこで,ここでは定理
  「素数位数の群は巡回群である」
を紹介します.前節で,位数4の群Z4の元の位数は1,2,4,位数4の群Z2×Z2の元の位数は1,2であることをみてきましたが,この定理は,有限群において,任意の元の位数はその群の位数の約数であるという事実から得られます.
 
 巡回群の例をあげますが,平面の回転群Gを考えてみましょう.自然数kが与えられたとき,
  θ=2π/k
  ω=[cosθ,−sinθ]
    [sinθ, cosθ]
とおくと,ω^k=1(単位元)ですから
  G={1,ω,ω^2,・・・,ω^(k-1)}
となります.このように,群Gの元が皆一つの生成元<ω>のベキの形で表されるとき,「巡回群」といいます.
 
 このように,位数nの巡回群:Cnは,正n角形の原点を通る1つの軸を中心とした2π/n回転から生成される群と等価と見なすことができるので,SO(2)と絶対値1の複素数のなす乗法群とは同型になります.
 
 また,位数nの巡回群:Cnは,ω=1とおいたmod nの加法群:Znと同型であることも容易に理解されます.したがって,「位数が素数pの群はZpと同型である」ことになり,
  位数5の群は1通り(Z5),
  位数7の群は1通り(Z7),
  位数11の群は1通り(Z11),
  位数pの群は1通り(Zp),
  ・・・・・・・・・・・・・・・
という結果が得られます.
 
 なお,ω^jが生成元となるための条件は
  {1,ω^j,ω^2j,・・・,ω^(k-1)j}
が互いに相異なることですから,生成元の個数はオイラーの関数:φ(k)個となります.
 
 φ(k)は{1,2,・・・k}の中でkと互いに素な自然数の個数として定義されます.たとえば,k=6ならφ(6)=2となり,{1,2,3,4,5,6}のなかで6と互いに素なものは1と5の2つで,生成元はωとω^5となります.
 
===================================
 
【5】位数6の群
 
 既にお気づきのように,位数6が抜け落ちていますが,これも埋めていきましょう.
 
 球面上の運動の有限群は5つの回転群(巡回群,正2面体群,正4面体群,正8面体群,正20面体群)=広義の正多面体群に限ることが知られていますが,位数6の巡回群:C6(正六角形の回転群=Z6と同型)は省略して,位数6の正2面体群:D3について考察してみます.
 
 平面の回転群をそのまま空間の群と見なしたものが巡回群ですが,SO(3)ではその裏返しも存在し,位数kの巡回群(回転運動)とその鏡映sからなる
  {1,ω,ω^2,・・・,ω^(k-1),s,sω,sω^2,・・・,sω^(k-1)}
が正2面体群(位数2k)です.
 
 「正2面体群」とは,正n角形をそれ自身に移す回転全体のなす群であって,重心を通る垂直軸を中心とした回転と対称軸を中心としたπ回転から生成される位数2nの群と幾何学的に考えることができます.この正2面体という奇妙な名前は,2枚の正多角形を貼り合わせたものをつぶれた多面体と見なすことから由来しています.
 
 ここで,1つの正三角形を考えることにします.三角形の中心まわりの角度120°の右回り回転をbとすると,bは3回やると元に戻るので
  b^3=1
また,頂点を通る中心線に関して裏返す作用をaとすると
  a^2=1
と書けるので,位数6の正2面体群は2元<a,b>によって生成される
  {1,b,b^2,a,ab,ab^2}
です.すなわち,位数3の巡回群{1,b,b^2}とその裏返し{a,ab,ab^2}とからなります(回転∪鏡映).
 
 D3の群表を書けば,どの元も各行各列にちょうど1回ずつ登場し,魔法陣のようであることが理解されるでしょう.
 
  ※   1   b   b^2  a   ab  ab^2
  1   1   b   b^2  a   ab  ab^2
  b   b   b^2  1   ab^2 a   ab
  b^2  b^2  1   b   ab  ab^2 a
  a   a   ab  ab^2 1   b   b^2
  ab  ab  ab^2 a   b^2  1   b
  ab^2 ab^2 a   ab  b   b^2  1
 
 2つの生成元a,bが
  a^2=b^3=(ab)^2=1
という関係を満たすことを確かめてほしいのですが,正n角形では一般に,
  a^2=b^n=(ab)^2=1
となり,積abの位数は2なのです.
 
===================================
 
 ところで,アミダクジ(置換行列)
  [1 2 3]
  [3 1 2]
のように,元と元を1対1で置換する写像も群をなします.この群を対称群,その部分群を置換群と呼びます.また,偶置換全体も対称群の部分群になっていて,これを交代群と呼びます.n文字の置換全体がなす群がn次対称行列Snというわけです.その位数|Sn|はn!に等しくなります.
 
 3次対称群S3の6個の元に
  e =[1 2 3]  c1=[1 2 3]  c3=[1 2 3]
     [3 1 2]     [2 3 1]     [3 1 2]
 
  t1=[1 2 3]  t2=[1 2 3]  t3=[1 2 3]
     [1 3 2]     [3 2 1]     [2 1 3]
と名前をつけて,S3の演算表を作ると
  ※    e   c1  c2  t1  t2  t3
  e    e   c1  c2  t1  t2  t3
  c1   c1  c2  e   t3  t1  t2
  c2   c2  e   c1  t2  t3  t1
  t1   t1  t2  t3  e   c1  c2
  t2   t2  t3  t1  c2  e   c1
  t3   t3  t1  t2  c1  c2  e
となり,
  D3      S3
  1   ←→ e
  b   ←→ c1
  b^2  ←→ c2
  a   ←→ t1
  ab  ←→ t2
  ab^2 ←→ t3
と置き換えると,両者は同型であることがわかります.
 
 S3は主対角線に関して非対称ですから,交換法則が成り立たない非可換群で,S3は位数が最小の非可換群として重要な存在となっています.
 
 実は,素数pに対し,位数2pの群は巡回群Z2pか正2面体群Dpと同型であるという定理があります.そこで,証明抜きで結論にはいりますが,位数6の有限群は
  (1)位数6の巡回群Z6(可換群のとき)
  (2)3次対称群S3=D3(非可換群のとき)
のいずれかに同型です.
 
 直積Z2×Z3については検討しませんでしたが,位数は6でしかも可換群ですから,Z2×Z3はZ6と同型になります.位数6の場合と同様に,位数10の群はZ10かD5と同型となります.Z10はZ2×Z5と同型です.
 
===================================
 
 なお,正2面体群は正n角形を自分自身にうつす写像全体をなすわけですが,正3角形に対する正2面体群D3(位数6)はS3と同型,正方形に対する正2面体群D4(位数8)は,S4(位数24)の部分群となっています.
 
 4文字1,2,3,4の置換全体のなす群が4次対称群S4で,その位数は4!=24となりますが,一般に位数nの有限群は,n次対称群Snの部分群と同型になることが知られています.
 
 また,上の演算表から
  ※    e   c1  c2
  e    e   c1  c2
  c1   c1  c2  e
  c2   c2  e   c1
の部分だけを取り出すとZ3と同型ですから,{e,c1,c2}はS3の位数3の部分群,また,
  ※    e   t1
  e    e   t1
  t1   t1  e
だけを取り出すとZ2と同型ですから,{e,t1}はS3の位数2の部分群であることがわかります.
 
 有限群Gの部分群Hに対し,|H|は|G|の約数であるというのが有名なラグランジュの定理です.有限群において,任意の元の位数はその群の位数の約数であるという定理については前述しましたが,このことがラクランジュの定理と密接に関係していることは明らかでしょう.ラグランジュの定理は,たとえば,位数6のS3には位数4や位数5の部分群は存在しないということを教えてくれます.
 
===================================
 
【6】位数8の群,位数9の群,位数12の群,・・・
 
 位数7,10,11の群の群は解決済みなので,位数8,9,12の場合をみていきましょう.
 
 位数4の場合にZ4とZ2×Z2の2つの群が現れましたが,一般に素数pに対し,位数がp^nの可換群Zp^nは,
  Zp^n1×Zp^n2×・・・×Zp^ni  (n1+n2+・・・+ni=n)
のように,位数がpのベキ乗である巡回群Zp^kのいくつかの直積と同型であるという「可換群の基本定理」が知られています.
 
 したがって,位数8=2^3の可換群のうち,同型でないものは
  Z8,Z4×Z2,Z2×Z2×Z2
の3通り,位数16=2^4の可換群は
  Z16,Z8×Z2,Z4×Z4,Z4×Z2×Z2,Z2×Z2×Z2×Z2
の5通り,位数9=3^2の可換群は
  Z9,Z3×Z3
の2通り,位数243=3^5の可換群は
  Z243,Z81×Z3,Z27×Z9,Z27×Z3×Z3,Z9×Z9×Z3,
  Z9×Z3×Z3×Z3×Z3,Z3×Z3×Z3×Z3×Z3
の7通りとなります.
 
 また,位数12=2^2・3の可換群Gは,位数2^2の可換群G1と位数3の可換群G2の直積と同型になり,G1はZ4とZ2×Z2の2通り,G2はZ3の1通りですから,
  Z4×Z3,Z2×Z2×Z3
の2通りで与えられます.Z2×Z3はZ6と,Z4×Z3はZ12と同型になりますから,
  Z12,Z2×Z6
としても同じことです.
 
 異なる素数piに対し,n=p1^n1・p2^n2・・・pk^nkのとき,位数nの巡回群Znは,直積
  Zp1^n1×Zp1^n1×・・・×Zpk^nk,
に分解されるのですが,位数nの可換群・巡回群の構造は,nの素因数分解を反映しているというわけです.
 
===================================
 
 残念ながら,非可換群についての結果はわかりませんでした.たとえば,位数12の群には正4面体群があり,これは4次の交代群:A4と同型で,巡回群C12(Z12)や正2面体群D6とは異なります.また,位数12の非可換群では,D3×Z2なども考えられるところです.
 
 これ以上先に進むためには,取っつきにくい話,たとえば,
(1)群準同型とは群の積を保存
  φ(xy)=φ(x)φ(y)
する写像のことで,さらに全単射のとき群同型と呼ぶ.
(2)その際,
  a^(-1)Ha=H   (Ha=aH)
がGのすべての元aに対して成立するとき,HをGの正規部分群と呼ぶのだが,正規部分群の正体は,群準同型の核にあたる.
などを十分マスターしておく必要がありそうです.
 
 シローの定理により,群Gの位数|G|を割るすべての素数pに対するシローp部分群が複雑に絡み合って,群G全体の構造が決まっているのですが,とはいっても,「群論」は取っつきにくいし,わかったようでいても,いつまでもわからないというのが本音です.
 
 かくいう小生も群・環・体などの書物を読むと,定義がややこしいのに辟易し,個々の公式の運用に埋没してしまいます.そのすべてを会得することは夢のまた夢であって,現実としては,見はてぬ夢として諦めざるを得ないとも思いますが,ともあれ,「群の積を保存するという基準に基づいて,すべての群を分類すること」が群論の究極の目的となっているのです.
 
===================================
 
[補]正多面体群
 
 正多面体の回転を考えると,正4面体(位数12)では4つの頂点の偶置換を引き起こすので4次交代群A4と同型,正8面体(位数24)では対面する面は4組あり,これらの組の置換を引き起こすので4次対称群S4と同型,正20面体(位数60)では30個の辺を5組に分ける偶置換として作用するので5次交代群A5と同型になります.正多面体の回転群は3次の特殊直交群SO(3)の有限部分群です.
 
 3次元空間の回転群には,この他に2種類の有限部分群,正n角錐のもつ巡回群Cnと正n角柱のもつ二面体群Dnがあります.クラインは,平面内での正n角形を,球の赤道に内接する正n角形の各頂点と北極・南極を結んでできる多面体を上下から赤道面に押しつぶしてできる体積が0の正凸面体と考え,この群を正2面体群と命名しました.
 
 2面体群とは,正n角形を回転してもとの正n角形に重ねる巡回群に対し,折り返しも用いてもとの正n角形に重ねる変換すべてを含む群となります.すなわち,巡回群Cnは正n角錐のもつ回転対称性であり,正二面体群Dnはと正n角柱のもつ回転対称性であって,桜の花はC5,雪の結晶はD6というわけです.
 
 以上をまとめると,SO(3)の有限回転群は,
  (1)巡回群(Cn:位数n)
  (2)正2面体群(Dn:位数2n)
  (3)4次交代群(A4:位数12)←→正4面体群と同型
  (4)4次対称群(S4:位数24)←→正6(8)面体群と同型
  (5)5次交代群(A5:位数60)←→正12(20)面体群と同型
のいずれかであることになります.
 
===================================