Quasi-polynomial

From Wikipedia, the free encyclopedia
Jump to: navigation, search
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[edit]

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

See also[edit]

References[edit]