数式処理ソフトによるガロア群の算出と、べき根を用いた厳密解の表現 その14

「退職後は素人数学者」さんより、改訂版の記事を送っていただいたので掲載します。特筆すべき点は、すべての \(V_k\) を根に持つ多項式 \(F(x)\) を具体的に整数係数の多項式として求める部分の計算が、因子の組み合わせを工夫することにより劇的に短縮されていることです!

その他にも、細かい改良が色々と散りばめられていて、かなり完成度が上がっています。

以前問題視されていた、「べき根の選び方の不定性によって、\(0\) になる可能性もならない可能性もある式」が分母にある場合の対処については、掲載されているプログラム本体には取り入れられていないものの、具体例の考察の中で参考として紹介されている計算の中で利用してくださっているようです。

「退職後は素人数学者」さん、いつもありがとうございます。

数式処理ソフトによるガロア群の算出と、べき根を用いた厳密解の表現 その13

先日、「ゼロから学ぶグレブナー基底(入門編)」を受講してきて、グレブナー基底のことがちょっとはわかるようになりました!おかげで、jurupapa さんの所のコメント欄や ehito さんの所でしばしば挙げられていた、グレブナー基底を使ったプログラムがわかるようになりました。感激!(ものによっては、グレブナー基底以外の部分のハードルが私には高くて、部分的にしかわからなかったものもありましたが)

今や、jurupapa さんの GaloisGroupSolver で \(g(x)\) を順次因数分解していくところで、「アルゴリズムA」の代わりにグレブナー基底を使うと、何がどうなって問題を回避できるようになっているのかも理解できるようになりました!

それらについて改めて考えたり、maxima での動作を確かめたりしているうちに、最初の方の処理「与えられた整数係数の方程式のガロア群を置換群として求める」も、元々私が公開していたものとは別のやり方で計算できるアルゴリズムを何通りか思いつきました。ひとつ思いつくと思い込みの壁が崩れるため、続けていくつかのバリエーションが出てきたのですが、その中にはグレブナー基底を使わないものもあります。このため、新しいアルゴリズムではガロア群の計算は結構軽量化できると思います(少なくとも、数式処理ソフトの利用を前提とする限りは。手計算では、軽くなったと言っても \(4\) 次以上の方程式に対しては相変わらず到底実現可能な域ではないでしょう)。

jurupapa さんや「退職後は素人数学者」さんが実際に動作するプログラムを組み上げてくださったおかげで、元々私が公開していた記事のアルゴリズムでは、次の2ヶ所の処理が極めて重いことが解っていました。

  1. 最小分解体の原始元 \(V\) を根に持つ有理数係数多項式 \(F(x)\) の算出
  2. 各解を \(V\) の有理数係数多項式として表す式の算出

これは、私のアルゴリズムではどちらの処理も「解の対称式のかなり高次の多項式・有理式をまず求め、更に解と係数の関係からそれらの値を求める」という方針になるためです(正確には、2. はお二人とも私のアルゴリズムそのものではなく、計算量を軽減する工夫をされていましたが、それでも「解の基本対称式の値がわかっていることを利用して、解の多項式の次数下げをひたすら繰り返す」という部分は共通で、それが計算を重くしているという事情は同じでした)。

このうち、2. の処理については既に「代数拡大体上の因数分解」の技法によって、もっとはるかに簡単に計算できるようになっており、jurupapa さんのプログラムに取り込まれています。これに続いて、ついに 1. も「解の基本対称式を利用した次数下げ」から脱却できるようになったわけです(…ということ自体は既にかなり前に ehito さんが呈示しておられたのですが、そこで使われていたのがグレブナー基底だったため、私にはその原理がわからなかったのです)。

また例によって結構余裕のない日々がしばらく続くのですが、1ヶ月なり数ヵ月なり後に、グレブナー基底の解説と共に新しいアルゴリズムを紹介する記事を書くつもりでおりますので、この話題に注目されてる方がいらしたら気長にお待ち頂ければと思います。

Mathpower2018 数学の決闘 解答一部公開

今年の Mathpower は開催しないことになってしまいました。そうなると気になってくるのは去年の後始末です。結局、「数学の決闘」の解答は未公開のままでした。運営サイドには終了後すぐに公開用の解答は提出してあったのですが…。このままだとお蔵入りになってしまうので、ここで個人的に公開することにします。

“Mathpower2018 数学の決闘 解答一部公開” の続きを読む

数式処理ソフトによるガロア群の算出と、べき根を用いた厳密解の表現 その12

うまく変数が消えていく理由

以前話題にして、河下希さんに解決していただいた『「根 \(x_{1} ,x_{2},\dots,x_{n}\) と係数 \(a_{n-1}, \dots, a_{1}, a_{0}\) の関係」について』の件ですが、別解が作れましたので公開します(以下常体)。

“数式処理ソフトによるガロア群の算出と、べき根を用いた厳密解の表現 その12” の続きを読む

数式処理ソフトによるガロア群の算出と、べき根を用いた厳密解の表現 その11

\(\newcommand{\zettaiti}[1]{\lvert #1 \rvert} \newcommand{\field}[1]{\mathbb{#1}} \newcommand{\Q}{\field{Q}} \newcommand{\rnsg}{\vartriangleright}\)

組成列の計算

前記事での「退職後は素人数学者」さんの考察を見て、組成列の計算法について改めて考えてみました。

「退職後は素人数学者」さんのアルゴリズムだと、組成列 \[ G_{0} \rnsg G_{1} \rnsg \dots \] を計算する際、単位群が現れるまでは、どの \(G_{k}\) に対しても改めてその正規部分群全てを計算し直すことになります。しかし、どの \(G_{k}\) の(正規)部分群も、最初の群 \(G_{0}\) の部分群です。

したがって、一連の計算では、最初に \(G_{0}\) の部分群を全部求めておけば、後はそれを再利用することができます。

“数式処理ソフトによるガロア群の算出と、べき根を用いた厳密解の表現 その11” の続きを読む

数式処理ソフトによるガロア群の算出と、べき根を用いた厳密解の表現 その10

「退職後は素人数学者」さんが、また新たに文書を送ってくださいました。

与えられた有限群(置換群)のすべての部分群、あるいは正規部分群をしらみつぶしによらずに求めるアルゴリズムが記載されており、それに基づいて \(S_6\) までの対称群で、すべての部分群の共役類による分類を完成したり、可解な部分群をすべて特定したりされています。さらに、今度こそ正しく組成列を求めるアルゴリズムを構成されて、いくつかの組成列を求められたりしています(実際のプログラムではなく、プログラムの実行結果が載っています)。

あとは、前回の私の記事ともども、実際のプログラムにまとめ上げれば不備のないプログラムができ上がることでしょう!

「退職後は素人数学者」さん、いつもありがとうございます。

数式処理ソフトによるガロア群の算出と、べき根を用いた厳密解の表現 その9

\(\newcommand{\zettaiti}[1]{\lvert #1 \rvert} \newcommand{\field}[1]{\mathbb{#1}} \newcommand{\Q}{\field{Q}} \newcommand{\rnsg}{\vartriangleright} \DeclareMathOperator{\Gal}{Gal}\)
可解な方程式で、\(V\) の最小多項式 \(g(x)\) をガロア群の組成列にしたがって因数分解を進めて行く過程で、「退職後は素人数学者」さんの原アルゴリズムにほぼ沿った形で(グレブナー基底に頼らず)「\(\text{分母}=0\)」の問題に煩わされずに計算する方法があることがわかりました。「ガロア群が可解であるとき、方程式はべき根で解ける」の証明を思い返していて気づきました。以下解説します(以下常体)。

“数式処理ソフトによるガロア群の算出と、べき根を用いた厳密解の表現 その9” の続きを読む

数式処理ソフトによるガロア群の算出と、べき根を用いた厳密解の表現 その8

jurupapa さんが、新しく maxima 用のプログラムを公開されました。

GaloisGroupSolverをGithubに公開しました

“数式処理ソフトによるガロア群の算出と、べき根を用いた厳密解の表現 その8” の続きを読む

数式処理ソフトによるガロア群の算出と、べき根を用いた厳密解の表現 その7

\(\newcommand{\field}[1]{\mathbb{#1}}\newcommand{\Q}{\field{Q}}\)
「最小分解体の原始元 \(V\) で各解 \(\alpha_{1}, \alpha_{2}, \dotsc\) を表す式」の求め方について、これまでよりもずっと計算量が少なくて済む技法があることがわかりました。私は勉強不足で知らなかったのですが、その技法とは「代数拡大体上での因数分解」で、おそらく代数屋さんなら100万回くらいは見たことのある話なんだろうと思います。

“数式処理ソフトによるガロア群の算出と、べき根を用いた厳密解の表現 その7” の続きを読む

数式処理ソフトによるガロア群の算出と、べき根を用いた厳密解の表現 その6

前記事での「退職後は素人数学者」さんからの報告により、方程式 \(x^{3}-2=0\) については「退職後は素人数学者」さんのプログラムと jurupapa さんのプログラムでは結果が異なり、

「退職後は素人数学者」さんは解が出たが、それは不適な解も含んだものになった
jurupapa さんは計算の途中で \(0\) による割り算が発生し、エラーで手続きが停止する

ということになっています。

不可解なのは、同じアルゴリズムに従っているはずの2つのプログラムの動作がなぜか異なっていたことでしたが、おおよその事情がわかってきたので報告します。これまでの検討から、\(x^{3}-2=0\) を解く際の一連の異常には

べき根の選び方の不定性によって、\(0\) になる可能性も、ならない可能性もあるような式

が深く関わっていることがわかってきました(ここで、「べき根の選び方の不定性」というのは、\(1\) の原始 \(p\) 乗根の具体的な表式に含まれるべき根に関するものも含んでおり、\(1\) の原始 \(p\) 乗根の \(p-1\) 通りの不定性も包含したものとする)。実は、「退職後は素人数学者」さんの元記事「可解な代数方程式のガロア理論に基づいた解法」の第11節の、拡大体での商の計算(「分母の有理化」)のアルゴリズム(以下、アルゴリズム A とします)は、このような「べき根の不定性によって、\(0\) になる可能性がある式」が分母にある時はうまく行かない時があることがわかりました。おそらくこれが一連の問題の根っこにあります。
“数式処理ソフトによるガロア群の算出と、べき根を用いた厳密解の表現 その6” の続きを読む