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

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

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

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

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

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

Определение

[править | править код]

Подмножество положительных чисел имеет асимптотическую плотность , где , если предел отношения числа элементов , не превосходящих , к при существует и равен .

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

.

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

[править | править код]

Пусть  — подмножество множества натуральных чисел Для любого положим и .

Определим верхнюю асимптотическую плотность множества как

где lim sup — частичный предел последовательности. также известно как верхняя плотность

Аналогично определим , нижнюю асимптотическую плотность как

Будем говорить, имеет асимптотическую плотность , если . В данном случае будем полагать

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

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

Несколько более слабое понятие плотности = верхняя плотность Банаха; возьмем , определим как

Если мы запишем подмножество как возрастающую последовательность

то

и если предел существует.

  • Очевидно, d() = 1.
  • Если для некоторого множества A существует d(A), то для его дополнения имеем d(Ac) = 1 — d(A).
  • Для любого конечного множества положительных чисел F имеем d(F) = 0.
  • Если  — множество всех квадратов, то d(A) = 0.
  • Если  — множество всех четных чисел, тогда d(A) = ½. Аналогично, для любой арифметической прогрессии получаем d(A) = 1/a.
  • Множество всех бесквадратных чисел имеет плотность
  • Плотность множества избыточных чисел находится между 0.2474 и 0.2480.
  • Множество чисел, чьё двоичное представление содержит нечетное число цифр, — пример множества, не обладающего асимптотической плотностью, так как верхняя плотность равна
в то время, как нижняя