Ehrhart–Macdonald reciprocity

Ehrhart–Macdonald reciprocity
Name	Ehrhart–Macdonald reciprocity
Field	Mathematics
Introduced	1960s
Author	Eugène Ehrhart; I. G. Macdonald

Ehrhart–Macdonald reciprocity. Ehrhart–Macdonald reciprocity is a theorem in Mathematics that relates counting lattice points in dilations of a rational convex polytope to counting interior lattice points in complementary dilations. The result connects areas of Combinatorics, Convex geometry, Integer programming, Enumerative geometry, and Algebraic geometry. It has consequences for the study of Pick's theorem, Euler characteristic, and generating functions appearing in the work of Brion, Barvinok, and Stanley.

Introduction

Ehrhart–Macdonald reciprocity concerns a rational convex polytope P in Euclidean space studied by Eugène Ehrhart and later extended by I. G. Macdonald. The theorem involves the Ehrhart polynomial (or Ehrhart quasipolynomial) associated to P, which counts lattice points in integer dilates kP for k in the nonnegative integers, and relates it to the count of lattice points in the interior of kP. The statement unifies ideas from Geometry of numbers, Combinatorial commutative algebra, Toric varieties, and the theory of Generating functions developed in works by Noam Elkies, Mikhail Gromov, and Paul Monsky.

Statement

Let P be a rational convex polytope in R^d with vertices in the rational lattice and let L_P(k) denote the number of lattice points in the k-fold dilation kP for integer k ≥ 0. Then L_P(k) is given for k ∈ Z≥0 by an Ehrhart quasipolynomial. The reciprocity theorem asserts that for positive integers k the number of lattice points in the interior of kP equals (−1)^d L_P(−k). This relates evaluations at negative integers of the Ehrhart quasipolynomial to interior counts, echoing classical reciprocity phenomena such as those for the Riemann–Roch theorem on Algebraic curves and reciprocity laws in Class field theory.

Proofs

Proofs of Ehrhart–Macdonald reciprocity proceed by diverse methods, each bridging different mathematical subjects. A combinatorial proof uses inclusion–exclusion and Ehrhart series represented as rational generating functions following techniques by Richard Stanley and I. G. Macdonald, while analytic proofs employ meromorphic continuation of lattice-point generating functions similar to arguments by Hadamard and Poisson summation used in Geometry of numbers. Geometric proofs translate the problem into properties of cones and use Brion's theorem about lattice-point enumeration in polytopes attributed to Michel Brion. Algebraic proofs leverage Hilbert series of graded rings associated to semigroup algebras studied by David Eisenbud and Bernd Sturmfels, relating Ehrhart series to Hilbert series reciprocity phenomena established in Commutative algebra.

Examples and applications

Elementary examples include integral simplices and cubes where Ehrhart polynomials reduce to binomial expressions; these connect to Pick's theorem for lattice polygons and to counting integer points in standard simplices used by George Pólya and G. H. Hardy. Applications appear in optimization via Integer programming where lattice counts give bounds in cutting-plane methods developed by Ralph Gomory, and in Toric varieties where lattice-point enumeration corresponds to dimensions of graded pieces as in the work of Victor V. Batyrev and David Cox. In Enumerative combinatorics the reciprocity translates combinatorial reciprocity theorems for chromatic polynomials studied by Birkhoff and Whitney into geometric lattice-point statements, while in Number theory connections arise with counting representations by quadratic forms explored by Carl Friedrich Gauss and Srinivasa Ramanujan.

Generalizations and related results

Generalizations include reciprocity for rational cones and rational polytopes with interior lattice-point enumerators treated by Alexander Barvinok and Matthias Beck. Relations to the Euler–Maclaurin formula and local Euler–Maclaurin expansions connect to work by Victor Khovanskii and Akihiro Gyoja, while the connection with Hilbert polynomials and Serre duality echoes results by Jean-Pierre Serre and Grothendieck in Algebraic geometry. Macdonald-type reciprocity extends to inside-out polytopes analyzed by Thomas Zaslavsky and to flow and tension polynomials on graphs studied by W. T. Tutte and Neil Robertson.

History and attribution

The counting function now known as the Ehrhart polynomial originated in enumerative investigations by Eugène Ehrhart in the 1960s; later work by I. G. Macdonald formulated and proved the reciprocity relation linking negative evaluations to interior counts. Subsequent contributions and proofs were developed by many authors including Richard Stanley, Michel Brion, Alexander Barvinok, Bernd Sturmfels, Matthias Beck, and David Eisenbud, who brought techniques from Commutative algebra, Convex geometry, and Algebraic topology to bear on the subject. The theorem stands at an intersection of developments across Combinatorics, Number theory, and Algebraic geometry and continues to inform research in related topics such as Toric geometry and computational lattice-point enumeration.

Category:Theorems in combinatorics