The unreasonable ubiquitousness of quasi-polynomials

Kevin Woods¹

¹Oberlin College

The electronic journal of combinatorics, Tome 21 (2014) no. 1

Résumé

A function $g$, with domain the natural numbers, is a quasi-polynomial if there exists a period $m$ and polynomials $p_0,p_1,\ldots,p_{m-1}$ such that $g(t)=p_i(t)$ for $t\equiv i\bmod m$. Quasi-polynomials 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+\cdots+a_dx_d\le b(t)$. Recent results of Chen, Li, Sam; Calegari, Walker; and Roune, Woods show a quasi-polynomial 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) quasi-polynomial behaviors: sets $S_t\subseteq\mathbb{N}^d$ that are defined with quantifiers ($\forall$, $\exists$), boolean operations (and, or, not), and statements of the form $a_1(t)x_1+\cdots+a_d(t)x_d \le 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. The title is a play on Eugene Wigner's "The unreasonable effectiveness of mathematics in the natural sciences''.

Détail

DOI : 10.37236/3750

Classification : 05A15, 52B05, 52C07, 03F30
Mots-clés : Ehrhart polynomials, quasi-polynomials, Presburger arithmetic, rational generating functions