Blog Archives

Topic Archive: Pressburger Arithmetic

CUNY Logic WorkshopFriday, March 27, 20152:00 pmGC 6417

John Goodrick

Counting lattice points and parametric Presburger formulas

Universidad de los Andes Bogotá Colombia

In 2013, Kevin Woods showed that for a subset S of the d-th Cartesian power of the natural numbers N, the following are equivalent:

(1) S is definable in Presburger arithmetic,
(2) S is a finite union of intersections of polyhedra with translates of lattices,
(3) S has a rational generating function.

More recently, Woods has studied so-called parametric Presburger families: subsets of powers of N definable with addition and the ordering, plus one special “parameter” variable t which can be multiplied by terms in the other variables. The special variable t also ranges over N, but it is the only variable which cannot be quantified over. This is useful for defining many families which are combinatorially interesting, such as the lattice points inside the t-th dilate of a given polyhedron and a version of the Frobenius problem.

Jointly with Tristram Bogart, we are working to understand the properties of parametric Presburger families. We will present a quantifier elimination result and some conjectures of Woods on Skolem functions and counting functions for these families, which we are studying using logical and syntactic methods.