Counting integer points in polytopes with an extension of Presburger arithmetic
Time and place
12:30 PM on Thursday, October 26th, 2017; NAC 6/111
John Goodrick (Los Andes University, Colombia )
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.
