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).
No comments:
Post a Comment