6

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

Mars Plastic
  • 4,239
aditya gupta
  • 370

1 Answers1

18

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

Adam Latosiński
  • 10,558
  • Is there a reference? – user5402 Jul 18 '19 at 23:02
  • 3
    @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 '19 at 02:09