An Invitation to Ehrhart Theory: Polyhedral Geometry and its Applications in Enumerative Combinatorics

Abstract

In this expository article we give an introduction to Ehrhart theory, i.e., the theory of integer points in polyhedra, and take a tour through its applications in enumerative combinatorics. Topics include geometric modeling in combinatorics, Ehrhart’s method for proving that a counting function is a polynomial, the connection between polyhedral cones, rational functions and quasisymmetric functions, methods for bounding coefficients, combinatorial reciprocity theorems, algorithms for counting integer points in polyhedra and computing rational function representations, as well as visualizations of the greatest common divisor and the Euclidean algorithm.

Felix Breuer was supported by Austrian Science Fund (FWF) special research group Algorithmic and Enumerative Combinatorics SFB F50-06.

1 Introduction

Polyhedral geometry is a powerful tool for making the structure underlying many combinatorial problems visible – often literally! In this expository article we give an introduction to Ehrhart theory and more generally the theory of integer points in polyhedra and take a tour through some of its many applications, especially in enumerative combinatorics.

In Sect. 2, we start with two classic examples of geometric modeling in combinatorics and then introduce Ehrhart’s method for showing that a counting function is a (quasi-)polynomial in Sect. 3. We present combinatorial reciprocity theorems as a first application in Sect. 4, before we talk about cones as the basic building block of Ehrhart theory in Sect. 5. The connection of cones to rational functions is the topic of Sect. 6, followed by methods for proving bounds on the coefficients of Ehrhart polynomials in Sect. 7. Section 8 discusses a surprising connection to quasisymmetric functions. Section 9 is about algorithms for counting integer points in polyhedra and computing rational function representations, in particular Barvinok’s theorem on short rational functions. Finally, Sect. 10 closes with a playful look at the connection between the Euclidean algorithm and the geometry of $\mathbb {Z}^2$.

2 Geometric Modeling in Combinatorics

Many objects in combinatorics can be conveniently modeled as integer vectors that satisfy a set of linear equations and inequalities. In applied mathematics, this paradigm has proven tremendously successful: the combinatorial optimization industry rests to a large part on mixed integer programming. However, also in pure mathematics this approach can help to prove theorems. We illustrate this approach of constructing geometric models of combinatorial objects and problems on two of the most classic counting functions in all of combinatorics: The chromatic polynomial of a graph and the restricted partition function.

Fig. 1.

(a) The graphic arrangement of the graph $G$. An edge between vertices $v_i$ and $v_j$ corresponds to a hyperplane $x_i=x_j$. (b) Points in the cube correspond to colorings. They can be visualized by drawing the graph $G$ in a coordinate system such that the height of a vertex $v_i$ is given by its color $x_i\in \{1,\ldots ,k\}$. This induces an orientation of the edges from the vertex with smaller to the vertex with the larger color. Moving from coloring $a$ through coloring $b$ to coloring $c$ we pass the hyperplane $x_2=x_3$ which is not part of the graphic arrangement; in $b$ vertices $v_2$ and $v_3$ are at the same height. Moving on through $d$ to $e$ we pass the hyperplane $x_1=x_2$ which is in the graphic arrangement; in $d$ two adjacent vertices are at the same height, so $d$ is not proper. Moving from $c$ to $e$ thus reverses the orientation of the edge between vertices $v_1$ and $v_2$ (Color figure online).

The chromatic polynomial $\chi _G(k)$ of a given graph $G$ counts the number of proper $k$-colorings of $G$. Let $V$ be the vertex set of $G$ and $\sim$ its adjacency relation. A $k$ -coloring is a vector $x\in [k]^V$ that assigns to each vertex $v\in V$ a color $x_v\in [k] := \{1,\ldots ,k\}$. Such a $k$-coloring $x$ is proper if for any two adjacent vertices $v\sim w$ the assigned colors are different, i.e., $x_v \not = x_w$. This way of describing a coloring as a vector rather than a function already suggests a geometric point of view (Fig. 1). Define the graphic arrangement of $G$ as the set of all hyperplanes $x_v = x_w$ for adjacent vertices $v \sim w$. Then the chromatic polynomial counts integer points $x\in \mathbb {Z}^V$ that are contained in the half-open cube $(0,k]^V$ but do not lie on any of the hyperplanes in the graphic arrangement of $G$, i.e.,

$$\begin{aligned} \chi _G(k) = \#\mathbb {Z}^V\cap \left\{ x\in \mathbb {R}^V \; \,|\,\; 0< x_v \le k \text { and } x_v \not = x_w \text { if } v\sim w \right\} . \end{aligned}$$

(1)

Fig. 2.

(a) The partition polytope is cut out from the standard simplex $\left\{ x \; \,|\,\; x_i\ge 0, \sum x_i = 1 \right\}$ by the braid arrangement of all hyperplanes $x_i=x_j$. (b) The integer points in the partition polytope for $k=18$ and $m=3$ correspond to the partitions of 18 in at most 3 parts.

The restricted partition function $p(k,m)$ counts the number of partitions of $k$ into at most $m$ parts.¹ This can be modeled simply by defining a partition of $k$ into at most $m$ parts as a non-negative vector $x\in \mathbb {Z}^m$ whose entries sum to $k$ and are weakly decreasing. For example, in the case $m=5$ and $k=14$ the partition $14=7+5+2$ would correspond to the vector $(7,5,2,0,0)$. In short,

$$\begin{aligned} p(k,m) = \#\mathbb {Z}^m\cap \{ x\in \mathbb {R}^m \; | \; x_1 \ge x_2 \ge \ldots \ge x_m \ge 0 \text { and } \sum _{i=1}^m x_i = k \}. \end{aligned}$$

(2)

Geometrically speaking, the restricted partition function thus counts integer points in an $(m-1)$-dimensional simplex in $m$-dimensional space. This is visualized in Fig. 2. Note that the constraints that all variables are non-negative and that their sum is equal to $k$ already defines an $(m-1)$-dimensional simplex, bounded by the coordinate hyperplanes. The braid arrangement, i.e., the set of all hyperplanes $x_i=x_j$, subdivides this simplex into $m!$ equivalent pieces; the definition of the restricted partition function then selects the one piece in which the coordinates are in weakly decreasing order.

It is interesting to observe that both constructions work with the braid arrangement. Indeed, there are a host of combinatorial models that fit into this setting. A great example are scheduling problems [21]: Given a number $k$ of time-slots, how many ways are there to schedule $d$ jobs such that they satisfy a boolean formula $\psi$ over the atomic expressions “job $i$ runs before job $j$”, i.e., $x_i < x_j$? E.g., if $\psi =(x_1< x_2)\rightarrow (x_3< x_2)$ then we would count all ways to place $3$ jobs in $k$ time-slots such that if job $1$ runs before job $2$, then job $3$ also has to run before $2$. We will return to scheduling problems in Sect. 8. However, the methods presented in this article are not restricted to this setup as we will see.

3 Ehrhart Theory

For any set $X\subset \mathbb {R}^d$ the Ehrhart function $\mathrm{ehr }_X(k)$ of $X$ counts the number of integer points in the $k$-th dilate of $X$ for each $1\le k\in \mathbb {Z}$, i.e.,

$$ \mathrm{ehr }_X(k) = \#\mathbb {Z}^d \cap (k\cdot X). $$

Both our constructions from the previous section are of this form, since (1) and (2) are, respectively, equivalent to

$$\begin{aligned} \chi _G(k)&= \#\mathbb {Z}^V\cap k\cdot \left\{ x\in \mathbb {R}^n \; \,|\,\; 0< x_v \le 1 \text { and } x_v \not = x_w \text { if } v\sim w \right\} , \\ p(k,m)&= \#\mathbb {Z}^m\cap k\cdot \{ x\in \mathbb {R}^m \; | \; x_1 \ge x_2 \ge \ldots \ge x_m \ge 0 \text { and } \sum _{i=1}^m x_i = 1 \}. \end{aligned}$$

We will call the set $X$ the geometric model of the counting function $\mathrm{ehr }_X$. The central theme of this exposition is that geometric properties of $X$ often translate into algebraic properties of $\mathrm{ehr }_X$. Ehrhart’s theorem is the prime example of this phenomenon. To set the stage, we introduce some terminology and refer to [46, 57] for concepts from polyhedral geometry not defined here.

A polyhedron is any set of the form $P=\left\{ x \in \mathbb {R}^d \; \,|\,\; Ax \ge b \right\}$ for a fixed matrix $A$ and vector $b$. All polyhedra in this article will be rational, i.e., we can assume that $A$ and $b$ have only integral entries. A polytope is a bounded polyhedron. Any dilate of a polytope contains only a finite number of integer points, whence the Ehrhart function of a polytope is well-defined. A polyhedron is half-open if some of its defining inequalities are strict. A partial polyhedral complex ² $X$ is any set that can be written as a disjoint union of half-open polytopes.

Our model of $p(k,m)$ is a polytope. Our model of $\chi _G(k)$ is not, though, as it is non-convex, disconnected and neither closed nor open. It is easily seen to be a partial polytopal complex, though, e.g., by rewriting $x_v \not = x_w$ to $(x_v < x_w) \vee (x_v > x_w)$ and bringing the resulting formula in disjunctive normal form. This makes partial polytopal complexes an extremely flexible modeling framework, as summarized in the following lemma.

Lemma 1

Let $\psi$ be any boolean formula over homogeneous linear equations and inequalities with rational coefficients in the variables $x_1,\ldots ,x_d,k$, such that for every $k$ the set of all $x$ such that $\psi (x)$ is bounded. Then there exists a partial polytopal complex $X$ such that for all $1 \le k\in \mathbb {Z}$,

$$ \#\left\{ x\in \mathbb {Z}^d \; \,|\,\; \psi (x,k) \right\} = \mathrm{ehr }_X(k). $$

The generality of Ehrhart functions of partial polytopal complexes underlines the strength of the following famous theorem by Eugène Ehrhart.

Theorem 1

(Ehrhart [31]). If $X$ is partial polytopal complex³, then $\mathrm{ehr }_X(k)$ is a quasipolynomial.

Quasipolynomials are an important class of counting functions which capture both polynomial growth and periodic behavior. A function $p(k)$ is a quasipolynomial if there exist polynomials $p_0(k),\ldots ,p_{\ell -1}(k)$ such that

$$ p(k) = \left\{ \begin{array}{ll} p_0(k) &{} \text {if } k \equiv 0 \mod \ell \\ p_1(k) &{} \text {if } k \equiv 1 \mod \ell \\ \vdots \\ p_{\ell -1}(k) &{} \text {if } k \equiv \ell -1 \mod \ell \end{array} \right. $$

for all $k\in \mathbb {Z}$. The polynomials $p_i$ are called the constituents of $p$ and their number is a period of $p$. The period is not uniquely determined, but of course the minimal period is; every period is a multiple of the minimal period. The degree of $p$ is the maximal degree of the $p_i$. If $d$ is the degree of $p$ and $\ell$ a period of $p$, then $p$ is uniquely determined by $\ell \cdot (d+1)$ values of $p$, or more precisely, by $d+1$ values $p(k'\cdot \ell + i)$ for each $i=0,\ldots ,\ell -1$. This is why it makes sense to say that $\mathrm{ehr }_X$ “is” a quasipolynomial, even though we have defined Ehrhart functions only at positive integers. As an example, the quasipolynomial given by the restricted partition function $p(k,2)$ is computed by interpolation in Fig. 3.

Fig. 3.

By counting the integer points in the dilates of $P$ and interpolating, we can compute the Ehrhart quasipolynomial of $P$. In this case $P$ is the restricted partition polytope for partitions into at most 2 parts.

Given this terminology, we can make our above statement of Ehrhart’s theorem more precise. Restricting our attention to polytopes $P$ for the moment, the following hold for $\mathrm{ehr }_P$. First, all constituents of $\mathrm{ehr }_P$ have the same degree. That degree is the dimension of $P$. Second, the leading coefficient of all constituents of $P$ in the monomial basis is the volume of $P$. Third, the least common multiple of the denominators of all vertices of $P$ is a period of $\mathrm{ehr }_P$. More precisely, if $v_1,\ldots ,v_N\in \mathbb {Q}^d$ are the vertices of $P$ and $v_{i,j}=\frac{a_{i,j}}{b_{i,j}}\in \mathbb {Q}$, then

$$ \ell =\mathrm{lcm }(\left\{ b_{i,j} \; \,|\,\; i=1,\ldots ,N, \; j=1,\ldots ,d \right\} ) $$

is a period of $\mathrm{ehr }_P$. In particular, if the vertices of $P$ are all integral the Ehrhart function is a polynomial.

Ehrhart’s theorem thus provides a very general method for proving that counting functions are (quasi-)polynomials. Simply by virtue of the geometric models from Sect. 2, we immediately obtain that the chromatic function is a polynomial because the vertices of our geometric model are integral. This proof of polynomiality is very different from the standard deletion-contraction method and generalizes to counting functions that do not satisfy such a recurrence, including all scheduling problems. Also we find that the restricted partition function into $m$ parts is a quasipolynomial with period $\mathrm{lcm }(1,2,\ldots ,m)$: The numbers $1,2,\ldots ,m$ appear in the denominators of the vertices, since we intersect the braid arrangement with the simplex $\left\{ x \; \,|\,\; x_i\ge 0,\sum x_i =1 \right\}$ instead of the cube. For more on the restricted partition function from an Ehrhart perspective, see [19].

Lemma 1 can be generalized even further, for example by allowing quantifiers via Presburger arithmetic [56] or by considering the multivariate case [55]. As a great introductory textbook on Ehrhart theory we recommend [10].

4 Combinatorial Reciprocity Theorems

Now that we know that the Ehrhart function $\mathrm{ehr }_P$ of a polytope $P$ is in fact a quasipolynomial we can evaluate it at negative integers. Even though the Ehrhart function itself is defined only at positive integers, it turns out that the values of $\mathrm{ehr }_P$ at negative integers have a very elegant geometric interpretation: $\mathrm{ehr }_P(-k)$ counts the number of integer points in the interior of $k\cdot P$.

Theorem 2

(Ehrhart-Macdonald Reciprocity [43]). If $P\subset \mathbb {R}^n$ is a polytope of dimension $d$ and $0<k \in \mathbb {Z}$ then

$$ \mathrm{ehr }_P(-k) = (-1)^d \cdot (\#\mathbb {Z}^n \cap k\cdot P^\circ ). $$

Here $P^\circ$ denotes the relative interior of $P$, which means the interior of $P$ taken with respect to the affine hull⁴ of $P$. If $P$ is given in terms of a system of linear equations and inequalities, the relative interior is often easy to determine. For example, if $P$ is defined by $Ax \ge b$ and $A'x = b'$, and $A'$ contains all equalities of the system⁵, then $P^\circ$ is given by $Ax > b$ and $A'x = b'$. In short, all we need to do is make weak inequalities strict.

Ehrhart-Macdonald reciprocity provides us with a powerful framework for finding combinatorial reciprocity theorems, i.e., combinatorial interpretations of the values of counting functions at negative integers. We start with a counting function $f$ defined in the language of combinatorics and translate this counting function into the language of geometry by constructing a linear model. In the world of geometry, we apply Ehrhart-Macdonald reciprocity to find a geometric interpretation of the values of $f$ at negative integers. Translating this geometric interpretation back into the language of combinatorics, a process which can be quite subtle, we then arrive at a combinatorial reciprocity theorem.

Let us start with the example of the restricted partition function $p(k,m)$. Applying Theorem 2 it follows that, up to sign, $p(-k,m)$ counts vectors $x$ such that $x_1 > x_2 > \ldots > x_m > 0$ and $\sum x_i = k$ for any positive integer $k$. Interpreting this geometric statement combinatorially, we find:

Theorem 3

Up to sign, $p(-k,m)$ counts partitions of $k$ into exactly $m$ distinct parts.

This result seems to be less well-known in partition theory than one would expect, even though it is an immediate consequence of Ehrhart-Macdonald reciprocity; see also [19]. A very similar geometric construction, however, is the basis of Stanley’s work on $P$-partitions and the order polynomial [49] which has many nice extensions, e.g., [39].

Next, we consider the chromatic polynomial $\chi _G(k)$. The model $X_G$ we use here is slightly different from (1) in that we work with the open cube ${(0,k+1)^V}$. This introduces a shift $\mathrm{ehr }_{X_G}(k) = \chi _G(k-1)$. The advantage is that $X_G$ is now a disjoint union of open polytopes $P_1,\ldots ,P_N$. As already motivated by Fig. 1, it turns out that the $P_i$ are in one-to-one correspondence with the acyclic orientations⁶ of the graph $G$ [35]. Applying Theorem 2 to each component individually, we find that $\chi _G(-k)$ counts all integer vectors $x$ in the closed cube such that points on the hyperplanes $x_v=x_w$ have a multiplicity equal to the number of closed components $\bar{P}_i$ they are contained in. To interpret this combinatorially, we define an orientation $o$ and a coloring $x$ of $G$ to be compatible if, when moving along directed edges, the colors of the vertices always increase or stay the same. Putting everything together and taking the shift into account we obtain Stanley’s reciprocity theorem for the chromatic polynomial below. The geometric proof we described is due to Beck and Zaslavsky [12] and can be generalized to cell-complexes [7].

Theorem 4

(Stanley [47]). Up to sign, $\chi _G(-k)$ counts pairs $(x,o)$ of (not necessarily proper) $k$-colorings $x$ and compatible acyclic orientations $o$ of $G$.

Next, the modular flow polynomial of a graph provides us with an example of a combinatorial reciprocity theorem that was first discovered via the geometric approach and that makes use of a different construction, unrelated to the braid arrangement. This example is illustrated in Fig. 4. A $\mathbb {Z}_k$-flow on a directed graph $G$ with edge set $E$ is a vector $y\in \mathbb {Z}_k^E$ that assigns to each edge of $G$ a number such that at each vertex $v$ of $G$ the sum of all flows into $v$ equals the sum of all flows out of $v$, modulo $k$. The modular flow polynomial $\varphi _G(k)$ of $G$ counts $\mathbb {Z}_k$-flows on $G$ that are nowhere zero. To model this in Euclidean space, we identify the elements of $\mathbb {Z}_k$ with the integers $0,\ldots ,k-1$. Nowhere zero vectors $y\in \mathbb {Z}_k^E$ thus correspond to integer points $y\in (0,k)^k$ in the $k$-th dilate of the open unit cube. If $A\in \mathbb {Z}^{V\times E}$ is the incidence matrix of $G$, the constraint that flow has to be conserved at each vertex can be expressed simply by requiring $Ay\equiv 0 \mod k$, or, equivalently, by $\exists b\in \mathbb {Z}^V: Ay = kb$. Note that for only finitely many $b\in \mathbb {Z}^V$ the hyperplane $Ay=b$ intersects the unit cube $(0,1)^E$. Let $P_1,\ldots ,P_N$ denote these sections and let $X$ be their union. Then $\varphi _G(k) = \mathrm{ehr }_X(k)$.

Fig. 4.

(a) A directed graph $G$ and the flow problem $G$ defines. (b) The corresponding partial polyhedral complex $X$. (c) The labelings of $G$ given by the points $v,w$ along with the different totally cyclic orientations of $G/\mathrm{supp }(v) = G/\mathrm{supp }(w)$.

Applying Ehrhart-Macdonald reciprocity, we obtain that, up to sign, $\varphi _G(-k)$ counts integer points in the $k$-th dilate of the union of the closures $\bar{P}_i$. In particular, we now count vectors that may have both entries $0$ and $k$, which are both congruent zero mod $k$, but which we have to count as different as Fig. 4 shows. This observation suggests that to find a combinatorial interpretation, we may want to consider assigning two different kinds of labels to the edges with zero flow. Pursuing this line of thought eventually leads to the following combinatorial reciprocity theorem, which again can be generalized to cell complexes [7], see also [13, 15].

Theorem 5

(Breuer-Sanyal [22]). Up to sign, $\varphi _G(-k)$ counts pairs $(y,o)$ of a $\mathbb {Z}_k$-flow $y$ on $G$ and a totally cyclic reorientation of $G/\mathrm{supp }(y)$.

Here a reorientation is a labeling of the edges of a directed graph with $+$ or $-$, indicating whether the direction of the edge should be reversed or not. Such a reorientation is totally cyclic, if every edge of the resulting directed graph lies on a directed cycle. $\mathrm{supp }(y)$ denotes the set of edges where $y$ is non-zero and $G/\mathrm{supp }(y)$ denotes the graph where $\mathrm{supp }(y)$ has been contracted.

For more on combinatorial reciprocity theorems we recommend the forthcoming book [11].

5 Cones and Fundamental Parallelepipeds

A polyhedral cone or cone, for short, is the set of all linear combinations with non-negative real coefficients of a finite set of generators $v_1,\ldots ,v_d\in \mathbb {Q}^n$. If the generators are linearly independent, the cone is simplicial. The cone is pointed or line-free if it does not contain a line $\{u+\lambda v\;|\; \lambda \in \mathbb {R}\}$.

Cones are the basic building blocks of Ehrhart theory, because the sets of integer points in simplicial cones have a very elegant description, which is illustrated in Fig. 5. Let $v_1,\ldots ,v_d\in \mathbb {Z}^n$ be linearly independent, and consider the simplicial cone $\mathrm{cone }_\mathbb {R}(v_1,\ldots ,v_d)$ generated by them. The discrete cone or semigroup $\mathrm{cone }_\mathbb {Z}(v_1,\ldots ,v_d)$ of all non-negative integral combinations of the $v_i$ reaches only those integer points in $\mathrm{cone }_\mathbb {R}$ that lie on the lattice $\mathbb {Z}v_1+\ldots + \mathbb {Z}v_d$ generated by the $v_i$. However, by shifting the discrete cone to all integer points in the fundamental parallelepiped $\varPi (v_1,\ldots ,v_d)$ we can not only capture all integer points in $C$, but we moreover partition them into $\#\mathbb {Z}^{n+1}\cap \varPi (v_1,\ldots ,v_d) = |\det (v_1,\ldots ,v_d)|$ disjoint classes. This number of integer points in the fundamental parallelepiped is called the index of $C$. Define

$$\begin{aligned} \mathrm{cone }_\mathbb {R}(v_1,\ldots ,v_d)&= \left\{ \sum _{i=1}^d \lambda _i v_i\, {\Bigg |}\, 0\le \lambda _i \in \mathbb {R}\right\} , \\ \mathrm{cone }_\mathbb {Z}(v_1,\ldots ,v_d)&= \left\{ \sum _{i=1}^d \lambda _i v_i\, {\Bigg |}\, 0\le \lambda _i \in \mathbb {Z}\right\} , \\ \varPi (v_1,\ldots ,v_d)&= \left\{ \sum _{i=1}^d \lambda _i v_i\, {\Bigg |}\, 0\le \lambda _i < 1\right\} . \end{aligned}$$

Fig. 5.

(a) The discrete cone $\mathrm{cone }_\mathbb {Z}(v_1,v_2)$ generated by $v_1$ and $v_2$. Its fundamental parallelepiped is shaded. (b) To generate all points in $\mathbb {Z}^2\cap \mathrm{cone }_\mathbb {R}(v_1,v_2)$ the discrete cone has to be translated by every integer point in the fundamental parallelepiped (shown as diamonds).

Lemma 2

Let $v_1,\ldots ,v_d\in \mathbb {Z}^n$ be linearly independent. Then

$$ \mathbb {Z}^n\cap \mathrm{cone }_\mathbb {R}(v_1,\ldots ,v_d) = (\mathbb {Z}^n\cap \varPi (v_1,\ldots ,v_d)) + \mathrm{cone }_\mathbb {Z}(v_1,\ldots ,v_d). $$

The main benefit of this decomposition is that it splits the problem of describing the integer points in a cone to into two parts: The finite problem of enumerating the integer points in the fundamental parallelepiped, and the problem of describing the discrete cone, which is easy as we shall see below. As an application of this result, we will now prove Ehrhart’s theorem for polytopes.

Suppose we want to compute the Ehrhart function of a polytope $P'\subset \mathbb {R}^n$. We embed $P'$ at height $1$ in $\mathbb {R}^{n+1}$, i.e., we pass to $P = P'\times \{1\}\subset \mathbb {R}^{n+1}$. Then, we consider the set $\mathrm{cone }(P)$ of all finite linear combinations of elements in $P$ with non-negative real coefficients as shown in Fig. 6. The intersections of $\mathrm{cone }(P)$ with the hyperplanes $H_k:=\left\{ x \; \,|\,\; x_{n+1} = k \right\}$ are lattice equivalent⁷ to the dilates $k\cdot P$ we are interested in. If we can describe the number of integer points in such sections of polyhedral cones, we will have a handle on computing Ehrhart functions.

Fig. 6.

(a) The three first dilates of a polytope $P'$ in the plane. (b) The polytope $P=P'\times \{1\}$ embedded in 3-space and the cone $C=\mathrm{cone }(P)$ over $P$. Sections $H_k\cap C$ are lattice equivalent to the dilates of $P'$.

Before we continue, we observe that we can make two more simplifications. First, we can restrict our attention to simplicial cones. While in general $\mathrm{cone }(P)$ will of course not be simplicial, we can always reduce the problem to simplicial cones by triangulating $P$. Second, we note that while $\mathrm{cone }(P)$ is indeed finitely generated by the vertices $w_1,\ldots ,w_N$ of $P$, these $w_i$ may be rational vectors. Instead, we would like to work with generators $v_i$ that are all integer and all at the same height wrt. the last coordinate. This can be achieved by letting $\ell$ denote the smallest integer such that $\ell \cdot w_i\in \mathbb {Z}^{n+1}$ for all $i$ and setting $v_i := \ell \cdot w_i$.

We have thus reduced the problem of computing the Ehrhart function of $P'$ to computing $\mathbb {Z}^{n+1}\cap H_k\cap C_\mathbb {R}$, the number of integer points at height $k$ in a simplicial cone $C_\mathbb {R}:=\mathrm{cone }_\mathbb {R}(v_1,\ldots ,v_d)$ given by integral generators with last coordinate equal to a constant $\ell$. Following Lemma 2 we concentrate on $C_\mathbb {Z}:=\mathrm{cone }_\mathbb {Z}(v_1,\ldots ,v_d)$ first. Since the last coordinate of all $v_i$ is $\ell$, $C_\mathbb {Z}\cap H_k$ is empty if $k \not \equiv 0 \mod \ell$. On the other hand, if $k \equiv 0 \mod \ell$ and $k>0$, then

$$ H_{k} \cap \mathrm{cone }_\mathbb {Z}(v_1,\ldots ,v_d) = v_d + (H_{k-\ell } \cap \mathrm{cone }_\mathbb {Z}(v_1,\ldots ,v_d)) \cup (H_{k} \cap \mathrm{cone }_\mathbb {Z}(v_1,\ldots ,v_{d-1})). $$

This is an instance of Pascal’s recurrence for the binomial coefficients, illustrated in Fig. 7, which yields for all integers $k\ge 0$,

$$ \#H_{\ell \cdot k} \cap \mathrm{cone }_\mathbb {Z}(v_1,\ldots ,v_d) = \left( {\begin{array}{c}k+d-1\\ d-1\end{array}}\right) $$

and $\#H_{k} \cap \mathrm{cone }_\mathbb {Z}(v_1,\ldots ,v_d) = 0$ if $k \not \equiv 0 \; \mathrm{mod } \;\ell$.

Fig. 7.

The $4\ell$-th level of $C=\mathrm{cone }_\mathbb {Z}(v_1,v_2,v_3)$ decomposes naturally into the $4\ell$-th level of $\mathrm{cone }_\mathbb {Z}(v_1,v_2)$ and a shift of the $3\ell$-th level of $C$.

Applying Lemma 2 we see that to get the counting function for $C_\mathbb {R}$, we need to shift the discrete cone $C_\mathbb {Z}$ by all the integer points in the fundamental parallelepiped, which allows us to reach lattice points at heights $k$ which are not a multiple of $\ell$. Organizing these shifts according to the last coordinate, we obtain for any $k\ge 0$ and $0\le r < \ell$

$$\begin{aligned}&\#\left( \mathbb {Z}^{n+1}\cap H_{\ell \cdot k+r} \cap C_\mathbb {R}\right) \nonumber \\&= h^*_r \left( {\begin{array}{c}k+d-1\\ d-1\end{array}}\right) + h^*_{\ell +r} \left( {\begin{array}{c}k+d-2\\ d-1\end{array}}\right) + \ldots + h^*_{(d-1)\cdot \ell +r} \left( {\begin{array}{c}k\\ d-1\end{array}}\right) \end{aligned}$$

(3)

where $h^*_i$ denotes the number of integer points at height $i$ in $\varPi (v_1,\ldots ,v_d)$.

Note that if we are interested in $\#\left( \mathbb {Z}^{n+1}\cap H_{m} \cap C_\mathbb {R}\right)$ for an arbitrary non-negative $m$ then we can always write $m = \ell k + r$ such that $k\ge 0$ and $0\le r < \ell$ simply by doing division with remainder. Also note that (3) is a polynomial of degree $d-1$ in $k$ for each fixed $r$. Since $r$ changes periodically with $m$, the counting function $m \mapsto \#\left( \mathbb {Z}^{n+1}\cap H_{m} \cap C_\mathbb {R}\right)$ is a quasipolynomial of period $\ell$. By construction, $\mathrm{ehr }_P(k)$ is a sum of such expressions and therefore itself a quasipolynomial, which completes the proof of Theorem 1.

6 Connection to Rational Functions

The results and constructions of the previous section translate immediately into the language of generating functions, formal power series and rational functions. When we represent an integer point $v\in \mathbb {Z}^n$ by a multivariate monomial $z^v:=z_1^{v_1}\cdot \ldots \cdot z_n^{v_n}$, the set of integer vectors in any given set $S\subset \mathbb {Z}^n$ can be written as a multivariate generating function

$$ \phi _S(z) = \sum _{v\in \mathbb {Z}^n \cap S} z^v. $$

Using the familiar geometric series expansion $\frac{1}{1-z^v} = \sum _{i=0}^\infty z^{iv}$ we see that generating functions of “discrete rays” of integer vectors can be represented as rational functions. Indeed, both discrete cones and Lemma 2 can be expressed succinctly in terms of rational functions.

$$\begin{aligned} \phi _{\mathrm{cone }_\mathbb {Z}(v_1,\ldots ,v_d)}(z)&= \frac{1}{(1-z^{v_1})\cdot \ldots \cdot (1-z^{v_d})}.\end{aligned}$$

(4)

$$\begin{aligned} \phi _{\mathrm{cone }_\mathbb {R}(v_1,\ldots ,v_d)}(z)&= \frac{\sum _{v\in \mathbb {Z}^n\cap \varPi (v_1,\ldots ,v_d)} z^v}{(1-z^{v_1})\cdot \ldots \cdot (1-z^{v_d})}. \end{aligned}$$

(5)

If we specialize by substituting $z_i=q$ for each $i$, then we obtain $(1-q^\ell )^d$ in the denominator, since, by construction, all generators $v_i$ have coordinate sum $\ell$. This explains the appearance of binomial coefficients, since

$$ \frac{1}{(1-q^\ell )^d} = \sum _{k=0}^\infty \left( {\begin{array}{c}k+d-1\\ d-1\end{array}}\right) q^{\ell \cdot k} $$

which turns (3) into

$$\begin{aligned} \sum _{k=0}^\infty \mathrm{ehr }_P(k)q^k = \frac{h^*_0 q^0 + \ldots + h^*_{d\cdot \ell -1}q^{d\cdot \ell -1}}{(1-q^\ell )^d}. \end{aligned}$$

(6)

In this way, many arithmetic calculations on the level $q$-series can be viewed as the projection of a geometric construction, via multivariate generating functions. The richer multivariate picture can be of use, for example, when converting arithmetic proofs into a bijective proofs, see [19].

Intuitively, we can think of the generating functions $\phi _S$ as weighted indicator functions of sets of integer vectors. Starting with generating functions $\phi _P$ for polyhedra $P$ and taking linear combinations of these, we obtain an algebra $\mathcal {P}$ of polyhedral sets. However, working with rational function representations introduces an equivalence relation on this algebra. For example, we can expand $\frac{1}{1-z}$ either as $\sum _{i=0}^\infty z^i$, the indicator function of all non-negative integers, or as $-\sum _{i=1}^\infty z^{-i}$, minus the indicator function of all negative integers. This phenomenon generalizes to multivariate generating functions: To determine the formal expansion of a rational function uniquely, we have to fix a “direction of expansion” which can be given for example in terms of a suitable pointed cone. For details we refer the reader to, e.g., [2, 6, 9, 10]. Important for our purposes is that to each rational function there corresponds an equivalence class of indicator functions and the simple example of the geometric series tells us what the equivalence relation is: Two elements in the algebra of polyhedral sets are equivalent if they are equal modulo lines, i.e., modulo sets of the form $\left\{ u+\lambda v \; \,|\,\; \lambda \in \mathbb {Z} \right\}$ for some $u,v\in \mathbb {Z}^n$. We say that a generating function $\phi$ is represented by some rational function expression $\rho$ if there exists a pointed cone $C$ such that the expansion of $\rho$ in the direction $C$ gives $\phi$; for this to be feasible we assume that the support of $\phi$ does not contain a line. Choosing a different direction $C'$ for the expansion of $\rho$ produces a generating function $\phi '$ that is equal to $\phi$ modulo lines.

Working with indicator functions of cones modulo lines does have its advantages. Most importantly, this allows us to “flip” cones by reversing the direction of some (or all) of their generators and opening some of their faces accordingly, as shown in Fig. 8.

Fig. 8.

Let $v_1 =(-2,1)$ and $v_2 =(0,1)$. Modulo lines, the closed cone $C_1$ generated by $v_1$ and $v_2$ is equal to the negative of the half-open cone $C_2$ generated by $-v_1$ and $v_2$. Integer points in corresponding fundamental parallelepipeds are shown as diamonds.

One beautiful application of this phenomenon is Brion’s theorem, which allows us to represent $\phi _P$ for any line-free polyhedron $P$ in terms of rational function representations of cones, i.e., as a linear combination of expressions of the form (5). Brion’s theorem is motivated in Fig. 9.

Fig. 9.

Modulo lines, a polytope is equal to the sum of its vertex cones. In 2 dimensions, this is easy to see by iteratively flipping cones.

For a polyhedron $P$ we define the vertex cone $\mathrm{vcone }(v,P)$ at a vertex $v$ of $P$ as the set

$$ \mathrm{vcone }(v,P) = v + \mathrm{cone }_\mathbb {R}(v_1,\ldots ,v_N), $$

where the $v_i$ are the directions of the edges incident to $v$, oriented away from $v$. We can easily represent each vertex cone by a rational function: For a simplicial cone $C$ we define $\rho _C$ as the rational function expression given in (5).⁸ For a non-simplicial cone $C$ we define $\rho _C$ as a linear combination of such expressions, given via a triangulation of $C$. Then, the generating function of the set of integer points in $P$ is the sum of the rational function representations of the vertex cones.

Theorem 6

(Brion [24]). Let $P$ be a polyhedron that does not contain any affine line. Then

$$ \phi _P = \sum _{\text {v vertex of P}} \rho _{\mathrm{vcone }(v,P)}(z). $$

The theorem of Lawrence-Varchenko [41, 53] is the corresponding analogue for cases in which it is necessary to work with indicator functions directly, not with equivalence classes modulo lines. It expresses $\phi _P$ as an inclusion-exclusion of vertex cones which have been “flipped forward” so that their generators all point consistently in one direction of expansion as shown in Fig. 10.

Fig. 10.

The Lawrence-Varchenko decomposition of a pentagon. The sign next to the apex of each vertex cone $C$ specifies whether $C$ is to be added or subtracted. The number in each region is the net balance of how often points in the region are counted when the signed vertex cones are summed. All generators point of all vertex cones point to the right, which means all vertex cones are forward.

7 Coefficients of (Quasi-)Polynomials

The geometric perspective provides a wide range of methods for establishing bounds on the coefficients of counting (quasi-)polynomials. In this section we will focus on polynomials for simplicity, but the results generalize to quasipolynomials.

The monomial basis is of course the classic choice for computing coefficients of polynomials. Geometrically, the elements of the monomial basis of the space of polynomials are the Ehrhart functions $\mathrm{ehr }_{[0,1)^i}(k)=k^i$ of half-open cubes $[0,1)^i$ of varying dimension. For us, it will be expedient to work with two different binomial bases instead, whose elements are the Ehrhart functions ${\mathrm{ehr }_{\varDelta ^d_i}(k) = \left( {\begin{array}{c}k+d-i\\ d\end{array}}\right) }$ of unimodular⁹ $d$-dimensional half-open simplices $\varDelta ^d_i$ with $i$ open facets. Up to lattice equivalence, such a $\varDelta ^d_i$ has the form

$$ \varDelta ^d_i = \left\{ x\in \mathbb {R}^{d+1}\, \Bigg | \, x_1 > 0,\ldots ,x_i > 0, x_{i+1} \ge 0, \ldots , x_{d+1} \ge 0, \sum _j x_j = 1\right\} . $$

These unimodular half-open simplices $\varDelta ^d_i$ form the basic building block of Ehrhart theory. They offer two different ways in which we can use them to construct a basis of the space of polynomials. The first basis, which defines the $h^*$-coefficients, fixes the dimension $d$ of the simplices and varies the number $i$ of open facets. In contrast, the second basis, which defines the $f^*$-coefficients, uses only open simplices with $i=d+1$, but varies their dimension $d$.

Formally, the $h^*$-vector $(h^*_0,\ldots ,h^*_d)$ and the $f^*$-vector $(f^*_0,\ldots ,f^*_d)$ of a polynomial $p(k)$ of degree at most $d$ are defined by

$$\begin{aligned} p(k)&= h^*_0 \left( {\begin{array}{c}k+d\\ d\end{array}}\right) + h^*_1 \left( {\begin{array}{c}k+d-1\\ d\end{array}}\right) + \ldots + h^*_d \left( {\begin{array}{c}k\\ d\end{array}}\right) \\&= f^*_0 \left( {\begin{array}{c}k-1\\ 0\end{array}}\right) + f^*_1 \left( {\begin{array}{c}k-1\\ 1\end{array}}\right) + \ldots + f^*_d \left( {\begin{array}{c}k-1\\ d\end{array}}\right) . \end{aligned}$$

Let us begin by taking a closer look at the $h^*$-coefficients. As we have seen in (3) and (6), the $h^*$-vector of the Ehrhart quasipolynomial of a simplex $\varDelta$ counts lattice points at different heights in the fundamental parallelepiped of $\mathrm{cone }(\varDelta \times \{1\})$, which immediately implies $h^*_i\ge 0$. This observation extends to half-open simplices where some facets have been removed. It follows that if a geometric model $X$ can be partitioned into half-open simplices that are all of full dimension, as shown in Fig. 11(a), it follows that $\mathrm{ehr }_X$ has non-negative $h^*$-vector as well. As it turns out, all (closed convex) polytopes have such a partitionable triangulation, which proves non-negativity of the $h^*$-vector for all polytopes.

Fig. 11.

(a) A half-open 2-dimensional partial polytopal complex and a partition into half-open 2-dimensional simplices. (b) A half-open partial polytopal complex $X$ that is not partitionable. A partition of this complex with half-open 2-dimensional simplices would have to contain a 2-dimensional simplex with at least two edges and, consequently, at least one vertex. However, $X$ does not contain any of its vertices. (c) A decomposition of $X$ into open simplices of various dimension.

Theorem 7

(Stanley [48]). If $P$ is an integral polytope, then $\mathrm{ehr }_P$ has a non-negative $h^*$-vector.

However, as the examples of the chromatic polynomial and the flow polynomial from Sects. 2 and 4 show, the geometric models $X$ that appear in combinatorial applications of Ehrhart theory are not simply polytopes: Often they are non-convex, disconnected, half-open or have non-trivial topology. This can lead to geometric models $X$ that are not partitionable and, consequently, to counting polynomials with negative $h^*$-coefficients.

Figure 11(b) gives an example of a half-open partial polytopal complex that is not partitionable: A partition of the complex in Fig. 11(b), for example, would require 4 half-open simplices of dimension 2 that have, in total, 6 closed edges but contain none of the vertices of the complex, which is impossible. Here it is important to recall that, because we are working with the $h^*$ basis, all half-open simplices participating in a partition are required to have the same dimension (in this example, dimension 2).

Such phenomena appear in practice. One prominent example of natural counting polynomials with negative entries in their $h^*$-vector are chromatic polynomials of hypergraphs. In this case, it is the non-trivial topology of the geometric models that gives rise to non-partitionability: It is easy to construct hypergraphs whose coloring complexes consists of, say, 2-dimensional spheres that intersect in 0-dimensional subspheres; such complexes are not partitionable and can produce negative $h^*$-coefficients [18].

As we have seen in Sect. 3, partial polytopal complexes are the right notion to describe combinatorial models in Ehrhart theory. While partial polytopal complexes are not always partitionable, they can always be written as a disjoint union of relatively open simplices of various dimension. The partial polytopal complex in Fig. 11(b) can, for example, be written as a disjoin union of open simplices of dimension 1 and 2 as shown in Fig. 11(c). This motivates the use of the $f^*$-basis. As it turns out, the $f^*$-vector of an open simplex $\varDelta$ has a counting interpretation similar to (3), even though its construction is more subtle [16]. It follows that all partial polytopal complexes with integer vertices have a non-negative $f^*$-vector. Moreover, this property characterizes Ehrhart polynomials of partial polytopal complexes.

Theorem 8

(Breuer [16]). If $X$ is an integral partial polytopal complex, then $\mathrm{ehr }_X$ has a non-negative $f^*$-vector.

Conversely, if $p(k)$ is a polynomial with non-negative $f^*$-vector, then there exists an integral partial polytopal complex $X$ such that $\mathrm{ehr }_X(k)=p(k)$.

While Theorem 8 characterizes Ehrhart polynomials of the kind of geometric objects that appear in many combinatorial applications, the question remains how to characterize Ehrhart polynomials of convex polytopes. This challenge is vastly more difficult, and, even though many constraints on the $h^*$-vectors of convex polytopes have been proven, is still wide-open even in dimension 3. At least in dimension 2, a complete characterization of the coefficients of Ehrhart polytopes is available. See [8, 36, 37, 51] for more information.

Still, there are a wealth of tools available for proving sharper bounds on the coefficients of counting polynomials $\mathrm{ehr }_X$, by exploiting the particular geometric structure of the partial polytopal complex $X$, even if $X$ is not convex. One of the most powerful techniques available is the use of convex ear decompositions. A convex ear decomposition is a decomposition of a simplicial complex $X$ into “ears” $E_0,\ldots ,E_N$ such that $E_0$ is the boundary complex of a simplicial polytope, the remaining $E_i$ are balls that are subcomplexes of the boundary complex of some simplicial polytope, and $E_i$ is attached to $\bigcup _{j<i}E_j$ along its entire boundary (and not just along some facets), i.e., $E_i \cap \bigcup _{j<i}E_j = \partial E_i$. For example, the complex in Fig. 1, consisting of the boundary of the cube and the two hyperplanes, has a convex ear decomposition: Start with the boundary of the cube as triangulated by the braid arrangement, glue in the triangulated square lying on one of the hyperplanes and then glue in the two triangles on the second hyperplane one after the other. If all simplices in this complex are unimodular (as in many combinatorial applications), this leads to the following bounds, which have been successfully applied to the chromatic polynomial by Hersh and Swartz [38] and to the integral and modular flow and tension polynomials by Breuer and Dall [17].

Theorem 9

(Chari [27], Swartz [52]). If $X$ is a simplicial complex in which all simplices are unimodular and $X$ has a convex ear decomposition then the $h^*$-vector of $\mathrm{ehr }_X(k)$ satisfies

• (a) $h^*_0 \le h^*_1 \le \cdots \le h^*_{\left\lfloor d/2 \right\rfloor }$,

• (b) $h^*_i \le h^*_{d-i}$ for $i\le d/2$, and

• (c) $(h^*_0,h^*_1-h^*_0,\ldots ,h^*_{\left\lceil d/2 \right\rceil } - h^*_{\left\lceil d/2 \right\rceil -1})$ is an $M$-vector¹⁰.

8 Quasisymmetric Functions

Polyhedral models are useful for the study of combinatorial objects beyond counting polynomials as well. For example, the simple construction from Sect. 2 of intersecting the cube with a subarrangement of the braid arrangement can serve as a lens into the world of quasisymmetric functions [21].

A quasisymmetric function is a formal power series $Q$ of bounded degree in countably many variables $x_1,x_2,\ldots$ such that the coefficients of $Q$ are shift invariant, i.e., for every $(\alpha _1,\ldots ,\alpha _m)$ the coefficients of the monomials $x_{i_1}^{\alpha _1}x_{i_2}^{\alpha _2}\cdots x_{i_m}^{\alpha _m}$ for any $i_1<i_2<\ldots <i_m$ are equal [50]. Note that a quasisymmetric function can have bounded degree without being a polynomial since we have infinitely many variables at our disposal.

To approach these from a geometric perspective, it is instructive to start with quasisymmetric functions in non-commuting variables or nc-quasisymmetric functions for short [14]. Here the variables $x_i$ do not commute multiplicatively and the constraint is that two monomials $x_{i_1}\cdots x_{i_d}$ and $x_{j_1}\cdots x_{j_d}$ have the same coefficient if the tuples $i=(i_1,\ldots ,i_d)$ and $j=(j_1,\ldots ,j_d)$ induce the same ordered set partition $\varDelta (i)=\varDelta (j)$. Here $\varDelta (i)=(\varDelta _1,\ldots ,\varDelta _m)$ is an ordered partition of the index set $\{1,\ldots ,d\}$ such that $i|_{\varDelta _l}$ is constant and $i|_{\varDelta _l}<i|_{\varDelta _{l+1}}$ for all $l$, e.g., $\varDelta (3,2,2,3,1) = (\{5\},\{2,3\},\{1,4\})=:5|23|14$.

To visualize what is going on here, we need a new way of associating integer vectors with monomials. Classically, we identify monomials in commuting variables with their exponent vector. Here, we identify monomials in non-commuting variables with their vector of indices, i.e., we identify $x_{v_1}\cdots x_{v_d}$ with $(v_1,\ldots ,v_d)\in \mathbb {Z}^d_{\ge 1}$. This allows us to picture the map $\varDelta$: If $\phi$ is an ordered set partition of $\{1,\ldots ,d\}$, then $\varDelta ^{-1}(\phi )$ is precisely the set of integer vectors contained in a simplicial cone of the partial polyhedral complex obtained by triangulating the positive orthant by the braid arrangement, as shown in Fig. 12. In other words, the monomial nc-quasisymmetric functions

$$ \mathcal {M}_\phi = \sum _{v\in \mathbb {Z}^d, \varDelta (v)=\phi } x_{v_1}\cdots x_{v_d} $$

form a basis of the space of nc-quasisymmetric functions and these are nothing but cones in the braid arrangement.

Fig. 12.

The “shift-invariant regions” of integer points that are mapped to the same ordered set partition by $\varDelta$ are the simplicial cones in the braid arrangement and correspond to the monomial quasisymmetric function.

Any nc-quasisymmetric function can be turned into a quasisymmetric function simply by allowing variables to commute. This can be modeled geometrically by taking an integer vector and permuting its entries so that they are in weakly increasing order, i.e., an element of the half-open simplicial cone $C:=\left\{ v \; \,|\,\; 0<v_1\le \ldots \le v_d \right\}$. This maps $\mathcal {M}_{(\phi _1,\ldots ,\phi _m)}$ to the monomial quasisymmetric function $M_{(|\phi _1|,\ldots ,|\phi _m|)}$ where

$$ M_{(\alpha _1,\ldots ,\alpha _m)} = \sum _{1\le i_1<\ldots <i_m} x_{i_1}^{\alpha _1}\cdot \ldots \cdot x_{i_m}^{\alpha _m}. $$

The monomial quasisymmetric functions form a basis of the space of quasisymmetric functions. Thus every quasisymmetric function can be visualized as assigning a weight to every face of the cone $C$. The support of a quasisymmetric function is thus a partial polyhedral subcomplex $X$ of the face lattice of $C$.

Going one step further it is possible to obtain a polynomial $p$ from a quasisymmetric function $Q$ by substituting 1 into the first $k$ variables and $0$ into all other variables, i.e., $Q(1^k)=p(k)$. Geometrically, this substitution eliminates all integer points that contain an entry larger than $k$. This corresponds to intersecting the complex $X$ of cones with the cube $(0,k]^d$, turning $X$ into a simplicial complex $X\cap (0,k]^d$ and $p$ into the Ehrhart function $\mathrm{ehr }_{X\cap (0,1]^d}(k) = Q(1^k)$.¹¹ These observations provide a direct translation between Ehrhart functions constructed using the braid arrangement and quasisymmetric functions.

This connection provides fertile ground for future exploration. On the one hand, the geometric approach offers a very flexible framework for defining quasisymmetric functions. Scheduling problems alone capture a wide range of known quasisymmetric functions, such as the chromatic symmetric function, the matroid invariant of Billera-Jia-Reiner, or Ehrenborg’s quasisymmetric function for posets, as well as new ones, such as the Bergman and arboricity quasisymmetric functions [21]. On the other hand, many methods for the analysis of Ehrhart polynomials carry over to the quasisymmetric function world. For example, the specialization $Q(1^k)$ collects the coefficients of $Q$ in the fundamental basis in the $h^*$-vector of the associated Ehrhart-polynomial – and similarly for the monomial basis and the $f^*$-vector. In particular, if $X$ is a partial subcomplex of the braid arrangement and $N, Q$ and $\mathrm{ehr }_{X\cap (0,1]^d}$ are the associated nc-quasisymmetric, quasisymmetric and Ehrhart functions, then partitionability of $X$ implies non-negativity of the coefficients in the fundamental basis of $N$ and $Q$ and non-negativity of the $h^*$-vector of $\mathrm{ehr }_{X\cap (0,1]^d}$. If $X$ is given by a scheduling problem, partitionability can be guaranteed if the boolean expression defining the scheduling problem takes the form of a certain kind of decision tree [21].

9 Algorithms for Counting Integer Points in Polyhedra

There are many different computational problems associated with polyhedra. The problem of deciding whether there exists a rational vector $v\in \mathbb {Q}^n$ satisfying a linear system of inequalities¹² is polynomial time computable, but when we look for an integer vector $v\in \mathbb {Z}^n$ instead, the problem becomes NP-hard [46]. However, if the dimension of the polyhedron, i.e., the number of variables of the system, is fixed a priori, then there is a polynomial time algorithm for finding an integer solution as Lenstra was able to show in 1983 [42]. While the problem of counting integer solutions is #P-hard as well, the question remained open whether it becomes polynomial time computable if the dimension is fixed. The first algorithm with a polynomial running time in fixed dimension was described by Barvinok in 1994 [5] and it took ten more years until such an algorithm was first implemented by De Loera et al. in 2004 [30].

In this section we give an overview over the algorithmic methods for computing the number of integer points in a polyhedron $P$, and the related problems of computing the Ehrhart polynomial $\mathrm{ehr }_P$ and a rational function expression of the multivariate generating function $\phi _P$ of all integer points in $P$. Independently of whether the goal is to compute $\mathrm{ehr }_P$ by first passing from $P$ to $\mathrm{cone }(P\times \{1\})$ or whether the goal is to compute $\phi _P$ and $\mathbb {Z}^n\cap P$ directly by using Brion’s theorem, the methods employed are similar and consist of three basic steps. First, the polyhedron $P$ is decomposed into simplicial cones. Second, a rational function representation of the integer points in these simplicial cones is computed. We will focus on this step in our exposition since it is crucial with regard to runtime complexity. Third, the obtained rational function expression needs to be specialized if the number of integer points or the Ehrhart (quasi-)polynomial is desired.

To decompose a polyhedron $P$ into simplicial cones, we start by appealing to Brion’s theorem and represent $P$ as the sum of its vertex cones, modulo lines.¹³ To achieve this, we need to compute the vertices and edge directions of $P$. Next, the resulting cones need to be triangulated to make them simplicial. There are sophisticated algorithms available for both tasks [32, 33, 44, 45]. It is also possible to compute a decomposition of $P$ into simplicial cones directly, without computing vertices or triangulating, using the Polyhedral Omega algorithm [23]. Polyhedral Omega is based on simple explicit rules for manipulating simplicial cones formally and is motivated by the symbolic computation framework of partition analysis [1].

In the second step, we use the ideas developed in Sects. 5 and 6 to represent the generating function $\phi _C$ of integer points in a simplicial cone $C=\mathrm{cone }_\mathbb {R}(v_1,\ldots ,v_d)\subset \mathbb {Z}^d$ as a rational function. Let $V$ denote the matrix with the generators $v_i$ of $C$ as columns. The straightforward approach is to use (5) and obtain a rational function expression by simply enumerating all integer points in the fundamental parallelepiped $\varPi (V)$ of $C$. This is both simple and efficient if the index $\mathbb {Z}^d\cap \varPi =|\det (V)|$ of $C$ is sufficiently small. However, in the worst case, the index may be exponential in encoding size of $V$, as Fig. 14 shows. Thus it is not clear a priori that there exists a rational function expression for $\phi _C$ whose encoding size is polynomial in the encoding size of the input. Barvinok’s key achievement was to find such a representation.

Fig. 13.

In order to compute all integer points in the fundamental parallelepiped $\varPi (a_1,a_2)$, shown in the left panel of (a), we proceed as follows. (a) Using the Smith normal form, we first perform a change of basis on the integer lattice $\mathbb {Z}^2$ and then a change of basis on the sublattice generated by $a_1,a_2$, so that the bases align. (b) Listing all the integer points in the aligned fundamental parallelepiped $\varPi (a_1',a_2')$ is easy. We transform these into integer points in $\varPi (a_1,a_2)$ by modular arithmetic (taking fractional parts of coordinates wrt. the original basis $a_1,a_2$).

Before we come to Barvinok’s short rational function representation, however, it is instructive to take a closer look at how to enumerate the integer points in $\varPi$ explicitly. There are several well-known approaches to this problem [23, 25, 40] which are all closely related. We will work with the Smith normal form of the matrix $V$, which can be computed in polynomial time [46]. The Smith normal form of $V$ is a representation $V=USW$ where $U,S,W$ are integer matrices, $U,W$ have determinant $\pm 1$ and $S$ is a diagonal matrix whose diagonal entries $s_1,\ldots ,s_d$ satisfy $s_i|s_{i+1}$. This can be interpreted as shown in Fig. 13. The columns of $V$ form a basis of a sublattice $J$ of the integer lattice $\mathbb {Z}^d$, and $V$ gives the coordinates of this basis with respect to the standard basis of $\mathbb {Z}^d$. The matrices $U$ and $W$ represent changes of basis on both lattices such that the new bases $B_J$ of $J$ and $B_{\mathbb {Z}^d}$ of $\mathbb {Z}^d$ line up. Since the elements of $B_J$ are multiples of the elements of $B_{\mathbb {Z}^d}$, the integer points $x_i$ in the fundamental parallelepiped of $B_J$ are easy to enumerate. By computing the coordinates of the $x_i$ wrt. the original basis $V$ of $J$ and taking fractional parts, we translate the $x_i$ into the fundamental parallelepiped $\varPi (V)$ and we are guaranteed that we get every point in $\mathbb {Z}^d\cap \varPi (V)$ exactly once. This process is summarized in the formula

$$ \phi _{\mathrm{cone }_\mathbb {R}(V)(z)} = \frac{\sum _{k_1=0}^{s_1-1}\cdots \sum _{k_1=0}^{s_1-1} z^{\frac{1}{s_d} V( W^{-1} (s_1'k_1,\ldots ,s_d'k_d)^\top \mod s_d ) } }{(1-z^{v_1})\cdot \ldots \cdot (1-z^{v_d})} $$

where $s_i'=\frac{s_d}{s_i}$. This particular expression is taken from [23].

Now we come to Barvinok’s central idea. Consider the cone $C$ generated by $(1,0,0)$, $(0,1,0)$ and $(1,1,a)$ for $0<a\in \mathbb {Z}$. Its fundamental parallelepiped contains $a$ integer points, as shown in Fig. 14, which is exponential in the encoding size $\mathcal {O}(\log (a))$ of $C$. Moreover, there is no way to write $C$ as a union of $\mathcal {O}(\log (a))$ unimodular cones of index 1. Using inclusion-exclusion, however, $C$ can be written as the positive orthant $C_1$ minus the cone $C_2$ generated by $(0,0,1)$, $(0,1,0)$, $(1,1,a)$ and the cone $C_3$ generated by $(1,0,0)$, $(0,0,1)$, $(1,1,a)$ which all have index 1. This generalizes. Let $C$ denote a simplicial cone in fixed dimension $d$ and let $I$ denote its index. Using the LLL algorithm it is possible to find an integer vector $u$ such that $C=\mathrm{cone }_\mathbb {R}(v_1,\ldots ,v_d)$ can be written as a signed combination of the cones $C_1=\mathrm{cone }_\mathbb {R}(u,v_2\ldots ,v_d)$, $C_2=\mathrm{cone }_\mathbb {R}(v_1,u,\ldots ,v_d)$, $\ldots$, $C_d=\mathrm{cone }_\mathbb {R}(v_1,\ldots ,v_{d-1},u)$, where some facets of the $C_i$ have to be opened according to a few explicit combinatorial rules [40]. The key property of this construction is that indices of the cones $C_i$ decrease quickly. Applying this decomposition recursively, the indices of the cones will eventually reach 1, i.e., the cones will become unimodular. At each node of the recursion tree one cone is split into $d$-cones, however, the depth of the tree is at most doubly logarithmic in $I$. Thus the total number of cones obtained is polynomial in the encoding length of $C$. The result is the following fundamental theorem.

Fig. 14.

$C=\mathrm{cone }_\mathbb {R}((1,0,0),(0,1,0),(1,1,a))$ has $a$ integer points in its fundamental parallelepiped. This number of integer points is therefore exponential in the encoding size of $C$ which is in $\mathcal {O}(\log (a))$. However $C$ can be written as a signed sum $C=C_1-C_2-C_3$ of unimodular cones. Here the facet of $C_2$ generated by $(0,1,0)$ and $(1,1,a)$ is open and the two facets of $C_3$ generated by $(1,1,a)$ and one of the other two generators are open.

Theorem 10

(Barvinok [5]). Let $C\subset \mathbb {Z}^d$ be a $d$-dimensional simplicial cone with integer generators. Then there exists signs $\epsilon _i$ and vectors $a_i,b_{i,j}$ such that

$$\begin{aligned} \phi _C(z) = \sum _{i=1}^N \epsilon _i\frac{z^{a_i}}{(1-z^{b_{i,1}})\cdot \ldots \cdot (1-z^{b_{i,d}})} \end{aligned}$$

(7)

and for fixed $d$ the number of summands $N$ is bounded by a polynomial in the encoding length of $C$.

The third step is to specialize the representation of $\phi _P$ in terms of multivariate rational functions we have obtained thus far, in order to get the Ehrhart polynomial $\mathrm{ehr }_P$ or the number $\#\mathbb {Z}^n\cap P$. This specialization is non-trivial, especially if Barvinok decompositions are used, since typically the desired specialization is a pole of the rational function representation. However, using an exponential substitution and limit arguments it is possible to compute this specialization in polynomial time.

The toolbox of algorithms we have described here has many more applications and extensions. For example, it is possible to extend these methods to handle multivariate Ehrhart polynomials [55], to compute intersections $\phi _{P\cap Q}$ given $\phi _P$ and $\phi _Q$ [4], to compute Pareto optima in multi-criteria optimization over integer points in polyhedra [28], to integrate and sum polynomials over polyhedra [3] and to convert between rational function representations and piecewise quasipolynomial representations of counting functions [54] – all in polynomial time if the dimension is fixed. As starting points for further reading we recommend the textbooks [6, 29].

10 Lattice Point Sets and the Euclidean Algorithm

After these very general considerations, we end this exposition on a playful note by taking a closer look at integer point geometry in dimension 2 and discussing several different ways in which the Euclidean algorithm makes an appearance.

Fig. 15.

(a) $\gcd (9,6)=3.$ (b) $-1\cdot 3 + 2 \cdot 2 = 1$ since $(2,1)$ is closest to the line through $(3,2)$ which means $\mathbb {Z}^2\cap \varPi ((3,2),(2,1))$ contains no integer point except the origin. (c) $\gcd (7,5)=1$ and $-2\cdot 7 + 3\cdot 5 = 1$.

The integer lattice in the plane is a great stage for visualizing the greatest common divisor, as Fig. 15 shows. For two integers $a,b\in \mathbb {Z}$, the line segment in the plane from the origin to the point $(a,b)$ contains precisely $\gcd (a,b)+1$ integer points. Let $(p,q)$ denote the coordinates of a lattice point closest to but not on the line $L$ through $(0,0)$ and $(a,b)$. By construction, the fundamental parallelepiped spanned by $(a,b)$ and $(p,q)$ contains precisely $\gcd (a,b)$ lattice points on the line and no lattice points off the line.

$$ \gcd (a,b)=\varPi ((a,b),(p,q))=\det \begin{pmatrix}a&{}p\\ b&{}q\end{pmatrix} = ap - bq. $$

Thus the coordinates of the closest points give precisely the coefficients produced by the extended Euclidean algorithm.

From the above observation it immediately follows that the value of the GCD increases linearly along any such line $L$. If $(a,b)$ is the integer point closest to the origin on such a line $L$, then $\gcd (a,b)=1$. The next values of the GCD on $L$ are thus $\gcd (2a,2b)=2$, $\gcd (3a,3b)=3$. The graph of the function $\gcd :\mathbb {Z}^2_{>0}\rightarrow \mathbb {Z}_{>0}$ is thus contained in a countable collection of rays from the origin through all points $(a,b)$ with $\gcd (a,b)=1$. This “graph” of the GCD is shown in Fig. 16.

Fig. 16.

The graph of the $\gcd$ $g=\gcd (a,b)$ as described in the text. Shown are the rays from the origin through $(a,b)$ starting at $(a,b)$ for all $a,b$ with $\gcd (a,b)=1$. The color of a ray is given by its depth in the recursion tree of the Euclidean algorithm. The plots in the rightmost column show parallel projections of the graph onto the $(g,a)$ and $(a,b)$ planes, respectively (Color figure online).

A closer look at the graph in Fig. 16 immediately reveals a recursive tree-like structure. It turns out that this tree corresponds precisely to the recursive operation of the Euclidean algorithm. The Euclidean algorithm as described by Euclid moves from $(a,b)$ to $(a-b,a)$ if $a>b$, it moves from $(a,b)$ to $(a,b-a)$ if ${a<b}$ and it terminates if $a=b$. The perceptive reader will note that this immediately gives a way to enumerate all positive rational numbers as nodes of an infinite binary tree [26]. However, tracing out these paths of the Euclidean algorithm in the plane does not yet reveal the connection to the graph of the GCD. To that end, we turn the Euclidean algorithm on its head.

We fix the point $p=(a,b)$ whose gcd we wish to compute and run the Euclidean algorithm by changing the basis $v_1$, $v_2$ of $\mathbb {Z}^2$ in each step. We define the center of the current basis as the sum $c=v_1+v_2$. If $p$ lies below the line through $c$ we change our basis to $v_1'=v_1$ and $v_2'=c$. If $p$ lies above the line through $c$ we change our basis to $v_1'=c$ and $v_2'=v_2$. If $p$ lies on the line through $c$ we are done since $\gcd (a,b) = \frac{a}{c_1} = \frac{b}{c_2}$. Tracing out all the paths the center can take throughout this recursion, we obtain Fig. 17 which reveals the tree structure of the base points of the rays in Fig. 16 and which gives a very natural (and novel) embedding of the Stern-Brocot tree [34, p. 116–117] in the plane.

Fig. 17.

The left panel shows all lattice points $(a,b)$ in the plane with $\gcd (a,b)=1$, up to a recursion depth of 5 in the Eulidean algorithm. The right panel also shows the tree structure induced by the inverted Euclidean algorithm as described in the text.

Fig. 18.

Following the Euclidean algorithm, we reduce the triangle $T_{12,7}$ recursively, by removing triangles with integral slope and applying shearing lattice transformations. In this way we can decompose the “staircase” of integer points below the line from the origin to $(12,7)$ into “simple” triangles.

To conclude, we follow [20] and examine the structure of the integer points below the line $L$ in more detail, going beyond the closest point $(p,q)$. Define $T_{a,b}$ to be the triangle with vertices $(0,0)$, $(a,0)$ and $(a,b)$. As we can see in Fig. 18, the “staircase” of integer points in $T_{a,b}$ is irregular: the possible steps as we move from one column to the next are of two different heights, and it is not clear a priori what the underlying pattern is. It turns out, however, that the triangles $T_{a,b}$ have a very nice recursive structure. The key observation is that triangles of the form $T_{c,c}$ are very easy to describe as we always go exactly one step higher as we move from one column to the next. However, if $a > b$, then $T_{a,b}$ contains a triangle of the form $T_{b,b}$, sitting in the lower right corner. Removing this translate of the half-open triangle $T_{b,b}'$, we are left with a triangle $\tilde{T}$ with vertices $(0,0), (a-b,0)$ and $(a,b)$. Shearing $\tilde{T}$ using the linear transformation $A:(x,y)\mapsto (x-y,y)$, we see that the integer points in $\tilde{T}$ have the same structure as those in $T_{a-b,b}$. Here it is crucial that the linear transformation $A$ maps $\mathbb {Z}^2$ bijectively onto itself. Now, if $a<b$ we can apply the same procedure in the other direction. Just like in the Euclidean algorithm we continue recursively until we reach a triangle of the form $T_{c,c}$ at which point we stop. We can thus decompose any triangle $T_{a,b}$ into simple triangles of the form $T_{c,c}$. This process is illustrated in Fig. 18.

This basic approach can yield much more information as detailed in [20]. For example, an analysis of how exactly the big and small steps in the staircase are distributed leads to several characterizations of Sturmian sequences of rational numbers. Moreover, using a recursive procedure similar in spirit to Fig. 18, it is possible to show that the sets of lattice points in 2-dimensional fundamental parallelepipeds always have a short positive description as a union of Minkowski sums of discrete line segments – this short description yields short rational function expressions for 2-dimensional fundamental parallelepipeds, which are quite distinct from those obtained via Barvinok’s algorithm.