The unreasonable ubiquitousness of quasi-polynomials (Q405135)

Summary: 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+\ldots+a_dx_d\leq b(t)\). Recent results of \textit{S. Chen, N. Li} and \textit{S. V. Sam} [Trans. Am. Math. Soc. 364, No. 1, 551--569 (2012; Zbl 1238.11045)], \textit{D. Calegari} and \textit{A. Walker} [Trans. Am. Math. Soc. 365, No. 10, 5085--5102 (2013; Zbl 1300.11100)] and \textit{B. Roune} and \textit{K. Woods} [The parametric Frobenius problem. forthcoming, (2014)] 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+\ldots+a_d(t)x_d \leq 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''.