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

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

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

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

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

Определение

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

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

$\lim \limits _{n\to +\infty }{\frac {a(n)}{n}}=\alpha$.

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

Пусть $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 {2}{3}}\,,$

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

${\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 {1}{3}}\,.$