В теории чисел , то теорема Эрдеша-Кац , названная в честь Пола Эрдеша и Марка Каца , а также известный как основная теорема вероятностной теории чисел , утверждает , что если ω ( п ) является числом различных простых делителей из п (последовательность A001221 в OEIS ), то, грубо говоря, на распределение вероятностей из
- стандартное нормальное распределение . Это расширение теоремы Харди – Рамануджана , которая утверждает, что нормальный порядок ω ( n ) равен log log n с типичной ошибкой размера.
Точное заявление
При любом фиксированном а < Ь ,
где нормальное (или «гауссово») распределение, определяемое как
В более общем смысле, если f ( n ) - сильно аддитивная функция () с участием для всех простых p , то
с участием
Оригинальная эвристика Каца
Интуитивно эвристика Каца для результата говорит, что если n - случайно выбранное большое целое число, то количество различных простых множителей n приблизительно нормально распределено со средним значением и логарифмом дисперсии log n . Это происходит из-за того, что для случайного натурального числа n события «число n делится на некоторое простое число p » для каждого p взаимно независимы.
Теперь, обозначив событие «число n делится на p » на, рассмотрим следующую сумму индикаторных случайных величин:
Эта сумма подсчитывает, сколько различных простых делителей имеет случайное натуральное число n . Можно показать, что эта сумма удовлетворяет условию Линдеберга , и поэтому центральная предельная теорема Линдеберга гарантирует, что после соответствующего изменения масштаба приведенное выше выражение будет гауссовым.
Фактическое доказательство теоремы, принадлежащее Эрдешу, использует теорию решет, чтобы сделать приведенную выше интуицию точной.
Числовые примеры
Теорема Эрдеша – Каца означает, что для построения числа около миллиарда требуется в среднем три простых числа.
Например, 1 000 000 003 = 23 × 307 × 14 1623. В следующей таблице представлены числовые сводные данные о росте среднего числа различных простых множителей натурального числа. с увеличением .
п | Количество цифры в 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 65 | 66 | 5 | 2.2 |
10 9 566 | 9 567 | 10 | 3,2 |
10 210 704 568 | 210 704 569 | 20 | 4.5 |
10 10 22 | 10 22 +1 | 50 | 7.1 |
10 10 44 | 10 44 +1 | 100 | 10 |
10 10 434 | 10 434 +1 | 1000 | 31,6 |
Около 12,6% из 10 000 цифр состоят из 10 различных простых чисел, а около 68% состоят из от 7 до 13 простых чисел.
Полая сфера размером с планету Земля, заполненная мелким песком, будет иметь около 10 33 зерен. Объем размером с наблюдаемую Вселенную будет содержать около 10 93 песчинок. В такой вселенной может быть место для 10 185 квантовых струн.
Числа такой величины - с 186 цифрами - потребуют в среднем только 6 простых чисел для построения.
Очень трудно, если не невозможно, эмпирически открыть теорему Эрдеша-Каца, поскольку гауссиан появляется только тогда, когда начинает быть рядом . Точнее, Реньи и Туран показали, что наилучшая возможная равномерная асимптотическая оценка ошибки приближения к гауссиану есть. [1]
Рекомендации
- ^ Реньи, А .; Туран, П. (1958). «Об одной теореме Эрдеша-Каца» (PDF) . Acta Arithmetica . 4 (1): 71–84.
- Эрдеш, Пол ; Кац, Марк (1940). «Гауссов закон ошибок в теории аддитивных функций теории чисел». Американский журнал математики . 62 (1/4): 738–742. DOI : 10.2307 / 2371483 . ISSN 0002-9327 . Zbl 0024.10203 .
- Куо, Вентан; Лю, Ю-Ру (2008). «Теорема Эрдеша – Каца и ее обобщения». В Де Конинк, Жан-Мари; Гранвиль, Эндрю ; Лука, Флориан (ред.). Анатомия целых чисел. На основе семинара CRM, Монреаль, Канада, март 13--17, 2006 . CRM Proceedings and Lecture Notes. 46 . Провиденс, Род-Айленд: Американское математическое общество . С. 209–216. ISBN 978-0-8218-4406-9. Zbl 1187.11024 .
- Кац, Марк (1959). Статистическая независимость в теории вероятностей, анализа и чисел . John Wiley and Sons, Inc.