Quasi-polynomial

{{For multi|quasi-polynomial bounds in the analysis of algorithms|Quasi-polynomial growth|functions that take the form of polynomials in a variable and an exponential function|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 \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

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.$

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.

Category:Polynomials

Category:Algebraic combinatorics