Quasi-polynomial

From Wikipedia, the free encyclopedia

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.

We can write a quasi-polynomial as $q(k) = c_d(k) k^d + c_{d-1}(k) k^{d-1} + \cdots + c_0(k)$ . If $c d (k)$ is not identically zero, then the degree of q is d. Equivalently, a function $f \colon \mathbb{N} \to \mathbb{N}$ is a quasi-polynomial if there exist polynomials $p_0, \dots, p_{s-1}$ such that $f (n) = p i (n)$ when $n \equiv i \bmod s$ . The polynomials $p i$ are called the constituents of f.

[edit] Examples

Given a d-dimensional polytope P with rational vertices $v_1,\dots,v_n$ , define tP to be the convex hull of $tv_1,\dots,tv_n$ . The function $L(P,t) = \#(tP \cap \mathbb{Z}^d)$ is a quasi-polynomial in t of degree d. In this case, L(P,t) is a function $\mathbb{N} \to \mathbb{N}$ . This is known as the Ehrhart quasi-polynomial, named after Eugène Ehrhart.
Given two quasi-polynomials F and G, the convolution of F and G is