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

 В теории чисел асимптотическая плотность — это одна изхарактеристик, помогающих оценить, насколько велико подмножествомножества натуральных чисел N.
 Интуитивно мы ощущаем, что нечётных чисел «больше», чем квадратов;однако множество нечётных чисел в действительности не «больше» множестваквадратов: оба множества бесконечны и счётны, и, таким образом, могутбыть приведены в соответствие «один к одному» друг с другом. Очевидно,чтобы формализовать наше интуитивное понятие, нам нужен лучший способ.
 Если мы случайным образом выберем число из множества {1,2,,n},то вероятность того, что оно принадлежит A, будет равна отношениюколичества элементов множества A{1,2,,n} к числу n.Если эта вероятность стремится к некоторому пределу при стремленииn к бесконечности, этот предел называют асимптотическойплотностью A. Мы видим, что это понятие может рассматриваться каквероятность выбора числа из множества A. Действительно,асимптотическая плотность (также, как и некоторые другие виды плотности)изучается в вероятностной теории чисел .
 Асимптотическая плотность отличается, например, от плотностипоследовательности. Отрицательной стороной такого подхода является то,что асимптотическая плотность определена не для всех подмножествN.

Определение


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

limn+a(n)n=α.

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


 Пусть A — подмножество множества натуральных чиселN={1,2,}. Для любого nN положимA(n)={1,2,,n}A и a(n)=|A(n)|.
 Определим верхнюю асимптотическую плотность d¯(A)множества A как

d¯(A)=lim supna(n)n
 где lim sup — частичный предел последовательности. d¯(A)также известно как верхняя плотность A.
 Аналогично определим d_(A), нижнюю асимптотическуюплотность A как

d_(A)=lim infna(n)n
 Будем говорить, A имеет асимптотическую плотность d(A),есди d_(A)=d¯(A). В данном случае будем полагатьd(A)=d¯(A).
 Данное определение можно переформулировать:

d(A)=limna(n)n
 если предел существует и конечен.
 Несколько более слабое понятие плотности = верхняя плотностьБанаха; возьмем AN, определим d(A) как

  d\^*(A) = \{limsup\_\{N-M \{rightarrow\{infty\} \{frac\{
 Если мы запишем подмножество N как возрастающуюпоследовательность

 $A=\{a_1 то

d_(A)=lim infnnan,


d¯(A)=lim supnnan
 и d(A)=limnnan если пределсуществует.

Примеры



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


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


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


  • Если A={n2;nN} — множество всех квадратов, то d(A) = 0.


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


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


  • Множество всех бесквадратных чисел имеет плотность 6π2


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


  • Множество A=n=0{22n,,22n+11} чисел, чье двоичное представление содержит нечетное число цифр, — пример множества, не обладающего асимптотической плотностью, так как верхняя плотность равна



 \{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\{, .