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 $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 $i\equiv n{\bmod {s}}$ . The polynomials $p_{i}$ are called the constituents of $f$ .

Examples[edit]

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