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

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

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

Теорема

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

,

где

.

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

В оригинальном доказательстве[1] утверждение о нормальности распределения в первой лемме теоремы основано на том, что функция является аддитивной и может быть представлена как сумма индикаторов делимости на простые числа. Далее, не вводя понятие случайной величины, авторы утверждают, что слагаемые-индикаторы независимы[2]. Затем не вдаваясь в подробности, авторы ссылаются на источник[3], где нормальность распределения доказывается для сумм слабозависимых случайных величин[4]. В конце доказательства авторы извиняются за поверхностность «статистической»[5] леммы.

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

Особенности

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

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

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

Например 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
1065 66 5 2,2
109566 9567 10 3,2
10210 704 568 210 704 569 20 4,5
101022 1022+1 50 7,1
101044 1044+1 100 10
1010434 10434+1 1000 31,6

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

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

Примечания
  1. Paul Erdős, Mark Kac. The Gaussian Law of Errors in the Theory of Additive Number Theoretic Functions // American Journal of Mathematics. — 1940. — Т. 62, № 1/4. — С. 738—742. (MR2, 42c ; Zentralblatt 24, 102
  2. Если число делится на , то оно не делится на простое . Значит, если несколько индикаторов приняли значение 1, то остальные индикаторы равны 0. Индикаторы слабо взаимозависимы и, кроме того, имеют разные распределения.
  3. 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.
  4. Взаимозависимость слагаемых видимо предполагается, но не уточняется.
  5. Кавычки авторов.

Ссылки
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.