Русская Википедия:Асимптотическая плотность
В теории чисел асимптотическая плотность — это одна из характеристик, помогающих оценить, насколько велико подмножество множества натуральных чисел <math>\mathbb{N}</math>.
Интуитивно мы ощущаем, что нечётных чисел «больше», чем квадратов; однако множество нечётных чисел в действительности не «больше» множества квадратов: оба множества бесконечны и счётны, и, таким образом, могут быть приведены в соответствие «один к одному» друг с другом. Очевидно, чтобы формализовать наше интуитивное понятие, нам нужен лучший способ.
Если мы случайным образом выберем число из множества <math>\{1,2,\ldots,n\}</math>, то вероятность того, что оно принадлежит A, будет равна отношению количества элементов множества <math>A\cap\{1,2,\ldots,n\}</math> к числу n. Если эта вероятность стремится к некоторому пределу при стремлении n к бесконечности, этот предел называют асимптотической плотностью A. Мы видим, что это понятие может рассматриваться как вероятность выбора числа из множества A. Действительно, асимптотическая плотность (также, как и некоторые другие виды плотности) изучается в Шаблон:Iw (Шаблон:Lang-en).
Асимптотическая плотность отличается, например, от плотности последовательности. Отрицательной стороной такого подхода является то, что асимптотическая плотность определена не для всех подмножеств <math>\mathbb{N}</math>.
Определение
Подмножество <math>A</math> положительных чисел имеет асимптотическую плотность <math>\alpha</math>, где <math>0 \leqslant \alpha \leqslant 1</math>, если предел отношения числа элементов <math>A</math>, не превосходящих <math>n</math>, к <math>n</math> при <math>n \to \infty</math> существует и равен <math>\alpha</math>.
Более строго, если мы определим для любого натурального числа <math>n</math> подсчитывающую функцию <math>a (n)</math> как число элементов <math>A</math>, не превосходящих <math>n</math>, то равенство асимптотической плотности множества <math>A</math> числу <math>\alpha</math> в точности означает, что
- <math>\lim\limits_{n \to +\infty}{\frac{a(n)}{n}} = \alpha</math>.
Верхняя и нижняя асимптотическая плотности
Пусть <math>A</math> — подмножество множества натуральных чисел <math>\mathbb{N}=\{1,2,\ldots\}.</math> Для любого <math>n \in \mathbb{N}</math> положим <math>A(n)=\{1,2,\ldots,n\} \cap A</math> и <math>a(n)=|A(n)|</math>.
Определим верхнюю асимптотическую плотность <math>\overline{d}(A)</math> множества <math>A</math> как
- <math> \overline{d}(A) = \limsup_{n \rightarrow \infty} \frac{a(n)}{n} </math>
где lim sup — частичный предел последовательности. <math>\overline{d}(A)</math> также известно как верхняя плотность <math>A.</math>
Аналогично определим <math>\underline{d}(A)</math>, нижнюю асимптотическую плотность <math>A</math> как
- <math> \underline{d}(A) = \liminf_{n \rightarrow \infty} \frac{ a(n) }{n} </math>
Будем говорить, <math>A</math> имеет асимптотическую плотность <math>d(A)</math>, если <math>\underline{d}(A)=\overline{d}(A)</math>. В данном случае будем полагать <math>d(A)=\overline{d}(A).</math>
Данное определение можно переформулировать:
- <math> d(A)=\lim_{n \rightarrow \infty} \frac{a(n)}{n} </math>
если предел существует и конечен.
Несколько более слабое понятие плотности = верхняя плотность Банаха; возьмем <math>A \subseteq \mathbb{N}</math>, определим <math>d^*(A)</math> как
- <math> d^*(A) = \limsup_{N-M \rightarrow \infty} \frac{| A \bigcap \{M, M+1, ... , N\}|}{N-M+1} </math>
Если мы запишем подмножество <math>\mathbb{N}</math> как возрастающую последовательность
- <math> A=\{a_1<a_2<\ldots<a_n<\ldots; n\in\mathbb{N}\}</math>
то
- <math>\underline{d}(A) = \liminf_{n \rightarrow \infty} \frac{n}{a_n},</math>
- <math>\overline{d}(A) = \limsup_{n \rightarrow \infty} \frac{n}{a_n}</math>
и <math>d(A) = \lim_{n \rightarrow \infty} \frac{n}{a_n}</math> если предел существует.
Примеры
- Очевидно, d(<math>\mathbb{N}</math>) = 1.
- Если для некоторого множества A существует d(A), то для его дополнения имеем d(Ac) = 1 — d(A).
- Для любого конечного множества положительных чисел F имеем d(F) = 0.
- Если <math>A=\{n^2; n\in\mathbb{N}\}</math> — множество всех квадратов, то d(A) = 0.
- Если <math>A=\{2n; n\in\mathbb{N}\}</math> — множество всех четных чисел, тогда d(A) = ½. Аналогично, для любой арифметической прогрессии <math>A=\{an+b; n\in\mathbb{N}\}</math> получаем d(A) = 1/a.
- Для множества P всех простых чисел мы получаем d(P) = 0 (см. Теорема о распределении простых чисел).
- Множество всех бесквадратных чисел имеет плотность <math>\tfrac{6}{\pi^2}</math>
- Плотность множества избыточных чисел находится между 0.2474 и 0.2480.
- Множество <math>A=\bigcup\limits_{n=0}^\infty \{2^{2n},\ldots,2^{2n+1}-1\}</math> чисел, чьё двоичное представление содержит нечетное число цифр, — пример множества, не обладающего асимптотической плотностью, так как верхняя плотность равна
- <math>\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 23\, ,</math>
- в то время, как нижняя
- <math>\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 13\, .</math>
Ссылки
