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.

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\}\; o\; mathbb\{N\}$ is a quasi-polynomial if there exist polynomials $p\_0,\; dots,\; p\_\{s-1\}$ such that $f(n)\; =\; p\_i(n)$ when . 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\}\; o\; 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$.

References

* Stanley, Richard P. (1997). [http://www-math.mit.edu/~rstan/ec/ "Enumerative Combinatorics", Volume 1] . Cambridge University Press. ISBN 0-521-55309-1, 0-521-56069-1.

ee also

* Polynomial
* Ehrhart polynomial