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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Теорема Эрдёша — Каца — утверждение в теории чисел, которое связывает распределение числа разных простых делителей больших чисел с формулами предельных законов теории вероятностей. Этот результат теории чисел, полученный Палом Эрдёшом и Марком Кацем[uk] в 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 \le \frac{\omega(n) - \log \log n}{\sqrt{\log \log n}} \le b \right\} \right | = \Phi(a,b)

где

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

Оригинальное доказательство[править | править вики-текст]

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

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

Особенности[править | править вики-текст]

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

Скорость роста повторного логарифма[править | править вики-текст]

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

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

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 210704569 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, volume 62, No. 1/4, (1940), pages 738—742, http://www.renyi.hu/~p_erdos/1940-12.pdf (MR2, 42c ; Zentralblatt 24, 102
  2. Если число n делится на m, то оно не делится на простое  p > \frac {n}{m}. Значит, если несколько индикаторов приняли значение 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. l-59.
  4. Взаимозависимость слагаемых видимо предполагается, но не уточняется.
  5. Кавычки авторов.

Ссылки[править | править вики-текст]