Polynomials $P(x)\in k[x]$ satisfying condition $P(x^2)=P(-x)P(x)$

Solution 1:

If $z\in \overline{k}$ is a root of $P(x)$, then $z^{2^m}$ is a root of $P(x)$ for every $m$. Since $P$ has finitely many roots, we must have $z=0$ or $z^{2^n-1}=1$ for some positive integer $n$.

As I previously mentioned in a comment, I think this argument could do with filling a gap, so I'll start from scratch.

$P(x) \in K[x]$ of degree $d$ satisfies $P(x^2) = P(x)P(-x)$. If we lift to the splitting field of $P$ over $K$, $P(x) = a_d \prod_{i=1}^d (x - \alpha_i)$. By the functional equation, $P(x) = (-1)^d a_d^2 \prod_{i=1}^d (x - \alpha_i^2)$. When $d=0$ we have the exceptional solution $P(x) = 0$; if $P(x)$ is non-zero then $a_d = (-1)^d$ and $\{\alpha_i\} = \{\alpha_i^2\}$ taken as multisets. Therefore there is a permutation $\pi$ for which $\alpha_i^2 = \alpha_{\pi(i)}$. If $i$ is in a cycle of length $n_i$ in $\pi$ then $\alpha^{2^{n_i}} = \alpha_i$, so $\alpha_i = 0$ or $\alpha_i^{2^{n_i}-1} = 1$. If $\alpha_i$ is a non-zero root, it's an odd power of unity, and so there is an odd $m_i$ for which it's a primitive $m_i$th root of unity. Then its minimum cycle length is the multiplicative order of $2 \bmod m_i$, which I will denote $\textrm{ord}_{m_i}(2)$ (or A002326$(\frac{m_i-1}{2})$).

If $\alpha_i \in K$ then that cycle of $\textrm{ord}_{m_i}(2)$ roots does not imply the presence of any other roots. However, if $\alpha_i \not\in K$ then each of the roots in the cycle requires its entire minimal polynomial over $K$, so we account for a factor of the LCM of their minimal polynomials. Therefore the key questions are about how the cyclotomic polynomials split: how many conjugates does each root have, and how many distinct minimal polynomials are covered by a cycle?

I'm not aware of any standard notation for these statistics, so let $c_K(m_i)$ be the number of conjugates of a primitive $m_i$th root of unity over $K$, and $\rho_K(m_i)$ be the number of distinct minimal polynomials covered by a cycle.

In general terms

Let $p$ be the characteristic of $K$. As shown in Proof that there are exactly $n$ distinct $n$th roots of unity in fields of characteristic zero., there are no primitive $n$th roots of unity if $n$ is a multiple of $p$; otherwise there are exactly $\varphi(n)$ (distinct) primitive $n$th roots of unity. (Note that in consequence for characteristic $2$ we don't lose any odd-power primitive roots of unity relative to characteristic $0$).

If there are primitive $m_i$th roots of unity, each comes as part of a set of $c_K(m_i) \rho_K(m_i)$, so there are $\frac{\varphi(m_i)}{c_K(m_i) \rho_K(m_i)}$ such sets. Therefore the generating function for the number of building blocks of $P$ with degree $n$ is (including the exceptional building block of degree one, $\alpha_i = 0$) $$A_K(x) = x + \sum_{\substack{m \textrm{ odd},\\ p \nmid m}} \frac{\varphi(m)}{c_K(m_i) \rho_K(m_i)} x^{c_K(m_i) \rho_K(m_i)}$$ To get a generating function for $t(K,d)$, we take $A_K$'s Euler transform $B_K$ and add $1$ for the exceptional solution $P(x) = 0$.

$K$ is algebraically closed and has characteristic $0$ or $2$

E.g. $K = \mathbb{C}$. The cyclotomics split completely, so the minimal polynomials are linear and $c_K(m_i) = 1$ Obviously this means that $\rho(m_i) = \textrm{ord}_{m_i}(2)$. $$A_{\mathbb{C}}(x) = x + \sum_{m \textrm{ odd}} \frac{\varphi(m)}{\textrm{ord}_m(2)} x^{\textrm{ord}_m(2)}$$

$$\begin{matrix} d & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ A_\mathbb{C} & 0 & 2 & 1 & 2 & 3 & 6 & 9 & 18 & 30 & 56 & 99 & 186 & 335 \\ 1 + B_\mathbb{C} & 2 & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 256 & 512 & 1024 & 2048 & 4096 \end{matrix}$$

$A_\mathbb{C}(n)$ looks suspiciously like OEIS A001037, which is neatly explained by the description

Number of degree-$n$ irreducible polynomials over GF(2)

OEIS also confirms that the Euler transform of A001037 is the powers of $2$, so the conjecture which jumps out from the table is in fact true.

$\mathbb{Q}$

The cyclotomic polynomials are irreducible, so $c_K(m_i) = \varphi(m_i)$ and $\rho(m_i) = 1$. $$A_\mathbb{Q}(x) = x + \sum_{m \textrm{ odd}} x^{\varphi(m)}$$

$$\begin{matrix} d & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ A_\mathbb{Q} & 0 & 2 & 1 & 0 & 1 & 0 & 2 & 0 & 1 & 0 & 1 & 0 & 2 \\ 1 + B_\mathbb{Q} & 2 & 2 & 4 & 6 & 10 & 14 & 22 & 30 & 44 & 58 & 81 & 104 & 143 \end{matrix}$$

Obviously these are the two extremes (for characteristic zero). In between them we have fields where the cyclotomics split partially.

$\mathbb{R}$

The first two cyclotomic polynomials are linear; the rest split into quadratics over $\mathbb{R}$, pairing each complex root of unity with its conjugate, so $c_{\mathbb{R}}(m_i) = 1 + [m_i > 2]$. A cycle contains a root and its square iff $-1$ is a power of $2 \pmod{m_i}$, so $$\rho_{\mathbb{R}}(m_i) = \begin{cases} 1 & m_i = 1 \\ \frac12 \textrm{ord}_{m_i}(2) & 2^j \equiv -1 \pmod{m_i} \\ \textrm{ord}_{m_i}(2) & \textrm{otherwise} \end{cases}$$

The first $m_i$ to diverge from the rational case is $m_i = 17$, which retains its two separate $8$-cycles, so the values obtained are closer to those for $\mathbb{Q}$ than for $\mathbb{R}$.

$$\begin{matrix} d & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ A_\mathbb{R} & 0 & 2 & 1 & 0 & 1 & 0 & 2 & 0 & 3 & 0 & 6 & 0 & 9 \\ 1 + B_\mathbb{R} & 2 & 2 & 4 & 6 & 10 & 14 & 22 & 30 & 46 & 62 & 94 & 126 & 190 \end{matrix}$$

Finite fields

Consider $\mathbb{F}_q$ where $q = p^a$ and $p$ is prime. Cribbing from another MSE answer,

Let $z$ be a primitive $n$th root of unity in an extension of $\mathbb{F}_q$. Let $\mathbb{F}_q[z]=\mathbb{F}_{q^k}$. Because the multiplicative group of $\mathbb{F}_{q^k}$ is cyclic of order $q^k-1$, we know that $k$ is the smallest positive integer with the property that $n \mid q^k-1$. By the Galois theory of finite fields the minimal polynomial of $z$ is $$m(x)=(x-z)(x-z^q)(x-z^{q^2})\cdots(x-z^{q^{k-1}})$$

So if $\alpha$ is a primitive $n$th root, the elements of the cycle are $\alpha^{2^i}$ and the elements of the root set are $(\alpha^{2^i})^{q^j}$. Clearly characteristic $2$ is a special case, and $A_{\mathbb{F}_{2^a}} = A_{\mathbb{C}}$.

Rather than try to add a lot more tables to this answer for other prime characteristics, I've put some code on Github to generate them.