Chapter 36: Polyhedral and Ehrhart Combinatorics

Why is the lattice-point count in a dilated polytope polynomial?

A polytope is a bounded convex hull of finitely many points. A lattice polytope has vertices in the integer lattice $\mathbb Z^d$. For a nonnegative integer $t$, its dilation is $tP=\{tx:x\in P\}$, and its lattice-point count is

$$ L_P(t)=|tP\cap\mathbb Z^d|. $$

Dilation changes the geometry continuously, while integer points enter discretely. Why should the resulting count obey one polynomial rather than an arbitrary staircase? The integrality of the vertices is the organizing condition. Rational vertices generally produce a quasipolynomial, with a different polynomial formula on different residue classes.

The foundation example is

$$ Q=\operatorname{conv}\{(0,0),(2,0),(0,2)\} =\{(x,y):x\ge0,\ y\ge0,\ x+y\le2\}. $$

Its dilation has integer points with $x,y\ge0$ and $x+y\le2t$. Count by fixing $x$:

$$ L_Q(t)=\sum_{x=0}^{2t}(2t-x+1) =\frac{(2t+1)(2t+2)}2=2t^2+3t+1. $$

This is a proof for every nonnegative integer $t$, not an extrapolation from a few numerical values. The leading coefficient is the triangle's area, two. For positive $t$, relative interior means strict satisfaction of the three facet inequalities: $x\gt0,y\gt0,x+y\lt2t$. Substituting $u=x-1,v=y-1$ gives $u,v\ge0$ and $u+v\le2t-3$. Hence

$$ L_{Q^{\circ}}(t)=2t^2-3t+1=L_Q(-t),\qquad t\ge1. $$

At $t=1$ the interior count is zero, and at $t=2$ it is three. The negative argument means evaluation of the polynomial extension; it does not mean counting points in the reflected polytope $(-t)Q$. This identity is the two-dimensional case of Ehrhart–Macdonald reciprocity.

For a full-dimensional lattice polytope $P\subseteq\mathbb R^d$, Ehrhart's theorem states that $L_P$ is a degree-$d$ polynomial. Its constant term is one and its leading coefficient is ordinary volume, with the lattice unit cube having volume one. Reciprocity states $L_{P^{\circ}}(t)=(-1)^dL_P(-t)$ for positive integers $t$. Lower-dimensional lattice polytopes use their affine dimension and the lattice induced in their affine span. Throughout the worked planar examples, the dimension is two.

The associated series is $\operatorname{Ehr}_P(z)=\sum_{t\ge0}L_P(t)z^t$. It has the form $h_P^{\ast}(z)/(1-z)^{d+1}$, which defines the lattice-counting numerator $h_P^{\ast}$. For $Q$, the series is $(1+3z)/(1-z)^3$. These definitions and the explicit formulas above supply the concluding investigation independently of Sections 36.1–36.10, which are optional extensions. The prerequisites on generating functions, posets, and geometric combinatorics explain the broader connections; external linear algebra and optimization background can deepen them.

36.1 Convex polytopes and face lattices

Optional extension; not required to complete the chapter foundation.

A nonempty proper face of a polytope $P$ is the set where some linear functional attains its maximum. Include the empty face and $P$ itself to form the face lattice, ordered by inclusion. Vertices are zero-dimensional faces, edges one-dimensional faces, and facets have dimension one below $P$. A face's rank is its dimension plus one, with the empty face assigned dimension $-1$ and rank zero.

The meet of two faces is their intersection. Their join is the smallest face containing both, obtained by intersecting all faces that contain their union. The union itself need not be a face. These operations make the face poset a lattice and connect geometric containment to the lattice-theory prerequisite.

Solved example. The triangle $Q$ has three vertices $v_0=(0,0),v_1=(2,0),v_2=(0,2)$ and three edges $e_{01},e_{02},e_{12}$. Including $\varnothing$ and $Q$, its face lattice has eight elements. The ranks have sizes $1,3,3,1$. Each vertex lies on exactly two edges; each edge contains exactly two vertices. For example, $e_{01}\wedge e_{02}=v_0$ and $v_1\vee v_2=e_{12}$. The join of all three vertices is $Q$.

Every subset of the three vertices determines a unique face, so this face lattice is the Boolean lattice on three elements. This is a simplex-specific fact. In a square, opposite vertices have the whole square as their join, since no edge contains both. Its face lattice has ten elements: one empty face, four vertices, four edges, and the whole polygon.

The combinatorial type records the face lattice, whereas a lattice realization also records integer coordinates. The unit triangle and $Q$ have isomorphic face lattices, but different areas and different lattice counts. Thus the face lattice alone cannot determine the Ehrhart polynomial.

Exercise. Determine the meet and join of the bottom and top edges of a square. Hint: they are disjoint but no proper face contains both. Solution: their meet is the empty face and their join is the whole square. This illustrates why a lattice join differs from set union.

36.2 Polyhedral cones and triangulations

Optional extension; not required to complete the chapter foundation.

A polyhedral cone generated by vectors $u_1,\ldots,u_r$ is $\{\sum_i\lambda_i u_i:\lambda_i\ge0\}$. It is pointed if it contains no nonzero line. A simplicial cone has linearly independent generators. For a full-dimensional simplicial integer cone, the absolute determinant of its generator matrix is its lattice index; index one means unimodular. Use primitive lattice ray generators, so scaling a generator does not artificially change the reported index.

For independent lattice generators, the half-open fundamental parallelepiped is $\Pi=\{\sum_i\theta_i u_i:0\le\theta_i\lt1\}$. Every lattice point of the cone is uniquely $p+\sum_i n_i u_i$ with $p\in\Pi\cap\mathbb Z^d$ and nonnegative integers $n_i$. Subtract the integer parts of the real generator coordinates to prove existence and uniqueness. Consequently its generating function is a finite numerator over geometric-series denominators.

A triangulation of a polytope is a collection of simplices covering it and meeting along common faces. Closed simplices overlap on those faces. Counting their points therefore requires inclusion–exclusion or a carefully chosen disjoint half-open decomposition. A geometric triangulation need not be unimodular, even when all its vertices are lattice points.

Exercise. Why is the triangle with vertices $(0,0),(2,0),(0,2)$ not unimodular? Hint: compute the determinant from one vertex. Solution: the edge vectors give determinant four, while a unimodular planar simplex has determinant magnitude one. Its Euclidean area is two and normalized area is four. Being a simplex does not make its lattice structure unimodular.

36.3 Lattice-point enumeration

Optional extension; not required to complete the chapter foundation.

For a finite lattice-point set, define its multivariate enumerator $G_P(X,Y)=\sum_{(a,b)\in P\cap\mathbb Z^2}X^aY^b$. At $X=Y=1$, this finite polynomial gives the number of points. For unbounded cones the analogous series is infinite; its rational expression requires a convergence region or a formal-series convention, and direct substitution at a pole is invalid.

Solved example and diagram. The dilation $2Q$ has vertices $(0,0),(4,0),(0,4)$. Its integer points satisfy $a,b\ge0$ and $a+b\le4$. There are fifteen points, of which twelve are boundary points and three are interior points. The diagram labels every point, distinguishes boundary from interior, and lists the five row lengths. The diagonal boundary contains five points, but its endpoints also belong to the horizontal and vertical boundaries; counting each side separately requires correcting these overlaps.

The enumerator can be written without expanding all fifteen terms:

$$ G_{2Q}(X,Y)=\sum_{b=0}^4Y^b\sum_{a=0}^{4-b}X^a. $$

This finite sum is valid at $X=1$. Replacing the inner sum by $(1-X^{5-b})/(1-X)$ gives a rational-looking expression with a removable singularity there; the finite sum explains why its limit is well defined. A removable singularity of the total expression is different from an uncancelled pole of an individual cone term.

For positive $t$, each edge of $tQ$ contains $2t+1$ lattice points. Subtract the three doubly counted vertices to get $B(t)=3(2t+1)-3=6t$ boundary points. The exact interior formula then gives $L_Q(t)-B(t)=2t^2-3t+1$. This checks reciprocity through a boundary calculation independent of the strict-inequality substitution.

Exercise. Enumerate the lattice points of $Q$ and state whether any lie in its interior. Hint: use rows with $b=0,1,2$. Solution: the rows are $(0,0),(1,0),(2,0)$; $(0,1),(1,1)$; and $(0,2)$. All six lie on at least one boundary edge, so the interior count is zero. The point $(1,1)$ lies on the diagonal and is not interior.

36.4 Ehrhart polynomials and quasipolynomials

Optional extension; not required to complete the chapter foundation.

Ehrhart's polynomial theorem applies to lattice polytopes. A quasipolynomial is a function $q(t)$ for which there are a positive period $s$ and polynomials $q_0,\ldots,q_{s-1}$ satisfying $q(t)=q_r(t)$ when $t\equiv r\pmod s$. A rational polytope has such a lattice-count function. If $sP$ has lattice vertices, a period divides $s$, though the minimal period can be smaller; the denominator need not be the minimal period.

Why does the lattice case become polynomial? Lift the vertices of a lattice simplex $S$ of dimension $r$ to $(v_i,1)$ in one higher dimension. Its cone's height-$t$ lattice points are exactly the points in $tS$. The lifted generators all have height one, and the parallelepiped decomposition gives

$$ \sum_{t\ge0}L_S(t)z^t=\frac{\sum_{j=0}^r b_jz^j}{(1-z)^{r+1}}, $$

where $b_j$ counts parallelepiped lattice points of height $j$. Heights lie between zero and $r+1$, excluding the latter. Taking coefficients expresses $L_S(t)$ as a combination of $\binom{t+r-j}{r}$, which are polynomials in $t$. For the small nonnegative arguments where a term has not yet appeared in the series, the binomial polynomial also vanishes. A lattice triangulation and inclusion–exclusion over common faces then prove polynomiality for the whole polytope. The leading terms add volumes of full-dimensional simplices; lower-dimensional intersections do not affect that coefficient.

This gives a proof mechanism for Ehrhart's theorem using lattice cones. A general triangulation-existence proof and the corresponding rational-height bookkeeping are omitted. In the rational case, denominator factors of the form $1-z^s$ produce residue-dependent coefficients instead of a single polynomial.

Solved example. For the rational interval $R=[0,1/2]$, the count is $L_R(t)=\lfloor t/2\rfloor+1$. Hence

$$ L_R(t)=\begin{cases}t/2+1,&t\equiv0\pmod2,\\ (t+1)/2,&t\equiv1\pmod2.\end{cases} $$

Its series is $(1+z)/(1-z^2)^2$, found by pairing the values at $t=2j$ and $t=2j+1$. The period-two dependence is real: the constant terms differ. By contrast, the lattice interval $[0,2]$ has the single polynomial $2t+1$.

Exercise. Give the quasipolynomial for $[0,1/3]$. Hint: separate the three possible residues. Solution: $L(t)=\lfloor t/3\rfloor+1$. On $t\equiv r\pmod3$, it equals $(t-r)/3+1$ for $r=0,1,2$. Its minimal period is three because these residue polynomials are different.

36.5 Ehrhart–Macdonald reciprocity

Optional extension; not required to complete the chapter foundation.

For a lattice polytope of affine dimension $d$, reciprocity is

$$ L_{P^{\circ}}(t)=(-1)^dL_P(-t),\qquad t\in\mathbb Z_{\gt0}, $$

where $P^{\circ}$ denotes relative interior. The right side evaluates the unique polynomial extension. For a rational polytope, the same identity holds with its quasipolynomial extension: evaluate at the residue class of the negative integer itself, rather than blindly using the positive argument's residue polynomial.

The intuition is that replacing closed facets by open facets reverses the boundary contributions. In one dimension, $[0,a]$ has $at+1$ lattice points and $(0,at)$ has $at-1$; indeed $-(a(-t)+1)=at-1$. In two dimensions the area term retains its sign, while the linear boundary term changes sign. For a lattice polygon, Pick's theorem yields $L_P(t)=\operatorname{area}(P)t^2+B(P)t/2+1$, and reciprocity changes the middle term to its negative.

Solved example. For $Q$, the closed count is $2t^2+3t+1$ and the interior count is $2t^2-3t+1$. For $t\ge2$, substitute $u=x-1,v=y-1$ in the strict inequalities to count $\binom{2t-1}{2}$ interior points. This expands to the same polynomial. At $t=1$, the strict feasible set is empty and the formula gives zero. Thus this example has a complete direct proof, without invoking the general theorem.

Proof sketch; omitted prerequisites. Simplicial-cone reciprocity compares open and closed fundamental parallelepipeds after inverting the generating variables. Triangulation then combines these identities, with face contributions canceling according to alternating dimension. The general valuation and cancellation argument is omitted; the explicit row counts prove every reciprocity claim made for $Q$.

For the rational interval $R=[0,1/2]$, the number of integers strictly between zero and $t/2$ is $\lceil t/2\rceil-1$. At $t=3$, its value is one. The odd-residue polynomial gives $L_R(-3)=(-3+1)/2=-1$, so $-L_R(-3)=1$, as required. Counting the reflected closed interval instead would give two, demonstrating why reflection is not polynomial reciprocity.

Exercise. Verify reciprocity for the unit cube in dimension three. Hint: closed and interior counts factor by coordinate. Solution: $L(t)=(t+1)^3$ and the interior count for positive $t$ is $(t-1)^3$. Since $(-1)^3L(-t)=-(-t+1)^3=(t-1)^3$, the sign is essential. At $t=1$ both the interior count and this expression are zero.

36.6 h-vectors and h*-polynomials

Optional extension; not required to complete the chapter foundation.

There are two different numerators. For the boundary complex of a simplicial $d$-polytope, let $f_{i-1}$ count faces with $i$ vertices and set $f_{-1}=1$ for the empty face. Define the combinatorial $h$-vector by

$$ \sum_{i=0}^d h_i z^i=\sum_{i=0}^d f_{i-1}z^i(1-z)^{d-i}. $$

This definition uses the simplicial boundary: applying it directly to a nonsimplicial boundary as though every face were a simplex would be incorrect. The $h$-vector repackages face numbers. For the triangle, $(f_{-1},f_0,f_1)=(1,3,3)$ gives $1+z+z^2$, hence $h=(1,1,1)$.

For a $d$-dimensional lattice polytope, define its Ehrhart numerator by

$$ \operatorname{Ehr}_P(z)=\frac{h_P^{\ast}(z)}{(1-z)^{d+1}},\qquad h_P^{\ast}(z)=\sum_{j=0}^d h_j^{\ast}z^j. $$

These coefficients are nonnegative integers, with $h_0^{\ast}=1$, $h_d^{\ast}=|P^{\circ}\cap\mathbb Z^d|$, and $\sum_jh_j^{\ast}=d!\operatorname{vol}(P)$ for a full-dimensional polytope. The latter is normalized volume, not ordinary volume. These are established Ehrhart facts; this section derives the example and the coefficient conversion rather than proving all general positivity results.

Extracting coefficients using $(1-z)^{-d-1}=\sum_{t\ge0}\binom{t+d}{d}z^t$ gives

$$ L_P(t)=\sum_{j=0}^d h_j^{\ast}\binom{t+d-j}{d}. $$

Solved example. For $Q$, $L(0)=1,L(1)=6,L(2)=15$. Multiply the series by $1-3z+3z^2-z^3$: the first coefficients are $1$, $6-3=3$, and $15-18+3=0$. Thus $h_Q^{\ast}(z)=1+3z$, or the padded vector $(1,3,0)$. The coefficient formula reads

$$ L_Q(t)=\binom{t+2}{2}+3\binom{t+1}{2}=2t^2+3t+1. $$

The coefficient sum four equals twice the area, and the last coefficient zero equals the number of interior points of $Q$. Meanwhile its boundary $h$-vector is $(1,1,1)$. A face-counting numerator and a lattice-counting numerator answer different questions.

Exercise. Compute both numerators for the unit square. Hint: its boundary has four vertices and four edges, while $L(t)=(t+1)^2$. Solution: its boundary is a simplicial one-dimensional complex, so the face formula gives $(1-z)^2+4z(1-z)+4z^2=1+2z+z^2$. Its Ehrhart numerator is $1+z$, because $L(t)=\binom{t+2}{2}+\binom{t+1}{2}$. Thus $h=(1,2,1)$ and $h^{\ast}=(1,1,0)$.

36.7 Brion's theorem

Optional extension; not required to complete the chapter foundation.

For a rational polytope $P$ and a vertex $v$, its tangent cone is $T_vP=v+\operatorname{cone}(P-v)$, extending all directions into $P$ indefinitely. Brion's theorem expresses the lattice enumerator of $P$ as the sum of the rational lattice enumerators of its vertex tangent cones:

$$ G_P(\mathbf X)=\sum_{v\text{ vertex of }P}G_{T_vP}(\mathbf X). $$

The identity lives in rational functions, not in a single common convergent expansion of all cone series. Oppositely directed cones may require incompatible series expansions. See the primary paper Brion, Points entiers dans les polyèdres convexes (1988).

Solved example. For the integer interval $[0,N]$, $N\ge1$, its two tangent cones have rational functions $1/(1-X)$ and $X^N/(1-X^{-1})$. Algebra gives

$$ \frac1{1-X}+\frac{X^N}{1-X^{-1}} =\frac{1-X^{N+1}}{1-X}=1+X+\cdots+X^N. $$

Their infinite tails cancel. Each term has a pole at $X=1$, but the sum has the finite value $N+1$. Evaluating each term at one before adding is invalid.

For the triangle $Q$, all three tangent cones have unimodular primitive directions. The explicit identity is

$$ G_Q(X,Y)=\frac1{(1-X)(1-Y)} +\frac{X^2}{(1-X^{-1})(1-X^{-1}Y)} +\frac{Y^2}{(1-Y^{-1})(1-XY^{-1})} =1+X+Y+X^2+XY+Y^2. $$

At $(2,0)$ the directions are $(-1,0),(-1,1)$; at $(0,2)$ they are $(0,-1),(1,-1)$. Each determinant has magnitude one. The vertex numerators encode the cone apices. Although $Q$ itself is not a unimodular simplex, its vertex cones are unimodular: these are different determinant tests.

Proof sketch; omitted prerequisites. A polyhedral indicator identity sums tangent cones along all faces with alternating signs. Under the lattice generating-function valuation, cones containing lines contribute zero in the rational-function framework, leaving the vertex terms. The valuation construction is omitted. The displayed interval identity and triangle identity can instead be verified directly by common-denominator algebra.

Exercise. Use the two tangent rays to enumerate $[2,5]\cap\mathbb Z$. Hint: shift the interval formula. Solution: $X^2/(1-X)+X^5/(1-X^{-1})=X^2+X^3+X^4+X^5$. The total at $X=1$ is four after cancellation.

36.8 Barvinok's algorithm

Optional extension; not required to complete the chapter foundation.

For each fixed dimension $d$, lattice points in a bounded rational polytope described by binary-encoded rational inequalities can be counted in time polynomial in the input bit length. This is the fixed-dimension counting theorem of Barvinok (1994). Dimension is a fixed parameter, not an input allowed to grow under the same polynomial bound. The algorithm returns a compressed description or count rather than necessarily listing every point.

The organizing steps are vertex-cone localization, decomposition into cones with manageable lattice index, short rational generating functions, and exact extraction of the finite total. Signed cone decompositions prevent the number of pieces from growing like the determinant. Merely splitting a cone into every unimodular piece can require a number of pieces proportional to a determinant that is exponentially large in its bit length; this would not prove the complexity theorem.

Solved small decomposition. Return to the index-two cone $C=\operatorname{cone}\{(1,0),(1,2)\}$. Insert the ray $w=(1,1)$. The two cones $C_1=\operatorname{cone}\{(1,0),w\}$ and $C_2=\operatorname{cone}\{w,(1,2)\}$ are unimodular, and their intersection is the ray generated by $w$. Exact inclusion–exclusion gives

$$ G_C=\frac1{(1-X)(1-XY)} +\frac1{(1-XY)(1-XY^2)}-\frac1{1-XY} =\frac{1+XY}{(1-X)(1-XY^2)}. $$

The negative ray term corrects the shared boundary. This is a complete small example of the cone-decomposition step; it is not a reconstruction of the full polynomial-time recursion. On setting $Y=1$, the expression becomes $(1+X)/(1-X)^2$, whose coefficient at $X^N$ is $2N+1$, matching direct slice enumeration. This specialization is valid as a formal height series since every abscissa slice is finite.

At the final counting step for a bounded polytope, one chooses a substitution avoiding identically zero cone denominators, expands terms as Laurent series near the identity, and takes the finite constant term after pole cancellation. For the interval $[0,2]$, set $X=e^s$:

$$ \frac1{1-e^s}=-\frac1s+\frac12+O(s),\qquad \frac{e^{2s}}{1-e^{-s}}=\frac1s+\frac52+O(s). $$

The poles cancel and the constants sum to three. This illustrates exact limit extraction; arbitrary floating-point evaluation near the poles can lose precision through cancellation.

Exercise. If the shared ray were not subtracted in the index-two example, how much would the coefficient at $X^N$ be overcounted after $Y=1$? Hint: the ray has one point at each nonnegative abscissa. Solution: the missing correction is $1/(1-X)$, so each coefficient is one too large, giving $2N+2$ instead of $2N+1$. Boundary bookkeeping is part of correctness.

36.9 Order, matching, and flow polytopes

Optional extension; not required to complete the chapter foundation.

Later Section 39.1 is recommended for the broader polyhedral-combinatorics treatment, not an entry requirement. The bridge here is that a combinatorial feasibility system can define a lattice polytope whose dilations count discrete assignments. For a full primary treatment of the order-polytope connection, see Stanley, Two poset polytopes (1986).

For a finite poset $\mathcal P$, choose the convention

$$ \mathcal O(\mathcal P)=\{x\in[0,1]^{\mathcal P}:x_p\le x_q\text{ whenever }p\le q\}. $$

Its lattice points at scale $t$ are weakly order-preserving maps to $\{0,\ldots,t\}$. For a chain $p\lt q$, they are pairs $0\le a\le b\le t$, numbering $\binom{t+2}{2}$. For an antichain of two elements, the constraints disappear and the count is $(t+1)^2$. The inequalities' orientation must remain consistent; reversing all coordinates yields another common convention.

A matching polytope is the convex hull of edge-incidence vectors of matchings in a graph. A useful contrast is the fractional system $x_e\ge0$ and $\sum_{e\ni v}x_e\le1$ at every vertex. For bipartite graphs this system is integral and describes the matching polytope. For general graphs it need not: on a triangle, setting all three edge variables to $1/2$ satisfies those inequalities but has total $3/2$, larger than any matching's size one. The valid odd-set inequality for that triangle is $\sum_e x_e\le1$. Integer vertices cannot be assumed from integer coefficients alone.

For a directed graph with incidence matrix $B$ and prescribed net inflow vector $b$, a flow polytope uses $Bx=b$, $x\ge0$, plus any stated capacity bounds. Boundedness must be checked: free directed cycles can create unbounded circulation directions.

Solved example. On edges $s\to u,u\to t,s\to t$, impose net outflow one at $s$ and net inflow one at $t$. Conservation gives $x_{su}=x_{ut}=a$ and $x_{st}=1-a$, with $0\le a\le1$. At scale $t$, write $x_{su}=x_{ut}=a$ and $x_{st}=t-a$, so there are $t+1$ nonnegative integer flows. The polytope is a lattice segment with endpoints $(0,0,1)$ and $(1,1,0)$, and Ehrhart polynomial $t+1$ in its induced one-dimensional lattice.

Exercise. For a two-edge path, write its matching polytope and count its dilated lattice points. Hint: the shared vertex supplies one inequality. Solution: $x_1,x_2\ge0$ and $x_1+x_2\le1$. At scale $t$, the count is $\binom{t+2}{2}$, since there are $t-x_1+1$ choices for $x_2$ at each $x_1=0,\ldots,t$. At scale one the three points represent the empty matching and the two singleton matchings.

36.10 Newton polytopes and toric geometry connections

Optional extension; not required to complete the chapter foundation.

For a nonzero Laurent polynomial $f=\sum_{a\in A}c_a x^a$ over $\mathbb C$, with every listed $c_a\ne0$, its support is $A\subseteq\mathbb Z^d$ and its Newton polytope is $\operatorname{conv}(A)$. Coefficient values affect roots, but the convex hull of exponent vectors already constrains possible behavior. For nonzero $f,g$, $\operatorname{Newt}(fg)=\operatorname{Newt}(f)+\operatorname{Newt}(g)$, where $+$ denotes Minkowski sum. Exposed-face terms in any chosen direction multiply to a nonzero polynomial, so their maximum weights add; this proves equality even though individual interior coefficients can cancel.

For $Q$, the polynomial $1+x^2+y^2$ has Newton polytope $Q$, despite using only three of its six lattice points. The lattice-point list describes all monomials permitted by $Q$, not the actual support of every polynomial with that Newton polytope.

Solved toric example. Homogenize with projective variables $U,V,W$. The six lattice points of $Q$ correspond to

$$ U^2,\ UV,\ UW,\ V^2,\ VW,\ W^2. $$

They define the quadratic Veronese map from the projective plane to projective five-space. Its graded coordinate algebra is the subalgebra of $\mathbb C[U,V,W]$ generated by these six quadratics, with each quadratic assigned degree one. At degree $t$, it contains every ordinary monomial of total degree $2t$: distribute its $2t$ variable factors into $t$ pairs. Distinct monomials are linearly independent, so the degree-$t$ dimension is

$$ \binom{2t+2}{2}=L_Q(t). $$

This explicitly proves the Hilbert-series/Ehrhart-series equality for this example. In general the algebra generated only by degree-one lattice monomials may omit points in $tP$ unless $P$ has the integer decomposition property: every lattice point of $tP$ must be a sum of $t$ lattice points of $P$. The full cone semigroup algebra, using all $(a,t)$ with $a\in tP\cap\mathbb Z^d$, has Ehrhart graded dimensions by construction. Conflating these two algebras would hide an important hypothesis. The normal-semigroup algebra background rests on the established theory of Hochster (1972); normality and Cohen–Macaulay theory are omitted prerequisites, not assumptions needed for the explicit monomial count.

A second established connection is Bernstein's root-count theorem. For generic Laurent polynomial coefficients with fixed finite supports in $d$ variables, the number of isolated solutions in $(\mathbb C\setminus\{0\})^d$, counted with multiplicity, equals the lattice-normalized mixed volume of the Newton polytopes. Generic means outside a proper algebraic exceptional set. Special coefficients can produce fewer isolated torus solutions or positive-dimensional solution sets. See the primary paper Bernshtein, The number of roots of a system of equations (1975). This is an established theorem; no conjectural root-count claim is used here.

In dimension two, use the convention that mixed volume is the coefficient of $\lambda\mu$ in $\operatorname{area}(\lambda P+\mu R)$. Two unit squares therefore have mixed volume two. For an exact example, take

$$ f=1+x+y+2xy,\qquad g=3+2x+4y+xy. $$

Both Newton polytopes are the unit square. Solving the first equation gives $y=-(1+x)/(1+2x)$; at $x=-1/2$ the first equation cannot hold. Substitution into the second gives $3x^2+3x-1=0$, with two distinct roots $(-3\pm\sqrt{21})/6$. Neither is zero, $-1$, or $-1/2$, so both yield nonzero valid ordinates and two torus solutions. This is a direct verification for particular coefficients, not an assertion of genericity based only on the supports.

Proof sketch; omitted prerequisites. Newton faces control what happens when solutions approach the toric boundary. Generic nondegeneracy prevents boundary contributions, and intersection theory computes the remaining count through mixed volume. Toric compactification and intersection multiplicities are omitted. The monomial-dimension and two-equation calculations above are complete elementary examples; the general theorem requires that deeper machinery.

Exercise. Compute the Newton polytope of $(1+x)(1+y)$ and compare it with those of the two factors. Hint: list the four exponent vectors. Solution: the product is $1+x+y+xy$, with Newton polytope the unit square. The factors have horizontal and vertical unit segments as Newton polytopes; their Minkowski sum is exactly that square.

Compute an Ehrhart polynomial and explain its reciprocity

The investigation returns to $Q$ and connects its face structure, lattice enumerator, and monomial interpretation. The introduction supplies the full counting and reciprocity foundation; the optional sections give additional routes and generalizations. Use exact integers and rationals for claims intended as proofs, and explain what finite experimental checks do and do not establish.

Worked solution: faces and finite enumeration. The eight faces are $\varnothing$; the three singleton vertices; the segments between each pair; and $Q$. At scale one the six points are $(0,0),(1,0),(2,0),(0,1),(1,1),(0,2)$. At scale two the rows have lengths $5,4,3,2,1$. The strict interior consists of $(1,1),(1,2),(2,1)$, and the other twelve points lie on $x=0$, $y=0$, or $x+y=4$.

Worked solution: polynomial and reciprocity. For each integer $x=0,\ldots,2t$, the ordinate can take $2t-x+1$ values, so

$$ L_Q(t)=\sum_{x=0}^{2t}(2t-x+1)=(2t+1)(t+1)=2t^2+3t+1. $$

The area is two, the boundary count at positive scale is $6t$, and $L_Q(0)=1$ because zero dilation is a single point. For $t\ge2$, interior points correspond to $u,v\ge0$ with $u+v\le2t-3$, giving

$$ L_{Q^{\circ}}(t)=\frac{(2t-2)(2t-1)}2=2t^2-3t+1. $$

At $t=1$ there are no solutions and the same formula is zero. Evaluating the closed polynomial at $-t$ gives exactly this expression, proving reciprocity. By contrast, reflection preserves the lattice and $|(-t)Q\cap\mathbb Z^2|=L_Q(t)$, which is generally larger. At $t=2$, the reflected closed count is fifteen, while polynomial evaluation at $-2$ is three.

Worked solution: generating functions. The binomial decomposition is $L_Q(t)=\binom{t+2}{2}+3\binom{t+1}{2}$. Summing gives

$$ \operatorname{Ehr}_Q(z)=\frac1{(1-z)^3}+\frac{3z}{(1-z)^3} =\frac{1+3z}{(1-z)^3}. $$

Thus the padded Ehrhart numerator vector is $(1,3,0)$. Its coefficient sum four is $2!\operatorname{area}(Q)$, and its final coefficient zero counts scale-one interior points. The simplicial boundary face formula gives $h=(1,1,1)$. Changing the triangle's edge lengths while retaining its face lattice can change the first numerator but leaves this boundary $h$-vector unchanged.

Worked solution: reproducible exploration. The expected independent counts are

The bijection sends $(x,y)\in tQ\cap\mathbb Z^2$ to $(2t-x-y,x,y)$, the exponents of $U^{2t-x-y}V^xW^y$. It is invertible by reading the last two exponents. Faces correspond to which nonnegativity constraint is an equality: the three boundary edges have at least one zero exponent, while interior lattice points give all three exponents positive. This makes the face-lattice/Ehrhart/Newton connection explicit in the example, without treating all toric geometry as a counting identity.

Application. A polynomial approximation model using three homogeneous variables of total degree $2t$ has exactly $L_Q(t)$ candidate monomials before imposing additional relations or sparsity restrictions. This count determines a feature-space dimension and helps estimate storage requirements. In sparse polynomial solving, Newton polytopes and mixed volumes give a different kind of information: generic complex torus root counts, not real-root counts or a guarantee for every coefficient choice. Both applications read discrete algebraic structure from exponent geometry.

Worked solution: optional extension. For $Q_m$, the same row sum gives

$$ L_{Q_m}(t)=\binom{mt+2}{2}=\frac{m^2}{2}t^2+\frac{3m}{2}t+1. $$

The interior count is $(mt-1)(mt-2)/2$ for positive $t$; when $mt=1$ or $2$ this is zero and agrees with the empty interior. The numerator is

$$ h_{Q_m}^{\ast}(z)=1+\frac{m^2+3m-4}{2}z+\frac{(m-1)(m-2)}2z^2. $$

For positive integer $m$ these coefficients are nonnegative integers. The sum is $m^2$, the normalized area; the last coefficient counts positive integer pairs with sum strictly below $m$. At $m=1$ the numerator is one, and at $m=2$ it is $1+3z$. The face lattice stays the same eight-element lattice throughout, while the Ehrhart numerator changes with the lattice realization.