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.$$

  • 4
    $\begingroup$ You can be sure $p(x)$ is not a polynomial in $g(x)$ if $\deg p$ is not divisible by $\deg g$. $\endgroup$ – Bernard Jul 18 at 14:18
  • 1
    $\begingroup$ For general polynomial decomposition algorithms $\ p(x) = f(g(x))\,$ see my comment here. $\endgroup$ – 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)$.

  • $\begingroup$ Is there a reference? $\endgroup$ – Paracosmiste Jul 18 at 23:02
  • 2
    $\begingroup$ @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. $\endgroup$ – Bill Dubuque Jul 19 at 2:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.