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

В теорії чисел асимптотична щільність — це одна з характеристик, які допомагають оцінити, наскільки велика підмножина множини натуральних чисел $\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}}\,.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.