ゼルコバの木テント村

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

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

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

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

二乗グラフを用いた極大部分群の抽出には成功しているが，適用範囲は限定的であることがわかった．つまり，除去リストと部分群のサイズが同じであるとすると，部分群は|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を根とする生成ツリーではないかと思う．つまり，「１」を根とする木構造だ．もし，このようなものができれば，部分木の生成は葉先から枝刈りしてゆく操作となる．葉を削除してもその上のノードをカットする訳ではないから，このリストは削除の順序を決めるためにのみ用いられるものになるだろう．つまり，優先削除リストだ．隣接リストの逆リストになるのではないか？

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

これはストレートに位数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,

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

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

極大部分群の抽出は一応組み込み完了しているが，かなり見当違いのことをやっている感がある．登録解除という再帰関数でノード１個を群から除去しているが，やり過ぎになっている．⇒ある程度動くようになってきたが，まだ完全ではない．S4の場合，素群が17個，合成群が11個，単位群1で合計29個の真部分群を持っているのに対し，

▲追加登録で配列レンジオーバーが起きる．追加登録の中でG.Nをインクリメントしているためだ．しかし，Gの台集合や乗積表は上位のG1のそれらを引き継いでいるはずなので，サイズ的にはカバーできるはずなのだが… ⇒ミスがあったので対処した．

やられてしまった！Googleにアクセスすると以下のような警告が出る．

Googleをアンインストールしても状況は変わりない（アンインストールしても自動的に再インストールされる）．「更新」を実行してみる．これでも同じならスマホではGoogleが使えないことになる．（カスペルスキーで完全スキャンを実行してみたが，ウィルスは検出できなかった．カスペルスキーで検出できないとすればもはやこのウィルスを駆除する手段はない）⇒やはり同じだ．Googleかないし，カスペルスキーに問い合わせるしかない… しかし，そんなことにかまっている時間も惜しい…

見た限り，警告が出されて，Googleを開くことができないだけなので，しばらく放置することにする．検索は他のPCで実行することもできるし，Chromeはスマホでも問題なく開ける．

Dドライブが満杯になってしまった．100GBあるのだが，プロジェクトフォルダが１個で１GB使っているのですぐに満杯になってしまう．.vsが容量のほとんどを使っている．これは外に出した方がよい．Cドライブに置いてもよいのではないだろうか？あるいは，個人フォルダに置くことも考えられる．⇒.vsをCドライブに移動し，ツール→オプション→C/C++→詳細設定→IntelliSenseで「常にフォールバック一を仕様」とTrueとし，フォールバック位置をC:\.vsに変更した．ここまではよいのだが，実行しようとすると，以下のエラーになってしまう．

どうもよくわからない．ipchというフォルダだけ付け替えることが必要なのだろうか？とりあえず，戻してみよう．今度は起動時にC:\.vsを使うと適切だというプロンプトが出た．多分これでいけるようになるのではないかと思う．⇒ipchフォルダを削除しても大丈夫かどうか確認しておこう．ipchフォルダを削除したら，今度はBrowse.VC.dbを格納する安全な場所が見つかったという報告が出た．このファイルは53MBでそれほど大きくはないが，これも削除してみよう．⇒これでソリューションのサイズは88MBまで縮小した．

S5の部分群分解で現在の出力は，■群S5は155個の真部分群を持つ■ 位数2X25 位数3X10 位数4X35 位数5X6 位数6X30 位数8X15 位数10X6 位数12X15 位数20X6 位数24X5 位数60X1，経過時間=0:4:5.612 同一と認められた部分群=1084 Z=0　経過時間は４分まで短縮された．冗長な処理のカットがある程度効いている．新部分群数は155でこれには単位群を含み，全体群S5は含まれない．同一部分群1084というのは位数60の部分群のことで，全体ではもっとずっと大きな数(3268)になる．

現行方式ではおそらくこれくらいが限度なのではないかと思う．ここで少し方角を変えて，極大部分群というのを抽出してみたい．検定3では極小な部分群を抽出しているが，この処理ではループを１回回っているだけなので，ほとんどあっという間に終わっている．同様のことが極大部分群でも実現できれば．大きなメリットがある．実行時間には大きい位数の部分群の抽出で相当なロスタイムが出ているので，極大な部分群のセットが取り出せれば，その部分をカットすることでかなりの効率の向上を望むことができるだろう．

部分群検定3というのは現行では極小部分群の抽出に特化しているので，リネームしておくことにしよう．極小部分群の抽出とした．この関数は別の検定でも使われているので，その用法・用途に関しては後で点検することにして先に進もう．極小部分群の抽出では正規部分群は扱わないので，それに関係するような論理を削除して少し整理しておこう．⇒リリース版では4秒を切った．これなら１秒台にもリーチが掛かりそうだ．

どこか壊してしまったのだろうか？カウントが合わなくなった．⇒関数追加登録で正規部分群のフラグを見ていた．#154で位数2の素郡というのを表示した後，検定完了までに相当なブランクがある．この部分をカットできればおそらく半分の時間で完了できるだろう．

現行論理では素郡の合併時に不足するノードがあれば自動的に補充するようになっているが，もしかすると補充なしで充足している組み合わせが存在している可能性がある．その辺りを確認しておこう．⇒確かにそのようだ．N1+N2とG2.Nを比較するとある程度把握できる（N1とN2に元々重複が存在する場合があり得るので必ずしも正確な数字ではない）．現在の検定6の仕様は大幅に改訂する必要があるような気がする．

アルゴリズムを変更して，素郡の合併だけで群が生成可能であるか否かを見ることにしたい．ただし，枝の追加は不可避と考えられるので，認めることにする．既存関数に部分群の生成というのがある．以前はこの関数では実際に部分群を生成していたのだが，現行版では検査をするだけの作りになっている．部分群検定4ではこの関数を使って検定を実施している．また，部分群複合関数の中でもこの関数が呼ばれている．部分群検定5はこの部分群複合が基本関数となっている．

検定4，検定5でも部分群分解はできたはずだが，廃止されたのは時間が掛かり過ぎるという理由からだ．（検定4ではすべての部分群を列挙できなかったかもしれない…）その意味では回収したとしても単なる手戻りになってしまう可能性がある．確かに，今のところもっとも効率的なアルゴリズムは検定6であり，そこからの後退は許されない．現行の検定6では積極的に部分群を構成しているため作業が進むところが利点だ．

部分群検定3は検定5と6の前処理として使われる．これは元のべきから部分群を生成する手続きで，重複を弾くために同一元集合検査を実施している．⇒現行論理，つまり検定6のままで部分群を実際に生成する前に部分群の元集合の検査を実施すればよいのではないか？部分群の生成という関数名は誤解され易いので，元集合の検査とリネームしておこう．どうも，どこかでミスっているのだろうか？元集合の合併を実行後，元集合の検査を通すと100%失格しているのだが，事後に追加ゼロ検査を実施すると，７７７件もヒットする．これはどういうことだろう？

大分整ってきたのではないかと思う．表示でまだ不揃いな点がある．部分群のダンプでは〈(),()〉のような表記になっているが，検定時には〈3〉群〈(24)〉のように表記している行と，　群〈5,12〉のような表記が入り混じっている．⇒群で始まるときには，〈2, 5〉のような表記を標準とする．その後に，詳細として〈(14)(23)〉のような表記を置くのは任意とする．部分群のダンプでは，登録された情報からは群〈5,12〉のような数字を取り出すことができない．部分群生成元には置換の積の形式の情報しか格納されないからだ．まぁ，これは仕方ないだろう．⇒部分群のダンプと検定時出力がまったく一致しない．

これはかなりおかしい．そもそもカウントが合っていない．部分群のダンプの方が１つ少ない．部分群のダンプ：S4 N=24 素群数=24 部分群数=16　というものおかしい．素群数＜部分群数のはずだ．部分群検定3の出口では部分群数=16を素群数に転記しているだけだ．素群数はこの場所以外では更新されない．プリント文にミスがあった．「カウントが合っていない」というのは，部分群のダンプは０発進，検定時出力は１発進になっているためだ．どちらかに統一する必要がある．分かり易いのはリストに単位群を追加することではないだろうか？そうすれば，インデックスを直接表示できる．

ただし，この場合一つだけ問題がある．単位群を追加するとすれば群全体も部分群として登録しないと数が合わなくなってくる．これまでは「自明の部分群を除く」と説明してきたが，「自明の部分群のうち単位群を含む」ではやや苦しい．一つの釈明として「真部分群」という言い方をしているので，これなら群全体を除外しても差し支えないと言えるかもしれない．それが最適解であるような気がする．全体群を生成する素群集合というのも知りたいのだが，その計算をしていると処理時間が無闇に長くなってしまうという弊害がある．⇒部分集合と部分群生成元の先頭に単位元を入れた．

部分群のダンプと検定時出力がまった一致しない．なぜだろう？事後に書き直しなどしていないはずなのだが… いや，勘違いしていた．検定時のダンプは部分群リスト順になっている訳ではない．実際，終盤になってから素群が現れることもある．

部分群検定のアルゴリズムを書換えて部分群検定6とした．検定6では素群リストをベースにその「積」を計算し，必要なノードを補充して合成群を生成→部分群リストに追加→検定の自動延長→部分群の追加がなくなるまでこれを反復という動作になっている．A5はほぼ１５秒程度で完了するが，S5では１５分掛かっている．A5の十倍だ．S5の部分群でもっとも大きいのは位数60のA5だが，この素性を見ておこう．

(32)〈3,22〉群：{e,3,4,30,48,51,89,42,116,115,34,71,73,77,63,46,108,111,112,37,93,52,74,38, 41,85,100,68,67,99,45,33,64,96,90,94,60,12,8,7,11,19,23,20,15,16,78,56,55,59, 103,107,104,81,82,26,25,29,119,86,}は位数60のS5の合成群である

A5の生成元は置換#3と#22で，置換リストで見ると，

置換リスト(3) →        {1,2,4,5,3,}  →        (3 4 5)
置換リスト(22) →       {1,5,4,2,3,}  →        (2 5 3 4)

FKさんのコメントによると，A5の生成元は[[(2,4),(3,5)], [(1,2,5)]]のようになっている．この違いはどこから出てきているのだろう？

置換リスト(16) →       {1,4,5,2,3,}  →        (2 4)(3 5)
置換リスト(45) →       {2,5,3,4,1,}  →        (1 2 5)

これで見ると，〈16, 45〉でA5が生成できることになる．しかし，生成された部分群リストでは〈16〉から生成される群は以下の５つだけだ．

(96)〈16〉群{e,23,}は位数2のS5の素群である
(97)〈16,18〉群：{e,23,25,41,85,100,68,60,82,111,}は位数10のS5の合成群である
(98)〈16,19〉群：{e,23,26,45,99,107,}は位数6のS5の合成群である
(99)〈16,21〉群：{e,23,29,33,64,96,90,86,55,119,}は位数10のS5の合成群である
(100)〈16,42〉群：{e,23,56,78,94,67,}は位数6のS5の合成群である

〈3,22〉と〈16, 45〉は同型というよりは，同一と見るべきだろう．重複検査を行っているところで情報を出せるようにしてみよう．⇒結構難しい．置換に関しては置換プリントで取り出すことができるが，ループカウンタが違う．検定では部分群リストであり，そこから直接置換番号にアクセスすることはできない．部分群を生成するところで置換番号を記録できるのではないか？ないし，置換そのものを群の名称にしてしまうことも考えられる．置換群はPという置換クラスの変数を持っている．

しかし，部分群リストには部分群そのものは登録されていない．台集合が記載されているだけだ．⇒２つの部分群が一致した場合にダンプするように改変したのだが，むしろ速くなった．６分２３秒で完了している．というか，これは，実際にはループの半分をカットした効果だが…

■群S5は154個の真部分群を持つ■位数2X25 位数3X10 位数4X35 位数5X6 位数6X30 位数8X15 位数10X6 位数12X15 位数20X6 位数24X5 位数60X1
経過時間=0:6:28.352

どうもどこかに整合していないところがあるような気がする．一度整理してみよう．部分群の生成では，①置換リスト，②部分集合，③部分群生成元という３つのテーブルを使っている．①は親群を生成するときに用いた置換のリストで，(1)置換番号(０発進，単位元を含む)，(2)置換（全単射），(3)巡回置換の積表現の３項目からなっている．②は２次元配列で，部分群の元集合を生成順に格納したもの，③は部分群生成時の生成元のリストであり，②の部分集合の生成順に格納されている．②と③には単位群は含まれていない．

部分群は生成元を特定するために，置換リストを用いて置換を決定し，それから取り出した置換積を部分群の生成元として割り当てている．これは置換.置換プリントによって置換リストから取り出された値である．部分群が２つの素群から合成される場合には，部分群生成元から取り出された素群の生成元を連結して新たな部分群の生成元としている．いま注目している位数60のS5の部分群は，〈2,21〉なので部分群[2]と部分群[21]から合成されたものと推定される．

部分群[2]は{e, 3, 4}，部分群[21]は{e, 30, 48}でそれぞれ，(45), (123)を生成元としているから，位数60の生成元は(345), (123)でなくてはならない．(345)は置換リストでは#3，(123)は#30だが，これらは元の番号であり，部分群の番号ではないことに注意する必要がある．位数60の部分群が生成されたときには停止するようにしてみた．

★群(1 2 5),(2 3)(4 5),(2 4)(3 5)と群(3 4 5),(1 2 3)は一致する．

というのが出てきた．

★群(2 4)(3 5),(1 2 3)と群(3 4 5),(1 2 3)は一致する★

というのもある．見つかった！

★群(2 4)(3 5),(1 2 5)と群(3 4 5),(1 2 3)は一致する★

これが，FK氏の言うA5の生成元集合だ．

▲おかしな行が出てきた．

(109)〈22〉（）位数3のS5の素群である

()の中が空なのはなぜだろう？⇒ミスタイプで消してしまったようだ．

(109)〈22〉群(1 2 3)は位数3のS5の素群である

部分群検定の代わりに部分群検定3（生成元により素群を生成する）を使うことで位数2×9, 位数3×8，位数4×6に変化した．位数3の部分群は４個なので多分重複が発生している．これを削減するかないし抑制しなくてはならない．⇒確かに{e,3,4}と{e,4,3}など順序が異なるだけの同一集合が４組ある．しかし，重複を排除しようとすると，■群S4は16個の部分群を持つ合成群である■位数2X7 位数3X4 位数4X3 飽和=0のように今度は不足してしまう．

見たところ重複が発生するのは位数２の場合に限定されているようにも思われる．しかし，そう断定するのは難しい．やはり，重複を検査するしかないのではないだろうか？とりあえず，ソートしないで直接比較するルーチンを作ってみよう．HasSameElementsという関数を作った．⇒これで以下のように変化した．■群S4は18個の部分群を持つ合成群である■位数2X9 位数3X4 位数4X3 飽和=0　位数４は実際には７個だが，この段階では検出できない．

最終出力は■群S4は28個の部分群を持つ■位数2X9 位数3X4 位数4X7 位数6X4 位数8X3 位数12X1のようになった．⇒一つ問題がある．部分群検定3で生成される素群は必ずしも排他的ではない可能性が出てきた．部分群検定5はすべての素群が排他的（単位元を除き直和）であることを仮定しているので，不整合が発生する可能性があるのではないか？S4の場合，１を含む素群は５個ある．{e,1,}，{e,1,14,15,20,21,}，{e,1,6,16,17,7,22,23,}，{e,1,6,7,}，{e,1,2,3,4,5,}

いや，これらの中で素群となるのは{e,1,}だけだ．素群は全部で１６個あるが，これらの中には元が重複するものは存在していない．多分，素群にはノードの重複はないと言えるのではないかと思う．一応そういう仮定で進めることにしよう．いや，やはり重複はある．{e,7,}と{e,17,7,22,}では７が重複している．１３も{e,10,23,13,}で重複し，１６は{e,9,16,18,}で重複する．改訂版の動作をA5で確認してみよう．⇒素群は３１個生成されているので，多分同じ動作になるだろう．ただし，現行論理では完了までに２時間掛かる！

A5の素群にはS4の場合と異なり，元の重複は存在していない．⇒重複があったとしても追加登録関数で弾いているので，実質的な障害にはならない．素群生成時にも追加登録関数は使われているので，ノードのダブりが生じる可能性はないとしてよい．これでいよいよ部分群検定の高速化に入れるのではないか？

一番分かりやすいのは素群SとS’から合成群SxS’を生成するという方法だろう．ただし，このとき不足するノードが発生するのでそれを注入する必要が生じる．これができれば多分相当高速なアルゴリズムになると思う．生成された素群数をｓとすれば，現行の検定5では2^sのケースが発生するのに対し，s^2のコストでほぼ検定が完了するのではないかと思う．この再検定で生成された合成群に関してはさらに追検定が必要になる可能性はあるが，おそらくほとんどの場合は（なんらかの理由で）不用になるのではないかと思う．

位数最大となる極大な部分群の位数が分かれば，それだけでも計算コストは劇的に削減可能となるのだが… ⇒極大な部分群の最大位数を求める公式は得られていないので，最大部分群=12に固定して検定を実施したところ，20秒以内で完了した．確かに効果はある．

■群A5は57個の真部分群を持つ■位数2X15 位数3X10 位数4X5 位数5X6 位数6X10 位数10X6 位数12X5
経過時間=0:0:14.39