Quasi-polynomial
In mathematics, a quasi-polynomial (pseudo-polynomial) is a generalization of polynomials. While the coefficients of a polynomial come from a ring, the coefficients of quasi-polynomials are instead periodic functions with integral period. Quasi-polynomials appear throughout much of combinatorics as the enumerators for various objects.
A quasi-polynomial can be written as [math]\displaystyle{ q(k) = c_d(k) k^d + c_{d-1}(k) k^{d-1} + \cdots + c_0(k) }[/math], where [math]\displaystyle{ c_i(k) }[/math] is a periodic function with integral period. If [math]\displaystyle{ c_d(k) }[/math] is not identically zero, then the degree of [math]\displaystyle{ q }[/math] is [math]\displaystyle{ d }[/math]. Equivalently, a function [math]\displaystyle{ f \colon \mathbb{N} \to \mathbb{N} }[/math] is a quasi-polynomial if there exist polynomials [math]\displaystyle{ p_0, \dots, p_{s-1} }[/math] such that [math]\displaystyle{ f(n) = p_i(n) }[/math] when [math]\displaystyle{ i \equiv n \bmod s }[/math]. The polynomials [math]\displaystyle{ p_i }[/math] are called the constituents of [math]\displaystyle{ f }[/math].
Examples
- Given a [math]\displaystyle{ d }[/math]-dimensional polytope [math]\displaystyle{ P }[/math] with rational vertices [math]\displaystyle{ v_1,\dots,v_n }[/math], define [math]\displaystyle{ tP }[/math] to be the convex hull of [math]\displaystyle{ tv_1,\dots,tv_n }[/math]. The function [math]\displaystyle{ L(P,t) = \#(tP \cap \mathbb{Z}^d) }[/math] is a quasi-polynomial in [math]\displaystyle{ t }[/math] of degree [math]\displaystyle{ d }[/math]. In this case, [math]\displaystyle{ L(P,t) }[/math] is a function [math]\displaystyle{ \mathbb{N} \to \mathbb{N} }[/math]. This is known as the Ehrhart quasi-polynomial, named after Eugène Ehrhart.
- Given two quasi-polynomials [math]\displaystyle{ F }[/math] and [math]\displaystyle{ G }[/math], the convolution of [math]\displaystyle{ F }[/math] and [math]\displaystyle{ G }[/math] is
- [math]\displaystyle{ (F*G)(k) = \sum_{m=0}^k F(m)G(k-m) }[/math]
which is a quasi-polynomial with degree [math]\displaystyle{ \le \deg F + \deg G + 1. }[/math]
See also
References
- Stanley, Richard P. (1997). Enumerative Combinatorics, Volume 1. Cambridge University Press. ISBN 0-521-55309-1, 0-521-56069-1.
 |  |
