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

 В теории чисел асимптотическая плотность — это одна из характеристик, помогающих оценить, насколько велико подмножество множества натуральных чисел 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\{, .