[GAP Forum] GaloisType is running very long

[Daniel Blazewicz]

Thank you very much for immediate answer and code fix. Seems your patch works fine.

Best wishes,
Daniel Błażewicz

Od: "Alexander Hulpke" <hulpke at math.colostate.edu>
Do: "Daniel Blazewicz" <klajok at interia.pl>; 
Wysłane: 19:12 Poniedziałek 2014-12-29
Temat: Re: [GAP Forum] GaloisType is running very long

> Dear Forum, Dear Daniel Blazewicz,
> 
> > I was executing GaloisType method for several irreducible polynomials of the form x^12+ax+b to find solvable examples. And my loop "hung" at x^12+63*x-450. After 2 days I decided to break the execution. FYI, I use 4 years old laptop with ~2GHz CPU. Do you know if it is expected that GaloisType method can take days (weeks?) for polynomials of 12th degree?
> 
> Yes and No.
> 
> Why No:
> In your case there actually is a minor bug (a routine for approximating a root iterates between two approximations without stopping). This will be fixed in the next release. Thank you very much for reporting it. (I append the (pathetic -- it shows my lack of knowledge of numerical analysis) routine if you want an immediate patch.)
> 
> What I would recommend for a search like yours is to call
> ProbabilityShapes
> on the polynomial first. If it returns S_n (or A_n) as only possibilities -- and this will happen in most cases -- the result is correct and you presumably can eliminate the polynomial.
> 
> Why Yes:
> If you happen upon a polynomial whose Galois group is M_{12} the certificate for distinguishing it from A_{12} is very expensive. Such a calculation will possibly take weeks. (ProbabilityShapes should be done always quickly, but does not guarantee that a Galois group cannot be larger.)
> 
> Best wishes,
> 
>     Alexander Hulpke
> 
> -- Colorado State University, Department of Mathematics,
> Weber Building, 1874 Campus Delivery, Fort Collins, CO 80523-1874, USA
> email: hulpke at math.colostate.edu, Phone: ++1-970-4914288
> http://www.math.colostate.edu/~hulpke
> 
> 
> BindGlobal("ApproximateRoot",function(arg)
> local r,e,f,x,nf,lf,c,store,letzt;
>   r:=arg[1];
>   e:=arg[2];
> 
>   store:= e<=10 and IsInt(r) and 0<=r and r<=100;
>   if store and IsBound(APPROXROOTS[e]) and IsBound(APPROXROOTS[e][r+1])
>     then return APPROXROOTS[e][r+1];
>   fi;
> 
>   if Length(arg)>2 then
>     f:=arg[3];
>   else
>     f:=10;
>   fi; 
>   x:=RootInt(NumeratorRat(r),e)/RootInt(DenominatorRat(r),e);
>   nf:=r;
>   c:=0;
>   letzt:=[];
>   repeat
>     lf:=nf;
>     Add(letzt,x);
>     x:=ApproxRational(1/e*((e-1)*x+r/(x^(e-1))),f+6);
>     nf:=AbsInt(x^e-r);
>     if nf=0 then
>       c:=6;
>     else
>       if nf>lf then
>         lf:=nf/lf;
>       else
>         lf:=lf/nf;
>       fi;
>       if lf<2 then
>         c:=c+1;
>       else
>         c:=0;
>       fi;
>     fi;
>   # until 3 times no improvement
>   until c>2 or x in letzt;
>   if store then
>     if not IsBound(APPROXROOTS[e]) then
>       APPROXROOTS[e]:=[];
>     fi;
>     APPROXROOTS[e][r+1]:=x;
>   fi;
>   return x;
> end);
> 
> 
> 
> 
>