经典证明:用信息熵证明素数无穷多

    偶然读到一个非常帅的证明:用信息熵可以瞬间证明素数有无穷多个。这个证明比本 Blog 之前讲过的五种非主流证明 (282, 539, 1678) 看上去都要帅,并且更重要地,它道出了素数无穷多的根本原因:只有无穷多的素数,才有能力表达出如此丰富的自然数世界。
    假设我们从所有不超过 n 的自然数中随机选取一个数 N ,并把它分解成质因数的乘积 N = P1^X1 * P2^X2 * … * Pm^Xm,其中 m 是不超过 n 的素数的个数。注意到由于 2^Xi ≤ Pi^Xi ≤ N ≤ n 对所有 i 都成立,因此我们有 Xi ≤ log(n) 。真正帅的地方来了。考虑随机选取一个 N 带来的信息熵,我们有:

log(n) = H(N)
         = H(X1, X2, …, Xm)
         ≤ H(X1) + H(X2) + … + H(Xm)
         ≤ log(log(n)+1) * m

    上面的第一个等号是由信息熵的定义直接得出的。第二个等号是由唯一分解定理得到的:由于一个数可以唯一地分解为质因数的乘积,因此 N 和 (X1, X2, …, Xm) 是一一对应的,知道了前者也就确定了后者,它们的信息熵是相同的。第三行的不等式是由于我们放开了 Xi 的取值条件(每个 Xi 独立取值可能会导致它们的乘积超过 n ),必然会增加结果的不确定性。而每个 Xi 的取值范围不会超出 0 到 log(n) ,最多 log(n)+1 种情况,因此 H(Xi) ≤ log(log(n)+1) ,这就得到了第四行的那个不等式。
    整理上式,我们得到了 m ≥ log(n) / log(log(n)+1) ,这不但告诉我们当 n 趋于无穷大时不超过 n 的素数个数也是趋于无穷的,还给出了不超过 n 的素数个数的一个下界。

29 条评论

发表评论

3  ×    =  15