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

Основная теорема вероятностной теории чисел

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

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

— стандартное нормальное распределение . ( Это последовательность A001221 в OEIS .) Это расширение теоремы Харди–Рамануджана , которая утверждает, что нормальный порядок ω ( n ) равен log log  n с типичной ошибкой размера . ${\displaystyle \omega (n)}$ ${\displaystyle {\sqrt {\log \log n}}}$

Точное утверждение

Для любого фиксированного a  <  b ,

${\displaystyle \lim _{x\rightarrow \infty }\left({\frac {1}{x}}\cdot \#\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)}$

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

В более общем случае, если f ( n ) является строго аддитивной функцией ( ) с для всех простых p , то ${\displaystyle \scriptstyle f(p_{1}^{a_{1}}\cdots p_{k}^{a_{k}})=f(p_{1})+\cdots +f(p_{k})}$ ${\displaystyle \scriptstyle |f(p)|\leq 1}$

${\displaystyle \lim _{x\rightarrow \infty }\left({\frac {1}{x}}\cdot \#\left\{n\leq x:a\leq {\frac {f(n)-A(n)}{B(n)}}\leq b\right\}\right)=\Phi (a,b)}$

с

${\displaystyle A(n)=\sum _{p\leq n}{\frac {f(p)}{p}},\qquad B(n)={\sqrt {\sum _{p\leq n}{\frac {f(p)^{2}}{p}}}}.}$

Оригинальная эвристика Каца

Интуитивно эвристика Каца для результата гласит, что если n — случайно выбранное большое целое число, то число различных простых множителей n приблизительно нормально распределено со средним значением и дисперсией log log  n . Это происходит из того факта, что при заданном случайном натуральном числе n события «число n делится на некоторое простое число p » для каждого p взаимно независимы.

Теперь, обозначив событие «число n делится на p » через , рассмотрим следующую сумму индикаторных случайных величин: ${\displaystyle n_{p}}$

${\displaystyle I_{n_{2}}+I_{n_{3}}+I_{n_{5}}+I_{n_{7}}+\ldots }$

Эта сумма подсчитывает, сколько различных простых множителей имеет наше случайное натуральное число n . Можно показать, что эта сумма удовлетворяет условию Линдеберга , и, следовательно, центральная предельная теорема Линдеберга гарантирует, что после соответствующего масштабирования приведенное выше выражение будет гауссовым.

Фактическое доказательство теоремы, принадлежащее Эрдёшу, использует теорию решета, чтобы сделать вышеизложенную интуицию строгой.

Числовые примеры

Теорема Эрдёша–Каца означает, что для построения числа около миллиарда в среднем требуется три простых числа.

Например, 1 000 000 003 = 23 × 307 × 141623. В следующей таблице представлена ​​численная сводка роста среднего числа различных простых множителей натурального числа с увеличением . ${\displaystyle n}$ ${\displaystyle n}$

Распространяющееся гауссовское распределение различных простых чисел, иллюстрирующее теорему Эрдеша-Каца

Около 12,6% из 10 000-значных чисел состоят из 10 различных простых чисел, а около 68% — из 7–13 простых чисел.

Полая сфера размером с планету Земля, заполненная мелким песком, имела бы около 10 ³³ зерен. Объем размером с наблюдаемую вселенную имел бы около 10 ⁹³ зерен песка. В такой вселенной могло бы быть место для 10 ^{185 квантовых струн.}

Для построения чисел такой величины — 186 цифр — потребовалось бы в среднем всего 6 простых чисел.

Очень трудно, если не невозможно, обнаружить теорему Эрдеша-Каца эмпирически, поскольку гауссиана появляется только тогда, когда начинает приближаться к . Точнее, Реньи и Туран показали, что наилучшая возможная равномерная асимптотическая граница ошибки в приближении к гауссиане равна ^[1] ${\displaystyle n}$ ${\displaystyle 10^{100}}$ $${\displaystyle O\left({\frac {1}{\sqrt {\log \log n}}}\right).}$$

Ссылки

1. Реньи, А.; Туран, П. (1958). «Об одной теореме Эрдеша-Каца» (PDF) . Акта Арифметика . 4 (1): 71–84. дои : 10.4064/aa-4-1-71-84.

• Эрдёш, Пол ; Кац, Марк (1940). «Гауссовский закон ошибок в теории аддитивных числовых теоретико-функций». American Journal of Mathematics . 62 (1/4): 738–742. doi :10.2307/2371483. ISSN  0002-9327. JSTOR  2371483. Zbl  0024.10203.
• Kuo, Wentang; Liu, Yu-Ru (2008). "Теорема Эрдёша–Каца и её обобщения". В De Koninck, Jean-Marie; Granville, Andrew ; Luca, Florian (ред.). Анатомия целых чисел. На основе семинара CRM, Монреаль, Канада, 13–17 марта 2006 г. Труды и лекции CRM. Том 46. Провиденс, Род-Айленд: Американское математическое общество . стр. 209–216. ISBN 978-0-8218-4406-9. Збл  1187.11024.
• Кац, Марк (1959). Статистическая независимость в теории вероятностей, анализе и теории чисел . John Wiley and Sons, Inc.

Внешние ссылки

• Вайсштейн, Эрик В. «Теорема Эрдёша – Каца». Математический мир .
• Тимоти Гауэрс: Важность математики (часть 6, 4 мин.) и (часть 7)