Quasi-polynomial

For quasi-polynomial time complexity of algorithms, see Quasi-polynomial time.

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 $q(k) = c_d(k) k^d + c_{d-1}(k) k^{d-1} + \cdots + c_0(k)$, where $c_{i}(k)$ is a periodic function with integral period. 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.

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

$(F*G)(k) = \sum_{m=0}^k F(m)G(k-m)$

which is a quasi-polynomial with degree $\le \deg F + \deg G + 1.$

See also

• Ehrhart polynomial

References

• Stanley, Richard P. (1997). Enumerative Combinatorics, Volume 1. Cambridge University Press. ISBN 0-521-55309-1, 0-521-56069-1.