This post continues my series on favorite theorems of the 21st century, choosing one theorem for each year and for each of the seven major subject categories. For an overview of the categories and of my previous selections, see this earlier post. My choice for 2002 in Algorithms and Complexity is the theorem of Barvinok and Woods giving an efficient algorithm, for every fixed number of coin denominations, to compute the total number of unattainable amounts in the Frobenius coin problem. The theorem was proved in 2002 and published in 2003 (Barvinok and Woods 2003).
Given positive coprime integers , let Thus is the set of positive integers that cannot be paid using coins of denominations , when any non-negative number of coins of each denomination is allowed. The assumption that the are coprime is essential: it guarantees that all sufficiently large positive integers are representable, and hence that the set is finite.
The classical Frobenius coin problem asks for the largest element of this finite set. For there is the famous closed formula but for larger the problem becomes much subtler. If is allowed to vary as part of the input, the Frobenius problem is computationally hard; in particular, it is known to be NP-hard. On the other hand, Kannan (Kannan 1992) proved in 1992 that for every fixed the Frobenius number can be computed in polynomial time. This is a typical and beautiful phenomenon in the geometry of numbers and integer programming: a problem may be intractable in variable dimension but become efficiently solvable once the dimension is fixed.
Barvinok and Woods pushed this point of view further. Instead of asking only for the largest exceptional integer, they asked for the total number of exceptional integers. In other words, they considered the size This quantity is sometimes called the genus of the numerical semigroup generated by . It measures the full extent of the failure of representability, not just the final failure before all larger integers become attainable.
The striking feature of Theorem is not only that the answer can be computed efficiently, but also the method by which it is computed. The proof is based on the theory of short rational generating functions, a technique developed by Barvinok for counting lattice points in polyhedra of fixed dimension. Rather than listing the elements of a set one by one, the method encodes the set as a compact rational function.
For a finite set of positive integers, define its generating function by If we could explicitly list all elements of , then the polynomial would immediately give the desired number, since The difficulty is that the set may be very large, so writing down this polynomial term by term may be hopelessly inefficient.
The key insight of Barvinok and Woods is that, when is fixed, one can compute a short expression for the relevant generating function. Such an expression is typically a sum of rational functions of the form where the number of summands and the size of the data appearing in them are polynomially bounded. This compact representation can encode an enormous finite or infinite set without enumerating its elements.
The representable positive integers are generated by the semigroup The formal generating function of this semigroup is closely related to although this expression counts representations rather than represented integers, since the same integer may have many different representations. The work of Barvinok and Woods supplies the algorithmic machinery needed to pass from such representation-counting data to a short generating function for the actual set of attainable integers, and hence also for its finite complement among the positive integers.
If denotes the set of positive representable integers, then because every positive integer is either unattainable or attainable. Thus a short rational expression for one of these two generating functions gives a short rational expression for the other. Since is finite, its generating function is regular at , and the desired number is obtained by taking the limit Although the rational expression may have apparent poles at , these singularities cancel, and the limit can be evaluated efficiently.
What makes this theorem especially elegant is the way it transforms a problem about coins into a problem about the geometry and algebra of generating functions. The unattainable integers are not found by a direct search through a long interval, nor by computing the Frobenius number first and checking every smaller integer. Instead, the whole exceptional set is compressed into a symbolic object of polynomial size, and the answer is extracted from that object analytically.