Proof that field trace in $GF(2^k)$ maps half of the elements to 0 and the other half to 1.

Question

I'm reading a proof on the solutions of equation $a = z^z + z$ in $GF(2^k)$, that is, the finite field with $2^k$. At some point it uses that the trace function defined as $Tr(a) = a + a^2 + \cdots + a^{2^{k-1}}$ maps half of the elements of $GF(2^k)$ to 0 and half of the elements to 1. I'm trying to proof it.

My approach

The solutions of the equations are proved to be of the form $\theta$ and $\theta + 1$. As the trace is linear we have $Tr(\theta + 1) = Tr(\theta) + Tr(1)$.

If k is odd then $Tr(1) = 1 + 1^2 + \cdots + 1^{2^{k-1}} = 1$ so it is natural to define from the set $$A = \{ a \in GF(2^k):Tr(a) = 0\}$$ to $$B = \{ a \in GF(2^k):Tr(a) = 1\}$$ the mapping $f(a) = a+1$.

This mapping appears to me to a bijection.

What happens if k is even?

Answer 1

The trace is a linear form, so it is a map

$$Tr: GF(2^k)\to GF(2).$$

But then linear algebra tells us (rank-nullity) that the null space of this surjective (see below) map is isomorphic to $GF(2^{k-1})$, because it is a vector subspace of $GF(2^k)$ of dimension $k-1$. By definition the null space is things that map to $0$, and the cardinality is clearly half of all the elements, so the rest must go to $1$.

• This is surjective because $Tr$ is the sum of the Galois conjugates, and you know the Galois group is cyclic and generated by $x\mapsto x^2$, so anything of trace $0$ satisfies $x+x^2+x^4+x^8+\ldots +x^{2^{k-1}}=0$. But only $2^{k-1}$ things can possibly satisfy this, so something has trace $1$.