From: Mark McConnell <mmcconn@math.okstate.edu>
Newsgroups: sci.math.symbolic
Subject: Re: Number field extensions and irreducible polynomials
Date: 9 Nov 1995 19:49:51 GMT

cmcquinn@math.unl.edu (Chad J McQuinn) wrote:
>Using Maple or MMA, does anyone know of a way to generate the splitting
>field for an irreducbile polynomial over Q? In Maple, I've found out how
>to do some similar things, such as test for irreducibility of a given
>polynomial over an arbitrary (finite) number field extension, but this one
>eludes me so far.
>Please note that I am not looking for "Solve the polynomial and adjoin the
>roots"- I would like a little more elegance than that.

Let f(x) be the given irred polynomial over Q, of degree n, and K its
splitting field.

I'll be referring to H. Cohen, "A course in computational algebraic
number theory", Springer Grad. Texts in Math #138.

The answer depends on what you mean by "generate K".  I'll
assume you mean writing the splitting field as Q(theta) and figuring
out the minimal polynomial of theta.  This is called finding a primitive
element theta of K.  If alpha_1, ..., alpha_n are the roots of f, we
find a primitive element by induction, finding one for Q(theta_i, alpha_{i+1})
where theta_i is a primitive element of Q(alpha_1, ..., alpha_i).
(Let theta_1 = alpha_1.  Note that theta_{i-1} is the final theta you want.)
The "theorem on the primitive element" says that a primitive
element for Q(theta_i, alpha_{i+1}) is of the form

         theta_i + k * alpha_{i+1}

for almost all rational integers k.  You just keep trying k's at random
until one gives you a primitive element.  See Cohen, end of section 4.5.
The book explains, among other things, how to test whether your
random k has worked.

Before we can do this, we have to know how to add two algebraic numbers.
How do you add alpha and beta, when all you know about these
numbers is a minimal polynomial A(x) for alpha and B(x) for beta?  The answer
is to find R(x), the resultant with respect to y of A(x-y) and B(y).
The roots of R(x) are the various conjugates of alpha+beta.
So the irreducible factors of R(x) over Q[x] --which may have different
degrees--are minimal polynomials for the different possible values of
alpha+beta.  See Cohen, section 4.2.1, and the preceding pages.

In the present case, let T_i(x) be the minimal polynomial of theta_i.
The minimal polynomial of k*alpha_{i+1} is g(x) = k^n*f(x/k).  A
maximal-degree factor of the resultant should be the minimal polynomial
of a primitive element of Q(theta_i, alpha_{i+1}), as long as
k is generic enough.

Hrre's a sample in Maple:

f := x^5 + x + 3:

galois(f);

   its says the Galois group is S_5.  Thus the degree of Q(theta_i) should
   be 5, 5*4, 5*4*3, 5*4*3*2=120 for i=1,2,3,4.  (Note that
   theta_1 = alpha_1.)  In other words,
   we have to do three steps of "construct a new prim element",
   and degree(theta_i) should be 5, 20, 60, 120 resp.

   Let's guess that theta_2 = theta_1 + alpha_2 is a primitive element
   of Q(alpha_1, alpha_2).  In other words, guess k = 1.

resultant(subs(x=x-y, f), subs(x=y, f), y);

   get a polyn of degree 25

factor(");

   it factors as (deg 5) * (deg 10)^2.  Since we don't get any degree 20
   factors, k = 1 was not a good choice.  (I think you can prove that
   it won't be a good choice at the later steps of the induction, either.)
   Now try k = 2.

g := 2^5 * subs(x=y/2, f):
resultant(subs(x=x-y, f), g, y);

   mess of degree 25

factor(");

   there is a factor of degree 20.  Isolate it and call it T2.
   This is the min polynomial of theta_2.

   Now let's try to find a min polynomial for theta_3.  I'll try
   k = 2 again, so I don't have to redefine g.

resultant(subs(x=x-y, T2), g, y);

   [it's probably dumb to substitute the x-y into the bigger polyn,
    since that makes the computations bigger]

   get a 100-degree answer

factor(");

   get (deg 20)(deg 20)(deg 30)^2
   Since I didn't get any deg 60 factor, k = 2 was a bad choice.
   (One could probably have proved that in advance.)
   Try k = 3, chosen at random.

g := 3^5 * subs(x=y/3, f):
factor(resultant(subs(x=x-y, T2), g, y));


   get (deg 20)(deg 20)(deg 60)
   Isolate the deg-60 factor and call it T3.  This is the min polynomial
   of theta_3.

   One more step gets you T4, a deg-120 polynomial that is the min
   polynomial for a primitive element of K/Q.