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

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

See also

References

This article is issued from Wikipedia - version of the Tuesday, December 22, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.