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.
_______________________________________________
Forum mailing list
Forum@gap-system.org
https://mail.gap-system.org/mailman/listinfo/forum
