Personal tools
You are here: Home Administration Mathematics Department Events Counting integer points in polytopes with an extension of Presburger arithmetic

Counting integer points in polytopes with an extension of Presburger arithmetic

John Goodrick (Los Andes University, Colombia)
When Oct 26, 2017
from 12:30 PM to 02:00 PM
Contact Name
Add event to calendar vCal
iCal

Abstract: Fix some polytope P in R^d whose vertices have integer coordinates. Then for any positive integer t, one can ask to compute the number f_P(t) of points in the lattice Z^d that lie within the t-th dilate of P. By a theorem of Ehrhart, the function f_P(t) is always a polynomial. If the vertices of P are rational (i.e. in Q^d instead of Z^d), then the function f_P(t) is no longer necessarily polynomial but it is a quasi-polynomial: there is a number m and polynomials g_1, ..., g_m such that f_P(t) = g_i(t) whenever t is congruent to i modulo m.

In this talk, we will review the classic theory of Ehrhart polynomials and present a generalization (based on recent joint work with Tristram Bogart and Kevin Woods): if f(t) is the function which counts the number of integer points within a bounded region of R^d which is defined by a formula using addition, multiplication by the parameter t, inequalities, and quantifiers over variables from Z (but not over the domain of the variable t), then f(t) is quasi-polynomial for all sufficiently large values of t. We call such families "parametric Presburger families" in analogy with the logical theory of Presburger arithmetic. We will also present some new applications of this result to other combinatorially interesting families of sets of integer points.