伦敦 伦敦00:00:00 纽约 纽约00:00:00 东京 东京00:00:00 北京 北京00:00:00

400-668-6666

切比雪夫

当前位置:主页 > 切比雪夫 >
切比雪夫

伯特兰-切比雪夫定理

  声明:,,,。详情

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

  该定理被约瑟·伯特兰(Joseph Bertrand)提出,由切比雪夫(Chebyshev)证明。

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

  引理 1: 设 n 为一自然数, p 为一素数, 则能整除 n! 的 p 的最高幂次为:s,([x]表示不大于x的最大整数)。

  证明: 能整除 n! 的 p 的最高幂次显然等于从 1 到 n 的各自然数中 p 的最高幂次之和, 即

  (其中 si 为能整除 i 的 p 的最高幂次)。 然后将从 1 到 n 的所有 (n 个) 自然数排列在一条直线上, 在每个数字上叠放一列 si 个记号, 显然记号的总数是 s。 关系式

  表示的是先计算各列的记号数 (即 si) 再求和。 但我们也可以先计算各行的记号数再求和, 由此得到的关系式正是引理 1。为了证明这一点, 我们从数字所在的直线开始自下而上计数。很明显所有第一行有记号的数字都含有因子 p (因为否则的线, 没有记号),这种数字的总数 (也就是该行的记号总数)是 n/p ; 第二行有记号的数字都含有因子 p2 (因为否则的线, 在第二行上不会有记号),这种数字的总数 (也就是该行的记号总数) 是 n/p2 ,依此类推,第i行的记号总数为 n/pi 。 将所有这些数字相加便证明了引理 1。Q.E.D.(此段冗余 应放入“勒让德定理”词条 直接从推论1.1开始)

  我们之所以用这样一种比较文字化的方式来叙述引理 1 的证明过程, 目的在于更清楚地显示该证明的基本思路:即利用一个有限二维点阵求和的不同方式 (顺序) 得到互相等价的不同表达式。 这是数学证明中一种常用的手段。

  的 p 的最高幂次, 则:(a) p^s ≤ 2n; (b) 若 p √2n,则s≤1;(c) 若 2n/3 p ≤ n,则s = 0。

  证明: (a) 设 m 为满足 p^m ≤ 2n 的最大自然数, 则显然对于 i m, [2n/pi ]- 2 [n/pi ]= 0 - 0 = 0。因此推论 1.1 中的求和止于 i = m, 共计 m 项。 由于 [2x ]- 2 [x ]≤ 1, 因此这 m 项中的每一项不是 0 就是 1, 其求和结果不超过项数本身, 即 s ≤ m, 因此 p^s ≤ p^m ≤ 2n。

  (b) 因为 p √2n 表明 p^2 2n, 因此由 (a) 可得 s ≤ 1。

  (c) 因为 n ≥ 3 及 2n/3 p ≤ n 表明 p^2 2n,因此推论 1.1 中的求和只有 i = 1 一项, 即: s = [2n/p] - 2 [n/p] 。 由于 2n/3 p ≤ n 还表明 1 ≤ n/p 3/2, 因此 s = 2n/p - 2 n/p = 2 - 2 = 0。 Q.E.D.

  引理 2: 设 n 为自然数, p 为素数, 则 Π(p≤n) p 4^n。

  假设引理对 n N 成立 (N 2), 我们来证明 n = N 的情形。 如果 N 为偶数, 则

  如果 N 为奇数, 设 N = 2m + 1 (m ≥ 1)。 注意到所有 m + 1 p ≤ 2m + 1 的素数都是组合数

  的因子 (因为它们是 (2m+1)! 的因子, 但却不是 m! 和 (m+1)! 的因子); 另一方面组合数

  , 并被称为 Chebyshevs Bound (以 Chebyshev 命名的结果, 无论是前面提到的 Bertrand 假设的别称 Chebyshev 定理还是这里所说的 Chebyshevs Bound, 都有不止一个对应, 查阅文献时要当心)。

  用反证法, 假设命题不成立,即存在某个 n ≥ 2, 在 n 与 2n 之间没有素数。 我们来看

  (s(p)为质因子 p 的幂次)。 由推论 1.2(a) 知 p 2n, 由反证法假设知 p ≤ n, 再由推论 1.2(c) 知 p ≤ 2n/3,因此 (2n)!/(n!n!) = Πp≤2n/3 ps(p)。 将连乘分解为 p ≤ √2n 及 √2n p ≤ 2n/3 两部分 (这一分解要求 n 4, 但后面我们会看到, 我们的整个方法只适用于 n ≥ 50, 因此我们其实是假定 n ≥ 50, 对 50 以下的情形只需直接验证即可), 并利用推论 1.2(b) 可得:

  (2n)!/(n!n!) ≤ Πp≤√2n ps(p) · Π√2n p ≤ Πp≤√2n ps(p) · Πp≤2n/3 p

  该乘积中的第一组的被乘因子数目为 √2n 以内的素数数目,即不多于 √2n/2 - 1 (因偶数及 1 不是素数), 而每个因子按照推论 1.2(a) 均不大于 2n, 因此该组乘积不大于 (2n)√2n/2-1。 第二组乘积按照引理 2 小于 42n/3, 由此得到:

  (2n)!/(n!n!) (2n)√2n/2-1 · 42n/3。

  另一方面, (2n)!/(n!n!) 是 (1+1)2n 展开式中最大的一项, 而该展开式共有 2n 项 (我们将首末两项 1 合并为 2), 因此 (2n)!/(n!n!) ≥ 22n / 2n = 4n / 2n。将此式与上一段最后的结果联立并略经化简可得 4n/3 (2n)√n/2。两端取对数并进一步化简可得:

  由于幂函数 √2n 随 n 的增长速度远快于对数函数ln(2n), 因此上式对于足够大的 n 显然不可能成立。简单的数值计算表明, 对于 n = 50 上式左边为 13.8629..., 右边为 13.8155..., 不等式不成立。 这表明我们所作的反证假设, 即 Bertrand 假设不成立, 对于 n ≥ 50 是错误的, 换句话说 Bertrand 假设对于 n ≥ 50 成立。 简单的验证可以证明 Bertrand 假设对于 n 50 也成立 (事实上前面说过,Bertrand本人就已经对 n 3000000 做过验证), 因此我们证明了 Bertrand 假设。 Q.E.D.

  由于本文是本系列文章的第一篇,在这里稍稍说上几句题外话。 对于没有从事过研究工作的人来说,复杂数学定理(Bertrand 假设当然不在此列)的证明常常显得有些高深莫测。一个具有足够理解力和适当基础的人也许可以看懂一个复杂证明的每一个推理环节,但一环环地攀完了长长的逻辑链条后仍不免有一种 “只见树木, 不见森林”的感觉。那些幽深曲折,有时甚至是匪夷所思的精巧思路委实让人惊叹不已。那些精巧思路的一部分是来源于经年累月的尝试和努力,就象小时候很多人爱玩的画报上的迷宫游戏,一次次碰壁,一次次重来,才换得最后那条精巧的胜利折线。局外人只看结果,自不免惊为神来之笔。不过这类比拟不可无限外推,让人误以为只要敢于尝试,不怕碰壁,就一定能够成功。须知人力有时而穷,一味地相信“人定胜天”并不是科学的态度。数学世界不是画报上的迷宫,画报上的迷宫是有限的,数学世界的变化却是无穷的。数学是一门大智慧的学问,绝非是只凭苦力就一定能够换取成功的。如果一味地蛮干,甚至是只学了一点初等数学就迫不及待地企图用自己的勤奋来攻克最艰深的数学问题,则往往穷尽一生一世也只是枉费心力,且有可能走火入魔。

  重新回到 Bertrand 假设上来, Bertrand 假设是一个非常简单的定理, 本文所介绍的证明其基本思路在于显示当 n 与 2n 之间不存在素数时 (2n)!/(n!n!) 将无法找到足够多的素数因子来作分解, 也就是说 (2n)!/(n!n!) 的素数分解表达式将小于 (2n)!/(n!n!),这就是上面不等式无法成立的原因。 为什么选 (2n)!/(n!n!) 作为分析的对象? 那是因为 (2n)!/(n!n!) = (n+1)···(2n)/n! 包含了所有 n 与 2n 之间的素数因子 (分子上的 (n+1)···(2n)),而又很聪明地约去了许多小于 n 的素数因子 (分母上的 n!),因此非常适合于用来显示缺少了 n 与 2n 之间的素数所造成的后果。

  Bertrand 假设对素数分布作了非常粗略的描述,它表明在x附近的素数分布密度至少是 1/x。与素数定理给出的1/ln(x)相比,Bertrand假设给出的显然很粗略(不过素数定理给出的密度是平均意义上的,而Bertrand 假设给出的是严格的密度下界),因而存在加强的余地。在本文的最后我们列举其中两个这样的加强结果(定理):

  定理 1: 对任意自然数 n 6, 至少存在一个 4k + 1 型和一个 4k + 3 型素数 p 使得 n p 2n。

  定理 2: 对任意自然数 k, 存在自然数 N, 对任意自然数 n N 至少存在 k 个素数 p 使得 n p 2n。


点击次数:  更新时间:2020-10-15 12:21   【打印此页】  【关闭
上一篇:切比雪夫方程   
下一篇:切比雪夫距离
http://juegosamenos.com/qiebixuefu/171/