# When is a polynomial a composition of a polynomial with some (unspecified) non-linear polynomial?

When can a polynomial be written as a polynomial function of another polynomial? asks whether, given $$p$$ and $$q$$ polynomials, there is a polynomial $$w$$ with $$p(x) = w(q(x))$$ which is a good question with a nice answer. We can try to generalize to ask:

Given a polynomial $$p$$, do there exist polynomials $$q$$ and $$w$$ with $$p(x) = w(q(x)).$$

That is to say, we can ask the question not for a specific $$q$$, but ask whether any such $$q$$ exists.

Alas, that question isn't interesting, for $$q(x) = x$$ and $$w = p$$ provides a solution for any $$p$$; indeed, we can let $$q$$ be any linear polynomial $$q(x) = ax + b$$ with $$a \ne 0$$ and then find $$w$$ (assuming we're working over a field, which is the case I'm thinking of), essentially by substitution. So my question is this:

Given a polynomial $$p$$ over a field, is there a (relatively easy) way to determine whether there's a non-linear polynomial $$q$$ and some polynomial $$w$$ with the property that $$p(x) = w(q(x))?$$

I'd be happy with an answer even over some specific field like $$\Bbb R$$ or $$\Bbb C$$.

• Since $\deg p = \deg w\cdot \deg q$ it it is necessary that $\deg p$ is not prime. This is far from sufficient. (And this assumes both $q$ and $w$ are non-linear.) – Thomas Andrews Jul 18 '19 at 14:55
• Is this math.stackexchange.com/a/672847/42969 the answer to your question? – Martin R Jul 18 '19 at 14:57
• It would be interesting to learn what is known about solving such problems with integer coefficients. – hardmath Jul 18 '19 at 15:53
• 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:18
• When $p(x)=w(q(x))$ has $p'(x)=w'(q(x))q'(x),$ When $p,w,q\in\mathbb Q[x]$, then if $p'(x)$ is irreducible then $p(x)$ can't be written in this form. – Thomas Andrews Jul 18 '19 at 17:19