PRESBURGER ARITHMETIC, RATIONAL GENERATING FUNCTIONS, AND QUASI-POLYNOMIALS

Presburger arithmetic is the first-order theory of the natural numbers with addition (but no multiplication). We characterize sets that can be defined by a Presburger formula as exactly the sets whose characteristic functions can be represented by rational generating functions; a geometric characterization of such sets is also given. In addition, if p = (p1,..., pn) are a subset of the free variables in a Presburger formula, we can define a counting function g(p) to be the number of solutions to the formula, for a given p. We show that every counting function obtained in this way may be represented as, equivalently, either a piecewise quasi-polynomial or a rational generating function. Finally, we translate known computational complexity results into this setting and discuss open directions. §1. Introduction. A broad and interesting class of sets are those that can be defined over N = {0, 1, 2,...} with first order logic and addition. Definition 1.1. A Presburger formula is a first-order formula in the language of addition, evaluated over the natural numbers. We will denote a generic Pres-burger formula as F (u), where u are the free variables (those not associated wit