五次元世界の冒険

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

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

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

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

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

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

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

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

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

投稿日

カテゴリー:

,

投稿者:

井汲 景太

タグ:

コメント

“数式処理ソフトによるガロア群の算出と、べき根を用いた厳密解の表現 その13” への2件のフィードバック

  1. 退職後は素人数学者のアバター
    退職後は素人数学者

    お久しぶりです。「可解な代数方程式のガロア理論に基づいた解法」の第2版を書いていて，まもなく完成します。前にもお知らせしたとおり，私自身はブログを開設していないため，今回もまた本ブログに投稿させて頂きたいと思います。申し訳ありませんが，よろしくお願い致します。第2版でのおもな変更は以下のとおりです。
    (1)根の間に成り立つn個の関係式r1,r2,…,rnは，根と係数の関係から求めるのではなく，f(x)をx-x1,x-x2,…,x-xnで順次割っていったときの余りとして求めるように変更しました。
    (2)最小多項式g(x)=Π(x-vi)は，x-viをi=1,2,…,n!の順に掛けていくのではなく，x-viをいくつかのグループに分け，グループ毎にx-viの積を求め，最後にこれらを掛け合わせてg(x)を求めるように変更しました。これにより，g(x)の計算時間を大幅に短縮することができました。
    (3)根をvの多項式で表すときの連立1次方程式は，クラメールの方法で解くように変更しました。この方法は行列式を計算するだけなので，LU分解法のような複雑なアルゴリズムはありません。計算時間はLU分解法と同程度です。
    (4)ガロア群の組成列を求めるとき，すべての正規部分群を求めることによって，最大の正規部分群を見落とすことのないように修正しました。
    (5)体を拡大するときに出てくるθi(x)は，まずそのpk乗を計算し，つぎにそのpk乗根を取って戻していましたが，pk乗を経由せずに直接求めるように修正しました。
    (6)べき根の選び方に制約がある場合として，x^3-2=0とx^5-3=0の計算例を追加しました。
    このほかに，6次方程式の計算例も検討しましたが，今の方法では到底不可能であることがわかりました。グレブナー基底を使った新しい方法に期待したいと思います。

    返信
    1. 井汲 景太のアバター
      井汲 景太

      ありがとうございます。書くべきことの内容はだいたい頭の中にあるのですが、他にやりたいことがあるのと、現在の勤め先（と言うか、アルバイト先）での準備に時間を取られるのとでなかなかこちらに着手できません。まだしばらく手つかずとなってしまいそうです。
      改訂版をお送りいただければそれをこちらで公開する程度の時間は取れますので、またよろしくお願いいたします。

      返信

コメントを残す

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください。