[GAP Forum] the size of Galois group of a rational polynomial

[Bill Allombert]

On Mon, Jul 29, 2019 at 02:13:42PM +0900, macsyma wrote:
> Dear GAP Forum,
> 
> I'm looking for a quick way to get the size of Galois group of an irreducible integer polynomial f (to speed up PARI's function nfsplitting).
> The method I'm currently trying is what we call "local method" comparing the information of the factorization of f modulo prime numbers with the data of the cyclic index polynomials generated from TransGrp. Here is my PARI/GP's code:
> 
> cnt(M) = [[ss, #select(tt -> ss == tt, M)]|ss <- Set(M)];
> fast_nfsplitting(f) =
> {
>   my(d = poldegree(f));
>   if(d <= 37 && (d-24)*(d-30)*(d-32)*(d-36) <> 0 && polisirreducible(f),
>     my(dc = poldisc(f), P = 0, L = List([]), fd, ci, ds, ans, dd,
>        CId = CI[d]); /* CI is a list s.t. [[[ 1/2*x_1^2+1/2*x_2, 1 ]],
>        [[ 1/3*x_1^3+2/3*x_3, 1 ],[ 1/6*x_1^3+1/2*x_1*x_2+1/3*x_3, 1 ]], ...] */
>     forprime(p = 2, 10^3,
>       if(Mod(dc, p) <> 0,
>         listput(L, fd = factormod(f, p, 1)[, 1]~);
>         if(#fd == d, P++;if(P == 3, break))));
>     ci = vecsum([vecprod([eval(concat("x_", j))|j <- s[1]])*s[2]|s <- cnt(L)])/#L;
>     ds = vecmin([norml2(s[1]-ci)|s <- CId],&j);ans = CId[j];
>     print([ds*1., dd = 1/polcoef(ans[1], d, x_1), ans[2]]);
>     nfsplitting(f, dd),
>   nfsplitting(f))
> };
> /* for(i = 2, 20, fast_nfsplitting(x^i-2));
> time = 960 ms.*/
> 
> However, in the case of DegreeAction = 24, 30, 32, 36,
> it takes a considerable amount of time to generate the CycleIndex data files by my GAP's code:
> 
> tst := function(G)
>   local s;
>   if IsSolvable(G) then s:=1; else s:=0; fi;
>   return([CycleIndex(G),s]);
> end;;
> 
> for n in [2..37] do
>   fn := Concatenation("./CI.",String(n));
>   PrintTo(fn, "[");
>   L := AllTransitiveGroups(DegreeAction, n);
>   for G in L do AppendTo(fn, tst(G), ","); od;
>   AppendTo(fn, "]");
>   # After this, reshape using sed etc.
> od;;
> 
> and even if all the data is obtained, it will be huge so it will take time to search.
> Is there any other better way to get the size of Galois group of f?

PARI/GP has polgalois for degree <=11, GAP has GaloisType() which is
more general but slower. On the other hand, Magma GaloisGroup() function
is the best implementation by far.

We are working on a GAP implementation of some parts of the algorithm
used by magma, but it is not ready yet.

Cheers,
Bill.