A function g, with domain the natural numbers, is a quasi-polynomial if there exists a period m and polynomials p0,p1,…,pm-1 such that g(t)=pi(t) for t≡i&bmod;m. Quasi-polynomials classically 13; and ``reasonably'' 13; 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 a1x1+⋯+adxd≤b(t). Recent results of Chen, Li, Sam; Calegari, Walker; and Roune, Woods show a quasi-polynomial structure in several problems where the ai 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 St that are defined with quantifiers (∀, ∃), boolean operations (and, or, not), and statements of the form a1(t)x1+⋯+ad(t)xd ≤b(t), where ai(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.
Résumé. Une fonction g, ayant les entiers naturels pour domaine, est un quasi-polynôme si il existe un entier m et des ploynômes p0,p1,…,pm-1 tels que g(t)=pi(t) pour t≡i&bmod;m. Les quasi-polynômes apparaissent dans la théorie d'Erhart, ainsi que dans d'autres contextes où l'on s'intéresse à des familles de polyhèdres paramétrisées par une variable t, et définies par des inégalités linéaires de la forme a1x1+⋯+adxd≤b(t). Des résultats récents de Chen, Li, Sam; Calegari, Walker; et Roune, Woods exhibent une structure de quasi-polynôme dans plusieurs problèmes où les ai peuvent aussi varier en fonction de t. Nous nous intéressons à ces cas "non-raisonnables" et nous conjecturons l'existence d'une classe générale d'ensembles qui exhibent divers (possiblement) comportement de type quasi-polynômes : il s'agit des ensembles St qui sont définis en termes de quantifieurs (∀, ∃), d'opérateurs booléens (conjonction, disjonction, négation), et d'énoncés de la forme a1(t)x1+⋯+ad(t)xd ≤b(t), où ai(t) et b(t) sont des polynômes en la variable t. Ces ensembles généralisent des ensembles définis dans l'arithmétique de Presburger. Nous démontrons plusieurs relations entre nos conjectures, ainsi que plusieurs cas spéciaux de ces mêmes conjectures.