インテジャーズ

INTEGERS

数、特に整数に関する記事。

数論的関数 ω(n)

この記事では数論的関数\omega (n)を導入して、定理を二つ証明します。

定義

定義 自然数nに対して、nの素因数全体のなす集合を\mathrm{prime}(n)と表す。ただし、\mathrm{prime}(1):=\emptyset

定義 自然数nに対して、\omega (n):=\#\mathrm{prime}(n)によって\omega (n)を定義する。

平均的振る舞い

\omega (n)の振る舞いは高度に非自明です。順調に値が大きくなっていくようなことは決してなく、nが素数のときは必ず\omega (n)=1となります。一方、平均的な振る舞いに関しては綺麗な公式が成り立ちます。証明にはChebyshevの定理およびMertensの第二定理を用います。

定理 ある実数Aが存在して
\displaystyle \sum_{n \leq x}\omega (n) = x\log \log x + Ax + O\left( \frac{x}{\log x} \right), \ (x \to \infty)
が成立する。

証明. 二重和の順番を入れ替えることによって

\displaystyle \sum_{n \leq x}\omega (n) = \sum_{n \leq x}\sum_{p \mid n}1 = \sum_{p\leq x}\left[ \frac{x}{p} \right]

を得る。ここで、pは素数であり、x以下のpの倍数の個数が[ x/p ] であることに注意。よって、Chebyshevの定理およびMertensの第二定理より

\begin{equation}\begin{split} \sum_{n \leq x} \omega (n) &= x\sum_{p \leq x}\frac{1}{p} - \sum_{ p\leq x}\left\{ \frac{x}{p} \right\} = x\sum_{p \leq x}\frac{1}{p} + O(\pi (x)) \\ &= x\log \log x +Ax +O\left( \frac{x}{\log x} \right)\end{split}\end{equation}

を得る。 Q.E.D.

\omega (n)とEulerのトーシェント関数\varphi (n)に関して成り立つ、割と(証明が)お気に入りの極限公式を紹介します:

定理 \ \ \ \displaystyle \lim_{n \to \infty}\frac{2^{\omega (n)}}{\varphi (n)} = 0.

トーシェント関数の一般公式によって、\displaystyle n=\prod_{p \mid n}p^{e_p}と素因数分解されるとき、

\displaystyle \frac{2^{\omega (n)}}{\varphi (n)} = \prod_{p \mid n}\frac{2}{p^{e_p-1}(p-1)}

が成り立ちます。

定理の証明. 任意にN \in \mathbb{N}をとって固定する。p_ii番目の素数を表すことにし、

p_i \leq 4N+1 < p_{l+1}

なるlをとる(このようなlは一意的に定まる)。1\leq i \leq lなるiに対し、

\displaystyle \frac{4}{p_i^{f_i-1}(p_i-1)} < \frac{1}{N} -①

を満たすようなf_i \in \mathbb{N}を一つずつ選び固定する(このような f_iは必ずとれる)。

\displaystyle M:= \prod_{i=1}^lp^{f_i}とおく。このとき、

\displaystyle n \geq M \Longrightarrow \frac{2^{\omega(n)}}{\varphi (n)} < \frac{1}{N}

を示せばよい。任意にn \geq Mを満たすnをとって

\displaystyle n=\prod_{i=1}^kp_i^{e_i}, \ (e_1 \geq 0, \dots, e_{k-1} \geq 0, e_k > 0)

と素因数分解する(指数に0を許しているものがあるため、k=\omega (n)とは限らないことに注意)。

k > lのとき: lの取り方から、

\displaystyle \frac{2^{\omega (n)}}{\varphi(n)} = \prod_{i=1, \ e_i > 0}^k\frac{2}{p_i^{e_i-1}(p_i-1)} \leq \frac{4}{p_k^{e_k-1}(p_k-1)} \leq \frac{4}{p_k-1} < \frac{1}{N}

となる。

k \leq lのとき: 1 \leq j \leq kであって、f_j \leq e_jを満たすようなものが存在する。実際、このようなjが存在しないと仮定すると、n < Mとなってnの取り方に反する。よって、①より

\displaystyle \frac{2^{\omega (n)}}{\varphi (n)} = \prod_{i=1, \ e_i > 0}^k\frac{2}{p_i^{e_i-1}(p_i-1)}\leq \frac{4}{p_j^{e_j-1}(p_j-1)} \leq \frac{4}{p_j^{f_j-1}(p_j-1)} < \frac{1}{N}

が成り立つ。 Q.E.D.

証明から、分子の2というのは重要ではなく、任意の正の実数aに対して

\displaystyle \lim_{n \to \infty}\frac{a^{\omega (n)}}{\varphi (n)} = 0

が成り立つことを同様に示せることがわかります。