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