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

editovat

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í

 

Horní a dolní asymptotická hustota

editovat

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

 

a dolní asymptotická hustota tam má limes inferior

 

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

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  .

Reference

editovat

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