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

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

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

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

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

Визначення

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

то

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

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

і ${\displaystyle d(A)=\lim _{n\rightarrow \infty }{\frac {n}{a_{n}}}}$ якщо границя існує.

Приклади

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

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

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

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

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

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

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

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

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

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

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

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