Shortest irreducible polynomials over $\Bbb F_p$ of degree $n$
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$, what is the least number $\lambda(p, n)$ of nonzero coefficients an irreducible polynomial of degree $n$ over $\Bbb F_p$ can have?
Some trivial to easy observations:
- The only polynomial of degree $n$ with exactly one nonzero coefficient is $X^n$, and this is reducible iff $n > 1$, so $\lambda(p, 1) = 1$ and $\lambda(p, n) > 1$ for $n > 1$.
- For $p \neq 2$, the squaring map on $\Bbb F_p^{\times}$ is $2$-to-$1$, so there are always nonsquares $a$ modulo $p$, and for such $a$ the polynomial $x^2 - a$ is irreducible, and so $\lambda(p, 2) = 2$. The only irreducible polynomial of degree $2$ over $\Bbb F_2$ is $X^2 + X + 1$, so $\lambda(2, 2) = 3$.
- Any irreducible polynomial of degree $> 1$ has nonzero constant term. In particular, the only polynomial over $\Bbb F_2$ with exactly two nonzero coefficients and nonzero constant term is $X^n + 1$, but this always has root $1$ and so has $X + 1$ as a factor; thus, $\lambda(2, n) \geq 3$ for $n > 1$.
- The only (monic) polynomials over $\Bbb F_3$ with exactly two nonzero coefficients, the constant term among them, are $X^n \pm 1$. Now, $X^n - 1$ again always has root $1$. If $n$ is not a power of $2$, say, $n = 2^m q$ for $q > 1$, one can factor $X^n + 1 = (X^{2^m} + 1)(X^{2^m (q - 1)} - X^{2^m (q - 2)} + \cdots + X^{2^m})$, and if $n$ is a power of $2$ larger than $2$ (indeed, any multiple of $4$), we can factor $X^n + 1 = (X^{n / 2} - X^{n / 4} - 1)(X^{n / 2} + X^{n / 4} - 1)$. In summary, if $n > 2$ then $X^n \pm 1$ is reducible and so $\lambda(3, n) \geq 3$. On the other hand $X^2 + 1$ is irreducible, so $\lambda(3, 2) = 2$.
- For $n = p$, this question shows that $X^p - X + a$ is irreducible for all $a \neq 0$, so $\lambda(p, p) \leq 3$. Then, using that the Frobenius map $\phi: X \mapsto X^p$ is an automorphism we see that every polynomial $X^p + a$ is reducible---indeed, it factors as $(X - b)^p$, where $b := \phi^{-1}(-a)$---and so (again since the constant term of any irreducible polynomial of degree $n > 1$ is nonzero) $\lambda(p, p) = 3$.
Some more observations from answers:
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$. With this in hand, all $\lambda(p, n)$, $n \leq 3$, are resolved.
Jim Belk's answer shows more generally that we can quickly characterize the $(p, n)$ for which there is an irreducible polynomial of the form $X^n + a$, that is, for which $\lambda(p, n) = 2$.
Yet more results:
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$.
Together with the above, a few naive Maple scripts yield the following table that includes all $(p, n)$ such that $p < 2^5, n \leq 2^4$. (The table includes a column for $n = 49$, because this is the smallest value for which $\lambda(p, n) = 4$ for some small $p$, and possibly any $p$.) \begin{array}{c|cccccccc} \lambda & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & \cdots & 49\\ \hline 2 & \co & \ch & \ch & \ch & \ch & \ch & \ch & \ci & \ch & \ch & \ch & \ch & \ci & \ch & \ch & \ci & \cdots & \ch\\ 3 & \co & \ct & \ch & \ch & \ch & \ch & \ch & \ch & \ch & \ch & \ch & \ch & \ch & \ch & \ch & \ch & \cdots & \cf\\ 5 & \co & \ct & \ch & \ct & \ch & \ch & \ch & \ct & \ch & \ch & \ch & \ch & \ch & \ch & \ch & \ct & \cdots & \ch\\ 7 & \co & \ct & \ct & \ch & \ch & \ch & \ch & \ch & \ct & \ch & \ch & \ch & \ch & \ch & \ch & \ch & \cdots & \ch\\ 11 & \co & \ct & \ch & \ch & \ct & \ch & \ch & \ch & \ch & \ct & \ch & \ch & \ch & \ch & \ch & \ch & \cdots & \ch\\ 13 & \co & \ct & \ct & \ct & \ch & \ct & \ch & \ct & \ct & \ch & \ch & \ct & \ch & \ch & \ch & \ct & \cdots & \ch\\ 17 & \co & \ct & \ch & \ct & \ch & \ch & \ch & \ct & \ch & \ch & \ch & \ch & \ch & \ch & \ch & \ct & \cdots & \ch\\ 19 & \co & \ct & \ct & \ch & \ch & \ct & \ch & \ch & \ct & \ch & \ch & \ch & \ch & \ch & \ch & \ch & \cdots & \ch\\ 23 & \co & \ct & \ch & \ch & \ch & \ch & \ch & \ch & \ch & \ch & \ct & \ch & \ch & \ch & \ch & \ch & \cdots & \ch\\ 29 & \co & \ct & \ch & \ct & \ch & \ch & \ct & \ct & \ch & \ch & \ch & \ch & \ch & \ct & \ch & \ct & \cdots & \ct\\ 31 & \co & \ct & \ct & \ch & \ct & \ct & \ch & \ch & \ct & \ct & \ch & \ch & \ch & \ch & \ct & \ch & \cdots & \ch\\ \end{array}
Some data:
- The only values of $\lambda(n, p)$ that occur for $p \leq 11, n \leq 2^8$ or $p \leq 97, n \leq 20$ are $1, 2, 3, 4, 5$. Apparently minimal examples are: $\lambda(2, 1) = 1$, $X$; $\lambda(3, 2) = 2$, $X^2 + 1$; $\lambda(2, 2) = 3$, $X^2 + X + 1$; $\lambda(3, 49) = 4$, $X^{49} + X^{14} + X + 2$; $\lambda(2, 8) = 5$, $X^8 + X^7 + X^2 + X + 3$. For all $106$ values of $n \leq 2^8$ for which $\lambda (2, n) > 3$ we have $\lambda(2, n) = 5$. For all $p = 3, 5, 7, 11$ and $n \leq 2^8$ for which $\lambda(p, n) > 3$ (there are $23$, $14$, $2$, and $1$ of these, resp.) we have $\lambda(p, n) = 4$.
OEIS A057486 is the sequence of "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$," i.e., a list of $n > 1$ such that $\lambda(2, n) > 3$.
Remarkably, it was recently shown that $\lambda(2, 57885161) > 3$. (Not unrelated is the fact that $2^{57885161}-1$ is a Mersenne prime, though I don't know the extent of this relationship.)
One can also determine values for small enough $p, n$ by consulting these tables.
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).
Richard G. Swan, "Factorization of polynomials over finite fields", Pacific Journal of Mathematics, (12) 3, pp. 1099-1106, (1962).
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$
Here's a proof of the pattern about $\lambda(p,3)$: As with degree $2$, a polynomial of degree $3$ is irreducible iff it has no roots, and there exists a noncube mod $p$ if and only if $p\equiv 1 \pmod{3}$. So in this case we must have $\lambda(p,3)=2$.
Conversely, if $p\equiv 2\pmod{3}$, then we must have $\lambda(p,3)\ge3$. But given a cubic irreducible polynomial mod $p$, since $p\ne 3$, we can perform a translation so that the coefficient of $X^2$ is $0$ (depressing the polynomial). This shows that $\lambda(p,3)\le 3$ and so $\lambda(p,3)=3$.
This latter argument shows more generally that if $p\nmid n$, then $\lambda(p,n)\le n$, though this looks to be a pretty crappy bound.