Теорема Эрдёша — Каца: различия между версиями
[отпатрулированная версия] | [непроверенная версия] |
м →Ссылки: переименование категории |
Функция «Добавить ссылку»: добавлено 3 ссылки. |
||
Строка 14: | Строка 14: | ||
== Оригинальное доказательство == |
== Оригинальное доказательство == |
||
В оригинальном доказательстве<ref>{{статья |автор= [[Эрдёш, Пол|Paul Erdős]], Mark Kac |заглавие=The Gaussian Law of Errors in the Theory of Additive Number Theoretic Functions |ссылка=http://www.renyi.hu/~p_erdos/1940-12.pdf |язык= |издание=American Journal of Mathematics |тип= |год=1940 |том=62 |номер=1/4 |страницы=738—742 |doi= |issn=}} (MR2, 42c ; Zentralblatt 24, 102</ref> утверждение о нормальности распределения в первой лемме теоремы основано на том, что функция <math>\omega(n)</math> является аддитивной и может быть представлена как сумма [[Индикатор (математика)|индикаторов]] делимости на простые числа. Далее, не вводя понятие случайной величины, авторы утверждают, что слагаемые-индикаторы независимы<ref> Если число <math>n</math> делится на <math>m</math>, то оно не делится на простое <math> p > \frac {n}{m}</math>. Значит, если несколько индикаторов приняли значение 1, то остальные индикаторы равны 0. Индикаторы слабо взаимозависимы и, кроме того, имеют разные распределения. </ref>. Затем не вдаваясь в подробности, авторы ссылаются на источник<ref> 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.</ref>, где нормальность распределения доказывается для сумм слабозависимых случайных величин<ref>Взаимозависимость слагаемых видимо предполагается, но не уточняется.</ref>. В конце доказательства авторы извиняются за поверхностность «статистической»<ref>Кавычки авторов.</ref> леммы. |
В оригинальном доказательстве<ref>{{статья |автор= [[Эрдёш, Пол|Paul Erdős]], Mark Kac |заглавие=The Gaussian Law of Errors in the Theory of Additive Number Theoretic Functions |ссылка=http://www.renyi.hu/~p_erdos/1940-12.pdf |язык= |издание=American Journal of Mathematics |тип= |год=1940 |том=62 |номер=1/4 |страницы=738—742 |doi= |issn=}} (MR2, 42c ; Zentralblatt 24, 102</ref> утверждение о нормальности распределения в первой лемме теоремы основано на том, что функция <math>\omega(n)</math> является аддитивной и может быть представлена как сумма [[Индикатор (математика)|индикаторов]] [[Делимость|делимости]] на простые числа. Далее, не вводя понятие случайной величины, авторы утверждают, что слагаемые-индикаторы независимы<ref> Если число <math>n</math> делится на <math>m</math>, то оно не делится на простое <math> p > \frac {n}{m}</math>. Значит, если несколько индикаторов приняли значение 1, то остальные индикаторы равны 0. Индикаторы слабо взаимозависимы и, кроме того, имеют разные распределения. </ref>. Затем не вдаваясь в подробности, авторы ссылаются на источник<ref> 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.</ref>, где нормальность распределения доказывается для сумм слабозависимых случайных величин<ref>Взаимозависимость слагаемых видимо предполагается, но не уточняется.</ref>. В конце доказательства авторы извиняются за поверхностность «статистической»<ref>Кавычки авторов.</ref> леммы. |
||
В [[1958 год]]у [[Реньи, Альфред|Альфред Реньи]] и [[Туран, Пал|Пал Туран]] дали более точное доказательство. |
В [[1958 год]]у [[Реньи, Альфред|Альфред Реньи]] и [[Туран, Пал|Пал Туран]] дали более точное доказательство. |
||
== Особенности == |
== Особенности == |
||
В теореме идёт речь о распределении детерминированных величин, а не о [[Распределение вероятностей|распределении вероятностей]] [[Случайная величина|случайной величины]]. Но если на достаточно большом отрезке натуральных чисел выбирать ''случайно'' число <math>n</math>, то число различных простых делителей этого числа будет иметь приблизительно нормальное распределение с математическим ожиданием и дисперсией равным среднему значению <math>\log \log n</math> на отрезке. Поскольку эта функция, называемая повторным логарифмом, растёт медленно, то такое усреднение не будет приводить к большой ошибке даже на очень длинных отрезках. Вид распределения связывает теорему Эрдёша — Каца с [[Центральная предельная теорема|центральной предельной теоремой]]. |
В теореме идёт речь о распределении детерминированных величин, а не о [[Распределение вероятностей|распределении вероятностей]] [[Случайная величина|случайной величины]]. Но если на достаточно большом отрезке [[Натуральное число|натуральных чисел]] выбирать ''случайно'' число <math>n</math>, то число различных простых делителей этого числа будет иметь приблизительно нормальное распределение с [[Математическое ожидание|математическим ожиданием]] и дисперсией равным среднему значению <math>\log \log n</math> на отрезке. Поскольку эта функция, называемая повторным логарифмом, растёт медленно, то такое усреднение не будет приводить к большой ошибке даже на очень длинных отрезках. Вид распределения связывает теорему Эрдёша — Каца с [[Центральная предельная теорема|центральной предельной теоремой]]. |
||
== Скорость роста повторного логарифма == |
== Скорость роста повторного логарифма == |
Версия от 14:42, 10 августа 2021
Теорема Эрдёша — Каца — утверждение в теории чисел, которое связывает распределение числа разных простых делителей больших чисел с формулами предельных законов теории вероятностей. Этот результат теории чисел, полученный Палом Эрдёшом и Марком Кацем в 1940 году утверждает, что если — число различных простых делителей числа , то предельное распределение величины
является стандартным нормальным распределением. Это глубокое обобщение теоремы Харди — Рамануджана, которая утверждает, что «среднее» значение равно , а «среднее отклонение» не более .
Теорема
Более формально теорема утверждает, что для любых фиксированных выполнено:
- ,
где
- .
Оригинальное доказательство
В оригинальном доказательстве[1] утверждение о нормальности распределения в первой лемме теоремы основано на том, что функция является аддитивной и может быть представлена как сумма индикаторов делимости на простые числа. Далее, не вводя понятие случайной величины, авторы утверждают, что слагаемые-индикаторы независимы[2]. Затем не вдаваясь в подробности, авторы ссылаются на источник[3], где нормальность распределения доказывается для сумм слабозависимых случайных величин[4]. В конце доказательства авторы извиняются за поверхностность «статистической»[5] леммы.
В 1958 году Альфред Реньи и Пал Туран дали более точное доказательство.
Особенности
В теореме идёт речь о распределении детерминированных величин, а не о распределении вероятностей случайной величины. Но если на достаточно большом отрезке натуральных чисел выбирать случайно число , то число различных простых делителей этого числа будет иметь приблизительно нормальное распределение с математическим ожиданием и дисперсией равным среднему значению на отрезке. Поскольку эта функция, называемая повторным логарифмом, растёт медленно, то такое усреднение не будет приводить к большой ошибке даже на очень длинных отрезках. Вид распределения связывает теорему Эрдёша — Каца с центральной предельной теоремой.
Скорость роста повторного логарифма
Повторный логарифм — это чрезвычайно медленно растущая функция. В частности, числа до миллиарда содержат в разложении на простые в среднем три простых числа.
Например 1 000 000 003 = 23 × 307 × 141 623.
n | Число знаков в n | Среднее число простых чисел в разложении | среднее отклонение |
---|---|---|---|
1000 | 4 | 2 | 1,4 |
1 000 000 000 | 10 | 3 | 1,7 |
1 000 000 000 000 000 000 000 000 | 25 | 4 | 2 |
1065 | 66 | 5 | 2,2 |
109566 | 9567 | 10 | 3,2 |
10210 704 568 | 210 704 569 | 20 | 4,5 |
101022 | 1022+1 | 50 | 7,1 |
101044 | 1044+1 | 100 | 10 |
1010434 | 10434+1 | 1000 | 31,6 |
Если заполнить шар размером с Землю песком, потребуется около 1033 песчинок. Для заполнения видимой части вселенной потребовалось бы 1093 песчинок. Там же может поместиться 10185 квантовых струн.
Числа такого размера — с 186 знаками — в среднем состоят лишь из 6 простых чисел в разложении.
Примечания
- ↑ Paul Erdős, Mark Kac. The Gaussian Law of Errors in the Theory of Additive Number Theoretic Functions // American Journal of Mathematics. — 1940. — Т. 62, № 1/4. — С. 738—742. (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.
- ↑ Взаимозависимость слагаемых видимо предполагается, но не уточняется.
- ↑ Кавычки авторов.
Ссылки
- Weisstein, Eric W. Erdős–Kac Theorem (англ.) на сайте Wolfram MathWorld.
- Timothy Gowers: The Importance of Mathematics (part 6, 4 mins in) and (part 7)