Small-o notation

앞서 설명한 Big-O notation 과 같이 Small-o notation 또한 중요합니다. 이는 다음처럼 정의됩니다.

 

$f(x) = o(g(x)) \text{ as } x\rightarrow \infty$ 라는 것은 $$\lim_{x\rightarrow\infty}\frac{f(x)}{g(x)} =0$$ 을 의미한다.

 

따라서 앞서 보인 $$\lim_{x\rightarrow\infty}\frac{M(x)}{x} = 0$$ 은 $M(x) = o(x)$ 를 의미합니다.

 

더 일반적으로, $f(x) ~ g(x)$ 는 $f(x) = g(x) + o(g(x))$ 와 동치입니다. 이제 이를 통해 아래 정리를 증명하겠습니다.

 

$$M(x) = o(x) \text{ as } x\rightarrow \infty$$ 라면 $\psi (x) \sim x$ 이다.

 

Proof

우선, 다음을 보이겠습니다. $$\psi (x) = x\sum_{qd \leq x} \mu (d) f(q) + O(1) \quad (1)$$ 이 때, $f(n) = \sigma_0 (n) - \log n - 2\gamma$ 입니다. 이를 보이기 위해서는, 다음의 세 항등식에서 출발하는 것이 좋습니다. $$[x] = \sum_{n\leq x}1 ,\quad \psi (x) = \sum_{n\leq x}\Lambda (n), \quad 1 = \sum_{n\leq x}\left[\frac{1}{n}\right]$$ 그리고 시그마 안의 함수를 다음처럼 표현할 수 있습니다. $$1 = \sum_{d\mid n}\mu (d) \sigma_0 \left(\frac{n}{d}\right),\quad \Lambda (n) = \sum_{d\mid n}\mu (d) \log \frac{n}{d},\quad \left[\frac{1}{n}\right]=\sum_{d\mid n}\mu (d) $$ 그렇다면 $$\begin{align*}[x]-\psi (x) - 2\gamma &= \sum_{n\leq x}\left\{1 - \Lambda (n) - 2\gamma \left[\frac{1}{n}\right]\right\} \\ &= \sum_{n\leq x}\sum_{d\mid n}\mu (d) \left\{\sigma_0 \left(\frac{n}{d}\right) - \log \frac{n}{d} - 2\gamma\right\} \\ &= \sum_{qd \leq x}\mu (d) \left\{\sigma_0 (q) - \log q - 2\gamma\right\} = \sum_{qd\leq x}\mu (d) f(q)\end{align*}$$ 가 되어, (1) 이 보여집니다. 이제 $$\sum_{qd\leq x}\mu (d) f(q) = o(x)$$ 임을 보이면 증명이 완료됩니다. 이 글의 마지막 정리를 사용하면 $$\sum_{qd \leq x}\mu (d) f(q) = \sum_{n \leq b}\mu (n) F\left(\frac{x}{n}\right) + \sum_{n \leq a}f(n) M \left(\frac{x}{n}\right) - F(a)M(b)\quad (2)$$ 이 때 $a, b$ 는 $ab = x$ 인 임의의 양수입니다. 또, $$F(x) = \sum_{n \leq x}f(n)$$ 입니다. 이제 다음의 두 정리를 사용하겠습니다. $$\begin{align*}\sum_{n \leq x}\sigma_0 (n) = x \log x + (2\gamma -1 )x + O(\sqrt{x})\end{align*}$$ $$\sum_{n \leq x}\log n = \log [x]! = x \log x - x + O(\log x)$$ 그럼 $F(x)$ 는 $$\begin{align*}F(x) &= \sum_{n\leq x}\sigma_0 (n) - \sum_{n\leq x}\log n - 2\gamma \sum_{n\leq x}1 \\ &= x \log x + (2 \gamma -1 )x + O(\sqrt{x}) - \left(x \log x - x + O (\log x )\right) - 2\gamma x + O(1) \\ &= O(\sqrt{x}) + O(\log x) + O(1) = O(\sqrt{x})\end{align*}$$ 가 성립하고, 그러므로 어떤 상수 $B > 0$ 이 존재하여 $\left\vert F(x)\right\vert \leq B\sqrt{x}$ 가 모든 $x \geq 1$ 에 대해 성립합니다. 따라서 $$\left\vert\sum_{n\leq b}\mu (n) F \left(\frac{x}{n}\right)\right\vert \leq B \sum_{n\leq b}\sqrt{\frac{x}{n}} \leq A \sqrt{xb} = \frac{Ax}{\sqrt{a}}$$ 가 성립하는 상수 $A > B >0$ 이 존재합니다. 이제 임의의 $\epsilon > 0$ 에 대해 어떤 상수 $a > 1$ 가 존재하여 $$\frac{A}{\sqrt{a}} < \epsilon$$ 이 성립하게 할 수 있고, 이 때 $$\left\vert \sum_{n \leq b}\mu (n) F \left(\frac{x}{n}\right)\right\vert < \epsilon x \quad (3)$$ 이 성립합니다. $a$ 는 $x$ 가 아니라 $\epsilon$ 에 의존합니다. $M(x) = O(x)$ 임은 정의에 의해 자명하므로, 같은 $\epsilon > 0$ 에 대해 어떤 $c$ 가 존재하여 $x > c$ 일 때 $$\frac{\left\vert M(x)\right\vert}{x} < \frac{\epsilon}{K}$$ 가 되도록 할 수 있습니다. ( 이 때 $K$ 는 양수입니다. ) 따라서 $$\left\vert\sum_{n\leq a}f(n) M\left(\frac{x}{n}\right)\right\vert \leq \sum_{n\leq a}\left\vert f(n)\right\vert \frac{\epsilon}{K}\frac{x}{n} = \frac{\epsilon x}{K}\sum_{n\leq a}\frac{\left\vert f(n)\right\vert}{n}$$ 이 모든 $n \leq a$ 에 대해 $\frac{x}{n} > c$ 가 성립할 때 성립함을 알 수 있습니다. 즉, $x > ac$ 일 때 성립합니다. 이제 $$K = \sum_{n\leq a}\frac{\left\vert f(n)\right\vert}{n}$$ 이라고 하면, 위의 부등식은 $$\left\vert \sum_{n\leq a}f(n) M \left(\frac{x}{n}\right)\right\vert < \epsilon x \quad (4)$$ 가 $x > ac$ 일 때 성립하게 됩니다. 또, $$\left\vert F(a) M(b) \right\vert < A\sqrt{a}\left\vert M(b) \right\vert < A \sqrt{a}b < \epsilon \sqrt{a}\sqrt{a}b = \epsilon x\quad (5)$$ 가 성립하므로, $(3), (4), (5)$ 를 조합하면 $(2)$ 는 $$\left\vert\sum_{qd \leq x}\mu (d) f(q) \right\vert < 3\epsilon x$$ 가 $x > ac$ 일 때 성립합니다. 그런데 $a, c$ 는 $x$ 와 의존하지 않으므로 임의로 조건을 만족하게 설정할 수 있고, 따라서 증명이 완성됩니다.