THE PARTIAL-FRACTIONS METHOD FOR COUNTING SOLUTIONS TO INTEGRAL LINEAR SYSTEMS

MATTHIAS BECK

Dedicated to Lou Billera on the occasion of his sixtieth birthday.

Abstract. We present a new tool to compute the number ϕ_{A}(b) of integer solutions to the linear system

x ≥ 0 , A x = b ,

where the coefficients of A and b are integral. ϕ_{A}(b) is often described as a vector partition function. Our methods use partial fraction expansions of Euler’s generating function for ϕ_{A}(b). A special class of vector partition functions are Ehrhart (quasi-)polynomials counting integer points in dilated polytopes.

1. Euler’s generating function

We are interested in computing the number of integer solutions of the linear system

x ∈ ℝ_{≥0}^{d} , A x = b ,

where A is a nonnegative (m × d)-integral matrix and b ∈ ℤ^{m}. We think of A as fixed and study the number of solutions ϕ_{A}(b) as a function of b. (Strictly speaking, this function should only be defined for those b which lie in the nonnegative linear span of the columns of A.)

The function ϕ_{A}(b), often called a vector partition function, appears in a wealth of mathematical areas and beyond: Number Theory (partitions), Discrete Geometry (polyhedra), Commutative Algebra (Hilbert series), Algebraic Geometry (toric varieties), Representation Theory (tensor product multiplicities), Optimization (integer programming), as well as applications to Chemistry, Biology, Physics, Computer Science, and Economics.

Denote the columns of A by c_{1}, …, c_{d}. The following lemma goes back to at least Euler [15]:

Lemma 1 (Euler). ϕ_{A}(b) equals the coefficient of z^{b} := z_{1}^{b_{1}} ⋯ z_{m}^{b_{m}} of the function

f(z) = \frac{1}{(1 − z^{c_{1}}) ⋯ (1 − z^{c_{d}})}

Date: February 29, 2004. 2000 Mathematics Subject Classification. Primary 05A15, 52C07; Secondary 52C45. Key words and phrases. Vector partition function, partial fractions expansion, quasi-polynomial, lattice-point

counting, rational convex polytope, Ehrhart theory.

This paper was written while the author was at the Mathematical Sciences Research Institute in Berkeley and at the Max-Planck-Institut für Mathematik in Bonn. The author thanks both institutes for their hospitality. Thanks also to Ira Gessel and Sinai Robins for fruitful discussions, and to the referees for many helpful comments.

To appear in Discrete & Computational Geometry (special issue in honor of Louis Billera).

expanded as a power series centered at z = 0.

Proof. Expand each factor of the right-hand side into a geometric series. □

Equivalently, the coefficient of z^{b} in f(z) equals the constant term in \frac{f(z)}{z^{b}}, denoted by const \frac{f(z)}{z^{b}}. So Euler’s Lemma can be conveniently stated as

ϕ_{A}(b) = const \frac{1}{(1 − z^{c_{1}}) ⋯ (1 − z^{c_{d}}) z^{b}} .

In a series of articles [3, 5, 6, 7], we used complex integration of \frac{f(z)}{z^{b}} to compute ϕ_{A}(b) for special cases of A. Similar techniques were applied in [19]. Here we expand \frac{f(z)}{z^{b}} into partial fractions to compute its constant term, and hence ϕ_{A}(b). This work constitutes in a sense a refinement of the complex-integration methods, with the advantage that it is more flexible and—more importantly— applicable for any integral linear system.

2. Vector partition functions

The nature of the counting function ϕ_{A}(b) is given by the following theorem. A quasi-polynomial is a finite sum Q(b) = ∑_{n} c_{n}(b) b^{n} with coefficients c_{n} that are functions of b which are periodic in every component of b. The degree of Q is the degree of the largest power b^{n} appearing in Q. A matrix is unimodular if every square submatrix has determinant ±1.

Theorem 2 (Sturmfels [22]). The function ϕ_{A}(b) is a piecewise-defined quasi-polynomial in b of degree d − rank(A). The regions of ℝ^{m} in which ϕ_{A}(b) is a single quasi-polynomial are polyhedral, that is, they are defined by linear constraints. If A is unimodular then ϕ_{A} is a piecewise-defined polynomial.

The unimodular case of this theorem is due to Dahmen and Micchelli [11, Corollary 3.1].

The computation of both ϕ_{A}(b) and the chamber complex consisting of the regions of quasipolynomiality give rise to challenging problems. The most powerful technique for computing ϕ_{A}(b) which we are aware of is due to Brion and Vergne [8]. (The methods described here are much more elementary.) The chamber complex is still much of a mystery. A promising approach can be found in [23].

We finish this section with a reciprocity theorem. Let ϕ_{A}^{∘}(b) count the integer solutions of

x > 0 , A x = b .

Both ϕ_{A} and ϕ_{A}^{∘} are quasi-polynomials, and can hence be algebraically defined for arguments which are not integer vectors in the positive span of A. The following identity shows the close relationship between the two functions.

Theorem 3 ([4]). The quasi-polynomials ϕ_{A} and ϕ_{A}^{∘} satisfy

ϕ_{A}(−b) = (−1)^{d−rank A}ϕ_{A}^{∘}(b) .

This identity gives rise to a symmetry property of ϕ_{A}(b). Let r_{k} denote the sum of the entries in the k^{th} row of A, and let r = (r_{1}, …, r_{m}). Then the integer solutions of

x > 0 , A x = b

are in bijection (via x_{k} ↦ x_{k} − 1) with the integer solutions of

x ≥ 0 , A x = b − r ,

and hence ϕ_{A}^{∘}(b) = ϕ_{A}(b − r). This yields:

Corollary 4. The quasi-polynomial ϕ_{A} satisfies

ϕ_{A}(b) = (−1)^{d−rank A}ϕ_{A}(−b − r) .

3. The partial-fractions method

This section describes the idea behind our computations. Recall that our goal is to derive

ϕ_{A}(b) = const \frac{1}{(1 − z^{c_{1}}) ⋯ (1 − z^{c_{d}}) z^{b}} .

We start by expanding

\frac{1}{(1 − z^{c_{1}}) ⋯ (1 − z^{c_{d}}) z^{b}} .

into partial fractions in one of the components of z, say z_{1}:

\frac{1}{(1 − z^{c_{1}}) ⋯ (1 − z^{c_{d}}) z^{b}} = \frac{1}{z_{2}^{b_{2}} ⋯ z_{m}^{b_{m}}} ∑_{k=1}^{d} \frac{A_{k}(z, b_{1})}{1 − z^{c_{k}}} + ∑_{j=1}^{b_{1}} \frac{B_{j}(z)}{z_{1}^{j}} .

Here A_{k} and B_{j} are polynomials in z_{1}, rational functions in z_{2}, …, z_{m}, and exponential in b_{1}. (We are tacitly assuming that there are no multiple poles (besides z = 0), which generally holds unless m = 1, a case which can be handled easily.) The two sums on the right-hand side correspond to the analytic and the meromorphic part with respect to z_{1} = 0. The latter does not contribute to the z_{1}-constant term, whence

ϕ_{A}(b) = const_{z_{2},...,z_{m}} (\frac{1}{z_{2}^{b_{2}} ⋯ z_{m}^{b_{m}}} const_{z_{1}} (∑_{k=1}^{d} \frac{A_{k}(z, b_{1})}{1 − z^{c_{k}}}))

= const (\frac{1}{z_{2}^{b_{2}} ⋯ z_{m}^{b_{m}}} ∑_{k=1}^{d} A_{k}(0, z_{2}, …, z_{m}, b_{1})) . (1)

The effect of one partial fraction expansion is to eliminate one of the variables of the generating function, at the cost of replacing one rational function by a sum of such. The following idea is now evident.

Algorithm. Apply (1) repeatedly to eliminate z_{1}, then z_{2}, etc., up to z_{m−1}.

The constant term of the remaining rational functions in the one variable z_{m} can be computed with the methods introduced in [5]. This implies, in particular, that any vector partition function is a quasi-polynomial whose nontrivial ingredients are Fourier-Dedekind sums [5]. The constant-term computation for the last variable also explains the quasi-polynomial character of ϕ_{A}, since in this last step roots of unity will appear, with the components of b as exponents.

We note that this algorithm computes ϕ_{A}(b) as a function of b, that is, it allows symbolic computation. Secondly, it is not very hard to deduce Sturmfels’s Theorem 2 from this algorithm. What might be more important, however, is the fact that the constraints which define the regions of quasi-polynomiality of ϕ_{A} are obtained “on the go” as one computes ϕ_{A}: When expanding into partial fractions, one has to check where the poles of a rational function are. The components of b will appear (linearly) in the exponents of these rational functions, and hence one will automatically have to split the computation into cases which give rise to different regions in the chamber complex of quasi-polynomiality.

While we hope that our algorithm gives a computational tool, in particular, for obtaining the chamber complex defining the regions of quasi-polynomiality of a vector partition function, it is not clear to us why the chambers obtained from the partial fractions analysis coincide with Sturmfels’s predicted chambers.

Our algorithm is best illustrated by going through an actual example.

4. An illustrating example

Let A = ( \begin{matrix}1 & 2 & 1 & 0 \\ 1 & 1 & 0 & 1 \end{matrix} ), and write b = (a, b), so ϕ_{A}(a, b) counts the integer solutions of

x_{1}, x_{2}, x_{3}, x_{4} ≥ 0 , \begin{aligned}x_{1} + 2x_{2} + x_{3} & = & a \\ x_{1} + x_{2} + x_{4} & = & b . \end{aligned}

By Euler’s Lemma 1,

ϕ_{A}(a, b) = const \frac{1}{(1 − zw)(1 − z^{2}w)(1 − z)(1 − w)z^{a}w^{b}} .

We first expand into partial fractions with respect to w:

\frac{1}{(1 − zw)(1 − z^{2}w)(1 − w)w^{b}} = −\frac{\frac{z^{b+1}}{(1−z)^{2}}}{1 − zw} + \frac{\frac{z^{2b+3}}{(1−z)(1−z^{2})}}{1 − z^{2}w} + \frac{\frac{1}{(1−z)(1−z^{2})}}{1 − w} + ∑_{k=1}^{b} \frac{…}{w^{k}} .

Taking constant terms gives

ϕ_{A}(a, b) = const_{z} (\frac{1}{(1 − z)z^{a}} const_{w} (\frac{1}{(1 − zw)(1 − z^{2}w)(1 − w)w^{b}} ))

= const (\frac{1}{(1 − z)z^{a}} (−\frac{z^{b+1}}{(1 − z)^{2}} + \frac{z^{2b+3}}{(1 − z)(1 − z^{2})} + \frac{1}{(1 − z)(1 − z^{2})}))

= const (−\frac{z^{b−a+1}}{(1 − z)^{3}} + \frac{z^{2b−a+3}}{(1 − z)^{2}(1 − z^{2})} + \frac{1}{(1 − z)^{2}(1 − z^{2})z^{a}} ) (2)

(At this point, we could interpret each of the three constant terms as counting integer solutions to new linear systems. For example, the last term gives the number of integer points (x, y) ≥ 0 satisfying 2x + y ≤ a. To keep a general flavor, we continue with our general algorithm.)

We compute the constant term of each of the three terms separately. For starters,

const \frac{z^{b−a+1}}{(1 − z)^{3}} = 0

if b − a + 1 > 0, equivalently (since a and b are integers) b ≥ a. If b < a, we use

\frac{1}{(1 − z)^{3}} = ∑_{k≥0} \binom{k + 2}{2}z^{k} ,

which gives

const \frac{1}{(1 − z)^{3}z^{a−b−1}} = \binom{a − b + 1}{2} = \frac{(a − b)^{2}}{2} + \frac{a − b}{2} .

Incidentally, this identity is true not only for b < a, but also for b = a and b = a + 1, because the right-hand side vanishes then. This suggests that the regions of quasi-polynomiality overlap, as was proved by Szenes and Vergne [23]. Hence for the first constant term, we obtain

const \frac{1}{(1 − z)^{3}z^{a−b−1}} = \begin{cases}0 & if b ≥ a, \\ \frac{(a−b)^{2}}{2} + \frac{a−b}{2} & if b ≤ a + 1. \end{cases}

For the second term in (2),

const \frac{z^{2b−a+3}}{(1 − z)^{2}(1 − z^{2})} = 0

if 2b − a + 2 ≥ 0. If a ≥ 2b + 3 we expand into partial fractions again:

const \frac{z^{2b−a+3}}{(1 − z)^{2}(1 − z^{2})} = const (\frac{1/2}{(1 − z)^{3}} + \frac{\frac{a−2b−3}{2} + \frac{1}{4}}{(1 − z)^{2}} + \frac{\frac{(a−2b−3)^{2}}{4} + \frac{a−2b−3}{2} + \frac{1}{8}}{1 − z} + \frac{(−1)^{a+1}/8}{1 + z})

= \frac{(a − 2b)^{2}}{4} + \frac{2b − a}{2} + \frac{1 + (−1)^{a+1}}{8} .

Similar to the first constant-term computation, this identity is also valid for a = 2b + 2, 2b + 1, 2b, whence

const \frac{z^{2b−a+3}}{(1 − z)^{2}(1 − z^{2})} = \begin{cases}0 & if a ≤ 2b + 2, \\ \frac{(a−2b)^{2}}{4} + \frac{2b−a}{2} + \frac{1+(−1)^{a+1}}{8} & if a ≥ 2b. \end{cases}

The computation for the last term in (2) is almost identical. (Note that this term always contributes.)

const \frac{1}{(1 − z)^{2}(1 − z^{2})z^{a}} = const (\frac{1/2}{(1 − z)^{3}} + \frac{\frac{a}{2} + \frac{1}{4}}{(1 − z)^{2}} + \frac{\frac{a^{2}}{4} + \frac{a}{2} + \frac{1}{8}}{1 − z} + \frac{(−1)^{a}/8}{1 + z})

= \frac{a^{2}}{4} + a + \frac{7 + (−1)^{a}}{8} .

Summing up all terms in (2) gives finally

ϕ_{A}(a, b) = \begin{cases}\frac{a^{2}}{4} + a + \frac{7+(−1)^{a}}{8} & if a ≤ b, \\ −\frac{(a−b)^{2}}{2} − \frac{a−b}{2} + \frac{a^{2}}{4} + a + \frac{7+(−1)^{a}}{8} & if \frac{a}{2} − 1 ≤ b ≤ a + 1, \\ −\frac{(a−b)^{2}}{2} − \frac{a−b}{2} + \frac{(a−2b)^{2}}{4} + \frac{2b−a}{2} + \frac{1+(−1)^{a+1}}{8} + \frac{a^{2}}{4} + a + \frac{7+(−1)^{a}}{8} & if b ≤ \frac{a}{2} \end{cases}

= \begin{cases}\frac{a^{2}}{4} + a + \frac{7+(−1)^{a}}{8} & if a ≤ b, \\ ab − \frac{a^{2}}{4} − \frac{b^{2}}{2} + \frac{a+b}{2} + \frac{7+(−1)^{a}}{8} & if \frac{a}{2} − 1 ≤ b ≤ a + 1, \\ \frac{b^{2}}{2} + \frac{3b}{2} + 1 & if b ≤ \frac{a}{2}. \end{cases}

It is a fun exercise to show that ϕ_{A}(a, b) = ϕ_{A}(−a − 4, −b − 3), as promised by Corollary 4.

We pause for a moment to introduce the geometry behind our linear system. By thinking of x_{3} and x_{4} as slack variables, we can see that

x_{1}, x_{2}, x_{3}, x_{4} ≥ 0 , \begin{aligned}x_{1} + 2x_{2} + x_{3} & = & a \\ x_{1} + x_{2} + x_{4} & = & b . \end{aligned}

is equivalent to

x_{1}, x_{2} ≥ 0 , \begin{aligned}x_{1} + 2x_{2} & ≤ & a \\ x_{1} + x_{2} & ≤ & b . \end{aligned}

Depending on the relationship between a and b, the geometric figure described by this linear system is a quadrilateral or triangle.

[figure: (0, b); (0, a/2); (b, 0); (a, 0); (2b − a, a − b); (0, 0)]

The inequalities which define the different cases for ϕ_{A}(a, b) determine the chamber complex in the parameter space, and in this example also the combinatorial type of the polytope: Except for boundary cases, in the first (a ≤ b) and last (b ≤ \frac{a}{2}) case, it is a triangle, and in the second case (a > b > \frac{a}{2}) a quadrilateral. In fact, the geometry of the triangle in the first case only depends on a, which is reflected in ϕ_{A}(a, b), and similarly the last case shows only dependency on b. In this last case, the triangle actually has integer vertices (the linear system is unimodular), whence we get a polynomial. In the first two cases the vertices of the polytope are half-integral, which is reflected in the period-2 quasi-polynomials. The following picture illustrates the three overlapping chambers.

[figure: a; b; \frac{a^{2}}{4} + a + \frac{7+(−1)^{a}}{8}; ab − \frac{a^{2}}{4} − \frac{b^{2}}{2} + \frac{a+b}{2}; +\frac{7+(−1)^{a}}{8}; \frac{b^{2}}{2} + \frac{3b}{2} + 1]

5. Ehrhart quasi-polynomials

A convex polytope P in ℝ^{d} is the convex hull of finitely many points in ℝ^{d}. Alternatively (and this correspondence is nontrivial [24]), one can define P as the bounded intersection of affine halfspaces. A polytope is rational if all of its vertices have rational coordinates. (A vertex of P is a point v ∈ P for which there is a hyperplane H such that {v} = P ∩ H.) We denote by P^{∘} the relative interior of P. For a positive integer t, let L_{P}(t) denote the number of integer points (“lattice points”) in the dilated polytope tP = {tx : x ∈ P}. The fundamental result about the structure of L_{P} is as follows.

Theorem 5 (Ehrhart [14]). If P is a convex rational polytope, then the functions L_{P}(t) and L_{P^{∘}}(t) are quasi-polynomials in t whose degree is the dimension of P. If P has integer vertices, then L_{P} and L_{P^{∘}} are polynomials.

Ehrhart conjectured and partially proved the following reciprocity law, which was proved by Macdonald [20].

Theorem 6 (Ehrhart-Macdonald). The quasi-polynomials L_{P} and L_{P^{∘}} satisfy

L_{P}(−t) = (−1)^{dim P}L_{P^{∘}}(t) .

The computation of Ehrhart quasi-polynomials is only slightly easier than that of ϕ_{A}. Recent work includes [1, 8, 9, 10, 12, 13, 16, 17, 18, 21].

Suppose the convex polytope P ⊂ ℝ^{d} is given by an intersection of halfspaces, that is,

P = {x ∈ ℝ^{d} : A x ≤ b} ,

for some (m × d)-matrix A and m-dimensional vector b. We may convert these inequalities into equalities by introducing slack variables. If P has rational vertices, we can choose A and b in such a way that all their entries are integers, without loss of generality nonnegative ones. In summary, we may assume that a convex rational polytope P is given by

P = {x ∈ ℝ_{≥0}^{d} : A x = b} ,

where A ∈ M_{m×d}(ℤ_{≥0}) and b ∈ ℤ_{≥0}^{m}. (If we are interested in counting the integer points in P, we may assume that P is in the nonnegative orthant, i.e., the points in P have nonnegative coordinates, as translation by an integer vector does not change the lattice-point count.)

The connection to vector partition functions is now evident. Since tP = {x ∈ ℝ_{≥0}^{d} : A x = t b}, we obtain L_{P}(t) = ϕ_{A}(tb) as a special evaluation of ϕ_{A}. Note that tb, t = 1, 2, … lie in the same chamber of quasi-polynomiality of ϕ_{A}. Ehrhart’s Theorem 5 is therefore a special case of Sturmfels’s Theorem 2, and Theorem 6 is a special case of Theorem 3.

As an example, the quadrilateral Q described by

x, y ≥ 0 , \begin{aligned}x + 2y & ≤ & 5 \\ x + y & ≤ & 4 \end{aligned}

(a special case of the polygons appearing in Section 4) with vertices (0, 0), (4, 0), (3, 1), (0, 5/2) has the Ehrhart quasi-polynomial

L_{Q}(t) = ϕ_{A}(5t, 4t) = \frac{23}{4} t^{2} + \frac{9}{2} t + \frac{7 + (−1)^{t}}{8} .

Ehrhart quasi-polynomials are easier to compute, since one does not need to derive/know the chamber complex of quasi-polynomiality of ϕ_{A}. Our algorithm, naturally, works just as well for L_{P}.

6. Concluding remarks

Many open problems and questions remain untouched. Most importantly, we hope that our ideas will give rise to practical implementations of computing vector partition functions (including the chamber complex defining the regions of quasi-polynomiality) in their various disguises in form of a computer software. Again, the partial-fraction method is more general and more flexible than algorithms using complex residues, for example in [6].

Not unrelated is the question of computational complexity. It is known that the rational generating function of the Ehrhart quasi-polynomial of a d-polytope can be computed in polynomial time if d is fixed [2]. We have not analyzed the complexity of our algorithm. This seems interesting in the light that our algorithm depends on the number of contraints, geometrically corresponding to the facets (codimension-1 faces) of the polytope. Barvinok’s algorithm, in contrast, depends on the number of vertices of the polytope.

Another venue which should be explored is the following: After each step in our algorithm, one could reinterpret the constant term of each summand as counting integer solutions of a linear system. It might be interesting to simplify each of these linear systems (as far as this is possible without changing the number of integer solutions), and then proceed with the algorithm.

References

1. Alexander I. Barvinok, Computing the Ehrhart polynomial of a convex lattice polytope, Discrete Comput. Geom. 12 (1994), no. 1, 35–48.

2. , A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed, Math. Oper. Res. 19 (1994), 769–779.

3. Matthias Beck, Counting lattice points by means of the residue theorem, Ramanujan J. 4 (2000), no. 3, 299–310.

4. , Multidimensional Ehrhart reciprocity, J. Combin. Theory Ser. A 97 (2002), no. 1, 187–194.

5. Matthias Beck, Ricardo Diaz, and Sinai Robins, The Frobenius problem, rational polytopes, and Fourier-Dedekind sums, J. Number Theory 96 (2002), no. 1, 1–21.

6. Matthias Beck and Dennis Pixton, The Ehrhart polynomial of the Birkhoff polytope, Discrete Comput. Geom. 30 (2003), no. 4, 623–637.

7. Matthias Beck and Sinai Robins, Explicit and efficient formulas for the lattice point count in rational polygons using Dedekind-Rademacher sums, Discrete Comput. Geom. 27 (2002), no. 4, 443–459.

8. Michel Brion and Michèle Vergne, Residue formulae, vector partition functions and lattice points in rational polytopes, J. Amer. Math. Soc. 10 (1997), no. 4, 797–833.

9. Sylvain E. Cappell and Julius L. Shaneson, Euler-Maclaurin expansions for lattices above dimension one, C. R. Acad. Sci. Paris Sér. I Math. 321 (1995), no. 7, 885–890.

10. Beifang Chen, Lattice points, Dedekind sums, and Ehrhart polynomials of lattice polyhedra, Discrete Comput. Geom. 28 (2002), no. 2, 175–199.

11. Wolfgang Dahmen and Charles A. Micchelli, The number of solutions to linear Diophantine equations and multivariate splines, Trans. Amer. Math. Soc. 308 (1988), no. 2, 509–532.

12. J. DeLoera, R. Hemmecke, J. Tauzer, and R. Yoshida, Effective lattice point counting in rational convex polytopes, Preprint, 2003.

13. Ricardo Diaz and Sinai Robins, The Ehrhart polynomial of a lattice polytope, Ann. of Math. (2) 145 (1997), no. 3, 503–518.

14. Eugène Ehrhart, Sur un problème de géométrie diophantienne linéaire. II. Systèmes diophantiens linéaires, J. Reine Angew. Math. 227 (1967), 25–49.

15. Leonhard Euler, De partitione numerorum in partes tam numero quam specie dates, Leonhardi Euleri Opera Omnia, Ser. 1 Vol. III (F. Rudio, ed.), Teubner, Leipzig, 1917, pp. 132–147.

16. Victor Guillemin, Riemann-Roch for toric orbifolds, J. Differential Geom. 45 (1997), no. 1, 53–73.

17. Jean-Michel Kantor and Askold Khovanskii, Une application du théorème de Riemann-Roch combinatoire au polynôme d’Ehrhart des polytopes entiers de R^{d}, C. R. Acad. Sci. Paris Sér. I Math. 317 (1993), no. 5, 501–507.

18. A. G. Khovanskiĭ and A. V. Pukhlikov, The Riemann-Roch theorem for integrals and sums of quasipolynomials on virtual polytopes, Algebra i Analiz 4 (1992), no. 4, 188–216.

19. Jean B. Lasserre and Eduardo S. Zeron, On counting integral points in a convex rational polytope, Math. Oper. Res. 28 (2003), no. 4, 853–870.

20. I. G. Macdonald, Polynomials associated with finite cell-complexes, J. London Math. Soc. (2) 4 (1971), 181–192.

21. James E. Pommersheim, Toric varieties, lattice points and Dedekind sums, Math. Ann. 295 (1993), no. 1, 1–24.

22. Bernd Sturmfels, On vector partition functions, J. Combin. Theory Ser. A 72 (1995), no. 2, 302–309.

23. András Szenes and Michèle Vergne, Residue formulae for vector partitions and Euler-MacLaurin sums, Adv. in Appl. Math. 30 (2003), no. 1-2, 295–342, Formal power series and algebraic combinatorics (Scottsdale, AZ, 2001).

24. Günter M. Ziegler, Lectures on polytopes, Springer-Verlag, New York, 1995.

Max-Planck-Institut für Mathematik, Vivatsgasse 7, 53111 Bonn, Germany

E-mail address: beck@mpim-bonn.mpg.de