在数论中，埃尔德什-卡茨定理（），以埃尔德什·帕尔和马克·卡茨命名，也被称为概率数论的“基本定理”。该定理指出，如果 \omega(n) 是整数 n 的不同素因子个数，那么，粗略地说，
: \frac{\omega(n) - \ln\ln n}{\sqrt{\ln\ln n}}
的概率分布收敛于标准正态分布。（\omega(n) 是整数数列线上大全中的数列 A001221。）这是哈代—拉马努金定理的推广，后者指出 \omega(n) 的正规序（normal order）是 \ln\ln n，典型误差大小为 \sqrt{\ln\ln n}。
精确表述
对于任意固定的 a ，有：
:\lim_{x \rightarrow \infty} \left ( \frac {1}{x} \cdot \#\left\{ n \leq x : a \le \frac{\omega(n) - \ln \ln n}{\sqrt{\ln \ln n}} \le b \right\} \right ) = \Phi(a,b)
其中 \Phi(a,b) 是标准正态（或“高斯”）分布，定义为：
: \Phi(a,b)= \frac{1}{\sqrt{2\pi}}\int_a^b e^{-t^2/2} \, dt.
更一般地，如果 f(n) 是一个强加性函数（即对于所有素数 p，有 f(p_1^{a_1}\cdots p_k^{a_k})=f(p_1)+\cdots+f(p_k)），且对于所有素数 p 都有 |f(p)|\le 1，则：
:\lim_{x \rightarrow \infty} \left ( \frac {1}{x} \cdot \#\left\{ n \leq x : a \le \frac{f(n) - A(n)}{B(n)} \le b \right\} \right ) = \Phi(a,b)
其中
:A(n)=\sum_{p\le n}\frac{f(p)}{p},\qquad B(n)=\sqrt{\sum_{p\le n}\frac{f(p)^2}{p}}.
卡茨的原始启发式
直观地说，卡茨对该结果的启发式论证表明，如果 n 是一个随机选取的大整数，那么 n 的不同素因子的数量近似服从均值和方差均为 \ln\ln n 的正态分布。这源于一个事实：对于随机选取的自然数 n，事件“数字 n 能被素数 p 整除”对于不同的 p 是相互独立的。
现在，用 n_p 表示事件“数字 n 能被 p 整除”，考虑以下指示随机变量的和：
:I_{n_{2}} + I_{n_{3}} + I_{n_{5}} + I_{n_{7}} + \ldots
这个和计算了随机自然数 n 有多少个不同的素因子。可以证明这个和满足林德伯格条件（Lindeberg condition），因此林德伯格中心极限定理保证了在适当的缩放后，上述表达式将服从高斯分布。
该定理的实际证明由爱尔特希完成，使用了筛法使上述直觉得以严格化。
数值例子
爱尔特希-卡茨定理意味着构建一个大约十亿的数字平均需要三个素数。
例如，1,000,000,003 = 23 × 307 × 141623。下表提供了随着 n 的增加，自然数 n 的平均不同素因子数量增长的数值摘要。
大约 12.6% 的 10,000 位数字由 10 个不同的素数构成，大约 68% 由 7 到 13 个素数构成。
如果一个像地球一样大的空心球体填满细沙，大约会有 1033 粒沙子。可观测宇宙体积内大约能容纳 1093 粒沙子。在这个宇宙中可能有空间容纳 10185 个量子弦。
即使是这种量级的数字——有 186 位数——平均也只需要 6 个素数来构建。
通过经验发现爱尔特希-卡茨定理是非常困难的，如果不是不可能的话，因为只有当 n 达到 10^{100} 左右时，高斯分布才会显现出来。更确切地说，雷尼（Rényi）和图兰（Turán）表明，逼近高斯分布的误差的最佳一致渐近界限是
: O\left(\frac{1}{\sqrt{\ln \ln n}}\right).
参考文献
*
*
*
外部链接
*
- [https://www.youtube.com/watch?v=17Xg7Y6DrbI Timothy Gowers: The Importance of Mathematics (part 6, 4 mins in) and (part 7)]
评论 (0)