Interested Article - Теорема Эрдёша — Каца

Теорема Эрдёша — Каца — утверждение в теории чисел , которое связывает распределение числа разных простых делителей больших чисел с формулами предельных законов теории вероятностей . Этот результат теории чисел , полученный Палом Эрдёшом и Марком Кацем в 1940 году утверждает, что если $\omega (n)$ — число различных простых делителей числа $n$ , то предельное распределение величины

{\frac {\omega (n)-\log \log n}{\sqrt {\log \log n}}}

является стандартным нормальным распределением . Это глубокое обобщение теоремы Харди — Рамануджана , которая утверждает, что «среднее» значение $\omega (n)$ равно $\log \log n$ , а «среднее отклонение» не более ${\sqrt {\log \log n}}$ .

Теорема

Более формально теорема утверждает, что для любых фиксированных $a<b$ выполнено:

\lim _{x\rightarrow \infty }{\frac {1}{x}}\left|\left\{n\leq x:a\leq {\frac {\omega (n)-\log \log n}{\sqrt {\log \log n}}}\leq b\right\}\right|=\Phi (a,b)

,

где

\Phi (a,b)={\frac {1}{\sqrt {2\pi }}}\int _{a}^{b}e^{-t^{2}/2}\,dt.

.

Оригинальное доказательство

В оригинальном доказательстве утверждение о нормальности распределения в первой лемме теоремы основано на том, что функция $\omega (n)$ является аддитивной и может быть представлена как сумма индикаторов делимости на простые числа . Далее, не вводя понятие случайной величины, авторы утверждают, что слагаемые-индикаторы независимы . Затем не вдаваясь в подробности, авторы ссылаются на источник , где нормальность распределения доказывается для сумм слабозависимых случайных величин . В конце доказательства авторы извиняются за поверхностность «статистической» леммы.

В 1958 году Альфред Реньи и Пал Туран дали более точное доказательство.

Особенности

В теореме идёт речь о распределении детерминированных величин , а не о распределении вероятностей случайной величины . Но если на достаточно большом отрезке натуральных чисел выбирать случайно число $n$ , то число различных простых делителей этого числа будет иметь приблизительно нормальное распределение с математическим ожиданием и дисперсией равным среднему значению $\log \log n$ на отрезке. Поскольку эта функция, называемая повторным логарифмом, растёт медленно, то такое усреднение не будет приводить к большой ошибке даже на очень длинных отрезках. Вид распределения связывает теорему Эрдёша — Каца с центральной предельной теоремой .

Скорость роста повторного логарифма

Повторный логарифм — это чрезвычайно медленно растущая функция. В частности, числа до миллиарда содержат в разложении на простые в среднем три простых числа.

Например 1 000 000 003 = 23 × 307 × 141 623.

n	Число знаков в n	Среднее число простых чисел в разложении	среднее отклонение
1000	4	2	1,4
1 000 000 000	10	3	1,7
1 000 000 000 000 000 000 000 000	25	4	2
10 ⁶⁵	66	5	2,2
10 ⁹⁵⁶⁶	9567	10	3,2
10 ^{210 704 568}	210 704 569	20	4,5
10 ^{10 ²²}	10 ²² +1	50	7,1
10 ^{10 ⁴⁴}	10 ⁴⁴ +1	100	10
10 ^{10 ⁴³⁴}	10 ⁴³⁴ +1	1000	31,6

Если заполнить шар размером с Землю песком, потребуется около 10 ³³ песчинок. Для заполнения видимой части вселенной потребовалось бы 10 ⁹³ песчинок. Там же может поместиться 10 ¹⁸⁵ квантовых струн .

Числа такого размера — с 186 знаками — в среднем состоят лишь из 6 простых чисел в разложении.

Примечания

Paul Erdős , Mark Kac. // American Journal of Mathematics. — 1940. — Т. 62 , № 1/4 . — С. 738—742 . 17 октября 2014 года. (MR2, 42c ; Zentralblatt 24, 102
Если число $n$ делится на $m$ , то оно не делится на простое $p>{\frac {n}{m}}$ . Значит, если несколько индикаторов приняли значение 1, то остальные индикаторы равны 0. Индикаторы слабо взаимозависимы и, кроме того, имеют разные распределения.
Cf. for instance the first chapter of S. Bernstein’s paper, "Sur I’extension du theoreme limite du calcul des probabilites aux sommes de quantites dependantes", Mathematische Annalen, vol. 97, pp. 1-59.
Взаимозависимость слагаемых видимо предполагается, но не уточняется.
Кавычки авторов.