Теорема Эрдёша — Каца — утверждение в теории чисел, которое связывает распределение числа разных простых делителей больших чисел с формулами предельных законов теории вероятностей. Этот результат теории чисел, полученный Палом Эрдёшом и Марком Кацем в 1940 году утверждает, что если — число различных простых делителей числа , то предельное распределение величины
является стандартным нормальным распределением. Это глубокое обобщение теоремы Харди — Рамануджана, которая утверждает, что «среднее» значение равно , а «среднее отклонение» не более .
Теорема Более формально теорема утверждает, что для любых фиксированных выполнено:
,
где .
Оригинальное доказательство В оригинальном доказательстве (MR2, 42c ; Zentralblatt 24, 102 утверждение о нормальности распределения в первой лемме теоремы основано на том, что функция является аддитивной и может быть представлена как сумма индикаторов делимости на простые числа. Далее, не вводя понятие случайной величины, авторы утверждают, что слагаемые-индикаторы независимы Если число делится на , то оно не делится на простое . Значит, если несколько индикаторов приняли значение 1, то остальные индикаторы равны 0. Индикаторы слабо взаимозависимы и, кроме того, имеют разные распределения. . Затем не вдаваясь в подробности, авторы ссылаются на источник 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. 1-59., где нормальность распределения доказывается для сумм слабозависимых случайных величинВзаимозависимость слагаемых видимо предполагается, но не уточняется.. В конце доказательства авторы извиняются за поверхностность «статистической»Кавычки авторов. леммы.
В 1958 году Альфред Реньи и Пал Туран дали более точное доказательство.
Особенности В теореме идёт речь о распределении детерминированных величин, а не о распределении вероятностей случайной величины. Но если на достаточно большом отрезке натуральных чисел выбирать случайно число , то число различных простых делителей этого числа будет иметь приблизительно нормальное распределение с математическим ожиданием и дисперсией равным среднему значению на отрезке. Поскольку эта функция, называемая повторным логарифмом, растёт медленно, то такое усреднение не будет приводить к большой ошибке даже на очень длинных отрезках. Вид распределения связывает теорему Эрдёша — Каца с центральной предельной теоремой.
Скорость роста повторного логарифма Повторный логарифм — это чрезвычайно медленно растущая функция. В частности, числа до миллиарда содержат в разложении на простые в среднем три простых числа.
Например 1 000 000 003 = 23 × 307 × .
nЧисло знаков в n Среднее число простых чисел в разложении среднее отклонение1000421,41 000 000 0001031,71 000 000 000 000 000 000 000 000254210656652,21095669567103,210210 704 568204,51010221022+1507,11010441044+110010101043410434+1100031,6
Если заполнить шар размером с Землю песком, потребуется около 1033 песчинок. Для заполнения видимой части вселенной потребовалось бы 1093 песчинок. Там же может поместиться 10185 квантовых струн.
Числа такого размера — с 186 знаками — в среднем состоят лишь из 6 простых чисел в разложении.
Примечания
Ссылки
Timothy Gowers: The Importance of Mathematics (part 6, 4 mins in) and (part 7)
Категория:Теория чисел Категория:Непрерывные распределения Категория:Теоремы о простых числах Категория:Пал Эрдёш