[GAP Forum] GaloisType is running very long

[Alexander Hulpke]

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);