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

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

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

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

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

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

Определение[править | править вики-текст]

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

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

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

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

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

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

где 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.
  • Множество чисел, чье двоичное представление содержит нечетное число цифр, — пример множества, не обладающего асимптотической плотностью, так как верхняя плотность равна
в то время, как нижняя

Ссылки[править | править вики-текст]