新・方程式のガロア群の求め方 その3

\(\newcommand{\Q}{\mathbb{Q}}\)前回の記事の補足を2つ書く。ひとつは、前回最後に紹介したガロア群発見法で、最後の方が手際よくなかった所の改良。もうひとつは、前回始めの方で書いた「次数に関するふるい分け」の適用範囲をもうちょっと広げられる、という話になる。

“新・方程式のガロア群の求め方 その3” の続きを読む

新・方程式のガロア群の求め方 その2

\(\newcommand{\Q}{\mathbb{Q}}\)予告通り、「ガロア群の(私にとっては)新しい求め方」の話の残りを公開する。ひとつは「前回の求め方で、方程式が可約だった場合」の対処法。残りは、また別のアルゴリズムである。

“新・方程式のガロア群の求め方 その2” の続きを読む

数式処理ソフトによる~ その15 & 新・方程式のガロア群の求め方

\(\newcommand{\Q}{\mathbb{Q}}\)
これまで、与えられた方程式のガロア群を求めたり、可解な方程式の解をべき根で表すことをテーマにして一連の記事を書いてきた。本記事では、その過程にグレブナー基底を利用する方法とその数学的背景、及びガロア群を求める新しいやり方を解説する。後者は、これまで非常に重かった計算をだいぶ軽減できると期待できる………と元々は思っていたのだが、前記事で「退職後は素人数学者」さんが従来の手法での計算時間の大幅な短縮を実現されていたので、そちらでの意義はあんまりないかもしれない(笑)。

“数式処理ソフトによる~ その15 & 新・方程式のガロア群の求め方” の続きを読む

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