準多項式

準多項式で表される計算時間については「w:Quasi-polynomial time」をご覧ください。

準多項式（じゅんたこうしき、quasi-polynomial、pseudo-polynomial）は多項式を一般化したものである。多項式の係数は環の元になっているが、準多項式の係数は整数周期を持つ周期関数である。準多項式は組合せ数学の多くの理論でさまざまな対象の列挙子として用いられる。

準多項式は ${\displaystyle q(k)=c_{d}(k)k^{d}+c_{d-1}(k)k^{d-1}+\cdots +c_{0}(k)}$ と表される。ここで ${\displaystyle c_{i}(k)}$ は整数周期を持つ周期関数である。${\displaystyle c_{d}(k)}$ が恒等的に 0 でなければ q の次数は d である。また ${\displaystyle n\equiv i{\bmod {s}}}$ で ${\displaystyle f(n)=p_{i}(n)}$ であるような多項式 ${\displaystyle p_{0},\dots ,p_{s-1}}$ が存在するとき、関数 ${\displaystyle f\colon \mathbb {N} \to \mathbb {N} }$ は準多項式である。多項式 ${\displaystyle p_{i}}$ を f の成分という。

• 有理点 ${\displaystyle v_{1},\dots ,v_{n}}$ を頂点とする d 次のポリトープ Pについて、tP を ${\displaystyle tv_{1},\dots ,tv_{n}}$ の凸包と定義する。関数 ${\displaystyle L(P,t)=\#(tP\cap \mathbb {Z} ^{d})}$ は t による d 次の準多項式である。このとき L(P,t) は ${\displaystyle \mathbb {N} \to \mathbb {N} }$ 関数である。これはウジェーヌ・エルハート（Eugène Ehrhart）にちなみエルハート準多項式と呼ばれる。
• 2つの準多項式 F、G の合成積は

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

と定義される。これは次数 ${\displaystyle \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.