Asymptoottinen tiheys

Lukuteoriassa asymptoottinen tiheys on yksi ominaisuuksista , joka auttaa arvioimaan, kuinka suuri luonnollisten lukujen joukon osajoukko on . $\mathbb {N}$

Intuitiivisesti tunnemme, että parittomia lukuja on "enemmän" kuin neliöitä ; parittomien lukujen joukko ei kuitenkaan ole varsinaisesti "isompi" kuin neliöiden joukko: molemmat joukot ovat äärettömiä ja laskettavia , joten ne voidaan saattaa yksi-yhteen vastaavuuteen keskenään. Ilmeisesti tarvitsemme paremman tavan virallistaaksemme intuitiivisen konseptimme.

Jos valitsemme satunnaisesti joukosta luvun , niin todennäköisyys, että se kuuluu ryhmään A , on yhtä suuri kuin joukon alkioiden lukumäärän suhde lukuon n . Jos tämä todennäköisyys pyrkii tiettyyn rajaan , kun n pyrkii äärettömyyteen, tätä rajaa kutsutaan A :n asymptoottiseksi tiheydeksi . Näemme, että tätä käsitettä voidaan pitää todennäköisyytenä valita luku joukosta A. Itse asiassa asymptoottista tiheyttä (samoin kuin joitain muitakin tiheystyyppejä ) tutkitaan todennäköisyyslaskentateoriassa . $\{1,2,\ldots ,n\}$ $A\cap \{1,2,\ldots ,n\}$

Asymptoottinen tiheys eroaa esimerkiksi sekvenssitiheydestä . Tämän lähestymistavan haittapuoli on, että asymptoottista tiheyttä ei ole määritelty kaikille :n alajoukoille . $\mathbb {N}$

Määritelmä

Positiivisten lukujen osajoukolla on asymptoottinen tiheys , jossa , jos alkioiden lukumäärän suhteen raja , joka ei ylitä arvoa for , on olemassa ja on yhtä suuri kuin . $A$ $\alpha$ $0\leqslant \alpha \leqslant 1$ $A$ $n$ $n$ $n\to\infty$ $\alpha$

Tarkemmin sanottuna, jos määrittelemme mille tahansa luonnolliselle luvulle laskentafunktion alkioiden lukumääräksi, joka ei ylitä , niin joukon asymptoottisen tiheyden yhtäläisyys luvun kanssa tarkoittaa täsmälleen, että $n$ $a(n)$ $A$ $n$ $A$ $\alpha$

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

Ylempi ja alempi asymptoottinen tiheys

Antaa olla osajoukko asettaa luonnollisia numeroita.Jokaiselle , Asetamme ja . $A$ $\mathbb {N} =\{1,2,\ldots \}.$ $n\in \mathbb {N}$ $A(n)=\{1,2,\ldots ,n\}\cap A$ $a(n)=|A(n)|$

Määrittelemme joukon ylemmän asymptoottisen tiheyden muodossa ${\overline {d}}(A)$ $A$

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

missä lim sup on sekvenssin osaraja . tunnetaan myös nimellä huipputiheys ${\overline {d}}(A)$ $A.$

Samoin määrittelemme , alempi asymptoottinen tiheys as ${\alleviivaus {d}}(A)$ $A$

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

Sanomme, että sillä on asymptoottinen tiheys , jos . Tässä tapauksessa oletamme $A$ $d(A)$ ${\underline {d}}(A)={\overline {d}}(A)$ $d(A)={\overline {d}}(A).$

Tämä määritelmä voidaan muotoilla uudelleen:

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

jos raja on olemassa ja se on äärellinen.

Hieman heikompi käsite tiheydestä = ylempi Banachin tiheys ; ota , määrittele $A\subseteq \mathbb {N}$ $d^{*}(A)$

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

Jos kirjoitamme osajoukon kasvavana sekvenssinä $\mathbb {N}$

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

sitten

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

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

ja jos raja on olemassa. ${\displaystyle d(A)=\lim _{n\rightarrow \infty }{\frac {n}{a_{n))))$

Esimerkkejä

Ilmeisesti d( ) $\mathbb {N}$ = 1.

Jos jollekin joukolle A on olemassa d ( A ), niin sen komplementille on d ( A c ) = 1 - d ( A ).

Kaikille positiivisten lukujen F äärelliselle joukolle meillä on d(F) = 0.

Jos on kaikkien neliöiden joukko, niin d(A) = 0. ${\displaystyle A=\{n^{2};n\in \mathbb {N} \))$

Jos on kaikkien parillisten lukujen joukko, niin d(A) = 1/2. Vastaavasti mille tahansa aritmeettiselle progressiolle saadaan d(A) = 1/ a . ${\displaystyle A=\{2n;n\in \mathbb {N} \))$ ${\displaystyle A=\{an+b;n\in \mathbb {N} \))$

Kaikkien alkulukujen joukolle P saadaan d(P) = 0 (katso alkulukujakaumalause ).

Kaikkien neliöttömien lukujen joukolla on tiheys ${\displaystyle {\tfrac {6}{\pi ^{2))))$

Ylimääräisten lukujen joukon tiheys on välillä 0,2474 ja 0,2480.

Lukujoukko , jonka binääriesitys sisältää parittoman määrän numeroita, on esimerkki joukosta, jolla ei ole asymptoottista tiheyttä, koska ylempi tiheys on ${\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}}\,,

kun taas pohja

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

Asymptoottinen tiheys

Määritelmä

Ylempi ja alempi asymptoottinen tiheys

Esimerkkejä

Linkit