方程式のGalois群を計算するアルゴリズム

昔Galois理論を勉強した時、教科書に載っていた計算例を見ても、一般の方程式に適用可能か分からず、計算至上主義者のわたしは、任意の方程式で使える方法を知りたいと思った。当時は計算機代数を知らずプログラムを書いたことすらなかったので、ちゃんとした定式化には至らなかったけど、今思い出してみると、当時考えていた方向性は正しかったよう。別に難しくはないと思うのだけど教科書とかには、ちゃんと書いてない気がする

#わたしの読んだ教科書にあったGalois群の計算は、最小分解体の適当な基底を取って自己同型を計算する方法と、分解式と対称群の部分群の知識を使って決定する方法が書かれていたように思う。1967年にZassenhausが提案したGalois群を計算するアルゴリズムは後者の方法の延長であるらしい。前者の方法は特別な場合を除けば基底を決定するのが難しい気がする

fを有理数体上の既約多項式として、
(1)代数体上の因数分解を繰り返し適応していけば、fの根$a_1 , \cdots, a_n$を独立な生成元とする最小分解体が得られる。同時に残りの解が、生成元の多項式$g_1 , \cdots , g_m$(但しn+m=deg(f))として具体的に得られ、、$a_1 , \cdots, a_n$が満たす関係式(最小分解体の定義多項式)$h_1= \cdots = h_n=0$も得られる
(2)Galois群の作用は最小分解体の自己同型で有理数体を不変に保つので、生成元の行き先を決めればいい。これらの行き先は(生成元はfの根で自己同型は生成元が満たす関係式を保つ必要があるので)fの根で、高々有限の可能性しかなく、あとはどのmappingが可能であるのか調べればいい。満たすべき条件は、関係式$h_1= \cdots = h_n=0$を保つこと

(1)の最小分解体の計算については、例えばRisa/Asirでspという関数が実装されていて、計算できる。sp関数が、上の$g_1 , \cdots , g_m$と$h_1,\cdots , h_n$を全部決定してくれる
http://www.asir.org/manuals/html-jp/man_212.html

(2)はGalois群の元を全部計算するので、位数が大きい場合は計算が急激に大変になっていくけど、とにかく、どういう変換が生き残るかははっきりする。$mod (h_1 , \cdots , h_n)$の計算を大量にすることになるので、こっちの計算には、一般にはグレブナー基底が必要なはず。代数体係数でもグレブナー基底は計算できるので、fが任意の代数体係数の多項式でもGalois群は計算できる。今は、最小分解体の自己同型からGalois群を計算するアルゴリズムも知られているらしいので、もっと効率的な方法があるかもしれないけど、真面目に調べる気がない。

例1:f=x^3-3*x-1の場合
Risa/Asirでsp(x^3-3*x-1)とやると、最小分解体は一つの元tで生成されて、他の解が-t^2+2とt^2-t-2であることが分かる。あと、勿論h(t)=t^3-3*t-1=0。pをtを変数とする任意の多項式として
e0(p)(t)=p(t)
e1(p)(t)=p(-t^2+2)
e2(p)(t)=p(t^2-t-2)
という3種類の変換が考えられる。e0(h)=e1(h)=e2(h)=0は明らかで、{e0,e1,e2}が求めるべきGalois群をなす
e1(\t->-t^2+2)(t)=-(-t^2+2)^2+2=-t^4+4*t^2-2=t^2-t-2 (mod h)
e1(\t->t^2-t-2)(t)=(-t^2+2)^2-(-t^2+2)-2=t (mod h)
などの計算から具体的な根の置換が得られる。この場合は可能な変換が全て生き残る

例2:f=x^4-2
明らかに、2つの生成元a,bがあり、残りの2解は、-a,-bで、a^2+b^2=f(a)=f(b)=0。変換候補は、4*3=12通りあるけど、(a,b)->(a,-a)とかはa^2+b^2が2*a^2に変換され、これはmod(a^2+b^2,f(a))で0でないので除外される(根の置換としては、-bがaに変換されるので、変換の行き先が衝突してる)。同様に(a,b)->(a,-a),(-a,a),(b,-b),(-b,b)が外れて、Galois群は位数8の群になる

例3:f=x^3-x-1
2つの独立な生成元a,bがあり、残りの1解は-(a+b)。また、a^2+a*b+b^2-1=f(a)=f(b)=0。aとbの入れ替えは明らかにGalois群の元。(a,b)->(-a-b,b)という変換を考えるとf(-a-b)=0は当然成り立つし、
(-a-b)^2+(-a-b)*b+b^2-1=a^2+a*b+b^2-1=0
なので、この変換も問題ない。今の場合全ての互換が生き残るので他はチェックしなくてもGalois群は3次対称群

例4:f=x^5-4*x-1
sp(x^5-4*x-1)によって、最小分解体は4つの生成元a,b,c,dからなり、解は[a,b,c,d,-a-b-c-d]で
d^2+(c+b+a)*d+c^2+(b+a)*c+b^2+b*a+a^2=0
c^3+(b+a)*c^2+(b^2+b*a+a^2)*c+b^3+a*b^2+a^2*b+a^3=0
b^4+a*b^3+a^2*b^2+a^3*b+a^4-4=0
a^5-4*a-1=0
が満たすべき関係式。

もう手計算でやるレベルじゃないので、Risa/Asirでアルゴリズムを実装してみた。Risa/Asirは情報も機能も足りない気がするので、色々辛い。計算すると、群の位数が120であるので、Galois群は5次対称群。この程度の計算なら一瞬で終わる。

2013年3月11日追記)
イデアルによる剰余を計算する関数があったので、コードを修正した
http://www.math.kobe-u.ac.jp/OpenXM/Current/doc/asir2000/html-jp/man_222.html#SEC222

2013年3月17日追記)最小分解体を計算する関数spから情報を取り出して使う方法が分かったので、方程式を引数に取るように変更

Risa/Asirのコード

load("gr");
load("sp");  /* 最小分解体の計算 */

/* 補助関数 */
def select1(CUR , LS){
   RET = [];
   if(length(CUR)==0){
      for(I=0;I<length(LS);I++){
         RET = cons( [LS[I]] , RET);
      }
      return RET;
   }
   for(I = 0 ; I<length(CUR) ; I++){
       TMP = CUR[I];
       NewElems = [];
       for(K=0;K<length(LS);K++){
          OK = 1;
          for(J=0;J<length(TMP);J++){
              if(TMP[J]==LS[K])OK = 0;
          }
          if(OK)NewElems = cons(LS[K] , NewElems);
       }
       for(L=0;L<length(NewElems);L++){
          RET=cons(cons(NewElems[L],TMP) , RET);
       }
   }
   return RET;
}

/* LSの中からN個の要素を抽出したリストのリスト */
def select(LS , N){
   RET = [];
   for(I=0;I<N;I++){
      RET = select1(RET , LS);
   }
   return RET;
}


/*
方程式のGalois群を計算する

返り値は、方程式の解のうち、最小分解体の生成元を与えるものの置換の像
リストの最初の要素が、恒等写像を作用した結果

例:x^4-2の場合(Galois群の位数は8)
galois(x^4-2)は、以下のような結果を返す
[[t#19,t#20],[-t#19,t#20],[t#19,-t#20],[-t#19,-t#20],
[t#20,t#19],[-t#20,t#19],[t#20,-t#19],[-t#20,-t#19]]

方程式の解は、[t#19 , t#20 , -t#19 , -t#20]で、
(t#19,t#20)->(t#19,-t#19)のような解の置換は許されない

*/

def galois(F){
  Sols = sp(F);
  Roots = [];
  Rels = [];
  Vars = [];
  for(I = 0 ; I < length(Sols[0]) ; I++){
     C = coef(Sols[0][I] , 1, var(F));
     Roots = cons(var(F) - algptorat(Sols[0][I])/C , Roots);
  }
  for(I = 0 ; I < length(Sols[1]) ; I++){
     Rels = cons(defpoly(Sols[1][I][0]) , Rels);
     Vars = cons(algptorat(Sols[1][I][0]) , Vars);
  }
  /* ==================== */
  Basis = gr(Rels , Vars , 0);
  Perms = select(Roots , length(Vars));
  TmpVars = [];
  for(I=0;I<length(Vars);I++)TmpVars = cons(uc() , TmpVars);
  Ret = [];
  for(I = 0 ; I < length(Perms) ; I++){
     if( Perms[I]==Vars )continue;
     for(J = 0 ; J<length(Rels) ; J++){
        /* (x,y) -> (p(x,y) , q(x,y))みたいな同時代入を行いたい */
        /* subst(F , x , p(x,y) , y , q(x,y))の結果は */
        /* F(p(x,q(x,y)) , q(x,y))のようになってしまう */
        Expr = Rels[J];
        for(K = 0 ; K < length(Vars) ; K++){
           Perm = Perms[I][K];
           for(L = 0 ;L < length(Vars) ; L++){
              Perm = subst(Perm , Vars[L] , TmpVars[L]);
           }
           Expr = subst(Expr , Vars[K] , Perm);
        }
        for(K = 0 ; K < length(Vars) ; K++){
           Expr = subst(Expr , TmpVars[K] , Vars[K]);
        }
        /* ここまで代入処理 */
        if( p_nf(Expr , Basis , Vars , 0)!=0 )break;
        if( J==length(Rels)-1 )Ret = cons(Perms[I] , Ret);
     }
  }
  return cons(Vars , Ret);
}