跳慮跋考

興味も思考も行先不明

ランダウの記号でも定式化がしたい!

Taylor 展開とは平均値の定理を繰り返し用いる事によって適当に滑らかな函数の冪級数展開を与えるものですが、何も全ての項が必要になるとは限らなくて、そういう場合に残りの項については「今気にしない程度の大きさである事」だけ分かればよい訳です。
その為の記法が Landau の記号であって、例えば  e^x = 1 + x + \frac{1}{2!} x^2 + \cdots に於いて  x \to 0  x^2 と同程度に速く減衰する項をあまり気にしない時は  e^x = 1 + x + O(x^2) と書きます。
これが非常に便利ではあるのですが、同時に  O(x^2) で「 x^2 程度の何か」を指すというのは釈然としない記法でもあります。数学的に適当な事を書いている様な印象。しかし Landau の記号が指すものを集合と看做すならば、環  R 上のイデアル  I により  x \in R  R/I への射影したものを  x + I と書く様に、集合を足したりするが如き記法も無い訳ではありません。
 \frac{1}{x} O(x^2) = O(x) の筈ですから Laudau の記号がイデアルにはなりませんが、函数全体の線型部分空間と考えるとどうだろうか、というのがここからのお話です。


さて  X \mathbb{R}^n の部分集合とし、 X 上の実数値函数全体の集合を  \mathcal{F} と置きます。
 f, g \in \mathcal{F} に対して和を  (f+g)(x) = f(x) + g(x) \ (\forall x \in X) スカラー倍を  a \in \mathbb{R} について  (af)(x) = af(x) \ (\forall x \in X) と定めれば  \mathcal{F} は実線型空間となっています。また函数同士の積も  (fg)(x) = f(x) g(x) \ (\forall x \in X) で定義されます。
それから  x \to \infty の場合を別に扱うのは面倒なので、 \mathbb{R}^n \cup \{\infty\} を一点コンパクト化として  \overline{X}  \mathbb{R}^n \cup \{\infty\} 上での  X の閉包とします。これにより、例えば  X = \mathbb{R} の時  \infty \in \overline{X} となり*1、「 \infty の近傍」を使って極限の議論が可能になります。一般に  \overline{X} に於ける  a の近傍系を  \mathcal{N}(a) と書く事にします。

Landau の記号

 O_a(g) = \{\, f \in \mathcal{F} \mid \exists M > 0,\ \exists A \in \mathcal{N}(a),\ \forall x \in A \cap X,\ |f(x)| \le M |g(x)| \,\}
と定義する。また  \exists M > 0, でなく  \forall M > 0, としたものを  o_a(g) と定義する。

定義から直ちに  g \in O_a(g)  o_a(g) \subset O_a(g) が分かります。

 O_a(g) は要するに  a の十分近くに於いて  g の定数倍で抑えられる函数全体の集合であり、特に  g の値が  a 付近で  0 でない時は  f \in O_a(g) \Leftrightarrow \limsup_{x \to a} \frac{f(x)}{g(x)} \le \infty です。上極限が特に  0 の場合が  o_a(g) という事になります。

線型性

 O_a(g)  \mathcal{F} の線型部分空間である。

任意の  g \in \mathcal{F} に対して  0 \le 1 \cdot |g(x)| \ (\forall x \in X) より  0 \in O_a(g) である。
 f_1,\ f_2 \in O_a(g) とする。仮定より正実数  M_i a の近傍  A_i が存在し、  |f_i(x)| \le M_i |g(x)| \ (\forall x \in A_i) が成り立つ( i = 1,2 )。
任意の  c_1, c_2 \in \mathbb{R}  x \in A_1 \cap A_2 \cap X について
 |c_1 f_1(x) + c_2 f_2(x)| \le |c_1f_1(x)| + |c_2f_2(x)| \le (|c_1| M_1 + |c_2| M_2) |g(x)|
であり、 a \in \mathring{A}_1 \cap \mathring{A}_2 = (A_1 \cap A_2)^{\circ} より  A_1 \cap A_2  a の近傍なので、  c_1 f_1 + c_2 f_2 \in O_a(g) が成り立つ。

これにより商空間  \mathcal{F} / O_a(g) を考える事が出来ます。以下、標準全射  \mathcal{F} \to \mathcal{F} / O_a(g)  \pi_g と書く事にしましょう。また  O_a(g_1) \subset O_a(g_2) の場合は線型写像
 \mathcal{F}/O_a(g_1) \to \mathcal{F}/O_a(g_2),\ f + O_a(g_1) \mapsto f + O_a(g_2)
が誘導されますが、これを  \pi_{g_2,g_1} と書く事にします。
 f \in \mathcal{F} に対して同値類  \pi_g(f)  [f]  \overline{f} と書き表されるのが一般的に思いますが、  f + O_a(g) と書く場合もある様なのでそれを採用すると、あの曖昧模糊としていた Landau の記法がこうした同値類を表すものとして解釈出来そうだと分かってきます。
以下、Landau の記号に期待される性質がこの捉え方から導ける事を示しましょう。

同値性

 h \in o_a(g) ならば  O_a(g + h) = O_a(g) である。

 f \in O_a(g+h) とすると  |f(x)| \le M |g(x) + h(x)| \ (\forall x \in A \cap X) である(以下一々「  M > 0  A \in \mathcal{N}(a) が存在して~」という事を断らない)。
 h \in o_a(g) より例えば  |h(x)| \le 1 \cdot |g(x)| \ (\forall x \in A' \cap X) が成り立つので、  |f(x)| \le M(|g(x)| + |h(x)|) \le 2M |g(x)| \ (\forall x \in A \cap A' \cap X) となり  f \in O_a(g) である。
逆に  f \in O_a(g) とする。 \epsilon \in (0,1) に対して  |h(x)| \le \epsilon |g(x)| \ (\forall x \in A' \cap X) が成り立つので  |g(x) + h(x)| \ge |g(x)| - |h(x)| \ge (1 - \epsilon) |g(x)| である。 f \in O_a(g) より  |f(x)| \le M|g(x)| \ (\forall x \in A \cap X) なので、任意の  x \in A \cap A' \cap X に対し  |f(x)| \le \frac{M}{1-\epsilon} |g(x) + h(x)| が成り立つ。即ち  f \in O_a(g+h) である。

 O_a(g) = O_a(h) かつ  g, h  a の近くで  0 でないならば  O_a(1/g) = O_a(1/h) である。

 f \in O_a(1/g) とすると  |f(x)| \le M |g(x)|^{-1} \ (\forall x \in A \cap X) である。
 h \in O_a(h) = O_a(g) より  |h(x)| \le M' |g(x)| \ (\forall x \in A' \cap X) なので  |g(x)|^{-1} \le M' |h(x)|^{-1} が成り立つ。
すると  |f(x)| \le MM' |h(x)|^{-1} \ (\forall x \in A \cap A' \cap X) より  f \in O_a(1/h) である。
よって  f \in O_a(1/h) であり、逆も同様なので  O_a(1/g) = O_a(1/h) が成り立つ。

演算

 O_a(g_1) \subset O_a(g_2) ならば  (f_1 + O_a(g_1)) + (f_2 + O_a(g_2)) = f_1 + f_2 + O_a(g_2) である。

左辺を  \pi_{g_2,g_1}(f_1 + O_a(g_1)) + (f_2 + O_a(g_2)) と看做せば  \pi_{g_2} 線型写像である事から従う。

 f_i \in O_a(g_i) \ (i=1,2) ならば  f_1f_2 \in O_a(g_1g_2) である。

 f_i について  |f_i(x)| \le M_i |g_i(x)| \ (\forall x \in A_i \cap X) であり、この時任意の  x \in A_1 \cap A_2 について
 |f_1(x)f_2(x)| = |f_1(x)| |f_2(x)| \le M_1M_2 |g_1(x)| |g_2(x)| = M_1M_2 |g_1(x)g_2(x)|
が成り立つから、 f_1f_2 \in O_a(g_1g_2) である。

 h \in \mathcal{F} について  h \in O_a(h) であったので、 f \in O_a(g) に対して  fh \in O_a(gh) が成り立ち、  h写像  \mathcal{F} \to \mathcal{F},\ f \mapsto fh 写像  f + O_a(g) \mapsto fh + O_a(gh) を誘導する事が分かります。

 f_i \in O_a(g_i) \ (i=1,2) ならば  f_1 + f_2 \in O_a(|g_1| + |g_2|) である。

 f_i \in O_a(g_i) より  |f_i(x)| \le M_i |g_i(x)| \ (\forall x \in A_i \cap X) である。
 |f_1(x) + f_2(x)| \le |f_1(x)| + |f_2(x)| \le M_1 |g_1(x)| + M_2 |g_2(x)|
  \le \max \{ M_1, M_2 \} ( |g_1(x)| + |g_2(x)| ) \ (\forall x \in A_1 \cap A_2 \cap X) より  f_1 + f_2 \in O_a(|g_1| + |g_2|) が成り立つ。

特に  g_1  g_2 が打ち消し合わない限り  f_1 + f_2 \in O_a(g_1 + g_2) となります。

最後に  f_1 + O_a(g_1)  f_2 + O_a(g_2) の積を考えてみます。
 f_i + h_i \in \pi_{g_i}^{-1}(f_i + O_a(g_i)) \ (i = 1,2) と置くと  (f_1 + h_1) (f_2 + h_2) = f_1f_2 + f_1h_2 + f_2h_1 + h_1h_2 であり、  f_ih_j \in O_a(f_ig_j),\ h_1h_2 \in O_a(g_1g_2) より  f_1h_2 + f_2h_1 + h_1h_2 \in O_a(|f_1g_2| + |f_2g_1| + |g_1g_2|) となりますから、結局
 (f_1 + O_a(g_1)) (f_2 + O_a(g_2)) = f_1f_2 + O_a(|f_1g_2| + |f_2g_1| + |g_1g_2|)
が成り立っている事が分かります。

解析学の例

 X = (-\epsilon, \epsilon) \setminus \{0\} \subset \mathbb{R} \ \ (\epsilon > 0) として、 a = 0,\ g(x) = x^n \ (n \in \mathbb{N}) と置きます。 \overline{X} = [-\epsilon, \epsilon ] より  a \in \overline{X} なので  O_a(g) = O_0(x^n) が定義でき、これが通常  O(x^n) と書かれるものです。
 (1 - x)(1 + x + x^2 + \cdots + x^n) = 1 - x^{n+1} = 1 + O(x^{n+1}) であり(この二つ目の等号は、厳密には「左辺を  \pi_{x^{n+1}} で射影すると右辺になる」意です)、両辺を  \frac{1}{1-x} 倍すると  \frac{1}{1-x} = 1 + x + \cdots + x^n + O(\frac{x^{n+1}}{1-x}) となります。ここで  -x \in o(1) より  O(1-x) = O(1) なので  O(\frac{1}{1-x}) = O(1) であり、両辺を  x^{n+1} 倍する事で  O(\frac{x^{n+1}}{1-x}) = O(x^{n+1}) を得ますから  \frac{1}{1-x} = 1 + x + \cdots + x^n + O(x^{n+1}) が成り立ちます。この結果は  \frac{1}{1-x} の Taylor 展開や、等比級数の和の公式を  1, x, x^2, \cdots へ適用したものと一致しています(但しその場合は  x \to 0 の漸近挙動だけでなくて  |x| < 1 上の函数等式が得られます)。

計算量理論の例

 X = \mathbb{N} として、 a = \infty と置きます。 \mathbb{N} は離散位相を入れるとコンパクトでないから  \mathbb{N} \cup \{\infty\} 上で稠密であり、従って  \infty は実際に  1, 2, 3, \ldots の様な発散数列の極限となっています。 \{\, n \in \mathbb{N} \mid n > N \,\}_{N \in \mathbb{N}}  \infty の基本近傍系なので、今の場合は
 O_{\infty}(g) = \{\, f \in \mathcal{F} \mid \exists N \in \mathbb{N},\ \exists M > 0,\ n > N \implies |f(n)| \le M |g(n)| \,\}
が成り立ちます。計算量理論ではこれが通常  O(g(n)) と書かれるものです。
Wikipedia の記事 から例を拾ってくると、例えば  (n + O(n^{1/2})) (n + O(\log n))^2  (n + O(\log n))^2 = n^2 + O(|2n\log n| + |(\log n)^2|) = n^2 + O(n \log n) から
 (n + O(n^{1/2})) (n + O(\log n))^2 = (n + O(n^{1/2})) (n^2 + O(n \log n))
  = n^3 + O(|n^2 \log n| + |n^{5/2}| + |n^{3/2} \log n|) = n^3 + O(n^{5/2})
となります。

*1:一点コンパクト化だと  \lim_{x \to +\infty} x = \lim_{x \to -\infty} x になってしまいますが、まぁ正負の両方向を同時に考えたりはしないので問題無いでしょう。