Asymptotická hustota

V teorii čísel je asymptotická hustota jednou z charakteristik, která pomáhá odhadnout, jak velká je podmnožina množiny přirozených čísel . $\mathbb {N}$

Intuitivně cítíme, že existuje „více“ lichých čísel než čtverců ; nicméně, soubor lichých čísel není opravdu “větší” než soubor čtverců: oba soubory jsou nekonečné a spočetné , a tak moci být přinesen do osobní korespondence spolu navzájem. Je zřejmé, že k formalizaci našeho intuitivního konceptu potřebujeme lepší způsob.

Pokud náhodně vybereme číslo z množiny , pak pravděpodobnost, že patří do A , bude rovna poměru počtu prvků množiny k číslu n . Jestliže tato pravděpodobnost směřuje k určité limitě , zatímco n směřuje k nekonečnu, tato limita se nazývá asymptotická hustota A . Vidíme, že tento pojem lze považovat za pravděpodobnost výběru čísla z množiny A . Asymptotická hustota (stejně jako některé další typy hustoty) je studována v pravděpodobnostní teorii čísel . $\{1,2,\ldots ,n\}$ $A\cap \{1,2,\ldots ,n\}$

Asymptotická hustota se například liší od hustoty sekvence . Nevýhodou tohoto přístupu je, že asymptotická hustota není definována pro všechny podmnožiny . $\mathbb {N}$

Definice

Podmnožina kladných čísel má asymptotickou hustotu , kde , jestliže limita poměru počtu prvků nepřesahující , k for existuje a je rovna . $A$ $\alpha$ $0\leqslant \alpha \leqslant 1$ $A$ $n$ $n$ $n\to\infty$ $\alpha$

Přesněji, definujeme-li pro libovolné přirozené číslo počítací funkci jako počet prvků nepřesahujících , pak rovnost asymptotické hustoty množiny k číslu přesně znamená, že $n$ $a(n)$ $A$ $n$ $A$ $\alpha$

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

Horní a dolní asymptotické hustoty

Dovolit být podmnožinou množiny přirozených čísel.Pro libovolné , Nastavíme a . $A$ $\mathbb {N} =\{1,2,\ldots \}.$ $n\in \mathbb {N}$ $A(n)=\{1,2,\ldots ,n\}\cap A$ $a(n)=|A(n)|$

Horní asymptotickou hustotu množiny definujeme jako ${\overline {d}}(A)$ $A$

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

kde lim sup je částečná limita posloupnosti . také známý jako nejvyšší hustota ${\overline {d}}(A)$ $A.$

Podobně definujeme nižší asymptotickou hustotu jako ${\underline {d}}(A)$ $A$

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

Řekneme, že má asymptotickou hustotu , jestliže . V tomto případě budeme předpokládat $A$ $d(A)$ ${\underline {d}}(A)={\overline {d}}(A)$ $d(A)={\overline {d}}(A).$

Tuto definici lze přeformulovat:

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

pokud limita existuje a je konečná.

Poněkud slabší pojem hustoty = horní Banachova hustota ; brát , definovat jako $A\subseteq \mathbb {N}$ $d^{*}(A)$

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

Zapíšeme-li podmnožinu jako rostoucí posloupnost $\mathbb {N}$

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

pak

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

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

a pokud limit existuje. ${\displaystyle d(A)=\lim _{n\rightarrow \infty }{\frac {n}{a_{n))))$

Příklady

Je zřejmé, že d( ) $\mathbb {N}$ = 1.

Jestliže pro nějakou množinu A existuje d ( A ), pak pro její doplněk platí d ( A c ) = 1 - d ( A ).

Pro jakoukoli konečnou množinu kladných čísel F máme d(F) = 0.

Jestliže je množina všech čtverců, pak d(A) = 0. ${\displaystyle A=\{n^{2};n\in \mathbb {N} \))$

Jestliže je množina všech sudých čísel, pak d(A) = 1/2. Podobně pro libovolnou aritmetickou progresi dostaneme d(A) = 1/ a . ${\displaystyle A=\{2n;n\in \mathbb {N} \))$ ${\displaystyle A=\{an+b;n\in \mathbb {N} \))$

Pro množinu P všech prvočísel dostáváme d(P) = 0 (viz věta o rozdělení prvočísel ).

Množina všech čísel bez čtverců má hustotu ${\displaystyle {\tfrac {6}{\pi ^{2))))$

Hustota množiny přebytečných čísel je mezi 0,2474 a 0,2480.

Množina čísel, jejichž binární reprezentace obsahuje lichý počet číslic, je příkladem množiny, která nemá asymptotickou hustotu, protože horní hustota je ${\displaystyle 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}}\,,

zatímco dno

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

Asymptotická hustota

Definice

Horní a dolní asymptotické hustoty

Příklady

Odkazy