Асимптотическая плотность (Gvnbhmkmncyvtgx hlkmukvm,)

В теории чисел асимптотическая плотность — это одна из характеристик, помогающих оценить, насколько велико подмножество множества натуральных чисел $\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\}$ чисел, чьё двоичное представление содержит нечетное число цифр, — пример множества, не обладающего асимптотической плотностью, так как верхняя плотность равна