The Lumber Room

"Consign them to dust and damp by way of preserving them"

Testing irreducibility using prime numbers

Here’s a simple and nice test for irreducibility in ${\mathbb{Z}[x]}$ that N told me about a year ago. (I just noticed this lying around while cleaning; I don’t have a year’s buffer like Raymond Chen.) Apologies for the ugly formatting; you’ll have to trust that the result (Theorem 1, or Corollary 8) is more beautiful than it looks. :-)

Actually I’m not sure why I wrote this originally, given that it’s all already well-explained in the originals and even partially on Wikipedia. Perhaps my proofs are different or simpler or I was bored or something.

1. Irreducibility test

In its simplest form, the test can be stated as follows.

Theorem 1 Given a polynomial ${f(x) = a_nx^n + a_{n-1}x^{n-1} + \dots + a_o}$ with integer coefficients, let ${G = \max_{i}|\frac{a_i}{a_n}|}$. If there exists an integer ${m \ge G+2}$ such that ${f(m)}$ is prime, then ${f}$ is irreducible.

For example, with the polynomial $x^2 + 3x + 1$, we have $G = 3$, and $f(5)=f(G+2)=41$ is prime, which proves that it is irreducible. (We could also evaluate f at e.g. 7, 8, 9, or 10 to get the same conclusion.)

It follows directly from the following two results:

Lemma 2 Given a polynomial ${f(x) = a_nx^n + a_{n-1}x^{n-1} + \dots + a_o}$ with integer coefficients, let ${G = \max\limits_{0\le i\le n-1}|\frac{a_i}{a_n}|}$. Then for any root ${\alpha}$ of ${f}$, ${|\alpha| < G + 1}$.

Proof: Let ${\alpha}$ be any (complex) root of ${f}$. As ${a_n\alpha^n + a_{n-1}\alpha^{n-1} + \dots + a_o = 0}$, either ${|\alpha| \le 1}$, or ${|\alpha^n| \le \sum_{i=1}^{n-1}{|\frac{a_i}{a_n}| |\alpha^i|} \le G \sum_{i=1}^{n-1} |\alpha^i| = G\frac{|\alpha|^n-1}{|\alpha|-1} < G\frac{|\alpha|^n}{|\alpha|-1}}$ which means that ${|\alpha|-1 < G}$. Thus in either case ${|\alpha| < G+1}$. $\Box$

Lemma 3 Given a polynomial ${f}$ with integer coefficients, suppose ${f(m)}$ is prime for some ${m}$ such that ${|m-\alpha| > 1}$ for every root ${\alpha}$ of ${f}$. Then ${f}$ is irreducible.

Proof: Suppose ${f}$ can be factorized in ${{\mathbb Z}[x]}$ as ${f(x) = g(x)h(x)}$ where ${g}$ and ${h}$ have nonzero degree. As ${f(m) = g(m)h(m)}$ is prime, at least one of ${|g(m)|}$ and ${|h(m)|}$ must be 1, say ${|g(m)|=1}$.

Let the roots of ${g(x)=0}$ (over ${{\mathbb C}}$) be ${\alpha_1, \dots, \alpha_k}$. Then ${|g(m)| = |c|\prod_{i=1}^k{|m-\alpha_i|}}$, where ${c}$ the leading coefficient of ${g}$ being an integer, ${|c| \ge 1}$. As each factor ${|m-\alpha_i| > 1}$, this implies that ${|g(m)| > 1}$, which is a contradiction. $\Box$

A related nice result can be proved:

Theorem 4 Let ${p}$ be a prime number, written in base ${b}$ as ${a_na_{n-1}\dots a_0}$. Then the digit polynomial ${f(x) = a_nx^n + a_{n-1}x^{n-1} + \dots + a_0}$ is irreducible in ${{\mathbb Z}[x]}$.

Note that this result does not automatically follow from Theorem 1. Unless ${a_n > 1}$, ${G}$ could be as large as ${b-1}$, and the fact that ${f(b)}$ is prime does not help, as the theorem only applies for ${m \ge G+2 = b+1}$.

On the other hand, Theorem 1 is “best-possible” in terms of the absolute values of the coefficients: consider, for ${b=10}$, the polynomials ${x^3-9x^2+x-9 = (x-9)(x^2+1)}$, or ${x^3-9x^2-9x+1 = (x+1)(x^2-10x+1)}$, for both of which ${G = 9 = b-1}$, and ${f(b)}$ is prime!

Clearly, then, Theorem 4 depends not only on ${f(b)}$ being prime, but also on the signs of the coefficients. It turns out that we only need the sign of ${a_{n-1}}$:

Lemma 5 Given a polynomial ${f(x) = a_nx^n + a_{n-1}x^{n-1} + \dots + a_o}$ with integer coefficients such that ${\frac{a_{n-1}}{a_n} \ge 0}$, let ${G = \max\limits_{0\le i\le n-2}|\frac{a_i}{a_n}|}$. Then for any root ${\alpha}$ of ${f}$, either ${\Re(\alpha) \le 0}$ or ${|\alpha| < \frac{1 + \sqrt{1 + 4G}}{2}}$.

Proof: If ${|\alpha| \le 1}$, we are done. Else, as before, ${|\alpha^n + \frac{a_{n-1}}{a_n}\alpha^{n-1}| \le G\frac{|\alpha|^{n-1}-1}{|\alpha|-1}}$.

So if ${\Re(\alpha) > 0}$, then ${|\alpha^n + \frac{a_{n-1}}{a_n}\alpha^{n-1}| = |\alpha|^n |1 + \frac{a_{n-1}}{a_n\alpha}| \ge |\alpha|^n}$, so ${|\alpha^n| < G\frac{|\alpha|^{n-1}}{|\alpha|-1}}$ which means that ${{|\alpha|}(|\alpha|-1) < G}$, from which we get ${|\alpha| < \frac{1 + \sqrt{1 + 4G}}{2}}$. $\Box$

We can now prove the theorem for bases other than 2: Proof: As ${a_n \ge 1}$ and all the coefficients lie between ${0}$ and ${b-1}$, we have ${G \le b-1}$. Thus by Lemma 5, for any root ${\alpha}$ of ${f}$, we have ${|b-\alpha| > b - \frac{1 + \sqrt{1 + 4(b-1)}}{2} \ge 1}$ if ${b \ge 3}$. As ${f(b) = p}$ is prime, Lemma 3 now implies the irreducibility of ${f}$. $\Box$
The theorem is also true for base 2, see \cite{Murty} or \cite{BFO}.

2. Generalisations

We can consider a few variants of Lemma 2 that are stronger when ${G > 1}$.

Lemma 6 Given a polynomial ${f(x) = a_nx^n + a_{n-1}x^{n-1} + \dots + a_o}$ with integer coefficients, let ${a_{n-r}}$ be the first nonzero coefficient of ${f}$ after ${a_n}$ (i.e., ${a_m = 0}$ if ${n-r < m < n}$). Let ${G = \max\limits_{0\le i\le n-r}|\frac{a_i}{a_n}|}$. Then for any root ${\alpha}$ of ${f}$, ${|\alpha| < G^{1/r} + 1}$.

Proof: If ${|\alpha| \le 1}$, we are done. Else, ${|\alpha^n| \le \sum_{i=0}^{n-1}{|\frac{a_i}{a_n}| |\alpha^i|} \le G \sum_{i=0}^{n-r} |\alpha^i| = G\frac{|\alpha|^{n-r+1}-1}{|\alpha|-1} < G\frac{|\alpha|^{n-r+1}}{|\alpha|-1}}$ which means that ${G > |\alpha|^{r-1}(|\alpha|-1) > (|\alpha|-1)^r}$. Thus in either case ${|\alpha| -1 < G^{1/r}}$. $\Box$

Lemma 7 Given a polynomial ${f(x) = a_nx^n + a_{n-1}x^{n-1} + \dots + a_o}$ with integer coefficients, let ${K = \max\limits_{0\le i\le n-1}|\frac{a_i}{a_n}|^{\frac1{n-i}}}$. Then for any root ${\alpha}$ of ${f}$, ${|\alpha| < 2K}$.

Proof: If ${|\alpha| \le K}$, we are done. Else, ${|\alpha^n| \le \sum_{i=0}^{n-1}{|\frac{a_i}{a_n}| |\alpha^i|} \le \sum_{i=0}^{n-1} {K^{n-i} |\alpha^i|} = K^n\frac{\left(\frac{|\alpha|}{K}\right)^n-1}{\frac{|\alpha|}{K}-1} < K^n\frac{\left(\frac{|\alpha|}{K}\right)^n}{\frac{|\alpha|}{K}-1}}$ which means that ${\frac{|\alpha|}{K}-1 < 1}$, i.e., ${|\alpha| < 2K}$. $\Box$

We can combine all these into the following result.

Corollary 8 Given a polynomial ${f(x) = a_nx^n + a_{n-1}x^{n-1} + \dots + a_o}$ with integer coefficients and ${\frac{a_{n-1}}{a_n} \ge 0}$, let ${a_{n-r}}$ be the first nonzero coefficient of ${f}$ after ${a_{n-1}}$ (i.e., ${a_m = 0}$ if ${n-r < m < n-1}$). Let ${G = \max_{i\le n-r}|\frac{a_i}{a_n}|}$. Let ${K = \max_{i\le n-r}|\frac{a_i}{a_n}|^{\frac1{n-i}}}$. If there exists an integer ${m \ge \min(G,\frac{1 + \sqrt{1 + 4G}}{2},G^{1/r} + 1, 2K) + 1}$ such that ${f(m)}$ is prime, then ${f}$ is irreducible.

Proof: As in Lemmas 5, 6 and 7, we can prove that either ${\Re(\alpha) \le 0}$ or ${|\alpha| \le \min(G,\frac{1 + \sqrt{1 + 4G}}{2},G^{1/r} + 1, 2K)}$. Lemma 3 then gives the result. $\Box$

Perhaps the “generalisations” in this section, as they contain no new idea, are like the “cheap generalization” Pólya talks about:

There are two kinds of generalizations. One is cheap and the other is valuable.

It is easy to generalize by diluting a little idea with a big terminology. It is much more difficult to prepare a refined and condensed extract from several good ingredients.

— [G. Pólya]

And also

However, one must not forget that there are two kinds of generalization, one facile and one valuable. One is generalization by dilution, the other is generalization by concentration. Dilution means boiling the meat in a large quantity of water into a thin soup; concentration means condensing a large amount of nutritive material into an essence. The unification of concepts which in the usual view appear to be far removed from each other is concentration. Thus, for example, group theory has concentrated ideas which formerly were found scattered in algebra, number theory, geometry and analysis and which appeared to be very different. Examples of generalizations by dilution would be still easier to quote, but this would be at the risk of offending sensibilities.

— [Pólya and Szegö]

3. Remarks and historical notes

4 was proved for base 10 by Arthur Cohn, a student of Issai Schur, as attributed by Pólya and Szegö in their book, first published in 1925.\cite{PolyaSzego}

It was extended to all bases by Brillhart, Filaseta and Odlyzko in 1981.\cite{BFO} They point out that not all irreducible polynomials can be shown irreducible by a theorem of this sort, as there exist irreducible polynomials that never take a prime value at integral arguments, e.g., ${x^2 + x + 4}$.

A simplified proof was given by M. Ram Murty\cite{Murty}, who points out that this theorem is a (strong) converse to Buniakowski’s conjecture, that any irreducible polynomial takes primes values infinitely often, unless it has a common divisor—this is a generalization of Dirichlet’s theorem about primes in arithmetic progressions. He also extends it to an analogue in function fields. He observes that this theorem sometimes applies when most traditional tests fail, e.g., ${x^4+6x^2+1}$ is reducible modulo ${p}$ for every ${p}$, but ${f(8)=4481}$ is prime which proves that it is irreducible.

4. References
[BFO] John Brillhart, Michael Filaseta, and Andrew Odlyzko. On an irreducibility theorem of A. Cohn. Canadian Journal of Mathematics, 33(5):1055–1059, 1981.
[Murty] M. Ram Murty. Prime numbers and irreducible polynomials. The American Mathematical Monthly, 109(5):452–458, 2002. [JSTOR]
[Polya] G. Polya. Induction and Analogy in Mathematics. Princeton University Press, New Jersey, 1954. Volume 1 of Mathematics and Plausible Reasoning.
[PolyaSzego] G. Pólya and G. Szegö. Problems and Theorems in Analysis. Springer–Verlag, Berlin, 1972.