Catálogo de publicaciones - libros

Thus far we have often been concerned with the difference between the discrete volume of a polytope and its continuous volume. In other words, the quantity

A unifying theme of this book is the study of the number of integer points in polytopes, where the polytopes lives in a real Euclidean space ℝ. The integer points ℤ form a lattice in ℝ, and we often call the integer points . This chapter carries us through concrete instances of lattice-point enumeration in various integral and rational polytopes. There is a tremendous amount of research taking place along these lines, even as the reader is looking at these pages.

Given the profusion of examples that gave rise to the polynomial behavior of the integer-point counting function () for special polytopes , we now ask whether there is a general structure theorem. As the ideas unfold, the reader is invited to look back at Chapters 1 and 2 as appetizers and indeed as special cases of the theorems developed below.

The natural generalization of a two-dimensional angle to higher dimensions is called a . Given a pointed cone к ⊂ ℝ, the solid angle at its apex is the proportion of space that the cone к occupies. In slightly different words, if we pick a point х ∊ ℝ “at random,” then the probability that х ∊ к is precisely the solid angle at the apex of к. Yet another view of solid angles is that they are in fact volumes of spherical polytopes: the region of intersection of a cone with a sphere. There is a theory here that parallels the Ehrhart theory of Chapters 3 and 4, but which has some genuinely new ideas.

Our goal in this chapter is two fold, or rather, there is one goal in two different guises. The first one is to prove a set of fascinating identities, which give linear relations among the face numbers . They are called , in honor of their discoverers Max Wilhelm Dehn (1878–1952) and Duncan MacLaren Young Sommerville (1879–1934). Our second goal is to unify the Dehn—Sommerville relations (Theorem 5.1 below) with Ehrhart—Macdonald reciprocity (Theorem 4.1).

Equipped with a solid base of theoretical results, we are now ready to return to computations. We use Ehrhart theory to assist us in enumerating .

We now consider the vector space of all complex-valued periodic functions on the integers with period . It turns out that every such function () on the integers can be written as a polynomial in the root of unity ξ := . Such a representation for () is called a . Here we develop the finite Fourier theory using rational functions and their partial fraction decomposition. We then define the Fourier transform and the convolution of finite Fourier series, and show how one can use these ideas to prove identities on trigonometric functions, as well as find connections to the classical Dedekind sums.

We’ve encountered Dedekind sums in our study of finite Fourier analysis and we became intimately acquainted with their siblings in our study of the coin-exchange problem in Chapter 1. They have one shortcoming, however (which we'll remove): the definition of () requires us to sum over terms, which is rather slow when = 2, for example. Luckily, there is a magical for the Dedekind sum () that allows us to compute it in roughly log () = 100 steps. This is the kind of magic that saves the day when we try to enumerate lattice points in integral polytopes of dimensions ≤4. There is an ongoing effort to extend these ideas to higher dimensions, but there is much room for improvement. In this chapter we focus on the computational-complexity issues that arise when we try to compute Dedekind sums explicitely.

In this chapter, we return to integer-point transforms of rational cones and polytopes and connect them in a magical way that was first discovered by Michel Brion. The power of Brion’s theorem has been applied to various domains, such as Barvinok’s algorithm in integer linear programming, and to higher-dimensional Euler-Maclaurin summation formulas, which we study in Chapter 10.

Thus far we have often been concerned with the difference between the discrete volume of a polytope and its continuous volume. In other words, the quantity