Overview

  • When does Perron’s coefficient inequality prove irreducibility?
  • Which root bound makes one prime value sufficient?
  • What does Cohn’s theorem say about the digits of a prime?

Perron’s criterion

Theorem · Perron

Let f=xn+an−1xn−1+⋯+a0∈Z[x]f=x^n+a_{n-1}x^{n-1}+\cdots+a_0\in\mathbb Z[x], where n≥2n\ge2 and a0≠0a_0\ne0. If

∣an−1∣>1+∑i=0n−2∣ai∣,|a_{n-1}|>1+\sum_{i=0}^{n-2}|a_i|,

then ff is irreducible over Q\mathbb Q.

Proof

On ∣z∣=1|z|=1, the term an−1zn−1a_{n-1}z^{n-1} strictly dominates the sum of all other terms. Rouché's theorem gives exactly n−1n-1 roots inside the unit circle and one outside. If the monic polynomial factored over Z\mathbb Z, one positive-degree monic factor would have all roots strictly inside. Its constant coefficient would be a nonzero integer whose absolute value is the product of numbers smaller than one, an impossibility.

References 2

Example

Example · x5+3x+1x^5+3x+1

Its reciprocal polynomial is

f∗(x)=x5f(1/x)=x5+3x4+1.f^*(x)=x^5f(1/x)=x^5+3x^4+1.

Now 3>1+13>1+1, so Perron's criterion proves f∗f^* irreducible. Since the constant term of ff is nonzero, coefficient reversal preserves factorizations and proves ff irreducible. The same argument works for xn+3x+1x^n+3x+1 for every n≥2n\ge2.

References 1
  • perron1907Coefficient-dominance theorem; the reversal and worked family are direct applications.Source

A prime-value criterion

Theorem · prime-value criterion

Let f∈Z[x]f\in\mathbb Z[x] be nonconstant. Suppose an integer mm satisfies ∣f(m)∣|f(m)| prime and ∣m−α∣>1|m-\alpha|>1 for every complex root α\alpha of ff. Then ff is irreducible over Q\mathbb Q.

In an integral factorization f=ghf=gh, each positive-degree factor has an integer leading coefficient b≠0b\ne0, so

∣g(m)∣=∣b∣∏g(α)=0∣m−α∣>1.|g(m)|=|b|\prod_{g(\alpha)=0}|m-\alpha|>1.

Both factors would therefore give integer divisors of f(m)f(m) larger than one in absolute value. A practical sufficient condition is a certified root bound ∣α∣≤R|\alpha|\le R and ∣m∣>R+1|m|>R+1.

For example, the roots of x4−10x2+1x^4-10x^2+1 are ±2±3\pm\sqrt2\pm\sqrt3, all of absolute value less than 44. At m=6m=6, the value is 937937, a prime. Every distance is greater than 22, so the criterion proves irreducibility. Primality can be checked by the primes at most 937<31\sqrt{937}\lt 31.

References 2

Cohn’s criterion

Cohn's decimal theorem says that if p=an10n+⋯+a0p=a_n10^n+\cdots+a_0 is prime, with n≥1n\ge1, 0≤ai≤90\le a_i\le9, and an≠0a_n\ne0, then anxn+⋯+a0a_nx^n+\cdots+a_0 is irreducible over Q\mathbb Q. Brillhart, Filaseta, and Odlyzko extend the result to arbitrary integer bases b≥2b\ge2, again assuming a nonconstant digit polynomial. The digit restrictions are essential to this statement; a prime value alone does not imply irreducibility.

For instance, 101101 is prime, so its decimal digits give the irreducible polynomial x2+1x^2+1. The unrestricted prime-value inference fails for (x−1)(x+1)(x-1)(x+1), which takes the prime value 33 at x=2x=2, and is reducible.

References 2

Limitations

The two arguments use integrality in different ways. Perron’s criterion would force a factor to have a nonzero constant coefficient of absolute value less than one. In the prime-value criterion, each nonconstant factor would take an integer value of absolute value greater than one at the chosen point. Both conclusions contradict a factorization in Z[x]\mathbb Z[x].

Neither argument follows from real-rootedness alone. For example, x2−1x^2-1 has only real roots and is reducible.

References 2

A prime constant term

Let f=a0+∑i=1raixni∈Z[x]f=a_0+\sum_{i=1}^r a_i x^{n_i}\in\mathbb Z[x] be primitive, with nonzero coefficients and 0<n1<⋯<nr0<n_1<\cdots<n_r. Suppose ∣a0∣=∑i∣ai∣=p|a_0|=\sum_i|a_i|=p is prime. Set

C=gcd⁡i(xni+sgn⁡(a0ai)),C=\gcd_i\bigl(x^{n_i}+\operatorname{sgn}(a_0a_i)\bigr),

with monic gcd. Then CC is the cyclotomic part, and f/Cf/C is irreducible and nonreciprocal. Thus ff is irreducible exactly when C=1C=1.

Every root has modulus at least 11. The prime constant term forces all but one irreducible factor to have constant term ±1\pm1; those factors are cyclotomic. Equality in the triangle inequality identifies their gcd.

For positive coefficients, irreducibility is equivalent to the nin_i not all having the same 22-adic valuation. For example, 3+x+x2+x53+x+x^2+x^5 is irreducible.

References 1

Questions

SettledIrreducibility methods

Does one prime value prove irreducibility?

Scope. Integer polynomials without additional coefficient or root restrictions

No: (x−1)(x+1)(x-1)(x+1) takes the prime value 33 at x=2x=2. A distance-to-roots bound, a sufficiently large evaluation, or digit restrictions can turn a prime value into an irreducibility criterion.

References 1
Discuss this question →

Related topics

References

  1. Neue Kriterien für die Irreduzibilität algebraischer Gleichungen

    Perron, Oskar. Journal für die reine und angewandte Mathematik, 132, 288–307, 1907.

    Read the source
  2. Polynomials

    Prasolov, Victor V. Springer, Algorithms and Computation in Mathematics, vol. 11, 2004.

    Read the source
  3. Prime numbers and irreducible polynomials

    Murty, M. Ram. The American Mathematical Monthly, 109(5), 452–458, 2002.

    Read the source
  4. An irreducible that factors modulo all primes

    Conrad, Keith. Author-hosted expository note.

    Read the source
  5. On an irreducibility theorem of A. Cohn

    Brillhart, John and Filaseta, Michael and Odlyzko, Andrew. Canadian Journal of Mathematics, 33(5), 1055–1059, 1981.

    Read the source
  6. Polynomials with Special Regard to Reducibility

    Schinzel, Andrzej. Cambridge University Press, Encyclopedia of Mathematics and its Applications, vol. 77, 2000.

    Read the source
  7. Modern Computer Algebra

    von zur Gathen, Joachim and Gerhard, Jürgen. Edition 3. Cambridge University Press, 2013.

    Read the source
  8. An irreducibility criterion for polynomials over integers

    Koley, Biswajit and Reddy, A. Satyanarayana. Bulletin Mathématique de la Société des Sciences Mathématiques de Roumanie, 63(111)(1), 83–89, 2020.

    Read the source