В теорії чисел асимптотична щільність — це одна з характеристик, які допомагають оцінити, наскільки велика підмножина множини натуральних чисел
.
Інтуїтивно ми відчуваємо, що непарних чисел «більше», ніж квадратів; однак множина непарних чисел насправді не «більша» від множини квадратів: обидві множини нескінченні і зліченні, і, таким чином, можуть бути приведені у відповідність «один до одного» одна з одною. Очевидно, щоб формалізувати наше інтуїтивне поняття, потрібен кращий спосіб.
Якщо ми випадковим чином виберемо число з множини
, то ймовірність того, що воно належить A, дорівнюватиме відношенню кількості елементів множини
до числа n. Якщо ця імовірність прямує до деякої границі при прямуванні n до нескінченності, цю межу називають асимптотичною щільністю A. Очевидно, що це поняття може розглядатися як імовірність вибору числа з множини A. Дійсно, асимптотична щільність (також, як і деякі інші види щільності) вивчається в імовірнісній теорії чисел (англ. Probabilistic number theory).
Асимптотична щільність відрізняється, наприклад, від щільності послідовності. Негативною стороною такого підходу є те, що асимптотична щільність визначена не для всіх підмножин
.
Підмножина
натуральних чисел має асимптотичну щільність
, де
, якщо границя відношення числа елементів
, що не перевершують
, до
при
існує і дорівнює
.
Більш строго, якщо ми визначимо для будь-якого натурального числа
лічильну функцію
як число елементів
, що не перевершують
, то рівність асимптотичної щільності множини
числу
точно означає, що
.
Нехай
— підмножина множини натуральних чисел
Для будь-якого
покладемо
і
.
Визначимо верхню асимптотичну щільність
множини
як
![{\displaystyle {\overline {d}}(A)=\limsup _{n\rightarrow \infty }{\frac {a(n)}{n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fc1af153fb9ca6245c64a9563c86d114af9baf24)
де lim sup — часткова границя послідовності.
також відоме як верхня щільність
Аналогічно визначимо
, нижню асимптотичну щільність
як
![{\displaystyle {\underline {d}}(A)=\liminf _{n\rightarrow \infty }{\frac {a(n)}{n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7db172e55ad6226f0ca80461b735d7b5c264d43c)
Будемо казати, що
має асимптотичну щільність
, якщо
. У цьому випадку вважатимемо
Це визначення можна переформулювати:
![{\displaystyle d(A)=\lim _{n\rightarrow \infty }{\frac {a(n)}{n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b53a10d7a4899f619b8b4418ded8d7e1e83644bb)
якщо границя існує і скінченна.
Дещо слабше поняття щільності = верхня щільність Банаха; візьмемо
, визначимо
як
![{\displaystyle d^{*}(A)=\limsup _{N-M\rightarrow \infty }{\frac {|A\bigcap \{M,M+1,...,N\}|}{N-M+1}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4b7d4a75fbb2fd6812d38231ee44e2cea4527e10)
Якщо ми запишемо підмножину
як зростаючу послідовність
![{\displaystyle A=\{a_{1}<a_{2}<\ldots <a_{n}<\ldots ;n\in \mathbb {N} \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9dd44189bfbdae374513f5ebec6c9082ffe48f95)
то
![{\displaystyle {\underline {d}}(A)=\liminf _{n\rightarrow \infty }{\frac {n}{a_{n}}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b283aa8c6da9ddf975e27089f645fe40b21b9a88)
![{\displaystyle {\overline {d}}(A)=\limsup _{n\rightarrow \infty }{\frac {n}{a_{n}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3d9e585534d9633cca77f6b255bdc9c0f0cc69bc)
і
якщо границя існує.
- Очевидно, d(
) = 1.
- Якщо для деякої множини A існує d(A), то для її доповнення маємо d(Ac) = 1 — d(A).
- Для будь-якої скінченної множини додатних чисел F маємо d(F) = 0.
- Якщо
— множина всіх квадратів, то d(A) = 0.
- Якщо
— множина всіх парних чисел, тоді d(A) = ½. Аналогічно, для будь-якої арифметичної прогресії
отримуємо d(A) = 1/a.
- Множина всіх безквадратних чисел має щільність
![{\displaystyle {\tfrac {6}{\pi ^{2}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/56a8566e1e80f314ab6e3cf432221410d744d4c4)
- Щільність множини надлишкових чисел міститься між 0.2474 і 0.2480.
- Множина
чисел, чиє двійкове подання містить непарне число цифр, — приклад множини, що не має асимптотичної щільності, оскільки верхня щільність дорівнює
![{\displaystyle {\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 {2}{3}}\,,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/14d9216e89fae11debcfa3b9ff128ac35e570729)
- тоді, як нижня
![{\displaystyle {\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 {1}{3}}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8551915e242fc9824e1e884525260afa8cfc3d30)