インテジャーズ

インテジャーズ

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

チェビシェフの定理

この記事では素数定理の弱い版であるChebyshevの定理を証明します。素数定理やその他の定理の証明に必要となるので先に準備しておこうという記事です。

最初に、この記事を読むための前提知識となる記事をあげておきます:
integers.hatenablog.com
integers.hatenablog.com
integers.hatenablog.com
一つ目の記事内容は全部理解しておく必要がありますが、二つ目についてはLegendreの公式、三つ目については補題のみ用います。

\displaystyle \pi (x) := \sum_{p \leq x}1, \displaystyle \vartheta (x) := \sum_{p \leq x}\log xは既に素数定理の記事で取り扱いましたが、ここではもう一つの関数

\displaystyle \psi (x) := \sum_{p^m \leq x}\log p

を導入します(素数だけではなく、素数冪に関する和をとる)。

\displaystyle \psi (x) = \sum_{p \leq x}\left[ \frac{\log x}{\log p} \right] \log p = \sum_{m=1}^{\infty}\vartheta (x^{\frac{1}{m}})

が成り立つことは容易に確認できます。この記事でも、漸近挙動は全てx \to \inftyで考えます。

補題1 \ \ \ \psi (x) = \vartheta (x) +O(x^{\frac{1}{2}}\log^2 x).

証明. m \geq 2に対して、\vartheta(x^{\frac{1}{m}}) < x^{\frac{1}{m}}\log x \leq x^{\frac{1}{2}}\log xであり、\displaystyle \sum_{m \geq 2}\vartheta (x^{\frac{1}{m}})\displaystyle m > \left[ \frac{\log x}{\log 2} \right] のみを考えればよい有限和なので、

\displaystyle \psi (x) = \vartheta (x) + \sum_{m \geq 2}\vartheta (x^{\frac{1}{m}}) = \vartheta (x) + O(x^{\frac{1}{2}}\log^2 x).

Q.E.D.

素数定理 次の同値な漸近公式が成立する:
\displaystyle \pi (x) \sim \frac{x}{\log x}, \ \vartheta (x) \sim x, \ \psi (x) \sim x.

同値性の証明. 最初の二つが同値であることは素数定理の記事で証明した。補題1および\vartheta (x) \leq \psi (x)より後ろ二つが同値であることもわかる。 Q.E.D.

定義 正の数A, Bが存在して、十分大きいxに対して Ag(x) < f(x) < Bg(x)が成り立つとき、f(x) \asymp g(x)と書く。 f(x)およびg(x)xに関する正値関数。

次が素数定理の弱い版であるChebyshevの定理です:

Chebyshevの定理 \ \ \ \displaystyle \pi (x) \asymp \frac{x}{\log x}, \ \vartheta (x) \asymp x, \ \psi (x) \asymp x.

証明. 正の数A, Bが存在して、十分大きいxに対して\vartheta (x) < Axおよび\psi (x) > Bxが成り立つことを示せばよい。実際、これが示されれば、補題1および\vartheta (x) \leq \psi (x)によって後ろの二つが成り立つ。素数定理の記事で示した0 < \varepsilon < 1に対して成り立つ不等式


\displaystyle \frac{\vartheta (x)}{x} \leq \frac{\pi (x)\log x}{x} \leq \frac{1}{1-\varepsilon}\frac{\vartheta (x)}{x} + \frac{\log x}{x^{\varepsilon}}

によって、一つ目の漸近公式も成立する。

さて、Genocchi素数に関する記事で示した補題「x \geq 3ならばx\# < 2^{2x-3}」の対数をとれば、\vartheta (x) < (2x-3)\log 2が得られる。後は\psi (x) > Bxを示せばよい。\displaystyle \binom{2n}{n} = \prod_{p \leq 2n}p^{e_p}と素因数分解するとき、

\displaystyle e_p = \sum_{m=1}^{\infty} \left( \left[ \frac{2n}{p^m} \right] -2\left[ \frac{n}{p^m} \right] \right)

が成り立つ(これはLegendreの公式から従う)。括弧の中身は0または1しか値を取り得ない。また、和は実質有限和で\displaystyle m \leq \left[ \frac{\log 2n}{\log p} \right] までを考えればよい。よって、\displaystyle e_p \leq \left[ \frac{\log 2n}{\log p} \right] であり、

\displaystyle \log \binom{2n}{n} = \sum_{p \leq 2n}e_p\log p \leq \sum_{ p\leq 2n}\left[ \frac{\log 2n}{\log p} \right] \log p = \psi (2n)

が成り立つ。また、\displaystyle \binom{2n}{n} = \frac{(n+1)(n+2)\cdots (2n)}{1 \cdot 2 \cdots n} \geq 2^nなので、\psi (2n) \geq n \log 2が示された。よって、x \geq 2に対して、n = [ x/2 ] とおけば

\displaystyle \psi (x) \geq \psi (2n) \geq n\log 2 \geq \frac{1}{4}\log x

が得られる。 Q.E.D.

n番目の素数p_nの言葉に言い換えると次の定理が得られます:

定理 \ \ \ \ p_n \asymp n\log n.

証明. \displaystyle \pi (x) \asymp \frac{x}{\log x}より

\displaystyle n \asymp \frac{p_n}{\log p_n} -①

が得られる。自然対数をとれば、

\log n \asymp \log p_n - \log \log p_n.

両辺を\log p_nで割ることによって

\displaystyle \frac{\log n}{\log p_n} \asymp 1 - \frac{\log \log p_n}{\log p_n}.

第二項はn \to \infty0に収束するため、\log n \asymp \log p_nが分かる。①と組み合わせることによって証明が完了する。 Q.E.D.