Overview

  • When does the Newton polytope prove absolute irreducibility?
  • How are monomial factors detected?
  • What can be concluded when the polytope decomposes?

Newton polytopes and products

For f=∑acaxaf=\sum_{\mathbf a}c_{\mathbf a}x^{\mathbf a}, its Newton polytope is

Newt⁡(f)=conv⁡{a∈Z≥0r:ca≠0}.\operatorname{Newt}(f)=\operatorname{conv}\{\mathbf a\in\mathbb Z_{\ge0}^{r}:c_{\mathbf a}\ne0\}.

For a product, Newt⁡(gh)=Newt⁡(g)+Newt⁡(h)\operatorname{Newt}(gh)=\operatorname{Newt}(g)+\operatorname{Newt}(h), where the right side is the Minkowski sum. For a linear weight with unique maxima on the two factor polytopes, the product of the highest-weight terms is nonzero and is the unique highest-weight term of the product. Varying the weight determines the polytope and proves the identity.

A lattice polytope is integrally indecomposable if every expression as a sum of two lattice polytopes has a point as one summand. A point polytope corresponds to a monomial, not necessarily to a constant.

References 1
  • GaoLauder2001 · §2, Lemma 1 and Corollary 2Product formula, with its origin attributed to Ostrowski, and the monomial caveat.Source

The indecomposability criterion

Theorem (Newton-polytope criterion)

Let f∈K[x1,…,xr]f\in K[x_1,\ldots,x_r] be nonconstant and divisible by no variable xix_i. If Newt⁡(f)\operatorname{Newt}(f) is integrally indecomposable, then ff is absolutely irreducible.

Any factorization over K‾\overline K decomposes the same lattice polytope. One factor must therefore have point support and be a monomial. Since no variable divides ff, that factor is a nonzero constant. This excludes every nontrivial factorization.

The criterion depends only on the support. It remains valid after changing the nonzero coefficients, over any field, provided the support is unchanged.

References 2

Connections and evidence

Published

How can exponent geometry prove absolute irreducibility?

A polynomial factorization forces a Minkowski sum of lattice polytopes. If the support cannot decompose and monomial factors are excluded, no factorization survives over any field extension.

Scope. Let kk be any field and f∈k[X1,…,Xr]f\in k[X_1,\ldots,X_r] be nonconstant. Write P=Newt⁡(f)P=\operatorname{Newt}(f) for the convex hull of its exponent vectors.

How can exponent geometry prove absolute irreducibility?A polynomial factorization forces a Minkowski sum of lattice polytopes. If the support cannot decompose and monomial factors are excluded, no factorization survives over any field extension. Connection 1: Any factorization over k̄: f = gh leads to P = Newt(g) + Newt(h). The Newton polytope of a product is the Minkowski sum of the factor polytopes, also over the algebraic closure. Connection 2: Triangular support; gcd = 1 leads to P integrally indecomposable. For a lattice triangle with vertices v₀,v₁,v₂, gcd of all coordinates of v₀−v₁ and v₀−v₂ equal to one implies integral indecomposability. Connection 3: P = Newt(g) + Newt(h) is an input to AND. Every hypothetical factorization supplies this decomposition of P. Connection 4: P integrally indecomposable is an input to AND. Integral indecomposability forces a point summand in every such decomposition. Connection 5: AND leads to One factor is a monomial. A point Newton polytope means that the corresponding nonzero factor has exactly one monomial. Connection 6: One factor is a monomial is an input to AND. This reduces every hypothetical factorization to one with a monomial factor. Connection 7: No variable divides f is an input to AND. A nonconstant monomial divisor would contain at least one variable as a divisor. Connection 8: AND leads to f absolutely irreducible. Every factorization over the algebraic closure has a constant factor, which is exactly absolute irreducibility.Any factorization over k̄: f = gh — related articleAny factorization over k̄:f = ghP = Newt(g) + Newt(h) — related articleP = Newt(g) + Newt(h)Triangular support; gcd = 1 — related articleTriangular support; gcd =1P integrally indecomposable — related articleP integrallyindecomposableANDANDOne factor is a monomial — related articleOne factor is a monomialNo variable divides f — related articleNo variable divides fANDANDf absolutely irreducible — related articlef absolutely irreducibleConnection 1: The Newton polytope of a product is the Minkowski sum of the factor polytopes, also over the algebraic closure.Ostrowski product formula[1]Connection 2: For a lattice triangle with vertices v₀,v₁,v₂, gcd of all coordinates of v₀−v₁ and v₀−v₂ equal to one implies integral indecomposability.Gcd of vertex differences[2]Connection 3: Every hypothetical factorization supplies this decomposition of P.A lattice decomposition[3]Connection 4: Integral indecomposability forces a point summand in every such decomposition.No nontrivialdecomposition [4]Connection 5: A point Newton polytope means that the corresponding nonzero factor has exactly one monomial.A point summand [5]Connection 6: This reduces every hypothetical factorization to one with a monomial factor.A monomial factor [6]Connection 7: A nonconstant monomial divisor would contain at least one variable as a divisor.Exclude variable factors[7]Connection 8: Every factorization over the algebraic closure has a constant factor, which is exactly absolute irreducibility.The monomial is a unit[8]
Linked nodes open articles; numbered connections open the evidence below.Open full-size diagram

deduction or information flowAND joint hypotheses

A lattice polytope is integrally indecomposable if every Minkowski decomposition into lattice polytopes has a point as one summand. If PP has this property and no variable divides ff, then ff is absolutely irreducible. The diagram proves this over k‾\overline k; no characteristic restriction is needed. A nonzero constant term suffices to exclude variable divisors.

For a lattice triangle conv⁡(v0,v1,v2)\operatorname{conv}(v_0,v_1,v_2), indecomposability is equivalent to

gcd⁡(all coordinates of v0−v1 and v0−v2)=1.\gcd\bigl(\text{all coordinates of }v_0-v_1\text{ and }v_0-v_2\bigr)=1.

For example, for every field kk and every λ∈k\lambda\in k,

1+X2+Y3+λXY1+X^2+Y^3+\lambda XY

is absolutely irreducible: its vertices are (0,0),(2,0),(0,3)(0,0),(2,0),(0,3), the extra exponent (1,1)(1,1) lies inside the triangle, and gcd⁡(2,3)=1\gcd(2,3)=1. More generally, arbitrary interior coefficients are allowed whenever the three vertex coefficients remain nonzero.

The arrow has no converse: a decomposable support may still carry an irreducible polynomial. Also, X(1+X+Y)X(1+X+Y) has an indecomposable translated triangle but is reducible; excluding monomial factors is essential.

Inspect all 8 connections and exact references
Evidence for each connection
ConnectionStatement and source
1Any factorization over k̄: f = gh → P = Newt(g) + Newt(h)Deduction

The Newton polytope of a product is the Minkowski sum of the factor polytopes, also over the algebraic closure.

  • R1 · Gao–Lauder (2001)§2.1, Lemma 1 and Corollary 2, p. 5 of arXiv:math/0012099v1Product formula attributed to Ostrowski; absolute-irreducibility criterion explicitly excludes variable divisors.Primary source
2Triangular support; gcd = 1 → P integrally indecomposableDeduction

For a lattice triangle with vertices v₀,v₁,v₂, gcd of all coordinates of v₀−v₁ and v₀−v₂ equal to one implies integral indecomposability.

  • R2 · Gao (2001)Theorem 4.2; restated as Gao–Lauder, Theorem 7, p. 8 of arXiv:math/0012099v1The pyramid criterion specializes to the exact gcd criterion for triangles; the linked primary restatement supplies the complete statement.Primary source
3P = Newt(g) + Newt(h) → ANDConstruction / input

Every hypothetical factorization supplies this decomposition of P.

4P integrally indecomposable → ANDConstruction / input

Integral indecomposability forces a point summand in every such decomposition.

5AND → One factor is a monomialDeduction

A point Newton polytope means that the corresponding nonzero factor has exactly one monomial.

  • R1 · Gao–Lauder (2001)§2.1, Lemma 1 and Corollary 2, p. 5 of arXiv:math/0012099v1Product formula attributed to Ostrowski; absolute-irreducibility criterion explicitly excludes variable divisors.Primary source
6One factor is a monomial → ANDConstruction / input

This reduces every hypothetical factorization to one with a monomial factor.

7No variable divides f → ANDConstruction / input

A nonconstant monomial divisor would contain at least one variable as a divisor.

8AND → f absolutely irreducibleDeduction

Every factorization over the algebraic closure has a constant factor, which is exactly absolute irreducibility.

  • R1 · Gao–Lauder (2001)§2.1, Lemma 1 and Corollary 2, p. 5 of arXiv:math/0012099v1Product formula attributed to Ostrowski; absolute-irreducibility criterion explicitly excludes variable divisors.Primary source

Sources and scope checked .

Example

Example

Consider f=1+x2y+xy3f=1+x^2y+xy^3 over any field. Its Newton polygon has vertices (0,0),(2,1),(1,3)(0,0),(2,1),(1,3). The oriented edge vectors are (2,1),(−1,2),(−1,−3)(2,1),(-1,2),(-1,-3), all primitive integer vectors.

A nontrivial Minkowski summand of a triangle must itself be a triangle with parallel corresponding edges; a segment summand would introduce another edge direction. The two triangular summands would therefore divide each edge into two positive integral lengths. A primitive edge has lattice length one, so this is impossible. The polygon is integrally indecomposable. The nonzero constant term excludes nonconstant monomial factors. The criterion therefore proves absolute irreducibility in every characteristic.

References 1

Limitations

Monomial factors. The polynomial x(1+x+y)x(1+x+y) has a translated indecomposable triangle as its Newton polygon, but has a nonconstant monomial factor. The hypothesis excluding variable divisors is essential.

The converse is false. Over a field of characteristic different from two, x2+y2+1x^2+y^2+1 is absolutely irreducible, although its polygon is twice the standard simplex and hence decomposable. Its projective homogenization X2+Y2+Z2X^2+Y^2+Z^2 is nonsingular; a reducible projective conic over an algebraically closed field is a pair of lines, possibly repeated, and is singular. In characteristic two this example becomes (x+y+1)2(x+y+1)^2, so the characteristic restriction is necessary.

References 1
  • GaoLauder2001 · §5A decomposable polytope makes the shape test inconclusive; the examples are direct checks.Source

Laurent polynomials and changes of exponents

In the Laurent polynomial ring K[x1±1,…,xr±1]K[x_1^{\pm1},\ldots,x_r^{\pm1}], every nonzero scalar times a monomial is a unit. Thus the polytope criterion has a simpler form: a Laurent polynomial with at least two terms and an integrally indecomposable Newton polytope is absolutely irreducible in the Laurent ring.

A matrix in GLr(Z)\mathrm{GL}_r(\mathbb Z) defines an invertible monomial substitution. It preserves Laurent irreducibility and takes Newton polytopes to their images under the corresponding lattice map. For ordinary polynomials, any common monomial factor must be removed separately.

Example

The polynomial xayb−1x^ay^b-1, with a,b≥0a,b\ge0 and (a,b)≠(0,0)(a,b)\ne(0,0), is absolutely irreducible exactly when gcd⁡(a,b)=1\gcd(a,b)=1. If the gcd is one, a lattice change sends its exponent vector to (1,0)(1,0). If the gcd is e>1e>1, it is (xa/eyb/e)e−1(x^{a/e}y^{b/e})^e-1, which factors over K‾\overline K, possibly with repeated factors.

References 1

When the polytope decomposes

A possible Minkowski decomposition is a necessary condition on the supports of two factors. The coefficients must still satisfy their product equations. Thus the polytope can rule out a factorization without solving for any coefficients, but a decomposition does not construct factors.

For example, (1+x)(1+y)(1+x)(1+y) and 1+x+y+2xy1+x+y+2xy have the same square Newton polygon over Q\mathbb Q. The first factors. The second is absolutely irreducible: as a polynomial in yy, it is (1+2x)y+(1+x)(1+2x)y+(1+x), and these two coefficients are coprime even over Q‾\overline{\mathbb Q}.

When the polygon has few possible summands, its geometry can also reduce the work needed by a factorization algorithm. Weimann’s published 2025 method uses such information under explicit nondegeneracy and characteristic assumptions.

References 2

Related topics

References

  1. Decomposition of Polytopes and Polynomials

    Gao, Shuhong and Lauder, Alan G. B. Discrete & Computational Geometry, 26(1), 89–104, 2001.

    Read the source
  2. Absolute irreducibility of polynomials via Newton polytopes

    Gao, Shuhong. Journal of Algebra, 237(2), 501–520, 2001.

    Read the source
  3. Improvements of convex-dense factorization of bivariate polynomials

    Weimann, Martin. Polynesian Journal of Mathematics, 2(4), 1–34, 2025.

    Read the source