# The unreasonable ubiquitousness of quasi-polynomials

Abstract : 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+⋯+a_dx_d≤ 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$ 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.
Keywords :
Type de document :
Communication dans un congrès
Alain Goupil and Gilles Schaeffer. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), pp.695-706, 2013, DMTCS Proceedings

Littérature citée [17 références]

https://hal.inria.fr/hal-01229674
Contributeur : Alain Monteil <>
Soumis le : mardi 17 novembre 2015 - 10:19:43
Dernière modification le : vendredi 8 juin 2018 - 20:38:01
Document(s) archivé(s) le : jeudi 18 février 2016 - 11:35:36

### Fichier

dmAS0159.pdf
Fichiers éditeurs autorisés sur une archive ouverte

### Identifiants

• HAL Id : hal-01229674, version 1

### Citation

Kevin Woods. The unreasonable ubiquitousness of quasi-polynomials. Alain Goupil and Gilles Schaeffer. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), pp.695-706, 2013, DMTCS Proceedings. 〈hal-01229674〉

### Métriques

Consultations de la notice

## 22

Téléchargements de fichiers