位数の取得 - ATPとCASのこと

前回も触れたように，nfsplitting の処理時間は結果の多項式の次数を第二引数として与えることで一般に短縮されます．この性質を利用するため本プログラムでは，その次数，つまり，入力多項式 $f$ の $\mathbb{Q}$ 上の Galois 群 $G$ の位数を，予め用意したある範囲内の全ての cycle index polynomial (https://en.wikipedia.org/wiki/Cycle_index) の中から $G$ の cycle index polynomial $Z(G)$ を特定することで取得しています．

置換群の cycle index polynomial とは，その群に属する元の cycle type ( https://groupprops.subwiki.org/wiki/Cycle_type_of_a_permutation ) の頻度を変数名と次数，そして係数により，一つの多変数多項式で表したもので，群の位数の逆数は（1個しかない）単位元の cycle type の頻度（対応する単項式の係数）として現れます．参照する cycle index polynomial のデータは，次数が $37$ 以下の $f$ の Galois 群を全て含む，GAP の Transitive Groups Library transgrp ( https://www.gap-system.org/Packages/transgrp.html ) から抽出したもので，その制約から次数が $38$ 以上の $f$ についてはノーヒントで nfsplitting を実行しています．なお，同型でない群でも同じ cycle index polynomial を有するものが存在するため，群自体の特定には至らないことはよく目にする注意です．

実際の $f$ から $Z(G)$ を特定するには，前回も引用した「正の数 $M$ 以下で $f$ の判別式の因数ではない素数 $p$ を法とする $f$ の既約因子の次数型（どのような次数の因子がいくつずつあるか）の密度が， $M\to+\infty$ のとき， $G$ の同じ型の cycle type の頻度に収束する」という Chebotarev's density theorem を踏まえ， $p$ が値の小さいほうから 10^3 個目の素数となる，または，単位元の cycle type が 3 回現れるまで，既約分解を繰り返し，各次数型と密度から cycle index polynomial と同じ書式の多項式を作り，用意したデータのうち，この多項式との差の係数ベクトルの $l_2$ ノルムが最小となるものを $Z(G)$ としています．

以下，この処理を組み込んだ関数 nfsplitting2 と標準の nfsplitting の実行例です．

? for(i=1,30,nfsplitting2(x^i-2));
[0,1,1]
[0.03125000000,2,1]
[0.004801097394,6,1]
[0.001226218787,8,1]
[0.0008579881657,20,1]
[0.002494223903,12,1]
[0.0007927650227,42,1]
[0.002837500000,16,1]
[0.0004409526648,54,1]
[0.003434499314,40,1]
[7.133182736E-5,110,1]
[0.001070169231,48,1]
[0.0004472513280,156,1]
[0.002071109694,84,1]
[0.0006910009183,120,1]
[0.001790521626,64,1]
[0.001964397853,272,1]
[0.001106438745,108,1]
[0.0002551165675,342,1]
[0.001759224398,160,1]
[0.001657411051,252,1]
[0.0006244174148,220,1]
[0.001948888552,506,1]
[0.0008731821745,500,1]
[0.0008779652962,312,1]
[0.0003889834061,486,1]
[0.002439757082,336,1]
[0.0008391018743,812,1]
  *** nfsplitting: Warning: increasing stack size to 16000000.
time = 10,490 ms.

? for(i=1,30,nfsplitting(x^i-2));
  *** nfsplitting: Warning: increasing stack size to 16000000.
  *** nfsplitting: Warning: increasing stack size to 32000000.
  *** nfsplitting: Warning: increasing stack size to 64000000.
time = 3min, 24,135 ms.

GAP の組み込み関数 ProbabilityShapes は同じ原理で作動し，例えば

gap> ProbabilityShapes(x^16-x^15-x^14+4*x^13-3*x^12-x^11+5*x^10-7*x^9+2*x^8+4*x^7-5*x^6+5*x^5-x^4-2*x^3+2*x^2-2*x+1);time;
[ 1947 ]
111832
gap> TransitiveGroup(16,1947);
t16n1947
gap> Size(last);
7962624

のように位数を得ることも可能ですが，一般に

? galoisord(x^16-x^15-x^14+4*x^13-3*x^12-x^11+5*x^10-7*x^9+2*x^8+4*x^7-5*x^6+5*x^5-x^4-2*x^3+2*x^2-2*x+1)
time = 90 ms.
%2 = [0.006932446267,7962624,1]

のような高速処理は望めません．