Kevin Woods

The unreasonable ubiquitousness of quasipolynomials
dmtcs:2335 
Discrete Mathematics & Theoretical Computer Science,
January 1, 2013,
DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)

https://doi.org/10.46298/dmtcs.2335
The unreasonable ubiquitousness of quasipolynomials
Authors: Kevin Woods ^{1}
NULL
Kevin Woods
1 Oberlin College
A function $g$, with domain the natural numbers, is a quasipolynomial if there exists a period $m$ and polynomials $p_0,p_1,\ldots,p_m1$ such that $g(t)=p_i(t)$ for $t\equiv i\bmod m$. Quasipolynomials classically – and ``reasonably'' – appear in Ehrhart theory and in other contexts where one examines a family of polyhedra, parametrized by a variable t, and defined by linear inequalities of the form $a_1x_1+⋯+a_dx_d≤ b(t)$. Recent results of Chen, Li, Sam; Calegari, Walker; and Roune, Woods show a quasipolynomial structure in several problems where the $a_i$ are also allowed to vary with $t$. We discuss these ``unreasonable'' results and conjecture a general class of sets that exhibit various (eventual) quasipolynomial behaviors: sets $S_t$ that are defined with quantifiers $(\forall , ∃)$, boolean operations (and, or, not), and statements of the form $a_1(t)x_1+⋯+a_d(t)x_d ≤ b(t)$, where $a_i(t)$ and $b(t)$ are polynomials in $t$. These sets are a generalization of sets defined in the Presburger arithmetic. We prove several relationships between our conjectures, and we prove several special cases of the conjectures.