Overview

  • When does irreducibility modulo a prime imply irreducibility over Q?
  • How can factorizations modulo several primes prove irreducibility?
  • Can an irreducible rational polynomial be reducible modulo every prime?

The reduction criterion

Theorem · reduction criterion

Let f∈Z[x]f\in\mathbb Z[x] be primitive of degree n≥2n\ge2. If a prime pp does not divide its leading coefficient and fˉ∈Fp[x]\bar f\in\mathbb F_p[x] is irreducible, then ff is irreducible over Q\mathbb Q.

The leading-coefficient condition is essential. For example, 2x2+3x+1=(2x+1)(x+1)2x^2+3x+1=(2x+1)(x+1) becomes the irreducible linear polynomial x+1x+1 modulo 22. Here reduction lowers the degree, so the criterion does not apply.

Proof

Gauss's lemma turns a rational factorization into f=ghf=gh in Z[x]\mathbb Z[x]. Since the product of the leading coefficients is not divisible by pp, both factors retain their positive degrees after reduction. Their reductions would factor fˉ\bar f, a contradiction.

References 1

Factor-degree restrictions

Let f∈Z[x]f\in\mathbb Z[x] be primitive of degree nn, and let pp not divide its leading coefficient. Factor its reduction into monic irreducible polynomials, recording each factor with its multiplicity. If their degrees are d1,…,drd_1,\ldots,d_r, define

Dp={∑i∈Idi:I⊆{1,…,r}}∩{1,…,n−1}.D_p=\left\{\sum_{i\in I}d_i:I\subseteq\{1,\ldots,r\}\right\}\cap\{1,\ldots,n-1\}.

Every proper rational factor of ff has degree in DpD_p. Indeed, Gauss’s lemma gives integral factors, their degrees are preserved modulo pp, and each reduced factor is a product of some of the listed irreducible factors.

If primes p1,…,psp_1,\ldots,p_s satisfy

Dp1∩⋯∩Dps=∅,D_{p_1}\cap\cdots\cap D_{p_s}=\varnothing,

then ff is irreducible over Q\mathbb Q. It is enough to test degrees at most ⌊n/2⌋\lfloor n/2\rfloor, since a reducible polynomial has a factor in that range. Repeated factors in a reduction are allowed in this degree argument; they must be counted with multiplicity.

References 1
  • Prasolov2004 · Chapter 2Reduction and coefficient methods for rational irreducibility; the subset-sum formulation follows directly from reduction of an integral factorization.Source

Example

Example · f=x4+x3+x+2f=x^4+x^3+x+2

f mod 2=x(x3+x2+1),f mod 3=(x2+1)(x2+x−1).\begin{aligned}f\bmod2&=x(x^3+x^2+1),\\ f\bmod3&=(x^2+1)(x^2+x-1).\end{aligned}

The cubic has no root in F2\mathbb F_2, so it is irreducible there. The two quadratics have no roots in F3\mathbb F_3, so they are irreducible there. Modulo 22, a proper rational factor could have degree 11 or 33. Modulo 33, it could only have degree 22. The sets are disjoint; hence ff is irreducible over Q\mathbb Q.

References 1
  • ConradIrredQ · §3The reduction principle underlying the certificate; these two displayed factorizations are calculated for this entry.Source

A polynomial reducible modulo every prime

The polynomial x4+1x^4+1 is irreducible over Q\mathbb Q: translating by 11 gives x4+4x3+6x2+4x+2x^4+4x^3+6x^2+4x+2, Eisenstein at 22. Nevertheless it is reducible modulo every prime. At 22 it is (x+1)4(x+1)^4. For odd pp, its roots are primitive eighth roots of unity; since p2≡1(mod8)p^2\equiv1\pmod8, they lie in Fp2\mathbb F_{p^2}, so all irreducible factors have degree at most two.

In fact degree 22 remains compatible with every reduction, so even intersecting all the sets DpD_p does not prove irreducibility here. Indeed, C2×C2C_2\times C_2, the Galois group, contains no 44-cycle. For a separable irreducible polynomial over Q\mathbb Q, Chebotarev and the Frobenius factorization theorem show that an irreducible good reduction exists exactly when the group contains an nn-cycle.

Modular factorizations

Modulo 2

(x+1)4(x + 1)^{4}
Factor degrees
1 + 1 + 1 + 1
Squarefree reduction
No
Possible proper factor degrees
1, 2, 3

The reduction has repeated factors, so the Frobenius cycle criterion does not apply. It still restricts factor degrees because the degree is preserved.

References 2

Using other local information

If a degree remains in every set DpD_p considered, these reductions have not excluded a factor of that degree. Newton polygons can give additional restrictions from coefficient valuations, including at primes where the reduction has repeated factors. Intersecting all the available degree sets may then prove irreducibility.

References 1

Connections and evidence

Classical

How can several local tests prove irreducibility?

Different local tests constrain the same hypothetical factor degree. Their intersection can be empty even when every modular reduction is reducible.

Scope. Let f∈Z[X]f\in\mathbb Z[X] be monic and separable, of degree n≥2n\ge2, with f(0)≠0f(0)\ne0.

How can several local tests prove irreducibility?Different local tests constrain the same hypothetical factor degree. Their intersection can be empty even when every modular reduction is reducible. Connection 1: Factor modulo selected primes leads to Subset sums of modular degrees. Gauss’s lemma and monicity preserve the degree of every rational factor after reduction; its degree is a subset sum, counting modular factors with multiplicity. Connection 2: Compute p-adic Newton polygons leads to Multiples of slope denominators. On an edge of reduced slope −a/b, each local factor uses a multiple of b roots, bounded by the edge length. Connection 3: Subset sums of modular degrees is an input to Intersect permitted proper degrees. Intersect the degree sets supplied by the selected modular factorizations. Connection 4: Multiples of slope denominators is an input to Intersect permitted proper degrees. Include the degree sets supplied by every selected Newton polygon in the same intersection. Connection 5: Intersect permitted proper degrees leads to f is irreducible over ℚ. A proper rational factor would have a positive degree below n belonging to every displayed degree set, contradicting an empty intersection. Connection 6: f is irreducible over ℚ is equivalent to Galois action is transitive. For a separable polynomial, irreducible factors correspond to Galois orbits on the roots; one factor is equivalent to one orbit.Factor modulo selected primes — related articleFactor modulo selectedprimesSubset sums of modular degrees — related articleSubset sums of modulardegreesCompute p-adic Newton polygons — related articleCompute p-adic NewtonpolygonsMultiples of slope denominators — related articleMultiples of slopedenominatorsIntersect permitted proper degrees — related articleIntersect permitted properdegreesf is irreducible over ℚ — related articlef is irreducible over ℚGalois action is transitive — related articleGalois action is transitiveConnection 1: Gauss’s lemma and monicity preserve the degree of every rational factor after reduction; its degree is a subset sum, counting modular factors with multiplicity.Reduction of factors [1]Connection 2: On an edge of reduced slope −a/b, each local factor uses a multiple of b roots, bounded by the edge length.Root valuations [2]Connection 3: Intersect the degree sets supplied by the selected modular factorizations.Necessary restrictions[3]Connection 4: Include the degree sets supplied by every selected Newton polygon in the same intersection.Necessary restrictions[4]Connection 5: A proper rational factor would have a positive degree below n belonging to every displayed degree set, contradicting an empty intersection.If the intersection isempty [5]Connection 6: For a separable polynomial, irreducible factors correspond to Galois orbits on the roots; one factor is equivalent to one orbit.Factor–orbitcorrespondence [6]
Linked nodes open articles; numbered connections open the evidence below.Open full-size diagram

deduction or information flow equivalence

If the irreducible modular factor degrees at a prime pp, repeated according to multiplicity, are dp,1,…,dp,rd_{p,1},\ldots,d_{p,r}, every proper rational factor has degree in

Dp={∑i∈Idp,i:I⊆{1,…,r}}∩{1,…,n−1}.D_p=\left\{\sum_{i\in I}d_{p,i}:I\subseteq\{1,\ldots,r\}\right\}\cap\{1,\ldots,n-1\}.

If the Newton edges at a prime qq have reduced slopes −aj/bj-a_j/b_j, with bj>0b_j>0, and horizontal lengths LjL_j, the corresponding restriction is

Nq={∑jbjkj:kj∈Z, 0≤kj≤Lj/bj}∩{1,…,n−1}.N_q=\left\{\sum_j b_jk_j: k_j\in\mathbb Z,\ 0\le k_j\le L_j/b_j\right\}\cap\{1,\ldots,n-1\}.

Thus ⋂pDp∩⋂qNq=∅\bigcap_pD_p\cap\bigcap_qN_q=\varnothing proves irreducibility. One may use either kind of test alone. These are necessary degree restrictions; they do not assert that each permitted degree actually occurs. Squarefree reduction is unnecessary for this argument, but modular multiplicities must be counted.

The quartic example above has D2={1,3}D_2=\{1,3\} and D3={2}D_3=\{2\}. Two reducible reductions therefore certify rational irreducibility. The degree-six exponential example gives the parallel Newton-polygon certificate N2={2,4}N_2=\{2,4\}, N3={3}N_3=\{3\}.

Inspect all 6 connections and exact references
Evidence for each connection
ConnectionStatement and source
1Factor modulo selected primes → Subset sums of modular degreesDeduction

Gauss’s lemma and monicity preserve the degree of every rational factor after reduction; its degree is a subset sum, counting modular factors with multiplicity.

  • R1 · ConradTheorem 3.1 and its proof, p. 3The subset-sum restriction is the direct reduction-of-factors consequence used here.Primary source
2Compute p-adic Newton polygons → Multiples of slope denominatorsDeduction

On an edge of reduced slope −a/b, each local factor uses a multiple of b roots, bounded by the edge length.

  • R2 · Hajir (2005)Theorem 2.1, p. 520The root–slope theorem; integrality of a slope factor’s constant-term valuation gives the denominator restriction.Primary source
3Subset sums of modular degrees → Intersect permitted proper degreesConstruction / input

Intersect the degree sets supplied by the selected modular factorizations.

4Multiples of slope denominators → Intersect permitted proper degreesConstruction / input

Include the degree sets supplied by every selected Newton polygon in the same intersection.

5Intersect permitted proper degrees → f is irreducible over ℚDeduction

A proper rational factor would have a positive degree below n belonging to every displayed degree set, contradicting an empty intersection.

6f is irreducible over ℚ ↔ Galois action is transitiveEquivalence

For a separable polynomial, irreducible factors correspond to Galois orbits on the roots; one factor is equivalent to one orbit.

Sources and scope checked .

Questions

SettledIrreducibility methods

Does every irreducible rational polynomial have an irreducible reduction?

Scope. Separable irreducible polynomials over Q; good primes preserve degree and give squarefree reduction.

No. For a polynomial of degree nn, an irreducible reduction at a good prime exists exactly when its Galois group contains an nn-cycle. The polynomial x4+1x^4+1 is a counterexample: it is irreducible over Q\mathbb Q, and its Klein four-group contains no 4-cycle.

References 2
Discuss this question →

Related topics

References

  1. Irreducibility tests in Q[T]

    Conrad, Keith. Author-hosted expository note.

    Read the source
  2. Polynomials

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

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

    Conrad, Keith. Author-hosted expository note.

    Read the source
  4. Chebotarëv and his density theorem

    Stevenhagen, Peter and Lenstra, Jr., Hendrik W. The Mathematical Intelligencer, 18(2), 26–37, 1996.

    Read the source
  5. Schönemann–Eisenstein–Dumas-type irreducibility conditions that use arbitrarily many prime numbers

    Bonciocat, Nicolae Ciprian. Communications in Algebra, 43(8), 3102–3122, 2015.

    Read the source
  6. On the Galois group of generalized Laguerre polynomials

    Hajir, Farshid. Journal de théorie des nombres de Bordeaux, 17(2), 517–525, 2005.

    Read the source
  7. Galois groups as permutation groups

    Conrad, Keith. Author-hosted expository notes.

    Read the source