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

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

ω ( n ) − log ⁡ log ⁡ n log ⁡ log ⁡ n {displaystyle {frac {omega (n)-log log n}{sqrt {log log n}}}}

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

Теорема

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

lim x → ∞ 1 x | { n ≤ x : a ≤ ω ( n ) − log ⁡ log ⁡ n log ⁡ log ⁡ n ≤ b } | = Φ ( a , b ) {displaystyle lim _{x ightarrow infty }{frac {1}{x}}left|left{nleq x:aleq {frac {omega (n)-log log n}{sqrt {log log n}}}leq b ight} ight|=Phi (a,b)} ,

где

Φ ( a , b ) = 1 2 π ∫ a b e − t 2 / 2 d t . {displaystyle Phi (a,b)={frac {1}{sqrt {2pi }}}int _{a}^{b}e^{-t^{2}/2},dt.} .

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

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

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

Особенности

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

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

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

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

Если заполнить шар размером с Землю песком, потребуется около 1033 песчинок. Для заполнения видимой части вселенной потребовалось бы 1093 песчинок. Там же может поместиться 10185 квантовых струн.

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