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

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

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

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

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

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

\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)

где $\Phi (a,b)$ - это нормальное (или «гауссово») распределение, определяемое как

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

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

\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)

с

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 n . Это происходит из-за того, что для случайного натурального числа n события «число n делится на некоторое простое число p » для каждого p взаимно независимы.

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

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

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

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

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

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

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

н	Количество цифры в н	Среднее количество различных простых чисел	Стандартный отклонение
1,000	4	2	1.4
1,000,000,000	10	3	1.7
1,000,000,000,000,000,000,000,000	25	4	2
10 ⁶⁵	66	5	2.2
10 ^9,566	9,567	10	3.2
10 ^210,704,568	210,704,569	20	4.5
10 ^{10 ²²}	10 ²² + 1	50	7.1
10 ^{10 ⁴⁴}	10 ⁴⁴ + 1	100	10
10 ^{10 ⁴³⁴}	10 ⁴³⁴ + 1	1000	31.6

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

Полая сфера размером с планету Земля, наполненная мелким песком, имела бы около 10 ³³ зерна. Объем размером с наблюдаемую Вселенную имел бы около 10 ⁹³ песчинки. Там может быть место для 10 ¹⁸⁵ квантовые струны в такой вселенной.

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

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

Ссылки

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

Эрдеш, Пол ; Кац, Марк (1940). «Гауссов закон ошибок в теории аддитивных теоретико-числовых функций». Американский журнал математики . 62 (1/4): 738–742. дои : 10.2307/2371483 . ISSN 0002-9327 . JSTOR 2371483 . Збл 0024.10203 .
Го, Вэньтан; Лю, Ю-Ру (2008). «Теорема Эрдеша – Каца и ее обобщения». В Де Конинке, Жан-Мари; Гранвилл, Эндрю ; Лука, Флориан (ред.). Анатомия целых чисел. По материалам семинара по CRM, Монреаль, Канада, 13–17 марта 2006 г. Материалы CRM и конспекты лекций. Том. 46. Провиденс, Род-Айленд: Американское математическое общество . стр. 209–216. ISBN 978-0-8218-4406-9 . Збл 1187.11024 .
Кац, Марк (1959). Статистическая независимость в теории вероятностей, анализе и теории чисел . Джон Уайли и сыновья, Inc.

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

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

[ 1 ]