The unreasonable ubiquitousness of quasi-polynomials

Title:
The unreasonable ubiquitousness of quasi-polynomials
Authors:
Woods, Kevin
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),...,Pm-1 such that g(t) - p(i)(t) for t equivalent to i mod 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(1)x(1) +...+a(d)x(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, 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 subset of N-d that are defined with quantifiers (for all, there exists), 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. The title is a play on Eugene Wigner's "The unreasonable effectiveness of mathematics in the natural sciences".
Citation:
Woods, Kevin. 2014. "The unreasonable ubiquitousness of quasi-polynomials." Electronic Journal Of Combinatorics 21(1): 44.
Publisher:
Electronic Journal Of Combinatorics
DATE ISSUED:
2014-02-28
Department:
Mathematics
Type:
Article
Additional Links:
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p44
PERMANENT LINK:
http://hdl.handle.net/11282/594873

Full metadata record

DC FieldValue Language
dc.contributor.authorWoods, Kevinen
dc.date.accessioned2016-01-26T13:38:30Zen
dc.date.available2016-01-26T13:38:30Zen
dc.date.issued2014-02-28en
dc.identifier.citationWoods, Kevin. 2014. "The unreasonable ubiquitousness of quasi-polynomials." Electronic Journal Of Combinatorics 21(1): 44.en
dc.identifier.issn1077-8926en
dc.identifier.urihttp://hdl.handle.net/11282/594873en
dc.description.abstractA function g, with domain the natural numbers, is a quasi-polynomial if there exists a period m and polynomials p(0),p(1),...,Pm-1 such that g(t) - p(i)(t) for t equivalent to i mod 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(1)x(1) +...+a(d)x(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, 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 subset of N-d that are defined with quantifiers (for all, there exists), 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. The title is a play on Eugene Wigner's "The unreasonable effectiveness of mathematics in the natural sciences".en
dc.language.isoen_USen
dc.publisherElectronic Journal Of Combinatoricsen
dc.relation.urlhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p44en
dc.subject.departmentMathematicsen_US
dc.titleThe unreasonable ubiquitousness of quasi-polynomialsen_US
dc.typeArticleen
dc.identifier.journalElectronic Journal Of Combinatoricsen
dc.subject.keywordEhrhart polynomialsen_US
dc.subject.keywordGenerating functionsen_US
dc.subject.keywordPresburger arithmeticen_US
dc.subject.keywordQuasi-plynomialsen_US
dc.subject.keywordRational generating functionsen_US
dc.identifier.volume21en_US
dc.identifier.issue1en_US
All Items in The Five Colleges of Ohio Digital Repository are protected by copyright, with all rights reserved, unless otherwise indicated.