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

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

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

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

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

ОпределениеПравить

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

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

$\underset{n\to <!--\; \to \; -->+\mathrm{\infty <!--\; \infty \; -->}}{lim}\frac{a(n)}{n}=\mathrm{\alpha <!--\; \alpha \; -->}$$\lim \limits _{n\to +\infty }{\frac {a(n)}{n}}=\alpha$ .

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

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

Определим верхнюю асимптотическую плотность $\stackrel{¯<!--\; ¯\; -->}{d}(A)$${\overline {d}}(A)$  множества $A$$A$  как

$\stackrel{¯<!--\; ¯\; -->}{d}(A)=\underset{n\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}}{lim sup}\frac{a(n)}{n}$${\overline {d}}(A)=\limsup _{n\rightarrow \infty }{\frac {a(n)}{n}}$ 

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

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

$\underset{\_<!--\; \_\; -->}{d}(A)=\underset{n\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}}{lim inf}\frac{a(n)}{n}$${\underline {d}}(A)=\liminf _{n\rightarrow \infty }{\frac {a(n)}{n}}$ 

Будем говорить, $A$$A$  имеет асимптотическую плотность $d(A)$$d(A)$ , если $\underset{\_<!--\; \_\; -->}{d}(A)=\stackrel{¯<!--\; ¯\; -->}{d}(A)$${\underline {d}}(A)={\overline {d}}(A)$ . В данном случае будем полагать $d(A)=\stackrel{¯<!--\; ¯\; -->}{d}(A).$$d(A)={\overline {d}}(A).$ 

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

$d(A)=\underset{n\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}}{lim}\frac{a(n)}{n}$$d(A)=\lim _{n\rightarrow \infty }{\frac {a(n)}{n}}$ 

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

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

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

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

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

то

$\underset{\_<!--\; \_\; -->}{d}(A)=\underset{n\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}}{lim inf}\frac{n}{a_n},$${\underline {d}}(A)=\liminf _{n\rightarrow \infty }{\frac {n}{a_{n}}},$ 

$\stackrel{¯<!--\; ¯\; -->}{d}(A)=\underset{n\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}}{lim sup}\frac{n}{a_n}$${\overline {d}}(A)=\limsup _{n\rightarrow \infty }{\frac {n}{a_{n}}}$ 

и $d(A)=\underset{n\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}}{lim}\frac{n}{a_n}$$d(A)=\lim _{n\rightarrow \infty }{\frac {n}{a_{n}}}$  если предел существует.

ПримерыПравить

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

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

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

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

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

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

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

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

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

$\stackrel{¯<!--\; ¯\; -->}{d}(A)=\underset{m\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}}{lim}\frac{1+2^2+\cdots <!--\; \cdots \; -->+2^{2m}}{2^{2m+1}-<!--\; -\; -->1}=\underset{m\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}}{lim}\frac{2^{2m+2}-<!--\; -\; -->1}{3(2^{2m+1}-<!--\; -\; -->1)}=\frac{2}{3},$${\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}}\,,$ 

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

$\underset{\_<!--\; \_\; -->}{d}(A)=\underset{m\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}}{lim}\frac{1+2^2+\cdots <!--\; \cdots \; -->+2^{2m}}{2^{2m+2}-<!--\; -\; -->1}=\underset{m\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}}{lim}\frac{2^{2m+2}-<!--\; -\; -->1}{3(2^{2m+2}-<!--\; -\; -->1)}=\frac{1}{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}}\,.$