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.