2020.01.22
# 離散数学 # ガロア # 群論

「ガロア理論」を本気で学ぶための、1時間でわかる離散数学の基礎

一歩ずつ進めば必ず理解できます!
芳沢 光雄 プロフィール

離散数学の「デザイン」とは何か?

離散数学で扱うデザインは、絵のデザインとは異なって、\(v\)個の元からなる集合\(\Omega\)と、\(\Omega\)の\(k\)個の元から成るいくつかの部分集合(の集合)\(B\)との組\( \left(\Omega, B\right) \)がなす構造で、次の条件を満たすとき\(t-\left(v, k, \lambda\right) \)デザインという。

\(\Omega\)の相異なる任意の\(t\)個の元\( \alpha_1, \alpha_2, \cdots, \alpha_t\)に対し,それらを含む\(B\)の元はちょうど\( \lambda \)個ある。

デザインのイメージはつかみ難い面があるので、具体例として次の\( 2-\left(16,4,1\right) \)デザインを挙げよう。

16人麻雀大会
16人の大人の、5日間にわたる麻雀大会を、次の条件を満たすように計画できる。
(i)毎日4人ずつのグループを4つ作って、16人全員が麻雀ゲームをする。
(ii)16人のうちのどの2人に対しても、その2人を含む麻雀ゲームのグループは、5日間を通してちょうど1つだけ存在する。

 1日目:{ 1, 2, 3, 4 } , { 5, 6, 7, 8 } , { 9, 10, 11, 12 } , { 13, 14, 15, 16 }
 2日目:{ 1, 5, 9, 13 } , { 2, 6, 10, 14 } , { 3, 7, 11, 15 } , { 4, 8, 12, 16 }
 3日目:{ 1, 6, 11, 16 } , { 2, 5, 12, 15 } , { 3, 8, 9, 14 } , { 4, 7, 10, 13 }
 4日目:{ 1, 8, 10, 15 } , { 2, 7, 9, 16 } , { 3, 6, 12, 13 } , { 4, 5, 11, 14 }
 5日目:{ 1, 7, 12, 14 } , { 2, 8, 11, 13 } , { 3, 5, 10, 16 } , { 4, 6, 9, 15 }

この例では、1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16から成る集合を\(\Omega\)とし、\(B\)は「{ }」で囲まれた\(\Omega\)の部分集合20個からなる集合である。

 

上の\( 2-\left(16,4,1\right) \)デザインは、有限幾何学の世界では「位数4のアフィン平面」と呼ばれるものである。本稿の要となるものは、有限幾何学の世界では「位数2の射影平面」と呼ばれる次の\( 2-\left(7,3,1\right) \)デザインである(下図参照)。

\[\Omega = \{1, 2, 3, 4, 5, 6, 7\} \\ B=\{l_1, l_2, l_3, l_4, l_5, l_6, l_7 \} \\ l_1=\{1,2,3\}, \ l_2=\{3,4,5\}, \ l_3=\{5,6,1\}, \ l_4=\{2,4,6\},\\ l_5=\{1,7,4\}, \ l_6=\{2,7,5\}, l_7=\{3,7,6\} \]

位数2の射影平面

\( t-\left(v, k, \lambda\right) \)デザイン\( \left(\Omega, B\right) \)の自己同型写像とは、グラフの頂点集合上の置換で、\(B\)の各元を\(B\)の元に移すものである。また、デザインの自己同型群とは、デザインの自己同型写像全体がつくる群のことである(演算は写像の合成)。

たとえば、図で示した\( 2-\left(7,3,1\right) \)デザインに対しては、 \[ f = \left( \begin{array}{cc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 6 & 5 & 4 & 3 & 2 & 7 \end{array} \right) \] という\(\Omega\)上の置換は自己同型写像になる。実際\(f\)は、\( l_1\)は\( l_3\)に移し、\( l_2\)は\( l_2\)に移し、\( l_3\)は\( l_1\)に移し、\( l_4\)は\( l_4\)に移し、\( l_5\)は\( l_5\)に移し、\( l_6\)は\( l_7\)に移し、\( l_7\)は\( l_6\)に移す。

実は、\( 2-\left(7,3,1\right) \)デザインの自己同型群は、元の個数が168の群になる。この群は、群論の世界では「可換群でない単純群」という性質をもつ。

「単純群」は整数における素数のようなもの

ここで、単純群という言葉の説明をしておこう。まず、\( H\)が群\( G\)の部分群であるとき、次の条件(*)を満たすならば、\( H\)を\( G\)の正規部分群という。

(*):\( G\)のすべての元\( g\)に対し、\( g^{-1} Hg=H\)が成立する。
   ただし、\(g^{-1} Hg=\{g^{-1} hg\)全体\(|h\)は\(H\)の元\(\}\)

さらに、群\( G\)の正規部分群が\( G\)と\( \{e\)(単位元)\( \}\)しか存在しないとき、\( G\)を単純群という。ちなみに単純群は、整数の世界に例えると素数のようなものだと言えよう。

次に、対称群という言葉と置換群という言葉を説明する。

一般に集合\(\Omega\)上の対称群とは、\(\Omega\)上の置換全部からなる群のことであり、記法として\(S^\Omega\)で表す。ここで\(\Omega\)の元の個数が\(n\)ならば、\(S^\Omega\)の元の個数は\(n!\) ( \(n\) の階乗)であり、\(S^\Omega\)を\(n\)次対称群ともいい、\(S_n\)で表す。

また、\(S^\Omega\)の部分群を一般に\(\Omega\)上の置換群という。ちなみに、上で図で示した\( 2-(7,3,1) \)デザインの自己同型群は、元の個数が168個の \[ \Omega=\{1,2,3,4,5,6,7\} \] 上の置換群である。

関連記事