41
$\begingroup$

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

$\endgroup$
18
  • 5
    $\begingroup$ Interesting! I am curious a related question, is the set $\lambda(2,n), n\geq 1$ bounded? $\endgroup$
    – user119882
    Jun 6, 2015 at 9:26
  • 1
    $\begingroup$ @KCd How did you produce those examples? $\endgroup$ Jun 7, 2015 at 6:29
  • 2
    $\begingroup$ 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.) $\endgroup$
    – KCd
    Jun 7, 2015 at 7:09
  • 1
    $\begingroup$ 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$. $\endgroup$
    – KCd
    Jun 7, 2015 at 7:19
  • 1
    $\begingroup$ @KCd I just wrote a short Maple script and confirmed your results. $\endgroup$ Jun 7, 2015 at 16:03

2 Answers 2

9
$\begingroup$

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:

  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$

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Jun 8, 2015 at 7:04
  • $\begingroup$ 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. $\endgroup$ Jun 8, 2015 at 7:15
  • 1
    $\begingroup$ @HarryAltman Good point. I've added that to the statement of the theorem for clarity, and I've added that case to the proof. $\endgroup$
    – Jim Belk
    Jun 8, 2015 at 17:13
6
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Great, thanks for this observation. (But doesn't the second argument show that $\lambda(p, n) \leq n$ and not the strict inequality?) $\endgroup$ Jun 7, 2015 at 5:44
  • 1
    $\begingroup$ 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$! $\endgroup$ Jun 7, 2015 at 19:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.