{'fraction_non_alphanumeric': 0.0454093723721428, 'fraction_numerical': 0.00833269627704304, 'mean_word_length': 3.791941391941392, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Ehrhart-Macdonald reciprocity extended

For a convex polytope P with rational vertices, we count the number of integer points in integral dilates of P and its interior. The Ehrhart-Macdonald reciprocity law gives an intimate relation between these two counting functions. A similar counting function and reciprocity law exists for the sum of all solid angles at integer points in dilates of P. We derive a unifying generalization of these reciprocity theorems which follows in a natural way from Brion's Theorem on conic decompositions of polytopes.


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 tP and the sum of the solid angles in tP, 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 In other words, K P (m) equals • the intersection of the halfspaces defining a face F if m is on the face F of P, shifted to the origin.
A lattice of sets is a collection L of sets, partially ordered by set inclusion, such that for any two sets A, B ∈ L A ∩ B ∈ L and A ∪ B ∈ L . A function v on L with values in some abelian group is a valuation (often called a finitely additive measure) if for any A, B ∈ L We consider the lattice L 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 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 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 Our motivation for studying the function V P (t) comes from special cases of valuations. The first example is In this case V P (t) counts the number of integer points in tP 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) := # tP ∩ 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 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 tP weighted by their solid angle in tP. Theorem 1.1 specializes to the following fundamental theorem due to Macdonald [11]. Note again that V P (t) = V −P (t).
be the sum of the solid angles of tP 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 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( This time V P (t) counts those integer points m that after a small step in direction v will be in tP.
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(tP, 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 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.

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, 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 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 σ Pv (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, This is a rational function because v P (m) is constant on faces. In what follows, we adjust a valuation-based proof of Brion's Theorem given in [2] to our more general setting. Let W be the union of regions corresponding to subfaces of a face F ⊆ S, that is, The set W is a convex polyhedron that contains a line, except when F is a vertex. Because v is a valuation, the generating function β W (z) satisfies, Now unless F 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 By inclusion-exclusion, 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 β Pv (z) = β P (z) .

Valuations on the triangulation lattice
A subset G of a lattice L is a generating set if G is closed under intersection and every element of L 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 L, and v is a function on G that satisfies Then v extends uniquely to a valuation on L.
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 F 1 , F 2 , . . . , F n is again a face if only if one of the faces F 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 inclusionexclusion 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.

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 + pt) for a fixed r. The fact that V S (r + pt) is a polynomial in t will be recovered in passing.
By Theorem 2.2, so we need to look at the integer generating functions for (r + pt)-dilates of cones more closely. For a vertex v of S, suppose S v = v + d k=1 R ≥0 w k for some integer vectors w 1 , . . . , w d ; then Note that pv is an integer vector. Now let R v (z) denote the rational function equal to the integer generating function of rv + d k=1 R ≥0 w k ; because this cone is simple, R v (z) is easy to write down: .
Note that we are using the fact that v is a valuation. For the open cone S • v we obtain, completely analogously, , From the form of these generating functions, we can immediately conclude that V S (r + pt) 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 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 The two half-open parallelepipeds relate as as illustrated in Figure 1. Using the notation z −1 = z −1 1 , . . . , z −1 d , we have which allows us to rephrase (4.1) as

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.)