Асимптотична щільність

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

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