Bill Daly on Wed, 11 Feb 2009 20:42:20 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Splitting field


(I've tried sending messages to pari-users before, but something was always screwed up. I hope it's fixed by now.)

Anyway, I looked for a simple way to generate the splitting field of a polynomial but didn't find one, so I wrote one:

splittingpol(f) =
{
   local(h,fac,g,v);
   h = f;
   while(1,
       fac = lift(factornf(f,subst(h,x,r)));
       g = fac[matsize(fac)[1],1];
       if (poldegree(g,x) < 2,
           v = vector(matsize(fac)[1],j,
               -polcoeff(fac[j,1],0,x)
           );
           return([h,v]);
       );
       h = rnfequation(nfinit(subst(h,x,r)),g);
   );
}

It assumes that factornf() always returns factors in increasing order by degree; if this is not the case, I could do a search for an appropriate factor g of degree > 1, returning if all the factors are linear.

f must be a polynomial in x. splittingpol(f) returns a vector with 2 components:

[1] = a polynomial in x which represents the splitting field of f;
[2] = a vector of length poldegree(f) whose components are the roots of f in terms of a root r of the splitting polynomial.

It works as follows. During each iteration of the main loop, I factor f in the number field of the current value of h (initially, h is set to f), using r as the root of the number field generated by h. I take g to be the factor of highest degree in x (the coefficients of g are generally polynomials in r). If the degree of g in x is 1, then all of the factors are linear and I am done. Otherwise, I use rnfequation() to replace h with a polynomial (in x) which represents the field containing g over the field generated by subst(h,x,r). This gives me a field containing the roots of f augmented by the roots of g. By repeating this loop, I must eventually arrive at a polynomial h which contains all the roots of f.

This may provide a relatively quick way of finding the Galois group of f.

Regards, Bill