April 7, 2005

2000 Mathematics Subject Classification. Primary 52C07; Secondary 05A15.We thank Margaret Readdy for helpful comments. Parts of this paper was written while the first author was at SUNY Binghamton and the Mathematical Sciences Research Institute, Berkeley; he thanks both institutions for their hospitality. The second author was partially supported by National Science Foundation grant 0200624 and by a University of Kentucky College of Arts and Sciences 2004 summer grant.
<ph f="cmbx">Ehrhart-Macdonald reciprocity extended</ph>

Matthias Beck

Richard Ehrenborg

Department of Mathematics, San Francisco State University, San Francisco, CA 94132, USA E-mail address : beck@math.sfsu.edu URL: http://math.sfsu.edu/beck Department of Mathematics, University of Kentucky, Lexington, KY 40506-0027, USA E-mail address : jrge@ms.uky.edu URL: http://www.ms.uky.edu/~jrge/

1 Introduction

The origin of this work lies in two beautiful reciprocity theorems of Ehrhart and Macdonald. One attaches to a convex rational polytope P   two counting functions: the number of integral points in t P   and the sum of the solid angles in t P   , as functions of a positive integer t   . These functions are quasi-polynomials in t   which have a life beyond the positive integers. Namely, when evaluated at negative integers, they give the respective counting function for the interior of P   . Our goal is to unify and generalize the integral-point and solid-angle counting functions, using the philosophy of valuations. Our main tool is Brion's Theorem on conic decompositions of polytopes.
A convex polyhedron P   is the intersection of (open or closed) half-spaces in R d   . We say P   is a convex polytope if it is bounded, and P   is a cone if each hyperplane bounding the half-spaces that define P   contains the origin. To each integer point m ∈ Z d   in a convex polyhedron P   we attach the tangent cone K P ( m )   , defined as follows. Denote the characteristic function of a set X   by 1 X ( x )   , that is, it is 1 for x ∈ X   and 0 otherwise. Let f P ( m , x ) = lim ε → 0 + 1 P ( m + ε x )   . Then the tangent cone at m   is K P ( m ) = { x ∈ R d : f P ( m , x ) = 1 } .   In other words, K P ( m )   equals
  • ∙   R d   if m   is in the interior of P   ;
  • ∙   ∅   if m   is not in the closure of P   ;
  • ∙   the intersection of the halfspaces defining a face ℱ   if m   is on the face ℱ   of P   , shifted to the origin.
A lattice of sets is a collection ℒ   of sets, partially ordered by set inclusion, such that for any two sets A , B ∈ ℒ   A ∩ B ∈ ℒ and A ∪ B ∈ ℒ .   A function v   on ℒ   with values in some abelian group is a valuation (often called a finitely additive measure ) if for any A , B ∈ ℒ  
v ( A ∪ B ) = v ( A ) + v ( B ) − v ( A ∩ B ) . (1.1)
We consider the lattice ℒ   generated by (open, closed, half-open) cones. We define v P ( m )   as the valuation v   evaluated at the tangent cone K P ( m )   . This is a valuation when viewed as a function of P   . However, we will mostly be interested in v P ( m )   as a function in m   .
The counting function we study is V P ( t ) : = ∑ m ∈ Z d v t P ( m ) ,   initially defined for positive integers t   . This function only makes sense if P   is bounded, that is, P   is a convex polytope. In order to state our main theorem, recall that a quasi-polynomial Q   of degree d   as an expression of the form Q ( t ) = c d ( t ) t d + ⋅ ⋅ ⋅ + c 1 ( t ) t + c 0 ( t ) ,   where c 0 , c 1 , . . . , c d   are periodic functions of t   and c d ≢ 0   . The least common multiple of the periods of the c j   is called the period of Q   . The denominator of the polytope P   is the least common multiple of the denominators of the vertices of P   . We denote the relative interior of P   by P ∘   .
Theorem 1.1. For any closed convex rational d   -polytope, V P ( t )   is a quasi-polynomial in t   of degree d   . The period of V P ( t )   divides the denominator of P   . In particular, if P   has integer vertices then V P   is a polynomial. Its evaluation at negative integers gives
V P ( − t ) = ( − 1 ) d V − P ∘ ( t ) . (1.2)
Our motivation for studying the function V P ( t )   comes from special cases of valuations. The first example is v ( A ) : = { 1 if 0 ∈ A , 0 if 0 ∉ A .   In this case V P ( t )   counts the number of integer points in t P   and Theorem  1.1 specializes to the following fundamental theorem due to Ehrhart [5, 6] . Note that V P ( t ) = V − P ( t )   .
Corollary 1.2 (Ehrhart). If P   is a closed convex rational d   -polytope, then L P ( t ) : = # ( t P ∩ Z d )   is a quasi-polynomial of degree d   , having period that divides the denominator of P   . In particular, if P   has integer vertices, then L P   is a polynomial. The evaluation of L P   at negative integers gives
L P ( − t ) = ( − 1 ) d L P ∘ ( t ) . (1.3)
The reciprocity law ( 1.3 ), conjectured and partially proved by Ehrhart, was in its full generality first proved by Macdonald [11] .
The second example of a valuation is v ( A ) : = solid angle of A at 0 ,   that is, the ratio of the volumes of A ∩ B   and B   , where B   is a sufficiently small d   -ball centered at the origin. Now V P ( t )   counts the integer points in t P   weighted by their solid angle in t P   .
Theorem  1.1 specializes to the following fundamental theorem due to Macdonald [11] . Note again that V P ( t ) = V − P ( t )   .
Corollary 1.3 (Macdonald). Suppose P   is a convex rational d   -polytope. Let A P ( t )   be the sum of the solid angles of t P   at all integer points. Then A P   is a quasi-polynomial of degree d   , whose period divides the least common multiple of the denominators of the vertices of P   . The evaluation of A P   at negative integers gives
A P ( − t ) = ( − 1 ) d A P ( t ) . (1.4)
In particular, if P   has integer vertices, then A P   is a polynomial which is either even or odd.
It is not hard to conclude the first half of Macdonald's Theorem from Ehrhart's Theorem (Corollary  1.2 ), since all integer points in a given face of P   have the same solid angle. The nontrivial part is equation ( 1.4 ).
A third example of a valuation is as follows. Fix a vector v ∈ R d   , and let v ( A ) : = { 1 if v ∈ A , 0 if v ∉ A .   This time V P ( t )   counts those integer points m   that after a small step in direction v   will be in t P   .
Note that, in particular, V P ( t ) ≠ V − P ( t )   . Theorem  1.1 specializes to the following statement. Let D ( P , v ) = { m ∈ Z d : m + ε v ∈ P for small enough ε > 0 }   and D P , v ( t ) = # D ( t P , v )   .
Corollary 1.4. Suppose P   is a convex rational d   -polytope and v   is a fixed vector in R d   . Then D P , v ( t )   is a quasi-polynomial of degree d   . The period of D P , v ( t )   divides the least common multiple of the denominators of the vertices of P   . In particular, if P   has integer vertices, then D P , v   is a polynomial. The evaluation of D P , v   at negative integers gives D P , v ( − t ) = ( − 1 ) d D − P ∘ , v ( t ) .  
We conceived Theorem  1.1 when we realized that Ehrhart's and Macdonald's theorems (Corollaries  1.2 and  1.3 ) follow very naturally from a theorem of Brion [4] , which in itself can be thought of as a consequence of a theorem due to Brianchon [3] and Gram [7] . To state these results, we need to introduce a few notions of polyhedral geometry in the next section. By no means do we claim that our approach is the easiest to Corollaries  1.2 and  1.3 ; our goal is merely to show the intimate connections of these results. Another such connection is given by Barvinok's result [1] , which uses Brion's Theorem to conclude that in fixed dimension, the generating function of an Ehrhart quasi-polynomial is polynomial-time computable.

2 Conic decompositions of polytopes

Given a d   -dimensional closed convex polyhedron P ⊂ R d   , the hyperplane H = { x ∈ R d : a ⋅ x = b }   is a supporting hyperplane of P   if P ∩ H ≠ ∅   and P   lies entirely on one side of H   , that is, P ⊆ { x ∈ R d : a ⋅ x ≤ b }   or P ⊆ { x ∈ R d : a ⋅ x ≥ b }   . A face of P   is a set of the form P ∩ H   , where H   is a supporting hyperplane of P   . Note that both P   itself and the empty set are faces of P   . The ( d − 1 )   -dimensional faces are called facets, the 1-dimensional faces edges, and the 0-dimensional faces vertices of P   .
For a vertex v   of P   , we define the affine vertex cone P v   as the shifted cone K P ( v ) + v   .
The integer generating function σ P   of a convex polyhedron P   is σ P ( z ) = σ P ( z 1 , . . . , z d ) = ∑ ( m 1 , . . . , m d ) ∈ P ∩ Z d z 1 m 1 ⋯ z d m d = ∑ m ∈ P ∩ Z d z m .   Here we view z   as a d   -dimensional complex variable.
A polyhedron is rational if each of its defining halfspaces can be described as { x ∈ R d : a ⋅ x ≤ b }   for some a ∈ Z d   and b ∈ Z   . If P   is a rational polyhedron then σ P ( z )   can be written as a rational function in z 1 , . . . , z d   (see, for example, [13] ). The following theorem can be derived, for example, from the Brianchon-Gram Theorem [3, 7] ; this is shown in [2] . The original proof of Brion is in [4] ; other, more elementary proofs can be found in [9, 10] .
Theorem 2.1 (Brion). For a convex rational polytope P ⊂ R d   , represent the generating functions of the vertex cones P v   as rational functions. Then ∑ v vertex of P σ P v ( z ) = σ P ( z ) .  
We need to extend Brion's Theorem to our more general setting, albeit for our purposes we only need a version for simplices. Our extension concerns the generating function for the valuation v P   , that is, β P ( z ) = ∑ m ∈ Z d v P ( m ) z m .   This is a rational function because v P ( m )   is constant on faces.
Theorem 2.2. Suppose S   is a rational simplex and v   is a valuation. Then, as rational functions, ∑ v vertex of S β S v ( z ) = β S ( z ) .  
In what follows, we adjust a valuation-based proof of Brion's Theorem given in [2] to our more general setting.
  • Proof of Theorem  2.2 . Suppose S   is a rational d   -simplex. The hyperplanes bounding S   divide R d   into regions. These regions are in one-to-one correspondence with the non-empty faces of S   , namely the closure of each region touches a unique maximal face of S   . Denote the region corresponding to the face ℱ   by ch ( ℱ )   . We orient the hyperplanes in such a way that they point towards S   . Thus ch ( S ) = S   is closed, the region corresponding to a vertex is open, and all the other regions are half open.
    Let W   be the union of regions corresponding to subfaces of a face ℱ ⊆ S   , that is, W = ⋃ G ⊆ ℱ ch ( G ) .   The set W   is a convex polyhedron that contains a line, except when ℱ   is a vertex. Because v   is a valuation, the generating function β W ( z )   satisfies, β W ( z ) = ∑ G ⊆ ℱ β ch ( G ) ( z )   Now unless ℱ   is a vertex, β W ( z )   is zero: There is an integer vector m   such that W + m = W   ; but 1 − z m   is not a zero divisor in the ring of rational functions in z   . In summary, we have ∑ G ⊆ ℱ β ch ( G ) ( z ) = { β ch ( ℱ ) ( z ) if ℱ is a vertex, 0 otherwise.   By inclusion-exclusion, β ch ( ℱ ) ( z ) = ( − 1 ) dim ℱ ∑ v vertex of ℱ β ch ( v ) ( z ) .   Again using that v   is a valuation, we have
    ∑ v vertex of S β P v ( z ) = ( d + 1 ) β S ( z ) + ∑ ℱ facet of S β ch ( ℱ ) ( z )
    = β S ( z ) + d ( − 1 ) d ∑ v vertex of S β ch ( v ) ( z ) + ∑ ℱ facet of S ( − 1 ) d − 1 ∑ v vertex of ℱ β ch ( ℱ ) ( z )
    = β S ( z ) + ∑ v vertex of S ( d ( − 1 ) d + d ( − 1 ) d − 1 ) β ch ( ℱ ) ( z )
    = β S ( z ) .
    This completes the proof. □
Theorem  2.2 can be extended to general convex polytopes using the valuation theorems of the next section. Since we do not need the general case to prove our main theorem, we leave the proof to the reader.
Theorem 2.3. Suppose P   is a convex rational polytope and v   is a valuation. As rational functions, we have the identity ∑ v vertex of P β P v ( z ) = β P ( z ) .  

3 Valuations on the triangulation lattice

A subset G   of a lattice ℒ   is a generating set if G   is closed under intersection and every element of ℒ   is the union of elements of G   . The following extension theorem is due to Groemer [8] and generalizes a valuation theorem for polyhedra due to Volland [14] .
Theorem 3.1 (Groemer). Suppose G   generates the lattice ℒ   , and v   is a function on G   that satisfies v ( n ⋃ i = 1 A i ) = ∑ 1 ≤ i ≤ n v ( A i ) − ∑ 1 ≤ i < j ≤ n v ( A i ∩ A j ) + ∑ 1 ≤ i < j < k ≤ n v ( A i ∩ A j ∩ A k ) − ⋯   whenever A 1 , A 2 , . . . , A n , A 1 ∪ A 2 ∪ ⋅ ⋅ ⋅ ∪ A n ∈ G   . Then v   extends uniquely to a valuation on ℒ   .
A (rational) polytope is the union of finitely many open or closed convex (rational) polytopes.
We apply Groemer's Theorem as follows. Given a (rational) polytope P   , fix a triangulation of P   into (rational) simplices. Let T P   denote the set of all unions of faces of these simplices. Hence T P   is a lattice, whose top element is P   . The generating set of T P   consists of the simplices of the triangulation and their faces, which are also simplices. The union of n   faces ℱ 1 , ℱ 2 , . . . , ℱ n   is again a face if only if one of the faces ℱ k   contains all the others. In this situation the condition of Groemer's Theorem, Theorem  3.1 , is directly satisfied. This means that we can define a function arbitrarily on the faces of the triangulation, and this function will extend uniquely to a valuation on T P   . Moreover, the values on elements of T P   are given by an iterated application of the inclusion-exclusion formula ( 1.1 ). In particular:
Corollary 3.2. Two valuations that agree on all (rational) simplices agree on all (rational) polytopes.
This result is useful to us, since V P   is a valuation as a function of P   .

4 Proof of the reciprocity theorem

  • Proof of Theorem  1.1 . Because of Corollary  3.2 , it is enough to prove Theorem  1.1 for simplices.
    Without loss of generality we may assume that the simplex S   has the same dimension as the space it lies in. Hence suppose S   is a rational d   -simplex in R d   , whose vertices have coordinates with denominator p   . We will prove the reciprocity identity ( 1.2 ) for the function V S ( r + p t )   for a fixed r   .
    The fact that V S ( r + p t )   is a polynomial in t   will be recovered in passing.
    By Theorem  2.2 , V S ( r + p t ) = ∑ m ∈ ( r + p t ) S ∩ Z d v ( r + p t ) S ( m ) = lim z → 1 β ( r + p t ) S ( z ) = lim z → 1 ∑ v vertex of S β ( r + p t ) S v ( z ) ,   so we need to look at the integer generating functions for ( r + p t )   -dilates of cones more closely.
    For a vertex v   of S   , suppose S v = v + ∑ k = 1 d R ≥ 0 w k   for some integer vectors w 1 , . . . , w d   ; then ( r + p t ) S v = ( r + p t ) v + ∑ k = 1 d R ≥ 0 w k = t p v + ( r v + ∑ k = 1 d R ≥ 0 w k ) .   Note that p v   is an integer vector. Now let R v ( z )   denote the rational function equal to the integer generating function of r v + ∑ k = 1 d R ≥ 0 w k   ; because this cone is simple, R v ( z )   is easy to write down:
    let Π ̲ v = r v + ∑ k = 1 d [ 0 , 1 ) w k   , then R v ( z ) = β Π ̲ v ( z ) ∏ k = 1 d ( 1 − z w k ) ,   whence β ( r + p t ) S v ( z ) = z t p v R v ( z ) = z t p v β Π ̲ v ( z ) ∏ k = 1 d ( 1 − z w k ) .   Note that we are using the fact that v   is a valuation. For the open cone S v ∘   we obtain, completely analogously, β ( r + p t ) S v ∘ ( z ) = z t p v β Π ¯ v ( z ) ∏ k = 1 d ( 1 − z w k ) ,   where Π ¯ v = r v + ∑ k = 1 d ( 0 , 1 ] w k   .
    From the form of these generating functions, we can immediately conclude that V S ( r + p t )   is a polynomial in t   which implies that V S   is a quasi-polynomial: We know that the sum of the generating functions of all vertex cones is a polynomial in the variables of z   , hence the singularities of the rational functions cancel. To compute V S ( r + p t ) = lim z → 1 ∑ v vertex of S z t p v R v ( z ) ,   we can write all the rational functions on the right-hand side over one denominator and use L'Hospital's Rule to compute the limit. The result is a polynomial in t   , as we simply evaluate z   at 1 after using L'Hospital's Rule the correct number of times.
    To prove the reciprocity law, we relate the geometry of Π ̲ v   with the geometry of Π ¯ v   . This geometry depends on r   ; let us include this dependency in our notation. Recall that Π ̲ v = Π ̲ v ( r ) = r v + ∑ k = 1 d [ 0 , 1 ) w k   and Π ¯ v = Π ¯ v ( r ) = r v + ∑ k = 1 d ( 0 , 1 ] w k .   The two half-open parallelepipeds relate as
    Π ¯ v ( r ) = − Π ̲ v ( − r ) + ∑ k = 1 d w k , (4.1)
    as illustrated in Figure  1 . Using the notation z − 1 = ( z 1 − 1 , . . . , z d − 1 )   , we have β − Π ̲ v ( − r ) ( z ) = β Π ̲ v ( − r ) ( z − 1 ) ,   which allows us to rephrase ( 4.1 ) as β Π ¯ v ( r ) ( z ) = β Π ̲ v ( − r ) ( z − 1 ) d ∏ k = 1 z w k .  

    Figure 1 . Top: Π ¯ v ( r )   Bottom: Π ̲ v ( − r ) → − Π ̲ v ( − r ) → − Π ̲ v ( − r ) + ∑ w k  

    Now by the extended Brion-Theorem for simplices (Theorem  2.2 ) and the rational generating functions for simple cones,
    V − S ∘ ( r + p t ) = lim z → 1 β − ( r + p t ) S ∘ ( z )
    = lim z → 1 β ( r + p t ) S ∘ ( z − 1 )
    = lim z → 1 ∑ v vertex of S z − t p v β Π ¯ v ( r ) ( z − 1 ) ∏ k = 1 d ( 1 − z − w k )
    = lim z → 1 ∑ v vertex of S z − t p v β Π ̲ v ( − r ) ( z ) ∏ k = 1 d z − w k ∏ k = 1 d ( 1 − z − w k )
    = lim z → 1 ∑ v vertex of S z − t p v β Π ̲ v ( − r ) ( z ) ∏ k = 1 d ( z w k − 1 )
    = ( − 1 ) d V S ( − r − p t )
    □

5 Concluding remarks

There exists a slightly more general version of our main Theorem  1.1 . Namely, instead of P   one can take P ∘   together with some facets of P   . Then P ∘   on the other side of the reciprocity identity gets replaced by P ∘   together with the remaining facets. This parallels a theorem of Stanley which generalizes Ehrhart-Macdonald Reciprocity [12] .
There is also a theorem analogous to Brion's for polyhedra (not just polytopes). Our proof goes through in this case once one allows unbounded simplices, which result when one moves a certain face of a simplex to infinity. (Any polyhedron can be triangulated into bounded and unbounded simplices.) References

  1. A. I. Barvinok, A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed, Math. Oper. Res. 19 (1994), 769–779.
  2. M. Beck, S. Robins, F. Sottile, and J. Weitsman, Conic decompositions of polytopes, Preprint (2004).
  3. C. J. Brianchon, Théorème nouveau sur les polyèdres, J. Ecole (Royale) Polytechnique 15 (1837), 317–319.
  4. M. Brion, Points entiers dans les polyèdres convexes, Ann. Sci. École Norm. Sup. (4) 21 (1988), no. 4, 653–663.
  5. E. Ehrhart, Sur les polyèdres rationnels homothétiques à n   dimensions, C. R. Acad. Sci. Paris 254 (1962), 616–618.
  6. , Sur un problème de géométrie diophantienne linéaire. I. Polyèdres et réseaux, J. Reine Angew. Math. 226 (1967), 1–29.
  7. J. P. Gram, Om rumvinklerne i et polyeder, Tidsskrift for Math. (Copenhagen) 4 (1874), no. 3, 161–163.
  8. H. Groemer, On the extension of additive functionals on classes of convex sets, Pacific J. Math. 75 (1978), no. 2, 397–410.
  9. M.-N. Ishida, Polyhedral Laurent series and Brion's equalities, Internat. J. Math. 1 (1990), no. 3, 251–265.
  10. J. Lawrence, Rational-function-valued valuations on polyhedra, Discrete and computational geometry (New Brunswick, NJ, 1989/1990), Amer. Math. Soc., Providence, RI, 1991, pp. 199–208.
  11. I. G. Macdonald, Polynomials associated with finite cell-complexes, J. London Math. Soc. (2) 4 (1971), 181–192.
  12. R. P. Stanley, Combinatorial reciprocity theorems, Advances in Math. 14 (1974), 194–253.
  13. , Enumerative Combinatorics, 2nd ed., vol. I, Cambridge University Press, 1997.
  14. W. Volland, Ein Fortsetzungssatz für additive Eipolyederfunktionale im euklidischen Raum, Arch. Math. 8 (1957), 144–149.

Department of Mathematics, San Francisco State University, San Francisco, CA 94132, USA E-mail address : beck@math.sfsu.edu URL: http://math.sfsu.edu/beck Department of Mathematics, University of Kentucky, Lexington, KY 40506-0027, USA E-mail address : jrge@ms.uky.edu URL: http://www.ms.uky.edu/~jrge/