素数定理のRichterによる新しい初等的証明の調査

素数定理

★ $N$ 以下の素数の個数を $\pi(N)$ と表すとき,

$\displaystyle \lim_{N\to \infty}\frac{\pi(N)}{N/\log N}=1 \tag{1}$

が成り立つ.

1.1 この記事では2020年2月9日にarXivに投稿されたFlorian K. Richterの論文

A new elementary proof of the Prime Number Theorem, arXiv:2002.03255.

で提示された $(1)$ 式の新しい証明の解説を試みる.

1.2 Richterはノースウェスタン大学の若い数学者で, 近年の数学上の大成果である "Erdős sumset conjecture" を解決した3人の数学者のうちの1人である:

J. Moreira, F. K. Richter, D. Robertson, A proof of the Erdős sumset conjecture, Annals of Mathematics, Volume 189 (2019), Issue 2, pp. 605-652.

Erdős sumset conjectureは次のような主張である:

定理上漸近密度が正であるような自然数からなる無限集合 $A$ に対し, 必ずある自然数からなる無限集合 $B, C$ が存在して, $A\supset B+C$ が成り立つ. ここで, $B+C:=\{b+c \mid b\in B, c\in C\}$ である.

1.3 Richterによる素数定理の新証明の流れを数学的厳密性を犠牲にしてここにラフに記述する.

Mertens関数の商 $M=M(N)/N$ が $0$ に漸近することを示したい(これが示されると素数定理が従う $\to$ 2.1).

証明全体においてキーとなるのは, よい条件を満たす, 自然数からなる2つの有限集合 $B_1$ , $B_2$ の存在である(Richterの集合などと呼んでもよいかもしれない $\to$ 3.2).

$B_1, B_2$ はともに「その集合からランダムに2元を選んだとき, それらが互いに素である確率が非常に高い」という条件を満たし, $B_1$ と $B_2$ とではある種のパリティが異なるが, その個数分布は $\rho$ 進的に連動している. ここで, $\rho$ は $1$ より少しだけ大きい数であり, 「個数分布が $\rho$ 進的に連動する」とは, 任意の $j\geq 0$ に対して $\#(B_1\cap (\rho^j, \rho^{j+1}])=\#(B_2\cap (\rho^j, \rho^{j+1}])$ が成り立つことをいう.

$B_1$ に対応する量 $E_1$ および $B_2$ に対応する量 $E_2$ を定義することができるが, 「その集合からランダムに2元を選んだとき, それらが互いに素である確率が非常に高い」という条件から, 簡単な計算により

$M-E_1 \approx 0$

を導出できる. 「 $B_1$ と $B_2$ とではある種のパリティが異なる」ということから, $B_2$ に対する同様の計算結果は

$M+E_2 \approx 0$

となる( $\to$ 3.1, 3.6). 一方, 「 $B_1$ と $B_2$ の個数分布が $\rho$ 進的に連動する」ことからは

$E_1 \approx E_2$

が言える( $\to$ 3.7). 以上を組み合わせると

$\displaystyle M \approx 0$

と素数定理が導かれる( $\to$ 3.11).

1.4 上記議論は素数定理の証明における新しい議論であり, Richterの集合の存在が確定した後の議論は初等的な不等式評価のみで実行される. Richterの集合の存在性には素数分布の情報が必要となるが, それはいわゆるChebyshevの定理で本質的に事足りる. 参考文献の[note]の言葉遣いでいけば第二世代のビッグ・オー不等式に対応し, 第三世代のビッグ・オー不等式であるSelbergの漸近公式([note]の定理7.2)は一切使わない真に新しい証明である. もちろんRiemannのゼータ関数および複素関数論も用いていない.

なお, Selbergの漸近公式に依らない初等的な素数定理の新証明は1984年にDaboussiによっても与えられているが, そのことも含めてRichterの論文の一ページ目に小気味好く解説されている.

松本先生の教科書『リーマンのゼータ関数』(朝倉書店)では

ただし, 初等的方法の効力は今のところ解析的方法には及ばないのであって, 初等的方法で得られる誤差項評価は現在最良のものでも定理3.1の古典的な誤差高評価 $O(x\exp(-c_1\sqrt{\log x})$ にすら届かない.

という文があり, Selberg-Erdősの初等的証明の発見はそれなりの驚きと意義があったであろうけれども, 導出できる定理の強さの観点ではRiemannゼータ関数を用いる証明には劣っていると言えなくない. すると, 初等的証明を新たに発見することは単なる趣味のようなもので, 数学的意義が殆どないようにも思われるかもしれない.

しかしながら, 新しい証明にはそれまでの証明にはなかったポテンシャルが秘められている可能性があるのでその探求には常に意義があると私は思うし, Richterの証明の場合には既に応用が発見されている.

今回のRichterによる証明はSarnak予想とChowla予想に関連する近年の研究の発展にインスパイアされたものとのことで, 既に別の論文

V. Bergelson, F. K. Richter, Dynamical generalizations of the Prime Number Theorem and disjointness of additive and multiplicative semigroup actions, arXiv:2002.03498.

において同様の手法を用いて素数定理の力学系的, エルゴード理論的な一般化が与えられている. この意味でもRichterの素数定理の証明法を学んでおくことは今後この分野の研究の進展を追うためにも必須となるかもしれない.

Notation:
集合 $S$ の元の個数を $\#S$ で表す.
$\mathbb{N}$ : 自然数全体の集合. ただし, この記事では便宜上, 自然数は $1$ 以上とする.
$\mathcal{P}$ : 素数全体の集合.
$\mathcal{P}_k$ : 相異なる $k$ 個の素数の積として表されるような自然数全体のなす集合.
$N\in \mathbb{N}$ に対し, $[N]:=\{1,2,\dots,N\}$ を表す.
集合 $S\subset \mathbb{N}$ の空でない有限部分集合 $A\subset S$ および関数 $f\colon S\to \mathbb{C}$ に対して,

$\begin{align} &\mathbb{E}_{n\in A}\bigl(f(n)\bigr):=\frac{1}{\#A}\sum_{n\in A}f(n),\\ &\mathbb{E}_{n\in A}^{\log}\bigl(f(n)\bigr):=\frac{\sum_{n\in A}f(n)/n}{\sum_{n\in A}1/n}. \end{align}$

$\mu\colon \mathbb{N}\to \{0,\pm1\}$ : Möbius関数.
$\lfloor x\rfloor$ : $x$ を超えない最大の整数.
$o$ および特定の近傍で $O$ を考える場合, "as $x\to \infty$ " のような条件を添え字で明記する. $O$ に添え字が付いていない場合は考えている範囲全体で不等式が成立するものとする.
$\mathbf{1}_A$ は集合 $A$ の指示関数(特性関数).
$\mathbf{1}_{m\mid n}$ は $m\mid n$ のとき $1$ , $m\nmid n$ のときに $0$ を意味する.
$\mathrm{gcd}(m,n)$ : $m$ と $n$ の最大公約数.
$A,B\subset \mathbb{N}$ に対して、 $A+B:=\{a+b \mid a\in A, b \in B\}$ , $A\cdot B:=\{ab \mid a\in A, b \in B\}$ .

References
[note] 次のページからダウンロードできるPDFファイルにおいてSelbergによる素数定理の初等的証明がまとめられているが, そこから幾つかの事実を引用することにする:
note.com

[A] T. M. Apostol, Introduction to Analytic Number Theory, Undergraduate Texts in Mathematics, Corrected fifth printing, Springer, 1998.

2.1 素数定理には多数の同値な主張があり, 通常 $(1)$ そのものではなく, いずれかの同値な主張を選択してそれを証明することになる. Richterが選んだのは少なくともLandauに遡ることができる

$\displaystyle \lim_{N\to \infty}\mathbb{E}_{n\in[N]}\bigl(\mu(n)\bigr) = 0 \tag{2}$

だ. 読者の利便性を考えて $(2) \Longrightarrow (1)$ の証明を[A]から引っ張ってきてここに記しておこう.

2.2 $x\geq 1$ に対して

$\displaystyle \psi(x)=x-\sum_{\substack{m,n\in \mathbb{N} \\ mn\leq x}}\mu(m)\bigl(d(n)-\log n-2\gamma\bigr)+O(1)$

が成立する.

ここで, $\psi(x)$ は第二Chebyshev関数([note]の定義6.13), $d(n)$ は $n$ の正の約数の総和, $\gamma$ はEulerの定数([note]の命題5.4).

証明. 和における $m,n$ は $\mathbb{N}$ の元をはしるものとする. まず,

$\displaystyle \lfloor x\rfloor=\sum_{n\leq x}1,\quad \psi(x)=\sum_{n\leq x}\Lambda(n),\quad 1=\sum_{n\leq x}\left\lfloor \frac{1}{n}\right\rfloor$

が成り立つことに注意する. ここで, $\Lambda$ はvon Mangoldt関数([note]の定義6.9)で真ん中の等式は第二Chebyshev関数の定義に他ならない.

次に, 必要なら[note]の補題6.10を参照して

$\displaystyle d(n)=\sum_{m\mid n}1,\quad \log n=\sum_{m\mid n}\Lambda(m),\quad 1=\sum_{m\mid n}\left\lfloor\frac{1}{m}\right\rfloor$

が成り立つが, それぞれにMöbiusの反転公式([note]の命題6.8)を適用することにより

$\displaystyle 1=\sum_{m\mid n}\mu(m)d\left(\frac{n}{m}\right),\quad \Lambda(n)=\sum_{m\mid n}\mu(m)\log\frac{n}{m},\quad \left\lfloor\frac{1}{n}\right\rfloor=\sum_{m\mid n}\mu(m)$

を得る. 以上を組み合わせると

$\begin{align} \lfloor x\rfloor-\psi(x)-2\gamma&=\sum_{n\leq x}\left(1-\Lambda(n)-2\gamma\left\lfloor\frac{1}{n}\right\rfloor\right)\\ &=\sum_{n\leq x}\sum_{m\mid n}\mu(m)\left(d\left(\frac{n}{m}\right)-\log\frac{n}{m}-2\gamma\right)\\ &=\sum_{mn\leq x}\mu(m)\bigl(d(n)-\log n-2\gamma\bigr) \end{align}$

と計算でき, これから直ちに所望の等式に到達する. Q.E.D.

ここまで再チェック完了.

2.3 [note]の補題6.15より $(1)$ は

$\psi(x)=(1+o_{x\to\infty}(1) )x$

と同値である. 従って, 2.2より, $(2) \Longrightarrow (1)$ を示すためには $(2)$ の仮定のもと

$\displaystyle \sum_{mn\leq x}\mu(m)\bigl(d(n)-\log n-2\gamma\bigr)=o_{x\to\infty}(x)$

を示せばよいことがわかる.

2.4 $x\geq 1$ に対して

$\displaystyle \sum_{n\leq x}d(n)=x\log x+O(x)$

が成り立つ.

証明. $n/m\mapsto n$ と変数変換して二重和の変形を行うことにより

$\begin{align} \sum_{n\leq x}d(n)&=\sum_{n\leq x}\sum_{m\mid n}1=\sum_{mn\leq x}1\\ &=\sum_{m\leq x}\sum_{n\leq \frac{x}{m}}1=\sum_{m\leq x}\left(\frac{x}{m}+O(1)\right)\\ &=x\sum_{m\leq x}\frac{1}{m}+O(x) \end{align}$

を得る. [note]の命題5.4より

$\displaystyle \sum_{m\leq x}\frac{1}{m}=\log x+\gamma+O\left(\frac{1}{x}\right)$

が成り立つので, 代入すればよい. Q.E.D.

2.5 (Dirichlet.) $x\geq 1$ に対して

$\displaystyle \sum_{n\leq x}d(n)=x\log x+(2\gamma-1)x+O(\sqrt{x})$

が成り立つ.

証明. まず,

$\displaystyle \sum_{n\leq x}d(n)=\sum_{mn\leq x}1=2\sum_{\substack{mn\leq x \\ m=n}}1+\sum_{\substack{mn\leq x \\ m=n}}1$

と分割する.

$\displaystyle \sum_{\substack{mn\leq x \\ m=n}}1=\sum_{n\leq x}\sum_{n < m \leq \frac{x}{n}}1=\sum_{n\leq \sqrt{x}}\left(\left\lfloor\frac{x}{n}\right\rfloor-n\right)$

なので,

$\begin{align} \sum_{n\leq x}d(n)&=2\sum_{n\leq \sqrt{x}}\left(\frac{x}{n}-n+O(1)\right)+O(\sqrt{x})\\ &=2x\sum_{n\leq \sqrt{x}}\frac{1}{n}-2\sum_{n\leq \sqrt{x}}n+O(\sqrt{x}) \end{align}$

を得る. 1つ目の和には[note]の命題5.4を, 2つ目には普通の和の公式を適用することにより

$\begin{align} \sum_{n\leq x}d(n)&=2x\left(\log\sqrt{x}+\gamma+O\left(\frac{1}{\sqrt{x}}\right)\right)-2\left(\frac{x}{2}+O(\sqrt{x})\right)+O(\sqrt{x})\\ &=x\log x+(2\gamma-1)x+O(\sqrt{x}) \end{align}$

が示された. Q.E.D.

2.6 $x,a,b\geq 1$ , $x=ab$ とし, 関数 $f, g, F, G$ が

$\displaystyle F(x)=\sum_{n\leq x}f(n),\quad G(x)=\sum_{n\leq x}g(n)$

なる関係にあるとする. このとき,

$\displaystyle \sum_{mn\leq x}f(m)g(n)=\sum_{m\leq a}f(m)G\left(\frac{x}{m}\right)+\sum_{n\leq b}g(n)F\left(\frac{x}{n}\right)-F(a)G(b)$

が成り立つ. やはり, $m,n$ は $\mathbb{N}$ の元を動いている.

証明. これは左辺を計算するために

$\displaystyle \sum_{m\leq a}\sum_{n\leq \frac{x}{m}}f(m)g(n)=\sum_{m\leq a}f(m)G\left(\frac{x}{m}\right)$

および

$\displaystyle \sum_{n\leq b}\sum_{m\leq \frac{x}{n}}g(n)f(m)=\sum_{n\leq b}g(n)F\left(\frac{x}{n}\right)$

を足し合わせると

$\displaystyle \sum_{m\leq a}\sum_{n\leq b}f(m)g(n)=F(a)G(b)$

が重複して足されるという話である. Q.E.D.

2.7 $f(n)=d(n)-\log n-2\gamma$ , $g(n)=\mu(n)$ として, 2.6を適用することを考える. まず,

$\displaystyle F(x)=\sum_{n\leq x}f(n)=O(\sqrt{x})$

が確認できる. ただし, $\log x$ を経由するので例えば $x\geq 2$ としておく.

証明. 2.6および[note]の命題5.3より

$\begin{align} F(x)&=\sum_{n\leq x}d(n)-\sum_{\log n}-2\gamma\sum_{n\leq x}1\\ &=x\log x+(2\gamma-1)x+O(\sqrt{x})-(x\log x-x+O(\log x) )-2\gamma x+O(1)\\ &=O(\sqrt{x})+O(\log x)+O(1)=O(\sqrt{x}) \end{align}$

と計算できる. Q.E.D.

2.8 $ab=x$ を満たすような実数 $a \geq 2, b, x$ を考える. 2.7および[note]の命題5.5より

$\displaystyle \sum_{n\leq b}\mu(n)F\left(\frac{x}{n}\right)=O\left(\sum_{n\leq b}\sqrt{\frac{x}{n}}\right)=O(\sqrt{xb})=O\left(\frac{x}{\sqrt{a}}\right) \tag{3}$

が成り立つ. 以下, $\varepsilon > 0$ を任意にとり, $a$ を

$\displaystyle \left|\sum_{n\leq b}\mu(n)F\left(\frac{x}{n}\right)\right| < \varepsilon x\tag{4}$

が成り立つようにとる. $a$ は $\varepsilon$ のみに依存し, $x$ には依存しないことに注意.

$\varepsilon$ のみに依存する正の定数 $K=K(\varepsilon) > 0$ を

$\displaystyle K:=\sum_{n\leq a}\frac{|f(n)|}{n}$

で定める. また, Mertens関数を $M(x):=\sum_{n\leq x}\mu(n)$ で定め, 以下 $(2)$ を仮定することにより

$M(x)=o_{x\to\infty}(x)$

である. このとき, ある $x_0=x_0(\varepsilon)$ が存在して, $x\geq x_0$ ならば

$\displaystyle \frac{|M(x)|}{x} < \min\left\{1,\frac{\varepsilon}{K}\right\}$

が成り立つ. 以下, $x \geq ax_0$ を仮定する. すると $x/n\geq x_0$ なので,

$\displaystyle \left|\sum_{n \leq a}f(n)M\left(\frac{x}{n}\right)\right| < \sum_{n\leq a}|f(n)|\cdot \frac{\varepsilon}{K}\cdot\frac{x}{n}=\varepsilon x\tag{5}$

と評価できる.

最後に, $F(a)M(b)=O(\sqrt{a}b)$ であるが( $b\geq x_0$ に注意), このビッグ・オー係数は $(3)$ のものより小さいことから,

$\displaystyle \left|F(a)M(b)\right| < (\varepsilon\sqrt{a})\sqrt{a}b = \varepsilon x$

を得る. これと, 2.6, $(4)$ , $(5)$ を合わせることにより,

$\displaystyle \left|\sum_{mn\leq x}f(n)\mu(m)\right| < 3\varepsilon x$

なる評価に到達した.

$\varepsilon > 0$ は任意であったから, 2.3の観点から $(2)\Longrightarrow (1)$ の証明が完了となる.

2.9 $(2)\Longrightarrow (1)$ の証明は若干長く感じられるかもしれない. ただし, この部分は古典的であり, Richterの論文で新しい視点で議論されているのは $(2)$ の証明の部分のみであることに注意. また, [note]の言葉で考えると, Selbergによる素数定理の証明が「第三世代のビッグ・オー不等式」まで必要となるのに対して, $(2)\Longrightarrow (1)$ の証明は「第一世代のビッグ・オー不等式」しか用いないローテクなものである.

それではRichterの論文での議論に移ろう.

3.1 $B\subset\mathbb{N}$ を空でない有限集合とする. このとき, 不等式

$\displaystyle \limsup_{N\to\infty}\mathbb{E}_{n\in[N]}\left(\left|\mathbb{E}_{m\in B}^{\log}\bigl(1-m\mathbf{1}_{m\mid n}\bigr)\right|\right) \leq \sqrt{\mathbb{E}_{m\in B}^{\log}\mathbb{E}_{n\in B}^{\log}\bigl(\mathrm{gcd}(m,n)-1\bigr)}$

が成り立つ*1.

証明. Cauchy-Schwarzの不等式*2より

$\displaystyle \mathbb{E}_{n\in[N]}\left(\left|\mathbb{E}_{m\in B}^{\log}\bigl(1-m\mathbf{1}_{m\mid n}\bigr)\right|\right)^2\leq \mathbb{E}_{n\in[N]}\left(\left(\mathbb{E}_{m\in B}^{\log}\bigl(1-m\mathbf{1}_{m\mid n}\bigr)\right)^2\right)\tag{6}$

と評価できる. 2乗を展開すれば

$\displaystyle \mathbb{E}_{n\in[N]}\left(\left(\mathbb{E}_{m\in B}^{\log}\bigl(1-m\mathbf{1}_{m\mid n}\bigr)\right)^2\right)=S_1-2S_2+1,$

$\begin{align} S_1&=\mathbb{E}_{n\in[N]}\mathbb{E}_{m\in B}^{\log}\mathbb{E}_{l\in B}^{\log}\bigl(m\mathbf{1}_{m\mid n}\cdot l\mathbf{1}_{l\mid n}\bigr),\\ S_2&=\mathbb{E}_{n\in[N]}\mathbb{E}_{m\in B}^{\log}\bigl(m\mathbf{1}_{m\mid n}\bigr) \end{align}$

と分解することができる*3.

$\mathbb{E}_{n\in [N]}\bigl(m\mathbf{1}_{m\mid n}\bigr)=1+O(1/N)$ なので*4, 和の順序を入れ替えることにより

$\displaystyle S_1=1+O\left(\frac{1}{N}\right)$

がわかる*5.

同様に考えると, $\mathbb{E}_{n\in [N]}\bigl(m\mathbf{1}_{m\mid n}\cdot l\mathbf{1}{l \mid n}\bigr)=\mathrm{gcd}(m,l)\bigl(1+O(1/N)\bigr)$ なので*6, $B$ に依存する自然数 $g_B$ を

$\displaystyle g_B:=\max_{(m,l)\in B\times B}\mathrm{gcd}(m,l)$

とおけば

$\displaystyle S_2=1+\mathbb{E}_{m\in B}^{\log}\mathbb{E}_{l\in B}^{\log}\bigl(\mathrm{gcd}(m,l)-1\bigr)+O\left(\frac{g_B}{N}\right)$

を得る. 不等式 $(6)$ の両辺の平方根をとり, 右辺を $S_1$ , $S_2$ の得られた表示で整理し, 両辺の $\displaystyle \limsup_{N\to\infty}$ をとれば所望の不等式となる. Q.E.D.

次の命題が証明全体におけるキーであり, 良い性質を持つ2つの集合 $B_1, B_2$ の存在を主張する.

3.2 $0 < \eta < 1$ に対して, $\rho=\rho(\eta)\in (1,1+\eta]$ および $k_0=k_0(\eta)\in\mathbb{N}$ が存在し, 以下が成り立つ: 任意の整数 $k\geq k_0$ および任意の $l\in \mathbb{N}$ に対して空でない有限集合 $B_1=B_1(\eta,k,l)\subset\mathbb{N}$ , $B_2=B_2(\eta,k,l)\subset\mathbb{N}$ が存在して, 以下の性質が成り立つ:

(a) $B_1\subset \mathcal{P}\setminus [l],\quad B_2\subset \mathcal{P}_k\setminus [l]$ .
(b) 任意の $j\in \mathbb{N}\cup\{0\}$ に対して, $\#(B_1\cap (\rho^j, \rho^{j+1}]) = \#(B_2\cap (\rho^j, \rho^{j+1}])$ が成り立つ.
(c) $i=1,2$ に対して $\mathbb{E}_{m\in B_i}^{\log}\mathbb{E}_{n\in B_i}^{\log}\bigl(\mathrm{gcd}(m,n)-1\bigr) < \eta$ が成り立つ.

3.3 論文と同じく, 3.2が証明できたと仮定して $(2)$ が導かれることを先にみておく.

$\eta > 0$ を任意に取り, 3.2によって存在する $\rho\in (1,1+\eta]$ および $k_0\in\mathbb{N}$ をとる. 更に, $k_0$ 以上の偶数 $k$ および自然数 $l\in\mathbb{N}$ をとる. そうして, 3.2によって存在する集合 $B_1, B_2$ をとる. $B_1\cup B_2$ の最大限を $h_B$ と表す.

$i=1,2$ とする. $m\in B_i\cap[N]$ を固定し, $[\lfloor N/m\rfloor]=[N/m]$ と略記するとき,

$\begin{align} \mathbb{E}_{n\in[N/m]}\bigl(\mu(mn)\bigr)&=\frac{1}{\lfloor N/m\rfloor}\sum_{n\leq \frac{N}{m}}\mu(mn)=\left(1+O\left(\frac{h_B}{N}\right)\right)\frac{m}{N}\sum_{n\leq N}\mathbf{1}_{m\mid n}\mu(n)\\ &=\mathbb{E}_{n\in[N]}\bigl(m\mathbf{1}_{m\mid n}\mu(n)\bigr)+O\left(\frac{h_B}{N}\right) \end{align}$

なので,

$\begin{align} &\left|\mathbb{E}_{n\in [N]}\bigl(\mu(n)\bigr)-\mathbb{E}_{m\in B_i}^{\log}\mathbb{E}_{n\in[N/m]}\bigl(\mu(mn)\bigr)\right|\\ &=\left|\mathbb{E}_{n\in [N]}\bigl(\mu(n)\bigr)-\mathbb{E}_{m\in B_i}^{\log}\mathbb{E}_{n\in[N]}\bigl(m\mathbf{1}_{m\mid n}\mu(n)\bigr)\right|+O\left(\frac{h_B}{N}\right)\\ &\leq\mathbb{E}_{n\in[N]}\left(\left|\mathbb{E}_{m\in B_i}^{\log}\bigl(1-m\mathbf{1}_{m\mid n}\bigr)\right|\right)+O\left(\frac{h_B}{N}\right) \end{align}$

と評価できる. 両辺の $N$ に関する上極限をとって3.1および3.2の(c)を用いると

$\displaystyle \limsup_{N\to\infty}\left|\mathbb{E}_{n\in [N]}\bigl(\mu(n)\bigr)-\mathbb{E}_{m\in B_i}^{\log}\mathbb{E}_{n\in[N/m]}\bigl(\mu(mn)\bigr)\right|\leq \sqrt{\eta}$

を得る.

3.4 ここで少し上漸近密度を取り扱う. 集合 $A\subset\mathbb{N}$ の上漸近密度 $\overline{d}(A)$ は

$\displaystyle \overline{d}(A):=\limsup_{N\to\infty}\frac{\#(A\cap[N])}{N}$

と定義される. 一般に $\overline{d}(A\cup B)\leq \overline{d}(A)+\overline{d}(B)$ .

$m=p_1\cdots p_k$ を相異なる $k$ 個の $l$ 以上であるような素数の積とし, $\mathbb{N}_m$ を $m$ と互いに素な自然数全体のなす集合とし, $p_i\mathbb{N}$ を $p_i$ の倍数全体のなす集合とするとき,

$\displaystyle \frac{\lfloor N/p_i\rfloor}{N}=\frac{N/p_i+O(1)}{N}=\frac{1}{p_i}+O\left(\frac{1}{N}\right)\to\frac{1}{p_i}\leq \frac{1}{l}$

という計算から

$\displaystyle \overline{d}(\mathbb{N}\setminus\mathbb{N}_m)\leq \sum_{i=1}^k\overline{d}(p_i\mathbb{N})\leq \frac{k}{l}$

と評価できることがわかる.

3.5 ここで, 3.3の設定に戻る. $m\in B_i$ に対して, Möbius関数の乗法性*7から

$\begin{align} \mathbb{E}_{n\in[N/m]}\bigl(\mu(mn)\bigr)&=\frac{1}{\lfloor N/m\rfloor}\left(\sum_{\substack{n\leq N/m \\ n\in \mathbb{N}_m}}\mu(mn)+\sum_{\substack{n\leq N/m \\ n\not\in \mathbb{N}_m}}\mu(mn)\right)\\ &=\frac{1}{\lfloor N/m\rfloor}\left(\sum_{n\leq N/m}\mu(m)\mu(n)-\sum_{\substack{n\leq N/m \\ n\not\in \mathbb{N}_m}}\mu(m)\mu(n)+\sum_{\substack{n\leq N/m \\ n\not\in \mathbb{N}_m}}\mu(mn)\right) \end{align}$

と変形でき, 3.4を使うことにより

$\displaystyle \mathbb{E}_{n\in[N/m]}\bigl(\mu(mn)\bigr)=\mathbb{E}_{n\in[N/m]}\bigl(\mu(m)\mu(n)\bigr)+O_{N\to\infty}\left(\frac{k}{l}\right)$

が成り立つことがわかる( $i=1$ のときは, それで十分だからという理由で, $1/l\leq k/l$ と上から評価しておく).

3.6 さて, 3.2の(a)から $B_1$ の元は素数であり, $B_2$ の元は相異なる $k$ 個の素数の積である. 更に $k$ を偶数として選んでいることから, $m\in B_1$ のときは $\mu(m)=1$ , $m\in B_2$ のときは $\mu(m)=-1$ である. このことと, 3.3, 3.5の結論より

$\begin{align} \limsup_{N\to\infty}\left|\mathbb{E}_{n\in [N]}\bigl(\mu(n)\bigr)-\mathbb{E}_{m\in B_1}^{\log}\mathbb{E}_{n\in[N/m]}\bigl(\mu(n)\bigr)\right|\leq \sqrt{\eta}+O\left(\frac{k}{l}\right)\\ \limsup_{N\to\infty}\left|\mathbb{E}_{n\in [N]}\bigl(\mu(n)\bigr)+\mathbb{E}_{m\in B_2}^{\log}\mathbb{E}_{n\in[N/m]}\bigl(\mu(n)\bigr)\right|\leq \sqrt{\eta}+O\left(\frac{k}{l}\right) \end{align}$

が得られる.

3.7 実は3.2の(b)から

$\displaystyle \mathbb{E}_{m\in B_1}^{\log}\mathbb{E}_{n\in[N/m]}\bigl(\mu(n)\bigr)=\mathbb{E}_{m\in B_2}^{\log}\mathbb{E}_{n\in[N/m]}\bigl(\mu(n)\bigr)+O_{N\to\infty}(\eta)+o_{N\to\infty}(1)$

が成り立つことを証明できる(初見で「そんなこと証明できるはずがない」と思ってしまったのは内緒). まず, $(\rho^j,\rho^{j+1}]$ 毎に区切って三角不等式を用いることにより

$\begin{align} &\left|\mathbb{E}_{m\in B_1}^{\log}\mathbb{E}_{n\in[N/m]}\bigl(\mu(n)\bigr)-\mathbb{E}_{m\in B_2}^{\log}\mathbb{E}_{n\in[N/m]}\bigl(\mu(n)\bigr)\right|\\ &=\left|\sum_{j=0}^{\infty}\left(\mathbb{E}_{m\in B_1}^{\log}\bigl(\mathbf{1}_{(\rho^j,\rho^{j+1}]}(m)\mathbb{E}_{n\in[N/m]}\bigl(\mu(n)\bigr)\bigr)-\mathbb{E}_{m\in B_2}^{\log}\bigl(\mathbf{1}_{(\rho^j,\rho^{j+1}]}(m)\mathbb{E}_{n\in[N/m]}\bigl(\mu(n)\bigr)\bigr)\right)\right|\\ &\leq\sum_{j=0}^{\infty}\left|\mathbb{E}_{m\in B_1}^{\log}\bigl(\mathbf{1}_{(\rho^j,\rho^{j+1}]}(m)\mathbb{E}_{n\in[N/m]}\bigl(\mu(n)\bigr)\bigr)-\mathbb{E}_{m\in B_2}^{\log}\bigl(\mathbf{1}_{(\rho^j,\rho^{j+1}]}(m)\mathbb{E}_{n\in[N/m]}\bigl(\mu(n)\bigr)\bigr)\right| \end{align}$

と評価できる. 和の中身を評価していこう. $B_1, B_2$ は有限集合なので, $j$ は有限の範囲を考えれば十分であり, 以下の評価では実際にそう仮定する.

3.8 $m\in B_i$ , $m\in(\rho^j,\rho^{j+1}]$ とする( $i=1,2$ ). このとき,

$\displaystyle \mathbb{E}_{n\in[N/m]}\bigl(\mu(n)\bigr)=\mathbb{E}_{n\in[N/\rho^j]}\bigl(\mu(n)\bigr)+O_{N\to\infty}(\eta)+o_{N\to\infty}(1)$

が成り立つ.

証明. $N/\rho^{j+1}\leq N/m < N/\rho^j$ に注意する.

$\displaystyle \frac{1}{\lfloor N/m\rfloor}=\frac{\rho^{j+1}}{N}\left(1+O_{N\to\infty}(\eta)\right),\quad \frac{1}{\lfloor N/\rho^j\rfloor}=\frac{\rho^{j+1}}{N}\left(1+O_{N\to\infty}(\eta)\right)$

が成り立っている*8.

$\displaystyle \left|\frac{\rho^{j+1}}{N}\sum_{\frac{N}{m} < n\leq \frac{N}{\rho^j}}\mu(n)\right|\leq \frac{\rho^{j+1}}{N}\left(\frac{N(\rho-1)}{\rho^{j+1}}+1\right)\leq \eta+o_{N\to\infty}(1)$

と評価できることから,

$\displaystyle \frac{\rho^{j+1}}{N}\cdot O_{N\to\infty}(\eta)\left(\left|\sum_{n\leq N/m}\mu(n)\right|+\left|\sum_{n\leq \frac{N}{\rho^j}}\mu(n)\right|\right)=O_{N\to\infty}(\eta)$

と合わせて所望の評価を得る. Q.E.D.

3.9 $\#(B_i\cap (\rho^j,\rho^{j+1}])=t_j$ とおく. 3.2の(b)より $t_j$ これは $i=1,2$ によらず, $j > J$ では $t_j=0$ の状態にあるとする.

$\displaystyle E_j:=\frac{t/\rho^j}{\sum_{j=1}^Jt_j/\rho^j}$

とおけば, $1\not\in B_1, B_2$ に注意して,

$\displaystyle \frac{1}{\rho}E_j\leq \mathbb{E}_{m\in B_i}^{\log}\bigl(\mathbf{1}_{(\rho^j,\rho^{j+1}]}(m)\bigr) \leq \rho E_j$

と評価することができる. 従って,

$\displaystyle \frac{1}{\rho^2}\mathbb{E}_{m\in B_2}^{\log}\bigl(\mathbf{1}_{(\rho^j,\rho^{j+1}]}(m)\bigr) \leq \mathbb{E}_{m\in B_1}^{\log}\bigl(\mathbf{1}_{(\rho^j,\rho^{j+1}]}(m)\bigr) \leq \rho^2\mathbb{E}_{m\in B_1}^{\log}\bigl(\mathbf{1}_{(\rho^j,\rho^{j+1}]}(m)\bigr)$

とはさむことができ,

$\displaystyle \frac{\mathbb{E}_{m\in B_1}^{\log}\bigl(\mathbf{1}_{(\rho^j,\rho^{j+1}]}(m)\bigr)}{\mathbb{E}_{m\in B_2}^{\log}\bigl(\mathbf{1}_{(\rho^j,\rho^{j+1}]}(m)\bigr)}=1+O(\eta)$

がわかる*9.

3.10 上の2つの評価3.8, 3.9を用いると

$\begin{align} &\mathbb{E}_{m\in B_1}^{\log}\bigl(\mathbf{1}_{(\rho^j,\rho^{j+1}]}(m)\mathbb{E}_{n\in[N/m]}\bigl(\mu(n)\bigr)\bigr)-\mathbb{E}_{m\in B_2}^{\log}\bigl(\mathbf{1}_{(\rho^j,\rho^{j+1}]}(m)\mathbb{E}_{n\in[N/m]}\bigl(\mu(n)\bigr)\bigr)\\ &=\mathbb{E}_{n\in N/\rho^j}\bigl(\mu(n)\bigr)\left(\mathbb{E}_{m\in B_1}^{\log}\bigl(\mathbf{1}_{(\rho^j,\rho^{j+1}]}(m)\bigr)-\mathbb{E}_{m\in B_2}^{\log}\bigl(\mathbf{1}_{(\rho^j,\rho^{j+1}]}(m)\bigr)\right)\\ &\quad +\left(O_{N\to\infty}(\eta)+o_{N\to\infty}(1)\right)\mathbb{E}_{m\in B_1}^{\log}\bigl(\mathbf{1}_{(\rho^j,\rho^{j+1}]}(m)\bigr)\\ &=\left(O_{N\to\infty}(\eta)+o_{N\to\infty}(1)\right)\mathbb{E}_{m\in B_1}^{\log}\bigl(\mathbf{1}_{(\rho^j,\rho^{j+1}]}(m)\bigr) \end{align}$

を得る. $\mathbb{E}_{m\in B_1}^{\log}\bigl(\mathbf{1}_{(\rho^j,\rho^{j+1}]}(m)\bigr)$ が非負である事に注意すれば

$\begin{align} &\sum_{j=0}^{\infty}\left|\mathbb{E}_{m\in B_1}^{\log}\bigl(\mathbf{1}_{(\rho^j,\rho^{j+1}]}(m)\mathbb{E}_{n\in[N/m]}\bigl(\mu(n)\bigr)\bigr)-\mathbb{E}_{m\in B_2}^{\log}\bigl(\mathbf{1}_{(\rho^j,\rho^{j+1}]}(m)\mathbb{E}_{n\in[N/m]}\bigl(\mu(n)\bigr)\bigr)\right|\\ &\leq \left(O_{N\to\infty}(\eta)+o_{N\to\infty}(1)\right)\sum_{j=1}^{\infty}\mathbb{E}_{m\in B_1}^{\log}\bigl(\mathbf{1}_{(\rho^j,\rho^{j+1}]}(m)\bigr) \end{align}$

と評価することができ,

$\displaystyle \sum_{j=1}^{\infty}\mathbb{E}_{m\in B_1}^{\log}\bigl(\mathbf{1}_{(\rho^j,\rho^{j+1}]}(m)\bigr)=\mathbb{E}_{m\in B_1}^{\log}\bigl(\mathbf{1}_{B_1}\bigr)=1$

である事から3.7は真実である.

3.11 今示された3.7を用いることにより,

$\begin{align} 2\mathbb{E}_{n\in[N]}\bigl(\mu(n)\bigr)&= \mathbb{E}_{n\in [N]}\bigl(\mu(n)\bigr)-\mathbb{E}_{m\in B_1}^{\log}\mathbb{E}_{n\in[N/m]}\bigl(\mu(n)\bigr)\\ &\quad +\mathbb{E}_{n\in [N]}\bigl(\mu(n)\bigr)+\mathbb{E}_{m\in B_1}^{\log}\mathbb{E}_{n\in[N/m]}\bigl(\mu(n)\bigr)\\ &=\mathbb{E}_{n\in [N]}\bigl(\mu(n)\bigr)-\mathbb{E}_{m\in B_1}^{\log}\mathbb{E}_{n\in[N/m]}\bigl(\mu(n)\bigr)\\ &\quad +\mathbb{E}_{n\in [N]}\bigl(\mu(n)\bigr)+\mathbb{E}_{m\in B_2}^{\log}\mathbb{E}_{n\in[N/m]}\bigl(\mu(n)\bigr)\\ &\quad +O_{N\to\infty}(\eta)+o_{N\to\infty}(1) \end{align}$

と変形することができる. これに三角不等式を適用してから上極限 $\displaystyle\limsup_{N\to\infty}$ をとり, 3.6を用いることにより

$\displaystyle \limsup_{N\to\infty}\left|\mathbb{E}_{n\in[N]}\bigl(\mu(n)\bigr)\right|\leq O(\eta)+O\left(\frac{k}{l}\right)$

を得る. 任意に $\varepsilon > 0$ をとり, $O(\eta) < \varepsilon/2$ が成り立つように $\eta$ をとる. $\eta$ に依存して $k$ をとったあとに, $O(k/l) < \varepsilon/2$ が成り立つだけ大きな $l$ をとる. このようにすれば

$\displaystyle \limsup_{N\to\infty}\left|\mathbb{E}_{n\in[N]}\bigl(\mu(n)\bigr)\right|\leq \varepsilon$

が得られるので,

$\displaystyle \lim_{N\to\infty}\mathbb{E}_{n\in[N]}\bigl(\mu(n)\bigr)=0$

が従う. これは $(2)$ であり, 2節の議論から素数定理 $(1)$ が証明されたことになる.

後は3.2の $B_1$ , $B_2$ の存在性を示せばよい. そのために, Chebyshev型定理の評価を用いる. 古典的な結果であるが証明しておこう. まずは下からの評価を与える.

4.1 $x$ は $e$ 以上の実数とする. このとき,

$\displaystyle \pi(x) \geq (\log 2)\cdot \frac{x}{\log x}+O(1)$

が成り立つ.

証明. $x$ が偶数 $x=2n$ である場合に証明すれば十分である*10. Legendreの公式より

$\displaystyle \mathrm{ord}_p\binom{2n}{n}=\sum_{i=1}^{\lfloor\log_p(2n)\rfloor}\left(\left\lfloor\frac{2n}{p^i}\right\rfloor-2\left\lfloor\frac{n}{p^i}\right\rfloor\right)\leq\log_p(2n)$

である*11. よって

$\displaystyle \binom{2n}{n}=\prod_{p\in\mathcal{P}\cap[2n]}p^{\mathrm{ord}_p\binom{2n}{n}}\leq (2n)^{\#(\mathcal{P}\cap [2n]})$

と評価でき, 自然対数をとると

$\displaystyle \log\binom{2n}{n}\leq \#(\mathcal{P}\cap[2n])\log 2n \tag{7}$

を得る. [note]の命題5.3より

$\log(n!)=n\log n-n+O(\log n)$

なので,

$\displaystyle \log \binom{2n}{n}=(2\log 2)n+O(\log n)\tag{8}$

を得る. $(7)$ と $(8)$ を合わせれば証明が完了する. Q.E.D.

上からの評価には次の補題を用いる.

4.2 $x\geq e$ , $1 < \sigma \leq 16$ とする*12. このとき,

$\displaystyle \#(\mathcal{P}\cap (x,\sigma x])\leq \frac{\beta(\sigma)x}{\log x}+O\left(\frac{x}{\log^2x}\right)$

が成り立つ. ここで, $\beta(\sigma):=\sigma \log \sigma-(\sigma-1)\log (\sigma-1)$ とおいている.

証明. $\binom{\sigma x}{x}$ は $\binom{\lfloor \sigma x\rfloor}{\lfloor x\rfloor}$ を意味するものとする. $\mathcal{P}\cap (x,\sigma x]$ の元は $\binom{\sigma x}{x}$ を割り切るので,

$\displaystyle \binom{\sigma x}{x}\geq \prod_{p\in\mathcal{P}\cap (x,\sigma x]}p\geq x^{\#(\mathcal{P}\cap (x,\sigma x])}$

と評価でき, 自然対数をとると

$\displaystyle \log\binom{\sigma x}{x}\geq \#(\mathcal{P}\cap (x,\sigma x])\log x\tag{9}$

を得る. [note]の命題5.3より

$\begin{align} \log\binom{\sigma x}{x} &= \log\frac{\lfloor \sigma x\rfloor!}{\lfloor x\rfloor!(\lfloor \sigma x\rfloor-\lfloor x\rfloor)!}\\ &=\lfloor \sigma x\rfloor \log \lfloor \sigma x\rfloor -\lfloor \sigma x\rfloor+O(\log\lfloor \sigma x\rfloor)\\ &\quad -\bigl(\lfloor x\rfloor\log\lfloor x\rfloor-\lfloor x\rfloor + O(\log\lfloor x\rfloor)\bigr)\\ &\quad -\bigl( (\lfloor \sigma x\rfloor-\lfloor x\rfloor)\log(\lfloor \sigma x\rfloor - \lfloor x\rfloor)-(\lfloor \sigma x\rfloor - \lfloor x\rfloor) + O(\log(\lfloor \sigma x\rfloor - \lfloor x\rfloor) )\\ &=\lfloor \sigma x\rfloor \log \lfloor \sigma x\rfloor-\lfloor x\rfloor\log\lfloor x\rfloor-(\lfloor \sigma x\rfloor-\lfloor x\rfloor)\log(\lfloor \sigma x\rfloor - \lfloor x\rfloor)+O(\log x)\\ &=\sigma x \log (\sigma x)-x\log x-(\sigma-1)x\log( (\sigma-1)x)+O\left(\frac{x}{\log x}\right)\\ &=\sigma x\log \sigma-(\sigma-1)x\log (\sigma-1)+O\left(\frac{x}{\log x}\right)\\ &=(\sigma\log \sigma-(\sigma-1)\log(\sigma-1) )x+O\left(\frac{x}{\log x}\right) \end{align}$

と計算できる*13. $(9)$ と合わせて両辺を $\log x$ で割ればよい. Q.E.D.

Richterの証明において必要となる数論的情報は, Chebyshev型定理として証明した上記2つの補題から示される, 短区間における素数の個数に関する次の命題に集約される*14.

4.3 実数 $x_0\geq 1$ , $\varepsilon_0 > 0$ が存在して, 以下が成立する:

$\begin{align} \#(\mathcal{P}\cap (8^x,8^{x+1}]) &\geq \frac{8^x}{x}\qquad \quad (x\geq x_0),\\ \#(\mathcal{P}\cap (8^x, 8^{x+\varepsilon}])&\leq \frac{\sqrt{\varepsilon}8^x}{x}\qquad (\varepsilon \in (0,\varepsilon_0], x\geq x_1(\varepsilon) ). \end{align}$

ただし, $x_1(\varepsilon) \geq 1$ は $\varepsilon$ に依存して存在する実数.

証明. 4.2において $\sigma=8^{\varepsilon}$ とおくことにより、

$\displaystyle \#(\mathcal{P}\cap (8^x, 8^{x+\varepsilon}])\leq \frac{\beta(8^{\varepsilon})}{\log 8}\cdot\frac{8^x}{x}+O\left(\frac{8^x}{x^2}\right)$

が成り立つ。 $\varepsilon$ が例えば $0.16$ 以下であれば $\frac{\beta(8^{\varepsilon})}{\log 8} < \sqrt{\varepsilon}$ が成り立つので、 $x$ が十分大きければ

$\displaystyle \#(\mathcal{P}\cap (8^x, 8^{x+\varepsilon}])\leq \frac{\sqrt{\varepsilon}8^x}{x}$

が成り立つことがわかる。
1つ目の不等式の証明について, 4.2を用いたRichterの議論は細かい点が個人的に気になるが, ここでは代わりに4.1の逆向きの不等式として以下の4.4を用いることにする*15. 4.1と4.4を組み合わせると,

$\displaystyle \#(\mathcal{P}\cap (8^x,8^{x+1}])\geq \frac{8^{x+1}}{3(x+1)}-\frac{2\cdot 8^x}{3\log 2\cdot x}+O(1)$

と評価できる. 例えば $1/(x+1) > 3/(4x)$ と評価すれば, これは $8^x/x$ で下から押さえることができる. Q.E.D.

4.4 $x$ は $e$ 以上の実数とする. このとき,

$\displaystyle \pi(x) \leq 2\cdot \frac{x}{\log x}$

が成り立つ.

証明. 4.1のときと同様に考えて, $x$ が $3$ 以上の整数 $n$ のときに成立することを証明すればよく, $n$ が小さいときは直接成立を確認できるので, $n > 105$ と仮定してよい. このときに, $3$ 以上 $n$ 未満の整数では成立すると仮定して数学的帰納法で証明する. その際, $n$ は奇数であると仮定してよく, $n=2k+1$ とおく. まず,

$\displaystyle \binom{2k+1}{k}\geq \prod_{k+2\leq p\leq 2k+1}p\geq (k+2)^{\pi(2k+1)-\pi(k+1)}$

と評価でき, 一方

$\displaystyle \binom{2k+1}{k}=\frac{1}{2}\left\{\binom{2k+1}{k}+\binom{2k+1}{k+1}\right\}\leq \frac{1}{2}\sum_{j=0}^{2k+1}\binom{2k+1}{j}=2^{2k}$

と評価できるので, 合わせると

$\displaystyle (k+2)^{\pi(2k+1)-\pi(k+1)}\leq 2^{2k}$

を得る. 対数を取れば

$\displaystyle \pi(2k+1)-\pi(k+1)\leq \frac{2k\log 2}{\log (k+2)}$

となるが, 帰納法の仮定および条件 $n > 105$ を用いることにより

$\displaystyle \pi(n)=\pi(2k+1)\leq \frac{2k\log 2}{\log (k+2)}+\frac{2(k+1)}{\log (k+1)} < \frac{(\log 2+1)n+1}{\log \left(\frac{n}{2}\right)} < \frac{2n}{\log n}$

を得る. Q.E.D.

4.5 ある $\varepsilon_0 \in (0,1)$ が存在して以下が成立する: 任意の $\varepsilon \in (0,\varepsilon_0]$ と任意の $\delta \in (0,1)$ をとるとき、 $\varepsilon$ のみに依存する $x_0=x_0(\varepsilon) > 0$ と $\varepsilon, \delta$ のみに依存する $D=D(\varepsilon, \delta)\in (0,1)$ が存在して以下が成立する: $x_0$ 以上の整数 $n$ に対して、ある $x,y\in [n,n+1)$ が存在し、 $\varepsilon^4 < y-x < \varepsilon$ かつ

$\displaystyle \#(\mathcal{P}\cap(8^x,8^{x+\delta}])\geq D\cdot\frac{8^x}{x},\qquad \#(\mathcal{P}\cap(8^y,8^{y+\delta}])\geq D\cdot\frac{8^y}{y}$

が成り立つ。

証明. $x_0$ が4.3のもの以上とするとき、4.3の一つ目の不等式から区間 $(8^n,8^{n+1}]$ 内に少なくとも $8^n/n$ 個の素数が存在することがわかる。 $K_0:=\lceil \varepsilon^{-1}\rceil$ とおくとき、分割による被覆

$\displaystyle (8^n, 8^{n+1}]\subset (8^n, 8^{n+\varepsilon}]\cup(8^{n+\varepsilon},8^{n+2\varepsilon}]\cup\cdots\cup(8^{n+(K_0-1)\varepsilon},8^{n+K_0\varepsilon}]$

があるので、鳩の巣原理により或る $t\in [n,n+1)$ が存在して区間 $(8^t,8^{t+\varepsilon}]$ に少なくとも

$\displaystyle \frac{\varepsilon 8^n}{2n}$

個の素数が存在することがわかる。実際、上の $K_0$ 個の区間の全てがそれぞれ $\varepsilon 8^n/2n$ 個未満の素数しか含まなければ、区間 $(8^n, 8^{n+1}]$ の含む素数の個数が高々

$\displaystyle K_0\times\frac{\varepsilon 8^n}{2n}\leq \left(\frac{1}{\varepsilon}+1\right)\cdot\frac{\varepsilon 8^n}{2n} < \frac{\varepsilon 8^n}{2}$

で矛盾する。次に、 $K_1:=\lceil\varepsilon^{-3}\rceil$ とおく。分割による被覆

$\displaystyle (8^t,8^{t+\varepsilon}]\subset (8^t,8^{t+\varepsilon^4}]\cup(8^{t+\varepsilon^4},8^{t+2\varepsilon^4}]\cup\cdots\cup(8^{t+(K_1-1)\varepsilon^4},8^{t+K_1\varepsilon^4}]$

を考える。このとき、各 $1\leq j\leq K_1-1$ に対して小区間 $(8^{t+j\varepsilon^4},8^{t+(j+1)\varepsilon^4}]$ は高々

$\displaystyle \frac{64\varepsilon^28^n}{n}$

個の素数しか含まない。実際、 $\varepsilon_0$ を4.3の $\varepsilon_0$ の4乗根以下とし、 $x_0$ を4.3の $x_1(\varepsilon^4)$ 以上とすると、4.3の2つ目の不等式より

$\displaystyle \#(\mathcal{P}\cap(8^{t+j\varepsilon^4},8^{t+(j+1)\varepsilon^4}])\leq \frac{\varepsilon^28^{t+j\varepsilon^4}}{t+j\varepsilon^4}$

が成り立つ。あとは $n\leq t+j\varepsilon^4\leq t+\varepsilon\leq n+2$ に注意すればよい。

このことから、 $\varepsilon_0$ が十分小さければ、ある連続しない2つの整数 $a,b\in \{0,1,\dots,K_1-1\}$ が存在して( $a < b$ とする)、

$\begin{align} &\#(\mathcal{P}\cap(8^{t+a\varepsilon^4},8^{t+(a+1)\varepsilon^4}])\geq \frac{\varepsilon^48^n}{4n},\\ &\#(\mathcal{P}\cap(8^{t+b\varepsilon^4},8^{t+(b+1)\varepsilon^4}])\geq \frac{\varepsilon^48^n}{4n} \end{align}$

が成り立つことがわかる。実際、今考えている $K_1$ 個の小区間のうち、少なくも3つの区間が素数を少なくとも $\varepsilon^48^n/(4n)$ 個含むことを示せばよい。背理法で証明するために、 $K_1-2$ 個の小区間が素数をそれぞれ $\varepsilon^48^n/(4n)$ 個未満しか含まなかったと仮定する。残り2個の区間に含まれる素数の総計は先ほど示したことから高々

$\displaystyle \frac{128\varepsilon^28^n}{n}$

個しか含まないので、 $\varepsilon_0$ が(従って $\varepsilon$ が)十分小さければ

$\displaystyle \#(\mathcal{P}\cap (8^t,8^{t+\varepsilon}])\leq (K_1-2)\frac{\varepsilon^48^n}{4n}+\frac{128\varepsilon^28^n}{n} < \frac{\varepsilon8^n}{2n}$

なる評価に到達して、 $t$ の取り方に矛盾する。

さて、任意の $\delta\in (0,1)$ に対して

$\displaystyle x\in [t+a\varepsilon^4,t+(a+1)\varepsilon^4),\quad y\in [t+b\varepsilon^4,t+(b+1)\varepsilon^4)$

であって

$\begin{align} &\#(\mathcal{P}\cap (8^x,8^{x+\delta}])\geq \frac{\delta\varepsilon^48^n}{8n},\\ &\#(\mathcal{P}\cap (8^y,8^{y+\delta}])\geq \frac{\delta\varepsilon^48^n}{8n}\end{align}$

が成り立つようなものが存在する。これは $K_2:=\lceil\delta^{-1}\rceil$ とおいて分割による被覆

$\displaystyle (8^{t+a\varepsilon^4},8^{t+(a+1)\varepsilon^4}]\subset (8^{t+a\varepsilon^4},8^{t+a\varepsilon^4+\delta}]\cup\cdots\cup(8^{t+a\varepsilon^4+(K_2-1)\delta},8^{t+a\varepsilon^4+K_2\delta}]$

を考えて鳩の巣原理を適用すればよい( $b$ についても同様)。このとき、 $a,b$ が隣合わないことから $y-x > \varepsilon^4$ が成り立っており、 $x,y\in [t,t+\varepsilon)$ なので $y-x < \varepsilon$ である。すなわち、 $n < x, y < n+2$ に注意して、 $D(\varepsilon, \delta)=\varepsilon^4\delta/8^3$ ととれる。 Q.E.D.

4.6 ある $\varepsilon_0 \in (0,1)$ が存在して以下が成立する: 任意の $\varepsilon \in (0,\varepsilon_0]$ に対して $x_0=x_0(\varepsilon) > 0$ が存在して以下が成立する: 任意に整数 $k\geq \lceil 3\varepsilon^{-4}\rceil$ をとり、 $\delta:=\varepsilon/k$ として $D=D(\varepsilon,\delta)$ を4.5のものとする。 $x_0(\varepsilon)$ 以上の $k$ 個の整数 $n_1,\dots,n_k$ および実数 $x\geq x_0(\varepsilon)$ であって $n_1+\cdots+n_k=\lfloor x\rfloor$ を満たすようなものを任意にとる。このとき、実数 $x_1,\dots, x_k$ であって、

$\begin{align} \bullet \ &\#(\mathcal{P}\cap(8^{x_i},8^{x_i+\delta}]\geq D\cdot\frac{8^{x_i}}{x_i} \quad (1\leq i \leq k),\\ \bullet \ &|x_i-n_i|\leq 1 \quad (1\leq i \leq k), \\ \bullet \ &x_1+\cdots + x_k \in [x, x+\varepsilon) \end{align}$

を満たすようのものが存在する。

証明. $\varepsilon_0$ は4.5と同じもの、 $x_0(\varepsilon)$ は4.5のもの $+1$ とする。4.5より、各 $i\in [k]$ に対して $x_{i,1},y_{i,1}\in[n_i-1,n_i)$ , $x_{i,2}, y_{i,2}\in [n_i, n_i+1)$ であって

$\varepsilon^4 < y_{i,j}-x_{i,j} < \varepsilon$

および

$\displaystyle \#(\mathcal{P}\cap (8^{x_{i,j}},8^{x_{i,j}+\delta}])\geq D\cdot \frac{8^{x_{i,j}}}{x_{i,j}}$

が $j=1,2$ に対して成り立つようなものが存在する。よって、 $x_i \in \{x_{i,1},y_{i,1},x_{i,2},y_{i,2}\}$ であるように $x_i$ を選べば所望の性質のうち最初の二つは満たされる。

まずは $x_1:=x_{1,1}$ および

$\displaystyle x_{i+1}:=\begin{cases} x_{i+1,2} & (x_1+\cdots +x_i \leq n_1+\cdots +n_i-1) \\ x_{i+1,1} & (x_1+\cdots +x_i > n_1+\cdots +n_i-1)\end{cases}$

によって $x_1,\dots, x_k$ を定める。すると、帰納法によって

$n_1+n_2+\cdots + n_i-2 \leq x_1+\cdots +x_i < n_1+\cdots +n_i$

が満たされる。特に、

$\lfloor x\rfloor -2 \leq x_1+\cdots +x_k < \lfloor x\rfloor$

が成り立つ。その後、 $x_1$ から順次必要に応じて $x_i$ の値 $x_{i,j}$ を $y_{i,j}$ に取り替えていく。一回取り替える毎に $x_1+\cdots +x_k$ の増える量は $\varepsilon$ 未満なので、 $x$ 未満の値から一回取り替えていきなり $x+\varepsilon$ 以上になることはない。一方、 $x_1+\cdots +x_k$ の増える量は $\varepsilon^4$ 以上なので $k$ 回取り替えを行うと $3$ は増加して必ず $x$ を超えることになる。つまり、どこかのタイミングで $x_1+\cdots +x_k$ が $[x,x+\varepsilon)$ に入る。 Q.E.D.

以上の準備のもとに3.2を証明する。

4.7 (パラメーターの選択)
$\eta \in (0,1)$ を任意に選ぶ。
$K=K(\eta) > 0$ を $8^{1/K} < 1+\eta$ を満たすようにとる。
$\rho:=8^{1/K}$ とおく。
$\varepsilon_0$ は4.6のものとする。
$\varepsilon:=\min\{\varepsilon_0,1/(2K)\}$ とする。
$x_0$ を4.6の $x_0(\varepsilon)$ 以上の $\eta$ のみに依存する十分大きい数とする。
$k_0:=\lceil 3\varepsilon^{-4}\rceil$ とする。

整数 $k\geq k_0$ および $l \geq 1$ を任意にとる。
Chebyshev型の不等式である4.3の1つ目の不等式と4.4から、絶対定数 $C\geq 1$ があって

$\displaystyle \frac{8^n}{n}\leq \#(\mathcal{P}\cap (8^{n-1},8^{n+2}])\leq C\cdot \frac{8^n}{n} \quad (n\geq x_0)$

が成り立つ。

$\delta:=\varepsilon/k$ とおき、 $D=D(\varepsilon,\delta)$ を4.6のものとし、整数 $N$ を

$\displaystyle N\geq \left(\frac{ECK}{D}\right)^{2k}\cdot \frac{1}{\eta}$

を満たすようにとる( $E$ は絶対定数)。最後に整数 $s_1$ を

$s_1 =\max\left\{x_0,\frac{\log l}{\log 8}+1\right\}$

と選んでおく。

4.8 ( $A_1,\dots, A_k$ の構成)
有限集合 $A_1\subset s_1\mathbb{N}$ ( $s_1$ の倍数からなる)を

$\displaystyle \sum_{n\in A_1}\frac{1}{n}\geq N$

を満たすように選ぶ(調和級数が発散することから選べる)。以下、帰納的に $A_i$ まで決まっているときに、 $s_{i+1}$ を集合 $A_1+\cdots + A_i$ の最大元 $+1$ と定める。そうして、有限集合 $A_{i+1}\subset s_{i+1}\mathbb{N}$ を

$\displaystyle \sum_{n\in A_{i+1}}\frac{1}{n}\geq N$

を満たすように選ぶ。こうして、 $A_1, \dots, A_k$ を定義する。

このとき、 $A_1+\cdots + A_k$ の元は一意的な表示を持つ。∵ $A_1+\cdots +A_i$ でそうであると仮定して、 $A_1+\cdots +A_i+A_{i+1}$ もそうだということを示せばよい。 $n_1+\cdots +n_{i+1}=n_1'+\cdots +n_{i+1}'$ と2通りの表示があったとすると

$n_{i+1}-n_{i+1}'=(n_1'+\cdots +n_i')-(n_1+\cdots +n_i)$

が成り立つが、右辺は $-s_{i+1}$ より真に大きく $s_{i+1}$ 未満であり、左辺は $s_{i+1}$ の倍数である。このことから $n_{i+1}=n_{i+1}'$ であり、残りは帰納法の仮定から $n_1=n_1',\dots, n_i=n_i'$ が従う。こうして一意的な表示を持つことが示された。

$n\in A_1+\cdots +A_k$ をとる。4.3の1つ目の不等式から $\#(\mathcal{P}\cap (8^{n-1},8^{n+2}])\geq 8^n/n$ であり、

$\displaystyle (8^n,8^{n+1}]=(\rho^{Kn},\rho^{Kn+1}]\cup\cdots\cup(\rho^{Kn+K-1},\rho^{Kn+K}]$

から、鳩の巣原理により或る $i_n\in\{Kn,\dots, Kn+K-1\}$ が存在して小区間 $(\rho^{i_n},\rho^{i_n+1}]\subset (8^n,8^{n+1}]$ は少なくとも $8^n/(Kn)$ 個の素数を含む。

$\displaystyle \left\lfloor \frac{i_n}{K}\right\rfloor = n = n_1+\cdots +n_k$

と一意的に表示できるが( $n_1\in A_1, \dots, n_k\in A_k$ )、4.6において $x=i_n/K$ としたときの $x_1,\dots, x_k$ をとる。これらは $n$ に依存することに注意(本当は $n$ を明示すべきだが記号がうるさくなるので省略する)。 $x_{i+1}\geq n_{i+1}-1 > n_i+1 \geq x_i$ である。

4.9 ( $B_{n,2}$ の構成)
各 $i\in [k]$ について、4.6の1つ目の式から、 $\mathcal{P}\cap(8^{x_i},8^{x_i+\delta}]$ の部分集合 $P_{n_i}$ であって、

$\displaystyle \#P_{n_i}=\left\lfloor\frac{D8^{x_i}}{Kx_i}\right\rfloor$

が成り立つようなものをとることができる。 $P_{n_i}$ 達はどの2つをとっても互いに素な集合*16である。このとき、

$\displaystyle B_{n,2}:=P_{n_1}\cdot \cdots \cdot P_{n_k}$

とおく。4.6の3つ目の式と $k\delta=\varepsilon$ , $2\varepsilon \leq 1/K$ であることから

$B_{n,2}\subset (8^{x_1+\cdots +x_k},8^{x_1+\cdots +x_k+k\delta}]\subset (8^{i_n/K}, 8^{i_n/K+2\varepsilon}]\subset (\rho^{i_n},\rho^{i_n+1}]$

が成り立つ。

4.10 ( $B_{n,1}$ の構成)
$B_{n,1}\subset \mathcal{P}\cap (\rho^{i_n}, \rho^{i_n+1}]$ を $\#B_{n,1}=\#B_{n,2}$ が成り立つように選ぶ。選べる理由であるが、

$\displaystyle \#B_{n,2}\leq \prod_{i=1}^k\frac{D8^{x_i}}{Kx_i} < \frac{8^n}{Kn}$

と評価できることと $i_n$ の取り方からわかる。最後の不等号は $x_1+\cdots +x_k < i_n/K+\varepsilon < n+1$ , $8D < 1$ ,

$x_1\cdots x_k \geq (n_1-1)\cdots (n_k-1) \geq n_1+\cdots +n_k=n$

などから余裕で評価できる。

4.11 (Richterの集合の構成)
集合 $B_1, B_2$ を

$\displaystyle B_1:=\bigcup_{n\in A_1+\cdots +A_k}B_{n,1},\quad B_2:=\bigcup_{n\in A_1+\cdots +A_k}B_{n,2}$

と定める。 $B_{n,1}\subset (8^n, 8^{n+1}]$ であり、 $P_{n_i}\subset (8^{x_i},8^{x_i+\delta}]$ であるが、 $8^{x_i}\geq 8^{x_1}\geq 8^{n_1-1}\geq 8^{s_1-1}\geq l$ などより3.2の(a)が満たされるように構成されていることがわかる。また、 $B_1$ や $B_2$ の $(\rho^j,\rho^{j+1}]$ への制限は空集合であるか $B_{n,1}$ や $B_{n,2}$ であるため、3.2の(b)も成立することがわかる*17。従って、あとは3.2の(c)が成り立っていることを確認すればよい。

4.12 各 $i\in [k]$ と $n_i \in A_i$ に対し、 $Q_{n_i}:=\mathcal{P}\cap (8^{n_i-1},8^{n_i+2}]$ とし、

$\displaystyle Q_i:=\bigcup_{n_i \in A_i}Q_i$

とおく(これは非交和になっている)。 $\#Q_{n_i}\leq C8^{n_i}/n_i$ なので、

$\displaystyle \sum_{m\in Q_1\cdot\cdots \cdot Q_k}\frac{1}{m}=\prod_{i=1}^k\left(\sum_{m\in Q_i}\frac{1}{m}\right) \leq \prod_{i=1}^k\left(\sum_{n_i\in A_i}\frac{\#Q_{n_i}}{8^{n_i-1}}\right)\leq 8^kC^k\prod_{i=1}^k\left(\sum_{n_i\in A_i}\frac{1}{n_i}\right) \tag{10}$

と評価できる。一方、 $x_i$ が十分大きいことから

$\displaystyle \#P_{n_i}=\left\lfloor\frac{D8^{x_i}}{Kx_i}\right\rfloor\geq \frac{D8^{x_i}}{Kx_i}-1\geq \frac{D8^{x_i}}{2Kx_i}\geq \frac{D8^{n_i-1}}{2K(n_i+1)}\geq \frac{D8^{n_i}}{32Kn_i}$

が成り立ち、

$\begin{align} \sum_{m\in B_2}\frac{1}{m}&=\sum_{n_1\in A_1,\dots, n_k\in A_k}\left(\sum_{p_1\in P_{n_1},\dots, p_k\in P_{n_k}}\frac{1}{p_1\cdots p_k}\right)\geq \sum_{n_1\in A_1,\dots,n_k\in A_k}\prod_{i=1}^k\frac{\#P_{n_i}}{8^{n_i+2}}\\ &\geq \frac{D^k}{2048^kK^k}\prod_{i=1}^k\left(\sum_{n_i\in A_i}\frac{1}{n_i}\right)\tag{11} \end{align}$

と評価できる*18。 $(10), (11)$ を合わせると

$\displaystyle \sum_{m \in B_2}\frac{1}{m}\geq \frac{D^k}{16384^kC^kK^k}\sum_{m\in Q_1\cdot\cdots\cdot Q_k}\frac{1}{m}\tag{12}$

を得る。

4.13 ( $B_1$ に関する期待値評価)
$B_1$ の元は素数なので、

$\displaystyle \mathbb{E}^{\log}_{m\in B_1}\mathbb{E}^{\log}_{n\in B_1}\bigl(\mathrm{gcd}(m,n)-1\bigr)= \mathbb{E}^{\log}_{m\in B_1}\left(\frac{\sum_{n\in B_1}\frac{\mathrm{gcd}(m,n)-1}{n}}{\sum_{n\in B_1}\frac{1}{n}}\right) =\frac{\mathbb{E}^{\log}_{m\in B_1}\left(\frac{m-1}{m}\right)}{\sum_{n\in B_1}\frac{1}{n}} \leq \frac{1}{\sum_{n\in B_1}\frac{1}{n}}$

が成り立つ。また、3.2の(b)より各 $j$ に対して $\#(B_1\cap(\rho^j,\rho^{j+1}])=\#(B_2\cap(\rho^j,\rho^{j+1}])=t_j$ とおくと、

$\begin{align} \sum_{m\in B_1}\frac{1}{m}&=\sum_j\sum_{m\in B_1\cap(\rho^j,\rho^{j+1}]}\frac{1}{m}\geq \sum_j\frac{t_j}{\rho^{j+1}}\\ &=\frac{1}{\rho}\sum_j\frac{t_j}{\rho^{j+1}}\geq \frac{1}{\rho}\sum_j\sum_{m\in B_2\cap(\rho^j,\rho^{j+1}]}\frac{1}{m}=\frac{1}{\rho}\sum_{m\in B_2}\frac{1}{m} \end{align}$

と評価できるので、 $(11)$ , $A_i$ の取り方, $\rho < 2$ , $N$ の取り方より

$\displaystyle \mathbb{E}^{\log}_{m\in B_1}\mathbb{E}^{\log}_{n\in B_1}\bigl(\mathrm{gcd}(m,n)-1\bigr)\leq \frac{\rho}{\sum_{m\in B_2}\frac{1}{m}}\leq \frac{2048^kK^k\rho}{D^k\prod_{i=1}^k\left(\sum_{n_i\in A_i}\frac{1}{n_i}\right)}\leq \frac{2048^kK^k\rho}{D^kN} < \eta$

を示すことができた。これで3.2の(c)を $B_1$ に対して証明できたことになる。

4.14 $U, V$ を自然数からなる互いに素な集合とする。このとき、等式

$\begin{align} &\mathbb{E}_{m\in UV}^{\log}\mathbb{E}_{n\in UV}^{\log}\bigl(\mathrm{gcd}(m,n)-1\bigr)\\ &=\left(\mathbb{E}_{m\in U}^{\log}\mathbb{E}_{n\in U}^{\log}\bigl(\mathrm{gcd}(m,n)-1\bigr)\right)\cdot\left(\mathbb{E}_{m\in V}^{\log}\mathbb{E}_{n\in V}^{\log}\bigl(\mathrm{gcd}(m,n)-1\bigr)\right)\\ &\qquad +\mathbb{E}_{m\in U}^{\log}\mathbb{E}_{n\in U}^{\log}\bigl(\mathrm{gcd}(m,n)-1\bigr)+\mathbb{E}_{m\in V}^{\log}\mathbb{E}_{n\in V}^{\log}\bigl(\mathrm{gcd}(m,n)-1\bigr) \end{align}$

が成り立つ。

証明. これは

$\displaystyle \sum_{m\in UV}\frac{1}{m}=\left(\sum_{m\in U}\frac{1}{m}\right)\left(\sum_{m \in V}\frac{1}{m}\right)$

であることと、 $m_1,n_1\in U$ , $m_2, n_2\in V$ に対して

$\begin{align} &\mathrm{gcd}(m_1m_2,n_1n_2)-1\\ &=(\mathrm{gcd}(m_1,n_1)-1)(\mathrm{gcd}(m_2,n_2)-1)+(\mathrm{gcd}(m_1,n_1)-1)+(\mathrm{gcd}(m_2,n_2)-1) \end{align}$

が成り立つことからわかる。 Q.E.D.

よって、特に $\mathbb{E}_{m\in U}^{\log}\mathbb{E}_{n\in U}^{\log}\bigl(\mathrm{gcd}(m,n)-1\bigr)$ と $\mathbb{E}_{m\in V}^{\log}\mathbb{E}_{n\in V}^{\log}\bigl(\mathrm{gcd}(m,n)-1\bigr)$ が $1$ 以下であれば

$\begin{align} &\mathbb{E}_{m\in UV}^{\log}\mathbb{E}_{n\in UV}^{\log}\bigl(\mathrm{gcd}(m,n)-1\bigr)\\ &\leq 3\max\left\{\mathbb{E}_{m\in U}^{\log}\mathbb{E}_{n\in U}^{\log}\bigl(\mathrm{gcd}(m,n)-1\bigr), \mathbb{E}_{m\in V}^{\log}\mathbb{E}_{n\in V}^{\log}\bigl(\mathrm{gcd}(m,n)-1\bigr)\right\}\end{align}$

が成り立つ。

4.15 ( $B_2$ に関する期待値評価)
各 $i \in [k]$ について $P_{n_i}\subset Q_{n_i}$ であるため、 $B_2\subset Q_1\cdot \cdots \cdot Q_k$ が成り立つ。このことと、 $(12)$ から

$\displaystyle \mathbb{E}_{m\in B_2}^{\log}\mathbb{E}_{n\in B_2}^{\log}\bigl(\mathrm{gcd}(m,n)-1\bigr)\leq \left(\frac{16384CK}{D}\right)^{2k}\mathbb{E}_{m\in Q_1\cdot \cdots \cdot Q_k}^{\log}\mathbb{E}_{n\in Q_1\cdot \cdots \cdot Q_k}^{\log}\bigl(\mathrm{gcd}(m,n)-1\bigr)$

と評価できる。 $Q_i$ は素数の集合なので

$\displaystyle\mathbb{E}_{m\in Q_i}^{\log}\mathbb{E}_{n\in Q_i}^{\log}\bigl(\mathrm{gcd}(m,n)-1\bigr)\leq \frac{1}{\sum_{m\in Q_1}\frac{1}{m}}$

が成り立ち、 $Q_{n_i}\subset (8^{n_i-1}, 8^{n_i+2}]$ , $\#Q_{n_i}\geq 8^{n_i}/n_i$ , $A_i$ の取り方より

$\displaystyle \sum_{m \in Q_i}\frac{1}{m}\geq \frac{1}{64}\sum_{n_i\in A_i}\frac{1}{n_i}\geq \frac{N}{64} \ ( > 1)$

であることに注意すると、4.14を用いた数学的帰納法により

$\displaystyle \mathbb{E}_{m\in Q_1\cdot \cdots \cdot Q_k}^{\log}\mathbb{E}_{n\in Q_1\cdot \cdots \cdot Q_k}^{\log}\bigl(\mathrm{gcd}(m,n)-1\bigr)\leq 3^k\max\left\{\frac{1}{\sum_{m\in Q_1}\frac{1}{m}}, \dots, \frac{1}{\sum_{m\in Q_k}\frac{1}{m}}\right\}$

と評価でき、

$\displaystyle \mathbb{E}_{m\in B_2}^{\log}\mathbb{E}_{n\in B_2}^{\log}\bigl(\mathrm{gcd}(m,n)-1\bigr)\leq \frac{64\cdot 3^k}{N}\cdot\left(\frac{16384CK}{D}\right)^{2k}$

に到達する。 $N$ の取り方からこれは $\eta$ で上から押さえることができ、3.2の(c)が $B_2$ に対しても成立することが示された。

4.16 証明すべきことが全てなされたので、素数定理の証明も以上をもって完結する。

*1:期待値記号 $\mathbb{E}$ や $\mathbb{E}^{\log}$ を二重に用いる場合はここのように適宜括弧を省略する. 有限和なので当然問題は生じない.

*2: $\left(\mathbb{E}_{n\in A}\bigl(f(n)\bigr)\right)^2\leq \mathbb{E}_{n\in A}\bigl(\bigl(f(n)\bigr)^2\bigr)$ という型で用いる.

*3:次のように計算すればよい: $\begin{align} \left(\mathbb{E}_{m\in B}^{\log}\bigl(1-m\mathbf{1}_{m\mid n}\bigr)\right)^2&=\frac{\left(\sum_{m\in B}(1-m\mathbf{1}_{m\mid n})/m\right)^2}{\left(\sum_{m\in B}1/m\right)^2}=\frac{\sum_{m\in B}\sum_{l\in B}(1-m\mathbf{1}_{m\mid n}-l\mathbf{1}_{l\mid n}+m\mathbf{1}_{m\mid n}l\mathbf{1}_{l\mid n})/(ml)}{\left(\sum_{m\in B}1/m\right)\left(\sum_{l\in B}1/l\right)}\\ &=1-2\frac{\sum_{m\in B}m\mathbf{1}_{m\mid n}/m}{\sum_{m\in B}1/m}+\frac{\sum_{m\in B}\sum_{l\in B}(m\mathbf{1}_{m\mid n}l\mathbf{1}_{l\mid n})/(ml)}{\left(\sum_{m\in B}1/m\right)\left(\sum_{l\in B}1/l\right)}. \end{align}$

*4: $N=mq+r$ を $N$ を $m$ で割った表示とすると, $\displaystyle \mathbb{E}_{n\in N}\bigl(m\mathbf{1}_{m\mid n}\bigr)=\frac{\overbrace{m+m+\cdots+m}^{q}}{N}=\frac{N-r}{N}=1+O(1/N)$ .

*5: $\displaystyle \mathbb{E}_{m\in B}^{\log}\bigl(1+O(1/N)\bigr)=\frac{\sum_{m\in B}1/m+O\left(\sum_{m\in B}1/(Nm)\right)}{\sum_{m\in B}1/m}=1+O(1/N)$ .

*6: $m$ と $l$ の最小公倍数の倍数であって $N$ 以下であるような $n$ について $ml$ をピックアップしていくので, $N=\mathrm{lcm}(m,l)q+r$ と割り算をするとき, $\displaystyle \mathbb{E}_{n\in N}\bigl(m\mathbf{1}_{m\mid n}\cdot l\mathbf{1}_{l\mid n}\bigr)=\frac{\overbrace{ml+ml+\cdots+ml}^{q}}{N}=\frac{mlq}{N}$ を得る. よく知られているように $ml=\mathrm{gcd}(m,l)\mathrm{lcm}(m,l)$ であることから, $\displaystyle \frac{mlq}{N}=\frac{\mathrm{gcd}(m,l)(N-r)}{N}=\mathrm{gcd}(m,l)\bigl(1+O(1/N)\bigr)$ と計算できる.

*7: $a,b$ が互いに素な自然数であるとき, $\mu(ab)=\mu(a)\mu(b)$ が成り立つ. これは定義から明らか.

*8: $\displaystyle \frac{1}{\lfloor N/m\rfloor}=\frac{\rho^{j+1}}{N}\left(1+\frac{N/\rho^{j+1}-\lfloor N/m\rfloor}{\lfloor N/m\rfloor}\right)$ であるが, $\displaystyle \left|N/\rho^{j+1}-\lfloor N/m\rfloor\right|\leq N/m-N/\rho^{j+1} < \frac{N(\rho-1)}{\rho^{j+1}}\leq \frac{N\eta}{\rho^{j+1}}$ , $\displaystyle \frac{1}{\lfloor N/m\rfloor} < \frac{1}{N/m-1} < \frac{1}{N/\rho^{j+1}} < \frac{2\rho^{j+1}-1}{N}$ と評価できる. 最後の不等式は $N$ が( $B_1, B_2$ に依存して)十分大きければ実現される. $\frac{1}{\lfloor N/\rho^j\rfloor}$ についても同様.

*9: $\rho^2 < 1+3\eta$ , $\rho^2 > 1-3\eta$ .

*10: $x$ 以上の最小の偶数を $2n$ とすれば, $\pi(x)=\pi(2n)$ or $\pi(2n)-1$ であり, $\frac{2n}{\log(2n)}\geq \frac{x}{\log x}$ である. メモ: $y=x/\log x$ は $x\geq e$ で単調増加.

*11:一般に実数 $y$ に対して $\lfloor 2y\rfloor-2\lfloor y\rfloor =0, 1$ .

*12: $e$ とか $16$ という数はそれでないといけないというわけではない.

*13:4つ目の等号が得られる理由は, $\lfloor \sigma x\rfloor \log \lfloor \sigma x\rfloor=\sigma x\log (\sigma x)+O(\beta(\sigma x) )$ , $\lfloor x\rfloor\log\lfloor x\rfloor=x\log x+O(\beta(x) )$ , $(\lfloor \sigma x\rfloor-\lfloor x\rfloor)\log(\lfloor \sigma x\rfloor - \lfloor x\rfloor)=(\sigma-1)x\log( (\sigma-1)x)+O(\beta( (\sigma-1)x)+\beta( (\sigma-1)x+1) )$ および $\beta(x)=O\left(\frac{x}{\log x}\right)$ .

*14:Richterの論文で実際に素数の性質を使う部分は4.1, 4.2のそれぞれの冒頭の議論のみである. 実際には, 2.1の証明において[note]の補題6.7, 補題6.10の証明に素因数分解の情報が使われている.

*15:ただし, 本質的な考え方は全く同じであり, 違いは非常に細かい部分にある.

*16: $A$ と $B$ が互いに素な集合とは、 $A$ の元と $B$ の元の任意の組が互いに素なときにいう。

*17: $(\rho^{i_n},\rho^{i_n+1}]\subset (8^n,8^{n+1}]$ なので、 $n\mapsto i_n$ は単射である。

*18: $P_{n_i}\subset \mathcal{P}\cap (8^{x_i},8^{x_i+\delta}]$ であるが、 $x_i+\delta \leq n_i+2$ と大雑把に評価している。

2020-07-07

有限体の存在性に関するSoundararajanの記事

定理解説

昨日、SoundararajanがarXivに記事をあげていて、さらっと読んだので部分的に紹介する*1。

定理とその証明

次の有名な基本的定理をRamanujanとErdősによるBertrandの仮説の証明を真似れば証明できるということが書かれている。

定理 $\mathbb{F}$ を有限体、 $n$ を正整数とする。このとき、monicな既約多項式 $f(x)\in \mathbb{F}[x]$ で $\deg f=n$ であるようなものが存在する。

多項式の世界での素数の存在性である。

証明. $\#\mathbb{F}=q$ とする。 $n=1$ のときは次数 $1$ のmonic多項式は $q$ 個あるが、それらは全て既約である。以下、 $n\geq 2$ とする。

$\mathcal{F}_n(x)\in \mathbb{F}[x]$ を $\mathbb{F}[x]$ の元であって次数が $n$ であるようなmonic多項式(このようなものは $q^n$ 個ある)全ての積とする。 $\deg\mathcal{F}_n(x)=nq^n$ である。

$d\leq n$ であるような正整数 $d$ と次数が $d$ のmonic既約多項式 $p(x)$ を好きに選んだときの $\mathrm{ord}_{p(x)}(\mathcal{F}_n(x) )$ を計算しよう。これは $\mathcal{F}_n(x)$ を既約多項式分解したときの $p(x)$ の指数であり、Legendreの公式*2の類似によって計算できる。つまり、

$\displaystyle \mathrm{ord}_{p(x)}(\mathcal{F}_n(x) )=\sum_{k=1}^{\left\lfloor \frac{n}{d}\right\rfloor}$ ( $p(x)^k$ で割り切れるような次数 $n$ のmonic多項式の個数)

が成り立つ。 $p(x)^k$ で割り切れるような次数 $n$ のmonic多項式を $f(x)$ とするとき、 $f(x)=p(x)^kg(x)$ の $g(x)$ は次数が $n-kd$ であるようなmonic多項式であるから、そのようなものの個数は $q^{n-kd}$ 個であることがわかる。よって、

$\displaystyle \mathrm{ord}_{p(x)}(\mathcal{F}_n(x) )=\sum_{k=1}^{\left\lfloor \frac{n}{d}\right\rfloor}q^{n-kd}$

と計算できた。ここで、Bertrandの仮説の証明では中央二項係数 $\binom{2N}{N}$ が重要な役割を果たすが、ここではその類似物として

$\displaystyle \frac{\mathcal{F}_n(x)}{\mathcal{F}_{n-1}(x)^q}$

を扱う。用意した公式により

$\displaystyle \mathrm{ord}_{p(x)}\left(\frac{\mathcal{F}_n(x)}{\mathcal{F}_{n-1}(x)^q}\right)=\sum_{k=1}^{\left\lfloor \frac{n}{d}\right\rfloor}q^{n-kd}-q\sum_{k=1}^{\left\lfloor \frac{n-1}{d}\right\rfloor}q^{n-1-kd}=\begin{cases} 1 & (d\mid n)\\ 0 & (d\nmid n) \end{cases}$

と計算できる。 $\mathbb{F}[x]$ の元であって次数が $d$ のmonic既約多項式全体のなす集合を $\mathcal{P}_d$ と表すと、上記計算は

$\displaystyle \frac{\mathcal{F}_n(x)}{\mathcal{F}_{n-1}(x)^q}=\prod_{d\mid n}\prod_{p(x) \in \mathcal{P}_d}p(x) \in \mathbb{F}[x]\tag{1}$

の成立を意味する。次数は

$\displaystyle \deg\left(\frac{\mathcal{F}_n(x)}{\mathcal{F}_{n-1}(x)^q}\right)=nq^n-q\bigl( (n-1)q^{n-1}\bigr)=q^n$

である。背理法で定理を証明するために、 $\mathcal{P}_n=\varnothing$ であったと仮定しよう。 $\mathbb{F}[x]$ の元であって次数が $d$ のmonic多項式全体のなす集合を $\mathbb{F}[x]_d$ と表すことにすると、整除関係

$\displaystyle \left.\frac{\mathcal{F}_n(x)}{\mathcal{F}_{n-1}(x)^q}=\prod_{d\mid n, \ d\neq n}\prod_{p(x) \in \mathcal{P}_d}p(x) \ \right| \ \prod_{d=1}^{\left\lfloor\frac{n}{2}\right\rfloor}\prod_{f(x) \in \mathbb{F}[x]_d}f(x)$

が成り立つ。次数を評価すると、 $\#\mathbb{F}[x]_d=q^d$ に注意して、

$\begin{align} \deg\left(\prod_{d=1}^{\left\lfloor\frac{n}{2}\right\rfloor}\prod_{f(x) \in \mathbb{F}[x]_d}f(x)\right)&=\sum_{d=1}^{\left\lfloor \frac{n}{2}\right\rfloor}dq^d\leq \left\lfloor \frac{n}{2}\right\rfloor\sum_{d=1}^{\left\lfloor \frac{n}{2}\right\rfloor}q^d=\left\lfloor\frac{n}{2}\right\rfloor\cdot\frac{q(q^{\left\lfloor\frac{n}{2}\right\rfloor}-1)}{q-1}\\ &< \left\lfloor\frac{n}{2}\right\rfloor\cdot \frac{q}{q-1}\cdot q^{\left\lfloor\frac{n}{2}\right\rfloor}\leq 2\left\lfloor\frac{n}{2}\right\rfloor q^{\left\lfloor\frac{n}{2}\right\rfloor} \end{align}$

よって、先ほどの整除関係において次数の比較を行うと

$\displaystyle q^n < 2\left\lfloor\frac{n}{2}\right\rfloor q^{\left\lfloor\frac{n}{2}\right\rfloor}$

を得る。一方、

$q^n\geq (q^{\left\lfloor\frac{n}{2}\right\rfloor})^2\geq 2^{\left\lfloor\frac{n}{2}\right\rfloor}q^{\left\lfloor\frac{n}{2}\right\rfloor}\geq 2\left\lfloor\frac{n}{2}\right\rfloor q^{\left\lfloor\frac{n}{2}\right\rfloor}$

なので矛盾に到達した。 Q.E.D.

補足

素数 $p$ に対して位数 $p$ の有限体 $\mathbb{F}_p$ の存在性を示すのは容易いが、位数 $p^n$ の有限体 $\mathbb{F}_{p^n}$ の存在性の証明は比較的難しくなる。この記事で証明した定理(以下、「存在定理」)を用いると、次数 $n$ のmonicな $\mathbb{F}_p$ 係数既約多項式が存在するので、それが生成するイデアルによる $\mathbb{F}_p[x]$ の剰余環は位数が $p^n$ の有限体になっている。

このように存在定理を利用した有限体の存在性証明を採用する際、存在定理はゼータ関数を用いて証明されるのが標準的なようである。その証明を知りたい方には黒木先生の記事(PDF)

http://www.math.tohoku.ac.jp/~kuroki/LaTeX/20080424_finite_field.pdf

を参照していただきたい。

有限体の存在という極めて代数的な定理の証明にゼータ関数という解析(数論)的な対象を用いて見事に証明できるというのは面白い。

面白いし、その手法によるご利益もあるし、ゼータ関数について同時に学ぶことができて一石二鳥といいこと尽くめのようでもあるが、学生に厳密に理解させるためには無限和や無限積について別途説明する必要がある。

一方、今回Soundararajanが提案する方法では解析的な手法に頼らずに存在定理を証明することができるため、今後教育の現場で取り入れていってもよさそうだ。

なお、Soundararajanが指摘しているように、ゼータ関数を使った議論で得られるGaussの公式

$\displaystyle q^n=\sum_{d\mid n}d\#\mathcal{P}_d$

は $(1)$ 式の次数を比較することによっても得られる。それにMöbiusの反転公式を施せば $\#\mathcal{P}_n$ の明示公式が得られるが、 $\#\mathcal{P}_n\neq \varnothing$ だけだったら上述のようにRamanujan-Erdősの発想に基づく不等式評価で証明できるというわけだ。

*1:arXiv:2007.01389.

*2: $\mathrm{ord}_p(n!)$ の有名な計算公式。

2020-07-06

ベルヌーイ多項式の特殊値に関するキュートな定理

定理解説

ベルヌーイ多項式 $B_n(x)\in \mathbb{Q}[x]$ は

$\displaystyle F(x,t):=\frac{te^{xt}}{e^t-1}=\sum_{n=0}^{\infty}\frac{B_n(x)t^n}{n!}$

で定義されるのでした。Almkvist-Meurmanが証明した次の定理を紹介します*1。

定理 $n,k,h$ を正整数とする。 $\widetilde{B}_n(x):=B_n(x)-B_n(0)$ とおくとき、

$\displaystyle k^n\widetilde{B}_n\left(\frac{h}{k}\right)\in \mathbb{Z}$

が成り立つ。

ここで紹介する証明はSuryによるものです*2。なお、定理は $n=0$ の場合も $B_0(x)=1$ であることから自明に成立しています。

ベルヌーイ多項式の加法公式

命題 (加法公式)

$\displaystyle B_n(x+y)=\sum_{i=0}^n\binom{n}{i}B_i(x)y^{n-i}$

が成り立つ。

証明. 母関数について

$\displaystyle F(x+y,t)=\frac{te^{(x+y)t}}{e^t-1}=F(x,t)e^{yt}$

が成り立つので、あとは係数を比較すればよい。 Q.E.D.

$h=1$ の場合への帰着

$h=1$ の場合が証明できたと仮定し、一般の $h$ でも成立することを数学的帰納法で証明する。従って、 $h-1$ のときには成立すると仮定する。

加法公式と帰納法の仮定により

$\begin{align} k^nB_n\left(\frac{h}{k}\right) &= k^nB_n\left(\frac{h-1}{k}+\frac{1}{k}\right)\\ &=k^n\sum_{i=0}^n\binom{n}{i}B_i\left(\frac{h-1}{k}\right)\frac{1}{k^{n-i}}\\ &=\sum_{i=0}^n\binom{n}{i}k^iB_i\left(\frac{h-1}{k}\right)\\ &\equiv \sum_{i=0}^n\binom{n}{i}k^iB_i(0) \pmod{1} \end{align}$

が成り立つ。ここで、 $\bmod{1}$ は差が整数であることを意味する。最後の値は $h$ には依存しないものなので、

$\displaystyle k^nB_n\left(\frac{h}{k}\right)\equiv k^nB_n\left(\frac{1}{k}\right)\equiv k^nB_n(0)$

となる。

2つの漸化式

以下、

$\displaystyle a_n(k):=k^n\widetilde{B}_n\left(\frac{1}{k}\right)$

とおく。このとき、

$\displaystyle \sum_{n=1}^{\infty}\frac{a_n(k)t^n}{n!}=F\left(\frac{1}{k},kt\right)-F(0,kt)=\frac{kt(e^t-1)}{e^{kt}-1}$

が成り立つ。これを

$\displaystyle \left(\sum_{n=1}^{\infty}\frac{a_n(k)t^n}{n!}\right)(e^{kt}-1)=kt(e^t-1)$

として係数を比較すれば、 $n\geq 1$ に対して

$\displaystyle \sum_{i=1}^n\binom{n+1}{i}a_i(k)k^{n+1-i}=(n+1)k$

が得られる。両辺を $k$ で割って移項すれば

$\displaystyle \sum_{i=1}^{n-1}\binom{n+1}{i}a_i(k)k^{n-i}=(n+1)(1-a_n(k)).\tag{1}$

一方、

$\displaystyle \left(\sum_{n=1}^{\infty}\frac{a_n(k)t^n}{n!}\right)(1+e^t+\cdots +e^{(k-1)t})=kt$

として係数を比較すれば、 $ka_1(k)=k$ から $a_1(k)=1$ がわかり、 $n\geq 2$ の場合は

$\displaystyle \sum_{i=1}^{n-1}\binom{n}{i}a_i(k)s_{n-i}(k)+ka_n(k)=0$

が得られる。ここで、

$\displaystyle s_n(k):=\sum_{i=1}^{k-1}i^n$

である( $s_n(1):=0$ )。移項して

$\displaystyle -\sum_{i=1}^{n-1}\binom{n}{i}a_i(k)s_{n-i}(k)=ka_n(k)\tag{2}$

としておく。

証明

補題 $p$ を素数とし、整数 $i, r$ は $1\leq i\leq r$ を満たし、正整数 $m$ は $p$ と互いに素なものとする。このとき、

$\displaystyle \mathrm{ord}_p\binom{mp^r}{i}\geq r-i+1$

が成り立つ。 $\mathrm{ord}_p$ は $p$ で割り切れる回数(付値)を表すものとする。

証明二項係数の定義より

$\displaystyle \binom{mp^r}{i}=\frac{mp^r}{i}\binom{mp^r-1}{i-1}\equiv 0 \pmod{p^{r-\mathrm{ord}_p(i)}}$

である。また、 $i\geq 2$ であれば

$\mathrm{ord}_p(i)\leq \log_p(i)\leq \log_2(i)\leq i-1$

と評価でき、この不等式の最初と最後だけを見れば $i=1$ のときも正しい。 Q.E.D.

定理の証明 $h=1$ の場合に示せばよいのであった。 $a_n(k)\in \mathbb{Z}$ を $n$ に関する数学的帰納法で証明する。 $a_1(k)=1$ なので、 $n=1$ のときはOK。 $n\geq 2$ とし、 $a_1(k), a_2(k), \dots, a_{n-1}(k)\in \mathbb{Z}$ を仮定する。