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

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

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

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

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

Определение

Подмножество [math]\displaystyle{ A }[/math] положительных чисел имеет асимптотическую плотность [math]\displaystyle{ \alpha }[/math], где [math]\displaystyle{ 0 \leqslant \alpha \leqslant 1 }[/math], если предел отношения числа элементов [math]\displaystyle{ A }[/math], не превосходящих [math]\displaystyle{ n }[/math], к [math]\displaystyle{ n }[/math] при [math]\displaystyle{ n \to \infty }[/math] существует и равен [math]\displaystyle{ \alpha }[/math].

Более строго, если мы определим для любого натурального числа [math]\displaystyle{ n }[/math] подсчитывающую функцию [math]\displaystyle{ a (n) }[/math] как число элементов [math]\displaystyle{ A }[/math], не превосходящих [math]\displaystyle{ n }[/math], то равенство асимптотической плотности множества [math]\displaystyle{ A }[/math] числу [math]\displaystyle{ \alpha }[/math] в точности означает, что

[math]\displaystyle{ \lim\limits_{n \to +\infty}{\frac{a(n)}{n}} = \alpha }[/math].

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

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

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

[math]\displaystyle{ \overline{d}(A) = \limsup_{n \rightarrow \infty} \frac{a(n)}{n} }[/math]

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

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

[math]\displaystyle{ \underline{d}(A) = \liminf_{n \rightarrow \infty} \frac{ a(n) }{n} }[/math]

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

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

[math]\displaystyle{ d(A)=\lim_{n \rightarrow \infty} \frac{a(n)}{n} }[/math]

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

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

[math]\displaystyle{ d^*(A) = \limsup_{N-M \rightarrow \infty} \frac{| A \bigcap \{M, M+1, ... , N\}|}{N-M+1} }[/math]

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

[math]\displaystyle{ A=\{a_1\lt a_2\lt \ldots\lt a_n\lt \ldots; n\in\mathbb{N}\} }[/math]

то

[math]\displaystyle{ \underline{d}(A) = \liminf_{n \rightarrow \infty} \frac{n}{a_n}, }[/math]

[math]\displaystyle{ \overline{d}(A) = \limsup_{n \rightarrow \infty} \frac{n}{a_n} }[/math]

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

Примеры

• Очевидно, d([math]\displaystyle{ \mathbb{N} }[/math]) = 1.

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

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

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

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

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

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

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

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

[math]\displaystyle{ \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\, , }[/math]

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

[math]\displaystyle{ \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\, . }[/math]