WikiSort.ru - Не сортированное

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

${\displaystyle {\frac {\omega (n)-\log \log n}{\sqrt {\log \log n}}}}$

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

Теорема

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

${\displaystyle \lim _{x\rightarrow \infty }{\frac {1}{x}}\left|\left\{n\leq x:a\leq {\frac {\omega (n)-\log \log n}{\sqrt {\log \log n}}}\leq b\right\}\right|=\Phi (a,b)}$ ,

где

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

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

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

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

Особенности

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

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

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

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

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

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

Примечания

Ссылки

• Weisstein, Eric W. Erdős–Kac Theorem (англ.) на сайте Wolfram MathWorld.
• Timothy Gowers: The Importance of Mathematics (part 6, 4 mins in) and (part 7)