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

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

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

Если мы случайным образом выберем число из множества $\{1,2,\dots ,n\}$, то вероятность того, что оно принадлежит A, будет равна отношению количества элементов множества $A\cap \{1,2,\dots ,n\}$ к числу n. Если эта вероятность стремится к некоторому пределу при стремлении n к бесконечности, этот предел называют асимптотической плотностью A. Мы видим, что это понятие может рассматриваться как вероятность выбора числа из множества A. Действительно, асимптотическая плотность (также, как и некоторые другие виды плотности) изучается в Шаблон:Iw (Шаблон:Lang-en).

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

Определение

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

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

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

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

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

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

$\bar{d}(A)=\underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}\frac{a(n)}{n}$

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

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

$\underset{\_}{d}(A)=\underset{n\to \mathrm{\infty }}{\mathrm{lim\; inf}}\frac{a(n)}{n}$

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

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

$d(A)=\underset{n\to \mathrm{\infty }}{\lim }\frac{a(n)}{n}$

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

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

$d^{*}(A)=\underset{N-M\to \mathrm{\infty }}{\mathrm{lim\; sup}}\frac{|A\bigcap \{M,M+1,...,N\}|}{N-M+1}$

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

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

то

$\underset{\_}{d}(A)=\underset{n\to \mathrm{\infty }}{\mathrm{lim\; inf}}\frac{n}{a_n},$

$\bar{d}(A)=\underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}\frac{n}{a_n}$

и $d(A)=\underset{n\to \mathrm{\infty }}{\lim }\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 (см. Теорема о распределении простых чисел).

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

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

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

$\bar{d}(A)=\underset{m\to \mathrm{\infty }}{\lim }\frac{1+2^2+\cdots +2^{2m}}{2^{2m+1}-1}=\underset{m\to \mathrm{\infty }}{\lim }\frac{2^{2m+2}-1}{3(2^{2m+1}-1)}=\frac{2}{3},$

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

$\underset{\_}{d}(A)=\underset{m\to \mathrm{\infty }}{\lim }\frac{1+2^2+\cdots +2^{2m}}{2^{2m+2}-1}=\underset{m\to \mathrm{\infty }}{\lim }\frac{2^{2m+2}-1}{3(2^{2m+2}-1)}=\frac{1}{3}.$