Polynomial decomposition test
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.)
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.
If $f(x)=g(h(x))$ then $\deg f=\deg g\deg h$, so you should factor $\deg f$ to look for candidate degrees.
If $\deg f$ is prime, the anwer is trivially "no".
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.
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.
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)
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.
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.
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'$.