# When can a polynomial be written as a polynomial function of another polynomial?

Given two polynomials $$p(x)$$ and $$g(x)$$, how do I ascertain whether or not $$p(x)$$ is expressible as

$$p(x)= \sum_{i=0}^n a_i (g(x))^i,$$

where $$\{a_i\}_{i=1}^n$$ are constant coefficients.

Example: Let $$p(x)= x^6-3x^4+4x^2-1$$ and $$g(x)= x^2-1$$, then $$p(x)= (g(x))^3+g(x)+1.$$

• You can be sure $p(x)$ is not a polynomial in $g(x)$ if $\deg p$ is not divisible by $\deg g$. – Bernard Jul 18 at 14:18
• For general polynomial decomposition algorithms $\ p(x) = f(g(x))\,$ see my comment here. – Bill Dubuque Jul 19 at 2:20

I'm not sure how to put it in a simple condition, but there's a procedure that allows to check whether $$p(x)=w(g(x))$$ for $$w$$ being a polynomial function.
Let's perform a repeated polynomial division of $$p$$ over $$g$$, that is let $$q_n(x)$$ and $$r_n(x)$$, $$n\in\mathbb N$$ be polynomials such that $$\deg r_n < \deg g$$, $$q_n \neq 0$$ and $$p(x) = q_0(x) g(x) + r_0(x) \\ q_0(x) = q_1(x) g(x) + r_1(x) \\ q_1(x) = q_2(x) g(x) + r_2(x) \\ q_2(x) = q_3(x) g(x) + r_3(x) \\ \dots$$ Such division will always end in a finite number of steps. If all $$r_n$$ are constants, that is $$\deg r_n = 0$$, $$r_n(x) = r_n$$, then $$p(x) = \sum_n r_{n} \big(g(x)\big)^n$$ If at any point we get $$r_n(x)$$ that is not constant, then $$p(x)$$ cannot be expressed as a polynomial of $$g(x)$$.
• @Paracosmiste This is known as the $g$-adic expansion of $\,p\,$ in the general case when the coefficients $r_i$ have degree $< \deg g.\,$ It is easily seen to be unique.. It is analogous to radix expansions of integers and generalizes Taylor series expansions. If is often used to compute partial fraction expansions. – Bill Dubuque Jul 19 at 2:09