伯特蘭－切比雪夫定理

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

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

相關定理

西爾維斯特定理

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

艾狄胥定理

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

他又證明$k=2$、$N=6$時，而且其中一個質數是4的倍數加1，另一個是4的倍數減1。

根據質數定理，$n$和$2n$之間的質數數目是$n/\ln(n)$。

證明

證明的方法是运用反證法，反設定理不成立，然后用两种方法估计${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 < 2^{n-1}$

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

$\prod_{k+1 < p \le 2k+1 } p | { {2k+1} \choose {k+1} }$

同时又有 $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} {\lfloor \frac{n}{p^i} \rfloor}$

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

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

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

$\forall x>0, \lfloor 2x \rfloor - 2 \lfloor x \rfloor \le 1$ ，所以

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

于是得到三个上界：

1. $p^{s_p} \le 2n$
2. 若 $\sqrt{2n} < p$ ， $s_p \le 1$
3. 若 $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}$

結合之前關於C(2n,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}}$

兩邊取2的對數，并设$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