Landau記号

$\newcommand{\NN}{\mathbb{N}}$ $\newcommand{\ZZ}{\mathbb{Z}}$ $\newcommand{\QQ}{\mathbb{Q}}$ $\newcommand{\RR}{\mathbb{R}}$ $\newcommand{\CC}{\mathbb{C}}$ $\newcommand{\abs}[1]{\left\lvert#1\right\rvert}$ $\newcommand{\wenvert}[1]{\left\lvert\left\lvert#1\right\rvert\right\rvert}$ $\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}$

本稿では、Landauの$o$記号と$O$記号、およびVinogradov記号について解説する。

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$$ ということができる。

定理

• $f(x)=C$ が定数関数ならば $f(x)=O(1)$.
• $f(x)=o(g(x))$ ならば $f(x)=O(g(x))$.
• $f(x)=O(g(x)), g(x)=O(h(x))$ ならば $f(x)=O(h(x))$.
• $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))$.
• $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)=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))$.
• $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))$.
• $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)$.
• $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)$$.

定理の証明

• $\abs{f(x)}\leq C$ なので $f(x)=O(1)$.
• $x\rightarrow x_0$ のとき $f(x)=o(g(x))$ となるならば、$x_0$ の近くでは、$\abs{f(x)}\<\abs{g(x)}$.
• $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)}$.
• 前者の場合、$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)}$.
• $\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)}$.
• $\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)}$.
• $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)}$.
• $\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.$$

• $\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.$$