A result on the prime divisors of polynomial values

 Cropped from source

Issai Schur was a mathematician who obtained his doctorate over a hundred years ago. He was a student of the great group theorist Ferdinand Frobenius. Schur worked in various areas and proved many deep results, including some theorems in basic number theory.

Today we discuss a nice lemma due to Schur. Actually, it’s a theorem.

There are many things named after Schur. Wikipedia has compiled a list of them:

Frobenius-Schur indicator Herz-Schur multiplier Jordan-Schur theorem Lehmer-Schur algorithm Schur algebra Schur class Schur complement method Schur complement Schur decomposition Schur functor Schur index Schur multiplier Schur number Schur orthogonality relations Schur polynomial Schur product theorem Schur test Schur-convex function Schur-Horn theorem Schur-Weyl duality Schur-Zassenhaus theorem Schur’s inequality Schur’s lemma (from Riemannian geometry) Schur’s lemma Schur’s property Schur’s theorem

This lists two Schur lemmas. But when you click on Wikipedia’s “Schur’s lemma” page, there are three Schur lemmas. No, wait—there are four, including one called “Schur’s test.” But the result we are interested in is classed as a theorem. Wikipedia’s single page for “Schur’s theorem” lists not just five but six Schur’s theorems. This is one higher than the count eventually reached in Monty Python’s famous “Spanish Inquisition” skit. We want the sixth one, which is quite useful—like a lemma.

## The Result

Here is Schur’s lemma—no, theorem—published in 1912.

Theorem 1 Let ${f(x)}$ be a non-constant polynomial with integer coefficients. Then ${f}$ has infinitely many prime divisors.

Here ${f}$ has infinitely many prime divisors means that the number of primes that arise as divisors of the values ${f(n)}$ as ${n=0,1,2,3,\dots}$ is infinite. Note, this works even if the polynomial is reducible or contains some trivial factors. Thus

$\displaystyle f(x) = 10x^{3} + 100,$

is fine. As is ${x^{2}-1}$.

Schur’s theorem is quite fun, even just to prove. Here is a nice version from a paper by Ram Murty, whose work on extensions of Euclid’s famous proof of the infinitude of primes we covered last summer. We follow Murty’s proof.

Proof: Suppose ${f(x)}$ is an integral polynomial of least degree for which the statement fails,

$\displaystyle f(x) = a_{n}x^{n} + a_{n-1}x^{n-1} + \cdots + a_{1}x + a_{0},$

where ${a_n > 0}$. If ${a_{0}=0}$, then ${f(x)/x}$ is an integral polynomial of lower degree for which it must fail, so we have ${a_{0}\neq 0}$. By hypothesis, ${f}$ has only finitely many prime divisors, which we can represent as ${p_{1}, \dots, p_{r}}$. For each natural number ${m}$, define ${P = a_0 \cdot p_1 \cdots p_r}$ and

$\displaystyle Q_{m} = f(P^{m}).$

Now ${P > 1}$ because ${f(x)}$ can take the value ${+1}$ or ${-1}$ only finitely often, and all sufficiently large ${m}$ give ${Q_m > 1}$ for the same reason. Because ${P}$ includes ${a_0}$ as a factor, ${Q_m}$ is divisible by ${a_0}$, giving

$\displaystyle f(P^m) = a_0(K + 1)$

for some integer ${K}$ that by choice of ${P}$ is divisible by all of ${p_1,\dots,p_r}$. But then as in Euclid’s proof, ${K+1}$ is co-prime to all those primes, so it must furnish a prime divisor of ${f}$ that is not among them. This is a contradiction. $\Box$

This proof was simple but clever. Here is a concrete version for the polynomial ${x^{2} + a}$, which may help in understanding the proof: Say ${f(x)=x^{2} + a}$ is divisible by only ${p_{1},\dots,p_{r}}$ say. Let ${P=p_{1} \cdots p_{r}.}$ The trick is to look at

$\displaystyle f(aPt) = (aPt)^{2} + a = ag(t),$

where

$\displaystyle g(t) = a(Pt)^{2} + 1.$

For some ${n}$ large enough there exists a prime ${p}$ that divides ${g(n)}$. But this prime divides ${f(aPn)}$ and so ${p = p_{i}}$ for some ${i}$. But then ${g(n)}$ modulo ${p_{i}}$ is equal to ${1}$ which is a contradiction.

## An Application

As the proof hints, Schur’s theorem is a proper extension of Euclid’s, which is just the case ${f(x) = x}$. Here is a less-obvious application:

Theorem 2 Suppose that ${f(x)}$ is a polynomial with integer coefficients. Assume that ${f(n)}$ is a perfect square for all integers ${n}$ large enough. Then ${f(x)=g(x)^{2}}$ for some polynomial ${g(x)}$.

There are many proofs of this theorem. One uses the famous Hilbert Irreducibility theorem, which we also discussed last summer. Another proof uses Schur’s lemma and the fact that if ${f(x)}$ and ${g(x)}$ are products of irreducible integer polynomials that are collectively distinct then the ideal generated by ${f}$ and ${g}$ contains a positive integer—namely, their resultant ${R(f,g)}$. Again following Murty’s paper:

Proof: We can factor ${f(x)=g(x)^{2}h(x)}$, where ${h(x)}$ is a product of irreducible integer polynomials, and the goal is to show that ${h(x) = 1}$. If ${h}$ has positive degree, then by Schur’s theorem, there are infinitely many prime divisors ${p}$ of ${h}$. The square-freeness of ${h}$ implies that it shares no factors with its derivative ${h'}$, so ${r = R(h,h') > 0}$. We need only take ${p}$ dividing ${h(n)}$ for some ${n}$ large enough that ${f(n)}$ is a perfect square but such that ${p}$ does not divide ${r}$. Then the order of ${p}$ dividing ${f(n)}$ must be even, which implies that the order of ${p}$ dividing ${h}$ must be even. So ${p^2}$ divides ${h(n)}$.

By a similar token, since ${p}$ divides ${h(n+p)}$ as well and ${f(n+p)}$ is a perfect square, we get that ${p^2}$ divides ${h(n+p)}$. Now ${h(n+p)}$ is congruent to ${h(n) + ph'(n)}$ modulo ${p^2}$, and since ${p^2}$ divides ${h(n)}$ from before, it follows that ${p}$ divides ${h'(n)}$. Since ${r}$ belongs to the ideal generated by ${h}$ and ${h'}$ in ${\mathbb{Z}[x]}$, ${p}$ divides ${r}$ too, but this contradicts the choice of ${p}$. So ${h(x)}$ must be a constant. Since the notion of “irreducible” with ${\mathbb{Z}[x]}$ applies to constants, any square dividing ${h}$ is already part of ${g(x)}$, so ${h}$ must be a product of distinct primes. This forestalls ${p^2}$ dividing ${h}$ in the above, so we must have ${h = 1}$. $\Box$

## Open Problems

We did mention Schur’s long list of things named after him. Did people name things after others more often years ago? Or is naming them still common-place?

[fixed last proof]

1. January 30, 2019 10:42 am

I’m confused… why is it that p^2 dividing h(n) implies p divides h'(n)? This obviously resembles the fact that if f^2 divides h then f divides h’, but with actual numbers plugged in. It’s not obvious why it would still work in that context; because while you can differentiate h, the polynomial, you can’t different h(n), the number…

• February 2, 2019 12:03 pm

Thanks—you are right, the shortcut was incorrect.