# 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 > 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.

• 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).

• Interesting! I am curious a related question, is the set $\lambda(2,n), n\geq 1$ bounded? Commented Jun 6, 2015 at 9:26
• @KCd How did you produce those examples? Commented Jun 7, 2015 at 6:29
• For each $n > 1$ and $k$ running from $1$ to $n-1$, determine if $x^n + ax^k + b$ is irreducible as $a$ and $b$ run over $\mathbf F_p$ using a computer algebra package. Add $1$ if it is irreducible and add $0$ if it is reducible. Then see for which $n$ the sum over all $k$, $a$, and $b$ is $0$. The calculations were carried out months ago, in order to find the first two $n$, for small $p$, when there are no irreducible binomials or trinomials over $\mathbf F_p$. (It included your data $n = 8$ and $n = 13$ for $p = 2$, but I hadn't mentioned it before.)
– KCd
Commented Jun 7, 2015 at 7:09
• In particular, you're going to find $\lambda(3,n) \leq 3$ for $n \leq 57$ except at $n=49$ and $n=57$, $\lambda(5,n) \leq 3$ for $n \leq 70$ except at $n=35$ and $n=70$, and $\lambda(7,n) \leq 3$ for $n \leq 163$ except at $n=124$ and $n=163$.
– KCd
Commented Jun 7, 2015 at 7:19
• @KCd I just wrote a short Maple script and confirmed your results. Commented Jun 7, 2015 at 16:03

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:

1. $\lambda(p,n)=2$

2. $[\mathbb{F}_p(r):\mathbb{F}_p] = n$.

3. $x^n - \alpha$ is irreducible.

4. $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$

• Doesn't this run into a problem if $p\mid n$ (and hence $p\mid k$)? In that case, in characteristic $p$, there is no primitive $k$'th root of unity. Commented Jun 8, 2015 at 7:04
• Oh, silly me; if $p\mid n$, the order isn't defined -- you might want to rewrite the beginning as "$p\nmid n$ and $p$ has order $n$ modulo $n(p-1)$", for clarity! Because that is true; if $p\mid n$, then $\lambda(p,n)\ge 3$ by a different argument, namely, Frobenius. Commented Jun 8, 2015 at 7:15
• @HarryAltman Good point. I've added that to the statement of the theorem for clarity, and I've added that case to the proof. Commented Jun 8, 2015 at 17:13

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.

• Great, thanks for this observation. (But doesn't the second argument show that $\lambda(p, n) \leq n$ and not the strict inequality?) Commented Jun 7, 2015 at 5:44
• Oops, silly me. Off-by-one error. Will Fix. I should have noticed, given I just showed that in certain cases $\lambda(p,3)=3$! Commented Jun 7, 2015 at 19:29