## Irreducibility Criteria

```One of the most well-known methods of determining whether a given
polynomial (with integer coefficients) is irreducible over the
rationals (meaning that it cannot be factored into smaller
polynomials with rational coefficients) is Eisenstein's criterion,
which states that if all the coefficients (except possibly the
first) are divisible by a prime p, and the constant coefficient
is *not* divisible by p^2, then the polynomial is irreducible.

It often happens that this criterion is not directly applicable
to a given polynomial f(x), but it may be applicable to f(x+a)
for some constant a.  So we try various values of a, hoping to
transform f(x) into a polynomial that satisfies the conditions
of the criterion.

Notice that Eisenstein's criterion essentially reduces the problem
of factoring a polynomial of degree d to a problem of factoring d
integers, the coefficients of the transformed polynomial, to see if
they share a suitable common prime divisor.  Obviously as we try
various transformations we will produce polynomials with larger and
larger coefficients, so the computational task of computing and then
checking the factorizations of those coefficients can be significant.
Moreover, a simple transformation that allows us to apply Eisenstein's
criterion may not even exist.  However, if we are willing to factor
some large integers, there is another criterion that is, in some
ways, even easier than Eisenstein's, and that always works (assuming
the truth of a famous conjecture; see below).

Let F(x) denote a monic polynomial of degree d with integer
coefficients, and suppose we want to determine if this factors
into smaller polynomials with integer coefficients.  If
F(x) = g(x)h(x) where g(x) and h(x) are non-constant polynomials
with integer coefficients then it follows that for any integer k
the number F(k) is divisible by the integers g(k) and h(k).

Now let's take the example F(x) = x^2 + 13*x + 11, and notice the
following values

F(-2) = -11
F( 0) =  11
F( 2) =  41
F( 8) = 179
F(10) = 241

These are each primes, so if F(k) = g(k)h(k) it follows that either
g(k) or h(k) is  +-1 for each k = -2,0,2,8,19.  Now, it's certainly
possible for one of these factor polynomials to give a value of +-1
for some argument k, but for how many different values of k is this
possible?

Clearly if d_g is the degree of g(x), then g(k) can equal +1 no more
than d_g times, because the polynomial g(x)-1 can have no more than
d_g roots.  Similarly, g(k) can equal -1 for no more than d_g distinct
values of k.  Thus, the maximum number of times that g(k) could equal
either +1 or -1 is 2(d_g), and by the same reasoning the max number of
times that h(k) could equal +-1 is 2(d_h).  As a result, the maximum
possible number of distinct values of k for which F(k) can be a prime
(assuming F(x) factors as g(x)h(x))  is  2(d_g + d_h) = 2d.  So, if
we can find 2d+1 distinct integers k such that F(k) is a prime (or a
unit), then F(x) is irreducible.

Furthermore, a "certificate of irreducibility" doesn't really need to
include all 2d+1 values of k.  To understand why, suppose there are
distinct integers k1 and k2 such that g(k1)=1 and g(k2)=-1.  Just to
illustrate, let's imagine that g(x) is of degree 3, so we have

(k1)^3 + A(k1)^2 + B(k1) + C  =   1

(k2)^3 + A(k2)^2 + B(k2) + C  =  -1

Subtracting the second from the first gives

(k1^3 - k2^3)  +  A(k1^2 - k2^2) + B(k1 - k2)  =  2

Notice that each term on the left is divisible by (k1-k2), so that
difference must be a divisor of the right hand side, which is 2.  The
only integer divisors of 2 are +-1 and +-2, so if the numbers k1 and
k2 differ by more than 2, and if the absolute values of g(k1) and
g(k2) are both 1, then g(k1) and g(k2) must have the same sign.

Therefore, the maximum number of integers k differing by more than
2 for which g(k)=+-1 is only d_g, and the maximum number of such
integers for which h(k)=+-1 is only d_h, for a combined total of
(d_g + d_h) = d.  Thus, if we can find d+1 integers k that differ
by more than 2 and such that F(k) is a prime or unit, then F(x) is
irreducible.  For the preceeding example this means we can certify
the irreducibility with just the three values F(-2) = -11,
F( 2) = 41 , and F( 8) = 179.

Now, let's try this on a bigger polynomial, such as

F(x)  =  x^6 - 3x^5 - 87x^4 + 118x^3 - 33x^2 + 21x - 1

In this case we can easily compute

F(-22) = 107187629
F( -8) =    -58601
F( -4) =    -23269
F(  0) =        -1
F( 12) =    634859
F( 18) =  19888469
F( 30) = 588786929

Each of the arguments -22, -8, .., 30 differs by more than 2 from the
others, and each of the 7 values of F(k) is a prime or a unit, so it
follows that F(x) is irreducible over the integers (and therefore
over the rationals).

Admittedly this requires us to test for primality of some fairly large
numbers F(k), but it's usually quite easy to detect composites, so
you can focus in quickly on a set of d+1 "probable primes", and then
rigorously prove primality.  (Of course, the numbers in the above
example are small enough to simply check for trial divisors up to
the square root.)  In comparison, Eisenstein's criterion would require
us to actually factor a large number of *sets* of coefficients of
transformed polynomials, looking for a set that is suitable, and with
no guarantee that a suitable one exists.

Of course, if F(x) actually IS reducible, then we will find that the
values of F(k) for all but at most 2d+1 values of k are composite.  In
that case we can infer the polynomial factors of F(x) from the integer
factors of F(k), although it's probably easier to simply algebraically
solve the conditions on the coefficients of the factors.

One possible objection to the method of irreducibility testing described
above is thew fact that there exist irreducible polynomials f(x) such
that f(k) is *never* a prime for any integer k.  However, the first
step in the method is really to construct a "primal polynomial" F(x)
whose factorability is the same as that of f(x).  A primal polynomial
F(x) is one for which the greatest common divisor of  all the values
F(k) is 1.  If c is the constant coefficient of f(x) then the canonical
primal form of f(x) is F(x) = f(cx)/c.  Clearly F(x) is irreducible if
and only if f(x) is irreducible (over the rationals).

For example, if f(x) = x^3 - 21x^2 + 98x + 6 we have c=6 and
the canonical primal form is

F(x)   =    f(6x)/6    =    36x^3 - 126x^2 + 98x + 1

which is irreducible in view of the values

F(-6)  =  -12899
F(-3)  =   -2399
F( 0)  =       1
F( 9)  =   16921

Notice that we have F(0)=1 by definition, so for a primal
polynomial of degree d we only need to find d non-trivial prime
values (with arguments differing from each other and 0 by more
than 2).

In fairness, I should mention that the assertion that this method
will *always* work is based on a famous unproved conjecture.
Specifically, in 1857 Bouniakowsky conjectured that if f(x) is
an irreducible polynomial with integer coefficients such that no
number greater than 1 divides all the values of f(k) for every
integer k, then f(k) is prime for infinitely many integers k.
On this basis, the above test for irreducibility will always
work.  On the other hand, it won't always be easy.  For example,
the first prime value of x^12 + 488669 occurs with x=616980 and
has 70 decimal digits.
```