[GAP Forum] GaloisType is running very long
Alexander Hulpke
hulpke at math.colostate.edu
Mon Dec 29 18:11:34 GMT 2014
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);
More information about the Forum
mailing list