位数が大きな場合

これまでの RR シリーズでは,分解体の定義多項式,primitive element による入力多項式の根の表示, primitive element を根の \mathbb{Z} 線型結合で表した際の係数を古典的な Trager の方法( http://www.cecm.sfu.ca/personal/monaganm/teaching/TopicsinCA17/TragerFactor.pdf )により( http://ehito.hatenablog.com/entry/2019/02/24/150254 ),また,組成列も共役類の組み合わせ( http://ehito.hatenablog.com/entry/2019/02/13/200937 )から得ていましたが,今回は,galois 群の位数が数百程度の場合にも対応できるよう,外部ツールを用いるスタイルで再び実装しました.ただし,分解体と冪根の中間体上の定義多項式を同時に得るためにかつて用いた Groebner 基底( by asir )による方法は,次数や変数の個数の増大に敏感なため採用せず,同じく,代数体上の因数分解や GCD の利用も最小限に留めています.

具体的には
・分解体の \mathbb{Q} 上の定義多項式には,pari の nfsplitting (LLL アルゴリズムによるもの)
・分解体の primitive element による入力多項式の根の表示には,同じく pari の nfisincl
・galois 群(置換表現および同型写像表現)の生成には,独自アルゴリズム(多倍長浮動小数点数によるもの)
・組成列の生成には,gap の MaximalNormalSubgroups
・円分体およびその部分体上の因数分解には,pari の nfsubfields,nffactor
・分解体の各中間体上の定義多項式には,分解体の primitive element による添加する冪根の表示(1次のみ)を用いた簡約,そのフォールバックとして Lagrange Resolvents の総和
・各中間体上の加減乗除算,GCD 計算には,maxima の algebraic モード,gcd:subres
をそれぞれ利用しています.

以下,取り敢えず,実行データを掲載します.リストの要素は
・サンプル番号
・入力多項式
・galois 群の位数
・各中間体間の拡大次数
・分解体の \mathbb{Q} 上の定義多項式,primitive element による入力多項式の根の表示から,galois 群さらに組成列の生成までの時間(秒)
・分解体の各中間体上の定義多項式の生成から冪根による primitive element の表示までの時間(秒)
・上記2つの時間の合計(秒)
です.

【サンプルセット1】
サンプル番号 16 以降は,先行研究
https://core.ac.uk/download/pdf/81182361.pdf
http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/0920-2.pdf
http://www.jssac.org/Editor/Suushiki/V09/No1/V9N1_108.pdf
http://www.icm.tu-bs.de/ag_algebra/software/distler/Diplom.pdf (RadiRoot https://gap-packages.github.io/radiroot/ の作者の学位論文)

などからのものです.

       [[1,x^2-2,[2],[2],0.708,0.002,0.71],
       [2,x^3-3*x-1,[3],[3],0.552,0.139,0.691],
       [3,x^4-2,[8],[2,2,2],0.37,0.006,0.376],
       [4,x^4+x^2-1,[8],[2,2,2],0.509,0.006,0.515],
       [5,x^4-2*x^3+2*x^2+2,[12],[3,2,2],0.842,0.134,0.976],
       [6,x^4+2*x^3+3*x^2+4*x+5,[24],[2,3,2,2],0.454,0.585,1.04],
       [7,x^4+x+1,[24],[2,3,2,2],0.376,0.829,1.21],
       [8,x^5-2,[20],[2,2,5],1.78,0.387,2.16],
       [9,x^5-5*x+12,[10],[2,5],0.455,0.302,0.757],
       [10,x^5+20*x+32,[10],[2,5],0.941,0.756,1.7],
       [11,x^5+11*x+44,[10],[2,5],0.161,0.404,0.565],
       [12,x^5+x^4-4*x^3-3*x^2+3*x+1,[5],[5],0.277,0.178,0.455],
       [13,x^5+100*x^2+1000,[20],[2,2,5],0.845,0.285,1.13],
       [14,x^6+x^3+1,[6],[2,3],0.519,0.15,0.669],
       [15,x^6-2,[12],[2,2,3],0.396,0.571,0.967],
       [16,x^5-5*x^3+5*x-5,[20],[2,2,5],0.245,0.433,0.678],
       [17,x^6+x^3+7,[18],[2,3,3],0.35,0.106,0.456],
       [18,x^6-3*x^4+1,[24],[2,3,2,2],0.894,0.32,1.21],
       [19,x^6+x^4-9,[24],[2,3,2,2],0.171,0.625,0.796],
       [20,x^6+x^4-8,[48],[2,2,3,2,2],0.734,1.45,2.19],
       [21,x^6+x^4-x^2+5*x-5,[72],[2,2,2,3,3],4.27,34.8,39.1],
       [22,x^7+7*x^3+7*x^2+7*x-1,[14],[2,7],0.163,0.456,0.619],
       [23,x^7-14*x^5+56*x^3-56*x+22,[21],[3,7],0.202,1.34,1.54],
       [24,x^7-2,[42],[2,3,7],0.56,1.29,1.85],
       [25,x^8-2*x^6-x^4+7*x^2-5*x+1,[16],[2,2,2,2],0.479,0.043,0.522],
       [26,x^9+x^8+3*x^6+3*x^3-3*x^2+5*x-1,[18],[2,3,3],0.337,0.321,0.658],
       [27,x^12-3,[24],[2,2,2,3],0.659,0.109,0.768],
       [28,x^7-14*x^5+56*x^3-56*x+22,[21],[3,7],0.538,0.475,1.01],
       [29,
        x^15-x^14-14*x^13+13*x^12+78*x^11-66*x^10-220*x^9+165*x^8+330*x^7
            -210*x^6-252*x^5+126*x^4+84*x^3-28*x^2-8*x+1,[15],[3,5],1.25,
        0.321,1.57]]
       [30,
        x^14+28*x^11+28*x^10-28*x^9+140*x^8+360*x^7+147*x^6+196*x^5+336*x^4
            -546*x^3-532*x^2+896*x+823,[98],[2,7,7],7.114,199.4,206.5]]

サンプル番号 30 の冪根表示.

[[c7^2*(2*e3^4-e3^2+e2^6+e2^3)+c7^3*(2*e3^4+e2^5)+c7*(e3^4-e3^2+3*e2^6+e2^3)
                               +c7^4*(e3^4+3*e2^6+e2^3)+e3
                               +c7^5*(3*e2^6-e2^5+e2^3)+e2^6+e2^5+A,A],
  [e3^7+2*c7^5-c7^4+2*c7^3-c7^2+2*c7,e3],
  [e2^7-4*c7^5-c7^4-3*c7^3-3*c7^2-c7-4,e2],
  [c7^6+c7^5+c7^4+c7^3+c7^2+c7+1,c7]]


【サンプルセット2】
x^n-2\ (n=1,\ldots,30)(一部サンプルセット1と重複).一般の場合の位数は,https://mathoverflow.net/questions/143739/galois-group-of-xn-2 にあります.

      [[1,x-2,[1],[],1.193,0.0,1.193],
       [2,x^2-2,[2],[2],1.147,0.001,1.148],
       [3,x^3-2,[6],[2,3],1.172,0.09,1.262],
       [4,x^4-2,[8],[2,2,2],1.202,0.012,1.214],
       [5,x^5-2,[20],[2,2,5],1.153,0.186,1.339],
       [6,x^6-2,[12],[2,2,3],1.232,0.185,1.417],
       [7,x^7-2,[42],[2,3,7],1.314,0.526,1.84],
       [8,x^8-2,[16],[2,2,2,2],1.252,0.015,1.267],
       [9,x^9-2,[54],[2,3,3,3],1.295,0.21,1.505],
       [10,x^10-2,[40],[2,2,2,5],1.435,3.87,5.305],
       [11,x^11-2,[110],[2,5,11],1.837,0.926,2.763],
       [12,x^12-2,[48],[2,2,2,2,3],1.748,0.281,2.029],
       [13,x^13-2,[156],[2,2,3,13],4.897,1.238,6.135],
       [14,x^14-2,[84],[2,2,3,7],2.074,0.665,2.739],
       [15,x^15-2,[120],[2,2,2,3,5],2.333,1.345,3.678],
       [16,x^16-2,[64],[2,2,2,2,2,2],1.824,0.147,1.971],
       [17,x^17-2,[272],[2,2,2,2,17],13.31,4.305,17.62],
       [18,x^18-2,[108],[2,2,3,3,3],3.449,0.752,4.201],
       [19,x^19-2,[342],[2,3,3,19],18.02,10.46,28.49],
       [20,x^20-2,[160],[2,2,2,2,2,5],7.155,2.767,9.922],
       [21,x^21-2,[252],[2,2,3,3,7],11.41,3.08,14.49],
       [22,x^22-2,[220],[2,2,5,11],15.8,3.614,19.41],
       [23,x^23-2,[506],[2,11,23],58.19,53.77,112.0],
       [24,x^24-2,[96],[2,2,2,2,2,3],2.518,0.941,3.459],
       [25,x^25-2,[500],[2,2,5,5,5],71.24,49.02,120.3],
       [26,x^26-2,[312],[2,2,2,3,13],55.11,8.613,63.72],
       [27,x^27-2,[486],[2,3,3,3,3,3],77.09,53.58,130.7],
       [28,x^28-2,[336],[2,2,2,2,3,7],80.96,19.26,100.2],
       [29,x^29-2,[812],[2,2,7,29],360.1,169.8,529.9],
       [30,x^30-2,[240],[2,2,2,2,3,5],16.68,4.233,20.91]]
Evaluation took 352.3320 seconds (1212.0310 elapsed) using 229011.373 MB.

サンプル番号 29 の冪根表示.

[[e4+A,A],
  [e4^29+89224590*c29^27+20029198*c29^26+16908450*c29^25+155757840*c29^24
        +19982508*c29^23+19792500*c29^22+175147530*c29^21+19079970*c29^20
        +20022702*c29^19+123821880*c29^18+11445720*c29^17+20029952*c29^16
        +60090030*c29^15-20030010*c29^14+20030068*c29^13+28614300*c29^12
        -83761860*c29^11+20037318*c29^10+20980050*c29^9-135087510*c29^8
        +20267520*c29^7+20077512*c29^6-115697820*c29^5+23151570*c29^4
        +20030822*c29^3-49164570*c29^2+40060020*c29+20030010,e4],
  [c29^28+c29^27+c29^26+c29^25+c29^24+c29^23+c29^22+c29^21+c29^20+c29^19
         +c29^18+c29^17+c29^16+c29^15+c29^14+c29^13+c29^12+c29^11+c29^10+c29^9
         +c29^8+c29^7+c29^6+c29^5+c29^4+c29^3+c29^2+c29+1,c29]]