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. 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í

${\displaystyle \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:

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

a dolní asymptotická hustota tam má limes inferior

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

Reference

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