6

I have a polynomial of degree at least 4. How can I test if it is the composition of two other polynomials of degree at least 2? (Any polynomial is the composition of two polynomials if you allow one to be linear, of course.)

Bill Dubuque
  • 272,048
Charles
  • 32,122
  • 3
    There are efficient polynomial decomposition algorithms due to Ritt, Barton and Zippel, Kozen and Landau, etc, e.g. see here.. These are used in computer algebra systems. – Bill Dubuque Jul 18 '19 at 16:19

2 Answers2

10

James Rickards answers this question with his paper "When Is a Polynomial a Composition of Other Polynomials?" in The American Mathematical Monthly (118:4, pp. 358-363). In particular, a polynomial of degree $mn$ can be written as a composition of polynomials of degree $m$ and $n$ exactly when the roots of the polynomial can be partitioned into multisets $S_1,\ldots,S_m$ with $n$ elements each such that, for $0<j<n,$ $$ \sigma_j(S_1)=\cdots=\sigma_j(S_m) $$ where $\sigma_j$ is the $j$th symmetric polynomial.

Charles
  • 32,122
  • See http://www.jstor.org/stable/10.4169/amer.math.monthly.118.04.358. – lhf Feb 11 '14 at 21:18
  • 2
    The 2011 Math Monthly paper above is still not available through My JSTOR accounts, but an interesting summary is given by Ed Barbeau in the final section of these classroom notes. It turns out that James Rickards was (at the time) a high school student in Ottawa ON. – hardmath Jul 21 '15 at 23:04
3

If $f(x)=g(h(x))$ then $\deg f=\deg g\deg h$, so you should factor $\deg f$ to look for candidate degrees.

  1. If $\deg f$ is prime, the anwer is trivially "no".

  2. Another case where the decomposition is obvious is when all monomials in $f$ have exponents a multiple of some $d$; then $h(x)=x^d$ works.

  3. It may be worthwhile to apply a linear substitution to $f$ to get rid of the second-highest power of $x$; maybe that produces case 2.

  4. To check for quadratic $h$, a suitable linear substitution would make $h$ an even function; then $f$ becomes even as well (which is in fact contained in case 2 above; quadratic $h$ can always be assumed to be just $x^2$ after linear substitution)

  5. To check for cubic $h$, a suitable linear substitution plus vertical offset (that can be eaten up by $g$) makes $h$ and hence also $f$ odd; the substitution is again the one from 2 and must produce only odd exponents. For small degrees, the conditions on the coefficients may be checked manually.

  6. In all of the above, roots of $h$ are also roots of $f$, so finding some of the latter and trying to combine some $h$ from some of them may be promising.

  7. A different approach is to note that $f'(x)=h'(x)g'(h(x))$ so that any roots of $h'$ are also roots of $f'$.

Hagen von Eitzen
  • 374,180