Newton polytope

In mathematics, the Newton polytope is an integral polytope associated with a multivariate polynomial that can be used in the asymptotic analysis of those polynomials. It is a generalization of the Kruskal–Newton diagram developed for the analysis of bivariant polynomials.

Given a vector ${\displaystyle \mathbf {x} =(x_{1},\ldots ,x_{n})}$ of variables and a finite family ${\displaystyle (\mathbf {a} _{k})_{k}}$ of pairwise distinct vectors from ${\displaystyle \mathbb {N} ^{n}}$ each encoding the exponents within a monomial, consider the multivariate polynomial

$${\displaystyle f(\mathbf {x} )=\sum _{k}c_{k}\mathbf {x} ^{\mathbf {a} _{k}}}$$

where we use the shorthand notation ${\displaystyle (x_{1},\ldots ,x_{n})^{(y_{1},\ldots ,y_{n})}}$ for the monomial ${\displaystyle x_{1}^{y_{1}}x_{2}^{y_{2}}\cdots x_{n}^{y_{n}}}$. Then the Newton polytope associated to ${\displaystyle f}$ is the convex hull of the vectors ${\displaystyle \mathbf {a} _{k}}$; that is

$${\displaystyle \operatorname {Newt} (f)=\left\{\sum _{k}\alpha _{k}\mathbf {a} _{k}:\sum _{k}\alpha _{k}=1\;\&\;\forall j\,\,\alpha _{j}\geq 0\right\}\!.}$$

In order to make this well-defined, we assume that all coefficients ${\displaystyle c_{k}}$ are non-zero. The Newton polytope satisfies the following homomorphism-type property: $${\displaystyle \operatorname {Newt} (fg)=\operatorname {Newt} (f)+\operatorname {Newt} (g)}$$ where the addition is in the sense of Minkowski.

Newton polytopes are the central object of study in tropical geometry and characterize the Gröbner bases for an ideal.