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

Теорема Эрдёша — Каца — утверждение в теории чисел, которое связывает распределение числа разных простых делителей больших чисел с формулами предельных законов теории вероятностей. Этот результат теории чисел, полученный Палом Эрдёшом и Марком Кацем в 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$ выполнено:

$\underset{x\to \mathrm{\infty }}{lim}\frac{1}{x}\left|\{n\le x:a\le \frac{\omega (n)-\log \log n}{\sqrt{\log \log n}}\le b\}\right|=\mathrm{\Phi }(a,b)$,

где

$\mathrm{\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 × Шаблон:Num.

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
1065	66	5	2,2
109566	9567	10	3,2
10210 704 568	Шаблон:Num	20	4,5
101022	1022+1	50	7,1
101044	1044+1	100	10
1010434	10434+1	1000	31,6

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

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

Ссылки

• Шаблон:MathWorld
• Timothy Gowers: The Importance of Mathematics (part 6, 4 mins in) and (part 7)