Residue formulae for vector partitions and Euler-Maclaurin sums.

Lattice points in specified regions (11P21) (n)-dimensional polytopes (52B11) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35)

Abstract: Given a finite set of vectors spanning a lattice and lying in a halfspace of a real vector space, to each vector

a

in this vector space one can associate a polytope consisting of nonnegative linear combinations of the vectors in the set which sum up to

a

. This polytope is called the partition polytope of

a

. If

a

is integral, this polytope contains a finite set of lattice points corresponding to nonnegative integral linear combinations. The partition polytope associated to an integral

a

is a rational convex polytope, and any rational convex polytope can be realized canonically as a partition polytope. We consider the problem of counting the number of lattice points in partition polytopes, or, more generally, computing sums of values of exponential-polynomial functions on the lattice points in such polytopes. We give explicit formulae for these quantities using a notion of multi-dimensional residue due to Jeffrey-Kirwan. We show, in particular, that the dependence of these quantities on

a

is exponential-polynomial on "large neighborhoods" of chambers. Our method relies on a theorem of separation of variables for the generating function, or, more generally, for periodic meromorphic functions with poles on an arrangement of affine hyperplanes.

Review text

Let \(V\) be a real vector space of dimension \(n\) and \(\Gamma\subset V\) a lattice of full rank. Let \(\Phi =(\beta_1, \ldots, \beta_N)\) be a sequence of elements of the dual lattice \(\Gamma^*\), all lying to one side of some hyperplane. Let \(\lambda \in \Gamma^*\) lie in the convex cone \(C(\Phi)\) generated by \(\Phi.\) The set of non-negative real solutions to the equation \(\sum_{i=1}^N x_i\beta_i = \lambda\) is a rational convex polytope \(\Pi_\Phi(\lambda)\) in \({\mathbb R}^N\); the number \(i_\Phi(\lambda)\) of non-negative integer solutions defines the vector partition function \(\lambda \mapsto i_\Phi(\lambda)\) associated with \(\Phi.\) More generally, an Euler-MacLaurin sum is the sum \(S(f,\Phi,\lambda)\) of the values of an ``exponential-polynomial function \(f: {\mathbb R}^N \to {\mathbb C}\) at the integer points of \(\Pi_\Phi(\lambda)\). An exponential-polynomial function is a linear combination of exponentials \(e^{\langle y,x\rangle}\), \(y\in V^*\), with polynomial coefficients. Such a function is periodic-polynomial if the exponentials which appear satisfy \(M y \in 2\pi i{\mathbb Z}^N\) for some integer \(M\). Independent subsets of \(\Phi\) of cardinality less than \(n\) generate simplicial cones in \(C(\Phi);\) the complement is a union of open conic chambers. For each such chamber \({\mathfrak c}\), the restriction of \(S(f,\Phi,\lambda)\) to \(\overline{\mathfrak c}\) is given by a exponential-polynomial function. In the paper under review, the authors derive a residue formula for this function which holds throughout an collared neighborhood of \(\overline{\mathfrak c}\). To be more precise, let \(\square\) denote the zonotope determined by \(\Phi\): \(\square=\sum_{i=1}^N [0,1]\beta_i.\) Then, for each conic chamber \(\mathfrak c\) in \(C(\Phi)\), there is a periodic-polynomial \(i({\mathfrak c},\lambda)\) such that \(i_\Phi(\lambda)=i({\mathfrak c},\lambda)\) at all integer lattice points in the ``Minkowsi difference \({\mathfrak c} - \square = \{\xi-\mu \mid \xi\in {\mathfrak c}, \mu \in \square\}.\) Similarly, the Euler-MacLaurin sum \(S(f,\Phi,\lambda)\) is given by an explicit exponential-polynomial \(P(f,{\mathfrak c},\Phi)\) on \({\mathfrak c} - \square.\) This set contains \(\overline{\mathfrak c}\), and is often much larger. The fact that these sets overlap implies some divisibility properties of the difference \(i({\mathfrak c},\lambda)-i({\mathfrak c}',\lambda)\) for neighboring chambers \({\mathfrak c}, {\mathfrak c}'\). These results follow from a general residue formula for the coefficient of \(e^{\lambda}\) in the expansion of more general rational functions \(F(z)\) with poles along arrangements of hyperplanes. These functions \(F(z)\) take the form \[ \frac{\sum_\xi c_\xi e^{\langle \xi,z\rangle}} {\prod_{i=1}^R (1-u_ie^{\langle \alpha_i,z \rangle})}, \] where \(\xi,\alpha_i \in \Gamma^*.\) A partial fraction expansion due to the first author expresses such a function as a sum of similar functions for which the distinct \(\alpha_i\) that appear in the product are linearly independent. This allows to prove that the desired coefficient is equal to the Jeffery-Kirwan residue corresponding to the given chamber, evaluated on the sum of residues of \(e^{\langle \lambda,z-p \rangle}F(p-z)\) over representative poles \(p\) (modulo \(2\pi i \Gamma \)) of \(F(z),\) by generalizing a more straightforward calculation for the one-dimensional case. This general formula is then applied to the function \(\prod_{i=1}^N (1-e^{\beta_i})^{-1}=\sum_{\lambda} i_\Phi(\lambda) e^\lambda\) to obtain an explicit formula for the periodic-polynomial \(i({\mathfrak c},\lambda)\). Sums of exponentials over partition polytopes, and general Euler-MacLaurin sums are dealt with similarly. The authors show how Minkowski sums of polytopes can be expressed as partition polytopes, so that their main result may be applied to give explicit formulae for Ehrhart periodic-polynomials and enumeration of lattice points in general Minkowski sums. The paper includes an appendix with several illustrative examples.

Recommendations

Cites work

Cited in

(34)

This page was built for publication: Residue formulae for vector partitions and Euler-Maclaurin sums.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1398306)