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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

Определение[править | править исходный текст]

Подмножество A положительных чисел имеет асимптотическую плотность α, где 0 ≤ α ≤ 1, если предел отношения числа элементов A, не превосходящих n, к n при при n → ∞ существует и равен α.

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

a(n)/n → α при n → +∞.

Верхняя и нижняя асимптотическая плотности[править | править исходный текст]

Пусть 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(Ac) = 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.
  • Плотность множества избыточных чисел находится между 0.2474 и 0.2480.
  • Множество A=\bigcup\limits_{n=0}^\infty \{2^{2n},\ldots,2^{2n+1}-1\} чисел, чье двоичное представление содержит четное число цифр, — пример множества, не обладающего асимптотической плотностью, так как верхняя плотность равна
\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\, ,
в то время, как нижняя
\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\, .

Ссылки[править | править исходный текст]