The unreasonable ubiquitousness of quasi-polynomials – ScienceOpen
22
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      The unreasonable ubiquitousness of quasi-polynomials

      Preprint

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          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,...,p_{m-1} such that g(t)=p_i(t) for t=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_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 of d-tuples of natural numbers 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''.

          Related collections

          Most cited references13

          • Record: found
          • Abstract: not found
          • Article: not found

          The unreasonable effectiveness of mathematics in the natural sciences. Richard courant lecture in mathematical sciences delivered at New York University, May 11, 1959

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Points entiers dans les polyèdres convexes

              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              On vector partition functions

                Bookmark

                Author and article information

                Journal
                21 August 2013
                2014-03-02
                Article
                1308.4694
                8728b28e-bf6c-4d54-9279-497e49d6274f

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                History
                Custom metadata
                05A15, 52C07, 03B10
                Electronic Journal of Combinatorics 21 (2014), #P1.44
                Abstract updated to reflect title's play on Eugene Wigner's "The unreasonable effectiveness of mathematics in the natural sciences''. 23 pages. Improved exposition. Extended abstract published in the proceedings of FPSAC 2013
                math.CO math.LO

                Comments

                Comment on this article