月: 2023年10月

群の検査関数では，単位元と逆元の存在を確認している他，乗積表をスキャンして記載漏れがないかどうかをチェックしている．従って，この検査を通っている限り，その群は成立していると考えられるのだが… 追加登録関数を見てみよう．⇒既存の論理でｘの２乗は登録されている．従って，２乗が落ちているという問題ではない．位数４の部分群{e,(12)(34),(13)(24),(14)(23)}が出てこない理由を調べてみよう．e=#0，(12)(34)=#13，(13)(24)=#30，(14)(23)=#43だ．これはノード対から生成するという今の方法では生成できないのではないか？

むしろ，１個の元xから生成される群を列挙した方が話が早いような気がする．x^n=eとなったときにはすでに群として閉じている可能性はあるが，すべての要素の逆元を取る必要はあるだろう．それだけで十分だろうか？多分，べきも取る必要があるのではないかと思う．いや，追加登録関数はすでにそれらのことをやっているのだから，x^n=eの時点で処理は完了しているはずだ．部分群検定3というのを作って試してみた．

今度は■群A5は61個の部分群を持つ合成群である■位数2X15 位数3X20 位数5X24 飽和=0という結果になった．位数2X15 というのは一致している．位数3X20は合わない．定数は１０なので倍になっている．位数４の部分群は出てこない． 位数5X24も定数６なので18個も多い．位数６以上の部分群はまったく生成されていない． 位数４にはV4が含まれているはずだ．乗積表を見てみよう．※

※A5の部分群にV4が含まれているというのは間違い

1→     1, 2, 3, 4,
2→     2, 1, 4, 3,
3→     3, 4, 1, 2,
4→     4, 3, 2, 1,

なるほど，これでは現在の方式では生成できない．

1^2=2^2=3^2=4^2=1

だ．つまり，すべての元が生成元になっている．

さて，部分群の列挙の続きをやろう．現状ではA5の部分群として76個我列挙されている．内訳は，■群A5は76個の部分群を持つ合成群である■位数2X1 位数3X1 位数5X1 位数6X4 位数10X3 位数12X64 飽和=58．まだ，列挙というには程遠い状況だ．ともかく，重複を弾くところから入ることにする．⇒今度はだいぶいい感じになってきた．■群A5は62個の部分群を持つ合成群である■位数2X15 位数3X20 位数5X24 位数12X1 飽和=1．ただし，位数4, 6, 10 の部分群が消えてしまった．

その代わり位数3が本来10個のところ，20個も生成されている．論理ミスがあった．修正して，■群A5は17個の部分群を持つ合成群である■位数2X1 位数3X1 位数5X1 位数6X5 位数10X2 位数12X5 飽和=58のように変わっった．今度は１７個まで減ってしまった．seed1, seed2だけを除外するようにしたら，元の76個に戻ってしまった．（seedがダブらないようにループしているのだから当然だが）そもそも，この位数１：1，位数２：15，位数３：10，位数４：5，位数５：6，位数６：10，位数10：6，位数12：5，位数60：1，合計：59 という数字はどこから拾ってきたものだろう？

⇒この数字の出所は以下のURLだ．

http://mathweb.sc.niigata-u.ac.jp/~hoshi/2007/gap-hoshi.pdf

タイトルは「GAPを使ってみよう」となっている．新潟大のサイトだが，筆者の所属は早大だ．筆者の星明考氏は新潟大理学部教授で「群論序説」という本を書いている．

シードが１個だけの場合も部分群にカウントするようにして，以下の結果を得た．■群A5は135個の部分群を持つ合成群である■位数2X16 位数3X21 位数5X25 位数6X4 位数10X3 位数12X64 飽和=58．かなり網羅的になってきたように思われる．不足しているのは，位数４：５（▼５），位数６：１０（▼６），位数１０：６（▼３）だけになった．この方法で位数４がまったく出てこないのはなぜだろう？位数４は分解しないと得られないのだろうか？

シードを１個追加したときに群とならない場合でもシードを追加するようにしてみたが，結果は変わらなかった．■群A5は135個の部分群を持つ合成群である■位数2X16 位数3X21 位数5X25 位数6X4 位数10X3 位数12X64 飽和=58　まぁ，当然かもしれない．部分群を再分解してみたが，位相４という部分群は出てこない．なぜだろう？まず，これを取り出す方法を考えた方がよいのではないか？

A5の位数３の部分群は{e,(123),(132)}で，共役部分群は１０個ある．A5の位数４の部分群は、{e,(12)(34),(13)(24),(14)(23)}で，共役部分群は５個．A5の位数３，４の部分群はp-Sylow群．部分群がp-Sylow群でない場合には互いに共役でない部分群が存在する可能性がある．

Elsieの出力する置換リストには{e,(12)(34),(13)(24),(14)(23)}の記載がない．いや，これは意味が違うのではないか？これは「生成元の集合」であり，むしろ，〈e,(12)(34),(13)(24),(14)(23)〉と書くべきものだろう．つまり，位相４の部分群の生成集合の位数は４である．⇒いや，読み違えている．{e,(12)(34),(13)(24),(14)(23)}というのはそのものずばり，位数４の部分群だ．

位数と指数の関係：|G:H|=|G|/|H| ラグランジュの定理

A4と位数12の部分群HではHの指数は60/12=5となる．

▲部分群検定でused配列の使い方に疑義がある．関数本体では準同型検定.正規部分群の場合に限ってusedをマークしているが，それから呼び出される 追加登録 では逆に正規部分群検定でない場合に限りオンにしている．⇒usedの使われ方を点検する必要がある．⇒いや，その前にusedを無視したらどうなるか？というチェックをした方がよいのではないか？

※一番外側のiループでは台集合の並び順に原則すべて生成することになる（正規部分群の場合はつねにその動作を行う）が，その後の追加登録で追加されたノードを処理済にするためのマークになっているので，現行論理でよいと思われる．

usedを無視したらどうなるか？⇒A5の部分群は６１個ということになった．ただし，位数は２，３，５の三種しかない．台集合を比較すると重複しているので，やはりusedを無視するというのは間違いだ．ただし，部分群の合計が６１になるというのはそれ自体問題なので調べておく必要がある．というか，i=1～N-1までの部分群を作って，それに２を足しているのだから当然の数字だ．

ノード対を含む部分群を生成する場合もusedと同様の仕掛けが必要になる．２次元のテーブルを作らなくてはならないが，それに記載されている場合にはパスするというのでよいのだろうか？群表に記載された対はすべて除外されることになるのだが…

まだ，ロジックは書き始めたばかりだが，「■群A5は12個の部分群を持つ合成群である■位数3X1 位数12X9」というメッセージが出力された．本来なら位数３はｘ10，位数12ｘ５だが，位数１２の部分群が生成できたということはこの方針が間違っていなかったことを示していると言えそうだ．外側のiループですでに部分群に入っているかどうかを無視して生成するようにしたところ，■群A5は76個の部分群を持つ合成群である■位数2X1 位数3X1 位数5X1 位数6X4 位数10X3 位数12X64 という結果になった．これには相当重複が入っているが，位数１０の群が出てきたというのはよい傾向だ．

位相１０の部分群は６個あるのでまだ漏れはあるが，当初論理で位数２ｘ15，位数３ｘ10，位数５ｘ6は確定しているので，位数４ｘ６（不足数４）と位数５ｘ５（不足数４），位数６ｘ１０（不足数６），位数１０ｘ６（不足数３）という状態だ．ともかく，重複が発生しないような仕掛けにしなくてはならない．

先に進む前に，A4の部分群を既成ツールを使って出しておこうとしたのだが，例外が発生する．Printでエラーを出している．2023/09/14のログによると「A4の置換リストを保持しようとすると，479001600ｘ12ｘStringのサイズを持つ配列を用意しなくてはならない… OutOfMemory例外が起きてしまう」とあり，「置換リストを使わない」というオプションを設置している．

▲C#のPermuteで配列の長さ不足エラーが発生する．

array.CopyTo(Form1.Homo.map.map1, 1); をインデックス１から開始しているためだ．コピー元はarrayでコピー先は常設のHomoという準同型クラスオブジェクトの写像.map1だ．写像は０発進になっていたような気もするのだが…他の部分を見ても写像は０発進となっているように思われる．仮修正として写像のコンストラクタでmap1/2を１だけ長くしてみよう．おかしい．長さが増えていない．どうも，この「置換リストを使わない」というオプションは仕掛りのまま放置になっていたように思われる．⇒仮修正の妥当性をチェックする必要がある

置換関数の中で「置換リストを使わない」という分岐中で置換リストにアクセスしているというのはかなりおかしい．いや，置換リストの最初の１項目だけは使っているのかもしれない．置換リストはクラス置換のメンバーオブジェクトだ．置換リストは，①全単射の生成，②置換の生成の２箇所で生成されている．Permuteでは「置換リストを使わない」ときは，ArrayListの先頭しか生成しないようになっているはずだ．おそらく，「置換リストを使わない」は行列同型検定のときのみ適用することを予定していたのではないだろうか？

実際，自己同型検定は現状ではN<5であるか，ないし置換リストを使わないモードでないと動作しないようになっている．置換::id[]というのは，群の台集合のようなものなのではないだろうか？いずれにしても，置換リストがないと置換群は生成不能であるようだ．行列同型判定にELSIEを使おうとしていたので，群についての興味は薄くなっていたものと思われる．何か方法はあるだろうか？

おかしい．S4の部分群検定は動作している．S4が通っって，A4が通らないというのは妙だ．parityが非ゼロのときには，IsPermutationEvenが実行される．この中で落ちている．少なくともC#に移ってからは偶置換はテストされていないようだ．ただし，VBでは実施していたはずだ．VBでは通っていたものが通らなくなっているのだろうか？⇒IsPermutationEvenに入る前に落ちている．

IsPermutationEven((string[])list[0], array, size);

C#に移行した時点では， IsPermutationEven(ArrayList list, string[] array, int n)のような構文で動いていたのを修正している．従来論理ではIsPermutationEvenの冒頭で，if (list.Count < 1) return result;としていたので，問題は発生しなかった．元の論理に戻して動作するようになった．とりあえず，A4程度なら置換リストを使っても問題なく動作している．A5を試してみよう．

リリース版は走っているのだが，デバッグ版で起動時に障害が起きる．フォームのコンストラクタでInitializeComponentを実行する前に落ちてしまうので，手が付けられない．コンソールはこの時点ではすでに開かれている．C#プロジェクトがコンソールアプリになっているためだ．出力をWindowsアプリに切り替えても動作は変わらないので，コンソールが出ていることは障害の原因にはなっていないと思う．では，何のどこが悪いのか？C#部分（に限らず既存コードすべて）にはまったく手を触れていないはずなので，なぜこのようなことになってしまったのか？まったく理解に苦しむところだ．

ビルドオプション関係が書き換わってしまっていたり，いじってしまっている可能性はあり，それが影響している可能性が一番高いように思われるのだが，特定するのは難しい．既存コードと目視で比較するのと，作り直ししてしまうのでどちらが早いだろう？原因を特定したいところだが，動かないことにはどうにもならない（デバッグもできない）ので，出直して動かすことを優先する方が賢明かもしれない… まず，最終の準同型検定CSまで戻ってみることにしよう．とりあえず，最終版の準同型検定CSを準同型検定CS+とリネームして始めることにする．

▲警告が１件出ている．warning MSB8004: Output ディレクトリの末尾がスラッシュではありません。Output ディレクトリが適切に評価されるようにするために、このビルド インスタンスによってスラッシュが追加されます。⇒これは簡単に解決する．ElsieProjectの出力ディレクトリの末尾の\が落ちているためだ．しかし，別の警告が出てきた．

▲ warning MSB3270: 構築されているプロジェクトのプロセッサ アーキテクチャ “MSIL” と、参照 “D:\準同型検定CS＋\Debug\ElsieProject.dll” のプロセッサ アーキテクチャ “x86” の間には不一致がありました。この不一致は、ランタイム エラーを発生させる可能性があります。プロジェクトと参照の間でプロセッサ アーキテクチャが一致するように、構成マネージャーを使用してターゲットとするプロジェクトのプロセッサ アーキテクチャを変更するか、ターゲットとするプロジェクトのプロセッサ アーキテクチャに一致するプロセッサ アーキテクチャとの依存関係を参照で設定することを検討してください。

https://nanoris.livedoor.blog/archives/51798587.html

上のリンクの記事によると，原因は「Any CPU、x86、x64 が混在している。Any CPU に対して、x86, または x64 が固定的に組み合わさっている。」ということのようだが… 確かに，Any CPUとWin32が混在した状態になっている．ただし，これで問題なく動作してきたような気がするのだが… おそらく，この警告は昔から出ていたのだろう．

MSILというのは，ProcessorArchitectureの値で，「プロセッサおよびワードあたりのビット数に関して中立」という意味だ．x86というのはIntelのCPUという意味で，32ビットの場合も，64ビットの場合もあり得る．今の場合，AmdやAppleのCPUを使うということは想定されていないのだから，x86でよいのではないだろうか？どうしたことだろう．今度はリリース版で起動時障害が発生してしまった．デバッグ版でも同じだ．プラットフォームをAny CPUに戻したら実行できるようになった．これは警告を無視するしかないような気がする．

ここにAriadne100を移植する．前回は既存プロジェクトを使ったが，今回は新規にプロジェクトを起こしてみよう．⇒ちょっと失敗してしまった．Ariadne100の下にAriadne100ができてしまった．⇒既存フォルダがあると新規プロジェクトを生成できない．

pch.cpp, pch.h, framework.hをプロジェクトから除外した．dllmain.cppも外しておく．⇒*.pchファイルがない⇒プリコンパイル済みヘッダを使わないとする．これでようやくコンパイルができるようになった．エラーがかなり出ている．

▲E0167    型 “const char *” の引数は型 “char *” のパラメーターと互換性がありません    Ariadne100    D:\準同型検定CS＋\Ariadne100\Contract.cpp    613    ⇒対処した．

リリース版，デバッグ版のどちらでも動作するようになった．一度バックアップを取っておこう．フォルダ名は「アリアドネの糸巻き」，アセンブリ名は「アリアドネの糸」に変えてみた．EXEはアリアドネの糸.exeという名前になる．現行では下図のような画面になっている．これにどう組み込んだらよいか？

タブで切り替えるような作りになっているが，コンソールが常時出ているとしたら，それも不要という感じになる．当面，①行列同型，②ハミルトン閉路の２つのボタンがあればよいのではないか？画面に出すとすれば，むしろマトリックスを入出力できるようなグリッドを表示するというのが適切なのではないかという気がする．Ariadneを組み込むに当たってまずやるべきことは，すべてのクラスを名前空間の中に収納することだ．ARIADNATIVEとした．⇒一応EXEが走るところまで来たので，一度バックアップを取っておこう．

▲コンソールにはスクロールバーは付けられないのだろうか？⇒縦スクロールバーは自動的に付加されているが…

テストボタンを押すと，ハミルトン検定のメニュー画面が出るようになった．つまり，アリアドネ１００の画面がそのままコンソールに表示される．行列同型検定も同じような作りで起動できるようにしておこう．

NHKの笑わない数学の第一弾は「確率論」，第二弾は「非ユークリッド幾何」でどちらもFBの数学グループで話題沸騰中だ．わたしも巻き込まれてだいぶ時間を消費してしまったが，本線に戻ろう．グラフの隣接行列から距離行列を生成する「ワーシャル・フロイド法」というアルゴリズムがあり，これをハミルトン閉路問題に応用するという課題がにわかに浮上してきた．ロバート・フロイドがこのアルゴリズムを最初に発表したのは1962年（それ以前にバーナード・ロイとステファン・ワーシャルが独立に発見している）で，現在の三重ループの形に整理されたのはピーター・インガーマン(1962)による．

このアルゴリズムは元々はオートマトンや正規表現の世界から渡ってきたようで，重み付き最短経路を多項式時間で計算することができ，さらに重みの和が負であるようなサイクルを含まないグラフのサイクル検出にも適用できる．また，推移的閉包の検出にも適用可能であるようだ．FBのコメントではこのアルゴリズムが「フロイド・ライブネッツアルゴリズム」という名称で紹介されていた．

https://pydocument.hatenablog.com/entry/2023/04/29/132317?fbclid=IwAR1gENpzpPoA2siiWajP0Z3eyj4oCE9R4All5ovWCpKaCTFMPa6FebswHrY

しかし，どこを探してもそのようなものは出てこない．そもそも，Leibnizの名前をライブネッツとなまっている時点でおかしいのだが，上の記事では何度もこの名前で出てくるので執筆者はそれが正しいと確信しているようだ．この記事はHatena BlogのPyDocumentというシリーズものの一部で，『問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本』米田優峻著からの抜粋のように見えるが，ひょっとすると本当の著者はChatGPTなのではないだろうか？いかにもChatGPTのやりそうな間違いだ．

「GPU上での高速なブロック化フロイド・ワーシャル法」などというのもあり，かなり実用的に使われているアルゴリズムではあるようだ．

https://cir.nii.ac.jp/crid/1050564287852717824?fbclid=IwAR2oMq0IYmoIrE51iR163SnZNPBA-mxKVd9MzsPwBcowTvNgwBGhGZVwU3M

この記事では改良によって頂点数256～1024の場合は従来手法より高速化し，それ以上の場合は遅くなったと報告しているが，アリアドネの既存コードでは100点までしか計算できない．行列同型でもN=520を超えるサンプルではスタックオーバーフローが起きていたはずなので，500点を超えるサンプルを扱えるようにするのは難しそうだ．我々の目的からすれば，そこまで大きなサンプルは必要ないので，まぁ，500点が限界だとしてもとりあえず問題はないが…

アリアドネはFドライブのBACK2006-05-05/BABA_LABORATORYにある．このフォルダにはsamplesというフォルダがあるが，この中にはファイルが9452本も入っている．フォルダだけで13個もある．Narcissus，ないしNarkissosというフォルダが気になる．ハミルトン閉路問題ではないかという気がするのだが… 2002～2004年頃のものだ．どちらが最終版なのか？EXEのタイムスタンプはまったく同じなので時期は完全に一致している．前者はフォルダ数293, ファイル数19に対し，後者のフォルダ数は30．ファイル数は3566なので，おそらく，Narcissusを保存版としてくくり出したのだろう．

Narcissusのpublishというフォルダには，Narcissus.exeと一緒にELSIE.exeも入っている．このフォルダではELSIEとNAICISUSを並行して開発していたのだろうか？このフォルダのSOURCEにはELSIEのソースファイルしか入っていない．⇒走らせてみれば分かるだろう．

NarcissusというのはELSIEの一部だ．つまり，ELSIEはNarcissusを含んでいる．NarcissusはELSIEの機能のうち，グラフ同型検定に特化したものと言ってよい．ただし，この機能に関してはELSIEより少し詳細な設定ができる可能性がある．たとえば，表示モードを切り替えたり，ファイル形式の変換ツールが入っていたりする．まぁ，とりあえずはELSIEに含まれているものだけで十分だ．アリアドネのソースはVBだと思っていたが，C++だった．AriadneはELSIEとほぼ同等だから，準同型検定CSに組み組むのは難しくないと思われる．ただし，Ariadneを組み込むとこのプロジェクト全体の性格が大きく変化することになるので，フォルダ名を変えておくのが順当だろう．

もし，今後ハミルトン閉路問題が主題になるとすれば，日本語で「アリアドネ」ということでよいのではないだろうか？Ariadneの中にはAriadne100の他に，Asha, CounterStas, Hcp2Sat01というフォルダがある．Hcp2Satはハミルトン閉路問題をSAT（論理式の充足可能性問題）に変換するためのツールだ．CounterStasというのはよく分からないが，Stanislav Busyginとのやり取りに関係したものだろう．Ashaの中にはBlkblu.exeというのが入っているが実行できない．あとはBlkblu.cとテキストファイルが２本入っているだけだ．

Ashaというのは多分人名だと思う．確かにそうだ．Cソースの中に

printf(“\n%s   v. %d, by Asha Goldberg\n\n”, progname, versionno );

という一行があるので，Asha Goldbergという人物が書いたコードだということが分かる．この頃はネット上にソースが転がっているという時代ではないので，多分本人から送ってもらったものではないかと思う．ただし，メールの現物は残っていない．このコードはハミルトン閉路の解法アルゴリズムだ．いや，ハミルトン閉路を含むグラフを生成するためのコードかも知れない．ブラックとかブルーなどの色を頂点に割り当てるようなことをしている．おもしろそうだが，読み切るにはちょっと時間が必要なのでパスしておこう．データファイルのフォーマットはアリアドネと完全に同じ，各行が#で始まる隣接行列だ．

ELSIEを組み込んだときの手順を忘れてしまった．既存のプロジェクトを組み込むというのが最速だが，新規プロジェクトとして登録してからファイルを追加していったような気もする．その辺り，ログに残っているだろうか？ELSIEのときは，boostというライブラリの組み込みで立ち往生していた．ELSIEのプロジェクトファイルはElsieComeBackフォルダに入っているので多分既存プロジェクトを組み込んだだけだと思う．その後，ソースファイルの入れ替えをやったような記憶もあるが… それよりも，Ariadneに入っている本体以外のフォルダを削除してディレクトリを１段上げておいた方がよい．つまり，アリアドネの直下にAriadne100が来るという構成だ．

準同型検定CSというソリューション名も変える必要がある．名前の変更は調整できたが，ビルド→実行でエラーが出てしまった．

アプリケーションのシングルスタートアッププロジェクトがElsieComeBackになっていた．準同型検定に変えて動作するようになった．⇒既存プロジェクトの追加で以下のメッセージが出た．

OKでビルドできたが，「D8016    コマンド ライン オプション ‘/ZI’ と ‘/Gy-‘ は同時に指定できません」のようなエラーになった．/Gy-というのは，関数レベルでリンクしないという意味のようだ．ZIはエディットコンティニュの意味だ．/Gy 関数レベルでリンクするに統一した．

▲i, j, k が定義されていない，ないし，未使用という警告⇒対処した．

▲warning D9035: オプション ‘Gm’ の使用は現在推奨されていません。今後のバージョンからは削除されます。⇒最小リビルドを有効にするという意味だ．⇒オフにしておこう．

▲This function or variable may be unsafeがかなりの件数ある．fopen, scanf, getch, strcpy, sprintf, ctime, strcpy,.. などだ．

▲MAXNを520まで拡大して，スタックオーバーフローが発生した．ExcentricGraphでMakeRandomGraphの後，Shuffle関数の呼び出しができない．プロセスメモリは200MBくらいしか消費していない．MAXN=400なら動する．500でも動いている．⇒Shuffleの引数を参照からポインタに変えてみたが，スタックの使用量は減少していない上，Shuffleの中でGP例外が発生した．一度修正を元に戻すことにする．

#1 > 2 3
#2 > 1 3 4
#3 > 1 2
#4 > 2 

MatはVnというパラメータを持っている．これが決まらないと正しく動作しないというのはまずいと思う．clearmatではMAXNを与えている．引数のｎの範囲を初期化するようにした．これで隣接行列は正しくなったが，距離行列はまだおかしい．初期状態で①ー④と③ー④の間には∞が入っている，ここまでは正しい．⇒修正ミスだ．ECCENTRICITYのところをINFINITDISTANCEで書換えていた．⇒動作するようになった．