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.
