Re: decomposition of polynomials

In article <slrne1g080.36i.a282244@xxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Helmut Richter <hhr-m@xxxxxx> wrote:

Let f be a polynomial over Z. It is a well-known task with smart known
solutions to find polynomials g and h over Z such that f(x)=g(x)h(x)
if such g and h exist. But I have never seen solutions to the problem
to find polynomials g and h over Z such that f(x)=g(h(x)) if such g
and h exist.

That's a big "if", in the following sense.

Suppose I hand you a polynomial of degree 6. I do so by giving you
7 integers, or equivalently 6 rational numbers -- you might as well
assume that f, g, and h are monic polynomials in Q[x] because
you can move around the constant terms from factor to factor.
Now, for you to factor f as g h, you have to come up with, say,
a quadratic factor and a quartic factor, or two cubics, etc. In
each case, you need to come up with a total of 6 rational numbers --
the coefficients of g and h, partitioned according to the degrees
you think g and h have. You can if you like treat this as a
set of 6 equations (one for each coefficient in f) in 6 unknowns
(one for each coefficient in g and h ). As you may know, this
typically has a finite solution set over the complex numbers, which
of course makes perfect sense here -- there is a unique (up to order)
factorization of f into monic linear factors over C, and those
factors can be grouped in just a few ways to make g and h.

Now let's play the game again but trying to "factor" f as g o h .
(Again we start with f of degree 6.) The key difference now is
that the degree of g o h is the _product_ of the degrees of g and h.
So we have fewer possible pairs of degrees to consider, and they are
smaller degrees. You might consider, for example, the possibility
that g is a quadratic and h is a cubic. Well, again you can
write out the equations which state that f = g o h and compare
coefficients. You again have 6 equations, one for each coefficient
in f, but now only 5 unknown coefficients in g and h. That's
very different from the previous paragraph -- 6 equations in 5
unknowns are likely to be contradictory, meaning that there are
no solutions at all. (It's actually a little worse than this --
the equations are also a little redundant in the sense that if one
factorization is possible then there are multiple factorizations
since we can compose g and h with linear functions; so after
solving just 4 of the equations, you'll already run out of variables.)
In this way we conclude that most polynomials of any fixed degree are
likely to be irreducible -- over any field, not just Q -- in the
sense that f = g o h ==> deg(g)=1 or deg(h)=1.

(A sextic x^6 + q5 x^5 + ... is decomposable as cubic o quadratic iff
-q5^5+3*q5^3*q4+81*q1-27*q2*q5 = -27*q3-5*q5^3+18*q5*q4 = 0
and it's decomposable the other way iff
5*q5^4-24*q5^2*q4+16*q4^2-64*q2+32*q5*q3
= -64*q1-q5^5+8*q5^3*q4-16*q5*q4^2-8*q3*q5^2+32*q3*q4 = 0 .)

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

See also these news articles by Bill Dubuque, which also give citations
to the literature:
<y8zn06nl4kr.fsf@xxxxxxxxxxxxxxxxx>
<y8zy8yy9500.fsf@xxxxxxxxxxxxxxxxx>

dave
.

Relevant Pages

  • Integrating Rational Functions
    ... as a linear combination of a rational function, ... tangents of polynomials of degree 1, ... of which will have real number coefficients. ... has complex roots that show up in complex conjugate ...
    (sci.math)
  • Re: sparse polynomial arithmetic
    ... polynomials and the program operates under the *assumption* that ... but polynomials over multiprecision coefficients. ... "know" in advance that coefficients aren't going to overflow, ... so any comparison with a format ...
    (sci.math.symbolic)
  • Re: sparse polynomial arithmetic
    ... polynomials and the program operates under the *assumption* that ... but polynomials over multiprecision coefficients. ... "know" in advance that coefficients aren't going to overflow, ... so any comparison with a format ...
    (sci.math.symbolic)
  • Re: Genetic Algorithms for factorize multivariate polynomials
    ... integer powers rather than integer coefficients, ... and both of the candidate factor polynomials for these values. ... selection and no selection. ... and X and Y are different then in the offspring replace them with one ...
    (comp.ai.genetic)
  • functional translations and coefficient extraction (exponential sum decompositions)
    ... is the functional relation between exponentiation and translation ... and then coefficients of the inverse can be extracted ... which is precisely what is needed for the generalised berneulers ... also notice that this can be used on generalised trigonometric polynomials ...
    (sci.math)