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

редактировать

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

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

\ frac {\ omega (n) - \ журнал \ журнал n} {\ sqrt {\ журнал \ журнал n}}

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

Содержание

1 Точное утверждение
2 Исходная эвристика Каца
3 Числовые примеры
4 Ссылки
5 Внешние links

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

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

lim x → ∞ (1 x ⋅ # {n ≤ x: a ≤ ω (n) - log ⁡ log ⁡ n log ⁡ log ⁡ n ≤ b}) знак равно Φ (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)}

\ lim_ { x \ rightarrow \ infty} \ left (\ frac {1} {x} \ cdot \ # \ left \ {n \ leq x: a \ le \ frac {\ omega (n) - \ log \ log n} {\ sqrt {\ log \ log n}} \ le b \ right \} \ right) = \ Phi (a, b)

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

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

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

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

lim x → ∞ (1 x ⋅ # {n ≤ x: a ≤ f ( п) - A (N) B (N) ≤ b}) знак равно Φ (a, b) {\ 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)}

\ 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) = ∑ p ≤ nf (p) p, B (n) = ∑ p ≤ nf (p) 2 p. {\ Displaystyle А (п) = \ сумма _ {п \ Leq N} {\ гидроразрыва {е (р)} {р}}, \ qquad B (п) = {\ sqrt {\ сумма _ {р \ Leq п } {\ frac {f (p) ^ {2}} {p}}}}.}

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» на $np {\ displaystyle n_ {p}}$ $n_{{p}}$ , рассмотрим следующую сумму случайных величин индикатора:

I n 2 + I n 3 + I n 5 + I n 7 +… {\ displaystyle I_ {n_ {2}} + I_ {n_ {3}} + I_ {n_ {5}} + I_ {n_ { 7}} + \ ldots}

I _ {{n _ {{2}}}} + I _ {{n_ {{3}}}} + I _ {{n _ {{5}}}} + I _ {{n _ {{7}}}} + \ ldots

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

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

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

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

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

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
10	66	5	2,2
10	9,567	10	3,2
10	210,704,569	20	4,5
10	10 + 1	50	7,1
10	10 + 1	100	10
10	10 + 1	1000	31,6

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

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

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

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

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

Ссылки