Asymptotická hustota

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Asymptotická hustota je pojem z oboru teorie čísel, kde se jedná o jeden z nástrojů jak změřit jak „velká“ je nějaká podmnožina přirozených čísel.

Je-li náhodně vybíráno přirozené číslo z konečné množiny [1,n], pak pravděpodobnost, že bude prvkem množiny A, je rovna poměru prvků A v daném intervalu k celkovému počtu čísel z intervalu. Pokud pro n jdoucí k nekonečnu tento poměr (neboli tato pravděpodobnost) konverguje k nějaké limitě, pak se hodnota této limity nazývá asymptotická hustota množiny A. Asymptotickou hustotu lze tedy chápat jako pravděpodobnost, že při zvolení náhodného přirozeného čísla bude toto číslo prvkem A. Koneckonců, studium asymptotické hustoty je jedním z předmětů pravděpodobnostní teorie čísel.

Formální definice[editovat | editovat zdroj]

Podmnožina A přirozených číselasymptotickou hustotu α, kde

0 ≤ α ≤ 1,

pokud pro funkci a(n) vyjadřující počet prvků z A menších nebo rovných n platí

\lim_{n\to+\infty}\frac{a(n)}{n}=\alpha

Horní a dolní asymptotická hustota[editovat | editovat zdroj]

Horní asymptotická hustota má v definici místo limity limes superior:

\overline{d}(A) = \limsup_{n\to\infty} \frac{A(n)}{n}

a dolní asymptotická hustota tam má limes inferior

\underline{d}(A) = \liminf_{n\to\infty} \frac{A(n)}{n}.

Na rozdíl od asymptotické hustoty existují horní a dolní asymptotická hustota vždy. Posloupnost má asymptotickou hustotu tehdy a jen tehdy, pokud se její dolní a horní asymptotická hustota rovnají.

Příklady[editovat | editovat zdroj]

Celá množina přirozených čísel má asymptotickou hustotu 1, naopak každá konečná množina přirozených čísel má asymptotickou hustotu 0. Asymptotickou hustotu 0 může ovšem mít i nekonečná množina, příkladem takové množiny je množina čtvercových čísel, jiným příkladem je množina prvočísel (to plyne z prvočíselné věty). Složitějším příkladem je množina bezčtvercových celých čísel, která má asymptotickou hustotu \tfrac{6}{\pi^2}.

Reference[editovat | editovat zdroj]

V tomto článku byl použit překlad textu z článku Asymptotická hustota na slovenské Wikipedii.