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

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

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

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

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

Визначення

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

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

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

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

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

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

${\overline {d}}(A)=\limsup _{n\rightarrow \infty }{\frac {a(n)}{n}}$

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

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

${\underline {d}}(A)=\liminf _{n\rightarrow \infty }{\frac {a(n)}{n}}$

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

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

$d(A)=\lim _{n\rightarrow \infty }{\frac {a(n)}{n}}$

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

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

$d^{*}(A)=\limsup _{N-M\rightarrow \infty }{\frac {|A\bigcap \{M,M+1,...,N\}|}{N-M+1}}$

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

$A=\{a_{1}<a_{2}<\ldots <a_{n}<\ldots ;n\in \mathbb {N} \}$

то

${\underline {d}}(A)=\liminf _{n\rightarrow \infty }{\frac {n}{a_{n}}},$

${\overline {d}}(A)=\limsup _{n\rightarrow \infty }{\frac {n}{a_{n}}}$

і $d(A)=\lim _{n\rightarrow \infty }{\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 (див. Теорема про розподіл простих чисел).

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

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

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

${\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}}\,,$

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

${\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}}\,.$