Re: decomposition of polynomials

In article <dvanks$v80$1@xxxxxxxxxxxxxxxxx>
rusin@xxxxxxxxxxxxxxxxxxxxx (Dave Rusin) writes:
In article <Iw72Fz.CL2@xxxxxx>,
Peter L. Montgomery <Peter-Lawrence.Montgomery@xxxxxx> wrote:

In article <dv9i9h$tdu$1@xxxxxxxxxxxxxxxxx>
rusin@xxxxxxxxxxxxxxxxxxxxx (Dave Rusin) writes:

More high-falutin' responses are also possible. Look for
"polynomial decomposition", "primitive Galois group", and widen
your search to the more general problem of finding g, h with
f | (g o h) instead of f = g o h .
If you'd like to try your hand at this, consider the following
interesting example proposed when this question was asked in July 2001:
x^6+235*x^5+1430*x^4+1695*x^3+270*x^2-229*x+1

If we let alpha be a root of y^3 - y^2 - 2*y + 1,
then the sextic splits over the field Q(alpha, sqrt(21)).

Ah, good -- thanks for doing the hard work (not sure I remember how
you would do that!). Allow me to use this to illustrate my prior remarks.

Peter notes that the intermediate quadratic subfield in the splitting
field for this polynomial is K = Q(sqrt(21)). Sure enough, the polynomial
factors into two cubics over K. They are p +- sqrt(21) q where
p(x) = x^3+235/2*x^2+229/2*x-1 and q(x) = 49/2*x*(x+1).

So now if x is any root of f, it makes the product of these two
sums vanish, so p(x) is either sqrt(21) q(x) or its negative, so
that p(x)^2 - 21 q(x)^2 = 0, i.e. ( p(x)/q(x) )^2 - 21 = 0.

If it weren't for that darn q(x) in there, we would conclude that
the sextic is exactly the composite f = g o p where g(x) = x^2 - 21,
because that equation relates two monic sextics with equal roots!

We can do _something_ with the q there as well, but we don't quite
get a decomposition of f. Note that if as above x is any of the
roots of f, then 1/q(x) lies in the field Q(x) generated by x,
but this field is the same as the polynomial ring Q[x], so that
we may write 1/q as a _polynomial_ in x. In this particular
case that's not too hard: since f(x)=0, 1 = x * ((1-f(x))/x), and
that second factor is a polynomial in x , so we have a polynomial
inverse for x itself; you can do likewise to get an inverse for
y=x+1 (first rewrite f as a polynomial in y). Multiply these
two inverses together to get an inverse for q(x) (up to a constant).
Don't forget that you can throw away any multiple of f(x).
Likewise we can then multiply out p(x) * 1/q(x) and reduce mod f
to get a small polynomial which equals p(x)/q(x) whenever x is
a root of f(x). Carrying out this prescription I get this to be
h(x) = ( 938*x^4+5252*x^3+4*x^5+4388*x^2+84*x-225 )/49

Now we make the same observation as I made above when pretending
there was no q(x) : h(x)^2-21 vanishes whenever x is a root of f ;
except that now h^2 - 21 is of higher degree than f, so we don't
get equality, we get divisibility. Sure enough, you can calculate that
if h is as above and g(x) = x^2 - 21 then f | g o h since g o h =
4/2401 * (4*x^4+936*x^3+4785*x^2+2229*x+51)* f(x) .

You can reverse the logic of all this: if you have somehow found two
polynomials g and h with f | g o h, then any root x of f
would make g(h(x))=0, i.e. h(x) is one of the roots r_i of g.
So the field extension can be done in two steps, first up to the
splitting field of g, then adjoining the solutions to each
equation h(x) - r_i .

This particular sextic happens to have cylic galois group, so you
can view the splitting field either as a cubic extension of a quadratic
extension, as I did above, or a quadratic extension of a cubic extension.

Someone suggested using the Chain Rule to decide whether f is a
composite, which is clever but I don't see any way to use that for
the broader problem of finding composites which are _multiples_ of f.

dave

Let alpha denote a root of f. Another way to view the field f(alpha) is
Q(w21 + 1/w21) = Q(cos(2*pi/21)), where w21 is a primitive 21-st root of unity.
This is the real subfield of Q(w21). The galois group is cyclic of order 6,
and has four subgroups, all normal. So there are four subfields. These are

Q(cos(2*pi/21)) (degree 6)
Q(cos(2*pi/7)) (degree 3)
Q(cos(2*pi/21) + cos(8*pi/21) + cos(10*pi/21)) (degree 2)
Q (degree 1)

If you pick a polynomial h so that h(alpha) in the subfield of
degree 2 or 3, then h(alpha) will be the root of a
quadratic or cubic, say g(h(alpha)) = 0.
Then f(x) divides g(h(x)).

--
VP Cheney Burr-ed his gun as a bird flew past The nation responds "burr"
as we await bird flu shots and fight a real cold war.

pmontgom@xxxxxx Microsoft Research and CWI Home: Bellevue, WA
.

Relevant Pages

  • Re: decomposition of polynomials
    ... So now if x is any root of f, it makes the product of these two ... Don't forget that you can throw away any multiple of f. ... polynomials g and h with f | g o h, then any root x of f ... So the field extension can be done in two steps, ...
    (sci.math)
  • Re: Another Galois theory problem
    ... luck proving if it is perfect, it has the pth root property. ... it is an algebraic extension. ... It is generated by adjoining roots of polynomials, ... that r is a multiple root of x^p-a, ...
    (sci.math)
  • Re: Another Galois theory problem
    ... luck proving if it is perfect, it has the pth root property. ... it is an algebraic extension. ... polynomials agree everywhere does not imply they are the same ...
    (sci.math)
  • Re: JSH: JSH Paper proven totally wrong 5 years ago by many, so why is JSH still whining now ?
    ... to address) produce an incorrect result. ... result about algebraic integers. ... I have proposed that these polynomials ... xo is a root of p, then ris a root of the ...
    (sci.math)
  • Re: Question on algebraic numbers
    ... The algebraic closure of Q is, of course, formed by ... adjoining to Q the roots of all polynomials over Q. ... written as some finite expressions of integers. ... that any solvable root of a monic polynomial with integral coefficients ...
    (sci.math)