Quasi-polynomial

☆ Save On Wikipedia ↗

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 {\displaystyle q} {\displaystyle q} defined on Z {\displaystyle \mathbb {Z} } {\displaystyle \mathbb {Z} } of the form q ( n ) = c d ( n ) n d + c d − 1 ( n ) n d − 1 + ⋯ + c 0 ( n ) {\displaystyle q(n)=c_{d}(n)n^{d}+c_{d-1}(n)n^{d-1}+\cdots +c_{0}(n)} {\displaystyle q(n)=c_{d}(n)n^{d}+c_{d-1}(n)n^{d-1}+\cdots +c_{0}(n)}, where each c i ( n ) {\displaystyle c_{i}(n)} {\displaystyle c_{i}(n)} is a periodic function with integral period. If c d ( n ) {\displaystyle c_{d}(n)} {\displaystyle c_{d}(n)} is not identically zero, then the degree of q {\displaystyle q} {\displaystyle q} is d {\displaystyle d} {\displaystyle d}, and any common period of c 0 ( n ) , c 1 ( n ) , … , c d ( n ) {\displaystyle c_{0}(n),c_{1}(n),\dots ,c_{d}(n)} {\displaystyle c_{0}(n),c_{1}(n),\dots ,c_{d}(n)} is a period of q {\displaystyle q} {\displaystyle q}. The minimal such period (sometimes simply called the period or the quasi-period of q {\displaystyle q} {\displaystyle q}) is the least common multiple of the periods of c 0 ( n ) , c 1 ( n ) , … , c d ( n ) {\displaystyle c_{0}(n),c_{1}(n),\dots ,c_{d}(n)} {\displaystyle c_{0}(n),c_{1}(n),\dots ,c_{d}(n)}.

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

Generating functions

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

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

evaluates to a rational function of the form Q ( x ) = h ( x ) ( 1 − x r ) d + 1 {\displaystyle Q(x)={\frac {h(x)}{(1-x^{r})^{d+1}}}} {\displaystyle Q(x)={\frac {h(x)}{(1-x^{r})^{d+1}}}} where h ( x ) {\displaystyle h(x)} {\displaystyle h(x)} is a polynomial of degree < r ( d + 1 ) {\displaystyle <r(d+1)} {\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 d {\displaystyle d} {\displaystyle d}-dimensional convex polytope P {\displaystyle P} {\displaystyle P} with rational vertices v 1 , … , v n {\displaystyle v_{1},\dots ,v_{n}} {\displaystyle v_{1},\dots ,v_{n}}, define t P {\displaystyle tP} {\displaystyle tP} to be the convex hull of t v 1 , … , t v n {\displaystyle tv_{1},\dots ,tv_{n}} {\displaystyle tv_{1},\dots ,tv_{n}}. The function L ( P , t ) = # ( t P ∩ Z d ) {\displaystyle L(P,t)=\#(tP\cap \mathbb {Z} ^{d})} {\displaystyle L(P,t)=\#(tP\cap \mathbb {Z} ^{d})} is a quasi-polynomial in t {\displaystyle t} {\displaystyle t} (viewed as a positive integer variable) of degree d {\displaystyle d} {\displaystyle d}; the minimal positive integer r {\displaystyle r} {\displaystyle r} such that r P {\displaystyle rP} {\displaystyle rP} has integer vertices is a period of L ( P , t ) {\displaystyle L(P,t)} {\displaystyle L(P,t)}. This is known as the Ehrhart quasi-polynomial, named after Eugène Ehrhart.
  • Given two quasi-polynomials F {\displaystyle F} {\displaystyle F} and G {\displaystyle G} {\displaystyle G}, the convolution of F {\displaystyle F} {\displaystyle F} and G {\displaystyle G} {\displaystyle G} is
( F ∗ G ) ( k ) = ∑ m = 0 k F ( m ) G ( k − m ) {\displaystyle (F*G)(k)=\sum _{m=0}^{k}F(m)G(k-m)} {\displaystyle (F*G)(k)=\sum _{m=0}^{k}F(m)G(k-m)}
which is a quasi-polynomial with degree ≤ deg ⁡ F + deg ⁡ G + 1. {\displaystyle \leq \deg F+\deg G+1.} {\displaystyle \leq \deg F+\deg G+1.}

References

  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