Integer points in polyhedra (Q942862): Difference between revisions

This book grew out of lecture notes for a graduate course that the author taught at the ETH Zürich and the University of Michigan. It constitutes a self-contained overview of some aspects of a rapidly developing subject by one of the leading experts in the field. Let \(P \subset \mathbb R^d\) be a polytope (bounded polyhedron) and \(\mathbb Z^d\) the standard integer lattice in \(\mathbb R^d\). The main question addressed in this book is how to count integer lattice points in a polytope, in other words how to compute the quantity \(|P \cap \mathbb Z^d|\)? The first observation the author makes is that \(|P \cap \mathbb Z^d|\) is a valuation, meaning that whenever \(P = P_1 \cup P_2\) and \(Q = P_1 \cap P_2\), we have \[ |P \cap \mathbb Z^d| = |P_1 \cap \mathbb Z^d| + |P_2 \cap \mathbb Z^d| - |Q \cap \mathbb Z^d|. \] Therefore, to count integer lattice points in a polytope, it makes sense to decompose it into simpler pieces. Hence the author's starting point is a detailed investigation of the structure of polyhedra. This includes behavior of polyhedra under linear transformations, containment of lines and rays, polarity, tangent cones, decompositions modulo polyhedra with lines, and related topics. The author introduces the algebra of polyhedra, which allows him to formulate some geometric properties in a purely algebraic language. In particular, he gives a natural general definition of Euler characteristic as a valuation, and interprets action of a linear transformation on polyhedra in terms of the action of its associated valuation on the indicator functions, which are the elements of the algebra. The concept of a valuation is overall an important tool in the author's exposition, which allows him to state results in a fairly general setting. For instance, he extends the notion of volume to unbounded polyhedra by constructing an \textit{exponential valuation} on the algebra of polyhedra, which specializes to volume in the bounded case. Equipped with this machinery, the author can now compute volumes. Next he introduces the setting of lattices, their bases and fundamental domains, and develops basic results from the classical geometry of numbers. These include Minkowski's convex body theorem, basics of reduction theory, and the LLL algorithm. In the later parts of the book, the machinery of exponential sums and generating functions is used. The author introduces a \textit{counting valuation} on the space of rational functions on \(\mathbb C^d\) and uses it to state Brion's theorem. Toward the end of the book this counting valuation is related to the exponential valuation with the goal of expressing the number of integer lattice points in a rational polytope in terms of the volumes of its faces and a certain valuation on the tangent cones at those faces. This results in a nice exposition of Berline-Vergne recent ``local'' formula. Additional topics covered in the book include Ehrhart's polynomial, unimodular polytopes, decompositions for rational cones (including applications of continued fractions), and related results. The overall scope of the topics covered is fairly wide, ranging from classical results to some very recent advances. The book is well written, contains a large number of nice illustrations which help to develop reader's geometric intuition, and includes numerous exercises of varying degree of difficulty. The author also includes some useful references. This text requires a rather minimal background in algebra and analysis, and is likely to become a standard reference for graduate students and researchers alike.