Vrftsjtryk

This question is inspired by this thread which is on hold at the moment. Fix a field $k$. Let $P(x)in k[x]$ be such that $$(1) P(x^2)=P(-x)P(x).$$
Let $T(k,d)subseteq k[x]$ denote the set of solutions to $(1)$ of degree $d$, and $t(k,d)=big|T(k,d)big|$. Constant solutions are obviously $Pequiv 0$ and $Pequiv 1$. So $T(k,0)={0,1}$ and $t(k,0)=2$. We assume from now on that $d>0$, so $P(x)$ is non-constant.

Questions: (a) Is it possible to list all elements of $T(k,d)$? (b) How to calculate $t(k,d)$? (If this is too broad, we can take $k$ to be $Bbb R$ or $Bbb C$.)

Here is my attempt. If $zin overline{k}$ is a root of $P(x)$, then $z^{2^n}$ is a root of $P(x)$ for every $n$. Since $P$ has finitely many roots, we must have $z=0$ or $z^{2^n-1}=1$ for some positive integer $n$. Suppose that $0$ is a root of $P(x)$ of multiplicity $m_0$. Then, $P(x)=x^{m_0}P_1(x)$ for some $P_1(x)in k[x]$ such that $P_1(0)neq 0$. Using $(1)$ we get
$$(2) P_1(x^2)=(-1)^{m_0}P_1(-x)P_1(x).$$

Let $m_1$ be the smallest positive integer such that $P_1(x)$ has a root $w_1inoverline k$ such that $w_1^{2^{m_1}-1}=1$. Because $m_1$ is the smallest possible, $w_1$, $w_1^2$, $w_1^{2^2}$, $ldots$, $w_1^{2^{m_1-1}}$ are pairwise distinct roots of $P_1(x)$. This shows that
$$P_1(x)=prod_{r=0}^{m_1-1}left(x-w_1^{2^r}right)P_2(x),$$
where $P_2(x)inoverline{k}[x]$ satisfies
$$P_2(x^2)=(-1)^{m_0+m_1}P_2(-x)P_2(x).$$

In the end, we can use induction to show that there exist integers $m_0geq 0$, $m_1>0$, $m_2>0$, $dots$, $m_l>0$ such that
$$(3) P(x)=(-1)^d,x^{m_0},W_1(x),W_2(x),cdots,W_l(x),,$$
where $m_0+m_1+m_2+ldots+m_l=d$ and each $W_j(x)in overline{k}[x]$ is of the form
$$prod_{r=0}^{m_j-1},left(x-w_j^{2^{r}}right),,$$
where each $w_jinoverline{k}$ is a root of $z^{2^{m_j}-1}-1$, but not a root of $z^{2^r-1}=1$ for any positive integer $r<m_j$. If $k$ is algebraically closed then $(3)$ is as good a description as you can get, I guess. But what happens when $k$ is not algebraically closed?

In particular, if $d=4$ and $k=Bbb C$, there are the following possible choices:

1. $P(x)=x^4$




2. $P(x)=x^3,(x-1)$




3. $P(x)=x^2,(x-1)^2$




4. $P(x)=x^2,(x^2+x+1)$




5. $P(x)=x,(x-1)^3$




6. $P(x)=x,(x-1),(x^2+x+1)$




7. $P(x)=x,prodlimits_{r=0}^2,Bigg(x-expleft(frac{2pi {2^r} i}{7}right)Bigg)$




8. $P(x)=x,prodlimits_{r=0}^2,Bigg(x-expleft(-frac{2pi {2^r} i}{7}right)Bigg)$




9. $P(x)=(x-1)^4$




10. $P(x)=(x-1)^2,(x^2+x+1)$




11. $P(x)=(x-1),prodlimits_{r=0}^2,Bigg(x-expleft(frac{2pi {2^r} i}{7}right)Bigg)$




12. $P(x)=(x-1),prodlimits_{r=0}^2,Bigg(x-expleft(-frac{2pi {2^r} i}{7}right)Bigg)$




13. $P(x)=(x^2+x+1)^2$




14. $P(x)=prodlimits_{r=0}^3,Bigg(x-expleft(frac{2pi {2^r} i}{15}right)Bigg)$




15. $P(x)=prodlimits_{r=0}^3,Bigg(x-expleft(-frac{2pi {2^r} i}{15}right)Bigg)$




16. $P(x)=x^4+x^3+x^2+x+1$.

Unless I omitted something, this gives $t(Bbb C,4)=16$. Furthermore, only polynomials 1-6, 9-10, 13, 16 have real coefficients (in fact rationals), $t(Bbb R,4)= t(Bbb Q,4)=10$.

If $zin overline{k}$ is a root of $P(x)$, then $z^{2^k}$ is a root of $P(x)$ for every $k$. 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 notin 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 https://math.stackexchange.com/a/3025474/5676, 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.