伯特蘭-切比雪夫定理

用手机看条目

出自 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時驗證這個假設即可。

本條目對我有幫助17
MBA智库APP

扫一扫,下载MBA智库APP

分享到:
  如果您認為本條目還有待完善,需要補充新內容或修改錯誤內容,請編輯條目

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

Tracy,Mis铭.

評論(共0條)

提示:評論內容為網友針對條目"伯特蘭-切比雪夫定理"展開的討論,與本站觀點立場無關。

發表評論請文明上網,理性發言並遵守有關規定。

打开APP

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