Irreducibililty tests for cubic and quartic polynomials over finite fields

Question

The unpublished preprint:
D. G. A. Jackson, The irreducibility of a cubic over $\mathbb{F}_q$, Research Report 98-17, Univ. of Sydney (1998)
gives necessary and sufficient conditions (when ${\rm char}({\mathbb F}_q)\neq2,3$) for a cubic polynomial over $\mathbb{F}_q$ to be irreducible. I have conditions (below) which work for cubics when ${\rm char}(\mathbb{ F}_q)=2,3$, and also quartics. While I guess that such results have been published, I have been unable to find references. I would be most grateful if someone knows precise reference (if they exist).

Theorem A. Suppose $q=2^e$ and $c(x)=x^3+c_2x+c_3$ where $c_2c_3\neq0$. Then $c(x)$ is irreducible over $\mathbb{F}_q$ if and only if ${\rm Tr}_{\mathbb{F}_q/\mathbb{F}_2}(c_2^3/c_3^2)\equiv e\pmod2$, and a root $\beta$ of $b(x)=x^2+c_3x+c_2^3$ is a noncube.

Theorem B. Suppose $q=3^e$ and $c(x)=x^3+c_2x+c_3$. Then $c(x)$ is irreducible over $\mathbb{F}_q$ if and only if $-c_2$ is a square in $\mathbb{F}_q^\times,$ and ${\rm Tr}_{\mathbb{F}_q/\mathbb{F}_3}(c_3/\eta^3)\neq0$ where $\eta^2=-c_2$.

The factorization of a quartic should depend on two square roots and one cube root, at least when ${\rm char}(\mathbb{F}_q)\neq2,3$. Given that 1/4 of quartic polynomials are irreducible (in the limit as $q\to\infty$) one may guess that there is an irreducibility test of the form: $x^4+ax^3+bx^2+cx+d$ is irreducible over $\mathbb{F}_q$ if and only if $f$ or $g$ is a square, and $h$ is a cube; where $f,g,h$ are given rational functions of $a,b,c,d$. [Thus irreducibility should occur with limiting probability $(1-(1/2)^2)\times 1/3=1/4$, as $q\to\infty$; agreeing with the correct limiting probability.]

Question. Are expressions for $f,g,h$ known? What if ${\rm char}(\mathbb{F}_q)=2,3$? [I should say: "f is a square or g is a nonsquare". The probabilistic argument still works.]

Stephen Glasby

Answer 1

These results have been known for many years. Here are some references and further developments; full bibliographic details are at the end of this answer.

Reducibility criteria for cubics over finite fields of characteristic at least $5$ were given already in 1906 by Dickson. In fact he gave conditions for a cubic to have each of the possible factorization types. Reducibility criteria for cubics in characteristic $2$ were given in 1966 by Berlekamp, Rumsey and Solomon (see also their 1967 paper). Those criteria are slightly different than your Theorem A. Your Theorems A and B appear to have been published for the first time in 1975 by Williams, who also gave criteria for each of the possible factorization types.

Reducibility criteria for quartics over prime fields of odd order were given by Skolem in 1952. In 1969, Leonard gave a different proof of Skolem's result, which extends at once to non-prime fields of odd order. Finally, reducibility criteria for quartics in characteristic $2$ were given by Leonard and Williams in 1972.

Your Theorems A and B can be generalized in various ways. Bluher's 2004 paper generalizes your Theorem A to polynomials of the form $x^{p^k+1}+ax+b$. In a series of papers culminating in 1980, Agou determined all instances when $f(L(x))$ is irreducible over $\mathbf{F}_{p^s}$, where $f,L\in\mathbf{F}_{p^s}[x]$ and all terms of $L(x)$ have degree $p^i$ with $i\ge 0$. The case $f=x+c_3$ and $L=x^3+c_2 x$ with $p=3$ yields your Theorem B. Subsequently, a simpler proof of Agou's results was given by Cohen in 1982; following two related papers by Moreno, Cohen gave an even simpler proof in 1989.

References:

1. S. Agou, Irréducibilité des polynômes $f(\sum_{i=0}^m a_i X^{p^{ri}})$ sur un corps fini $\mathbf{F}_{p^s}$, Canadian Mathematical Bulletin 23 (1980), 207-212
2. E. R. Berlekamp, H. Rumsey and G. Solomon, Solutions of algebraic equations in field of characteristic 2, Jet Propulsion Lab. Space Programs Summary No. 4 (1966), 37-39
3. E. R. Berlekamp, H. Rumsey and G. Solomon, On the solution of algebraic equations over finite fields, Information and Control 10 (1967), 553-564.
4. A. W. Bluher, On $x^{q+1}+ax+b$, Finite Fields and their Applications 10 (2004), 285-305
5. S. D. Cohen, The irreducibility of compositions of linear polynomials over a finite field, Compositio Mathematica 47 (1982), 149-152
6. S. D. Cohen, The reducibility theorem for linearised polynomials over finite fields, Bulletin of the Australian Mathematical Society 40 (1989), 407-412
7. L. E. Dickson, Criteria for the irreducibility of functions in a finite field, Bulletin of the American Mathematical Society 13 (1906), 1-8
8. P. A. Leonard, On factoring quartics (mod $p$), Journal of Number Theory 1 (1969), 113-115
9. P. A. Leonard and K. S. Williams, Quartics over GF($2^n$), Proceedings of the American Mathematical Society 36 (1972), 347-350
10. Th. Skolem, The general congruence of 4th degree modulo $p$, $p$ prime, Nordisk matematisk tidskrift 34 (1952), 73-80
11. K. S. Williams, Note on cubics over GF($2^n$) and GF($3^n$), Journal of Number Theory 7 (1975), 361-365