What does polynomials in $x^2$ mean? The context is the following. The function $A(x)$ is split into odd and even powers.
$ 3 + 4x + 6x^2 + 2x^3 + x^4 + 10x^5 = (3 + 6x^2 + x^4) + x(4 + 2x^2 + 10x^4)$
Notice that the terms in parentheses are polynomials in $x^2$. More generally,
$ A(x) = A_e(x^2) + xA_o(x^2) $
What does "polynomials in $ x^2 $" mean? Does it mean $A_e$ or $Ao$ can be divided by $ x^2 $ or root squared?
 A: It means that the variable that appears in the polynomials is $x^2$. It follows a rather straight-forward pattern:

*

*$x^2 + 6x + 3$ is a polynomial in $x$

*$y^2 + 6y + 3$ is a polynomial in $y$

*$t^2 + 6t + 3$ is a polynomial in $t$

*$\dagger^2 + 6{\dagger} + 3$ is a polynomial in $\dagger$

*$*^2 + 6{*} + 3$ is a polynomial in $*$

*$(x^2)^2 + 6x^2 +3$ is a polynomial in $x^2$

*$(x+y)^2 + 6(x+y) + 3$ is a polynomial in $x+y$
Note that in the last two, I needed to use parentheses because the name of the variable contains arithmetic operations in them. And we don't want those "leaking out" into the actual polynomial (at least not at this stage). I could've written $x^4$ instead of $(x^2)^2$, and $(x^2+2xy+y^2)$ instead of $(x+y)^2$, but then the above pattern wouldn't be as visible.
Of course, a polynomial in $x^2$ is also, at the same time, a (different) polynomial in $x$ (for instance, it has double the degree). Spotting when a polynomial in $x$ (or some other plain single-letter variable) is simultaneously a polynomial in some compositely named variable like $x^2$ can be a very powerful tool. For instance in your case, where it is the backbone of the fast Fourier transform (at least that's what that looks like to me).
A: Recall the definition of a polynomial. A polynomial in $x$ can always be written in the form
$$a_nx^n+a_{n-1}x^{n-1}+\cdots+a_2x^2+a_1x+a_0,$$
which is equivalent to
$$\sum_{k=0}^na_kx^k,$$
where $a_0,\ldots a_n$ are constants.
So for a polynomial in $x^2$, replace all $x$s in the above definition with $x^2$, which gives
$$a_n(x^2)^n+a_{n-1}(x^2)^{n-1}+\cdots+a_2(x^2)^2+a_1(x^2)+a_0,$$
which is equivalent to
$$\sum_{k=0}^na_k(x^2)^k = \sum_{k=0}^na_kx^{2k}.$$
So all the powers of a polynomial in $x^2$ will be of the form $2k$, where $k$ is an integer; all the powers will be even.
