Asymptotická hustota

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. +more 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

Podmnožina A přirozených čísel má asymptotickou 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

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

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). +more Složitějším příkladem je množina bezčtvercových celých čísel, která má asymptotickou hustotu \tfrac{6}{\pi^2}.

Reference

Kategorie:Teorie čísel Kategorie:Kombinatorika