3
$\begingroup$

Let $f_b(x)=x^3+x+b$ where $b \in \mathbb F_{2^k}^*$ where $k$ is is odd. Let $2^k=n$. Then

$(n+1)/3$ of them is irreducible,

$(n-2)/2$ of them have $1$ solution,

$(n-2)/6$ of them have $3$ solutions. (over $\mathbb F_{2^k}$).

Question: Are these numbers known for even case?

$\endgroup$

2 Answers 2

2
$\begingroup$

The number of all the monic, irreducible polynomials over $\mathbb{K}=\mathbb{F}_{2^{k}}\simeq\mathbb{F}_2[x]/(h(x))$, with degree $3$, is given by $\frac{2^{3k}-2^k}{3}$ (see this question). If $q(x)$ is one of such polynomials, for some (exactly one) $\tau\in\mathbb{K}$ we have: $$ q(x+\tau) = x^3 + Ax+B,\qquad A,B\in\mathbb{K}. $$ Assume now $A\neq 0$. If $3$ is not a divisor of $|\mathbb{K}^*|$, every element of $\mathbb{K}$ is the cube of something, hence by considering $\frac{1}{\kappa^3}q(\kappa x+\tau)$ every monic, irreducible polynomial $q(x)$ can be associated with a polynomial of the type $x^3+x+C$ with $C\in\mathbb{K}$, and the association is essentially $2^{2k}$-to-$1$, so we have $\frac{n+1}{3}$ irreducible polynomials of the wanted type. The number of monic, irreducible polynomials with degree $2$ is $\frac{2^{2k}-2^k}{2}$, and since $2$ never divides $|\mathbb{K}^*|$, the number of polynomials of the given type with exactly one root in $\mathbb{K}$ is $\frac{n-2}{2}$. The remaining $\frac{n-2}{6}$ completely split over $\mathbb{K}$.

Now we have to understand what happens if $3$ divides $|\mathbb{K}^*|$, i.e. what happens if $k$ is even. In such a case, only $\frac{2^k-1}{3}$ elements of $\mathbb{K}$ are the cube of something, hence not every polynomial of the type $x^3+Ax+B$ can be mapped into a polynomial of the type $x^3+x+C$ by a linear transformation. However, a polynomial $r(x)=x^3+x+C$ is irreducible in $\mathbb{K}$ iff $r(a)\neq 0$ for every $a\in\mathbb{K}$, hence the number of different $C$s for which $r(x)$ is irreducible just depends on the size of $\{a^3+a:a\in\mathbb{K}\}$. Now $a^3+a=b^3+b$, with $a\neq b$, implies $a^2+ab+b^2=-1$.

Can you finish from here? At last we have that the number of polynomials belonging to the cases irreducible/just one root/completely splits is still around $\frac{n}{3}$/$\frac{n}{2}$/$\frac{n}{6}$ also if $k$ is even.

$\endgroup$
1
$\begingroup$

Many ways to skin this cat. I use as a starting point the following well known solvability condition of quadratic equations over a finite field of characteristic two. Here we need the trace function $$ tr:\Bbb{F}_{2^k}\to\Bbb{F}_2,tr(x)=x+x^2+x^4+x^8+\cdots+x^{2^{k-1}}. $$

Fact. The equation $$x^2+Bx+A=0$$ with $A,B\in\Bbb{F}_{2^k}, B\neq0$, has two solutions $x\in\Bbb{F}_{2^k}$ if $tr(A/B^2)=0$ and no solutions otherwise.

We will also need the fact that the trace is a surjective homomorphism of additive groups, and is stable under Frobenius, i.e. $tr(x^2)=tr(x)$. Therefore it takes both values $n/2$ times, and $tr(1)=k$ is zero or one according to the parity of $k$.

Because $f_b'(x)=x^2+1$ we see that the polynomial $f_b$ has zeros of multiplicity $>1$, iff $b=0$. Clearly $f_0(x)=0\Leftrightarrow x\in\{0,1\}$. So if we denote by $\Bbb{F}_n^{**}=\Bbb{F}_n\setminus\{0,1\}$ then each $x\in\Bbb{F}_n^{**}$ is a zero of some $f_b(x)$ for exactly one choice of $b\neq0$, namely $b=f_0(x)=x^3+x$.

This leads us to study the mapping properties of $f_0$. As was also pointed out in Jack's answer we have $$ \begin{aligned} &&f_0(x)&=f_0(a)\\ \Leftrightarrow&&(x+a)(x^2+ax+a^2+1)&=0. \end{aligned} $$ Assume that $a\in\Bbb{F}_{2^k}^{**}$. The above fact gives us that the quadratic factor has two zeros $x$, iff $$ tr(\frac{a^2+1}{a^2})=0\Leftrightarrow tr(\frac1a)=tr(1). $$ Here $1/a$ ranges over $\Bbb{F}_{2^k}^{**}$ as $a$ does. Therefore this trace condition is satisfied by $(n-2)/2$ elements $a\in\Bbb{F}_{2^k}^{**}$ if $k$ is odd, and by $(n-4)/2$ elements if $k$ is even.

To summarize:

  • the restriction of the polynomial mapping $f_0$ to the set $$S_3=\{a\in\Bbb{F}^{**}\mid tr(1/a)=tr(1)\}$$ is 3-to-1, and
  • the restriction of the polynomial mapping $f_0$ to the set $$S_1=\{a\in\Bbb{F}^{**}\mid tr(1/a)\neq tr(1)\}$$ is 1-to-1,
  • and $f_0(S_3)\cap f_0(S_1)=\emptyset$.

Consequently

  • The polynomial $f_b(x)$ has three zeros for $|S_3|/3$ choices of $b\neq0$. If $k$ is even (resp. odd) this number is $(n-4)/6$ (resp. $(n-2)/6$).
  • The polynomial $f_b(x)$ has a single zero for $|S_1|$ choices of $b\neq0$. If $k$ is even (resp. odd) this number is $n/2$ (resp. $(n-2)/2$).
  • The polynomial $f_b(x)$ has no zeros for $$n-1-|S_1|-\frac{|S_3|}3=\frac{n-(-1)^k}3$$ choices of $b\neq0$.
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .