伯特兰-切比雪夫定理

伯特兰-切比雪夫定理说明：若整数$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