Number of solns of $x^6+x=a$ in $\mathbb{F}_{2^m}$, where $m\geq 3$ is odd is same as number of solns of $x^2+ax+1=0$

I am reading a proof that narrows down to the following statement:

It is easy to see that the number of solutions of $x^6+x=a$ in $\mathbb{F}_{2^m}$, where $a\in \mathbb{F}_{2^m}$ and $m\geq 3$ is odd, is same as number of solutions of $x^2+ax+1=0$ in $\mathbb{F}_{2^m}$.

Why is this true? They say that $x^7=1$ for $x \neq 0$, which I also don't see. Thank you!

Solution 1:

This is only a proof that $f(x)=x^6+x$ is two-to-one on $\Bbb F_{2^m}$ when $m$ is odd.

Let $K = \Bbb F_2(a)$ and $M = \Bbb F_2(x)$. Let $L$ be the Galois closure of $M$ over $K$ and $G = Gal(L/K)$ Pick an element in $\Bbb F_4 \setminus \Bbb F_2$ and call it $\omega$. It is a primitive third root of unity.

We suspect that $M$ is a curve defined over $\Bbb F_4$, so first we need to determine the subgroup $G' = Gal(L / F_4(x)) \subset G$.
By looking at the map $f(x) = x^6+x$ over large-ish fields (say $\Bbb F_{2^{20}}$) and using the Cebotarev density theorem for function fields, we can observe that $|G'| = 60$ and it has $20,24,15,1$ elements with respectively $0,1,2,6$ fixed points.
This is enough to determine that it is isomorphic to $A_5$, and acts on the $6$ roots as $A_5$ acts by conjugation on its six $C_5$ subgroups

From this, we get the existence of a bunch of formulas :
If $\{p,q\}$ is any unordered pair of roots of $f(x)-a$, then the remaining four roots split into two pairs :
The pair $\{r,s\}$ with $r+s = \omega(p+q)$ and $rs = p^2+\omega pq+q^2$
And the pair $\{u,v\}$ with $u+v = \omega^2(p+q)$ and $uv = p^2+\omega^2 pq+q^2$.
You can notice that $pq+rs+uv = 0$.
The presence of $\omega$ in those formulas witness the fact that the Galois closure is defined over $\Bbb F_4$ and not $\Bbb F_2$, and that the behaviour of $f$ depends so much on the parity of $m$.

Also, since $r$ is a root of $X^2 + \omega(p+q)X + (p^2+\omega pq+q^2)$, you have $\omega = (p^2+q^2+r^2)/(pq+qr+pr)$ so just by knowing $r$ you can recover the knowledge of which pair you are in.
And so, if you know three roots, $p,q,r$ then you know a value for $\omega$, and then you know the remaining three roots

$s = r+\omega(p+q), u = q+\omega(p+r), v = p+\omega(q+r)$

Finally, if you look at a stabilizer in $A_5$ (or $S_5$) and pick something in its fixed subfield, you get $\Bbb F_4((p+q)^3)$ (or $\Bbb F_2((p+q)^3)$). The expression $(p+q)^3$ has five possible values, and $G$ is exactly the full permutation group on them.

Now the most important thing to take away from this is that $\omega = (p+q+r)^2/(pq+qr+pr) \in \Bbb F_4$,
or equivalently that for any three distinct roots $p,q,r$,
$(p+q+r)^4 + (p+q+r)^2(pq+qr+pr) + (pq+qr+pr)^2 = 0$.

To show this algebraically, multiply the expression with $(p+q)(q+r)(p+r)$ to get $p^6(q+r) + q^6(p+r) + r^6(p+q)$, which is then reduced to $(p+a)(q+r) + (q+a)(p+r) + (r+a)(p+q) = 0$

Since the only elements $y,z \in \Bbb F_{2^m}$ satisfying $y^2+yz+z^2 = 0$ are $y=z=0$, this implies that any degree $3$ factor over $\Bbb F_{2^m}$ has the form $(x+p)(x+q)(x+r) = x^3+0x^2+0x+pqr =x^3+pqr$, and so if it had a degree $3$ factor, it would factor as $(x^3+y)(x^3+z)$ for some $y,z \in \Bbb F_{2^m}$. But this is obviously impossible because the coefficient of $x$ is $1$ in $f$ but $0$ in this product.

This is also valid over $\Bbb F_{2^{5m}}$ so this also prevents a factorisation into factors of degree $1$ and $5$.

Looking in detail at the action of $S_5 \setminus A_5$, their cycle decompositions (and so the possible factorisations into irreducibles) are $(114)$ half the time, $(222)$ a sixth of the time, and $(6)$ a third of the time.

As for recognizing the range of $f$, I don't see a general method. It can't coincide with the image of a degree $2$ rational fraction for all odd $m$ at once (I don't think it's even possible for individual values of $m \neq 3$), because this would correspond to a subgroup of index $2$ in $S_5$ which is not $A_5$.

Solution 2:

This is not a solution, it is more of a suggestion. If you are not as familiar with Galois theory, you can try brute force. Try contradiction. Suppose that $x^6+x+a=0$ has at least three solutions. Then this means that $x^6+x+a=g(x)f(x)$, where $g$ and $f$ are polynomials of degree $3$. That is, you can express

$$x^6+x+a=(a_3x^3+a_2x^2+a_1x+a_0)(b_3x^3+b_2x^2+b_1x+b_0)$$ $$=a_3b_3x^6+(a_3b_2+a_2b_3)x^5+(a_3b_1+a_2b_2+a_1b_3)x^4+(a_3b_0+a_2b_1+a_1b_2+a_0b_3)x^3+(a_2b_0+a_1b_1+a_0b_0)x^2+(a_1b_0+a_0b_1)x+a_0b_0$$

By comparing coefficients you would obtain $$a_3b_3=1,$$ $$a_3b_2+a_2b_3=0,$$ $$a_3b_1+a_2b_2+a_1b_3=0,$$ $$a_3b_0+a_2b_1+a_1b_2+a_0b_3=0,$$ $$a_2b_0+a_1b_1+a_0b_0=0,$$ $$a_1b_0+a_0b_1=1,$$ and $$a_0b_0=a.$$

From there you can use those relations to obtain a contradiction.