双子素数予想に関するErdősの結果
参考文献
Erdős. P. 1940 The difference of consecutive primes. Duke Math. J. 6, 438--441.projecteuclid.org
素数の間隔の平均値
素数\begin{equation*}
p_+-p=2
\end{equation*}を満たす素数
に対して区間
]にある素数を下から順に
と書きます。このとき素数定理から
\begin{equation*}
r = \frac{N}{\log N}(1+o(1) ) \quad (N \to \infty)
\end{equation*}がわかります。特に任意の に対して
が十分大きいとき
\begin{equation}
r > \frac{N}{\log N} (1-\varepsilon) \label{eq1}
\end{equation}が成立します。また ]の素数の間隔を全て足し合わせると
\begin{equation}
\sum_{i=1}^{r-1} (p_{i+1}-p_i ) = p_r -p_1 < N \label{eq2}
\end{equation}がわかります。ここで に対し
\begin{equation*}
p_{i+1}-p_i > (1+\delta)\log N \quad (i=1,\dots, r-1)
\end{equation*}が成立しているなら\eqref{eq1}から十分小さい と十分大きい
に対して
\begin{equation*}
\sum_{i=1}^{r-1} (p_{i+1}-p_i) >N
\end{equation*}が成立することが分かりますが、これは\eqref{eq2}に矛盾します。
従って任意の に対して
が十分大きければ
\begin{equation*}
p_{i+1}-p_i \le (1+\delta) \log N < (1+\delta) \log p_i
\end{equation*}が成り立つ が存在します。従って特に次が成立します。
Theorem1
\begin{equation*}
\liminf_{p \to \infty} \frac{p_+-p}{\log p} \le 1
\end{equation*}
双子素数予想へのアプローチ
双子素数予想は自明に
\begin{equation*}
\liminf_{p\to \infty} (p_+-p) =2
\end{equation*}と同値です。もし
\begin{equation*}
\liminf_{p\to \infty}(p_+-p) < \infty
\end{equation*}がわかると明らかに
\begin{equation*}
\liminf_{p\to \infty} \frac{p_+-p}{\log p} =0
\end{equation*}です。一方で素数定理からはTheorem1が得られています。なので順当に考えると
\begin{equation}
\liminf_{p\to \infty} \frac{p_+ -p}{\log p} <1 \label{eq3}
\end{equation}を示すことが最初の目標になります。このような結果を最初に無条件で証明したのはPaul. Erdősです。本記事ではErdősによる\eqref{eq3}の証明*1について紹介します。
実際に\eqref{eq3}の証明を行う前に前述の値
\begin{equation*}
E_1 = \liminf_{p\to \infty} (p_+-p) \text{ 及び } E_2 = \liminf_{p\to \infty} \frac{p_+-p}{\log p}
\end{equation*}の評価の変遷を紹介。前述のとおり素数定理からは が簡単に導出でき、非自明な結果をいくつかピックアップすると
の方は
\begin{align*}
&E_2 < 1 \quad &&\text{(P. Erdős, 1940)}\\
&E_2< \frac{1}{2} \quad &&\text{(Bombieri, Davenport, 1965)}\\
&E_2=0 \quad &&\text{(Goldston, Pimtz, Yıldırım, 2009)} \\
\end{align*}の方は
\begin{align*}
&E_1 < 70000000 \quad &&\text{(Y. Zhang, 2014)}\\
&E_1 \le 600 \quad &&\text{(J. Maynard, 2015)}
\end{align*}などがあります。現在の世界記録は だそうです。本記事で紹介するErdősによる最初の結果は篩法で得られる双子素数の個数に関する結果を用いてThoerem1の証明をもじった初等的なものです。BombieriとDavenportによる1965年の結果ではHardy-Littlewoodの円周法とBombieri-Vinogradovの平均素数定理が基本的なツールです。Goldston, Pintz, Yıldırımによる2009年の結果では円周法を用いず篩法のみで計算しており、著者の頭文字を取ってGPYの篩などと呼ばれています。ZhangやMaynardによる結果はGPYの篩の手法を継承していますが、特にMaynardの結果は有名です。
Erdősによる(3)の証明
以下、記号等は概ねErdősの原論文に沿って議論します。次が主定理です。
Theorem2
ある が存在して
\begin{equation*}
\liminf_{p\to \infty} \frac{p_+-p}{\log p} {<} 1-c_1
\end{equation*}が成立する。
Theorem2の証明に向けて二つ補題を用意します。
Lemma3
ある定数 が存在して任意の正整数
に対して方程式
\begin{equation*}
a=p_i-p_j \quad ( p_i,p_j \le n)
\end{equation*}を満たす素数 の数は上から
\begin{equation*}< c_2 \prod_{p|a} \left(1+\frac{1}{p}\right) \frac{n}{(\log n)^2}
\end{equation*}と評価できる。
証明 求める方程式の解の個数は
\begin{equation*}
\pi_a(n) = \{ p\le n-a \; | \; p+a : \text{素数} \}
\end{equation*}と書ける。が奇数のときは
しかあり得ないので所望の評価は自明である。
が偶数のときSelbergの篩 - プライムスのTheorem4から
\begin{equation*}
\pi_a(n) \ll \prod_{2{<}p|a} \frac{p-1}{p-2} \frac{n}{(\log n)^2}
\end{equation*}が成立する。従って
\begin{equation*}
\prod_{2{<}p|a} \frac{p-1}{p-2} \ll \prod_{2{<}p|a} \left(1+\frac{1}{p}\right)
\end{equation*}が得られれば所望の不等式が得られるが、これは
\begin{align*}
\prod_{2 {<} p|a} \frac{(p-1)p}{(p-2)(p+1)} &= \prod_{2{<}p|a} \left( 1+\frac{2}{(p-2)(p+1)}\right) \ll 1
\end{align*}より成立する。(QED)
Lemma4
とし
\begin{equation*}
\sum_a' = \sum_{(1-c_3)\log n \le a \le (1+c_3)\log n}
\end{equation*}と書くことにする。このとき が十分小さいければ\begin{equation*}
\sum_a' \prod_{p|a} \left( 1+\frac{1}{p} \right) {<} \frac{1}{6c_2} \log n
\end{equation*}が十分大きい で成立する。
証明 をMöbius関数として
\begin{align*}
\sum_a' \prod_{p|a} \left( 1+\frac{1}{p} \right) &=\sum_a' \sum_{d|a} \frac{\mu(d)^2}{d} \\
&=\sum_{d \le (1+c_3)\log n} \frac{\mu(d)^2}{d} \sum_{d|a}' 1
\end{align*}が成立。最後の和は
\begin{align*}
\sum_{d|a}'1 = \left[ \frac{(1+c_3)\log n- (1-c_3)\log n}{d} \right] \le \frac{2c_3\log n}{d} +1
\end{align*}なので
\begin{align*}
&\sum_a' \prod_{p|a} \left( 1+\frac{1}{p} \right) \\
&\le 2c_3(\log n) \sum_{d\le (1+c_3)\log n} \frac{\mu(d)^2}{d^2} +\sum_{d\le(1+ c_3)\log n} \frac{\mu(d)^2}{d} \\
\end{align*}一つ目の の和は収束するので収束値を
と置く。二つ目の
の和は
\begin{equation*}
\le \log (1+c_3)+\log \log n
\end{equation*}なので結局
\begin{equation*}
\sum_{a}'\prod_{p|a} \left(1+\frac{1}{p}\right) \le \left(2Dc_3 +\frac{\log (1+c_3)+\log \log n}{\log n}\right) \log n
\end{equation*}となる。従って を十分小さくとれば所望の不等式が得られる。(QED)
以上で準備完了です。Theorem2を証明します。
Theorem2の証明 区間 ]における素数を小さい順に
と書く。さらに
\begin{equation*}
b_i = p_{i+1}-p_i \quad (i=1,\dots , x-1)
\end{equation*}と置く。Theorem1の議論と同様にして任意の に対して
が十分大なら
\begin{equation}
x >\left(\frac{1}{2}-\varepsilon \right) \frac{n}{\log n} \label{main eq1}
\end{equation}及び
\begin{equation}
\sum_{i=1}^{x-1} b_i < \frac{n}{2} \label{main eq2}
\end{equation}が成立することがわかる。またLemma3,4を用いれば
\begin{equation*}
(1-c_3)\log n\le b_i \le (1+c_3)\log n
\end{equation*}を満たす の数は上から
\begin{equation}
\le \sum_a' c_2 \prod_{p|a} \left(1+\frac{1}{p} \right) \frac{n}{(\log n)^2} \le \frac{n}{6\log n} \label{main eq3}
\end{equation}と評価できる。今 の集合を
\begin{align*}
&A=\{ b_i\; {|} \; b_i \le (1-c_3)\log n \} \\
&B= \{ b_i \; {|} \; (1-c_3)\log n \le b_i \le (1+c_3)\log n \} \\
&C= \{ b_i \; {|} \; b_i > (1+c_3)\log n \}
\end{align*}と三つに互いに素な三つの集合に分ける。もし仮に が空集合なら
なので\eqref{main eq1}と\eqref{main eq3}から
\begin{equation*}
{|}C| = x- |B|- 1> \left(\frac{1}{3}-\varepsilon \right) \frac{n}{\log n} -1
\end{equation*}が成立。従って を十分小さく取れば
\begin{align*}
\sum_{i=1}^{x-1}b_i &= \sum_{b_i \in B} b_i + \sum_{b_i \in C} b_i \\
& > (1-c_3)(\log n) |B| + (1+c_3)(\log n) |C| \\
& = (1-c_3)(\log n) (x-1-|C|) +(1+c_3)(\log n) |C| \\
& = (1-c_3) (x-1) \log n +2c_3(\log n) |C| \\
& > \left (\frac{1}{2} + \frac{c_3}{6} - (c_3+1)\varepsilon - o(1) \right)n > \frac{n}{2}
\end{align*}が十分大きい で成立。これは\eqref{main eq2}に矛盾する。従って
が十分大なら
は空集合出ない、つまり
\begin{equation*}
b_i = p_{i+1}-p_i < (1-c_3)\log n
\end{equation*}を満たす が存在する。従って
\begin{equation*}
\liminf_{p\to \infty} \frac{p_+-p}{\log p} < 1-c_3
\end{equation*}がわかる。(QED)
おわりに
もともとはMaynardの結果*2を紹介するつもりだったのですが、Maynardの手法はいくらか予備知識を仮定すれば計算自体は簡単な微積分と線形代数のみで扱うことが出来ます。ただブログとして書き起こすには非常に面倒くさい文量です。そもそもMaynardの論文自体はアクセスが容易なので、それならと思い立ち一番最初の結果を紹介することにしました。このあたりの篩法の計算*3を追えるならMaynardの論文も大体読めると思うので、興味があったらどうぞ。
*1:Erdős. P. 1940 The difference of consecutive primes. Duke Math. J. 6, 438--441.
Selbergの篩
Selbergの篩について解説します。
応用として双子素数の個数を計算します。
参考文献
リンク
リンク
リンク
篩法の問題設定
\begin{equation*}
\mathcal{A}_d =\{ a \in \mathcal{A} \; | \; a \equiv 0 \; (\text{mod} \; d ) \}
\end{equation*}とします。さらにパラメータ
\begin{equation*}
P(z) = \prod_{ p < z } p \quad (p \text{は素数})
\end{equation*}とし
目標は の評価です。今回はSelbergによって導入された
の上からの評価の方法を紹介します。
もちろん に対してなんら仮定なしに計算することはできないので、任意の
に対して
\begin{equation}
{|}\mathcal{A}_d |= \frac{\rho(d)}{d} X +R_d \label{hypo}
\end{equation}と書けるものと仮定して計算を行います。ここで は
を満たす乗法的関数とし、
かつ
が成り立っているものとします。
なぜ を、またなぜこのような設定で計算するかは以下の記事にて詳しく解説しています。
mathnote.info
注意としてMöbius関数 の基本公式
\begin{equation*}
\sum_{d|n} \mu(d) =
\begin{cases}
1 \quad &(n=1) \\
0 \quad &(n\neq 1)
\end{cases}
\end{equation*}を用いると
\begin{equation}
S(\mathcal{A},z) = \sum_{\substack{a \in \mathcal{A} \\ (a,P(z))=1}} 1 =\sum_{a \in \mathcal{A}} \sum_{d| (a, P(z))} \mu(d) \label{S(A,z)}
\end{equation}と書くことが出来ます。
Selbergの上界篩
Selbergの篩はそれ単体ではLemma1
を
を満たす任意の実数列とする。このとき
\begin{equation*}
\sum_{d|n} \mu(d) \le \left( \sum_{d|n} \lambda_d \right)^2
\end{equation*}が成立する。
証明 のときは両辺1となり、
のときはMöbiusの基本公式から左辺が0なので自明に成立する。(QED)
Lemma1から を計算する方法がSelbergの篩です。
の計算に入る前に一つ有用な反転公式を用意しておきます。
Lemma2
とし数論的関数
は
を満たすとする。このとき
\begin{equation*}
g(d)=\sum_{d|n} f(n) \; \Rightarrow \; f(d) = \sum_{d|n} \mu\left(\frac{n}{d} \right) g(n)
\end{equation*}が成立する。
証明 整数 に対して
\begin{align*}
\sum_{d|n}\mu\left( \frac{n}{d} \right) g(n) &= \sum_{d|n}\mu \left( \frac{n}{d} \right) \sum_{n|m} f(m) \\
&= \sum_{d|m}f(m) \sum_{d|n, n|m} \mu \left( \frac{n}{d} \right) \\
&= \sum_{l} f(ld) \sum_{d|n , n|ld}\mu \left(\frac{n}{d} \right) \\
&= \sum_{l}f(ld) \sum_{m|l} \mu(m)
\end{align*}ここで3行目の和において 、4行目の和において
と変数変換した。最後の和はMöbius関数の基本公式から
のとき1となりそれ以外は0なので最後の行は
に一致する。(QED)
Theorem3 (Selbergの篩)
を
\begin{equation*}
g(d) = \prod_{p |d} \frac{\rho(p)}{p-\rho(p)}, \; G(z) = \sum_{\substack{d|P(z) \\ d {<}z}} g(d)
\end{equation*}と定める。このとき\eqref{hypo}の下で
\begin{equation*}
S(\mathcal{A},z) \le \frac{X}{G(z)} + \sum_{\substack{d_1,d_2 | P(z) \\ d_1,d_2 {<} z}} \rho([d_1,d_2])
\end{equation*}が成立する。
証明 Lemma1と\eqref{S(A,z)}から を満たす任意の実数列
に対し
\begin{align}
S(\mathcal{A},z) &\le \sum_{a\in \mathcal{A}} \left(\sum_{d|a,P(z)} \lambda_d \right)^2 \notag \\
& = \sum_{d_1, d_2} \lambda_{d_1}\lambda_{d_2} |\mathcal{A}_{[d_1,d_2]}| \notag \\
&= XS + R \label{equation1}
\end{align}
が成立。ここで
\begin{equation*}
S = \sum_{d_1,d_2} \lambda_{d_1}\lambda_{d_2}\frac{\rho([d_1,d_2])}{[d_1,d_2]}
\end{equation*}\begin{equation*}
R=\sum_{d_1,d_2} \lambda_{d_1} \lambda_{d_2} R_{[d_1,d_2]}
\end{equation*}とおいた。は乗法的関数なので
\begin{align*}
S &= \sum_{d_1,d_2} \frac{\lambda_{d_1}\rho(d_1)}{d_1} \frac{\lambda_{d_2}\rho(d_2)}{d_2} \frac{(d_1,d_2)}{\rho({(}d_1,d_2){)}} \\
&= \sum_{d_1,d_2} \frac{\lambda_{d_1}\rho(d_1)}{d_1} \frac{\lambda_{d_2}\rho(d_2)}{d_2} \prod_{p|d_1,d_2} \left( 1+g(p)^{-1} \right) \\
&= \sum_{d_1,d_2} \frac{\lambda_{d_1}\rho(d_1)}{d_1} \frac{\lambda_{d_2}\rho(d_2)}{d_2}\sum_{d|d_1,d_2} g(d)^{-1} \\
&= \sum_{\substack{d|P(z) \\ d{<}z}} g(d)^{-1} \left( \sum_{d|e} \frac{\lambda_{e} \rho(e)}{e} \right)^2
\end{align*}
が成立。そこで
\begin{equation*}
\xi_d= \sum_{d|e} \frac{\lambda_e \rho(e)}{e}
\end{equation*}とおくとLemma2から
\begin{equation}
\frac{\lambda_d \rho (d)}{d} = \sum_{d|e} \mu \left( \frac{e}{d} \right) \xi_e \label{weight}
\end{equation}が成立する。したがって を決めるためには\eqref{weight}の下で
\begin{equation*}
S= \sum_{\substack{d|P(z)\\ d {<} z}} \frac{\xi_d^2}{g(d)}
\end{equation*}を最小にする を決定すればよい。\eqref{weight}で
のときの場合にコーシー・シュワルツの不等式を用いると
\begin{align*}
1&= \left( \sum_{e}\mu (e) \xi_e \right)^2 = \left( \sum_{e} \frac{\mu(e) \xi_e}{\sqrt{g(e)}} \sqrt{g(e)} \right)^2 \\
& \le \left(\sum_{\substack{e|P(z) \\ e {<}z }}\frac{\xi_e^2}{g(e)} \right) \left(\sum_{\substack{e|P(z) \\ e {<} z}}g(e) \right) = SG(z)
\end{align*}したがって の選び方に依らず
が成立するが、この不等式が等式になるように
を選べば最良になる。再び\eqref{weight}の
のときを用いると
\begin{align*}
S - G(z)^{-1} &= G(z)^{-1} \left(G(z) \sum_{d{<}z} \frac{\xi_d^2}{g(d)} -1 \right)\\
&= G(z)^{-1} \left(G(z) \sum_{d{<}z} \frac{\xi_d^2}{g(d)} -\sum_{d{<}z} \mu(d)\xi_d \right) \\
&= \sum_{d{<}z} \frac{\xi_d}{g(d)} \left( \xi_d - \frac{\mu(d)g(d)}{G(z)} \right)
\end{align*}
したがって に対し
\begin{equation*}
\xi_d = \frac{\mu(d)g(d)}{G(z)}
\end{equation*}すなわち
\begin{align}
\lambda_d &= \frac{d}{\rho(d)}\sum_{ \substack{e {<} z \\ d|e }} \mu\left( \frac{e}{d} \right) \frac{\mu(e)g(e)}{G(z)} \notag \\
&= \frac{\mu(d)}{G(z)} \prod_{p|d} \frac{p}{p-\rho(p)} \sum_{\substack{m {<} z/d \\ (m,d)=1 }} \mu(m)^2 g(m) \label{lambda}
\end{align}とすれば\eqref{equation1}から
\begin{equation*}
S(\mathcal{A},z) \le XS+R = \frac{X}{G(z)} + R
\end{equation*}が得られる。もし が成立すれば明らかに
\begin{equation*}
R \le \sum_{\substack{d_1,d_2 | P(z) \\ d_1,d_2 {<} z}} \rho ([d_1,d_2])
\end{equation*}が成立しTheorem3が成り立つことが確かめられるので、以下 を示す。
に対し
\begin{align*}
G(z) &= \sum_{n{<}z} \mu(n)^2 g(n) \\
&= \sum_{l|d} \sum_{\substack{n {<} z \\ (n,d)=l}}\mu(n)^2 g(n)\\
&= \sum_{l|d} \mu(l)^2 g(l) \sum_{\substack{ m{<}z/l \\ (m,d)=1}}\mu(m)^2 g(m) \\
& \ge \sum_{l|d} \mu(l)^2 g(l) \sum_{\substack{ m{<}z/d \\ (m,d)=1}}\mu(m)^2 g(m) \\
& = \prod_{p|d} \frac{p}{p-\rho(p)} \sum_{\substack{m{<}z/d \\ (m,d)=1}} \mu(m)^2 g(m)
\end{align*}となるが最後の式は\eqref{lambda}から に一致する。すなわち
が得られる。(QED)
双子素数への応用
Selbergの篩の応用として(ちょっと一般化して)正整数\begin{equation*}
\pi_{2a}(x)= \# \{ p\le x-2a \; | \; p+2a : \text{素数} \}
\end{equation*}の上からの評価を計算してみます*1。もちろん
以前、当ブログにてBrunの純正篩を紹介しました。
mathnote.info
この記事ではBrunの純正篩を用いて
\begin{equation*}
\pi_2(x) \ll \frac{x}{(\log x)^2} \log \log x \quad (x\to \infty)
\end{equation*}を証明しましたが、同様の手順で
\begin{equation*}
\pi_{2a}(x) \ll H(a) \frac{x}{(\log x)^2} \log \log x
\end{equation*}を示すことができます。ここで は
\begin{equation*}
H(a)= \prod_{2{<}p|a} \frac{p-1}{p-2}
\end{equation*}と定義されます。Hardy-Littlewood予想によると任意の に対して
\begin{equation*}
\pi_{2a}(x) = \frac{x}{(\log x)^2} \left( {\frak{S}}(a)+o(1)\right) \quad (x\to \infty)
\end{equation*}が特異級数と呼ばれる定数
\begin{equation*}
{\frak{S}}(a)=2H(a)\prod_{p>2} \left(1-\frac{1}{(p-1)^2} \right)
\end{equation*}に対して成り立つと予想されています。
Selbergの篩を用いるとBrunの純正篩を用いるよりも強い の上界を導くことが出来ます。
Theorem4
について一様に
\begin{equation*}
\pi_{2a}(x) \ll H(a) \frac{x}{(\log x)^2} \quad (x\to \infty)
\end{equation*}
Hardy-Littlewood予想を鑑みるとこれはOrder不等式としては最良の評価*2です。
Theorem4を証明するために
\begin{equation*}
\mathcal{A} = \{ n(n+2a) \; | \; n \le x -2a \}
\end{equation*}とします。のとき
よりTheorem4は自明なので
とします。
に対して
で数えられる元は
のどちらも
より大きい素数になるものを含むので
\begin{equation}
\pi_{2a}(x) \le S(\mathcal{A},z) + \pi (z) \le S(\mathcal{A},z) +z \label{twin prime}
\end{equation}が成立します。またこのとき\eqref{hypo}が
\begin{equation*}
X=x-2a, \; \rho(p)=
\begin{cases}
1 \quad (p\; | \; 2a) \\
2 \quad (p\nmid 2a)
\end{cases}
\end{equation*}で成立することが簡単に確かめられます。この設定でTheorem3を用いれば\eqref{twin prime}から に対して
\begin{equation}
\pi_{2a}(x) \le \frac{X}{G(z)} + \sum_{\substack{d_1,d_2 | P(z) \\ d_1,d_2 {<} z}}\rho([d_1,d_2]) +z \label{twin prime2}
\end{equation}なので以下右辺を計算していきます。
Lemma5
\begin{equation*}
\sum_{\substack{d_1,d_2 | P(z) \\ d_1,d_2 {<} z}}\rho([d_1,d_2]) \ll z^2(\log z)^2
\end{equation*}
証明 を約数個数関数、
を
の素因数の個数としたとき
なら
が成立する。従って
のとき
\begin{equation*}
\rho([d_1,d_2]) \le 2^{\nu( [d_1,d_2])} \le 2^{\nu(d_1)+\nu(d_2)} =\tau(d_1) \tau(d_2)
\end{equation*}が得られる。これより
\begin{equation*}
\sum_{\substack{d_1,d_2 | P(z) \\ d_1,d_2 {<} z}}\rho([d_1,d_2]) \le \left( \sum_{d{<} z} \mu(d)^2\tau(d)\right)^2
\end{equation*}となるが約数個数関数の平均値評価より右辺は である。(QED)
の評価のために一つ補題を用意します。
Lemma6
ある定数 が存在して任意の自然数
に対して
\begin{equation*}
\sum_{p{<}z} \frac{\rho(p)}{p} (\log p)^n \le \frac{2}{n}(\log z)^n +A (\log z)^{n-1}
\end{equation*}が成立する。
証明 のとき
に対して
\begin{equation*}
\sum_{w\le p {<} z} \frac{\rho(p)}{p}\log p \le 2\sum_{w \le p {<} z} \frac{\log p}{p}
\end{equation*}であるがMertensの第一定理から右辺は
\begin{equation*}
=2\log z - 2\log w +O(1) = 2\log \frac{z}{w} +O(1)
\end{equation*}となる。特にある定数 が存在して
\begin{equation}
\sum_{w\le p {<} z} \frac{\rho(p)}{p}\log p \le 2\log \frac{z}{w} +A \label{dim}
\end{equation}が成立する。とすれば
の場合が得られる。
のときAbelの公式を適用すると
\begin{align*}
\sum_{p {<} z} \frac{\rho(p)}{p}(\log p)^n & = \left( \sum_{p {<} z} \frac{\rho(p)}{p}\log p \right) (\log z)^{n-1} \\
& \quad - \int_1^z \left(\sum_{ p {<} t } \frac{\rho(p)}{p} \log p \right) \frac{d(\log t)^{n-1}}{dt}\; dt \\
&= \int_1^z \left( \sum_{t \le p {<} z} \frac{\rho(p)}{p}\log p \right) \frac{d (\log t)^{n-1}}{dt} \; dt
\end{align*}と書ける。従って\eqref{dim}を用いれば
\begin{align*}
\sum_{p {<} z} \frac{\rho(p)}{p}(\log p)^n & \le \int_1^z \left( 2\log \frac{z}{t} +A \right) \frac{d (\log t)^{n-1}}{dt} \; dt \\
& = \frac{2}{n}(\log z)^n +A (\log z)^{n-1}
\end{align*}が得られる。(QED)
Lemma7
に対して
\begin{equation*}
W(z) = \prod_{p{<}z} \left(1-\frac{\rho(p)}{p}\right)
\end{equation*}と定める。このとき
\begin{equation*}
\frac{1}{G(z)} \ll W(z)
\end{equation*}が成立する。
証明 *3に対し
\begin{equation*}
G(x,z)=\sum_{\substack{d|P(z) \\ d {<} x}}g(d)
\end{equation*}とする*4。定義から
\begin{equation*}
\frac{1}{W(z)} = \prod_{p {<} z} \left( 1+g(p) \right) =\sum_{d|P(z)} g(d)
\end{equation*}なので
\begin{equation*}
\frac{1}{W(z)} - G(x,z) = \sum_{\substack{d \ge x \\ d|P(z)}} g(d)
\end{equation*}が得られるがパラメータ に対して右辺の和において
が成り立つことに注意して右辺を
\begin{equation*}
\le \sum_{d|P(z)} g(d) \left(\frac{d}{x}\right)^{1-s} = x^{s-1} \prod_{p {<} z} \left( 1+ g(p)p^{1-s} \right)
\end{equation*}と評価する。得られた不等式の両辺に をかけて整理すれば
\begin{align}
1-W(z)G(x,z) &\le x^{s-1}W(z) \prod_{p {<} z} \left( 1+ g(p)p^{1-s} \right) \notag \\
&=x^{s-1} \prod_{p {<} z} \left(1-\frac{\rho(p)}{p} + \frac{\rho(p)}{p^s} \right) \notag \\
&=\text{exp} \left( -(s-1)\log x +\sum_{p{<} z} \log \left( 1+\frac{\rho(p)}{p^s} - \frac{\rho(p)}{p} \right) \right) \notag\\
&\le \text{exp} \left( -(s-1)\log x +\sum_{p{<} z}\rho (p) \left( \frac{1}{p^s}-\frac{1}{p}\right) \right) \label{eq lem7}
\end{align}と評価できる。ただし最後の行で不等式 を用いた。ここで指数関数のマクローリン展開を用いて
\begin{align*}
\frac{1}{p^s} -\frac{1}{p} &= \frac{1}{p} \left( \text{exp} \left( (1-s)\log p \right) -1 \right) = \frac{1}{p} \sum_{n=1}^{\infty} \frac{(1-s)^n (\log p)^n}{n!}
\end{align*}と書けることとLemma6を用いると
\begin{align*}
\sum_{p {<} z} \rho(p) \left( \frac{1}{p^s} - \frac{1}{p} \right) &= \sum_{n=1}^{\infty} \frac{(1-s)^n }{n!} \sum_{p {<} z} \frac{\rho(p)}{p}(\log p)^n \\
&\le \sum_{n=1}^{\infty} \frac{(1-s)^n }{n!}\left( \frac{2}{n} (\log z)^n + A (\log z)^{n-1} \right)
\end{align*}さらに とすると最後の式は
\begin{align*}
&\le 2 \sum_{n=1}^{\infty} \frac{1}{n!n} + \frac{A}{\log z} \sum_{n=1}^{\infty} \frac{1}{n!} \\
&\le 4 \sum_{n=1}^{\infty} \frac{1}{(n+1)!} + \frac{A}{\log 2} \sum_{n=1}^{\infty} \frac{1}{n!} \\
&\le 4 \sum_{n=0}^{\infty} \frac{1}{n!} + \frac{A}{\log 2} \sum_{n=0}^{\infty} \frac{1}{n!} =4e +\frac{Ae}{\log 2}
\end{align*}と評価できる。ただし二行目で不等式 を用いた。この不等式を\eqref{eq lem7}に代入すれば
で
\begin{align*}
1-W(z)G(x,z) \le \text{exp} \left( -\frac{\log x}{\log z} +4e +\frac{Ae}{\log 2} \right)
\end{align*}が得られる*5。この評価において
\begin{equation*}
c= 4e +\frac{Ae}{\log 2} + \log 2 , \; x= z^c
\end{equation*}とすれば
\begin{equation}
W(z)G\left( z^c, z\right) \ge \frac{1}{2} \gg 1 \label{eq2 lem7}
\end{equation}が成立する。
ここからを評価する。自明に
なので \eqref{eq2 lem7}を用いれば
\begin{equation*}
\frac{1}{G(z)} \le \frac{1}{W(z^{1/c})G(z.z^{1/c})}\frac{W(z^{1/c})}{W(z)}W(z) \ll \frac{W(z^{1/c})}{W(z)}W(z)
\end{equation*}
が成立。に注意して
\begin{align*}
\frac{W(z^{1/c})}{W(z)} &\le \prod_{z^{1/c} \le p {<} z} \left(1-\frac{2}{p} \right)^{-1} \ll \prod_{z^{1/c} \le p {<} z} \left(1-\frac{1}{p}\right)^{-2}
\end{align*}と評価できるが最後の積はMertensの第三定理から である。したがって
\begin{equation*}
\frac{1}{G(z)} \ll W(z)
\end{equation*}が得られる。(QED)
以上で準備完了です。Theorem4を証明します。
Theorem4の証明 不等式\eqref{twin prime2}及びLemma5とLemma7から
\begin{equation*}
\pi_{2a}(x) \ll XW(z)+z^2(\log z)^2
\end{equation*}が成立。は定義から
\begin{align*}
W(z) &=\frac{1}{2} \prod_{\substack{2{<} p {<} z \\ p|2a}} \frac{p-1}{p-2} \prod_{2 {<}p {<} z} \left(1-\frac{2}{p}\right) \\
&\ll \prod_{2 {<} p|2a}\frac{p-1}{p-2} \prod_{2 {<} p {<} z} \left(1-\frac{1}{p}\right)^2
\end{align*}なので再びMertensの第三定理より と評価できる。すなわち
\begin{equation*}
\pi_{2a}(x) \ll H(a)\frac{X}{(\log z)^2} +z^2(\log z)^2
\end{equation*}が得られる。とすれば
\begin{equation*}
\pi_{2a}(x) \ll H(a) \frac{X}{(\log x)^2} +x^{1/2}(\log x)^2 \ll H(a) \frac{x}{(\log x)^2}
\end{equation*}となりTheorem4が示される。(QED)
原始根③ 原始根とDirichlet指標 ~最小原始根について~
過去二回の記事において原始根や指数計算について紹介しました。
この記事では原始根とDirichlet指標との関係性について紹介し、応用として最小原始根の問題について考察します。
参考文献
(1) Multiplicative Number Theory (Graduate Texts in Mathematics 74) (Graduate Texts in Mathematics, 74)リンク
(2) Kearnes, K. "Solution of Problem 6420." Amer. Math. Monthly 91, 521, 1984.
当時学生だったKearnesによるTheorem 12の証明です。リンク先の記事はJSTORにGoogleアカウントなどでログインすれば読めます。
リンク : https://www.jstor.org/stable/2322590#metadata_info_tab_contents
Dirichlet指標について
Dirichlet指標については過去の記事で詳しく紹介しましたが、今回は新たに定義を与えることとします。
ここでは原始根と指数を使って素数を法とするDirichlet指標を定義します。以下 は素数、
を
の原始根とし、実数
に対して
\begin{equation*}
e(\alpha):=e^{2\pi i \alpha}
\end{equation*}と定めます。
Definition 1
整数 に対して
のとき
\begin{equation*}
\chi_k(n)=e \left(\frac{\text{ind}_g(n)}{p-1}k\right)
\end{equation*}と定め、のとき
と定める。このとき各
に対して
をmod
のDirichlet指標と呼ぶ。
定義から ならば
が成立することが分かります。従って
に対して
は異なる関数となります。このことからDirichlet指標は全部で
個あることが分かります。
次の性質は簡単に確かめることが出来ます。
Proposition 2
が
のDirichlet指標なら次が成立する。
原始根の話題に入る前に一つDirichlet指標についての補題を示しておきます。
Lemma 3
に対して
\begin{equation*}
\sum_{\substack{\chi \; (\text{mod} \; p) \\ \chi^d=\chi_0}}1 =d
\end{equation*} が成立。ここで和は条件を満たすmod のDirichlet指標を走る。
証明 整数 に対して
\begin{equation*}
\chi_k^d(n) =e \left(\frac{\text{ind}_g(n)}{p-1}kd\right) =1 =\chi_0(n)\quad (\forall n, \; p\nmid n)
\end{equation*}となるには であれば良い。
と書くとこれは
と同値である。
のうち
の倍数は
\begin{equation*}
l, \; 2l , \; \dots \; , \; \frac{p-1}{l}\; l
\end{equation*}で全てなので を満たすDirichlet指標は全部で
個である。(QED)
Dirichlet指標とべき乗剰余
正整数 と
なる整数
に対して
\begin{equation*}
x^d \equiv a \; (\text{mod}\; p)
\end{equation*}の解が存在するとき はmod
の
乗剰余であると言います。
のとき、指数を用いることで
乗剰余を次のように記述できます。
Proposition 4 
は 
乗剰余 
が成立する。
とする。このとき
証明 過去記事のProposition 3を適用すればよい。(QED)
乗剰余とDirichlet指標には次のような関係があります。
Proposition 5
,
とする。このとき
\begin{equation*}
\frac{1}{d}\sum_{\substack{\chi \; (\text{mod}\; p) \\ \chi^d=\chi_0}}\chi(a) =
\begin{cases}
1 \quad (a\text{が}\;d\text{乗剰余}) \\
0 \quad (a\text{が}\;d\text{乗剰余でない})
\end{cases}
\end{equation*}が成立する。
証明 が
乗剰余であるとき、ある
が存在して
\begin{equation*}
x^d \equiv a \; (\text{mod}\; p)
\end{equation*}となる。従ってDirichlet指標の乗法性とProposition 2から
\begin{equation*}
\sum_{\substack{\chi \; (\text{mod}\; p ) \\ \chi^d=\chi_0}}\chi(a) =\sum_{\substack{\chi \; (\text{mod}\; p) \\ \chi^d=\chi_0}}\chi(x)^d =d
\end{equation*}が成立する。
が
乗剰余でないとする。
と書くと
を満たすDirichlet指標は
に対して(Lemma 3の証明と同様に)
\begin{equation*}
\chi (n)=e \left( \frac{\text{ind}_g(n)}{d} m\right) \quad (m=1,\dots ,d)
\end{equation*}と書ける。したがって
\begin{equation*}
\sum_{\substack{\chi \; (\text{mod}\; ) \\ \chi^d=\chi_0}}\chi(a) = \sum_{m=1}^d e\left(\frac{\text{ind}_g(a)}{d}m\right)
\end{equation*}Prop3より であることに注意すると最後の和は1の
乗根にわたる和になっているが、これは
になる(この記事のLem 1)。(QED)
Proposition 5における等式とDirichlet指標に関する性質を合わせるとべき乗剰余についての計算ができますが、今回は原始根がメインターゲットなのでこのまま原始根の話題に引き継ぐことにします。
Dirichlet指標と原始根
整数\begin{equation*}
\text{ord}_p(a)=p-1
\end{equation*}が成立することを言いました。これはMöbius関数
Proposition 6
とする。このとき
\begin{equation*}
\sum_{d|p-1} \frac{\mu(d)}{d} \sum_{\substack{\chi \; (\text{mod}\; p) \\ \chi^d =\chi_0}}\chi(a)=
\begin{cases}
1 \; &(a\text{がmod} \; p \text{の原始根}) \\
0 \; &(a\text{がmod} \; p \text{の原始根でない})
\end{cases}
\end{equation*}が成立する。
証明 原始根の定義とMöbius関数の基本公式から
\begin{equation*}
\sum_{d|\frac{p-1}{\text{ord}_p(a)}}\mu(d)=
\begin{cases}
1 \quad &(a\text{がmod} \; p \text{の原始根}) \\
0 \quad &(a\text{がmod} \; p \text{の原始根でない})
\end{cases}
\end{equation*}が成立。また、過去記事のProposition 4から のとき
\begin{equation*}
(\text{ind}_g(a),p-1)=\frac{p-1}{\text{ord}_p(a)}
\end{equation*}なのでProposition 4から に対して
\begin{equation*}
d|\frac{p-1}{\text{ord}_p(a)} \; \Leftrightarrow \; d|\text{ind}_g(a) \;
\Leftrightarrow \; a:d \text{乗剰余}
\end{equation*}がわかる。これらの結果とProposition 5から
\begin{equation*}
\sum_{d|\frac{p-1}{\text{ord}_p(a)}}\mu(d)=\sum_{d|p-1}\frac{\mu(d)}{d}\sum_{\substack{\chi \; (\text{mod}\; p) \\ \chi^d =\chi_0}}\chi(a)
\end{equation*}が成立する。(QED)
最小原始根について
応用として最小原始根について紹介します。Problem 7
のなかで
の原始根であって最小の整数を
と書く。このとき
の大きさを評価せよ。
上からの評価
の上からの評価を得るためにProposition 6を応用します。そのためにDirichlet指標に関する有名な不等式を紹介します(証明略)。
Lemma 8 (Pólya-Vinogradovの不等式)
をmod
のDirichlet指標とし、
とする。このとき
\begin{equation*}
\sum_{1\le a\le M} \chi(n) \ll \sqrt{p}(\log p)
\end{equation*}が成立する。
証明 参考文献(1)の23章を参照。(QED)
Theorem 9
任意の に対して
\begin{equation*}
g(p)\ll p^{1/2+\varepsilon}
\end{equation*}が成立。
証明 とする。Proposition 6の和を
の時とそれ以外で分割すると
\begin{align*}
&\{ 1\le a \le H: a \text{はmod}\; p \text{の原始根} \} \notag \\
&=\sum_{1\le a \le H}\sum_{d|p-1} \frac{\mu(d)}{d} \sum_{\substack{\chi \; (\text{mod}\; p) \\ \chi^d =\chi_0}}\chi(a) \notag \\
&=\sum_{d|p-1}\frac{\mu(d)}{d}\sum_{1\le a\le H}\chi_0(a) \notag \\
&\quad +\sum_{d|p-1} \frac{\mu(d)}{d} \sum_{\substack{\chi \neq \chi_0 \\
\chi^d =\chi_0}}\sum_{1\le a\le H} \chi(a) \label{eq3}
\end{align*}と書ける。ここで最後の第二項の和はLemma 8から
\begin{align*}
\ll \sqrt{p}(\log p) \sum_{d|p-1} 1 \ll p^{1/2+\varepsilon/2}
\end{align*}ただしLemma3及び
\begin{equation*}
\log p \ll p^{\varepsilon/4}, \quad \sum_{d|p-1} 1 \ll p^{\varepsilon/4}
\end{equation*}を用いた*1。従って
\begin{align*}
&\{ 1\le a \le H: a \text{はmod}\; p \text{の原始根} \} \\
&= \sum_{d|p-1}\frac{\mu(d)}{d}\sum_{1\le a\le H}\chi_0(a) +O\left(p^{1/2+\varepsilon/2} \right) \\
&=\frac{\phi(p-1)}{p-1}H+O\left(p^{1/2+\varepsilon/2} \right)
\end{align*} が得られる。最後の式は適当な定数 に対して
\begin{equation*}
H=Cp^{1/2+\varepsilon}
\end{equation*}と取れば正になる。したがって
\begin{equation*}
g(p) \le H \ll p^{1/2+\varepsilon}
\end{equation*}が成立する。
下からの評価
上からの評価はDirichlet指標を用いましたが、下からの評価は平方剰余の相互法則を用いて初等的に証明することが出来ます。
Lemma 11
とする。このとき
以下のすべての素数の列
に対して
\begin{equation*}
\left( \frac{q_i}{p}\right)=1
\end{equation*}を満たす素数 が無限に存在する。ここで
はLegendre記号とする。
証明 正整数 に対して
の形で表される素数を考える。 平方剰余の相互法則の第二補充法則から
\begin{equation*}
\left( \frac{q_1}{p} \right) =\left(\frac{2}{p} \right) =(-1)^{(p^2-1)/8}=1
\end{equation*}が成立。また平方剰余の相互法則から
\begin{equation*}
\left(\frac{q_i}{p} \right) \left( \frac{p}{q_i} \right) =(-1)^{(p-1)(q_i-1)/4}=1 \quad (2\le i \le n)
\end{equation*}が成立する。ここで に注意して
\begin{equation*}
\left( \frac{p}{q_i} \right) =\left(\frac{1}{q_i} \right) =1 \quad (2 \le i \le n)
\end{equation*}が得られるので
\begin{equation*}
\left( \frac{q_i}{p}\right)=1 \quad (2\le i \le n)
\end{equation*}が成立する。従ってこの は要求される性質を満たしているが、Dirichletの素数定理からこのような形の素数、すなわち
\begin{equation*}
p \equiv 1 \; (\text{mod} \; 4q_1 q_2 \cdots q_n)
\end{equation*}を満たす素数 は無限に存在する。(QED)
Theorem 12
任意のに対して
\begin{equation*}
g(p)>M
\end{equation*}を満たす素数 が無限に存在する。
証明 Lemma 11の条件を満たす素数 を取る。整数
が
を満たすなら
の素因数分解は
\begin{equation*}
r=q_1^{t_1} q_2^{t_2} \cdots q_n^{t_n} \quad (0\le t_i )
\end{equation*}で与えられる。従ってLegendre記号の完全乗法性から
\begin{equation*}
\left(\frac{r}{p}\right) =\left(\frac{q_1}{p}\right)^{t_1} \left( \frac{q_2}{p}\right)^{t_2} \cdots \left(\frac{q_n}{p}\right)^{t_n}=1
\end{equation*}が成立する。すなわち を満たす整数
は全てmod
の平方剰余であり、原始根にはならない。つまり
が得られる。Lemma 11からこのような素数
は無限に存在するので主張が証明される。(QED)
終わりに
原始根に関する記事はこれで一旦区切りとします。ここで紹介した結果の改善等はWikipediaにお譲りします。お読みいただきありがとうございまました。
原始根② 指数計算
前回の原始根における記事で素数 を法とする原始根の存在を示しました。
mathnote.info
今回は原始根を用いて乗法群における対数の類似である指数を導入し、その性質について紹介します。
参考文献
(1)Elements of number theory
リンク
(2)整数論入門
リンク
indexの定義
まず原始根について簡単に復習します。
整数 と
を満たす整数に対して
\begin{equation*}
a^r\equiv 1 \; (\text{mod} \; m)
\end{equation*}を満たす最小の正整数 を
のmod
における位数と呼び
と書きます。
さらに を満たす
をmod
の原始根と呼びます。
一般にmod の原始根が存在するかどうかは分かりませんが、冒頭で紹介したように前回の記事で素数
を法とする原始根の存在を証明しました*1。
以下、素数 をひとつ固定します。
Definition1(指数)
をmod
の原始根とし、
を
を満たす整数とする。このとき
\begin{equation*}
g^r \equiv a \; (\text{mod} \; p)
\end{equation*}を満たす最小の非負整数 を
を底とする
の指数と呼び
と書く。
前回の記事のlemma 3から の時
\begin{equation}
a\equiv b \; (\text{mod} \; p) \; \Leftrightarrow \; \text{ind}_g(a)=\text{ind}_g(b) \label{eq2}
\end{equation}が容易に分かります。
以下、mod の原始根
を一つ固定して議論します*2。また
を略記して
と書くことにします。指数は対数と似た次のような性質を持ちます。
Proposition 2
のとき
\begin{equation*}
\text{ind}(ab) \equiv \text{ind}(a)+\text{ind}(b) \; (\text{mod}\; p-1)
\end{equation*}が成立する。
証明 前回の記事のLemma 3及び
\begin{equation*}
g^{\text{ind}(ab)} \equiv ab \equiv g^{\text{ind}(a)} g^{\text{ind}(b)} \; (\text{mod} \; p)
\end{equation*}より従う。(QED)
掛け算を行う際に対数表を用いて計算する方法は有名ですが、Proposition 2から指数表を用意することで対数と同様に掛け算を足し算に変換できることが分かります。
例として の指数表を見ていきます。
としたときの指数表は次のようになります。
この表は
- 各行の見出しが指数の10の位
- 各列の見出しが指数の1の位
- 行列の成分が2^(10×行の見出し+列の見出し)をmod
で見たときの値
というように対応しています。この表は指数と整数の相互参照が出来るようになっています。読み方の具体例を挙げます。
(例1) 26の指数 を知りたい場合、まず表の成分から26を見つける。26は2行目の3列にあるので見出しを見ることで
がわかる。
(例2) 逆に指数が19になる整数を見つけたい場合、表の2行10列目の成分である35が指数19を持つ。つまり となる。
(例3) 26×35をmod で計算したい。指数表からそれぞれの指数が12, 19であることがわかるのでProposition 2から
\begin{equation*}
\text{ind}(26\times 35)\equiv 12+19 =31 \; (\text{mod}\; 36)
\end{equation*}となる。指数が31となる数は指数表から22であることがわかるので\eqref{eq2}から
\begin{equation*}
26\times 35 \equiv 22 \; (\text{mod}\; 37)
\end{equation*}が得られる。
指数とべき乗剰余
次に指数を用いて合同方程式
\begin{equation}
x^n \equiv a \; ( \text{mod} \; p) \label{eq1}
\end{equation}について考えます。で\eqref{eq1}が解をもつとき
は
乗剰余であると言います。たとえば平方剰余についてはGaussによる有名な定理がありますが、一般の剰余に対して指数を用いて次のことが言えます。
証明 () \eqref{eq2}とProposition 2から、\eqref{eq1}が解を持つことは
\begin{equation*}
n \; \text{ind} (x) \equiv \text{ind}(a) \; (\text{mod} \; p-1)
\end{equation*}が解を持つことと同値。この一次合同方程式が解を持つことは となることと同値。
() \eqref{eq2}を用いて
\begin{align*}
&\text{ind}(a) \equiv 0 \; (\text{mod}\; d) \\
\Leftrightarrow \quad &\frac{p-1}{d} \text{ind}(a) \equiv 0 \; (\text{mod}\; \frac{p-1}{d}d = p-1) \\
\Leftrightarrow \quad &a^{(p-1)/d} \equiv 1 \; (\text{mod} \; p)
\end{align*}となる。(QED)
Proposition 3から指数表があれば具体的な整数 に対して\eqref{eq1}が解を持つかどうか簡単に判定することが出来ます。
の場合の指数表を再掲して具体例を見てみます。
(例1) が解を持つかどうか考える。このとき
であり、指数表から
なので
が成立。Proposition 3からこの方程式は解を持つことがわかる。
(例2) は解を持たない。なぜなら 指数表から
であり
となるため。
指数と位数の関係
指数について色々と紹介してきましたが、最後に指数と位数の関係について述べて終わりにしたいと思います。
Proposition 4
とする。このとき
に対して
の位数が
になることと
\begin{equation*}
(\text{ind}(a),p-1)=\frac{p-1}{\delta}
\end{equation*}が成立することは同値。
証明 とする。定義から
\begin{equation*}
a^{\delta} \equiv 1 \; (\text{mod}\; p)
\end{equation*}が成立。 従ってProp 3から は
の約数であることがわかる。さらに
の最小性から、
と
の公約数のうち
が最大のものとなる。従って
\begin{equation*}
(\text{ind}(a),p-1)=\frac{p-1}{\delta}
\end{equation*}が成立する。逆に等式が成立しているなら は
\begin{equation*}
\frac{p-1}{c} |\text{ind}(a)
\end{equation*}を満たす のうち最小の数である。このときProp 3から
\begin{equation*}
a^c \equiv 1 \; ( \text{mod} \; p)
\end{equation*}となるが、の最小性から
がわかる。(QED)
この命題をもちいて原始根の数を計算することが出来ます。
Corollary 5
とする。このとき
の元で位数
のものはちょうど
個存在する。特にmod
の原始根はちょうど
個存在する。
証明 Proposition 4から
\begin{equation*}
( r,p-1)=\frac{p-1}{\delta}
\end{equation*}を満たす を数え上げればよい。そのような
は
の倍数なので
\begin{equation*}
\frac{p-1}{\delta}, \; 2\; \frac{p-1}{\delta}, \dots , \; \delta \; \frac{p-1}{\delta}
\end{equation*}のうち
\begin{equation*}
r=c \; \frac{p-1}{\delta} \quad ((c,\delta)=1)
\end{equation*}と書ける数で全てである。従って位数 の元はちょうど
個ある。
おわりに
原始根を用いた指数計算について紹介しました。次回は原始根の大きさの問題について紹介します。
原始根① 素数の場合とArtin予想
最近、原始根に関するArtin予想というある未解決問題に興味があります。
この記事ではまず原始根を導入しその基本的な性質について議論し、最後にArtin予想について紹介します。
参考文献
(1)Elements of number theory*1
リンク
(2)整数論入門
リンク
Eulerの定理、Fermatの小定理と原始根
原始根の導入に先立ち、まずは合同式に関するEulerの定理を証明します。
Theorem1(Eulerの定理)
任意の整数 と
を満たす整数
に対して
\begin{equation*}
a^{\varphi (m)} \equiv 1 \quad (\mathrm{mod} \; m)
\end{equation*}が成立する。ここで はEulerのトーシェント関数とする。
証明 乗法群 の元を
\begin{equation*}
(\mathbb{Z}/p\mathbb{Z} )^{\times}=\{ r_1, \dots , r_{\varphi (m)} \}
\end{equation*}と羅列しておく。このとき から
\begin{equation*}
(\mathbb{Z}/p\mathbb{Z} )^{\times}= \{ ar_1, \dots , ar_{\varphi (m)} \}
\end{equation*}が成立する。したがって両方の成分をすべて掛け合わせると
\begin{align*}
a^{\varphi(m)} \cdot (r_1 \cdots r_{\varphi(m)}) \equiv r_1 \cdots r_{\varphi(m)} \quad (\mathrm{mod} \; m)
\end{align*}が成立する。これより定理の主張が従う。(QED)
Erlerの定理(Theorem1)において が素数の場合はFermatの小定理とも呼ばれています。Eulerの定理は
\begin{equation}
a^n \equiv 1 \quad (\mathrm{mod}\; m) \label{Euler eq}
\end{equation}を満たす解 を与えますが、他にこの方程式を満たす解
があるかどうかについては議論していません。これを動機として原始根を定義します。
Definition2(位数と原始根)
を満たす整数
に対して、
で方程式\eqref{Euler eq}を満たす最小の
を
のmod
における位数と呼び
と書く。また\begin{equation*}
\mathrm{ord}_m (a)=\varphi(m)
\end{equation*}が成り立つとき をmod
の原始根と呼ぶ。
群論的な言い方をするとmod の原始根とは乗法群
の生成元のことです。原始根が存在するかどうかは乗法群が巡回群になるか否かを問う問題と同値になります。
位数に関する補題
原始根について議論するために位数に関する基本的な補題をいくつか証明します。
以下 を仮定して計算します。
Lemma3
整数 に対し
\begin{equation*}
a^t \equiv a^{t'} \quad (\mathrm{mod}\; m) \Leftrightarrow t \equiv t' \quad (\mathrm{mod } \; \mathrm{ord}_m(a) )
\end{equation*}が成立する。特に は
の約数。
証明 は
の定義から明らかに成立するので
を示す。剰余の定理から適当な整数
と
を用いて
\begin{equation*}
t=\mathrm{ord}_m(a) \cdot q +r, \quad t'=\mathrm{ord}_m(a) \cdot q' +r'
\end{equation*}と表すことができる。これを仮定の式に代入すれば位数の定義から
\begin{equation*}
a^r \equiv a^{r'} \quad (\mathrm{mod}\; m)
\end{equation*}が成立。従って の大きさから
が成立することがわかる。これは
がmod
で成立することを意味している。
特にTheorem1と位数の定義から なので
となる。(QED)
Lemma4
整数 で
\begin{equation*}
\mathrm{ord}_m(a)=kl
\end{equation*}と表されていると仮定する。このとき
\begin{equation*}
\mathrm{ord}_m \left( a^k \right) =l
\end{equation*}が成立する
証明 仮定から
\begin{equation*}
\left( a^k \right)^l \equiv 1 \quad (\mathrm{mod}\; m)
\end{equation*}なのでLemma3から は
の倍数である。一方で
\begin{equation*}
a^{k \cdot \mathrm{ord}_m(a^k)} \equiv 1 \quad (\mathrm{mod} m)
\end{equation*}なのでLemma3から は
の倍数。つまり
は
の倍数となる。以上より
が成立する。(QED)
Lemma5
ならば
\begin{equation*}
\mathrm{ord}_m(aa')=\mathrm{ord}_m(a) \cdot \mathrm{ord}_m(a')
\end{equation*}が成立する。
証明 位数の定義からmod で
\begin{equation*}
1 \equiv \left( (aa')^{\mathrm{ord}_m(aa')} \right)^{\mathrm{ord}_m(a)} \equiv (a')^{\mathrm{ord}_m(aa')\cdot \mathrm{ord}_m(a)}
\end{equation*}が成立する。したがってLemma3から
\begin{equation*}
\mathrm{ord}_m(aa') \cdot \mathrm{ord}_m(a) \equiv 0 \quad (\mathrm{mod}\; \mathrm{ord}_m(a') )
\end{equation*}が成り立つが より
\begin{equation*}
\mathrm{ord}_m(aa') \equiv 0 \quad (\mathrm{mod}\; \mathrm{ord}_m(a') )
\end{equation*}が成立する。さらに、まったく同様に
\begin{equation*}
\mathrm{ord}_m(aa') \equiv 0 \quad (\mathrm{mod}\; \mathrm{ord}_m(a) )
\end{equation*}も成立。すなわち
\begin{equation*}
\mathrm{ord}_m(a) \cdot \mathrm{ord}_m(a') | \mathrm{ord}_m(aa')
\end{equation*}が成立する。一方で
\begin{equation*}
(aa')^{\mathrm{ord}_m(a) \cdot \mathrm{ord}_m(a')} \equiv 1 \quad (\mathrm{mod} \; m)
\end{equation*}が成り立つのでLemma3から
\begin{equation*}
\mathrm{ord}_m(aa') |\mathrm{ord}_m(a) \cdot \mathrm{ord}_m(a')
\end{equation*}以上より主張が成立する。(QED)
法が素数の場合の原始根
法が素数であれば原始根を構成することができます。
Theorem6
素数 に対して
の原始根が存在する。
証明 mod の位数として取りうる値の集合を
\begin{equation*}
\left\{ \mathrm{ord}_m(a) | a \in ( \mathbb{Z}/p \mathbb{Z} )^{\times} \right\} =\{ \delta_1, \dots , \delta_r \}
\end{equation*}と書くことにする。さらに と定め
\begin{equation*}
\tau = q_1^{\alpha_1} q_2^{\alpha_2} \cdots q_k^{\alpha_k}
\end{equation*}と素因数分解しておく。このとき の定め方から任意の
に対して、ある
が存在して
\begin{equation*}
q_s^{\alpha_s} | \delta_{i_s} \Leftrightarrow \delta_{i_s}=t_sq_s^{\alpha_s} \quad (t_s:=\delta_{i_s}/q_s^{\alpha_s} )
\end{equation*}が成立する。さらに に対応して
\begin{equation*}
\mathrm{ord}_p (a_s)=\delta_{i_s}=t_sq_s^{\alpha_s}
\end{equation*}となる が取れる。このときLemma4から
\begin{equation*}
\mathrm{ord}_p(a_s^{t_s})=q_s^{\alpha_s}
\end{equation*}が成立。は互いに素なので
と定めればLemma5から
\begin{equation*}
\mathrm{ord}_p(g)=q_1^{\alpha_1}\cdots q_k^{\alpha_k} =\tau
\end{equation*}が成立する。したがって はmod
の位数であり、Lemma3から
となる。一方で
次の合同方程式
\begin{equation*}
x^{\tau} \equiv 1 \quad (\mathrm{mod} \; p)
\end{equation*}を考えると の定義から
全てを解に持つ。すなわちこの方程式は
個の解をもつため
でなければならない*2。以上より
が成立。原始根の定義から
がmod
の原始根であることがわかる。(QED)
Artin予想について
素数 に対してmod
の原始根が存在することがわかりましたが、逆に整数
を固定したとき
を原始根にもつ素数
がどれだけあるかを問う問題がArtin予想です。
Conjecture7(Artin予想)
整数 を
もしくは平方数ではないものとする。このとき
を原始根に持つ素数
が無限に存在する。
除いた と平方数ですが、
は位数が2以下なのでmod
で原始根にはなりえず、また
が平方数
のときはTheorem1から
\begin{equation*}
a^{(p-1)/2} \equiv n^{p-1} \equiv 1 \quad (\mathrm{mod} \; p)
\end{equation*}となるのでやはり原始根にはならないことがわかります。
Artin予想は現在未解決ですが、いろいろと部分的な結果が証明されています。
Theorem8(C. Hooley, 1967)
任意の素数 に対して代数体
上の一般Riemann予想が成立するならArtin予想が成立する。さらに
を
で
を原始根にもつものの数とすると\begin{equation*}
\pi_a(x) \sim C(a) \frac{x}{\log x} \quad (x\to \infty)
\end{equation*}が成立。ここで は
に依存する定数。
unconditionalな結果で最も強いものは次の定理です。
Theorem9(D. R. Heath Brown, 1986)
次が成立する。
(1) Artin予想がなりたたないような素数 は高々2個
(2) Artin予想が成り立たないようなSquare free数 は高々3個
(3) Artin予想が成り立たないような の数は高々
個
証明はやはり篩法によるものです。
Brunの純正篩
以前の記事で篩法の根底にある考え方を紹介しました。
mathnote.info
今回はEratosthenesの篩を用いて初めて非自明な結果を導くことに成功したViggo Brunによる方法を紹介し、Brunの定理(双子素数の逆数和が収束すること)の証明を与えます。
この記事の4,5,6節(目次で☆のついてるところ)ではBrunの純正篩の計算を詳しく解説しました。特に6節では篩法を用いて の素因数の個数を評価する方法について紹介します。
一方で細かい計算や応用はさておいてBrunの定理の証明を手早く読みたかったり忙しくて細かいところが追えない人向けに7節では3節の結果から直接Brunの定理を導く方法を紹介します。
参考文献
この記事の大筋は(1)を、7節におけるBrunの定理の証明は(2)を参考にしました。(1) Sieve Methods
kindle版
リンク
ペーパーバック版
リンク
(2) 解析的整数論〈1〉素数分布論 (朝倉数学大系)
リンク
篩の問題設定
\begin{equation*}
S(\mathcal{A},z)=\# \{ a \in \mathcal{A} | (a,P(z))=1\}
\end{equation*}を評価することが篩法の目標です。
\begin{equation*}
\mathcal{A}_d=\{ a\in \mathcal{A}| a \equiv 0 \; (\mathrm{mod} \; d) \}
\end{equation*}とすると
\begin{equation*}
S(\mathcal{A},z)=\sum_{d|P(z)}\mu (d) |\mathcal{A}_d|
\end{equation*}が成りたつというものでした。
なんの仮定もなしに を計算することはできないので、何らかしらの乗法的関数
と
に対して
\begin{equation}
| \mathcal{A}_d|=\frac{\rho (d)}{d} X +R_d \quad (|R_d|\le \rho (d), d|P(z)) \label{brun2}
\end{equation}が成り立つことを仮定します。
この仮定のもとでLegendreの篩から
\begin{equation*}
S(\mathcal{A},z)=X\sum_{d|P(z)}\frac{\mu(d)\rho(d)}{d}+O\left( \sum_{d|P(z)}|R_d|\right)
\end{equation*}が得られるわけですが、このままでは残余項の和が長すぎて有効な結果が得られないことがこれまでの問題点でした。
Brunの純正篩
Legendreの篩における難点を解消した史上初の方法がBrunの純正篩*1です。Theorem1(Brunの純正篩)
任意の整数 に対して
\begin{equation*}
\sum_{\substack{d|n \\ \nu (d) \le 2s-1}} \mu(d) \le \sum_{d|n} \mu(d) \le \sum_{\substack{d|n \\ \nu (d) \le 2s}} \mu (d)
\end{equation*}が成立する。ここで は
の相異なる素因数の個数を表す。
パッと見でこの不等式が に与える影響はわかりづらいですが、それは後で説明することにしてまず不等式を証明します。
証明 のときは全て1になるから
とする。Möbius関数の基本公式から
\begin{equation*}
\sum_{d|n}\mu(d)=0 \quad (n>1)
\end{equation*}なので を
\begin{equation}
\sigma^{(k)}(n)=\sum_{\substack{d|n \\ \nu (d) \le k-1}}\mu(d) \label{brun3}
\end{equation}とすると目標の不等式は
\begin{equation}
(-1)^k\sigma^{(k)}(n)\le 0 \label{brun4}
\end{equation}と同値である。
次にを固定して
に関する数学的帰納法により
\begin{equation}
\sigma^{(k)}(n)=(-1)^{k-1}\binom{\nu(n)-1}{k-1} \quad (k \le \nu(n))\label{brun5}
\end{equation}を示す。のときは両辺1となるのでok。
で成立していると仮定する。このとき二項係数に関する公式
\begin{equation*}
\binom{\nu(n)}{k}=\binom{\nu(n)-1}{k-1}+\binom{\nu(n)-1}{k}
\end{equation*}を用いると
\begin{align*}
\sigma^{(k+1)}(n)&=\sigma^{(k)}+\sum_{\substack{d|n \\ \nu(d)=k}} \mu(d) \\
&=(-1)^{k-1}\binom{\nu(n)-1}{k-1}+(-1)^k\binom{\nu(n)}{k} \\
&=(-1)^k\binom{\nu(n)-1}{k}
\end{align*}となる。したがって全ての で\eqref{brun5}が示された。
ときはMöbius関数の基本公式と\eqref{brun3}より
である。
のときは\eqref{brun5}より
\begin{equation*}
(-1)^k\sigma^{(k)}(n)=-\binom{\nu(n)-1}{k-1} <0
\end{equation*}したがって\eqref{brun4}が成立する。(QED)
Theorem1を の評価とつなげる方法を紹介します。任意の
に対して
と定めてTheorem1を用いると
\begin{equation*}
\sum_{\substack{d|(a,P(z)) \\ \nu(d)\le 2s-1}}\mu(d) \le \sum_{d|(a,P(z))} \mu(d) \le \sum_{\substack{d|(a,P(z)) \\ \nu(d) \le 2s}}\mu(d)
\end{equation*}が得られます。この不等式を の元全体に渡って足し合わせて和の順序を交換することにより
\begin{equation*}
\sum_{\substack{d|P(z) \\ \nu(d) \le 2s-1}}\mu(d) |\mathcal{A}_d|
\le \sum_{d|P(z)} \mu(d) |\mathcal{A}_d|
\le \sum_{\substack{d|P(z) \\ \nu(d) \le 2s }} \mu(d) |\mathcal{A}_d|
\end{equation*}不等式の真ん中はLegendreの篩により と一致することがわかるのでTheorem1の系として次が得られます。
Corollary2
任意の整数列 、
と 整数
に対して
\begin{equation*}
\sum_{\substack{d|P(z) \\ \nu(d) \le 2s-1}}\mu(d) |\mathcal{A}_d|
\le S(\mathcal{A},z)
\le \sum_{\substack{d|P(z) \\ \nu(d) \le 2s }} \mu(d) |\mathcal{A}_d|
\end{equation*}が成立する。
応用ための準備☆
Corollary2より\begin{equation*}
S_r(\mathcal{A},z)=\sum_{\substack{d|P(z) \\ \nu(d)\le r-1}}\mu(d) |\mathcal{A}_d| \quad (r \in \mathbb{Z}_>1)
\end{equation*}の評価に帰着されます。ここでは具体的な問題に取り組むための準備として
\begin{align*}
S_r(\mathcal{A},z) &=X\sum_{\substack{d|P(z) \\ \nu(d) \le r-1}}\frac{\mu(d) \rho (d)}{d}+O\left( \sum_{\substack{d|P(z)\\ \nu(d) \le r-1}}|R_d| \right) \notag \\
&=: XS_r^{(1)}(\mathcal{A},z)+O\left( \sum_{\substack{d|P(z)\\ \nu(d) \le r-1}}|R_d| \right)
\end{align*}という形に分解しておきます。
まず二つほど基礎的な不等式を用意します。
Lemma3
を\eqref{brun3}で定義したものとする。このとき
\begin{equation*}
| \sigma^{(k)}(n) | \le \binom{\nu(n)}{k} \quad (n>1, k \le \nu(n))
\end{equation*}が成立する。
証明 \eqref{brun5}を用いれば
\begin{equation*}
| \sigma^{(k)}(n) | \le \binom{\nu(n)-1}{k-1} \le \binom{\nu(n)}{k}
\end{equation*}となる。(QED)
Lemma4
正整数に対して
\begin{equation*}
\frac{1}{r!} \le \left( \frac{e}{r} \right)^r
\end{equation*}が成立。
証明 目標の不等式の対数をとって
\begin{equation*}
\sum_{k=1}^r \log k \ge r\log r-r
\end{equation*}を示せばよい。これは積分を用いて
\begin{equation*}
\sum_{k=1}^r\log k \ge \int_1^r \log t \; dt \ge r\log r-r
\end{equation*}とすれば得られる。(QED)
つづいてについて考えていきます。Legendreの篩の解説でみたように、
の主要項は
\begin{equation*}
X \prod_{p\le z} \left( 1-\frac{\rho(p)}{p}\right)=: XW(z)
\end{equation*}で与えられる(と考えられる)ことがわかります。そこでこの素数に渡る積が0にならないように新たに
\begin{equation}
0\le \frac{\rho(p)}{p} <1 \quad (p \le z) \label{brun6}
\end{equation}を仮定して計算します。
Lemma5
を \eqref{brun3}で定義した関数とし、さらに\eqref{brun6}を仮定する。このとき
\begin{equation*}
S_r^{(1)}(\mathcal{A},z)=W(z)\left( 1+ \sum_{\substack{\delta|P(z)\\ \delta > 1}}\sigma^{(r)}(\delta) g(\delta) \right)
\end{equation*}が成立する。ここで
\begin{equation*}
g(\delta)=\prod_{p|\delta} \frac{\rho(p)}{p-\rho(p)} \quad (\delta| P(z))
\end{equation*}とする。
※仮定\eqref{brun6}より はwell-defined
証明 を
\begin{equation*}
\chi^{(r)}(n)=
\begin{cases}
1\quad &(\nu(n)\le r-1) \\
0\quad &(\nu(n)\ge r)
\end{cases}
\end{equation*}と定めると なのでMöbiusの反転公式から
\begin{equation*}
\mu(n)\chi^{(r)}(n)=\sum_{d|n} \mu\left( \frac{n}{d}\right) \sigma^{(r)}(d)
\end{equation*}が得られる。これを用いると
\begin{align*}
S_r^{(1)}(\mathcal{A},z)&=\sum_{d|P(z)}\mu (d)\chi^{(r)}(d) \frac{\rho(d)}{d} \\
&=\sum_{d|P(z)} \frac{\rho(d)}{d} \sum_{\delta |d}\mu \left(\frac{d}{\delta}\right) \sigma^{(r)}(\delta) \\
&=\sum_{\delta|P(z)} \sigma^{(r)}(\delta) \sum_{\substack{d|P(z) \\ \delta|d}} \mu\left(\frac{d}{\delta} \right)\frac{\rho(d)}{d}
\end{align*}と置けば
\begin{align*}
&=\sum_{\delta|P(z)} \frac{\sigma^{(r)}(\delta)\rho(\delta)}{\delta} \sum_{t|P(z)/\delta} \frac{\mu(t)\rho(t)}{t} \\
&=\sum_{\delta|P(z)} \frac{\sigma^{(r)}(\delta)\rho(\delta)}{\delta} \prod_{p|P(z)/\delta} \left(1-\frac{\rho(p)}{p}\right)
\end{align*}
が得られる。さらに に対し
\begin{align*}
\frac{\rho(\delta)}{\delta}\prod_{p|P(z)/\delta} \left(1-\frac{\rho(p)}{p}\right)&＝W(z) \prod_{p|\delta}\frac{\rho(p)}{p}\cdot \frac{p}{p-\rho(p)}\\
&=W(z)g(\delta)
\end{align*}であるから
\begin{align*}
S_r^{(1)}(\mathcal{A},z)&=W(z)\sum_{\delta|P(z)}\sigma^{(r)}(\delta) g(\delta) \\
&=W(z)\left( 1+ \sum_{\substack{\delta|P(z)\\ \delta > 1}}\sigma^{(r)}(\delta) g(\delta) \right)
\end{align*}が得られる。(QED)
Lemma5で現れた和
\begin{equation*}
\sum_{\substack{\delta|P(z)\\ \delta > 1}}\sigma^{(r)}(\delta) g(\delta)
\end{equation*}を評価します。
Lemma6
Lemma5と同じ条件のもとで
\begin{equation*}
\sum_{\substack{\delta|P(z)\\ \delta > 1}}\sigma^{(r)}(\delta) g(\delta) =O\left(\frac{1}{r!} \left(\sum_{p\le z}g(p)\right)^r \mathrm{exp}\left(\sum_{p\le z}g(p) \right) \right)
\end{equation*}
証明 Lemma3を用いれば
\begin{align*}
\left| \sum_{1 < \delta|P(z)}\sigma^{(r)}(\delta)g(\delta) \right| &\le \sum_{\substack{1<\delta|P(z) \\ \nu(\delta) \ge r}}\binom{\nu(\delta)}{r}g(\delta) \\
&=\sum_{m=r}^{\nu (P(z))}\binom{m}{r}\sum_{\substack{\delta|P(z) \\ \nu(\delta)=m}}g(\delta) \\
&\le \sum_{m=r}^{\nu (P(z))}\binom{m}{r} \frac{1}{m!} \left(\sum_{p\le z} g(p)\right)^m \\
&\le \sum_{m=r}^{\infty}\binom{m}{r} \frac{1}{m!} \left(\sum_{p\le z} g(p)\right)^m \\
&=\sum_{m=r}^{\infty}\frac{1}{r!(m-r)!}\left(\sum_{p\le z}g(p)\right)^{m-r+r} \\
&=\frac{1}{r!}\left( \sum_{p\le z} g(p) \right)^r \sum_{k=0}^{\infty}\frac{1}{k!}\left(\sum_{p\le z}g(p) \right)^k \\
&=\frac{1}{r!} \left(\sum_{p\le z}g(p)\right)^r \mathrm{exp}\left(\sum_{p\le z}g(p) \right)
\end{align*}と計算できる。(QED)
最後にCorollary2を偶奇を分けずに用いることができる形に書き直しておきます。
Theorem7
条件\eqref{brun2}及び\eqref{brun6}を仮定する。このとき任意の正整数 に対して
\begin{align*}
S(\mathcal{A},z)=XS_r^{(1)}(\mathcal{A},z)&+O\left( \frac{X}{r!}\left( \sum_{p\le z}\frac{\rho(p)}{p} \right)^r \right)\\
&+O\left( \left( 1+\sum_{p\le z}\rho(p) \right)^r \right)
\end{align*}が成立。ここで は
\begin{align*}
S_r^{(1)}(\mathcal{A},z)=W(z)\left(1+O\frac{1}{r!} \left(\sum_{p\le z}g(p)\right)^r \mathrm{exp}\left(\sum_{p\le z}g(p) \right) \right)
\end{align*}を満たす。
証明 が偶数のときはCorollary2から
\begin{equation*}
S_r(\mathcal{A},z)+\sum_{\substack{d|P(z) \\ \nu(d)=r}} \mu(d)|\mathcal{A}_d|
=S_{r+1}(\mathcal{A},z) \le S(\mathcal{A},z) \le S_r (\mathcal{A},z)
\end{equation*}が奇数のときも同様に
\begin{equation*}
S_r(\mathcal{A},z) \le S(\mathcal{A},z)\le S_r(\mathcal{A},z)+\sum_{\substack{d|P(z)\\ \nu(d)=r}}\mu(d)|\mathcal{A}_d|
\end{equation*}したがって任意の に対して
\begin{align*}
S(\mathcal{A},z)&=S_r(\mathcal{A},z)+O\left( \sum_{\substack{d|P(z)\\ \nu(d)=r }}|\mathcal{A}_d| \right) \\
&=XS_r^{(1)}(\mathcal{A},z) +O\left(X\sum_{\substack{d|P(z) \\ \nu(d)=r}}\frac{\rho(d)}{d} \right) +O\left(\sum_{\substack{d|P(z) \\ \nu(d)\le r}}|R_d| \right)
\end{align*}となる。これと不等式
\begin{equation*}
\sum_{\substack{d|P(z) \\ \nu(d) =r}} \frac{\rho(d)}{d} \le \frac{1}{r!} \left(\sum_{p \le z}\frac{\rho(p)}{p} \right)^r
\end{equation*}\begin{equation*}
\sum_{\substack{d|P(z) \\ \nu(d) \le r}}|R_d| \le \sum_{\substack{d|P(z) \\ \nu(d) \le r}}\rho(d) \le \left(1+\sum_{p\le z} \rho(p) \right)^r
\end{equation*}を用いれば所望の漸近公式が得られる。の漸近公式はLemma5及び6から得られる。(QED)
双子素数の個数の上からの評価☆
ここではTheorem7においてLegendreの篩と篩法入門 - プライムスで考えたように双子素数の個数
\begin{equation*}
\pi_2(x)=\# \{ p\le x | p+2 :\mathrm{素数} \}
\end{equation*}の評価を与えるためには
\begin{equation*}
\mathcal{A} = \{ n(n+2) |n\le x \}
\end{equation*}と定めます。必要な条件が成立することを補題としてまとめておきましょう。
Lemma8
上記の に対して条件\eqref{brun2}と\eqref{brun6}が
\begin{equation*}
X=x,\quad \rho(p)=
\begin{cases}
1 \quad (p=2) \\
2 \quad (p\ge 3)
\end{cases}
\end{equation*}に対して成立する。さらに に対して
\begin{equation*}
\pi_2(x) \le S(\mathcal{A},z) +z
\end{equation*}が成立する。
証明 Legendreの篩と篩法入門 - プライムスを参照(QED)
この でTheorem7を用いると
は次のように展開することができます。
Lemma9
を任意の実数とし、正整数
を
\begin{equation*}
6(\log \log z +1)\le \lambda r
\end{equation*}を満たすようにとる。このとき
\begin{equation*}
S(\mathcal{A},z)=xW(z)\left(1+O\left(\left(\lambda e^{1+\lambda} \right)^r \right) \right) +O\left(z^r\right)
\end{equation*}が成立する。
証明 Theorem7における一つ目のオーダー項は のオーダー項に吸収されることが簡単に分かるので予め無視する。Lemma8から
\begin{equation*}
\frac{\rho (p)}{p} \le \frac{2}{3} \quad (\forall p)
\end{equation*}が成立。Mertensの第二定理
\begin{equation*}
\sum_{p\le z} \frac{1}{p} \le \log \log z+1 \quad (z\to \infty)
\end{equation*}を用いれば
\begin{equation*}
\sum_{p\le z} g(p) = \sum_{p\le z} \frac{\rho(p)/p}{1-\rho(p)/p} \le 6(\log \log z+1)
\end{equation*}したがって仮定から
\begin{equation*}
\sum_{p\le z} g(p) \le \lambda r
\end{equation*}が得られる。以下の素数の個数
に対して
が成立することに注意してTheorem7を用いれば、Lemma4より
\begin{align*}
S(\mathcal{A},z) &=xW(z)\left( 1+O\left( \left(\frac{e}{r}\right)^r (\lambda r)^r e^{\lambda r} \right) \right)+O\left( (1+2\pi(z))^r \right)\\
&=xW(z)\left(1+O\left(\left(\lambda e^{1+\lambda} \right)^r \right) \right) +O\left(z^r\right)
\end{align*}となる。(QED)
パラメーターの導入により
が非常に見やすくなりました。最終的な評価を得るためにはLemma9において
に依存する形で
を選ぶ必要があります。
以下ではの選び方に関するモチベーションの説明をします。結論だけ先に述べると
\begin{equation}
\lambda= \frac{1}{4} , \quad r=\lfloor 24(\log \log z +1) \rfloor +1 \label{par}
\end{equation}と定めることでLemma9の条件を満たしていることがわかります。説明不要の場合は読み飛ばしてTheorem10を読み始めても大丈夫です。
モチベの説明 Lemma9における の項は比較的小さいことが期待されるので
を小さくするように選びます。特に
の主要項は
になると期待しているので
\begin{equation}
\left( \lambda e^{1+\lambda} \right)^r =o(1) \quad (z\to \infty) \label{c1}
\end{equation}を満たすことが求められます。一方でLemma9において条件
\begin{equation}
6(\log \log z+1) \le \lambda r \label{c2}
\end{equation}が課されているため、固定した に対して
はそれなりに大きくとる必要があります。以上の考察を実現するためのもっとも簡単な方法は
に条件
\begin{equation}
0 < \lambda e^{1+\lambda} <1 \label{c3}
\end{equation}を課せすことです。条件\eqref{c3}のもとで条件 \eqref{c2}を満たす は全て \eqref{c1}を満たしますが、
の項の影響を最小にするためには\eqref{c2}を満たす最小の
を取る必要があります。すなわち
は
\begin{equation*}
r=\left\lfloor \frac{6}{\lambda} (\log \log z+1) \right\rfloor+1
\end{equation*}と定めます。最後に具体的な の選び方ですが、今回は双子素数という具体的な問題を扱っていることもあり
の選び方による大きな影響はありません。したがって適当な値として
と定めておきます。もちろん
\begin{equation*}
\frac{1}{4}e^{1+1/4} =0.8725\dots <1
\end{equation*}ということで条件\eqref{c3}を満たしています。以上の考察によって\eqref{par}の取り方が定まります。
Theorem10
を
\begin{equation*}
\log z=\frac{\log x}{26\log \log x}
\end{equation*}で定める。このとき で
\begin{equation*}
S(\mathcal{A},z)=e^{-2\gamma} \mathfrak{S}_2 \frac{x}{(\log z)^2} (1+o(1) )+O\left(x^{25/26} \right)
\end{equation*}が成立。ここで はEuler-Mascheroni定数で
\begin{equation*}
\mathfrak{S}_2=2\prod_{p\ge 3} \left(1-\frac{1}{(p-1)^2}\right)
\end{equation*}とする。
証明 を\eqref{par}で定める。このとき
\begin{equation*}
\frac{1}{4}e^{1+1/4} =0.8725\dots <1
\end{equation*}に注意してLemma9から
\begin{equation*}
S(\mathcal{A},z)=xW(z)(1+o(1) )+O\left( z^r \right)
\end{equation*}が成立。についてはMertensの定理から
\begin{align*}
W(z) &=\frac{1}{2} \prod_{3\le p\le z}\left(1-\frac{2}{p}\right) \\
&=\frac{1}{2}\prod_{3\le p \le z} \left(1-\frac{1}{(p-1)^2}\right) \left(1-\frac{1}{p}\right)^2\\
&\sim \mathfrak{S}_2 \prod_{p\le z}\left(1-\frac{1}{p}\right)^2 \sim \frac{e^{-2\gamma} \mathfrak{S}_2}{(\log z)^2} \quad (z\to \infty)
\end{align*}と計算できる。一方 は
\begin{align*}
z^r&\le z^{24(\log \log z +1)+1} \\
&=z^{24\log \log z} \cdot z^{25}
\end{align*}であり の定義から
\begin{align*}
z^{24\log \log z}&=\mathrm{exp}\left(24\log z \log \log z\right) \\
&\le \mathrm{exp} \left(\frac{24}{26}\log x \right)=x^{24/26}
\end{align*}\begin{align*}
z^{25}&=\mathrm{exp}\left(\frac{25\log x}{26\log \log x} \right) \\
&=x^{25/ (26\log \log x)} \le x^{1/26} \quad (x\to \infty)
\end{align*}なので
\begin{equation*}
z^r \le x^{25/26}
\end{equation*}が得られる。以上から所望の公式が得られる。(QED)
Theorem10の系としてBrunの定理が得られます。
Corollary11(Brunの定理)
\begin{equation*}
\pi_2(x) =O \left( \frac{x}{(\log x)^2 } (\log \log x)^2 \right)
\end{equation*}が成立。特に
\begin{equation*}
\sum_{\substack{p \\ p+2:\mathbf{素数}}} \frac{1}{p}
\end{equation*}は収束する。
証明 の評価はLemma8とTheorem10から容易に得られる。逆数和はAbelの和公式から
\begin{align*}
\sum_{\substack{p\le x\\ p+2:\mathbf{素数}}}\frac{1}{p} &=\frac{\pi_2(x)}{x} +\int_3^x \frac{\pi_2(t)}{t^2} \; dt \\
&\ll \left( \frac{\log \log x}{\log x} \right)^2 +\int_3^x \frac{1}{t}\left(\frac{\log \log t}{\log t} \right)^2 \; dt\\
&\ll \int_{\log 3}^{\log x} \left( \frac{\log u}{u} \right)^2\; du \ll 1
\end{align*}と評価できる。(QED)
n,n+2の素因数の個数について☆
\begin{equation*}
\mathcal{A}=\{ n(n+2) | x< n \le 2x \}
\end{equation*}としておきます。この
\begin{equation*}
S(\mathcal{A},z)=\# \{ x < n \le 2x | (n(n+2),P(z) )=1 \}
\end{equation*}と定義されます。もし
ことがわかります。ここで関数
\begin{equation*}
\Omega(n)=\sum_{p|n} \sum_{p^{\alpha}||n} \alpha
\end{equation*}で定めます。記号
\begin{equation*}
2x \ge n \ge z^{\Omega(n)},\; 2x \ge n+2 \ge z^{\Omega (n+2)}
\end{equation*}が得られます。この不等式において
\begin{equation*}
\Omega (n) ,\Omega (n+2) \ll u
\end{equation*}が成立することがわかります。
以上の議論をTheorem10と合わせることで系として次のような結果が得られます。
Corollary12
無限に多くの自然数 で
\begin{equation*}
\Omega(n),\Omega (n+2) \ll \log \log n
\end{equation*}が成立する。
証明 Theorem10における を
の形に書き換えると
\begin{equation*}
u=26 \log \log x
\end{equation*}となる。この に対してTheorem10の漸近公式から
\begin{equation*}
S(\mathcal{A},z) \to \infty \quad (x \to \infty)
\end{equation*}が従う。すなわち任意に大きい に対して
で(☆)を満たすものが取れる。この
に対して上述の議論から
\begin{equation*}
\Omega (n), \Omega(n+2) \ll u \ll \log \log x \ll \log \log n
\end{equation*}が成り立つ。すなわちこの不等式を満たす が無限に存在する。(QED)
この評価が良いのか悪いのかという話ですが、一般に無条件では
\begin{equation*}
\Omega(n) \le \sum_{p|n}\frac{\log n}{\log p} \ll \log n \sum_{p|n} \log p\ll (\log n)^2
\end{equation*}しか言えません。これと比べるとはるかに因数の少ないペア が無限に得られており、双子素数予想に多少近づいているように思えます。一方で
は緩やかながら発散する評価です。双子素数予想の解決には
が欲しいところですが、これを導くためにはBrunの純正篩を凌ぐより良い篩法が必要になります。
Corollary11が の上からの評価から得られる結果であり、Corollary12は下からの評価から得られる結果です。Brunの定理は非常に有名ですが、双子素数予想の解決のためには下からの評価も大切です。
Brunの定理の別証明
4節から6節において細かい計算を行ったのは、Brunの純正篩を用いて の漸近公式を導出するためです。それはすなわち
の上下からの評価を同時に扱うことを意味します。一方でBrunの定理(上述のCorollary11)を証明するためには
の上からの評価だけで十分です。ここではCorollary2の不等式の上からの評価だけを用いてBrunの定理を証明します。
4~6節を飛ばした人に向けて改めて記号を定義します。まず数列 を
\begin{equation*}
\mathcal{A}=\{ n(n+2)| n \le x \}
\end{equation*}と置きます。この数列に対して次が成立します。
Lemma13
上記の に対して条件\eqref{brun2}が
\begin{equation*}
X=x,\quad \rho(p)=
\begin{cases}
1 \quad (p=2) \\
2 \quad (p\ge 3)
\end{cases}
\end{equation*}に対して成立する。さらに とすると
に対して
\begin{equation*}
\pi_2(x) \le S(\mathcal{A},z) +z
\end{equation*}が成立する。
証明 Legendreの篩と篩法入門 - プライムスを参照(QED)
次が有名なBrunの定理です。
Theorem14(Brunの定理)
\begin{equation*}
\pi_2(x) =O \left( \frac{x}{(\log x)^2 } (\log \log x)^2 \right)
\end{equation*}が成立。特に
\begin{equation*}
\sum_{\substack{p \\ p+2:\mathbf{素数}}} \frac{1}{p}
\end{equation*}は収束する。
証明 Corollary2とLemma13より任意の正整数 と
に対して
\begin{align*}
\pi_2(x) &\le S(\mathcal{A},z)+z \\
&\le \sum_{\substack{d|P(z) \\ \nu(d) \le 2r }} |\mathcal{A}_d| +z \\
&=x\sum_{\substack{d|P(z) \\ \nu(d) \le 2r}} \frac{\mu(d) \rho(d)}{d} + \sum_{\substack{d|P(z) \\ \nu(d) \le 2r}} R_d +z
\end{align*}二つ目の和は より
\begin{align*}
\le \sum_{\substack{d|P(z) \\ \nu(d) \le 2r}} \rho(d) &\le (1+\sum_{p\le z}\rho(p) )^{2r} \\
&\le (1+2\sum_{p\le z}1)^{2r} \le z^{2r}
\end{align*}と評価できるので
\begin{equation*}
\pi_2(x) \ll x\sum_{\substack{d|P(z) \\ \nu(d) \le 2r}} \frac{\mu(d) \rho(d)}{d} +z^{2r}
\end{equation*}が得られる。ここで和の項について
\begin{equation*}
W(z)=\sum_{d|P(z)} \frac{\mu(d)\rho(d)}{d} =\prod_{p\le z} \left(1-\frac{\rho(p)}{p}\right)
\end{equation*}と置くと
\begin{align*}
W(z)-\sum_{\substack{d|P(z) \\ \nu(d) \le 2r}} \frac{\mu(d) \rho(d)}{d}\ll \sum_{\substack
{d|P(z) \\ \nu(d)>2r}}\frac{\rho(d)}{d}
\end{align*}が成立。 のとき
であること及び、
に注意すると最後の和は
\begin{equation*}
\ll 2^{-2r} \sum_{d|P(z)} \frac{2^{2\nu(d)}}{d}=2^{-2r}\prod_{p\le z} \left(1+\frac{4}{p}\right)
\end{equation*}Mertensの定理より
\begin{equation*}
\sum_{p\le z}\frac{1}{p}\le \log \log z+1
\end{equation*}が成立すること及び を用いれば
\begin{equation*}
\sum_{p\le z}\log \left(1+\frac{4}{p}\right) \le 4\log \log z+4
\end{equation*}すなわち
\begin{equation*}
\prod_{p\le z}\left(1+\frac{4}{p}\right) \ll (\log z)^4
\end{equation*}が得られる。これを先の不等式に代入すると
\begin{equation*}
\sum_{\substack{d|P(z) \\ \nu(d) \le 2r}} \frac{\mu(d) \rho(d)}{d} =W(z)+O\left( 2^{-2r}(\log z)^4 \right)
\end{equation*}となる。したがって を用いると
は
\begin{align*}
\pi_2(x) &\ll xW(z)+x2^{-2r}(\log z)^4 +z^{2r} \\
&\ll \frac{x}{(\log z)^2}+x2^{-2r}(\log z)^4 +z^{2r}
\end{align*}と評価できる。ここで
\begin{equation*}
r=\left\lfloor \frac{6}{\log 4}\log \log z \right\rfloor,\; \log z=\frac{\log x}{13\log \log x}
\end{equation*}と定めると
\begin{equation*}
2^{-2r} \ll \mathrm{exp}(-6\log \log z) = \frac{1}{(\log z)^6}
\end{equation*}及び
\begin{equation*}
z^{2r} \ll z^{12\log \log z} =\mathrm{exp}\left(12\log z \log \log z\right) \le x^{12/13}
\end{equation*}が成立。これらの不等式を の評価に代入して
\begin{equation*}
\pi_2(x) \ll \frac{x}{(\log z )^2} +x^{12/13} \ll \frac{x}{(\log x)^2}(\log \log x)^2
\end{equation*}が得られる。逆数和の収束性についてはCorollary11の証明を参照。(QED)
おわりに
Brunの純正篩は"組み合わせ論的篩"と呼ばれる手法の一つです。Brunの純正篩を発展させた先にBrunの篩及びRosserの篩という手法があります。これらを用いるとBrunの定理における
*1:"純正"がつく理由は純正篩をより発展させたBrunの篩が別にあるから。
Legendreの篩と篩法入門
前回はEratosthenesの篩について考えました。
mathnote.info
今回はEratosthenesの篩における”素数をふるい出す”という操作のLegendreによる数式表現を与え、篩が双子素数やGoldbach予想などと関連する様子を紹介します。
参考文献
篩法の入門的なテキストをいくつか紹介します。とくにHalberstam&Richertは篩法の伝統的なテキストで、リーズナブルなうえに情報量が豊富でkindre版もあるのでおすすめです。日本語だと内山先生のテキストが有名ですが絶版のようなので図書館の蔵書検索のリンクを載せておきます。(1)Sieve Methods (Dover Books on Mathematics) (English Edition)
kindre版
リンク
ペーパーバック版
リンク
(2)Sieves in Number Theory (A Series of Modern Surveys in Mathematics, 43)
リンク
(3)内山三郎 素数の分布(宝文館出版)
CiNii 図書 - 素数の分布
素数の場合
が素数
は
なる任意の素数
と互いに素
後の応用を考えて変数 を導入します。
を仮定すると次の同値性がわかります。
が素数
なる任意の素数
さらにを
\begin{equation*}
P(z)=\prod_{\substack{p\; : \; \mathbb{素数}\\ p \le z }}p
\end{equation*}と定めれば最後の条件は と同値です。したがって
を
以下の素数の個数とすると
\begin{equation}
\pi(x)-\pi(z)+1=\sum_{(n,P(z))=1}1 \quad (\sqrt{x} < z \le x) \label{Le1}
\end{equation}と書くことができます。ここで左辺の1は右辺の和において を足してしまう分を調節するための項です。こうして得られた\eqref{Le1}はEratosthenesの篩のもっともシンプルな数式化と考えられます。
続いて の場合を考えます。この場合は
\begin{equation*}
\sum_{(n,P(z))=1}1 = 1+\sum_{\substack{z{<} n \le x \\ (n,P(z))=1}}1 \ge 1+\pi(x)-\pi(z)
\end{equation*}となるので
\begin{equation}
\pi(x)-\pi(z)+1 \le \sum_{(n,P(z))=1}1 \quad (2\le z\le \sqrt{x}) \label{Le2}
\end{equation}が得られます。
以上の議論からEratosthenesの篩を素数に用いる際
\begin{equation*}
\sum_{(n,P(z))=1}1
\end{equation*}を調べる必要があることがわかりました。
Legendreによる定式化
より一般の場合を考察するために整数列\begin{align*}
&S(\mathcal{A},z)=\sum_{\substack{a\in \mathcal{A} \\ (a,P(z))=1}}1 \\
&\mathcal{A}_d =\{ a \in \mathcal{A} | a\equiv 0 \; （\mathbb{mod} \; d)\}
\end{align*}と定めます*1。目標は
Legendreによる定式化を導入するためにMöbius関数
\begin{align*}
\mu(n)=
\begin{cases}
1 \quad &(n=1)\\
0 \quad &(\exists p \; \mathrm{s.t.} \; p^2|n) \\
(-1)^k \quad &(n=p_1 \cdots p_k,\; p_i \neq p_j \; (i\neq j))
\end{cases}
\end{align*}を用います。ここで定義中の は素数です。
Lemma1(Möbius関数の基本公式)
\begin{equation*}
\sum_{d|n}\mu (d)=
\begin{cases}
1 \quad &(n=1)\\
0 \quad &(n>1)
\end{cases}
\end{equation*}
証明 のときは明らか。
のときはMöbiusの定義から
と素因数分解できるときに示せば十分である。このとき約数
の選び方は
の
個の素因数の中から
個選ぶ組み合わせの数だけある。
の素因数が
個のとき
なので二項定理を用いれば
\begin{align*}
\sum_{d|n}\mu(d)=\sum_{m=0}^k\binom{k}{m}(-1)^m =(1-1)^k =0
\end{align*}となり主張が示される。(QED)
次の定理がLegendreによるEratosthenesの篩の定式化で、一般にLegendreの篩と呼ばれるものです*2。
Theorem2 (Legendreの篩)
\begin{equation*}
S(\mathcal{A},z)=\sum_{d|P(z)}\mu (d)|\mathcal{A}_d|
\end{equation*}
証明 Lemma1を用いれば は
\begin{align*}
S(\mathcal{A},z)=\sum_{\substack{a\in \mathcal{A} \\ (a,P(z))=1}}1=\sum_{a \in \mathcal{A}}\sum_{d|(a,P(z))}\mu (d)
\end{align*}なので
\begin{align*}
=\sum_{a \in \mathcal{A}}\sum_{d|a,P(z)}\mu(d)=\sum_{d|P(z)}\mu(d) \sum_{\substack{a\in \mathcal{A} \\ d|a}}1=\sum_{d|P(z)}\mu(d)|\mathcal{A}_d|
\end{align*}と計算できる。(QED)
素数の場合(2)
Legendreの篩を先の素数の場合に用いてみます。つまり\begin{equation*}
\mathcal{A}=\{ n\in \mathbb{N}|1\le n \le x\}
\end{equation*}の場合を計算します。応用として
\begin{equation*}
\pi(x) \ll \frac{x}{\log \log x} \quad (x\to \infty)
\end{equation*}を導きます。
これ以降の議論では とし整数
は
を満たすこととします。Legendreの篩よりこの仮定の下でも一般性が保たれています。
Prop3
なる任意の整数
に対して
\begin{equation*}
{|}\mathcal{A}_d|=\frac{x}{d}+R_d
\end{equation*}が成立。ここで は
を満たす関数とする。特に
\begin{equation*}
S(\mathcal{A},z)=x\prod_{p\le z}\left( 1-\frac{1}{p}\right) +O\left(2^{\pi(z)}\right)
\end{equation*}が成立する。
証明 \begin{equation*}
{|}\mathcal{A}_d|=\sum_{0{<} k \le x/d} 1=\left[ \frac{x}{d} \right]=\frac{x}{d}+\left\{ \frac{x}{d}\right\}
\end{equation*}より に対して一つ目の等式が従う。これをLegendreの篩に代入すれば
\begin{align}
S(\mathcal{A},z)&=\sum_{d|P(z)}\mu(d) \left( \frac{x}{d}+R_d \right)\notag \\
&=x\sum_{d|P(z)}\frac{\mu(d)}{d} +O\left( \sum_{d|P(z)}1 \right) \label{Le3}
\end{align}\eqref{Le3}の第一項の和は が乗法的なので
\begin{equation*}
\sum_{d|P(z)}\frac{\mu(d)}{d}=\prod_{p\le z} \left( 1-\frac{\mu(p)}{p}\right)=\prod_{p\le z}\left(1-\frac{1}{p}\right)
\end{equation*}と分解できる。第二項は二項定理から
\begin{equation*}
\sum_{d|P(z)}1=\sum_{m=0}^{\pi(z)} \binom{\pi(z)}{m} =2^{\pi(z)}
\end{equation*}と計算できる。したがって\eqref{Le3}は
\begin{equation*}
S(\mathcal{A},z)=x\prod_{p\le z}\left( 1-\frac{1}{p}\right) +O\left( 2^{\pi(z)} \right)
\end{equation*}となる。(QED)
Lemma４
に対して
\begin{equation*}
\prod_{p\le z}\left( 1-\frac{1}{p} \right) \ll \frac{1}{\log z} \quad (z\to \infty)
\end{equation*}が成立する。
証明 逆数を下から評価する。等比数列の和の公式より
\begin{equation*}
\prod_{p{<}z} \left( 1-\frac{1}{p}\right)^{-1} =\prod_{p{<}z} \left( 1+\frac{1}{p}+\frac{1}{p^2}+\cdots \right)
\end{equation*}
右辺の積を展開して得られる和において、少なくとも なる項は全て現れるから
\begin{equation*}
> \sum_{n\le z} \frac{1}{n} \gg \log z \quad (z\to \infty)
\end{equation*}となり*3主張が得られる。(QED)
Theorem5
\begin{equation*}
\pi(x)\ll \frac{x}{\log \log x} \quad (x\to \infty)
\end{equation*}
証明 \eqref{Le2}より
\begin{equation*}
\pi(x) \le S(\mathcal{A},z)+\pi(z)-1 \quad (2\le z <\sqrt{x})
\end{equation*}Prop3、Prop4及び自明な不等式 を用いれば
\begin{equation}
\ll \frac{x}{\log z} +2^z+z \quad (z< \sqrt{x}, z\to \infty) \label{Le4}
\end{equation}が得られる。この不等式において と取ると
\begin{equation*}
\pi(x) \ll \frac{x}{\log \log x} +x^{\log 2} + \log x
\end{equation*}したがって に注意すれば所望の評価が得られる。(QED)
Legendreの篩の欠点
Legendreの定式化によってEratosthenesの篩を用いて素数に関する定量的な評価であるTheorem5を得ることができました。しかし一方でTheorem5の評価は実際の素数の個数とくらべて非常に荒い評価になっています。Chebyshevは初等的な方法で\begin{equation*}
\frac{x}{\log x} \ll \pi(x) \ll \frac{x}{\log x}
\end{equation*}を示していますからLegendreの方法はChebyshevの方法と比較してはるかに劣った評価しか得られないことがわかります。
Legendreの方法において何が問題になっているかを考えてみます。の評価のために\eqref{Le4}を用いましたが明らかに
の項が
の評価を邪魔していることがわかります。例えばChebyshvの評価が得たいのなら
と取りたいものですがこれでは
があまりに大きくなりすぎるため有効な結果が得られません。一方で
が小さすぎると今度は
の項が大きくなってしまいます。
この邪魔な はそもそも\eqref{Le3}における
から生じています。この和が長すぎるがゆえに
が現れてしまうことで最終的な評価に対する誤差項の影響が大きくなってしまうというわけです。せっかくLegendreの篩という等式が得られているのに、それを単純に用いてしまうと良い評価が得られなくなってしまいます。
先にネタバレですが、この問題点を解決する方法がBrunの篩と呼ばれるものです。簡単に説明するとBrunはLegendreの篩における等式を不等式に置き換えることで、Legendreの篩を用いるよりもはるかに良い結果を生み出すことに成功しました。等式を不等式に置き換えると評価が良くなるというなんとも不思議なことが起こるわけです*4。
Brunの篩についてはいずれ別記事で紹介します。
(追記)Brunの純正篩についての記事を公開しました
mathnote.info
双子素数の場合
Legendreによる篩の定式化は数列が双子素数とは
と
の両方が素数になることを言います。素数の場合と同様にEratosthenesの篩を用いれば
に対して
が双子素数
かつ
が同値であることがわかります。ここで は
が素数であるかを判定するために
を満たすようにとる必要があります。最後の条件は明らかに
と同値です。したがって
を
\begin{align*}
\pi_2(x)=\# \{ p\le x | p:\mathbf{双子素数} \}
\end{align*}とし数列 を
\begin{equation*}
\mathcal{A}=\{ n(n+2)| n \le x\}
\end{equation*}と定めれば
\begin{equation*}
\pi_2(x)-\pi_2(z)= S(\mathcal{A},z) \quad (\sqrt{x+2} \le z \;{<} \;x)
\end{equation*}が得られます*5。
一方で に対しては\eqref{Le2}と同様に
\begin{equation*}
\pi_2(x)-\pi_2(z) \le S(\mathcal{A},z)
\end{equation*}となります。
Prop6
なる整数
に対して
\begin{equation*}
\rho (d)= \# \{ 1\le m \le d| m(m+2)\equiv 0 \;(\mathrm{mod}\; d) \}
\end{equation*}とする。このとき
\begin{equation*}
{|}\mathcal{A}_d|=x\frac{\rho (d)}{d}+R_d
\end{equation*}が成立する。ここで は
\begin{equation*}
{|}R_d|\le \rho (d)\quad (\mu(d)\neq 0)
\end{equation*}を満たす。
証明 の定義より
\begin{align*}
{|}\mathcal{A}_d{|}&=\sum_{\substack{n\le x \\ n(n+2)\equiv 0 \; (\mathrm{mod}\; d)}}1 \\
&=\sum_{\substack{1\le m \le d \\ m(m+2)\equiv 0 \; (\mathrm{mod}\; d)}}\sum_{\substack{n \le x\\ n \equiv m \; (\mathrm{mod}\; d)}}1 \\
&= \sum_{\substack{1\le m \le d \\ m(m+2)\equiv 0 \; (\mathrm{mod}\; d)}}\left( \left[ \frac{x-m}{d} \right]+1 \right) \\
&= \sum_{\substack{1\le m \le d \\ m(m+2)\equiv 0 \; (\mathrm{mod}\; d)}} \left( \frac{x}{d}+r(m) \right)
\end{align*}と書ける。ここで は
\begin{equation*}
{|}r(m)|=\left| 1- \left\{ \frac{x-m}{d} \right\} -\frac{m}{d} \right| \le 1
\end{equation*}を満たす。従って
\begin{equation*}
R_d= \sum_{\substack{1\le m \le d \\ m(m+2)\equiv 0 \; (\mathrm{mod}\; d)}}r(m)
\end{equation*}とすれば であり
\begin{equation*}
{|}\mathcal{A}_d| =x\frac{\rho(d)}{d}+R_d
\end{equation*}が成立する。(QED)
この公式をLegendreの篩に代入すれば双子素数の場合も素数と似たような議論ができそうです。そのためには についての乗法性が必要になります。
Prop7
は乗法的な数論的関数である。
証明 を互いに素な整数とする。Euclidの互除法より
となる整数
が存在する。
を
\begin{equation}
m_i(m_i+2)\equiv 0 \; (\mathrm{mod}\; d_i ) \quad (i=1,2) \label{Le5}
\end{equation}を満たす整数とし、と置く。このとき
\begin{equation*}
n\equiv m_i(1-d_ix_i) \equiv m_i \; (\mathrm{mod}\; d_i) \quad (i=1,2)
\end{equation*}であるから\eqref{Le5}より
\begin{equation*}
n(n+2)\equiv 0 \; (\mathrm{mod}\; d_1d_2)
\end{equation*}が成立する。
一方で整数 が
を満たすなら
とすれば\eqref{Le5}が成立する。さらに
\begin{equation*}
m_1d_2x_2+m_2d_1x_1 \equiv n \; ( \mathrm{mod}\; d_1 d_2)
\end{equation*}が成立する。
以上よりそれぞれの法における解が一対一に対応するので
\begin{equation*}
\rho(d_1d_2)=\rho(d_1)\rho(d_2)
\end{equation*}が示された*6。(QED)
Legendreの篩を用いて素数の場合の計算と同じことを双子素数に対して行ってみます。
Theorem8*7
\begin{equation*}
\pi_2(x) \ll \frac{x}{(\log\log x)^2} \quad (x\to \infty)
\end{equation*}
証明 の乗法性と
を用いればLegendreの篩から
\begin{align*}
S(A,z)&= x\sum_{d|P(z)}\frac{\mu(d)\rho(d)}{d}+O\left(\sum_{d|P(z)}\rho(d) \right)
\end{align*}が成立。簡単に がわかるので
\begin{align*}
\sum_{d|P(z)}\frac{\mu(d)\rho(d)}{d} &=\frac{1}{2} \prod_{3\le p\le z}\left(1-\frac{2}{p}\right) \\
&=\frac{1}{2}\prod_{3\le p \le z} \left(1-\frac{1}{(p-1)^2}\right) \left(1-\frac{1}{p}\right)^2\\
&=2\prod_{3\le p \le z}\left( 1-\frac{1}{(p-1)^2}\right) \prod_{p\le z}\left(1-\frac{1}{p}\right)^2 \\
&\ll \frac{\mathfrak{S}_2}{(\log z)^2}
\end{align*}ここで
\begin{equation*}
\mathfrak{S}_2=2\prod_{p\ge 3} \left(1-\frac{1}{(p-1)^2}\right)
\end{equation*}と置いた*8。さらに
\begin{equation*}
\sum_{d|P(z)}\rho(d)=\prod_{p\le z} (1+\rho(p)) \le 3^{\pi(z)} \le 3^z
\end{equation*}が成立する。したがって
\begin{equation*}
S(A,z) \ll \mathfrak{S}_2\frac{x}{(\log z)^2}+3^{z}
\end{equation*}が得られる。先の議論より
\begin{equation*}
\pi_2(x) \le S(A,z)+\pi_2(z) \ll \frac{x}{(\log x)^2}+3^{z}+z
\end{equation*}が成立するので とすれば所望の評価が得られる。(QED)
以上で篩を用いて双子素数の評価ができました。しかしヒューリスティックには が素数である確率は
であるため
\begin{equation*}
\pi_2(x) \sim \frac{\pi(x)}{\log x} \ll \frac{x}{(\log x)^2}
\end{equation*}であると期待できます。さらに、証明をすることはできないものの上述の証明において
\begin{equation*}
\mathfrak{S}_2\frac{x}{(\log z)^2}
\end{equation*}の項が の大きさを支配していると期待できます。実際次のような予想があります。
Hardy-Lettlewood予想
\begin{equation*}
\pi_2(x)\sim \mathfrak{S}_2\frac{x}{(\log x)^2}\quad (x\to \infty)
\end{equation*}
Hardy-Littlewood予想(と素数定理)によると双子素数の素数に対する相対漸近密度は0である*9、つまり
\begin{equation*}
\frac{\pi_2(x)}{\pi(x)}\sim \frac{\mathfrak{S}_2}{\log x} =o(1) \quad (x\to \infty)
\end{equation*}が得られますがTheorem8からはこれを導出することはできません。
Theorem8の評価はHardy-Littlewood予想と比較してはるかに弱いものですが、それでもLegendreの篩を発展させれば双子素数を数えることができるという可能性を見出すには十分な結果だと思います。
コメントとして上述の は双子素数に対する特異級数と呼ばれる定数です。特異級数は問題設定によって取り換えられますが、いずれも素数分布の理論においてそれ単体が研究対象になる重要な定数です。この後Goldbach予想についても議論しますが、そこでもGoldbach予想に関する特異級数が現れます。
Goldbach予想の場合
つぎに\begin{equation*}
N=p+p'
\end{equation*}と二つの素数の和で表すことができるかという問題です。
原理的には に対して
となることを確かめれば
\begin{align*}
\mathcal{A}=\mathcal{A}(N)=\{ n(N-n)| 1\le n\le N\}
\end{align*}と定めます。
Prop9
なる整数
に対して乗法的関数
を
\begin{equation*}
\rho(d)=\rho_N(d)=\# \{ 1\le m \le d| m(N-m) \equiv 0 \; (\mathrm{mod}\; d)\}
\end{equation*}とする。このとき
\begin{equation*}
{|}\mathcal{A}_d|=N\frac{\rho(d)}{d}+R_d
\end{equation*}が成立する。ここで は
\begin{equation*}
{|}R_d|\le \rho (d) \quad (\mu (d)\neq 0)
\end{equation*}を満たす。
証明 Prop6 及びProp7と同様に示される。(QED)
Eratosthenesの篩を用いて と
が素数か判定する場合、
である、つまり
であるような
に対して
はどちらも素数
が同値です。さらにパラメータ を
を満たすようにとれば
に対して
が同値になります。つまり
\begin{equation*}
S(\mathcal{A},z)=\# \{(p,p')| N=p+p' , p,p' > z\}+O(1)
\end{equation*}です*10。ここで最後の は
もしくは
のときに
となる可能性分の誤差です。
したがってを
\begin{equation*}
G(N)=\# \{ (p,p')| N=p+p'\}
\end{equation*}と定めれば
\begin{align*}
G(N)&=S(A,z)+O(1)+\# \{ (p,p')| N=p+p',p\; \mathrm{or} \; p' \le z\} \\
\\
&=S(\mathcal{A},z)+O(z) \quad (\sqrt{N}\le z < N/2)
\end{align*}が成立します。
のときは\eqref{Le2}と同様に
\begin{align*}
S(\mathcal{A},z)=\sum_{\substack{z\le n \le N-z \\ (n(N-n),P(z))=1}}1+O(1) \ge G(N)-O(z)
\end{align*}となります。したがって
\begin{equation}
G(N) \le S(\mathcal{A},z) +O(z) \quad (2\le z < N/2) \label{Le6}
\end{equation}を得ることができます。
以下Legendreの篩を用いて を評価しますが、計算の大略はTheorem8とほとんど同じなのでGoldbach予想に関する特異級数の導出のみ確かめていきます。
Theorem10
\begin{equation*}
G(N) \ll \mathfrak{S}(N) \frac{N}{(\log \log N)^2} \quad (2|N\ge 4)
\end{equation*}ここで
\begin{equation*}
\mathfrak{S}(N)=2\left(\prod_{\substack{p\ge 3 \\ p|N}} \frac{p-1}{p-2} \right)\prod_{p\ge 3} \left( 1-\frac{1}{(p-1)^2} \right)
\end{equation*}
証明 素数 に対して
\begin{equation*}
m(N-m)\equiv 0 \; (\mathrm{mod}\; p) \Leftrightarrow m\equiv 0 \; \mathrm{or} \; N-m \equiv 0
\end{equation*}なので なら
でそうでないなら
となる。したがってLegendreの篩を用いるときに現れる素数積は
\begin{align*}
\prod_{p\le z} \left(1-\frac{\rho(p)}{p} \right)&= \frac{1}{2} \prod_{\substack{3\le p \le z \\ p|N}}\left(1-\frac{1}{p}\right) \prod_{\substack{3\le p\le z \\ p\nmid N}}\left( 1-\frac{2}{p}\right)\\
&= \frac{1}{2}\prod_{\substack{3\le p \le z \\ p|N}}\frac{p-1}{p-2} \prod_{3\le p \le z }\left(1-\frac{2}{p}\right) \\
&=\frac{1}{2}\prod_{\substack{3\le p \le z \\ p|N}}\frac{p-1}{p-2} \prod_{3\le p \le z }\left(1-\frac{1}{p-1)^2}\right) \\
&\quad \times \prod_{3\le p \le z}\left(1-\frac{1}{p}\right)^2\\
&=2\prod_{\substack{3\le p \le z \\ p|N}}\frac{p-1}{p-2} \prod_{3\le p \le z }\left(1-\frac{1}{(p-1)^2}\right) \\
&\quad \times \prod_{p \le z}\left(1-\frac{1}{p}\right)^2
\end{align*}したがって
\begin{align*}
\prod_{p\le z} \left(1-\frac{\rho(p)}{p} \right) \ll \frac{\mathfrak{S}(N)}{(\log z)^2}
\end{align*}が成立する。残りの議論はTheorem8と同様に済む。(QED)
Goldbach予想は偶数が二つの素数の和で書けるかという予想ですが、より強く の漸近式が予想されています。
Hardy-Lettlewood予想
\begin{equation*}
G(N)\sim \mathfrak{S}(N)\frac{N}{(\log N)^2} \quad (2|N, N\to \infty)
\end{equation*}
篩法とはなにか
ここまで素数、双子素数、Goldbach予想について計算してきましたが、総じて次のような問題に集約されます。篩法の問題設定
を整数列とし
とする。さらにある
と乗法的関数
と
を満たす関数
に対して
\begin{equation*}
{|} \mathcal{A}_d|=\frac{\rho(d)}{d} X+R_d \quad (\mu(d) \neq 0)
\end{equation*}が成立していると仮定する。このとき
\begin{equation*}
S(\mathcal{A},z)=\sum_{\substack{a\in \mathcal{A}\\ (a,P(z))=1}}1=\sum_{d|P(z)}\mu(d)|\mathcal{A}_d|
\end{equation*}の良い評価を得よ。
これが最も基本的な問題設定であり、この問題に取り組む過程で篩法は一大理論として発展していきました。現状では篩法は双子素数予想などに有効なほとんど唯一の方法として存在感を高めており、さらには素数への応用だけでなくゼータ関数の理論などにも応用されています。
おわりに
いかがでしたか。もしかすると篩法に興味がわいてきたのではないでしょうか...!篩法のBrunによる発展はごく初等的な計算のみによるもので大学一年生程度の知識があれば概ね理解可能です。それにもかかわらず篩法の発見はRiemann zeta関数による素数定理の証明より20年以上後のことであることも面白い点だと思います。もしかすると数学にはまだまだ人類の知らない簡単かつ強力な理論が隠されているのかもしれないと思うとわくわくしますね!
*1:を篩にかけるとはすなわち
を考察することである。その意味で
を
を引数に持つSieving function(直訳は篩関数)などと呼ぶことがある。
*2:より多くの条件の下でさらに計算をすすめたものをLegendreの篩と呼ぶ方が一般的だがここではTheorem2をLegendreの篩と呼ぶ。
*3:最後の不等式は と
を比較すれば得られる。
*4:ちなみに問題によってはLegendreの篩と同等の方法が有効なときもある。例えば三素数定理のVinogradovによる証明など。
*5:この場合は右辺の和に1が現れないので調節は不要。
*6:中国剰余定理と同一の議論。
*7:この結果と後述のTheorem10は素数定理を考えれば文字通り自明な結果。Legendreの篩ではこの程度の結果が限界である。
*8:はフラクトゥールのS。
は定数なのでここでの議論には関係しないが、素数の理論において重要な定数なので明記した。
*9:自然数全体において素数が現れることが''レア''であることと同じくらい、素数全体において双子素数が現れることは''レア''と言える
*10:この操作についてはEratosthenesの篩(ふるい)と篩法 - プライムスの最後のGifが理解の参考になるかも。
Eratosthenesの篩(ふるい)と篩法
素数分布論における手法である篩法*1に関する入門記事です。本記事では篩法の原点であるEratostheneの篩と双子素数やGoldbach予想との関連を簡単に紹介します。
素数に関する諸問題
解析的な素数分布論におけるもっとも基本的な問題は素数の個数を問う問題です。つまり\begin{equation*}
\pi(x)\sim \frac{x}{\log x} \quad (x\to \infty)
\end{equation*}を示すことができます。素数定理を代表されるように
つづいて素数に関する有名な二つの未解決問題を紹介します。
双子素数予想
素数 で
も素数であるようなものが無限に存在する。
Goldbach予想
4以上の全ての偶数は二つの素数の和で書ける。
これらの問題は100年以上考察されていますが未解決のままです。その主な理由としてRiemann zeta関数を用いた議論だけではこの問題に一切アプローチができないことが挙げられます。残念なことに双子素数の性質を記述する"ゼータ関数"は今のところ発見されていません。
この状況を打開するために開発された方法が篩法です。篩法の特徴的な点として
- 双子素数予想やGoldbach予想にアプローチするほとんど唯一の方法である
- ほとんどの議論が初等的な計算のみで構成される
- Riemann zeta関数の理論と合わせることで非常に強力な結果が得られる
などが挙げられます。ここで初等的な計算というのは概ね大学1年生の解析学程度の知識があればできる計算のことです。
篩法で何がわかるのか
篩法はEratosthenesの篩のLegendreによる定式化をViggo Brunが応用したことから始まりました。まずは篩法を用いるとどんな定理が証明できるのか？について適当な代表例を紹介します。Thm A (V. Brun, 1919)
を素数
のうち
もまた素数であるようなもの(
以下の双子素数)の個数とする。このとき
\begin{equation*}
\pi_2(x) \ll \frac{x}{(\log x)^2} \quad (x\to \infty)
\end{equation*}が成立する。特に双子素数の逆数和は収束する。
Thm B (J. Chen, 1973)
十分大きな任意の偶数 に対し素数
と高々二つの素数の積である数
が存在して
\begin{equation*}
n=p+q
\end{equation*}が成立。
Thm C (J. Maynard, 2015)
で昇順に並べた素数全体の列とする。このとき\begin{equation*}
\liminf_{n\to \infty} (p_{n+1}-p_n) \le 600
\end{equation*}が成立する。
Thm Aは双子素数予想に関連する命題でVigoo Brun(1919)によって証明されました。篩法における最初の結果で、これを皮切りに篩法の理論が構築されていくことになります。
Thm BはGoldbach予想に関連する問題で、の素因子をあと一つ減らせばGoldbach予想が解決するというところまで迫った結果です。
Thm Cも双子素数予想に関連する問題です。双子素数予想は
\begin{equation*}
\liminf_{n\to \infty} (p_{n+1}-p_n)=2
\end{equation*}と同値であることが容易にわかります。双子素数予想より弱い主張である
\begin{equation*}
\liminf_{n\to \infty}(p_{n+1}-p_n)< \infty
\end{equation*}はBounded gap conjectureと呼ばれ長い間関心を集めていました。Bounded gap conjecture自体はMaynardのThm Cより早くY. Zhang(2013)において解決されていましたが、MaynardによるThm Cの証明が非常に簡単なためこちらの方が有名な気がします。
プライムスでも双子素数予想やGoldbach予想を題材に幾つかの記事に分けて篩法を学習し、上述の定理の証明を目標にして執筆していきます。
Eratosthenesの篩
篩法の原点はEratosthenesの篩にあります。ここではEratosthenesの篩を紹介し、それがどのように双子素数予想やGoldbach予想に関連するのかを考えます。Thm (Eratosthenesの篩)
を自然数とする。このとき次の二つは同値。
(i) は素数
(ii) は
以下の素因子を持たない
証明 が
以下の素数で割り切れるなら明らかに
は素数ではない。したがって(i)
(ii)が成立。一方で
が合成数なら
を割り切る二つの素数
が存在する。もし
なら
となり矛盾する。したがって少なくとも片方の素数は
以下でなければならない。つまり(ii)
(i)が成立。 (QED)
定義から が素数であるかを判定するためには
以下の素数で割り算を実行する必要がありますが、Eratosthenesの篩によって
以下の素数のみ確かめれば良いことがわかりました。実際に与えられたEratosthenesの篩を用いて与えられた数表から素数を見つけてみます。
このような操作によって数表から素数をふるいだしたことのある方は多いと思います。
今度は少々工夫してEratosthenesの篩によって双子素数を見つけ出したいと思います。
このような数表を用意してEratosthenesの篩にかけることで双子素数も見つけ出すことができます。
さらに工夫して今度はGoldbach予想について考えてみます。偶数 に対して
\begin{equation*}
G(N)=\# \{(p,p')| p,p':\mathbf{素数}, N=p+p'\}
\end{equation*}と定めます。Eratosthenesの篩を用いることで機械的に の値を求めることができます。具体的に
を計算してみます。
簡単な例でしたが、これらの例によってEratosthenesの篩が双子素数予想やGoldbach予想へのアプローチに役立つことを感じることができたと思います。
おわりに
今回はここまでにして、また別の記事で篩法の理論的な面を考察していきたいと思います。(追記) Erathosthenesの篩の理論的側面についての記事を公開しました
mathnote.info
最後に篩法における典型的なテキストであり、また今後の記事を書くために用いるテキストを紹介します。
参考文献
リンク
リンク
リンク
*1:素因数分解のアルゴリズムである数体ふるい法とは無関係
Dirichlet L関数の基本性質と関数等式
Dirichlet L関数についての簡単な性質を紹介し関数等式を証明します。
Dirichlet L関数は算術級数の素数定理の証明にも用いられる非常に重要な複素関数のクラスです。
参考文献
(1)素数とゼータ関数 (共立講座 数学の輝き)リンク
(2)Multiplicative Number Theory (Graduate Texts in Mathematics 74)
リンク
(3) 解析的整数論〈1〉素数分布論 (朝倉数学大系)
リンク
Dirichlet L関数は Dirichlet指標と密接に関係しています。Dirichlet指標については以下の記事の結果を引用します。
mathnote.info
mathnote.info
Dirichlet L関数の定義と性質
Dirichlet指標\begin{equation*}
L(s,\chi)=\sum_{n=1}^\infty \frac{\chi(n)}{n^s}
\end{equation*}と定め、これを指標
Lem1
が自明指標なら
は
で広義一様に収束して正則関数となる。
が非自明指標なら
は
で広義一様に収束して正則関数となる。
証明 まず が自明指標のときは
で広義一様に絶対収束することがわかるので、この範囲で
が正則関数であることがわかる。一方
が非自明指標の場合はDirichlet指標について - プライムスの定理4から
\begin{equation}
\sum_{n=1}^N \chi(n) \le q \quad (\forall N \in \mathbb{N}) \label{eq1}
\end{equation}が成立。Abel総和公式を用いることで
\begin{equation*}
\sum_{n\le x} \frac{\chi(n)}{n^s}=\frac{\sum_{n\le x}\chi(n)}{x^s}+s\int_1^{\infty}\frac{\sum_{n\le t}\chi(n)}{t^{s+1}} \; dt
\end{equation*}と表せるが、\eqref{eq1}より なら
で第一項は 0に収束し第二項は広義一様に絶対収束することがわかる。したがって主張が示された。(QED)
従って が非自明指標なら
が
で正則になるのでリーマンゼータ関数のような
での極は発生しません。つまりL関数の特殊値
を考えることができるのですが、この値を正確に求める問題は解析数論における難問の一つとして残っています*1。
Euler積表示
Dirichlet L関数も素数にわたる無限積表示であるEuler積表示を持つことが知られています。Thm2(Euler積表示)
任意のDirichlet指標 に対して
\begin{equation*}
L(s,\chi)=\prod_{p}\left( 1-\frac{\chi(p)}{p^s}\right)^{-1} \quad (\Re (s) >1)
\end{equation*}が成立。
証明 を昇順の全ての素数列とする。
の定義級数は
で絶対収束するので、
の完全乗法性に注意して
に対し
\begin{equation*}
L(s,\chi)-\frac{\chi(2)}{2^s}L(s,\chi)=1+\frac{\chi(3)}{3^s}+\frac{\chi(5)}{5^s}+\frac{\chi(7)}{7^s}+\cdots
\end{equation*}となる。同様に に対し
\begin{align*}
&\left(1-\frac{\chi(2)}{2^s}\right)L(s,\chi)-\frac{\chi(3)}{3^s}\left(1-\frac{1}{2^s}\right)L(s,\chi) \\
&=\left(1-\frac{\chi(2)}{2^s}\right)\left(1-\frac{\chi(3)}{3^s}\right)L(s,\chi) \\
&=1+\frac{\chi(5)}{5^s}+\frac{\chi(7)}{7^s}+\frac{\chi(11)}{11^s}+\cdots
\end{align*}と計算できる。この操作を まで続けることで
\begin{equation*}
\prod_{n=1}^{N-1}\left(1-\frac{\chi(p_n)}{p_n^s}\right)L(s,\chi)=1+\frac{\chi(p_N)}{p_N^s}+\cdots
\end{equation*}が得られるが、この右辺の和は なら
\begin{equation*}
\left| \frac{\chi(p_N)}{p_N^s}+\cdots \right| < \sum_{n=N}^{\infty}\frac{1}{n^{\Re(s)}} \to 1 \quad (N\to \infty)
\end{equation*}となるから の極限を取ることで
\begin{equation*}
\prod_p\left(1-\frac{\chi(p)}{p^s}\right)L(s,\chi)=1
\end{equation*}が得られる。(QED)
法 の指標
が法
の指標
で生成されるとは\begin{equation*}
\chi(n)=
\begin{cases}
\chi_1(n) \quad &((n,q)=1) \\
0 \quad &((n,q)>1)
\end{cases}
\end{equation*}が成立することを言います。が
から生成されるとき、Euler積を用いることで付随するDirichlet L関数の間の関係式を導くことができます。
Cor3
とし、
は法
のDirichlet指標で
は
を生成する法
のDirichlet指標とする。このとき
\begin{equation*}
L(s,\chi)=\prod_{p|q}\left( 1-\frac{\chi_1(p)}{p^s}\right) L(s,\chi_1)
\end{equation*}が成立する。
証明 Euler積表示を用いれば
\begin{equation*}
L(s,\chi)=\prod_{(p,q)=1}\left( 1-\frac{\chi_1(p)}{p^s}\right)^{-1}=\prod_{p|q}\left( 1-\frac{\chi_1(p)}{p^s}\right) L(s,\chi_1)
\end{equation*}となる。(QED)
特に法 の自明指標
に付随するDirichlet L関数は
\begin{equation*}
L(s,\chi_0)=\prod_{p|q} \left(1-\frac{1}{p^s} \right) \zeta(s)
\end{equation*}とリーマンゼータ関数を用いて書くことができます。またこの公式よりほとんどの場合 が原始指標のときのみを考えればよいことがわかります。また関数等式を含むL関数に対する主張の多くが
が原始指標のときのみ成立します。さらに因子
は虚軸上に零点を持つことが容易に分かるので、
が非原始指標なら
(を解析接続したもの)が虚軸上に零点を持つことがわかります。
関数等式の証明に必要な補題
Dirichlet L関数の関数等式は概ねリーマンゼータ関数の関数等式の証明と同じ方法で示すことができます。ただし、Dirichlet指標に関する知識などが必要になるためここでまとめておきます。Lem4(Gauss和の性質)
を法
の原始的Dirichlet指標とし
\begin{equation*}
\tau (\chi ):=\sum_{n=1}^q \chi(n) e^{2\pi i n /q}
\end{equation*}とする。この時、
\begin{equation}
\chi(n) \tau (\bar{\chi})=\sum_{h=1}^q\bar{\chi}(h)e^{2\pi i n h /q} \quad (\forall n \in \mathbb{Z}) \label{eq2}
\end{equation}及び
\begin{equation}
{|} \tau (\chi)|=q^{1/2} \label{eq3}
\end{equation}が成立する。
証明 Dirichlet指標のGauss和について - プライムスを参照。(QED)
Lem5
任意のに対し
\begin{equation}
\sum_{n=-\infty}^{\infty}e^{-n^2\pi x+2\pi i n \alpha}
=x^{-1/2}\sum_{n=-\infty}^{\infty}e^{-(n+\alpha)^2\pi /x}
\label{eq4}
\end{equation}が成立する。
証明 Poissonの和公式とテータ関数のモジュラー関係式 - プライムスを参照。(QED)
Lem6
任意のに対し
\begin{equation}
\sum_{n=-\infty}^{\infty}ne^{-n^2\pi x+2\pi i n \alpha}
=ix^{-3/2}\sum_{n=-\infty}^{\infty}(n+\alpha)e^{-(n+\alpha)^2\pi /x}
\label{eq5}
\end{equation}が成立する。
証明 を固定すると\eqref{eq4}の両辺は変数
の関数と見ることができる。両辺ともに和は一様に絶対収束するので
について項別に微分できて
\begin{equation*}
\sum2\pi i ne^{-n^2\pi x+2\pi i n \alpha}=-x^{-1/2}\sum2(n+\alpha)\frac{\pi}{x}e^{-(n+\alpha)^2\pi /x}
\end{equation*}が得られる。これを整理すれば\eqref{eq5}が得られる。(QED)
Dirichlet L関数の関数等式
まず関数等式の主張を見ていきます。Dirichlet L関数の関数等式の証明には\begin{equation*}
\epsilon_{\chi}=
\begin{cases}
0 \quad &(\chi(-1)=1) \\
1 \quad &(\chi(-1)=-1)
\end{cases}
\end{equation*}と定めます。さらに簡単のため
\begin{equation*}
\xi(s,\chi)=\left( \frac{\pi}{q}\right)^{-(s+\epsilon_{\chi})/2}\Gamma \left(\frac{s+\epsilon_{\chi}}{2} \right) L(s,\chi)
\end{equation*}という複素関数を用います。次がDirichlet L関数に対する関数等式です。
Thm7(関数等式)
を法
の原始指標とする。このとき
は
に解析接続され
\begin{equation*}
\frac{i^{\epsilon_{\chi}}q^{1/2}}{\tau(\chi)}\xi(s,\chi)=\xi(1-s,\bar{\chi})
\end{equation*}が任意の で成立する。
リーマンゼータ関数の場合と比べて余計な因子 がかかっていたり、変数
を
とシフトしていたりと幾分複雑です。さらに関数等式は
と
という異なる関数の間に成立する関係式となっています。しかし証明自体の難易度はリーマンゼータ関数とほぼ同じです。
Thm5を証明するために、まずはガンマ関数とL関数を関係付ける次の補題を示します。
Lem8
関数 を
\begin{equation*}
\omega(x,\chi)=\sum_{n=1}^{\infty}n^{\epsilon_{\chi}}\chi(n)e^{-n^2\pi x/q}
\end{equation*}と定める。このとき
\begin{equation}
\xi(s,\chi)=\int_{0}^{\infty} x^{(s+\epsilon_{\chi})/2-1}\omega (x,\chi) \; dx \label{eq8}
\end{equation}が で成立する。
証明 ガンマ関数の定義式より
\begin{equation*}
\Gamma \left(\frac{s+\epsilon_{\chi}}{2}\right) =\int_0^{\infty}e^{-t}t^{(s+\epsilon_{\chi})/2-1} \;dt
\end{equation*}が で成立。積分変数を自然数
に対して
と変数変換すれば
\begin{equation*}
\left( \frac{\pi}{q}\right)^{-(s+\epsilon_{\chi})/2}\Gamma\left(\frac{s+\epsilon_{\chi}}{2} \right) n^{-s}=\int_0^{\infty} x^{(s+\epsilon_{\chi})/2-1}n^{\epsilon_{\chi}}e^{-n^2\pi x/q}\; dt
\end{equation*}が得られる。したがって両辺に をかけた後、
に関する和を取ることで
\begin{equation*}
\xi(s,\chi)=\sum_{n=1}^{\infty}\int_0^{\infty} x^{(s+\epsilon_{\chi})/2-1}n^{\epsilon_{\chi}}\chi(n)e^{-n^2\pi x/q}\; dt
\end{equation*}が得られる。最後の無限和と積分は
\begin{equation*}
\int_0^{\infty} \left( \sum_{n=1}^{\infty}\; x^{(\sigma+\epsilon_{\chi})/2-1}n^{\epsilon_{\chi}}e^{-n^2\pi x/q}\right) \; dt
\end{equation*}が で収束することから
で和と積分の順序を交換することができ主張が従う。(QED)
次にLem4~Lem6を用いて の関数等式を証明します。
Lem9
が法
の原始的Dirichlet指標なら、任意の
に対して
\begin{equation}
\tau(\overline{\chi})\omega(x,\chi)=\left(\frac{i}{x}\right)^{\epsilon_{\chi}}\left(\frac{q}{x}\right)^{1/2}\omega \left(\frac{1}{x},\overline{\chi}\right) \label{eq6}
\end{equation}が成立する。
証明 の定義から
\begin{equation*}
2\omega(x,\chi)=\sum_{n=-\infty}^{\infty}n^{\epsilon_{\chi}}\chi(n)e^{-n^2\pi x/q}
\end{equation*}が成立。この両辺に をかけてLem4の\eqref{eq2}を適用すると
\begin{equation}
2\tau(\bar{\chi})\omega(x,\chi)=\sum_{h=1}^q \bar{\chi}(h) \sum_{n=-\infty}^{\infty} n^{\epsilon_{\chi}}e^{-n^2\pi x/q+2\pi i nh/q} \label{eq7}
\end{equation}が得られる。次にこの公式の に関する和に対してLem5とLem6を適用する。
のときは\eqref{eq4}を
として適用することで
\begin{equation*}
\sum_{n=-\infty}^{\infty}e^{-n^2\pi x/q+2\pi i n h/q}=\left( \frac{q}{x} \right)^{1/2}\sum_{n=-\infty}^{\infty}e^{-(qn+h)^2\pi /qx}
\end{equation*}が得られる。一方で のときは \eqref{eq5}を
として適用することで
\begin{equation*}
\sum_{n=-\infty}^{\infty}ne^{-n^2\pi x/q+2\pi i n h/q}=\left( \frac{i}{x}\right) \left( \frac{q}{x} \right)^{1/2} \sum_{n=-\infty}^{\infty} (qn+h)e^{-(qn+h)^2\pi /qx}
\end{equation*}が得られる。これらの結果はまとめて
\begin{align*}
&\sum_{n=-\infty}^{\infty}n^{\epsilon_{\chi}}e^{-n^2\pi x/q+2\pi i n h/q}\\
&=\left( \frac{i}{x}\right)^{\epsilon_{\chi}} \left( \frac{q}{x} \right)^{1/2} \sum_{n=-\infty}^{\infty} (qn+h)^{\epsilon_{\chi}}e^{-(qn+h)^2\pi /qx}
\end{align*}と書くことができる。この式を\eqref{eq7}に代入すれば
\begin{align*}
&2\tau(\bar{\chi})\omega(x,\chi) \\
&=\left( \frac{i}{x}\right)^{\epsilon_{\chi}} \left( \frac{q}{x} \right)^{1/2}\sum_{h=1}^q \sum_{n=-\infty}^{\infty} \bar{\chi}(h)(qn+h)^{\epsilon_{\chi}}e^{-(qn+h)^2\pi /qx}
\end{align*}となるが、に注意すればこれは
\begin{align*}
&=\left( \frac{i}{x}\right)^{\epsilon_{\chi}} \left( \frac{q}{x} \right)^{1/2}\sum_{h=1}^q \sum_{n=-\infty}^{\infty} \bar{\chi}(qn+h)(qn+h)^{\epsilon_{\chi}}e^{-(qn+h)^2\pi /qx} \\
&=\left( \frac{i}{x}\right)^{\epsilon_{\chi}} \left( \frac{q}{x} \right)^{1/2}\sum_{n=-\infty}^{\infty}\bar{\chi}(n)n^{\epsilon_{\chi}}e^{-n^2\pi /qx} \\
&=2\left( \frac{i}{x}\right)^{\epsilon_{\chi}} \left( \frac{q}{x} \right)^{1/2} \omega\left(\frac{1}{x},\bar{\chi}\right)
\end{align*}と書き直せる。したがって主張が示された。(QED)
以上で準備は終わりです。L関数の関数等式を証明します。
Thm7の証明 Lem8の\eqref{eq8}の積分を の部分と
の二つに分割し、
の方の積分のみ
と変数変換すれば
\begin{align*}
\xi(s,\chi)=&\int_1^{\infty}x^{-(s+\epsilon_{\chi})/2-1}\omega \left( x^{-1},\chi \right) dx \\
&+\int_1^{\infty}x^{(s+\epsilon_{\chi})/2-1}\omega(x,\chi) \; dx
\end{align*}さらに一つ目の積分にLem9の\eqref{eq6}を を
に置き換えて代入すれば
\begin{align}
=&\frac{i^{\epsilon_{\chi}}q^{1/2}}{\tau(\bar{\chi})}\int_1^{\infty}x^{-(s-\epsilon_{\chi})/2-1/2}\omega(x,\bar{\chi}) \; dx \notag \\
&+\int_1^{\infty}x^{(s+\epsilon_{\chi})/2-1}\omega(x,\chi) \; dx. \label{eq10}
\end{align}が得られる。最後の積分は両方とも全平面で絶対収束するので \eqref{eq10}は の全平面への解析接続を与えている。ここで
が定義から容易に分かること、及びLem4の\eqref{eq3}に注意すれば
\begin{equation*}
\frac{i^{\epsilon_{\chi}}q^{1/2}}{\tau(\chi)} \cdot \frac{i^{\epsilon_{\chi}}q^{1/2}}{\tau(\bar{\chi})}=1
\end{equation*}が成立。したがって\eqref{eq10}の両辺に をかけると
\begin{align*}
\frac{i^{\epsilon_{\chi}}q^{1/2}}{\tau(\chi)}\xi(s,\chi)&=\int_1^{\infty}x^{-(s-\epsilon_{\chi})/2-1/2}\omega(x,\bar{\chi}) \; dx \\
&\quad +\frac{i^{\epsilon_{\chi}}q^{1/2}}{\tau(\chi)}\int_1^{\infty}x^{(s+\epsilon_{\chi})/2-1}\omega(x,\chi) \; dx
\end{align*}この右辺は再び\eqref{eq10}より
\begin{equation*}
=\xi(1-s,\bar{\chi})
\end{equation*}となる。したがって主張が示された。(QED)
一般化されたRiemann予想
Euler積と関数等式から原始指標に付随するDirichlet L関数の零点についての情報を取り出すことができます。Thm10(L関数の自明零点)
任意の指標 に対し
は
で一位の零点を持つ。これら以外の零点は
の範囲にある。
証明 まずThm2のEuler積表示からすべてのDirichlet L関数 は
に零点を持たないことに注意。したがって
も
に零点を持たないことがわかる。
の定義式
\begin{equation*}
\xi(s,\chi)=\left( \frac{\pi}{q} \right)^{-(s+\epsilon_{\chi})/2}\Gamma\left( \frac{s+\epsilon_{\chi}}{2}\right) L(s,\chi)
\end{equation*}において、最初の因子 は零点も極も持たない関数である。一方
は
に一位の極を持ち零点は持たない。
はThm7より整関数であるから
はここで零点をもち、関数等式よりこれらの零点は全て一位の零点であることがわかる。もしこれらの零点以外に
に
の零点があるなら関数等式より矛盾が生じる。したがって主張が示される。(QED)
の
にある零点を非自明零点と呼びます。Riemann予想は次のようにDirichlet L関数にも一般化されます。
Con11(一般化されたRiemann予想)
原始指標 に付随するL関数
の任意の非自明零点
は
を満たす。
おわりに
Dirichlet L関数に対する関数等式の初出はHurwitz(1882)だそうです。一般化されたRiemann予想の初出はA.Piltz(1885)だそうです。
*1:は
が実指標のとき
のごく近くの実軸上に零点を持つかもしれないことが知られている。この零点の非存在を示すことは解析数論のひとつの目標であるが、
の下からの鋭い評価を求めることで
の近くに零点が存在しないことが証明できる。
