Overview

  • When is a product of distinct linear integer factors, minus one, irreducible?
  • What is the bound in Pólya’s small-value criterion?
  • Why do 2n+1 prime or unit values prove irreducibility in degree n?

Schur’s theorem

Theorem · the minus-one case of Schur's problem

For distinct integers a1,…,ama_1,\ldots,a_m, with m≥1m\ge1, the polynomial

P(x)=∏i=1m(x−ai)−1P(x)=\prod_{i=1}^{m}(x-a_i)-1

is irreducible over Q\mathbb Q.

Proof

A nontrivial factorization gives monic g,h∈Z[x]g,h\in\mathbb Z[x] of positive degrees with P=ghP=gh. At each aia_i, the integers g(ai),h(ai)g(a_i),h(a_i) multiply to −1-1, so g(ai)+h(ai)=0g(a_i)+h(a_i)=0. The polynomial g+hg+h has degree less than mm and at least mm distinct roots. It must vanish identically, contradicting the monicity of both factors.

Schur posed this problem in 1908. Westlund and Flügel gave the solution in 1909, including the plus-one case below.

References 2

The plus-one case

Theorem

For distinct integers a1,…,ama_1,\ldots,a_m, with m≥1m\ge1, the polynomial P(x)=∏i=1m(x−ai)+1P(x)=\prod_{i=1}^m(x-a_i)+1 is irreducible over Q\mathbb Q, except for integer translates of

x(x−2)+1=(x−1)2,x(x−1)(x−2)(x−3)+1=(x2−3x+1)2.x(x-2)+1=(x-1)^2,\qquad x(x-1)(x-2)(x-3)+1=(x^2-3x+1)^2.

Proof

If P=ghP=gh with monic integral factors of positive degree, then g(ai)h(ai)=1g(a_i)h(a_i)=1, so g(ai)=h(ai)=±1g(a_i)=h(a_i)=\pm1. The polynomial g−hg-h has degree less than mm and vanishes at all aia_i; hence g=hg=h. Thus m=2dm=2d, where d=deg⁡gd=\deg g, and g2−1g^2-1 has 2d2d distinct integer roots.

Let aa be the least root. One of g−1,g+1g-1,g+1 vanishes at aa; the other has dd distinct integer roots b1,…,bd>ab_1,\ldots,b_d>a. Its value at aa has absolute value two, giving

2=∏j=1d(bj−a)≥d!.2=\prod_{j=1}^{d}(b_j-a)\ge d!.

Therefore d≤2d\le2. For d=1d=1, the two roots differ by two. For d=2d=2, the positive differences are 1,21,2, so the opposite factor is (x−a−1)(x−a−2)(x-a-1)(x-a-2). Subtracting two gives the other factor (x−a)(x−a−3)(x-a)(x-a-3). These are exactly the two displayed cases, and their factorizations prove reducibility.

References 1
  • gyoryhajdutijdeman2011 · §1, p. 416 in the published article; p. 2 in the author manuscriptThe classical exception list and attribution to Westlund and Flügel; an elementary proof is given here.Source

Pólya’s criterion

Theorem · Pólya's criterion

Let P∈Z[x]P\in\mathbb Z[x] have degree n≥2n\ge2, and put N=⌈n/2⌉N=\lceil n/2\rceil. If there are nn distinct integers aa such that

0<∣P(a)∣<N!2N,0\lt |P(a)|\lt \frac{N!}{2^N},

then PP is irreducible over Q\mathbb Q.

Proof

If P=QRP=QR with positive-degree integral factors, choose the larger degree d=deg⁡Qd=\deg Q, so N≤d≤n−1N\le d\le n-1. At every selected integer, ∣Q(a)∣≤∣P(a)∣|Q(a)|\le|P(a)|, because the other integral factor is nonzero. Choose d+1d+1 of those arguments and order them as b0<⋯<bdb_0\lt \cdots\lt b_d. Their integer spacing gives ∏i≠j∣bj−bi∣≥j!(d−j)!\prod_{i\ne j}|b_j-b_i|\ge j!(d-j)!. Writing M=max⁡j∣Q(bj)∣M=\max_j|Q(b_j)|, Lagrange interpolation gives

1≤∣lc⁡(Q)∣≤M∑j=0d1j!(d−j)!=M2dd!.1\le|\operatorname{lc}(Q)|\le M\sum_{j=0}^{d}\frac1{j!(d-j)!}=M\frac{2^d}{d!}.

Consequently M≥d!/2d≥N!/2NM\ge d!/2^d\ge N!/2^N, contradicting the strict bound. Gauss's lemma justifies the integral factorization even when PP is not monic.

Example

For P(x)=∏j=09(x−j)+2P(x)=\prod_{j=0}^{9}(x-j)+2, the ten values at 0,…,90,\ldots,9 are all 22. Since 2<5!/25=15/42\lt 5!/2^5=15/4, Pólya proves irreducibility without expanding the polynomial. Nonzero values are essential: an integer zero would itself give a rational linear factor.

References 2

A prime-value criterion

Theorem · prime and unit values

Let f∈Z[x]f\in\mathbb Z[x] be primitive of degree n≥1n\ge1. If ∣f(a)∣|f(a)| is either 11 or a prime at 2n+12n+1 distinct integers aa, then ff is irreducible over Q\mathbb Q.

Proof

For a positive-degree integral factorization f=ghf=gh, every selected argument satisfies g(a)=1g(a)=1, g(a)=−1g(a)=-1, h(a)=1h(a)=1, or h(a)=−1h(a)=-1. Those four equations have at most 2deg⁡g+2deg⁡h=2n2\deg g+2\deg h=2n distinct solutions in total, a contradiction.

Example

At a=0,1,2,3,4a=0,1,2,3,4, the values of x2+x+41x^2+x+41 are 41,43,47,53,6141,43,47,53,61, all prime. Thus the criterion proves irreducibility. It says nothing about primality at all later arguments; at 4040 the value is 41241^2.

References 1
  • ConradIrredQ · Theorem 5.1The finite prime-or-unit-value criterion and its elementary counting proof.Source

Limitations

Remark

A single prime value is insufficient: (x−1)(x+1)(x-1)(x+1) takes the prime value 33 at 22. Conversely, x2+x+4x^2+x+4 is irreducible because its discriminant is −15-15, yet every integer value is even and at least 44. The preceding criterion does not apply.

A single prime value can suffice when extra information controls the factors: Cohn's criterion restricts the coefficients to base digits, while root bounds force nonconstant factors to have large absolute values at a chosen integer. For more general small-value criteria, Levit, Tverberg, and Győry–Hajdu–Tijdeman develop sharper bounds and extensions. The number and sizes of the values are essential hypotheses in these results.

References 4

Questions

ClaimedIrreducibility methods

Must an irreducible integer polynomial take a prime or unit value?

Scope. Primitive polynomials in Z[x], with integer arguments and without changing variables

No. The polynomial f=x2+x+4f=x^2+x+4 is primitive and has discriminant −15-15, so it is irreducible over Q\mathbb Q. For every integer aa, the product a(a+1)a(a+1) is nonnegative and even; hence f(a)f(a) is even and at least four. Thus the prime-value criterion is not necessary for irreducibility.

References 1
  • ConradIrredQ · §5, p. 5Elementary counterexample, proved here. The Claimed label records that the cited source is unpublished exposition.Source
Discuss this question →

Related topics

References

  1. Problem 226

    Schur, Issai. Archiv der Mathematik und Physik, 3, 13, 367, 1908.

    Historical citation verification
  2. Irreducibility criteria of Schur-type and Pólya-type

    Győry, Kálmán and Hajdu, Lajos and Tijdeman, Robert. Monatshefte für Mathematik, 163(4), 415–443, 2011.

    Read the source
  3. Verschiedene Bemerkungen zur Zahlentheorie

    Pólya, George. Jahresbericht der Deutschen Mathematiker-Vereinigung, 28, 31–40, 1919.

    Read the source
  4. Irreducibility tests in Q[T]

    Conrad, Keith. Author-hosted expository note.

    Read the source
  5. Irreducibility of polynomials with low absolute values

    Levit, R. J. Transactions of the American Mathematical Society, 132(2), 297–305, 1968.

    Read the source
  6. On the irreducibility of polynomials taking small values

    Tverberg, Helge. Mathematica Scandinavica, 32, 5–21, 1973.

    Read the source