Quasi-polynomial
In mathematics, a quasi-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.
Definition
A quasi-polynomial is a function defined on of the form, where each is a periodic function with integral period. If is not identically zero, then the degree of is, and any common period of is a period of.The minimal such period is the least common multiple of the periods of.
Equivalently, a function defined on is a quasi-polynomial if there exist a positive integer and polynomials such that when. The minimal such coincides with the minimal period of.
The polynomials are called the constituents of.
Generating functions
A function defined on is a quasi-polynomial of degree and period dividing if and only its generating functionevaluates to a rational function of the form where is a polynomial of degree.
Thus quasi-polynomials are characterized through generating functions that are rational and whose poles are rational roots of unity.
Examples
- Given a -dimensional convex polytope with rational vertices, define to be the convex hull of. The function is a quasi-polynomial in of degree ; the minimal positive integer such that has integer vertices is a period of. This is known as the Ehrhart quasi-polynomial, named after Eugène Ehrhart.
- Given two quasi-polynomials and, the convolution of and is