伯特蘭-切比雪夫定理

伯特蘭-切比雪夫定理說明：若整數$n>3$，則至少存在一個質數$p$，符合$n<p<2n-2$。另一個稍弱說法是：對於所有大於1的整數$n$，存在一個質數$p$，符合$n<p<2n$。

1845年約瑟·伯特蘭提出這個猜想。伯特蘭檢查了2至3×106之間的所有數。1852年切比雪夫證明了這個猜想。拉馬努金給出較簡單的證明，而艾狄胥則借二項式係數給出了另一個簡單的證明。

## 相關定理

### 西爾維斯特定理

詹姆斯·約瑟夫·西爾維斯特證明：$k$個大於$k$的連續整數之積，是一個大於$k$的質數的倍數。

### 艾狄胥定理

艾狄胥證明：對於任意正整數$k$，存在正整數$N$使得對於所有$n>N$而言，$n$和$2n$之間有$k$個質數。

根據質數定理，$n$和$2n$之間的質數數目大約是$n\over\log(n)$。

## 證明

切比雪夫原始的證明是他所證明的以下和質數計數函數$\pi(n)$相關的不等式的一個引申結果：

對於足夠大的$x$，有$A\frac{x}{\log(x)} < \pi(x) < \frac{6A}{5}\frac{x}{\log(x)} \; \text{，其中} \; A \approx 0.92129.$

在1932年，保羅·艾狄胥給出一個初等證明。下文的證明以保羅·艾狄胥提出的證明為基礎，證明的方法是運用反證法，反設定理不成立，然後用兩種方法估計${2n \choose n}$的上下界，得出矛盾的不等式

註：下面的證明中，都假設$p$屬於質數集。

### 不等式1

這條不等式是關於${2n \choose n}$的下界的。

- 對於正整數$n$，${2n \choose n} \ge \frac{4^n}{2n}$

證明：

對於 $k \le 2n$， ${2n \choose n} \ge {2n \choose k}$

若$k \ne n$，${2n \choose n} > {2n \choose k}$

因此$2n {2n \choose n} \ge \sum_{i=1}^{2n} {2n \choose i} + 1 = 2^{2n} = 4^n$

### 引理1

- $$\prod_{k+1 < p \le 2k+1 } p \ < 4^k$$

證明：

注意到所有大於 k+1 而小於 2k+1 的質數都在(2k+1)! 中而不在(k+1)! 或 k！中，於是$\prod_{k+1 < p \le 2k+1} p$ 是${ {2k+1} \choose {k+1} }$的因子。

$$\prod_{k+1 < p \le 2k+1 } p \quad \left \vert \ { {2k+1} \choose {k+1} }\right.$$

同時又有 $2{ {2k+1} \choose {k+1} } = { {2k+1} \choose {k+1} } + { {2k+1} \choose {k} }< \sum_{i=0}^{2k+1} { {2k+1} \choose {i} } =2 \cdot 4^k$

於是就有 $\prod_{k+1 < p \le 2k+1 } p\ \ \le { {2k+1} \choose {k+1} } < 4^k$

### 定理1

這個定理和${2n \choose n}$的上界有關。

- 對於所有正整數$n$， $\prod_{p \le n } p < 4^n$

數學歸納法：

當$n=2$，2 < 16，成立。

假設對於所有少於$n$的整數，敘述都成立。

顯然，若n>2且n是偶數，$\prod_{p \le n } p = \prod_{p \le n-1 } p$。對於奇數的n，設n=2k+1。

從引理1和歸納假設可得：

$$\prod_{p \le n } p = \prod_{p \le 2k+1 } p = \prod_{p \le k+1 } p \cdot \prod_{k+1 < p \le 2k+1 } p < 4^{k+1} \cdot 4^k = 4^{2k+1} = 4^n$$

### 系理1

首先的定理：

- 若$p$是質數，$n$是整數。設$s$是最大的整數使得$p^s|n!$，則$s=\sum_{i=1}^{\infty} {\lbrack \frac{n}{p^i} \rbrack}$

下面這些系理和${2n \choose n}$的上界有關。

若$p$為質數，設$s_p$是最大的整數使得 $p^{s_p}$ 整除 ${2n \choose n}$，則：

$$s_p=\sum_{i \ge 1} {( \lbrack \frac{2n}{p^i} \rbrack - 2 \lbrack \frac{n}{p^i} \rbrack ) }$$

對於所有$x>0$，$\lbrack 2x \rbrack - 2 \lbrack x \rbrack \le 1$，所以

$$s_p=\sum_{i \ge 1} {( \lbrack \frac{2n}{p^i} \rbrack - 2 \lbrack \frac{n}{p^i} \rbrack ) } \le max \left\{ r | p^r \le 2n \right\}$$

於是得到三個上界：

- $$p^{s_p} \le 2n$$
- 若 $\sqrt{2n} < p$， $s_p \le 1$
- 若 $2n/3 < p \le n$，$s_p=0$（因為 2n! 中只有兩個 p，在 n! 中恰有一個 p）

### 核心部分

假設存在大於1的正整數$n$，使得沒有質數$p$符合$n<p<2n$。根據系理1.2和1.3：

$${2n \choose n} = \prod_{p \le 2n} p^{s_p} = \prod_{p \le 2n/3 } p^{s_p} \le \prod_{ p \le \sqrt{2n} } p^{s_p -1} \cdot \prod_{ p \le 2n/3 } p$$

再根據系理1.1和定理1：

${2n \choose n} \le$ 上式最右方 $< (2n)^{\sqrt{2n}/2-1} \cdot 4^{2n/3}$

結合之前關於$2n \choose n$的下界的不等式1：

$$(2n)^{-1} 4^n < {2n \choose n} < (2n)^{\sqrt{2n}/2-1} \cdot 4^{2n/3}$$

$$4^n < (2n)^{\sqrt{2n}/2} \cdot 4^{2n/3}$$

$$4^{2n/3} < (2n)^{\sqrt{2n}}$$

兩邊取自然對數，並設$x = \sqrt{2n}$：

$x \ln 2 - 3 \ln x <0$。

顯然$x \ge 16$，即$n \ge 128$時，此式不成立，得出矛盾。

因此$n \ge 128$時，伯特蘭—切比雪夫定理成立。

再在$n<128$時驗證這個假設即可。

## 參考

- A simple proof of Bertrand's Postulate, Neil Lyall
- Number Theory. Tutorial 5: Bertrand's Postulate

## 外部連結

- Some Problems of Combinatorial Number Theory Related to Bertrand's Postulate, Lawrence E. Greenfield