Parametric Presburger arithmetic: logic, combinatorics, and quasi-polynomial behavior

DOI10.19086/DA.1254zbMATH Open1404.11029arXiv1608.08520OpenAlexW3098542245MaRDI QIDQ4645009FDOQ4645009

Authors:

Publication date: 9 January 2019

Published in: Discrete Analysis (Search for Journal in Brave)

Abstract: Parametric Presburger arithmetic concerns families of sets S_t in Z^d, for t in N, that are defined using addition, inequalities, constants in Z, Boolean operations, multiplication by t, and quantifiers on variables ranging over Z. That is, such families are defined using quantifiers and Boolean combinations of formulas of the form a(t) x <= b(t), where a(t) is in Z[t]^d, b(t) in Z[t]. A function g: N -> Z is a quasi-polynomial if there exists a period m and polynomials f_0, ..., f_{m-1} in Q[t] such that g(t)=f_i(t) for t congruent to i (mod m.) Recent results of Chen, Li, Sam; Calegari, Walker; Roune, Woods; and Shen concern specific families in parametric Presburger arithmetic that exhibit quasi-polynomial behavior. For example, S_t might be an a quasi-polynomial function of t or an element x(t) in S_t might be specifiable as a function with quasi-polynomial coordinates, for sufficiently large t. Woods conjectured that all parametric Presburger sets exhibit this quasi-polynomial behavior. Here, we prove this conjecture, using various tools from logic and combinatorics.

Full work available at URL: https://arxiv.org/abs/1608.08520

Recommendations

• The unreasonable ubiquitousness of quasi-polynomials
• The unreasonable ubiquitousness of quasi-polynomials
• Parametric Presburger arithmetic: complexity of counting and quantifier elimination
• Presburger arithmetic, rational generating functions, and quasi-polynomials
• Presburger arithmetic, rational generating functions, and quasi-polynomials

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Counting solutions of Diophantine equations (11D45)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Computing the Continuous Discretely
• Title not available (Why is that?)
• A mathematical introduction to logic.
• Convex Polytopes
• Generalized Ehrhart polynomials
• Weak quantifier elimination for the full linear theory of the integers
• The parametric Frobenius problem
• Integer hulls of linear polyhedra and scl in families
• On the completeness of a certain system of arithmetic of whole numbers in which addition occurs as the only operation
• The unreasonable ubiquitousness of quasi-polynomials
• Title not available (Why is that?)
• Quantifier elimination for modules with scalar variables
• Discretely ordered modules as a first-order extension of the cutting planes proof system
• Bounding quantification in parametric expansions of Presburger arithmetic
• Parametrizing an Integer Linear Program by an Integer

Cited In (8)

• Parametric Presburger arithmetic: complexity of counting and quantifier elimination
• One-variable logic meets Presburger arithmetic
• On parametrized families of numerical semigroups
• Periodic behavior in families of numerical and affine semigroups via parametric Presburger arithmetic
• Bounding quantification in parametric expansions of Presburger arithmetic
• A Plethora of Polynomials: A Toolbox for Counting Problems
• A Parametric Version of LLL and Some Consequences: Parametric Shortest and Closest Vector Problems
• On factorization invariants and Hilbert functions

This page was built for publication: Parametric Presburger arithmetic: logic, combinatorics, and quasi-polynomial behavior

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4645009)