Quasi-polynomial

In mathematics, a quasi-polynomial (sometimes called 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.

Definition

A quasi-polynomial is a function $q$ defined on $\mathbb{\mathbb{Z}}$ of the form $q(n)=c_d(n)n^d+c_{d-1}(n)n^{d-1}+\cdots +c_0(n)$, where each $c_i(n)$ is a periodic function with integral period. If $c_d(n)$ is not identically zero, then the degree of $q$ is $d$, and any common period of $c_0(n),c_1(n),\dots ,c_d(n)$ is a period of $q$. The minimal such period (sometimes simply called the period or the quasi-period of $q$) is the least common multiple of the periods of $c_0(n),c_1(n),\dots ,c_d(n)$.

Equivalently, a function $q$ defined on $\mathbb{\mathbb{Z}}$ is a quasi-polynomial if there exist a positive integer $s$ and polynomials $p_0,\dots ,p_{s-1}$ such that $q(n)=p_i(n)$ when $i\equiv nmods$. The minimal such $s$ coincides with the minimal period of $q$. The polynomials $p_i$ are called the constituents of $q$.

Generating functions

A function $q$ defined on $\mathbb{\mathbb{Z}}$ is a quasi-polynomial of degree $\le d$ and period dividing $r$ if and only its generating function

$Q(x):=\sum _{n\ge 0}q(n)x^n$

evaluates to a rational function of the form $Q(x)=\frac{h(x)}{(1-x^r{)}^{d+1}}$ where $h(x)$ is a polynomial of degree $<r(d+1)$. Thus quasi-polynomials are characterized through generating functions that are rational and whose poles are rational roots of unity.

Examples

• Given a $d$-dimensional convex polytope $P$ with rational vertices $v_1,\dots ,v_n$, define $tP$ to be the convex hull of $t{v}_1,\dots ,t{v}_n$. The function $L(P,t)=\mathrm{\#}(tP\cap {\mathbb{\mathbb{Z}}}^d)$ is a quasi-polynomial in $t$ (viewed as a positive integer variable) of degree $d$; the minimal positive integer $r$ such that $rP$ has integer vertices is a period of $L(P,t)$. 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 \mathrm{deg}F+\mathrm{deg}G+1.$