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

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

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

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

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

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

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

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

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

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

${\displaystyle {\overline {d}}(A)=\limsup _{n\rightarrow \infty }{\frac {a(n)}{n}}}$

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

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

${\displaystyle {\underline {d}}(A)=\liminf _{n\rightarrow \infty }{\frac {a(n)}{n}}}$

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

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

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

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

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

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

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

${\displaystyle A=\{a_{1}<a_{2}<\ldots <a_{n}<\ldots ;n\in \mathbb {N} \}}$

то

${\displaystyle {\underline {d}}(A)=\liminf _{n\rightarrow \infty }{\frac {n}{a_{n}}},}$

${\displaystyle {\overline {d}}(A)=\limsup _{n\rightarrow \infty }{\frac {n}{a_{n}}}}$

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

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

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

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

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

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

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

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

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

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

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

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

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