Solutions of affine polynomials in characteristic $2$

Question

I will give an example for expressing where I stuck about affine polynomials:

---

Let $\alpha \in \mathbb F_{2^k}^*$. Let $L_{\alpha}(x)=x^4+x^2+\alpha x$ be a linearized polynomial over $\mathbb F_{2^n}$ with $k \mid n$. What is $\{x \in \mathbb F_{2^n} \: | \: L_\alpha(x)\in \mathbb F_{2^{m}}\}$ where $m \geq1$ and $k \mid m$?

---

Process:

Firstly Since $L_\alpha : \mathbb F_{2^n} \to \mathbb F_{2^n}$, we have $\{x \in \mathbb F_{2^n} \: | \: L_\alpha(x)\in \mathbb F_{2^{m}}\}=\{x \in \mathbb F_{2^n} \: | \: L_\alpha(x)\in \mathbb F_{2^{(m,n)}}\}$. Therefore assume $m \mid n$.

There are $3$ possibilities for factorization of $L_{\alpha}$ in $\mathbb F_{2^k}$. (see factorization of $x^3+x+b$)

Now if $x^3+x+\alpha$ is irreducible over $\mathbb F_{2^k}$ we can write $x^3+x+\alpha=(x-w)(x-w^{2^k})(x-w^{2^{2k}})$ where $w \in \mathbb F_{2^{3k}}$. Since $0,w,w^{2^k},w^{2^{2k}}$ is root of $L_\alpha$, if $3k \not \mid n$, then $\{x \in \mathbb F_{2^n} \: | \: L_\alpha(x)\in \mathbb F_{2^{m}}\}=\mathbb F_{2^m}$ $\{x \in \mathbb F_{2^n} \: | \: L_\alpha(x)\in \mathbb F_{2^{m}}\}=\{0+\mathbb F_{2^m},w+\mathbb F_{2^m},w^{2^k}+\mathbb F_{2^m},w^{2^{2k}}+\mathbb F_{2^m} \}$ (abuse of set).

I just confused for the other cases: (maybe above case is wrong too?)

if $x^3+x+\alpha$ has one root in $\mathbb F_{2^k}$, $\cdots$

if $x^3+x+\alpha$ has three roots in $\mathbb F_{2^k}$, $\cdots$

---

see Morgan's answer: Since $x^{2^{m+2}} + x^{2^{m+1}} + \alpha x^{2^{m}} + x^{4}+x^{2}+\alpha x $ is linearized polynomial, the solution space is vector space over $\mathbb F_2$ and includes the $\mathbb F_{2^m}$. Since degree of the polynomial Morgan wrote is $2^{m+2}$. There are $3$ possibilities for dimension: $m,m+1$, or $m+2$. Moreover $L_{\alpha}$ has $1=2^0,2=2^1$, or $4=2^2$ solution(s). I think that this space need to be related with $x^4+x^2+\alpha x$ in easy way.

Furthermore, (symbolically) $x^{2^{m+2}} + x^{2^{m+1}} + \alpha x^{2^{m}} + x^{4}+x^{2}+\alpha x =(x^{2^m}-x)\otimes L_{\alpha}(x)=L_\alpha(x)\otimes(x^{2^m}-x)$.

---

I want to note that symbolically division works. I probably made a mistake in computation part.

Answer 1

An alternate approach: $L_{\alpha}(x) \in \mathbb{F}_{2^{m}}$ if and only if $(L_{\alpha}(x))^{2^{m}} = L_{\alpha}(x)$. Plugging this in we have $$x^{2^{m+2}} + x^{2^{m+1}} + \alpha x^{2^{m}} + x^{4}+x^{2}+\alpha x = 0.$$

From this it is clear that every element of $\mathbb{F}_{2^{m}}$ satisfies this equation. Furthermore, if $\omega$ is a root of $x^{4}+x^{2}+\alpha x$, then $\omega$ also satisfies this equation, as does $\omega + b$ for all $b \in \mathbb{F}_{2^{m}}$. So the dimension of $\{x \in \mathbb{F}_{2^{n}} \mid L_{\alpha}(x) \in \mathbb{F}_{2^{m}}\}$ depends on how many zeroes $x^{3}+x+\alpha$ has that are not in $\mathbb{F}_{2^{m}}$. (I'm not sure where $k$ comes into play.)

Answer 2

For $K$ a finite field containing $\alpha$, let $\phi_K(x) = x^{|K|}$ and $\psi_K(x) = \phi_K(x)+x$.
$L_\alpha, \phi_K, \psi_K$ are all $\Bbb F_2$-linear maps on $\overline K$.

Let $G_\alpha = \{0,u,v,u+v\}$ be the group of solutions (in $\overline{K}$) to $x^4+x^2+\alpha x = 0$, so that $L_\alpha(x) = x(x+u)(x+v)(x+u+v)$.

For any $x \in \overline K$, the roots of $L_\alpha(X) + L_\alpha(x)$ are $\{x+g \mid g \in G_\alpha \}$, and

$\psi_K(x) \in G_\alpha \iff \phi_K(x) = x+g, g \in G_\alpha \iff L_\alpha(\phi_K(x)) = L_\alpha(x) \iff \phi_K(L_\alpha(x)) = L_\alpha(x) \iff L_\alpha(x) \in K$

If $L_\alpha(x) =L_\alpha(y)$ then $y=x+g$, and so $\psi_K(y) = \psi_K(x)+\psi_K(g)$.
For $y \in K$, $L_\alpha(X)+y$ has a root $x$ in $K$ if and only if there is an $x$ such that $L_\alpha(x) =y$ and $\psi_K(x) = 0$.

Hence we get an isomorphism $\chi_{\alpha,K} : K/L_\alpha(K) \to G_\alpha/\psi_K(G_\alpha)$, defined by $\chi_{\alpha,K}(L_\alpha(x)) = \psi_K(x)$, that takes an element $y \in K$ and tells us how $\phi_K$ acts on the root of $L_\alpha(X)+y$.

(note that $|G_\alpha / \psi_K(G_\alpha) | = | \ker \psi_K|_{G_\alpha} | = |G_\alpha \cap K|$, so those two are isomorphic, but not canonically as far as I know)

(also this screams cohomology : if $\mathcal G = Gal(\overline K / K)$,
we have a short exact sequence of $\mathcal G$-modules $0 \to G_\alpha \to \overline K \xrightarrow{L_\alpha} \overline K \to 0$. This gives a long exact sequence $0 \to G_\alpha \cap K \to K \xrightarrow{L_\alpha} K \xrightarrow{\chi_{\alpha,K}} H^1(G_\alpha) \to H^1(\overline K)=0$ hence the isomorphism )

---

If $G_\alpha \subset K$ then $\psi_K(G_\alpha)$ is trivial, $L_\alpha(K)$ is a subspace of $K$ of codimension $2$ and we have an isomorphism $K/L_\alpha(K) \to G_\alpha$. The polynomials $L_\alpha(X) + y$ completely split $1/4$ of the time, and have two quadratic factors $3/4$ of the time. $\chi_{\alpha,K}$ even tells us how to combine the roots to make the factors.

If $G_\alpha \cap K = \{0,u\}$ then $\psi_K(G_\alpha) = \{0,u\}$. $L_\alpha(K)$ is a subspace of codimension $1$. If $y \in L_\alpha(K)$ then $L_\alpha(X)+y$ has two roots $x,x+u \in K$ and a pair of roots $(x+v,x+u+v)$ in the quadratic extension of $K$. If not then it is irreducible, and $\phi_K$ acts like $(x \mapsto x+v \mapsto x+u \mapsto x+v+u \mapsto x)$

If $G_\alpha \cap K = \{0\}$ then $\phi_K$ permutes the nonzero elements of $G$ cyclically, $\psi_K(G_\alpha) = G_\alpha$, and $K = L_\alpha(K)$ so $L_\alpha(X)+y$ has one linear factor and one cubic factor, forall $y \in K$.

This should be enough to answer your questions.