カテゴリー
ガロア理論 数学

新・方程式のガロア群の求め方 & ガロア群が可解である方程式の解き方 その5

\(\newcommand{\Q}{\mathbb{Q}}\renewcommand{\dotsc}{\cdots}\newcommand{\zettaiti}[1]{\lvert #1 \rvert}\)先日の記事で可約な方程式の解を実際にべき根で求める手順では、step2 では、一旦原始元 \(u\) に関する処理に還元し、また新しい \(g_{\beta}(x)\) の算出には一般には多項式の GCD 計算を用いる、という流れになっていた。しかし、その後色々考察を進めた結果、これはまだ無駄のある方針だった。せっかくのガロア理論の教えを私は十分に生かせておらず、その核心部「中間体と部分群の1体1対応」への眼差しが不十分だった。ここでは、GCD 計算なしで \(g_{\beta}(x)\) を求める手順を説明する。さらに、より一般に全 step を通じて \(g_{\alpha}(x), g_{\beta}(x), g_{\gamma}(x), \dotsc\) のどれがその step での既約分解対象になるかということも、一貫性のある形で早い段階で特定できることもわかった。

以下説明する。

カテゴリー
ガロア理論 数学

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

\(\newcommand{\Q}{\mathbb{Q}}\renewcommand{\dotsc}{\cdots}\DeclareMathOperator{\Res}{Res}\DeclareMathOperator{\Gal}{Gal}\)最近の記事を書いてきた知見から、従来の原始元 \(V\) を使う方法での計算について、計算効率を上げられる箇所が3ヵ所ほどあることに気づきましたので、紹介します。

カテゴリー
ガロア理論 数学

新・方程式のガロア群の求め方 & ガロア群が可解である方程式の解き方 その4

\(\newcommand{\Q}{\mathbb{Q}}\renewcommand{\dotsc}{\cdots}\DeclareMathOperator{\Res}{Res}\DeclareMathOperator{\Gal}{Gal}\)先日の、(私のこれまでの記事の中では)ガロア群の新しい求め方として公開した方法の改良について説明する。

先日書いたやり方では、方程式 \(f(x)=0\) の解 \(\alpha\) 1個だけを \(\Q\) に添加した \(\Q(\alpha)\) では \(f(x)\) の最小分解体にならなくて、他の解 \(\beta\) を添加した \(\Q(\alpha, \beta)\) で \(f(x)\) の \(2\) 次以上の因子を既約分解しようとする際、かなり計算が大変になる道筋を辿っていた。すなわち、\(u=\alpha+ c\beta\) が \(\Q(\alpha, \beta)\) を単拡大で作れる原始元となるような整数 \(c\) を見つけ、その \(u\) の \(\Q\) 上の最小多項式を求め、\(\alpha\), \(\beta\) を \(u\) の \(\Q\) 係数多項式として表し、\(f(x)\) の因子を \(\Q(u)\) 係数の多項式として表して \(\Q(u)\) 係数の範囲での因数分解を行っていた。

しかしこの場合、\(u\) の \(\Q\) 上の最小多項式も、\(\alpha\), \(\beta\) を \(u\) の \(\Q\) 係数多項式として表した式も、\(f(x)\) の因子を \(\Q(u)\) 係数の多項式として表した式も、\(u\) の多項式としてかなり次数が高くなり、それだけならまだしもその係数にかなり桁数の大きな数が出てきてしまうという問題があった。

そこで、今度はちょっと別の道筋を採り、原始元 \(u\) を持ち出さずにあくまで \(\alpha\), \(\beta\) の文字式として計算を進めるやり方を書いてみる。以前の記事でこのやり方を採らなかったのは、そのとき想定していたやり方だと maxima での計算に手間がかかってしまうのと(つまり、maxima での実装を漠然と想定していた)、求まったガロア群が可解群だった場合に実際にべき根を使って解を求めるやり方の見通しが立っていなかったからだが、前者についてはやや緩和でき、後者についても考察を続けて解決できたのでこうやって紹介することにする。

以下、\(f(x)=x^{6}-2\) を題材に取る。

カテゴリー
ガロア理論 数学

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

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

カテゴリー
ガロア理論 数学

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

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

カテゴリー
ガロア理論 数学

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

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

カテゴリー
ガロア理論 数学

数式処理ソフトによるガロア群の算出と、べき根を用いた厳密解の表現 その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 は開催しないことになってしまいました。そうなると気になってくるのは去年の後始末です。結局、「数学の決闘」の解答は未公開のままでした。運営サイドには終了後すぐに公開用の解答は提出してあったのですが…。このままだとお蔵入りになってしまうので、ここで個人的に公開することにします。

カテゴリー
ガロア理論 数学

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

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

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