The complexity of generating functions for integer points in polyhedra and beyond

Abstract

Motivated by the formula for the sum of the geometric series, we consider various classes of sets S ⊂ ℤ_d_ of integer points for which an a priori “long” Laurent series or polynomial Σ_m_∈_S_ xm can be written as a “short” rational function f(S; x). Examples include the sets of integer points in rational polyhedra, integer semigroups, and Hilbert bases of rational cones, among others. We discuss applications to efficient counting and optimization and open questions.

This enables to show that a priori different discrete models define the same curves in the scaling limit and exhibit some surprising symmetries. It gives also a way to tie links between these concrete measures on curves and conformal field theory. Important roles in this theory are played by Brownian loops and by the Schramm–Loewner Evolutions (SLE).

Most of the results described in this paper were derived in joint work with Greg Lawler, and Oded Schramm.