Quasi-polynomial

For quasi-polynomial bounds in the analysis of algorithms, see Quasi-polynomial growth. For functions that take the form of polynomials in a variable and an exponential function, see Exponential 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:\mathbb{\mathbb{N}}\to \mathbb{\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 nmods$. 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 $t{v}_1,\dots ,t{v}_n$. The function $L(P,t)=\mathrm{\#}(tP\cap {\mathbb{\mathbb{Z}}}^d)$ is a quasi-polynomial in $t$ of degree $d$. In this case, $L(P,t)$ is a function $\mathbb{\mathbb{N}}\to \mathbb{\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 \mathrm{deg}F+\mathrm{deg}G+1.$

References

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