From: Mark McConnell 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.