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 $\leq \deg F+\deg G+1.$

References

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

This article is issued from Wikipedia - version of the 7/17/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Quasi-polynomial

Examples

See also

References