準多項式

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

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

例

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

[math](F*G)(k) = \sum_{m=0}^k F(m)G(k-m)[/math]

と定義される。これは次数 [math]\le \deg F + \deg G + 1[/math] の準多項式になっている。

関連項目

• エルハート多項式

参考文献

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