Quasi-polynomial explained

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+ … +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

. Equivalently, a function

f\colonN\toN

is a quasi-polynomial if there exist polynomials

p_0,...,p_s-1

such that

f(n)=p_i(n)

when

i\equivn\bmods

. The polynomials

p_i

are called the constituents of

Examples

Given a

-dimensional polytope

with rational vertices

v_1,...,v_n

, define

to be the convex hull of

tv_1,...,tv_n

. The function

L(P,t)=\#(tP\capZ^d)

is a quasi-polynomial in

of degree

. In this case,

L(P,t)

is a function

N\toN

. This is known as the Ehrhart quasi-polynomial, named after Eugène Ehrhart.

Given two quasi-polynomials

and

, the convolution of

and

(F*G)(k)=

	k
\sum
	m=0

F(m)G(k-m)

which is a quasi-polynomial with degree

\le\degF+\degG+1.

References

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