jurupapa さんが、新しく maxima 用のプログラムを公開されました。
GaloisGroupSolverをGithubに公開しました
ehito さんが提案されたグレブナー基底を利用したアルゴリズムを、オプションで使用できるようになっており、これは以前私が漠然と想定していた「アルゴリズム B」に相当するものと言っていいようです。いちいち \(h_0(x), h_1(x), \dotsc\) や \(\theta_0(x), \theta_1(x), \dotsc\) を作って \(p\) 乗して…といった手続きを陽に行わなくても、グレブナー基底を求める過程で結果的に同等なことが自動的に実行されて、バシッと必要な結果が出てくるようですね。グレブナー基底すごい。高機能である分、代償として計算時間がかさむ場合があるようですが、それはやむを得ない犠牲だと思います。
この場合、「\(\theta_1(x)\) から \(\theta_{p-1}(x)\) までをもし作ったとしたときに、陽にゼロ多項式になってしまうものが出るような場合にうまく行くのか」は私にはよくわかっていませんが、それを除けば \(g(x)\) をべき根を使って逐次因数分解していく部分については概ね決定版と言っていいものができたのではないでしょうか。これでグレブナー基底にはだいぶ興味が重なったので、そのうち時間を見つけてかじってみようと思います。
あと、プログラム的に目指すべきことは「ガロア群の組成列を求めるアルゴリズムの不備を解消する」ことくらいになったのではないかと思います。
「数式処理ソフトによるガロア群の算出と、べき根を用いた厳密解の表現 その8」への5件の返信
計算方法の進歩が速すぎて，最近の話題には付いて行けなくなりました。ガロア群の組成列の計算法を検討中ですが，既にehitoさんが完成させてしまったようです。今後は私が貢献できることは何もないと思います。最近は少々弱気になってきました。以下の3つのコメントをよろしくお願いします。
(1)根の多項式表現
最近はグレブナー基底による方法が主流となっていますが，私としては未だに連立1次方程式による方法(「可解な代数方程式の…解法」第6節)が諦め切れません。連立1次方程式による方法で使っている数学的概念は大学の工学部で習うレベル(因みに私は工学部卒です)ですが，グレブナー基底による方法で使っている数学的概念は大学の理学部数学科のレベル(私の想像であって，実際に習うかどうかは不明)です。可解な方程式の解法入門用としては，前者のほうが易しくて優しいので，細々とでも残しておきたいです。また，もしも両者が同等のパフォーマンスならば，わざわざグレブナー基底に代える必要はないと思います。思い返してみると，両者のパフォーマンスを客観的に比較したことはまだないと思います。そこで，それを実際にやってみることをお願いしたいと思います。「可解な代数方程式の…解法」第10節の(例1)-(例7)について，計算時間を比較してみるのがよいと思います。それならば，連立1次方程式による方法の計算時間は本ブログ(「方程式のガロア群の求め方・さらなる補足」への1件のフィードバック)に示してあります。ただし，ここで示した計算時間は実時間(計算終了時刻と計算開始時刻の差)です。とくに，連立1次方程式による方法では計算できなかった(例3)と(例6)，計算結果がとんでもなく長い(例7)について，グレブナー基底による方法ではどのようになるかに興味があります。これで，グレブナー基底による方法の優位性が実証されれば，連立1次方程式による方法は諦め切れます。
(2)6次方程式の計算
jurupapaさんが6次方程式(簡単なものに限る)の計算に成功されているのは，私にとっては少々の驚きです。さらに，ehitoさんが数値解を用いないGalois群の計算ルーチンを投稿されているのを見て，今度は少々の驚きどころではなく，大変な驚きです。私のMathematicaプログラムでは到底無理です。本当に720次のg(x)を計算しているのでしょうか。どこか一部の計算を省略したりしてはいないのでしょうか。これに関して，何かご存じならば教えて下さい。jurupapaさんやehitoさんに直接聞いたほうがよいのでしょうが，今まで直接やりとりしたことがないので。
(3)ガロア群の組成列
正規部分群をしらみつぶしで探索する方法 ── 1個の元から生成される正規部分群を探索する。2個の元から生成される新規の正規部分群を探索する。同様にk=3,4,5,…として，k個の元から生成される新規の正規部分群を探索する。新規の正規部分群がなければ終了とする。── を検討中です。全然スマートな方法ではありませんが，他には思い付きませんでした。プログラムは殆ど完成していて，文書作成中です。もう少し先になれば報告できると思います。しかし，既にehitoさんが完成させてしまったようで，意味がなくなってしまいました。
すみません、別記事に書いた通り時間がないので手短に。
まず、各解を V の多項式で表す部分については、私の理解ではグレブナー基底は使っていません。1 年ちょっと前、jurupapa さんが Galois 群を求める所までの所に取り組まれていた時に計算の一部でグレブナー基底を使っていましたが、その計算は全体としてはやはり相当に時間がかかるものでした。一方、最近になって登場した新しい計算法で利用しているのはグレブナー基底ではなく「代数拡大体上での既約分解」で、手順と理論は https://ikumi.que.jp/blog/archives/746 で解説しています。
最近の jurupapa さんのプログラムでグレブナー基底を利用しているのは、組成列が求まった後にべき根を使って g_k(x) を求める所の計算で、これは（私が理解している所では、どうやら）べき根の取り方の不定性によって、0 になったりならなかったりする式が関与する場合でも信頼できる結果が得られる手順になっています。そこにグレブナー基底の優位性があります。ただ、最新記事で書いた通り、ここはグレブナー基底を使わず「退職後は素人数学者」さんのアルゴリズムほぼそのままで問題なく計算できるやり方は発見したので、わかりやすさと計算時間の両面でグレブナー基底を使ったアルゴリズムを上回る見通しは立っています。
ehito さんの、数値計算を使わない Galois 群計算ルーチンは、私には（maxima の文法や関数をよく知らないこともあって）何が何だかさっぱりわかりません。poly_reduced_grobner を使っているので、肝心な部分でグレブナー基底を使っていることだけはわかりますが…。コード全体の漠然とした雰囲気と、実際に maxima 上で例示されてる 3 例を計算させてみた時の処理の軽さ（一番複雑だった 4 次方程式でも数秒）からして、おそらく私の「n! 次の整数係数多項式をまず求め、それを既約分解する」という手順にはよらずに直接 g(x) を出しているのだろうと推測します。
ゼロから学ぶグレブナー基底（入門編）を受講してきたおかげで、ようやくグレブナー基底の基本的な知識と、数式処理ソフト上でのグレブナー基底の扱い方・表現がわかるようになりました！おかげで、これまで謎だった、グレブナー基底を利用したコードもわかるようになってきました。そのうち補足記事を書こうと思いますが、まずは ehito さんの数値計算を使わない Galois 群計算ルーチンについて。
今回改めて試してわかったことですが、このコードの主役は実はグレブナー基底ではなくて、splitfield という関数でした。これは splitfield(f(x), x) の形で呼ぶと、「f(x) の Q 上の（？）最小分解体を与える原始元の最小多項式と、その原始元による、f(x) の各根の Q 係数（？）多項式表現」を一揃い返してくれる関数のようです。どういう計算原理で動いているのか私にはさっぱりわからないのですが、非常に高速に動作し、おかげで「n! 次の対称式をまず求め、基本対称式の値からそれを簡約化し、整数係数の範囲で既約分解する」「連立１次方程式を解いて各根を V の多項式で表す」というえらく時間のかかる処理を丸ごとスキップして、あっという間に諸々を求められるようになっています。splitfield は maxima の組み込み関数のようなのですが、どういうわけか help document に載っておらず、詳しいことはわかりません（私が help の詳しい使い方をわかってないのかも…）。
splitfield が扱う原始元は、我々が使っている Galois の V（全根の整数係数の１次結合）とは限らず、例えば x^3-3x-1 に対しては根の一つを原始元とした結果が返ってきます。ehito さんのコードは、この原始元を V を使って表す式を求めたり、V の最小多項式を得たりするためにグレブナー基底を使っており、このコード内ではグレブナー基底の役割はごく補助的なものでした。（一方、g_k(x) の逐次分解を進めていく場面でグレブナー基底を使っている別のプログラム中では、もっと中心的な役割を果たしています）
一体どうやって splitfield がこんなに高速に動作するのかの計算原理は、また改めて ehito さんに問い合わせてみようと思います。
待てよ、ひょっとすると、splitfield は実は内部で数値計算をしているのかも？それならばこんな高速で動作するのも納得ですが。
そうか、たぶん数値計算じゃないですね。ehito さんが http://ehito.hatenablog.com/entry/2019/02/24/150254 でご自身の実装を公開されてますが、代数的に上手に計算する方法があるんですね。以前見た、「代数拡大体上での因数分解」を発展させた方法で、重い計算を回避して処理できる模様です。