16.5 形式的冪級数

目次

16.5.1 発散する母関数

\(x^{n}\) の係数が \(n!\) の母関数を \(F(x)\) とする:

\[ F(x) ::= 1 + 1x + 2x^{2} + \cdots + n!\,x^{n} + \cdots \]

全ての \(x \neq 0\) で \(x^{n} = o(n!)\) なので、この母関数は \(x = 0\) でのみ収束する1。

そして、\(x^{n}\) の係数が \(n \cdot n!\) の母関数を \(H(x)\) とする:

\[ H(x) ::= 0 + 1x + 4x^{2} + \cdots + n \cdot n!\, x^{n} + \cdots \]

この \(H(x)\) も \(x = 0\) でのみ収束する。つまり、実数上の部分関数として見たとき \(H(x)\) と \(F(x)\) は両方とも \(x = 0\) に対してだけ定義された自明な関数を表現する。

一方、\(F(x)\) と \(H(x)\) では \(n \neq 1\) のとき \(x^{n}\) の係数が異なる。両者を異なる形式的オブジェクトとして記号的に扱うと、利用価値が生まれる。

この例を示そう。\(F(x)\) から \(1\) を引いて \(x\) で割ると、\(x^{n}\) の係数が \((n + 1)!\) の母関数が得られる。つまり、次の関係が成り立つ:

\[ [x^{n}]\left( \frac{F(x) - 1}{x} \right) = (n + 1)! \tag{16.16}\]

さらに形式的な議論を進めると、次の恒等式2を証明できる:

\[ n! = 1 + \sum_{i=1}^{n} (i - 1) \cdot (i - 1)! \tag{16.17}\]

証明は次の通りである。恒等式 \(\text{(16.16)}\) から次が分かる:

\[ [x^{n}] H(x) ::= n \cdot n! = (n + 1)! - n! = [x^{n}] \left( \frac{F(x) - x}{x} \right) - [x^{n}] F(x) \]

これは次の恒等式を意味する:

\[ H(x) = \frac{F(x) - 1}{x} - F(x) \tag{16.18}\]

これを \(F(x)\) について解けば次を得る:

\[ F(x) = \frac{x H(x) + 1}{1 - x} \tag{16.19}\]

\([x^{n}](xH(x) + 1)\) は \(n \geq 1\) のとき \((n - 1) \cdot (n - 1)!\) に等しく、\(n = 0\) のとき \(1\) となる。よって畳み込み則より次の等式が得られる:

\[ [x^{n}] \left( \frac{x H(x) + 1}{1 - x} \right) = 1 + \sum_{i=1}^{n} (i - 1) \cdot (i - 1)! \]

これと恒等式 \(\text{(16.19)}\) より、示したかった恒等式 \(\text{(16.17)}\) が証明される。

16.5.2 冪級数からなる環

収束半径が \(0\) の無限級数を使って恒等式 \(\text{(16.19)}\) を「証明」できた。しかし、その証明で使った式変形はどのように正当化されるのだろうか？ その答えは実数の無限級数とそれらの間の演算を抽象化すると得られる。

例えば、次の二つの無限列が無限級数を表すとしよう:

\[ \begin{aligned} G &::= (g_{0},\, g_{1},\, g_{2},\, \ldots) \\ H &::= (h_{0},\, h_{1},\, h_{2},\, \ldots) \end{aligned} \]

二つの無限級数に適用できることが期待される基礎的な演算の一つに加算がある。\(G\) と \(H\) の加算の結果は、要素ごとの和として次の規則で定義できる:

\[ G \oplus H ::= (g_{0} + h_{0},\, g_{1} + h_{1},\, \ldots,\, g_{n} + h_{n},\, \ldots) \]

乗算も基礎的な演算である。\(G\) と \(H\) の乗算の結果は (要素ごとの積ではなく) 畳み込み則を参考にして次の規則で定義される:

\[ G \otimes H ::= \left( g_{0} h_{0},\, g_{0}h_{1} + g_{1}h_{0},\, \ldots,\, \sum_{i=0}^{n} g_{i}h_{n-i},\, \ldots \right) \]

無限列に対するこれらの演算は多くの優れた性質を持つ。例えば:

実は、演算 \(\oplus\), \(\otimes\) は第 9.7.1 項で説明した可換環の公理を全て満たす。実数の無限列全体の集合と演算 \(\oplus\), \(\otimes\) を合わせたものを、実数3上の形式的冪級数環 (ring of formal power series) と呼ぶ。

無限列 \(G\) が無限列 \(H\) の逆元 (inverse) とは、次の等式が成り立つことを意味する:

\[ G \otimes H = I \]

逆元は乗法逆元 (multiplicative inverse) や逆数 (reciprocal) とも呼ばれる。環の公理からは逆元が存在するなら一意と示せる (問題 9.33) ので、曖昧さのない逆元の表現として \(1/G\) を利用できる (ただし逆元が常に存在するとは限らない)。例えば、次のように \(I\), \(J\) を定めたとする:

\[ \begin{aligned} J &::= (1, -1, 0, 0, \ldots, 0, \ldots) \\ K &::= (1, 1, \ldots) \end{aligned} \]

このとき \(\otimes\) の定義より \(J \otimes K = I\) なので、\(K = 1 / J\) と \(J = 1/K\) が分かる。

等式 \(\text{(16.20)}\) より、形式的冪級数からなる環では零列 \(Z\) が逆元を持たないと分かる。そのため \(1/Z\) は定義されない ── 実数環あるいは第 9.7.1 項で定義した環 \(\mathbb{Z}_{n}\) で \(1/0\) が定義されないのと同様である。「無限列が逆元を持つ」と「最初の要素が \(0\) でない」が同値だと示すのはそれほど難しくない (問題 16.25)。

最後に、本章の最初に示した母関数の定義を正しく理解する方法を示そう:

\[ G(x) ::= \sum_{n=0}^{\infty} g_{n} x^{n} \]

この定義は、\(G(x)\) が形式的冪級数環の要素であることを意味するに過ぎない。つまり \(G(x)\) は実際には無限列 \((g_{0}, g_{1}, \ldots, )\) である。他にも、例えば式 \(x\) は次の無限列 \(X\) を意味すると解釈される:

\[ X ::= (0,\, 1,\, 0,\, 0,\, \ldots,\, 0,\, \ldots) \]

同様に、\(1 - x\) は上述した無限列 \(J\) の別表記と解釈される。また、次の見慣れた等式は、\(K\) が \(J\) の唯一の逆元 \(1/J\) であると主張している:

\[ \frac{1}{1 - x} = 1 + x + x^{2} + x^{3} + \cdots \tag{16.21}\]

言い換えれば、母関数の表記に含まれる変数 \(x\) は単なる装飾でしかない ── 畳み込み則を思い出すときに役に立つかもしれないが、それ以上の意味はない。等式 \(\text{(16.21)}\) は「\(x\) の値」や「無限級数の収束半径」といった概念と全く関係がなく、形式的冪級数環の二要素が満たす関係を示す。前項で考えた発散する母関数に関する議論も形式的冪級数の性質として完全に正当化される。

参考文献

[50], [25], [10], [20]

  1. 本節は mathoverflow に投稿された Use of everywhere divergent generating functions という質問に対する Aaron Meyerowitz の解答 (2010 年 11 月 12 日投稿) から着想を得た。 ↩︎

  2. 恒等式 \(\text{(16.17)}\) の組合せ論的証明は問題 15.72 に示した。 ↩︎

  3. 形式的冪級数環を構成する無限列の要素は実数ではなく複素数でも構わない。さらに一般的に言えば、任意の可換環の要素と考えることができる。 ↩︎

広告