Quasi-polynomial

For quasi-polynomial bounds in the analysis of algorithms, see Quasi-polynomial growth. For functions that take the form of polynomials in a variable and an exponential function, see Exponential 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 ${\displaystyle q}$ defined on ${\displaystyle \mathbb {Z} }$ of the form ${\displaystyle q(n)=c_{d}(n)n^{d}+c_{d-1}(n)n^{d-1}+\cdots +c_{0}(n)}$, where each ${\displaystyle c_{i}(n)}$ is a periodic function with integral period. If ${\displaystyle c_{d}(n)}$ is not identically zero, then the degree of ${\displaystyle q}$ is ${\displaystyle d}$, and any common period of ${\displaystyle c_{0}(n),c_{1}(n),\dots ,c_{d}(n)}$ is a period of ${\displaystyle q}$. The minimal such period (sometimes simply called the period or the quasi-period of ${\displaystyle q}$) is the least common multiple of the periods of ${\displaystyle c_{0}(n),c_{1}(n),\dots ,c_{d}(n)}$.

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

Generating functions

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

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

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

Examples

• Given a ${\displaystyle d}$-dimensional convex polytope ${\displaystyle P}$ with rational vertices ${\displaystyle v_{1},\dots ,v_{n}}$, define ${\displaystyle tP}$ to be the convex hull of ${\displaystyle tv_{1},\dots ,tv_{n}}$. The function ${\displaystyle L(P,t)=\#(tP\cap \mathbb {Z} ^{d})}$ is a quasi-polynomial in ${\displaystyle t}$ (viewed as a positive integer variable) of degree ${\displaystyle d}$; the minimal positive integer ${\displaystyle r}$ such that ${\displaystyle rP}$ has integer vertices is a period of ${\displaystyle L(P,t)}$. This is known as the Ehrhart quasi-polynomial, named after Eugène Ehrhart.
• Given two quasi-polynomials ${\displaystyle F}$ and ${\displaystyle G}$, the convolution of ${\displaystyle F}$ and ${\displaystyle G}$ is

${\displaystyle (F*G)(k)=\sum _{m=0}^{k}F(m)G(k-m)}$

which is a quasi-polynomial with degree ${\displaystyle \leq \deg F+\deg G+1.}$

1. Stanley, Richard P. (1997). "Section 4.4: Quasipolynomials". Enumerative Combinatorics, Volume 1. Cambridge University Press. ISBN   0-521-56069-1.
2. Beck, Matthias; Sanyal, Raman (2018), "Section 4.5: Quasipolynomials", Combinatorial Reciprocity Theorems: An Invitation to Enumerative Geometric Combinatorics, Graduate Studies in Mathematics, American Mathematical Society, ISBN   978-1-4704-2200-4