Asymptotische dichtheid

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

De asymptotische dichtheid (of natuurlijke dichtheid) is in de getaltheorie een waarde om mee aan te geven hoe 'groot' een deelverzameling van de natuurlijke getallen is.

Inleiding[bewerken]

Men zou kunnen denken dat er meer positieve gehele getallen bestaan dan kwadraten van gehele getallen. Immers, elk kwadraat is positief en behalve de kwadraten bestaan er nog veel andere positieve gehele getallen. In feite is echter de verzameling der gehele getallen niet groter dan de verzameling kwadraten: beide verzamelingen zijn oneindig en aftelbaar en er bestaat dus een bijectie tussen beide verzamelingen. Hieronder zal blijken dat de verzamelingen wel een verschillende 'dichtheid' hebben.

Neem nu een deelverzameling A binnen de positieve gehele getallen. Als we uit de verzameling {1, ..., n} random een geheel getal kiezen, dan is de kans dat het getal in A zit gelijk aan het aantal elementen van A in {1, ..., n} gedeeld door n, het totaal aantal elementen van {1, ..., n}. Nu laten we n naar oneindig gaan. Als de genoemde kans dan convergeert naar een bepaalde limietwaarde, dan wordt deze limiet de asymptotische dichtheid van A genoemd. Dit is als het ware de 'kans' dat een geheel willekeurig geheel getal in A zit. De asymptotische dichtheid (en andere dichtheden) wordt bestudeerd in de probabilistische getaltheorie.

Asymptotische dichtheid is iets anders dan bijvoorbeeld de Schnirelmann-dichtheid.

Opmerking: deze definitie heeft als 'nadeel' dat de asymptotische dichtheid niet voor alle deelverzamelingen van \mathbb{N} gedefinieerd is.

Definitie[bewerken]

Een deelverzameling A bestaande uit positieve gehele getallen heeft een asymptotische dichtheid (of natuurlijke dichtheid) α, waarbij

0 ≤ α ≤ 1,

indien de fractie elementen van A binnen de natuurlijke getallen {1, ..., n} asymptotisch naar α gaat, als n naar oneindig gaat.

Explicieter geformuleerd: als voor elk natuurlijk getal n de telfunctie a(n) gedefinieerd wordt als het aantal elementen van A dat kleiner dan of gelijk aan n is, dan betekent dat A een natuurlijke dichtheid α heeft, dat

a(n)/n → α als n → +∞.

Bovendichtheid en onderdichtheid[bewerken]

Beschouw weer A, een deelverzameling van de natuurlijke getallen \mathbb{N}=\{1,2,\ldots\}. Voor iedere n \in \mathbb{N} definiëren we A(n)=\{1,2,\ldots,n\} \cap A en a(n)=|A(n)|, het aantal elementen van A(n).

De bovendichtheid \overline{d}(A) van A definiëren we als

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

waarbij lim sup de limes superior is.

Evenzo wordt \underline{d}(A), de onderdichtheid van A gedefinieerd door

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

met lim inf de limes inferior.

We zeggen dat A een asymptotische dichtheid d(A) heeft indien \underline{d}(A)=\overline{d}(A), en in dat geval is d(A) gelijk aan deze waarde.

De definitie kan ook als volgt worden geformuleerd:

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

mits deze limiet bestaat.[1]

Uit de definities volgt dat ook het volgende geldt. Als iemand een deelverzameling van \mathbb{N} zou schrijven als een stijgende rij

 A=\{a_1<a_2<\ldots<a_n<\ldots; n\in\mathbb{N}\}

dan

\underline{d}(A) = \liminf_{n \rightarrow \infty} \frac{n}{a_n},
\overline{d}(A) = \limsup_{n \rightarrow \infty} \frac{n}{a_n}

en

d(A) = \lim_{n \rightarrow \infty} \frac{n}{a_n}

indien de limiet bestaat.

Opmerking[bewerken]

Een ietwat zwakker dichtheidsbegrip is de Banach-bovendichtheid; bij een gegeven verzameling A \subseteq \mathbb{N}, definieert men d^*(A) als

 d^*(A) = \limsup_{N-M \rightarrow \infty} \frac{| A \bigcap \{M, M+1, \ldots , N\}|}{N-M+1}

Voorbeelden[bewerken]

  • Als d(A) bestaat voor een zekere verzameling A, dan geldt voor het complement van A dat d(Ac) = 1 − d(A).
  • Het is makkelijk in te zien dat geldt d(\mathbb{N}) = 1.
  • Voor iedere eindige verzameling gehele getallen F geldt d(F) = 0.
  • Als A=\{n^2; n\in\mathbb{N}\} de verzameling van alle kwadraten is, dan is d(A) = 0.
  • Voor A=\{2n; n\in\mathbb{N}\}, de verzameling van alle even getallen, geldt d(A) = 0,5 . Evenzo hebben we voor iedere rij A=\{an+b; n\in\mathbb{N}\} dat geldt d(A) = 1/a.
  • Voor P, de verzameling van alle priemgetallen volgt uit de priemgetalstelling dat d(P) = 0.
  • De verzameling van alle kwadraatvrije gehele getallen heeft dichtheid \tfrac{6}{\pi^2}
  • Van de dichtheid van de overvloedige getallen is bekend dat deze ligt tussen 0.2474 en 0.2480.
  • De verzameling A=\bigcup\limits_{n=0}^\infty \{2^{2n},\ldots,2^{2n+1}-1\} van getallen die binair geschreven uit een oneven aantal bits bestaan is een voorbeeld van een verzameling die geen asymptotische dichtheid heeft, immers de bovendichtheid van A is
\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 23\, ,
terwijl de onderdichtheid van A gelijk is aan
\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 13\, .
  • Beschouw een equigedistribueerde rij \{\alpha_n\}_{n\in\N} in [0,1] en definieer een monotone familie \{A_x\}_{x\in[0,1]} van verzamelingen:
A_x:=\{n\in\mathbb{N}\,:\, \alpha_n<x \}\, .
Dan geldt volgens de definitie dat d(A_x)= x voor alle x.

Voetnoten[bewerken]

  1. Nathanson (2000) blz.256–257

Referenties[bewerken]