Is there a good argument why the pre-images $f^{-1}(\{ y\})$ for $f:k\to k, f(x)=x^4+x$ and $k=\Bbb{F}_{2^m}^\times$ has cardinality $4$? Let $f: \mathbb{F}_{2^m}^\times \to \mathbb{F}_{2^m}^\times$, $x \mapsto x^4 + x$.
While using Magma, I noticed that for $m=12$, it is
$
|f^{-1}(y)| = 4
$
for all $y \in im(f)$. I am quite curious if and why this is true for all $m \geq 3$.
The argument would be easy if $f$ would be a group homomorphism (which it is not, unfortunately). I guess it still has something to do with the form of $x^4 + x$ but I cannot understand the main point here.
Could you please help me here? Thank you!
 A: It is, indeed, the case that the non-empty preimages of singletons here have either four or two elements according to whether $m$ is even or odd. Your observations can be explained a bit more generally by using the theory of so called linearized polynomials, but that is the high road. First the low road.

Because we are in characteristic two $(x+y)^2=x^2+y^2$ and consequently also $(x+y)^4=x^4+y^4$. It follows that $f(x)=x^4+x$ is a homomorphism of additive groups from $\Bbb{F}_{2^m}$ to itself.
You hopefully know that the non-empty preimage of a singleton under a homomorphism is a coset of the kernel $N=\operatorname{ker}(f)$. This is because $f(x)=f(y)$ if and only if $f(x-y)=0$ if and only if $y\in x+N$. You excluded the element $0$ from  the reckoning, but the only effect this has on the mapping properties of $f$ is that the preimage of $0$ itself contains one element less.
So the key to answering your question is to identify the kernel of $f$. Obviously $f(0)=0$ and $f(1)=1+1=0$. What else? Because $f$ is a polynomial of degree four, it cannot have more than four zeros, and hence the kernel has at most four elements.
Anyway, we need to solve the equation
$$
0=f(x)=x^4+x=x(x^3+1)=x(x^3-1).
$$
We see that the other zeros are roots of unity of order three because they satisfy the equation $x^3=1$. Those exist in $\Bbb{F}_{2^m}$ if and only if $3\mid 2^m-1$. That is, if and only if $2\mid m$.
If $\omega$ is a non-trivial third root of unity, then $\omega^2$ is another. So

*

*$N=\{0,1\}$ when $m$ is odd, in which case $f^{-1}(\{z\})$ is either empty or has two elements differing from each other by one, and

*$N=\{0,1,\omega,\omega^2\}$ when $m$ is even. Observe that $x^3-1=(x-1)(x^2+x+1)$, so $\omega$ satisfies the equation $\omega^2=\omega+1$. After all $N$ must be an additive subgroup. In this case $f^{-1}(\{z\})$ is either empty or has four elements forming a coset of $N$.


Then the high road.
Let $k=\overline{\Bbb{F}_2}$ be an algebraic closure. I think of it as just an umbrella field that is a union of the finite fields $\Bbb{F}_{2^m}$ for all $m$ and with the subfield relations fixed in place. Again, the mapping $F:x\mapsto x^2$ is an additive homomorphism from $k$ to itself that also maps every finite subfield of $k$ to itself. It follows that all the sums of iterates of $F$, that is, polynomials of the form
$$L(x)=\sum_{i=0}^na_ix^{2^i}=a_0x+a_1x^2+a_2x^4+a_3x^8+\cdots a_nx^{2^n},$$
where the coefficients $a_i\in\Bbb{F}_2$ are also additive homomorphfisms. These are the linearized polynomials, and they all share the properties:

*

*$L(x+y)=L(x)+L(y)$ for all $x,y\in k$, and

*$L(x)\in\Bbb{F}_{2^m}$ whenever $x\in\Bbb{F}_{2^m}$.

Their key mapping properties include

*

*The zeros of $L(x)$ are simple if and only if $a_0=1$. This is because the derivative $L'(x)=a_0$ should not vanish at a zero for it to be simple. On the other hand, if $a_0=0$ then $L(x)=\left(\sum_{i=1}^na_ix^{2^{i-1}}\right)^2$, so all the zeros have multiplicity $>1$ (should we have $a_0=a_1=0$ etc it is easy to iterate this).

*Assuming $a_0=1=a_n$, then in the algebraic closure $k$  the polynomial $L$ has $2^n$ zeros. They form an $\Bbb{F}_2$-subspace $N$ that we can think of simply as the kernel of $L$. By linear algebra, every coset $z+N$, $z\in k$, is mapped to a single point $L(z)\in k$.

*Consequently, the restriction of $L$ to a finite subfield $\Bbb{F}_{2^m}$ has $N_m:=N\cap \Bbb{F}_{2^m}$ as its kernel. Again, by basic linear algebra, the cosets of $N_m$ are the non-empty preimages of singletons of such a restriction.

Basic examples of linearized polynomials include

*

*$L_\ell(x)=x+x^{2^\ell}$. It is well known that the roots of $L_\ell(x)$ are exactly the elements of $\Bbb{F}_{2^\ell}$. Hence $N=\Bbb{F}_{2^\ell}$ and the kernel of the restriction to $\Bbb{F}_{2^m}$ is thus $N_m=\Bbb{F}_{2^\ell}\cap \Bbb{F}_{2^m}=\Bbb{F}_2^d$ with $d=\gcd(m,\ell)$. This is relevant to your question. The kernel (and hence any non-empty preimage of a singleton) has size two or four according to whether $m$ is odd or even.

*$T_\ell(x)=x+x^2+x^4+x^8+\cdots+x^{2^{\ell-1}}$ is more commonly only known as the trace of $\Bbb{F}_{2^\ell}$. All its zeros are, in fact, in the subfield $\Bbb{F}_{2^\ell}$. This is a consequence of the fact that $T_\ell(x)+T_\ell(x)^2=L_\ell(x)$, where $L_\ell(x)$ is from the previous bullet.

So as an example, if, instead of the $f(x)$ in the question you look at the mapping
$$L(x)=T_3(x)=x^4+x^2+x$$
from $\Bbb{F}_{2^m}$ to itself, the kernel $N_m$ will be contained in the intersection $\Bbb{F}_{2^m}\cap \Bbb{F}_{2^3}$. If $3\mid m$ it follows that the kernel has four elements. On the other hand, if $3\nmid m$, the kernel is contained in the prime field $\Bbb{F}_2$. However, $T_3(1)=1$, so $1\notin N$. It follows that the kernel of the restriction $N_m=N\cap\Bbb{F}_{2^m}=\{0\}$ is trivial. Consequently the restriction of $T_3(x)$ to $\Bbb{F}_{2^m}$, $3\nmid m$, is injective.

More complicated linearized polynomials can be handled by viewing $k$ as a module over the polynomial ring $\Bbb{F}_2[\tau]$ where the indeterminate $\tau$ acts on $k$ via the Frobenius automorphism $F$. In this process the linearized polynomial $L(x)=\sum_ia_ix^{2^i}$ gets replaced by the action of its conventional associate $\sum_ia_i\tau^i$. See e.g. Lidl & Niederreiter, David Goss's book or Michael Rosen's book for more.
