Decomposing a Random Newton Polygon

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram CDF Player or other Wolfram Language products.

Requires a Wolfram Notebook System

Edit on desktop, mobile and cloud with any Wolfram Language product.

Consider a Newton polygon for a set of points in the plane with convex hull . The construction of the polygon is slightly different from the traditional one as follows (which is why some use the term Newton polytope).


The point is associated with the monomial , and a set of points in the plane is associated with the polynomial , that is, the sum of the monomials corresponding to the points in the set. For example, is associated with . Note that coefficients do not matter.

A polynomial that can be factored into a product of polynomials of lower degree is called reducible. The Newton polygon of a reducible polynomial corresponds to the Minkowski sum of the Newton polygons of the factors of . If a Newton polygon corresponds to a reducible polynomial, then is called decomposable.

In this Demonstration, a random set of points is chosen inside the square of side length from 1 to 8. The program checks if the corresponding Newton polygon is decomposable or indecomposable by checking all possible decompositions based on the boundary of the polygon; in the latter case, the corresponding polynomial is irreducible over any field, that is, absolutely (or geometrically) irreducible.


Contributed by: Kevin Choi (August 2016)
Open content licensed under CC BY-NC-SA




[1] S. Gao and A. G. B. Lauder, "Decomposition of Polytopes and Polynomials," Discrete and Computational Geometry, 26(1), 2001 pp. 89–104. doi:10.1007/s00454-001-0024-0.

Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.