Естественная плотность

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

В теории чисел, естественная плотность (также называемая асимптотической плотность или арифметическая плотность ) - это один из методов измерения того, насколько «большим» является подмножество из набора из натуральных чисел. Он в основном полагается на вероятность встретить элементы желаемого подмножества при прочесывании через интервал [1, n] по мере того, как n становится большим.

Интуитивно кажется, что существует больше натуральных чисел, чем полных квадратов, поскольку каждый полный квадрат уже положителен, а кроме того существует множество других положительных целых чисел. Однако набор положительных целых чисел на самом деле не больше, чем набор полных квадратов: оба набора являются бесконечными и счетными и поэтому могут быть помещены в однозначно. одна корреспонденция. Тем не менее, если рассматривать натуральные числа, квадратов становится все меньше. Понятие естественной плотности делает эту интуицию точной для многих, но не всех, подмножеств натуральных значений (см. плотность Шнирельмана, которая аналогична естественной плотности, но определена для всех подмножеств N {\ displaystyle \ mathbb {N}}\ mathbb {N} ).

Если целое число случайно выбрано из интервала [1, n], то вероятность того, что оно принадлежит A, является отношением количества элементов A в [1, n] к общему количеству элементы в [1, n]. Если эта вероятность стремится к некоторому пределу, когда n стремится к бесконечности, то этот предел называется асимптотической плотностью A. Это понятие можно понимать как своего рода вероятность выбора числа из множества A. Действительно, асимптотическая плотность (как и некоторые другие типы плотностей) изучается в вероятностной теории чисел.

Содержание

  • 1 Определение
    • 1.1 Верхняя и нижняя асимптотическая плотность
  • 2 Свойства и примеры
  • 3 Другие функции плотности
  • 4 Примечания
  • 5 См. Также
  • 6 Ссылки

Определение

Подмножество A положительных целых чисел имеет естественную плотность α, если пропорция элементов A среди всех натуральных чисел от 1 до n сходится к α, когда n стремится к бесконечности.

Более точно, если определить для любого натурального числа n счетную функцию a (n) как количество элементов A, меньшее или равное n, тогда естественная плотность A равенство α в точности означает, что

a (n) / n → α при n → ∞.

Из определения следует, что если множество A имеет естественную плотность α, то 0 ≤ α ≤ 1.

Верхняя и нижняя асимптотическая плотность

Пусть A {\ displaystyle A}A будет подмножеством множества натуральных чисел N = {1, 2,…}. {\ displaystyle \ mathbb {N} = \ {1,2, \ ldots \}.}\mathbb{N}=\{1,2,\ldots\}.Для любого n ∈ N {\ displaystyle n \ in \ mathbb {N}}п \ in \ mathbb {N} положим A (n) = {1, 2,…, n} ∩ A. {\ displaystyle A (n) = \ {1,2, \ ldots, n \} \ cap A.}A (n) = \ {1,2, \ ldots, n \} \ cap A. и a (n) = | A (n) | {\ displaystyle a (n) = | A (n) |}a (n) = | A (n) | .

Определите верхнюю асимптотическую плотность (также называемую «верхней плотностью») d ¯ (A) {\ displaystyle {\ overline {d}} (A)}\ overline {d} (A) из A {\ displaystyle A}A по

d ¯ (A) = lim sup n → ∞ a (n) n {\ displaystyle { \ overline {d}} (A) = \ limsup _ {n \ rightarrow \ infty} {\ frac {a (n)} {n}}}\ overline {d} (A) = \ limsup_ {n \ rightarrow \ infty} \ frac {a (n) } {n}

где lim sup - верхний предел. d ¯ (A) {\ displaystyle {\ overline {d}} (A)}\ overline {d} (A) также известен как верхняя плотность A. {\ displaystyle A.}A.

Аналогично, d _ (A) {\ displaystyle {\ underline {d}} (A)}\ underline {d} (A) , нижняя асимптотическая плотность (также называемая "нижней плотность ") из A {\ displaystyle A}A , определяется как

d _ (A) = lim inf n → ∞ a (n) n {\ displaystyle {\ underline {d }} (A) = \ liminf _ {n \ rightarrow \ infty} {\ frac {a (n)} {n}}}\ underline {d} (A) = \ liminf_ {n \ rightarrow \ infty } \ frac {a (n)} {n}

где lim inf - нижний предел. Можно сказать, что A {\ displaystyle A}A имеет асимптотическую плотность d (A) {\ displaystyle d (A)}d (A) , если d _ (A) = d ¯ (A) {\ displaystyle {\ underline {d}} (A) = {\ overline {d}} (A)}\ underline {d} (A) = \ overline {d} (A) , в этом случае d (A) { \ displaystyle d (A)}d (A) равно этому общему значению.

Это определение можно переформулировать следующим образом:

d (A) = lim n → ∞ a (n) n {\ displaystyle d (A) = \ lim _ {n \ rightarrow \ infty } {\ frac {a (n)} {n}}}d (A) = \ lim_ {n \ rightarrow \ infty} \ frac {a (n)} {n}

, если этот предел существует.

Можно доказать, что определения подразумевают, что также выполняется следующее. Если бы можно было записать подмножество N {\ displaystyle \ mathbb {N}}\ mathbb {N} как возрастающую последовательность, проиндексированную натуральными числами

A = {a 1 < a 2 < … } {\displaystyle A=\{a_{1}{\ displaystyle A = \ {a_ {1} <a_ {2} <\ ldots \}}

, то

d _ (A) = lim inf n → ∞ nan, {\ displaystyle {\ underline {d}} (A) = \ liminf _ {n \ rightarrow \ infty} {\ frac {n} {a_ {n}} },}\ underline {d} (A) = \ liminf_ {n \ rightarrow \ infty} \ frac {n} {a_n},
d ¯ (A) = lim sup n → ∞ nan {\ displaystyle {\ overline {d}} (A) = \ limsup _ {n \ rightarrow \ infty} {\ frac {n} {a_ {n}}}}\ overline {d} (A) = \ limsup_ {n \ rightarrow \ infty} \ frac {n} {a_n}

и d (A) = lim n → ∞ nan {\ displaystyle d (A) = \ lim _ {n \ rightarrow \ infty} {\ frac {n} {a_ { n}}}}d (A) = \ lim_ {n \ rightarrow \ infty} \ frac {n} {a_n} , если ограничение существует.

Несколько более слабым понятием плотности является верхняя банахова плотность; для данного набора A ⊆ N {\ displaystyle A \ substeq \ mathbb {N}}A \ Substeq \ mathbb {N} , определить d ∗ (A) {\ displaystyle d ^ {*} (A)}d ^ * (A) при

d ∗ (A) = lim sup N - M → ∞ | A ∩ {M, M + 1,…, N} | N - M + 1 {\ displaystyle d ^ {*} (A) = \ limsup _ {NM \ rightarrow \ infty} {\ frac {| A \ cap \ {M, M + 1, \ ldots, N \} | } {N-M + 1}}}{\ displaystyle d ^ {* } (A) = \ limsup _ {NM \ rightarrow \ infty} {\ frac {| A \ cap \ {M, M + 1, \ ldots, N \} |} {N-M + 1}}}

Свойства и примеры

макс {d (A), d (B)} ≤ d (A ∪ B) ≤ min {d (A) + d (B), 1}. {\ displaystyle \ max \ {d (A), d (B) \} \ leq d (A \ cup B) \ leq \ min \ {d (A) + d (B), 1 \}.}{\ displaystyle \ max \ {d (A), d (B) \} \ leq d (A \ cup B) \ Leq \ min \ {d (A) + d (B), 1 \}.}
  • Если A = {n 2: n ∈ N} {\ displaystyle A = \ {n ^ { 2}: n \ in \ mathbb {N} \}}{\ displaystyle A = \ {n ^ {2}: n \ in \ mathbb {N} \}} - это множество всех квадратов, тогда d (A) = 0.
  • Если A = {2 n: n ∈ N} {\ displaystyle A = \ {2n: n \ in \ mathbb {N} \}}{\ displaystyle A = \ {2n: n \ in \ mathbb {N} \}} - это набор всех четных чисел, тогда d (A) = 0,5. Точно так же для любой арифметической прогрессии A = {an + b: n ∈ N} {\ displaystyle A = \ {an + b: n \ in \ mathbb {N} \}}{\ displaystyle A = \ {an + b: n \ in \ mathbb {N} \}} мы получаем d (A) = 1 а. {\ displaystyle d (A) = {\ tfrac {1} {a}}.}{\ displaystyle d (A) = {\ tfrac {1} {a}}.}
  • Набор всех целых чисел без квадратов имеет плотность 6 π 2. {\ displaystyle {\ tfrac {6} {\ pi ^ {2}}}.}{\ tfrac {6} {\ pi ^ {2}}}. В общем, множество всех n-степенных чисел для любого натурального n имеет плотность 1 ζ (n), {\ displaystyle {\ tfrac {1} {\ zeta (n)}},}{\ displaystyle {\ tfrac {1} {\ zeta (n)}},} где ζ (n) {\ displaystyle \ zeta (n)}\ zeta (n) - это дзета-функция Римана..
  • Набор избыточных чисел имеет ненулевую плотность. В 1998 году Марк Делеглиз показал, что плотность множества обильных и совершенных чисел составляет от 0,2474 до 0,2480.
  • Множество
A = ⋃ n = 0 ∞ {2 2 n,…, 2 2 n + 1 - 1} {\ displaystyle A = \ bigcup _ {n = 0} ^ {\ infty} \ left \ {2 ^ {2n}, \ ldots, 2 ^ {2n + 1} -1 \ right \}}{\ displaystyle A = \ bigcup _ {n = 0} ^ {\ infty} \ left \ {2 ^ {2n}, \ ldots, 2 ^ {2n + 1} -1 \ right \} }
чисел, двоичное расширение которых содержит нечетное количество цифр, является примером набора, не имеющего асимптотической плотности, поскольку верхняя плотность этого набора равна
d ¯ (A) = lim m → ∞ 1 + 2 2 + ⋯ + 2 2 м 2 2 m + 1 - 1 = lim m → ∞ 2 2 m + 2 - 1 3 (2 2 m + 1 - 1) = 2 3, {\ displaystyle {\ overline {d}} (A) = \ lim _ {m \ to \ infty} {\ frac {1 + 2 ^ {2} + \ cdots + 2 ^ {2m}} {2 ^ {2m + 1} -1}} = \ lim _ {m \ to \ infty} {\ frac {2 ^ {2m + 2} -1} {3 (2 ^ {2m + 1} -1)}} = {\ frac {2} {3}},}{\ displaystyle {\ overline {d}} (A) = \ lim _ {m \ to \ infty} {\ frac {1 + 2 ^ {2} + \ cdots + 2 ^ {2m}} {2 ^ {2m + 1} -1}} = \ lim _ {m \ to \ infty } {\ frac {2 ^ {2m + 2} -1} {3 (2 ^ {2m + 1} -1)}} = {\ frac {2} {3}},}
, тогда как его более низкая плотность равна
d _ (A) = lim m → ∞ 1 + 2 2 + ⋯ + 2 2 m 2 2 m + 2 - 1 = lim m → ∞ 2 2 m + 2 - 1 3 (2 2 м + 2 - 1) = 1 3. {\ displaystyle {\ underline {d}} (A) = \ lim _ {m \ to \ infty} {\ frac {1 + 2 ^ {2} + \ cdots + 2 ^ {2m}} {2 ^ {2m +2} -1}} = \ lim _ {m \ to \ infty} {\ frac {2 ^ {2m + 2} -1} {3 (2 ^ {2m + 2} -1)}} = {\ frac {1} {3}}.}{\ displaystyle {\ underline {d}} (A) = \ lim _ {m \ to \ infty} {\ frac {1 + 2 ^ {2} + \ cdots + 2 ^ {2m}} {2 ^ {2m + 2} -1}} = \ lim _ {m \ to \ infty} {\ frac {2 ^ {2m + 2} -1} {3 (2 ^ {2m + 2} -1)}} = {\ frac {1} {3}}.}
A x: = {n ∈ N: α n < x }. {\displaystyle A_{x}:=\{n\in \mathbb {N} :\alpha _{n}{\ displaystyle A_ {x}: = \ {n \ in \ mathbb {N}: \ alpha _ {n} <x \}.}
Тогда по определению d (A x) = x {\ displaystyle d (A_ {x}) = x}d (A_x) = x для всех x {\ displaystyle x}x .

Другие функции плотности

Другие функции плотности на подмножествах натуральных чисел могут быть определены аналогично. Например, логарифмическая плотность набора A определяется как предел (если он существует)

δ (A) = lim x → ∞ 1 журнал ⁡ x ∑ n ∈ A, n ≤ x 1 n. {\ displaystyle \ mathbf {\ delta} (A) = \ lim _ {x \ rightarrow \ infty} {\ frac {1} {\ log x}} \ sum _ {n \ in A, n \ leq x} {\ frac { 1} {n}} \.}\ mathbf {\ delta} (A) = \ lim_ {x \ rightarrow \ infty} \ frac {1} {\ log x} \ sum_ {n \ in A, n \ le x} \ frac {1} {n} \.

Аналогично определяются верхняя и нижняя логарифмические плотности.

Для множества кратных целочисленной последовательности теорема Дэвенпорта – Эрдеша утверждает, что естественная плотность и логарифмическая плотность равны.

Примечания

См. Также

Ссылки

Эта статья включает материал из Asymptotic density на PlanetMath, который находится под лицензией Creative Commons Attribution / Share-Alike License.

Последняя правка сделана 2021-05-31 12:34:56
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте