The unreasonable ubiquitousness of quasi-polynomials
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 whe...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2013-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/2335/pdf |
| _version_ | 1827323979013029888 |
|---|---|
| author | Kevin Woods |
| author_facet | Kevin Woods |
| author_sort | Kevin Woods |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T02:01:22Z |
| format | Article |
| id | doaj.art-0931abc6d141454083ceb6ef3f588327 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:01:22Z |
| publishDate | 2013-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-0931abc6d141454083ceb6ef3f5883272024-03-07T14:52:36ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502013-01-01DMTCS Proceedings vol. AS,...Proceedings10.46298/dmtcs.23352335The unreasonable ubiquitousness of quasi-polynomialsKevin Woods0Oberlin CollegeA 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.https://dmtcs.episciences.org/2335/pdfquasi-polynomialsehrhart theorypresburger arithmeticrational generating functions[info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| spellingShingle | Kevin Woods The unreasonable ubiquitousness of quasi-polynomials Discrete Mathematics & Theoretical Computer Science quasi-polynomials ehrhart theory presburger arithmetic rational generating functions [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| title | The unreasonable ubiquitousness of quasi-polynomials |
| title_full | The unreasonable ubiquitousness of quasi-polynomials |
| title_fullStr | The unreasonable ubiquitousness of quasi-polynomials |
| title_full_unstemmed | The unreasonable ubiquitousness of quasi-polynomials |
| title_short | The unreasonable ubiquitousness of quasi-polynomials |
| title_sort | unreasonable ubiquitousness of quasi polynomials |
| topic | quasi-polynomials ehrhart theory presburger arithmetic rational generating functions [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| url | https://dmtcs.episciences.org/2335/pdf |
| work_keys_str_mv | AT kevinwoods theunreasonableubiquitousnessofquasipolynomials AT kevinwoods unreasonableubiquitousnessofquasipolynomials |