Landau記号

概要

Landauの$o$記号と$O$記号、およびVinogradov記号は関数の漸近的な挙動を比較するときに用いられ、関数の増大や収束の速度、近似の精度などをあらわすのに利用することができる。本記事では、これらの記号について解説する。

$$\newcommand{abs}[1]{\left\lvert#1\right\rvert} \newcommand{floor}[1]{\left\lfloor#1\right\rfloor} \newcommand{ind}[0]{\mathrm{ind}} \newcommand{mmod}[1]{\ \left(\mathrm{mod}\ #1\right)} \newcommand{ord}[0]{\mathrm{ord}} \newcommand{rank}[0]{\mathrm{rank}} \newcommand{wenvert}[1]{\left\lvert\left\lvert#1\right\rvert\right\rvert} $$

Landauの$o$記号

$x_0$ を実数、複素数あるいは無限大とする。
$x\rightarrow x_0$ のとき $f(x)/g(x)\rightarrow 0$ となるとき
$$f(x)=o(g(x)) ~ (x\rightarrow x_0)$$
とかく。また $(f(x)-g(x))/h(x)\rightarrow 0$ となるとき
$$f(x)=g(x)+o(h(x)) ~ (x\rightarrow x_0)$$
とかく。これをLandauの$o$記号という。
たとえば
$$x^2+x+1=o(x^3) ~ (x\rightarrow\infty)$$
かつ
$$x^2+x+1=x^2+o(x^2) ~ (x\rightarrow\infty)$$
が成り立つ。

$f(x)=o(g(x))$ のとき、$f(x)$ は $g(x)$ に比べて無視できるほど小さいといえる。
また $f(x)=g(x)+o(h(x))$ のとき、$f(x)$ と $g(x)$ の差は $h(x)$ に比べて無視できるほど小さいといえる。

より一般に、$f(x)=g(\lambda(x)h(x))$ かつ $\lambda(x)\rightarrow 0$ となる関数 $\lambda(x)$ が存在するとき
$$f(x)=g(o(h(x))) ~ (x\rightarrow x_0)$$
とかく。
たとえば
$$x^2+x+1=(1+o(1))x^2 ~ (x\rightarrow\infty)$$
が成り立つ。また、
$$\log x=x^{\log\log x/\log x}$$
かつ
$$\log\log x/\log x\rightarrow 0 ~ (x\rightarrow +\infty)$$
であるから
$$\log x=x^{o(1)} ~ (x\rightarrow +\infty)$$
が成り立つ。

$$f(x)=(1+o(1))g(x)$$
が成り立つとき、$f(x)$ と $g(x)$ は漸近的に等しいといい、
$$f(x)\sim g(x)$$
であらわす。たとえば
$$\frac{1}{1-x}-(1+x)\sim x^2 ~ (x\rightarrow 0)$$
が成り立つ。また、$\pi(x)$ を $x$ 以下の素数の個数とすると、素数定理は
$$\pi(x)\sim \frac{x}{\log x}$$
とあらわされる。

$f(x, y), g(x, y)$ が $2$ 変数関数で、各 $y$ について $x\rightarrow x_0$ のとき $f(x, y)/g(x, y)\rightarrow 0$ となるが、
$0$ に近づく速度が $y$ に依存するとき
$$f(x, y)=o_y(g(x, y))$$
であらわす。たとえば、$\epsilon>0$ について、$x\rightarrow +\infty$ のとき
$$\log x=o_\epsilon(x^\epsilon)$$
となる。

数列の場合は $\lim_{n\rightarrow\infty} a_n/b_n=0$ のとき
$$a_n=o(b_n)$$
とあらわす。

Landauの$O$記号

$x_0$ を実数、複素数あるいは無限大とする。
$x$ が $x_0$ に近いとき $\abs{f(x)/g(x)}\leq C$ となる定数 $C$ が存在するとき、
$$f(x)=O(g(x)) ~ (x\rightarrow x_0)$$
とかく。このことは $x$ が $x_0$ に近いとき $\abs{g(x)/f(x)}\geq C$ となる正の定数 $C>0$ が存在することと同値である。

また $x$ が $x_0$ に近いとき $\abs{(f(x)-g(x))/h(x)}\leq C$ となる定数 $C$ が存在するとき、
$$f(x)=g(x)+O(h(x)) ~ (x\rightarrow x_0)$$
とかく。たとえば
$$\sin x=O(x), 2x+1+\frac{1}{x}=O(x) ~ (x\rightarrow \infty)$$
が成り立つ。これをLandauの$O$記号という。

$f(x)=O(g(x))$ を
$$f(x)\ll g(x) ~ (x\rightarrow x_0)$$
あるいは
$$g(x)\gg f(x) ~ (x\rightarrow x_0)$$
とかくこともある。これらはVinogradov記号という。

$f(x, y), g(x, y)$ が $2$ 変数関数で、各 $y$ について $x$ が $x_0$ に近いとき $\abs{f(x, y)}\leq C(y)\abs{g(x, y)}$ となる、
$x$ に依存しないが $y$ に依存する定数 $C$ が存在するとき、
$$f(x, y)=O_y(g(x, y))$$
あるいは
$$f(x, y)\ll_y g(x, y)$$
であらわす。

Hardy-Littlewoodの$\Omega$記号

HardyとLittlewoodは、ある定数 $C>0$ について、
$$\abs{f(x)}>C\abs{g(x)}$$
となる $x$ で、いくらでも $x_0$ に近いものが存在することを、
$$f(x)=\Omega(g(x))$$
とあらわした。また、派生して
ある定数 $C>0$ について、
$$f(x)>Cg(x)$$
となる $x$ で、いくらでも $x_0$ に近いものが存在することを、
$$f(x)=\Omega_+(g(x))$$
とあらわし、
ある定数 $C<0$ について、
$$f(x)< Cg(x)$$
となる $x$ で、いくらでも $x_0$ に近いものが存在することを、
$$f(x)=\Omega_-(g(x))$$
とあらわす。すなわち
$$f(x)=\Omega(g(x))\Longleftrightarrow \limsup\abs{\frac{f(x)}{g(x)}}>0,$$
$$f(x)=\Omega_+(g(x))\Longleftrightarrow \limsup \frac{f(x)}{g(x)}>0,$$
$$f(x)=\Omega_-(g(x))\Longleftrightarrow \liminf \frac{f(x)}{g(x)}<0$$
ということができる。

  1. $f(x)=C$ が定数関数ならば $f(x)=O(1)$.
  2. $f(x)=o(g(x))$ ならば $f(x)=O(g(x))$.
  3. $f(x)=O(g(x)), g(x)=O(h(x))$ ならば $f(x)=O(h(x))$.
  4. $f(x)=o(g(x)), g(x)=O(h(x))$ または $f(x)=O(g(x)), g(x)=o(h(x))$ ならば $f(x)=o(h(x))$.
  5. $f_1(x)=o(g_1(x))$, $f_2(x)=o(g_2(x))$ ならば $kf_1(x)+\ell f_2(x)=o(g_1(x)+g_2(x))$.
  6. $f_1(x)=O(g_1(x))$, $f_2(x)=O(g_2(x))$ ならば $kf_1(x)+\ell f_2(x)=O(g_1(x)+g_2(x)), f_1(x) f_2(x)=O(g_1(x) g_2(x)), f_1(x)/g_2(x)=O(g_1(x)/f_2(x))$.
  7. $f_1(x)=O(g_1(x))$, $f_2(x)=o(g_2(x))$ ならば $f_1(x) f_2(x)=o(g_1(x) g_2(x))$.
  8. $b_n$ が非負の実数列で $a_n=o(b_n)$ かつ $\sum_{k=1}^\infty b_k=+\infty$ のとき $\sum_{k=1}^n a_n=o(\sum_{k=1}^n b_n)$.
  9. $f(x), g(x)$ が $x\geq a$ で定義された関数で $g(x)\geq 0 ~ (x\geq a)$, $f(x)=o(g(x)) ~ (x\rightarrow +\infty)$ かつ $\int_a^\infty g(t)dt=+\infty$ のとき
    $$\int_a^x f(t)dt=o\left(\int_a^x g(t)dt\right)$$.
  1. $\abs{f(x)}\leq C$ なので $f(x)=O(1)$.
  2. $x\rightarrow x_0$ のとき $f(x)=o(g(x))$ となるならば、$x_0$ の近くでは、$\abs{f(x)}\<\abs{g(x)}$.
  3. $x_0$ の近くで $\abs{f(x)}< C_1\abs{g(x)}, \abs{g(x)}< C_2\abs{h(x)}$ となる定数 $C_1, C_2$ が存在するので $\abs{f(x)}< C_1 C_2\abs{h(x)}$.
  4. 前者の場合、$x_0$ の近くで $\abs{g(x)}< C\abs{h(x)}$ となる定数 $C$ が存在する。$\epsilon>0$ とすると、$x_0$ の近くで $\abs{f(x)}<(\epsilon/C)\abs{g(x)}$ となるから、$\abs{f(x)}<\epsilon\abs{h(x)}$.
  5. $\ell>0$ とすると、$x_0$ の近くで $\abs{f_1(x)}<(\epsilon/k)\abs{g_1(x)}, \abs{f_2(x)}<(\epsilon/\ell)\abs{g_2(x)}$ となるから $\abs{kf_1(x)+\ell f_2(x)}< k\epsilon\abs{g_1(x)+g_2(x)}$.
  6. $\ell>0$ とすると、$x_0$ の近くで $\abs{f_1(x)}< C_1\abs{g_1(x)}, \abs{f_2(x)}< C_2\abs{g_2(x)}$ となるから $\abs{kf_1(x)+\ell f_2(x)}<(kC_1+\ell C_2)\abs{g_1(x)+g_2(x)}$, $\abs{f_1(x) f_2(x)}< C_1 C_2\abs{g_1(x) g_2(x)}$, かつ $\abs{f_1(x)/g_2(x)}< C_1 C_2\abs{g_1(x)/f_2(x)}$.
  7. $x_0$ の近くで $\abs{f_1(x)}< C\abs{g_1(x)}$ となる。$\epsilon>0$ とすると、$x_0$ の近くで $\abs{f_2(x)}<(\epsilon/C)\abs{g_2(x)}$ となるので、$\abs{f_1(x) f_2(x)}<\epsilon<\abs{g_1(x)g_2(x)}$.
  8. $\epsilon>0$ とすると、$n>n_0$ のとき、必ず $\abs{a_n}<(\epsilon/2)\abs{b_n}$ となる $n_0$ がとれる。よって $n>n_0$ のとき
    $\abs{\sum_{k=n_0+1}^n a_k}<(\epsilon/2)\sum_{k=1}^n b_k$ となる。
    $\sum_{k=1}^\infty b_k=+\infty$ だから、$\abs{\sum_{k=1}^{n_0} a_k}<(\epsilon/2)\sum_{k=1}^{n_1} b_k$ となる $n_1$ がとれる。よって $n>\max\{n_0, n_1\}$ のとき
    $$\abs{\sum_{k=1}^n a_k}<\abs{\sum_{k=1}^{n_0} a_k}+\abs{\sum_{k=n_0+1}^n a_k}<\frac{\epsilon}{2}\left(\sum_{k=1}^{n_1} b_k+\sum_{k=n_0+1}^n b_k\right)<\epsilon\sum_{k=1}^n b_k.$$
  9. $\epsilon>0$ とすると、$x>x_0$ のとき、必ず $\abs{f(x)}<(\epsilon/2)\abs{g(x)}$ となる $n_0$ がとれる。よって $x>x_0$ のとき
    $\abs{\int_{x_0}^x f(t)dt}<(\epsilon/2)\int_{x_0}^x g(t)dt$ となる。
    $\int_a^\infty g(t)dt=+\infty$ だから、$\abs{\int_a^{x_0}f(t)dt}<(\epsilon/2)\int_a^{x_1} g(t)dt$ となる $x_1$ がとれる。よって $x>\max\{x_0, x_1\}$ のとき
    $$\abs{\int_a^x f(t)dt}<\abs{\int_a^{x_0} f(t)dt}+\abs{\int_{x_0}^x f(t)dt}<\frac{\epsilon}{2}\left(\int_a^{x_1} g(t)dt+\int_{x_0}^x g(t)dt\right)<\epsilon\int_a^x g(t)dt.$$
Mathpediaを支援する
Landau記号