Solving Lattice Point Problems Using Rational Generating Functions

Kevin Woods
Oberlin College
Mathematics

As an example, consider the following problem. Given positive integers a1, . . . , ad that are relatively prime, let S be the set of integers that can be written as a nonnegative integer combination of these ai. We can think of the ai as denominations of postage stamps and S as the postal rates that can be paid exactly using these denominations. What can we say about the structure of this set, S? What is the largest integer not in S (called the Frobenius number)? How many positive integers are not in S? We attack these problems using the generating function fS(x), defined to be the sum, over all elements s of S, of the monomials xs. We will build up the general theory of computing generating functions—for this and other problems—and then use these generating functions to answer questions we’re interested in. We will approach these problems from an algorithmic perspective: what can we do in polynomial time?