You are here

Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra

Springer Verlag
Number of Pages: 

What if we lived in a country where, instead of the monetary system we currently use, there were only two types of coins, one of which was a 4-cent coin and one of which was an 11-cent coin? Clearly there would be some amounts that one would not be able to make using only these coins — there is no way to get 7 cents, for example. Or 13 cents. On the other hand, it is easy to see that we can make 15 cents, and with a little effort one can see how to use these two coins to form 52 cents and 115 cents.

The question of which values can be reached using these coins is an example of the Frobenius Coin Exchange Problem, which asks what integers can be written as m1a1 + m2a2+...+ mdad, where {a1,...,ad} is a fixed set of positive integers and the mi range over all non-negative integers. This problem, which is very elementary to state, is quite non-trivial and, while it is an easy elementary number theory result that all but a finite number of integers can be represented in this way (as long as the coin values are not all multiples of any given number), in the case where d>2 it is unknown even what the largest non-representable number is. There are a number of partial results known, and the study of this problem has led to quite a bit of interesting mathematics. The problem also serves as a motivating example for the material in Computing the Continuous Discretely, a book by Matthias Beck and Sinai Robins which has recently been published in Springer's 'Undergraduate Texts in Mathematics Series.'

Beck and Robins begin by interpreting the Frobenius Coin Exchange Problem in terms of combinatorics and number theory, as well as geometry, where it can be formulated in terms of the number of lattice points inside of certain polyhedra. The authors define the discrete volume of a polyhedron as the number of lattice points it contains, and the heart of their book is a deep discussion of the relationship between the discrete volume and the normal (or continuous) volume of polyhedra and polytopes.

As they prove various results about these objects they introduce the reader to a wide range of topics including generating functions, Fourier transforms, and Dedekind sums. Some of the topics that get touched on include the enumeration of magic squares, a discrete version of Green's Theorem, and Euler-Maclaurin summation formulae. If you are not familiar with these topics, then you owe it to yourself to pick up a copy of Computing the Continuous Discretely to read about a number of interesting problems in geometry, number theory, and combinatorics, all of which are interconnected and all of which can be built up pretty quickly from very elementary techniques. Even people who are familiar with the material would almost certainly learn something from the clear and engaging exposition that these two authors use.

The book assumes very few pre-requisites, using only elementary techniques in the early chapters and requiring not much more than a little complex analysis even in the late chapters. It contains a large number of exercises, many of which have hints, and some of which the authors use to develop and work out the details of the material. Each chapter also ends with a series of relevant open problems and historical notes which are often very interesting. One can easily imagine using the book that Beck and Robins have written for an undergraduate course or an independent study with students, although it is also full of mathematics that is self-contained and worth reading on its own.

Darren Glass is an assistant professor of mathematics at Gettysburg College. He can be reached at

Date Received: 
Saturday, December 30, 2006
Include In BLL Rating: 
Mathias Beck and Sinai Robins
Undergraduate Texts in Mathematics
Publication Date: 
Darren Glass
BLL Rating: 

 Preface.- The Coin-Exchange Problem of Frobenius.- A Gallery of Discrete Volumes.- Counting Lattice Points in Polytopes: The Ehrhart Theory.- Reciprocity.- Face Numbers and the Dehn-Sommerville Relations in Ehrhartian Terms.- Magic Squares.- Finite Fourier Analysis.- Dedekind Sums.- The Decomposition of a Polytope into Its Cones.- Euler-MacLaurin Summation in Rd.- Solid Angles.- A Discrete Version of Green's Theorem Using Elliptic Functions.- Appendix A: Triangulations of Polytopes.- Appendix B: Hints for Selected Exercises.- References.- Index.- List of Symbols.-

Publish Book: 
Modify Date: 
Thursday, December 30, 2010