Quasi-polynomial (original) (raw)

From Wikipedia, the free encyclopedia

Generalization of polynomials

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 (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 ) {\displaystyle q(k)=c_{d}(k)k^{d}+c_{d-1}(k)k^{d-1}+\cdots +c_{0}(k)} $q(k)=c_{d}(k)k^{d}+c_{d-1}(k)k^{d-1}+\cdots +c_{0}(k)$ , where c i ( k ) {\displaystyle c_{i}(k)} $c_{i}(k)$ is a periodic function with integral period. If c d ( k ) {\displaystyle c_{d}(k)} $c_{d}(k)$ is not identically zero, then the degree of q {\displaystyle q} $q$ is d {\displaystyle d} $d$ . Equivalently, a function f : N → N {\displaystyle f\colon \mathbb {N} \to \mathbb {N} } $f\colon \mathbb {N} \to \mathbb {N}$ is a quasi-polynomial if there exist polynomials p 0 , … , p s − 1 {\displaystyle p_{0},\dots ,p_{s-1}} $p_{0},\dots ,p_{s-1}$ such that f ( n ) = p i ( n ) {\displaystyle f(n)=p_{i}(n)} $f(n)=p_{i}(n)$ when i ≡ n mod s {\displaystyle i\equiv n{\bmod {s}}} $i\equiv n{\bmod {s}}$ . The polynomials p i {\displaystyle p_{i}} $p_{i}$ are called the constituents of f {\displaystyle f} $f$ .

Given a d {\displaystyle d} $d$ -dimensional polytope P {\displaystyle P} $P$ with rational vertices v 1 , … , v n {\displaystyle v_{1},\dots ,v_{n}} $v_{1},\dots ,v_{n}$ , define t P {\displaystyle tP} $tP$ to be the convex hull of t v 1 , … , t v n {\displaystyle tv_{1},\dots ,tv_{n}} $tv_{1},\dots ,tv_{n}$ . The function L ( P , t ) = # ( t P ∩ Z d ) {\displaystyle L(P,t)=\#(tP\cap \mathbb {Z} ^{d})} $L(P,t)=\#(tP\cap \mathbb {Z} ^{d})$ is a quasi-polynomial in t {\displaystyle t} $t$ of degree d {\displaystyle d} $d$ . In this case, L ( P , t ) {\displaystyle L(P,t)} $L(P,t)$ is a function N → N {\displaystyle \mathbb {N} \to \mathbb {N} } $\mathbb {N} \to \mathbb {N}$ . This is known as the Ehrhart quasi-polynomial, named after Eugène Ehrhart.
Given two quasi-polynomials F {\displaystyle F} $F$ and G {\displaystyle G} $G$ , the convolution of F {\displaystyle F} $F$ and G {\displaystyle G} $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)} $(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.} $\leq \deg F+\deg G+1.$

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