Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/hal-01229674
Contributor : Alain Monteil <>
Submitted on : Tuesday, November 17, 2015 - 10:19:43 AM
Last modification on : Friday, June 8, 2018 - 8:38:01 PM
Long-term archiving on: : Thursday, February 18, 2016 - 11:35:36 AM

File

dmAS0159.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01229674, version 1

Collections

Citation

Kevin Woods. The unreasonable ubiquitousness of quasi-polynomials. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. pp.695-706. ⟨hal-01229674⟩

Share

Metrics

Record views

51

Files downloads

687