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², 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² + 13x + 11, and notice the following values

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 2d_g, and by the same reasoning the max number of times that h(k) could equal ±1 is 2d_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 k₁ and k₂ such that g(k₁) = 1 and g(k₂) = –1. Just to illustrate, let's imagine that g(x) is of degree 3, so we have

Subtracting the second from the first gives

Notice that each term on the left is divisible by (k₁–k₂), 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 k₁ and k₂ differ by more than 2, and if the absolute values of g(k₁) and g(k₂) are both 1, then g(k₁) and g(k₂) 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 preceding 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

In this case we can easily compute

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 the 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³ – 21x² + 98x + 6 we have c = 6 and the canonical primal form is

which is irreducible in view of the values

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¹² + 488669 occurs with x = 616980 and has 70 decimal digits.

Return to MathPages Main Menu