Using Maple to find the minimum polynomial of an algebraic expression. \251Mike May, S.J., maymk@slu.edu, Saint Louis UniversityA worksheet using a technique described by A.H.M. Levelt, Univ. of Nijmegen. restart:In our study of field theory we have seen that the sums products, quotients,and roots of algebraic expressions are algebraic and have minimal polynomials. Once again, the proof is an existence proof that does not provide the minimal polynomial. One situation where we might want to find the minimal polynomial of an element is when we are trying to show that we have found a primitive element for a field extension. An element is primitive if and only if the degree of the minimal polynomial of an element is the same as the degree of the extension field.Consider for example the field K= Q[NiQtJSVzcXJ0RzYjIiIjLUYkNiMiIiQ=]. We know that K is generated over Q by a single element of order 4. We can guess that NiMvJSJ4RywmLSUlc3FydEc2IyIiIyIiIi1GJzYjIiIkRio= has order 4 and generates K over Q, but the only way to verify this is to find the irreducible polynomial satisfied by x and check its degree. One way to find the irreducible polynomial of x is to use grobner bases in a ring of polynomials over several indeterminates. For this example, consider the polynomial ring R = Q[x, s, t] and the ideal I generated by {NiUsJiokJSJzRyIiIyIiIkYmISIiLCYqJCUidEdGJkYnIiIkRigsKEYlRidGK0YnJSJ4R0Yo}. In R/I, the image of s is NiMtJSVzcXJ0RzYjIiIj, the image of t is NiMtJSVzcXJ0RzYjIiIk and the image of x is NiMsJi0lJXNxcnRHNiMiIiMiIiItRiU2IyIiJEYo. The minimum polynomial of NiMsJi0lJXNxcnRHNiMiIiMiIiItRiU2IyIiJEYo is the monic polynomial in x alone of minimal degree that is in the ideal I. Any polynomial in x that is in the ideal I is satisfied by the element NiMsJi0lJXNxcnRHNiMiIiMiIiItRiU2IyIiJEYo. The Groebner basis command will find such a polynomial.

We first need to load the Groebner package.with(Groebner);Next we define the generators of I and ask Maple to find a gbasis ordering the terms in lexicogrphical ordering with x at the end of the alphabet. (On the first pass, you don't need to understand the last sentence. Just follow the example.)f1:= s^2 - 2; f2:= t^2 - 3; f3:= x - t - s; G:= gbasis([f1, f2, f3],plex(s, t, x));The first element of G is the polynomial we want. We need to check that the polynomial is irreducible and that it is satisfied by x.The Maple command to factor a polynomial f is factor(f);while the command to substitute the value V for the variable X in expression E is subs(X = V, E);F:=factor(G[1]); 'F(sqrt(2) + sqrt(3))' = simplify(subs(x= sqrt(2) + sqrt(3), F));This shows that the polynomail F is irreducible and is satisfied by NiMsJi0lJXNxcnRHNiMiIiMiIiItRiU2IyIiJEYo, it is thus the minimal polynomial for NiMsJi0lJXNxcnRHNiMiIiMiIiItRiU2IyIiJEYo. Since the degree of this polynomial equals the degree of the field extension, Q[NiMsJi0lJXNxcnRHNiMiIiMiIiItRiU2IyIiJEYo] = Q[NiQtJSVzcXJ0RzYjIiIjLUYkNiMiIiQ=]. As a second example let NiMvJSJ4RywoLSUlc3FydEc2IyIiIyIiIi1GJzYjIiIkRiotRic2IyIiJkYq. Find the minimal polynomial of x. f1:= s^2 - 2; f2:= t^2 - 3; f3:= u^2 - 5; f4:= x - s - t - u; G:= gbasis([f1, f2, f3, f4],plex(s, t, u, x));F:=factor(sort(G[1],x)); 'F(sqrt(2) + sqrt(3) + sqrt(5))' = simplify(subs(x=sqrt(2)+sqrt(3)+sqrt(5),F));Thus NiMvJSJ4RywoLSUlc3FydEc2IyIiIyIiIi1GJzYjIiIkRiotRic2IyIiJkYq has degree 8 over Q, and generates Q[NiUtJSVzcXJ0RzYjIiIjLUYkNiMiIiQtRiQ2IyIiJg==].

1) Let NiMlJmFscGhhRw== be a primitive 7th root of unity. (Thus NiMlJmFscGhhRw== is a root of NiMsMCokJSJzRyIiJyIiIiokRiUiIiZGJyokRiUiIiVGJyokRiUiIiRGJyokRiUiIiNGJ0YlRidGJ0Yn.) Find the irreducible cubic equation satisfied by NiMvJSJ4RywmJSZhbHBoYUciIiIqJEYmIiInRic=.

In the previous examples, we factored the last polynomial produced by gbasis, and it has been irreducible each time. It is instructive to consider an example where the polynomial produced is reducible.Let NiMvJSJ4RywoLSUlc3FydEc2IyIiIyIiIi1GJzYjIiIkRiotRic2IyIiJ0Yq. Find the minimal polynomial for x.f1:= s^2 - 2; f2:= t^2 - 3; f3:= u^2 - 6; f4:= x - s - t - u; G:= gbasis([f1, f2, f3, f4],plex(s, t, u, x));F:=factor(G[1]);We now have to check to see which of the factors is satisfied by NiMsKC0lJXNxcnRHNiMiIiMiIiItRiU2IyIiJEYoLUYlNiMiIidGKA==.F1:=op(1,F); 'F1(sqrt(2) + sqrt(3) + sqrt(6))' = simplify(subs(x=sqrt(2)+sqrt(3)+sqrt(6),F1)); F2:=op(2,F); 'F2(sqrt(2) + sqrt(3) + sqrt(6))' = simplify(subs(x=sqrt(2)+sqrt(3)+sqrt(6),F2));Thus the irreducible polynomial of NiMsKC0lJXNxcnRHNiMiIiMiIiItRiU2IyIiJEYoLUYlNiMiIidGKA== is NiMsKiokJSJ4RyIiJSIiIiomIiNBRicqJEYlIiIjRichIiIqJiIjW0YnRiVGJ0YsIiNCRiw=, a polynomial of degree 4. The problem with the last example is that NiMvLSUlc3FydEc2IyIiJyomLUYlNiMiIiMiIiItRiU2IyIiJEYs, so that the field only has degree 4. Equivalently, Q[NiUtJSVzcXJ0RzYjIiIjLUYkNiMiIiQtRiQ2IyIiJw==] = Q[NiQtJSVzcXJ0RzYjIiIjLUYkNiMiIiQ=]. We check this by factoring NiMsJiokJSJ4RyIiIyIiIiIiJyEiIg== over QNiM3JC0lJXNxcnRHNiMiIiMtRiU2IyIiJA==.factor(x^2 - 6, {sqrt(2), sqrt(3)});(You may want to look over the worksheet on factoring examples to refresh yourself with the peculiarities of the factor command.)

The following example shows how to use the procedure with nested roots.We want to find the irreducible polynomial of NiMvJSJ4RywmLSUlc3FydEc2IywmLUYnNiMiIiMiIiItRic2IyIiJEYtRi0tRic2IyIiJkYt.f1:=s^2-2; f2:=t^2-3; f3:=u^2-s-t; f4:=v^2-5; f5:= x - u - v; G:=gbasis([f1,f2,f3,f4,f5],plex(s,t,u,v,x));F:=factor(sort(G[1],x)); 'F(sqrt(sqrt(2) + sqrt(3)) + sqrt(5))' = simplify(subs(x=sqrt(sqrt(2)+sqrt(3))+sqrt(5),F));

There is a thing we would like to do to clean up the process outlined above. We want is to be able to refer to a root of a polynomial with the RootOf construction. Consider the following example to find a minimum polynomial for the sum of the 1st, 3rd, and 5th powers of a primitive 7th root of unity. f1:=simplify((s^7 - 1)/(s - 1)); f2:=x - s - s^3 - s^5; zeta[7] := RootOf(f1); G:=gbasis([f1,f2],plex(s,x)); F:=factor(sort(G[1],x)); 'F(zeta[7] + zeta[7]^3 + zeta[7]^5)' = simplify(subs(x = zeta[7] + zeta[7]^3 + zeta[7]^5,F));

2) Find the degree of x = NiMsJiIiIyIiIi0lJXNxcnRHNiMiIiRGJQ== over Q. 3) Find the degree of x = NiMsKCIiIkYkKSIiIyomRiRGJCIiJCEiIkYkKSIiJUYnRiQ= over Q.4) Find the degree of NiMvJSJ4RykiIiMqJiIiIkYoIiInISIi over Q[NiMtJSVzcXJ0RzYjIiIj].