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

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

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

Якщо ми випадковим чином виберемо число з множини $\{1,2,\dots ,n\}$, то ймовірність того, що воно належить A, дорівнюватиме відношенню кількості елементів множини $A\cap \{1,2,\dots ,n\}$ до числа n. Якщо ця імовірність прямує до деякої границі при прямуванні n до нескінченності, цю межу називають асимптотичною щільністю A. Очевидно, що це поняття може розглядатися як імовірність вибору числа з множини A. Дійсно, асимптотична щільність (також, як і деякі інші види щільності) вивчається в імовірнісній теорії чисел (Шаблон:Lang-en).

Асимптотична щільність відрізняється, наприклад, від щільності послідовності. Негативною стороною такого підходу є те, що асимптотична щільність визначена не для всіх підмножин $\mathbb{N}$.

Визначення

Підмножина $A$ натуральних чисел має асимптотичну щільність $\alpha$, де $0⩽\alpha ⩽1$, якщо границя відношення числа елементів $A$, що не перевершують $n$, до $n$ при $n\to \mathrm{\infty }$ існує і дорівнює $\alpha$.

Більш строго, якщо ми визначимо для будь-якого натурального числа $n$ лічильну функцію $a(n)$ як число елементів $A$, що не перевершують $n$, то рівність асимптотичної щільності множини $A$ числу $\alpha$ точно означає, що

$\lim {\mathrm{\backslash limits}}_{n\to +\mathrm{\infty }}\frac{a(n)}{n}=\alpha$.

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

Нехай $A$ — підмножина множини натуральних чисел $\mathbb{N}=\{1,2,\dots \}.$ Для будь-якого $n\in \mathbb{N}$ покладемо $A(n)=\{1,2,\dots ,n\}\cap A$ і $a(n)=|A(n)|$.

Визначимо верхню асимптотичну щільність $\bar{d}(A)$ множини $A$ як

$\bar{d}(A)=\underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}\frac{a(n)}{n}$

де lim sup — часткова границя послідовності. $\bar{d}(A)$ також відоме як верхня щільність $A.$

Аналогічно визначимо $\underset{\_}{d}(A)$, нижню асимптотичну щільність $A$ як

$\underset{\_}{d}(A)=\underset{n\to \mathrm{\infty }}{\mathrm{lim\; inf}}\frac{a(n)}{n}$

Будемо казати, що $A$ має асимптотичну щільність $d(A)$, якщо $\underset{\_}{d}(A)=\bar{d}(A)$. У цьому випадку вважатимемо $d(A)=\bar{d}(A).$

Це визначення можна переформулювати:

$d(A)=\underset{n\to \mathrm{\infty }}{\lim }\frac{a(n)}{n}$

якщо границя існує і скінченна.

Дещо слабше поняття щільності = верхня щільність Банаха; візьмемо $A\subseteq \mathbb{N}$, визначимо $d^{*}(A)$ як

$d^{*}(A)=\underset{N-M\to \mathrm{\infty }}{\mathrm{lim\; sup}}\frac{|A\bigcap \{M,M+1,...,N\}|}{N-M+1}$

Якщо ми запишемо підмножину $\mathbb{N}$ як зростаючу послідовність

$A=\{a_1<a_2<\dots <a_n<\dots ;n\in \mathbb{N}\}$

то

$\underset{\_}{d}(A)=\underset{n\to \mathrm{\infty }}{\mathrm{lim\; inf}}\frac{n}{a_n},$

$\bar{d}(A)=\underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}\frac{n}{a_n}$

і $d(A)=\underset{n\to \mathrm{\infty }}{\lim }\frac{n}{a_n}$ якщо границя існує.

Приклади

• Очевидно, d($\mathbb{N}$) = 1.

• Якщо для деякої множини A існує d(A), то для її доповнення маємо d(A^c) = 1 — d(A).

• Для будь-якої скінченної множини додатних чисел F маємо d(F) = 0.

• Якщо $A=\{n^2;n\in \mathbb{N}\}$ — множина всіх квадратів, то d(A) = 0.

• Якщо $A=\{2n;n\in \mathbb{N}\}$ — множина всіх парних чисел, тоді d(A) = ½. Аналогічно, для будь-якої арифметичної прогресії $A=\{an+b;n\in \mathbb{N}\}$ отримуємо d(A) = 1/a.

• Для множини P всіх простих чисел отримуємо d(P) = 0 (див. Теорема про розподіл простих чисел).

• Множина всіх безквадратних чисел має щільність $\frac{6}{{\pi }^2}$

• Щільність множини надлишкових чисел міститься між 0.2474 і 0.2480.

• Множина $A=\bigcup _{n=0}^{\mathrm{\infty }}\{2^{2n},\dots ,2^{2n+1}-1\}$ чисел, чиє двійкове подання містить непарне число цифр, — приклад множини, що не має асимптотичної щільності, оскільки верхня щільність дорівнює

$\bar{d}(A)=\underset{m\to \mathrm{\infty }}{\lim }\frac{1+2^2+\cdots +2^{2m}}{2^{2m+1}-1}=\underset{m\to \mathrm{\infty }}{\lim }\frac{2^{2m+2}-1}{3(2^{2m+1}-1)}=\frac{2}{3},$

тоді, як нижня

$\underset{\_}{d}(A)=\underset{m\to \mathrm{\infty }}{\lim }\frac{1+2^2+\cdots +2^{2m}}{2^{2m+2}-1}=\underset{m\to \mathrm{\infty }}{\lim }\frac{2^{2m+2}-1}{3(2^{2m+2}-1)}=\frac{1}{3}.$