部分群分解を整備する

正規部分群分解は一応動作するようになったと見てよいと思う.次は,部分群分解だ.これは素群を含むすべての部分群を列挙する検定である.現行では極小部分群の抽出→極大部分群の抽出→部分群の合成のような手順になっているが,極大部分群の抽出の部分は一時的に止めて動作確認することにする.極小部分群の抽出は「生成元のすべてのべきを含む部分群を生成する方法」で行っている.これはよく言われる「軌道」というものではないだろうか?いや,少しというかかなり違うように思われる.これは後で調べることにする.極小部分群の抽出にはバージョンの分岐はない.使われているのは,部分群検定5~7だけだ.

Q8の部分群分解で停止する.(Count != 部分群数)の不一致が起きている.Count = 4で部分群数は5だ.Count=1で開始しているのに一致しないというのはおかしい.素群数=5,極大部分群数=0でi<5のときだけカウントされている.検定7の冒頭では素群数と部分群数は一致している(=5)この下図には{e}が含まれるものと思われる.部分集合には台集合が5個登録されている.部分集合[0]={e}である.

■群Q8は5個の真部分群を持つ■ 位数2X1 位数4X3と表示されているが,素群は3個しかダンプされていない.どうもi=3でループからブレークしているようだ.いや,ループ回数が 部分群数 – 1となっている.=は入っていないので,これは i < 部分群数でなくてはならないだろう.⇒多分これで解決したはずだ.

■群Q8は5個の真部分群を持つ■ 位数2X1 位数4X3という表示になっているが,真部分群には単位群を含まないことになっているようなので,1つマイナスした数字を出すことにする.

部分群のダンプの意味がよくわからない.

部分群のダンプ:Q8 N=8 素群数=5 部分群数=5 #は部分群の位数
[0] 〈1〉{1} #1
[1] 〈〉{1,-1} #2
[2] 〈〉{1,i,-1,-i} #4
[3] 〈〉{1,j,-1,-j} #4
[4] 〈〉{1,k,-1,-k} #4

〈〉で何を表そうとしているのだろう?意味不明だ.⇒部分群生成元[i]というのを表示している.極大部分群ではこの配列に※を格納している.合併群の場合には2つの部分群の生成元を連結した値が入る.素群では何も入れていない.置換リストを使っている場合には,生成元の置換が入るようになっているが,置換リストを使っていないため空になっている.極小部分群を生成したときのseedを格納するようにした.以下のようになった.これならわかる.

(1) 部分群 [1]⇒〈-1〉{1,-1} は位数2のQ8の素群である
(2) 部分群 [2]⇒〈i〉{1,i,-1,-i} は位数4のQ8の素群である
(3) 部分群 [3]⇒〈j〉{1,j,-1,-j} は位数4のQ8の素群である
(4) 部分群 [4]⇒〈k〉{1,k,-1,-k} は位数4のQ8の素群である

部分群のダンプ:Q8 N=8 素群数=5 部分群数=5 #は部分群の位数
[0] 〈1〉{1} #1
[1] 〈-1〉{1,-1} #2
[2] 〈i〉{1,i,-1,-i} #4
[3] 〈j〉{1,j,-1,-j} #4
[4] 〈k〉{1,k,-1,-k} #

A2, A3, A4, A5, S2, S3, S4, S5まで分解できた.内訳まではわからないが,下記URLにはこれらの部分群の個数のリストがある.

http://iitakashigeru.math-academy.net/seminar07/nakayamaohp.pdf

S5の分解では5分54秒掛かっている.約6分だ.上のサイトではPrologで11.46秒で計算完了している!以前はもう少し速かったような気もするのだが… 2023/10/29には部分群検定で4秒を切ったと書いてある.これは極小部分群の切り出しに限定されたものかもしれないが… 2023/10/25には,部分群検定6で6分23秒とある.それに比較すれば多少は速くなっているのだが… 部分群検定3に戻って確認してみる必要がある.⇒部分群検定3というののは残っていない.これは記事にもあるように現在は「極小部分群の抽出」とリネームされている.つまり,サブルーチンの扱いだ.極小部分群の抽出は現行の検定7でも使っているので,それ以上のことはできない.

部分群のリストをダンプするとき,可換/非可換と正規部分群の別を表示できるようにしたい.群の検査の自己同型検定は正規部分群検定になっていないのだろうか?正規部分群検定の中では,「共役変換検定」を使って正規であるか否かを判定している.共役変換検定という処理は準同型というクラスの関数で,準同型はA,Bという2つの群を抱えている.この中でB群から参照されているのはNだけだ.多分,Aが写像の定義域でBが値域になっているはずだが,値域の台集合は群から直接取っているのだろうか?map.map1がそれに該当するものと思われる.

写像 map = new 写像(G.N, G.台集合, G.台集合);

とあるが,これは

写像 map = new 写像(G.N, 台集合, G.台集合);

の誤りではないだろうか?写像というクラスでは配列を2つ持っているが,長さが同じことを仮定しているのではないだろうか?写像の検査という機能もある.これを見ておこう.写像の検査は準同型クラスのメソッドで群AとBを持ち,map1とmap2という2つの元集合を持っているが,これらのサイズは同一で,群の台集合の部分集合という位置付けと思われる.つまり,基本的にmap1→map2は全単射になっているのではないか?写像の検査で実施しているのは基本的にmap1/map2と群A/Bの台集合の突き合わせ検査である.つまり,記載漏れや重複がないことを確認しているに留まる.

共役変換検定の動作を確認してみよう.A4は位数4の正規部分群を1個持っているが,完全な検査になっているかどうか?Aの元集合としてはAの台集合が使われているので,抜け目はないように思われる.map1とmap2には同じもの(Bの台集合)が入っている.gxg^-1でg∈A,gxg^-1∈Bとなっているので,論理的には問題なさそうだ.ただし,これは写像や準同型などを持ち出さなくても群クラスの中で処理できたのいではないか?⇒書換えてみよう.⇒対処した.問題なさそうだ.

ここで,群の生成時,対称群と交代群では乗積表を使わない方式に統合しておくことにしよう.台集合は別途指定できるので,特に問題ないと思う.現行では「置換リストを使う」方式でS5まで扱えているので,とりあえず限界まで試してみることにする.⇒A3~A5, S2~S5までは実装した.VとQ8は残った.これらは対称群でも交代群でもないので,自動的には生成できない.部分群として取り出すという手段はあるが…

検定7で極大部分群の抽出3を復活させたが,S5でやけに時間が掛かっている.どうも,極大部分群を取ったことで余分なコストが掛かるようになってしまったように思われる.極大部分群検定は部分群検定から切り離しておいた方が無難かもしれない.古い論理の復活ということも考えられるかも知れない.極大部分群検定に入っている「結び目をほどく」がコスト要因になっていると考えられる.というか,S5はこの方法では極大部分群を取り出せなかったのではなかったろうか?なにかやり損なってしまった可能性もある.2023/11/06には「S5では1分以上掛かっている模様」とあるので,これほどには掛かっていなかった.

交代群ではまったく極大部分群を取れない.対称群ではS4までは取れるが,S5では時間が掛かるようになっている.いや,2023/11/06のログでは「S5の極大部分群で2秒」という書き込みもある.この2秒というのは,メモリを確保するまでの時間を除いた実処理時間と思われる.確かに,2秒台で終わっている.それまでの助走に時間を食われている.開発機の実装メモリは16GBだ.これを増設すればもう少し速くなる可能性はあるような気がするが… 機種名はDiginnosだ.⇒16GBというのは現在の標準だ.32GB搭載はハイエンドクラスにしか見られない.

正規部分群検定が動作していない

どうも正規部分群検定は動作していないように思われる.少なくともS5は正規部分群を持っているはずなのだが… 論理をいじっているので,正規部分群検定が止まっているようだ.共役変換検定というのをやって結果が正規のときのみ検定を実行するようになっているが,正規がfalseで固定されている.A4で位数4×3の正規部分群があると出た.これは正しいか?⇒間違っている.A4の位数4の部分群はV={e,(12)(34),(13)(24),(14)(23)})しかない.出力では,{a,d,l,i},{a,i,d,l},{a,l,i,d}の3つとなっているが,これらは位相同型なのではないか?部分群検定にはまだ位相同型検査が入っていないのではないか?

HasSameElementsは部分群検定6, 7 の辺りで導入された模様で,極小部分群の抽出,極大部分群の抽出で定着したものと思われる.この際,追番の付いていない部分群検定は正規部分群検定として系列から切り離した方がよいと思う.一度バックアップを取ってから始めよう.正規部分群検定を再帰実行することに意味があるだろうか?コードは残っているのだが,現状では使われていない.正規部分群の中に正規部分群が入っていることはあるので,意味がないということもないが… ⇒コードだけは残しておいてよいのではないか?いや,現状でもそうなっている.

正規部分群数とダンプの内容が合わない.群Q8は3個の非自明な正規部分群を持っている■というとき,位数2X1 位数4X3と表示される.位数2X1という正規部分群は存在していない.正規部分群抽出の過程で正規でない部分群も生成されている.これを登録して,部分群数をカウントアップしている.正規部分群の取り出しでは正規部分群だけを登録するようにした方がよい.⇒正規部分群だけを登録するようにしてみたが,今度は◎群Q8は4個の非自明な正規部分群を持っている 位数2X1 位数4X3のような表示になった.これは◎群Q8-2という部分群が持っている正規部分群位数2X1がどこかで足しこまれているためと思われる.いや,表示の問題だったようだ.これで正しくなった.

《 正規部分群分解 Q8 》
★★群Q8-1は位数2の正規部分群である★★ {1,-1}
★★群Q8-2は位数4の正規部分群である★★ {1,i,-1,-i}
  ★★群Q8-2-2は位数2の正規部分群である★★ {1,-1}
  ◎群Q8-2は1個の非自明な正規部分群を持っている 位数2X1
★★群Q8-4は位数4の正規部分群である★★ {1,j,-1,-j}
  ★★群Q8-4-2は位数2の正規部分群である★★ {1,-1}
  ◎群Q8-4は1個の非自明な正規部分群を持っている 位数2X1
★★群Q8-6は位数4の正規部分群である★★ {1,k,-1,-k}
  ★★群Q8-6-2は位数2の正規部分群である★★ {1,-1}
  ◎群Q8-6は1個の非自明な正規部分群を持っている 位数2X1
◎群Q8は4個の非自明な正規部分群を持っている 位数2X1 位数4X3

群の検査の中に群が可換であるか否かの判定を入れたい.どうすればよいか?結合法則の検査に組み込めばよいのではないか?⇒実装した.Q8は非可換群だが,A4が非可換になってしまう.これはかなりおかしい.どこかで間違えている可能性がある.いや,間違っていない.A4, S4, A5などはすべて非可換群だ.S3は位数最小の非可換群である.つまり,n≧3のSnはすべて非可換群である.言い換えれば,S2を除くすべての対称群は非可換である.n≠1ならGLn(R)は非可換群である.「可換群の任意の部分群は正規部分群である」また,「指数が最小素因子なら正規部分群である」とも(多分逆は成立しない).

https://www.osaka-kyoiku.ac.jp/~hiraki/L03/Qa.htm

上記リンクには

(1) G が 可換群ならばその任意の部分群は正規部分群である。◯
(2) G が 非可換群ならばその任意の部分群も非可換群である。X

とある.これは本当だろうか?(1)は間違いないとして,(2)を明示しているところは(ここの他には)見当たらない.また,以下もアリアドネの結果と一致しない.

https://www.osaka-kyoiku.ac.jp/~hiraki/L07/D2qs1.htm

(1) 4 次の対称群 S4 には全部で4つの正規部分群が存在する。◯
(2) 5 次の対称群 S5 には全部で5つの正規部分群が存在する。X

S4の正規部分群は:{e}, {e,(12)(34),(13)(24),(14)(23)}, A_4, S_4.これには自明な部分群2が含まれるので,我々の結果と一致している.つまり,「(1) 4 次の対称群 S4 には全部で4つの正規部分群が存在する」は正しい.「S5 の正規部分群は{e}、A4、S5、の3つである」つまり,S5の非自明な正規部分群はA4のみである.従って,『(2) 5 次の対称群 S5 には全部で5つの正規部分群が存在する。』は間違っている.このリンクは問題集になっているので,Yes, Noで答えるようになっているのかもしれないが,回答は公開されていない.

これまで構築した論理の動作を確認する

ある程度は整理が付いたが,先に進む前にこれまで構築した論理の動作確認を行っておく必要がある.

  1. 極大部分群の抽出機能は動作しているか?→極大部分群分解という関数がその機能に当たり,現在は「テスト」ボタンで動作確認している⇒この機能は興味深いので独立のボタンに割り当てておくことにしよう.⇒A4, A5の極大部分群は取れない⇒自乗リストをダンプする ⇒ 極大部分群分解はおおむね動作している.時間は計測していないが,S5では1分以上掛かっている模様.
  2. 任意の群を部分群に分解できているか?
  3. 正規部分群の抽出機能は動作しているか?
  4. 極小な部分群は素群であると言えるか?
  5. それぞれの処理の時間コストを計測する ⇒S5 の極大部分群で2秒
  6. 群の検査機能はおおむね動作している ⇒ 群の検査の中で自乗リストを生成してもよい,また自己同型検査も復活させてもよいのではないか?⇒自己同型検定は「置換リストを使わない」オプションか,N<5の場合しか実行しないようになっている.現行版は「置換リストを使う」になっている.置換リストは,①置換のコンストラクタ,②全単射の生成,③置換の生成で構築されている.これは群を生成するときに,置換から構成している場合に限定される⇒「置換リストを使わない」というのは意味があいまいなので,「置換リストを使う」に変えた方がよい.

位数3のA3の極大部分群がA3になっている.e以外の2つの元 1, 2 は冪等元なので,削減可能なノードは存在しない.⇒二乗根となる元が存在しないとき,つまり除去される元がないときは無動作とする.

S5の極大部分群分解の時間を計測してみた,2秒くらいしか掛かっていない.S5を生成してコピーするまでの時間が掛かっているのではないだろうか?いや,それも腑に落ちない.S5を選択した時点でForm1.GにはS5が入っているはずだ.あるいは,そこでGCが発生しているのかもしれない.いずれにしても反復したときには余分な時間は掛かっていないので,正味時間は2秒と見てよいと思う.これは十分高速と言ってよいと思う.⇒メモリの使用量が急速に増加しているのが原因のようだ.

ドロップダウンリストで群名を指定できる

二乗グラフを用いた極大部分群の抽出には成功しているが,適用範囲は限定的であることがわかった.つまり,除去リストと部分群のサイズが同じであるとすると,部分群は|G|/2でなくてはならず,|H|=|G|/2となるのはHが正規部分群である場合に限られるので群Gは指数2の正規部分群を持つものに限定される.おそらく対称群Snはこの条件を満たすものと思われるが,Anの場合は全滅だ.A5もA4も解けない.

あちこちいじって既成のコードが動かなくなっているので,まず,これを補修してツールとして使えるように再編成しておこう.できれば,群の型などを指定すれば自動的に群が生成できるようになるとさらによいのだが… ⇒ドロップダウンリストで群名を指定できるようにした.大分まとまってきたが,まだあちこちやりかけの状態になっている.

極大部分群の生成に成功した!

中々埒が明かない.最後の切り札として「べき除リスト」というのを作ってみることにする.べき除リストはべき乗リストの逆リストで,x^k=yのとき,y→xのようにリスティングするものだ.y→x, z なら,yを登録解除するときには同時にxとzも削除される.x^2=e のときは,e→xとなるが,eを削除すると,連鎖してすべての要素が削除されるようになると考えられる.このリストはできればソートして,要素数が少ないものから逐次削除するようにするというのが作りとしては望ましい.これができると,「極大部分群」が文字通り最小コストで生成できる可能性がある.ともかく,やってみることにしよう.

ロジックは一応書いてみたが,どうもこれは反対ではないかという気がしてきた.必要なのは「べき除リスト」ではなく「べき乗リスト」ではないか?というか,構築すべきは,単位元eを根とする生成ツリーではないかと思う.つまり,「1」を根とする木構造だ.もし,このようなものができれば,部分木の生成は葉先から枝刈りしてゆく操作となる.葉を削除してもその上のノードをカットする訳ではないから,このリストは削除の順序を決めるためにのみ用いられるものになるだろう.つまり,優先削除リストだ.隣接リストの逆リストになるのではないか?

これはx^2=yのとき,x→yを記入するためのものであり,x→yは単射であるから,単純な一次元配列でよいのではないか?しかし,この表から読み取りたいのは,むしろ子ノードをいくつ持つかということなので,少なくともその情報が読み取れるようになっていなくてはならない.⇒生成してみた.これで見ると参照カウントがゼロとなっているノードには以下がある.1, 2, 5, 6, 9, 10, 13, 14, 17, 18, 21, 22, 24の14個だ.これが優先的に削除してよいノードの候補と言える.

これはストレートに位数12の極大部分群の逆リストになっている.これが位数8の極大部分群になると,半数が葉ノードだ.これはとても正確なリストになっているので,最初に最大限の枝刈りを実行し,それから削除数を減らしてゆくという方法で達成できそうだ.まず,ともかくこれから位数12の極大部分群が取り出せることを確認してみよう.⇒そのものずばり,位数12の極大部分群が生成できた!

極大部分群分解:S4の極大部分群 →
1, 2, 5, 6, 9, 10, 13, 14, 17, 18, 21, 22,
◎S4の極大部分群<再構成>は位数12の群である:{e,3,4,7,8,11,12,15,16,19,20,23}

群S4の極大部分群<再構成>の台集合 ={e,3,4,7,8,11,12,15,16,19,20,23}
e→     e, 3, 4, 7, 8, 11, 12, 15, 16, 19, 20, 23,
3→     3, 4, e, 11, 7, 8, 15, 16, 12, 23, 19, 20,
4→     4, e, 3, 8, 11, 7, 16, 12, 15, 20, 23, 19,
7→     7, 12, 19, e, 15, 20, 3, 8, 23, 4, 11, 16,
8→     8, 16, 20, 4, 12, 23, e, 11, 19, 3, 7, 15,
11→    11, 15, 23, 3, 16, 19, 4, 7, 20, e, 8, 12,
12→    12, 19, 7, 20, e, 15, 8, 23, 3, 16, 4, 11,
15→    15, 23, 11, 19, 3, 16, 7, 20, 4, 12, e, 8,
16→    16, 20, 8, 23, 4, 12, 11, 19, e, 15, 3, 7,
19→    19, 7, 12, 15, 20, e, 23, 3, 8, 11, 16, 4,
20→    20, 8, 16, 12, 23, 4, 19, e, 11, 7, 15, 3,
23→    23, 11, 15, 16, 19, 3, 20, 4, 7, 8, 12, e,

極大部分分解の反復テストができない.マウスイベントが取れていない.⇒リブートして動作するようになった.不良の原因は不明.⇒再発した.カーソルの移動はできるが,マウスイベントが入らない.開発環境だけでなく,エディタなどでも動作不良が起きている.タスクバーの上でのクリックは有効だが,それ以外では入らない.かなり具合が悪い.どう対処すればよいか?タスクマネージャだけは使える.アプリを強制終了したら動作するようになった.アリアドネの糸巻きはコンソールを開いているのでその辺りで動作不良が起きているのかもしれない.

極大部分群の生成に手こずっている

極大部分群の生成に手こずっている.登録解除でブランクの積を持つノードの一部を登録解除することで一部の極大部分群が生成可能であることは確認できているが,生成できない極大群もある.ループを二重にしてこれを実行すると今度は乗積表が潰れてしまう.中々うまくゆかないので,最後の手段として「結び目をほどく」という再帰関数を作り,総当りを試みた.この方法はものすごく時間がかかる上に極小な部分群まで拾い出してしまう.しかも,答えも間違っている.