An efficient algorithm for determining whether a quartic with integer coefficients is irreducible over $\mathbb{Z}$

Question

I'm interested in what efficient algorithm could be used for determining if a quartic polynomial with integer coefficients is irreducible over $\mathbb{Z}$.

For quadratics and cubics it's not too bad, as one of the factors must be linear. We can use the rational root theorem to determine all the possible roots, and test whether any of them are actually a root. For a polynomial with small coefficients, this won't take very long.

For a quartic this may be harder, as it is possible that it may factor into two irreducible quadratics.

A naive approach might be:

• First do the rational root theorem test, to see if it has a linear factor.

• If not, then write $f(x) = ax^4 + bx^3 + cx^2 + dx + e = (\alpha x^2+ \beta x + \gamma)(\delta x^2 + \epsilon x + \zeta)$. By expanding out we may find relations such as $\gamma \zeta = e$ for example, so $\gamma, \zeta \mid e$, and so on. That's not too many possible choices for what I have written in Greek letters for small coefficients, so we can just try all possible combinations (reducing the number we need to check by using relations between the Greek letters) and see if any work.

Is there a solution that is much more efficient (perhaps also elegant)? I know of various things such as Eisenstein's criterion, that $f(x)$ is irreducible if and only if $f(x+c)$, $x^4f(1/x)$ are irreducible, etc. but these seem to be handy only in very particular cases. I'm asking if there's a general method that can work for any quartic.

If such an algorithm can also be extended to find the irreducibility of higher order polynomials as well, that'd be very useful to know.

Answer 1

Given a quartic

$ax^4+bx^3+cx^2+dx+e,$

we propose a factorization

$(\alpha x^2+\gamma x+\epsilon)(\alpha' x^2+\gamma' x+\epsilon')$

where $(\alpha)(\alpha')=a$ and $(\epsilon)(\epsilon')=e$. Then matching the cubic terms and the linear terms respectively give

$\alpha\gamma'+\alpha'\gamma=b\tag{1}$

$\epsilon\gamma'+\epsilon'\gamma=d\tag{2}$

If the determinant $\alpha\epsilon'-\alpha'\epsilon$ is nonzero, this sysyem has a unique solution for $\gamma$ and $\gamma'$, and the proposed factorization is checked by seeing if the quadratic terms catch the coefficient $c$ of $x^2$:

$\alpha\epsilon'+\gamma\gamma'+\alpha'\epsilon\overset{must}{=}c\tag{3}$

If the determinant is zero, then there is no solution unless either of the following equivalent conditions hold:

$b\epsilon=d\alpha,b\epsilon'=d\alpha'\tag{4}$

When this equality is satisfied, either (1) or (2) may be combined with (3) to generate a quadratic equation for $\gamma$, with either root suitable for factorization. Once a root for $\gamma$ is chosen, it is substituted back into (1) or (2) and the equation is solved for the corresponding value of $\gamma'$. The two possible choices differ at most by orderibg of the factors and constant multiplying factors.

Note that in the second case $\gamma$ and $\gamma'$, being derived from solving a quadratic equation, may be irrational or even a pair of complex conjugates. If so, and if the quartic has no rational roots, then the quartic is ireeducible over tbe rationals; but the roots of the quadratic factors are still relatively easy to obtain (versus using the full general solution method).

Example 1: $x^4-3x-2$

If this quartic with no rational roots is reducible, then it will factor as one of the following:

$x^4-3x-2=(x^2+\gamma x+1)(x^2+\gamma' x-2)$

$x^4-3x-2=(x^2+\gamma x-1)(x^2+\gamma' x+2)$

With the first trial, Eqs. (1) and (2) give a unique solution

$\gamma=1,\gamma'=-1.$

But checking this against (3) gives

$(x^2+x+1)(x^2-x-2)=x^4\color{red}{-2x^2}-3x-2,$

so the factorization fails. Trying the second candidate above we find that

$\gamma=-1,\gamma'=1$

$(x^2-x-1)(x^2+x+2)=x^4\color{blue}{+0x^2}-3x-2,$

and so this factorization holds. We get $(1\pm\sqrt5)/2$ as real zeroes and $(-1\pm i\sqrt7)/2$ as a complex conjugate pair.

Example 2: $x^4+x^3+x^2-x+1$

Here we have the two candidates

$x^4+x^3+x^2-x+1=(x^2+\gamma x+1)(x^2+\gamma' x+1)$

$x^4+x^3+x^2-x+1=(x^2+\gamma x-1)(x^2+\gamma' x-1)$

With the first candidate Eqs (1) and (2) become

$\gamma+\gamma'=1, \gamma+\gamma'=-1$

and these are clearly contradictory. The determinant of the coefficient is zero and Eq. (4) fails with $b\epsilon=1,d\alpha=-1$. But with the second candidate we have

$\gamma+\gamma'=1, -\gamma-\gamma'=-1$

with $b\epsilon=d\alpha=-1$, and so the nonunique case holds. We find that when either linear equation is combined with (3) the following quadratic equation for $\gamma$ results:

$\gamma^2-\gamma+3=0\implies\gamma=(1\pm i\sqrt{11})/2.$

From these we obtain the factorization

$x^4+x^3+x^2-x+1=\left(x^2+\dfrac{1+i\sqrt{11}}2x-1\right)\left(x^2+\dfrac{1-i\sqrt{11}}2x-1\right)$

and the zeroes

$x=\frac14[(-1\pm_1\sqrt{2\sqrt5+3})\pm_2i(-\sqrt{11}\pm_1\sqrt{2\sqrt5-3})]$

(Identical subscripts on the $\pm$ signs indicate signs that are to be chosen identically.)