Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1154.52009
Barvinok, Alexander
Integer points in polyhedra. (English)
[B] Zurich Lectures in Advanced Mathematics. Zürich: European Mathematical Society (EMS). viii, 190~p. EUR~34.00 (2008). ISBN 978-3-03719-052-4

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 \Bbb R^d$ be a polytope (bounded polyhedron) and $\Bbb Z^d$ the standard integer lattice in $\Bbb 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 \Bbb Z^d|$? The first observation the author makes is that $|P \cap \Bbb 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 \Bbb Z^d| = |P_1 \cap \Bbb Z^d| + |P_2 \cap \Bbb Z^d| - |Q \cap \Bbb 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 poylhedra 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 {\it 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 {\it counting valuation} on the space of rational functions on $\Bbb 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 Erhart'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.
[Lenny Fukshansky (Claremont)]

MSC 2000:: *52B20 Lattice polytopes (convex geometry)
52-02 Research monographs (convex and discrete geometry)
52C07 Lattices and convex bodies in n dimensions
05A15 Combinatorial enumeration problems
52B45 Dissections and valuations
52B55 Computational aspects related to geometric convexity
52C45 Combinatorial complexity of geometric structures

Keywords: integer lattice points; exponential valuation; counting valuation

Cited in: Zbl 1149.91028

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering

	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.
	Elementary number theory. Primes, congruences, and secrets.

Advanced Search

Zentralblatt MATH Berlin [Germany]