伯特兰-切比雪夫定理

用手机看条目

出自 MBA智库百科(https://wiki.mbalib.com/)

伯特兰-切比雪夫定理(Bertrand Chebyshev theorem)

目录

什么是伯特兰-切比雪夫定理

  伯特兰-切比雪夫定理是指1845年约瑟•伯特兰提出的猜想。伯特兰检查了2至3×106之间的所有数。1850年切比雪夫证明了这个猜想。拉马努金给出较简单的证明,而保罗•艾狄胥则借二项式系数给出了另一个简单的证明。

  伯特兰-切比雪夫定理说明:若整数n > 3,则至少存在一个质数p,符合n < p < 2n − 2。另一个稍弱说法是:对于所有大于1的整数n,存在一个质数p,符合n < p < 2n

伯特兰-切比雪夫定理的相关定理

西尔维斯特定理

  詹姆斯•约瑟夫•西尔维斯特证明:k个大于k的连续整数之积,是一个大于k的质数的倍数

艾狄胥定理

  艾狄胥证明:对于任意正整数k,存在正整数N使得对于所有n > Nn2n之间有k个质数。

  他又证明k = 2N = 6时,而且有,其中两个质数分别是4的倍数加1,4的倍数减1。

  根据质数定理,n2n之间的质数数目是n\over\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是最大的整数使得ps | n! ,则s=\sum_{i=1}^{\infty} {\lfloor \frac{n}{p^i} \rfloor}

  下面这些系理和{2n \choose n}的上界有关。

  若p为质数,设sp是最大的整数使得 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\}

  于是得到三个上界:

   p^{s_p} \le 2n

   若 \sqrt{2n} < ps_p \le 1

   若 2n/3 < p \le nsp = 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}}

  两边取2的对数,并设x = \sqrt{2n}

  xln2 − 3lnx < 0

  显然x \ge 16,即n \ge 128时,此式不成立,得出矛盾。

  因此n \ge 128时,伯特兰—切比雪夫定理成立。

  再在n < 128时验证这个假设即可。

本条目对我有帮助14
MBA智库APP

扫一扫,下载MBA智库APP

分享到:
  如果您认为本条目还有待完善,需要补充新内容或修改错误内容,请编辑条目

本条目由以下用户参与贡献

Tracy,Mis铭.

评论(共0条)

提示:评论内容为网友针对条目"伯特兰-切比雪夫定理"展开的讨论,与本站观点立场无关。

发表评论请文明上网,理性发言并遵守有关规定。

MBA智库
打开APP

以上内容根据网友推荐自动排序生成