For any prime $p$, one can realize any finite field $\Bbb F_{p^n}$ as the quotient of the ring $\Bbb F_p[X]$ by the maximal ideal generated by an irreducible polynomial $f$ of degree $n$. By dividing by the leading coefficient, we may as well assume $f$ is monic, in which case we can write it as
$$f(X) = X^n + a_{n – 1} X^n + \cdots + a_1 X + a_0.
\def\co{\color{#00bf00}{1}}
\def\ct{\color{#0000ff}{2}}
\def\ch{\color{#bf00bf}{3}}
\def\cf{\color{#ff0000}{4}}
\def\ci{\color{#ff7f00}{5}}
$$
If we let $\zeta$ denote a root of $f$, then $\Bbb F_{p^n} \cong \Bbb F_p[X] / \langle f \rangle \cong \Bbb F_p[\zeta]$, and so when computing multiplication in this field and write elements as polynomials in $\zeta$ of degree $< n$, one way or another we use iteratively the identity
$$\zeta^n = -a_{n – 1} \zeta^{n – 1} – \cdots – a_1 \zeta – a_0.$$
Manually multiplying elements in this field is naively more efficient, then, when one chooses a polynomial $f$ with fewer nonzero coefficients.
So, naturally, we can ask just how efficient we can be:
For any prime $p$ and any positive integer $n > 1$, what is the least number $\lambda(p, n)$ of nonzero coefficients an irreducible polynomial of degree $n$ over $\Bbb F_p$ can have?
Some general observations:
- The only polynomial of degree $n$ with exactly one nonzero coefficient is $X^n$, $\lambda(p, n) > 1$.
- Jim Belk's answer shows that there is an irreducible polynomial of the form $X^n + a$, that is, $\lambda(p, n) = 2$, if $p \not\mid n$ and $p$ has order $n$ modulo $n (p – 1)$. Thus, if these criteria do not hold for $(p, n)$, we have $\lambda(p, n) \geq 3$.
Case $p = 2$. Several behaviors are peculiar to the case $p = 2$. First, if $f(X) \in \Bbb F_p[X]$ has an even number of terms with coefficient $1$, then $f(1) = 0$ and so $f$ is divisible by $x – 1$, hence (if $\deg f > 1$) not irreducible. Thus, for $n > 1$, $\lambda(p, n)$ must be odd.
Some additional facts about this case:
- Swan has given several sufficient conditions for the reducibility of a trinomial $x^n + x^k + 1$ in $\Bbb F_2[x]$ (see citation below). One of these conditions in particular implies that all such trinomials are reducible when $n \equiv 0 \bmod 8$, and hence $\lambda(2, 8m) > 3$. More details can be found in $\S$40.9 of Jörg Arndt's Matters Computational (pdf warning, $>5$ MB).
- Ciet, Quiscater, and Siet showed similarly that $\lambda(2, n) > 3$ if $n \equiv 13 \bmod 24$ or $n \equiv 19 \bmod 24$.
Case $p \neq 2$.
- If $n = 2$ and we write $p = 2 q + 1$, then $p^2 = (2 q + 1)^2 = 4q(q + 1) + 1 \equiv 1 \pmod {4 q} = 1 \pmod {2(p – 1)}$, so by Jim Belk's characterization, $\lambda(p, 2)$ = 2.
- Harry Altman gives a proof (generalizing an observation) below that for $p > 3$ we have $\lambda(p, 3) = 2$ for $p \equiv 1 \bmod 3$ and $\lambda(p, 3) = 3$ for $p \equiv 2 \bmod 3$.
These facts together give us:
- A characterization of $(p, n)$ such that $\lambda(p, n) = 2$.
- Knowledge of all $\lambda(p, n)$, $n \leq 3$.
It thus remains to determine which $(p, n)$ have $\lambda(p, n) > 3$ and $\lambda(p, n)$ for those values. Some naive experimentation suggests that it is rare for $\lambda(2, n) > 5$ and for $\lambda(p, n) > 3$ for $p > 2$.
A naive Maple script gives that the only values of $\lambda(n, p)$ that occur for $p < 2^5, n \leq 2^8$ are $2, 3, 4, 5$. Apparently minimal examples are:
\begin{array}{crrr}
\hline
\lambda(p, n) & p & n & f(X) \\
\hline
2 & 3 & 2 & X^2 + 1 \\
3 & 2 & 2 & X^2 + X + 1 \\
4 & 5 & 35 & X^{35} + X^4 + 4 X + 1 \\
5 & 2 & 5 & X^8 + X^4 + X^3 + X + 1 \\
\hline
\end{array}
For $p = 2$, Table of Low-Weight Binary Irreducible Polynomials gives minimal polynomials (and hence values $\lambda(2, n)$) for all $n \leq 10^5$. In all cases, $\lambda(2, n) \in \{3, 5\}$. See also OEIS A057486, "Degrees of absolutely reducible trinomials, i.e. numbers $n$ such that $x^n + x^m + 1$ is factorable [modulo $2$] for all $m$ between $1$ and $n$."
- What is the smallest degree $n$, if any, such that $\lambda(2, n) > 5$, i.e., for which there are no irreducible trinomials or pentanomials over $\Bbb F_2$?
- If there is such a degree, what is the maximum value of $\lambda(2, n)$, if any?
Among $2 < p < 2^5$ and $n \leq 2^8$, the only values $\lambda(p, n) > 3$ are the following, and in each case $\lambda(p, n) = 4$:
\begin{array}{rl}
\hline
p & n \\
\hline
3 & 49, 57, 65, 68, 75, 98, 105, 123, 129, 130, 132, 149, 161, 175, 189, \\ & \quad 197, 207, 212, 213, 221, 223, 231, 233 \\
5 & 35, 70, 123, 125, 140, 181, 191, 209, 213, 219, 237, 249, 250, 253 \\
7 & 124, 163 \\
11 & 219 \\
17 & 231 \\
\hline
\end{array}
Searching $2 < p \leq 8161$ (the $2^{10}$th prime) and $n \leq 2^4$ yields no cases where $\lambda(p, n) > 3$.
- What is the smallest $n$ such that $\lambda(p, n) \leq 3$ for all $p > 2$? (We know from the above that $4 \leq n \leq 35$.)
- Is $\lambda(p, n) > 4$ for some $n$ and $p > 2$? If so, what is a minimal example, and what is the maximum value of $\lambda(p, n)$, $p > 2$?
References
Jörg Arndt, Matters Computational (pdf warning, $>5$ MB)
Mathieu Ciet, Jean-Jacques Quisquater, Francesco Sica, "A Short Note on Irreducible Trinomials in Binary Fields", (2002).
Gadiel Seroussi, "Table of Low-Weight Binary Irreducible Polynomials," Computer Systems Laboratory HPL-98-135.
Richard G. Swan, "Factorization of polynomials over finite fields", Pacific Journal of Mathematics, (12) 3, pp. 1099-1106, (1962).
Best Answer
Here is a helpful theorem:
Theorem. $\lambda(p,n) = 2$ if and only if $p \nmid n$ and $p$ has order $n$ modulo $n(p-1)$.
This tells us exactly where all of the 2's appear in the table. Using a little Mathematica code, we can fill in the missing $2$'s:
\begin{array}{c|cccccccc} \lambda & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20\\ \hline 2 & 1 & 3 & 3 & 3 & 3 & 3 & 3 & 5 & 3 & 3 & 3 & 3 & 5 & 3 & 3 & 5 & 3 & 3 & 5 & 3 \\ 3 & 1 & 2 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 \\ 5 & 1 & 2 & 3 & 2 & 3 & 3 & 3 & 2 & & & & & & & & 2 & \\ 7 & 1 & 2 & 2 & 3 & 3 & 2 & 3 & & 2 & & & & & & & & & 2 & \\ 11 & 1 & 2 & 3 & 3 & 2 & & & & & 2 & 3 \\ 13 & 1 & 2 & 2 & 2 & 3 & 2 & & 2 & 2 & & & 2 & 3 & & & 2 & & 2 &\\ 17 & 1 & 2 & 3 & 2 & & & & 2 & & & & & & & & 2 & 3 \\ 19 & 1 & 2 & 2 & 3 & & 2 & & & 2 & & & & & & & & & 2 & 3 \\ 23 & 1 & 2 & 3 & 3 & & & & & & & 2 \\ 29 & 1 & 2 & 3 & 2 & & & 2 & 2 & & & & & & 2 & & 2\\ 31 & 1 & 2 & 2 & 3 & 2 & 2 & & & 2 & 2 & & & & & 2 & & & 2 \\ \end{array}
Proof: The proof is a generalization of this answer by Lubin. Let $p$ be a prime and let $n\geq 2$.
Note first that if $p\mid n$, then $x^n-\beta = (x^{n/p}-\beta)^p$ for all $\beta\in\mathbb{F}_p$, and hence $\lambda(p,n)>2$. Therefore, we may assume that $p\nmid n$.
Let $\alpha$ be a primitive element of $\mathbb{F}_p$, and let $k=n(p-1)$. Then $\alpha$ is a primitive $(p-1)$'st root of unity, so the polynomial $x^n-\alpha$ has at least one root $r$ that is a primitive $k$'th root of unity. We claim that the following are equivalent:
$\lambda(p,n)=2$
$[\mathbb{F}_p(r):\mathbb{F}_p] = n$.
$x^n - \alpha$ is irreducible.
$p$ has order $n$ modulo $k$.
$(1) \Rightarrow (2)$ Suppose $\lambda(p,n)=2$. Then $x^n - \beta$ must be irreducible for some $\beta \in\mathbb{F}_n$. Since $\alpha$ is primitive, we know that $\alpha^j = \beta$ for some $j$. Then $r^j$ is a root of $x^n-\beta$, so $$[\mathbb{F}_p(r):\mathbb{F}_p] \;\geq\; [\mathbb{F}_p(r^j):\mathbb{F}_p] \;=\; n, $$ and hence $[\mathbb{F}_p(r):\mathbb{F}_p] = n$.
$(2) \Rightarrow (3)$ and $(3) \Rightarrow (1)$ are immediate.
$(2) \Leftrightarrow (4)$ Let $m\geq 1$. Then $\mathbb{F}_{p^m}$ contains the primitive $k$'th roots of unity if and only if $k \mid p^m - 1$, i.e. if and only if $p^m \equiv 1\;(\text{mod }k)$. In particular, the smallest value of $m$ for which $\mathbb{F}_{p^m}$ contains the primitive $k$'th roots of unity is the order of $p$ modulo $k$. Thus $[\mathbb{F}_p(r):\mathbb{F}_p]=n$ if and only if $p$ has order $n$ modulo $k$.$\quad\square$