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

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

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

Теорема


 Более формально теорема утверждает, что для любых фиксированных $a
limx1x|{nx:aω(n)loglognloglognb}|=Φ(a,b),
 где

Φ(a,b)=12πabet2/2dt..

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


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

Особенности


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

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


 Повторный логарифм — это чрезвычайно медленно растущая функция. Вчастности, числа до миллиарда содержат в разложении на простые в среднемтри простых числа.
 Например 1 000 000 003 = 23 × 307 × .
nЧисло знаков в nСреднее число простых чисел вразложениисреднее отклонение
1000421,4
1 000 000 0001031,7
1 000 000 000 000 000 000 000 0002542
10656652,2
1095669567103,2
10210 704 568204,5
1010\textsuperscript221022+1507,1
1010\textsuperscript441044+110010
1010\textsuperscript43410434+1100031,6

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