Асимптотическая плотность

В теории чисел асимптотическая плотность — это одна из характеристик, помогающих оценить, насколько велико подмножество множества натуральных чисел $\mathbb{N}$.

Интуитивно мы ощущаем, что нечётных чисел «больше», чем квадратов; однако множество нечётных чисел в действительности не «больше» множества квадратов: оба множества бесконечны и счётны, и, таким образом, могут быть приведены в соответствие «один к одному» друг с другом. Очевидно, чтобы формализовать наше интуитивное понятие, нам нужен лучший способ.

Если мы случайным образом выберем число из множества $\{1,2,\ldots,n\}$, то вероятность того, что оно принадлежит A, будет равна отношению количества элементов множества $A\cap\{1,2,\ldots,n\}$ к числу n. Если эта вероятность стремится к некоторому пределу при стремлении n к бесконечности, этот предел называют асимптотической плотностью A. Мы видим, что это понятие может рассматриваться как вероятность выбора числа из множества A. Действительно, асимптотическая плотность (также, как и некоторые другие виды плотности) изучается в вероятностной теории чисел (англ. Probabilistic number theory).

Асимптотическая плотность отличается, например, от плотности последовательности. Отрицательной стороной такого подхода является то, что асимптотическая плотность не определена для всех подмножеств $\mathbb{N}$.

Определение

Подмножество A положительных чисел имеет асимптотическую плотность α, где 0 ≤ α ≤ 1, если предел отношения числа элементов A, не превосходящих n, к n при при n → ∞ существует и равен α.

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

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

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

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

Определим верхнюю асимптотическую плотность $\overline{d}(A)$ множества $A$ как

$\overline{d}(A) = \limsup_{n \rightarrow \infty} \frac{a(n)}{n}$

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

Аналогично определим $\underline{d}(A)$, нижнюю асимптотическую плотность $A$ как

$\underline{d}(A) = \liminf_{n \rightarrow \infty} \frac{ a(n) }{n}$

Будем говорить, $A$ имеет асимптотическую плотность $d(A)$, есди $\underline{d}(A)=\overline{d}(A)$. В данном случае будем полагать $d(A)=\overline{d}(A).$

Данное определение можно переформулировать:

$d(A)=\lim_{n \rightarrow \infty} \frac{a(n)}{n}$

если предел существует и конечен.

Несколько более слабое понятие плотности = верхняя плотность Банаха; возьмем $A \subseteq \mathbb{N}$, определим $d^*(A)$ как

$d^*(A) = \limsup_{N-M \rightarrow \infty} \frac{| A \bigcap \{M, M+1, ... , N\}|}{N-M+1}$

Если мы запишем подмножество $\mathbb{N}$ как возрастающую последовательность

$A=\{a_1<a_2<\ldots<a_n<\ldots; n\in\mathbb{N}\}$

то

$\underline{d}(A) = \liminf_{n \rightarrow \infty} \frac{n}{a_n},$

$\overline{d}(A) = \limsup_{n \rightarrow \infty} \frac{n}{a_n}$

и $d(A) = \lim_{n \rightarrow \infty} \frac{n}{a_n}$ если предел существует.

Примеры

• Очевидно, d($\mathbb{N}$) = 1.

• Если для некоторого множества A существует d(A), то для его дополнения имеем d(A^c) = 1 — d(A).

• Для любого конечного множества положительных чисел F имеем d(F) = 0.

• Если $A=\{n^2; n\in\mathbb{N}\}$ — множество всех квадратов, то d(A) = 0.

• Если $A=\{2n; n\in\mathbb{N}\}$ — множество всех четных чисел, тогда d(A) = ½. Аналогично, для любой арифметической прогрессии $A=\{an+b; n\in\mathbb{N}\}$ получаем d(A) = 1/a.

• Для множества P всех простых чисел мы получаем d(P) = 0 (см. Теорема о распределении простых чисел).

• Множество всех бесквадратных чисел имеет плотность $\tfrac{6}{\pi^2}$

• Плотность множества избыточных чисел находится между 0.2474 и 0.2480.

• Множество $A=\bigcup\limits_{n=0}^\infty \{2^{2n},\ldots,2^{2n+1}-1\}$ чисел, чье двоичное представление содержит четное число цифр, — пример множества, не обладающего асимптотической плотностью, так как верхняя плотность равна

$\overline d(A)=\lim_{m \rightarrow \infty} \frac{1+2^2+\cdots +2^{2m}}{2^{2m+1}-1} = \lim_{m \rightarrow \infty} \frac{2^{2m+2}-1}{3(2^{2m+1}-1)} = \frac 23\, ,$

в то время, как нижняя

$\underline d(A)=\lim_{m \rightarrow \infty} \frac{1+2^2+\cdots +2^{2m}}{2^{2m+2}-1} = \lim_{m \rightarrow \infty} \frac{2^{2m+2}-1}{3(2^{2m+2}-1)} = \frac 13\, .$

Ссылки