Asymptotische dichtheid

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

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. Maar, hoewel de kwadraten een echte deelverzameling vormen van de positieve gehele getallen, hebben beide verzamelingen dezelfde kardinaliteit. De verzameling der gehele getallen is "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.

Zo zijn ook de even getallen gelijkmachtig met de natuurlijke getallen, maar iedereen zal vinden dat de even getallen slechts de helft vormen van alle natuurlijke getallen. Dit wordt uitgedrukt met de asymptotische dichtheid. Voor elk natuurlijk getal $n$ zijn de even getallen (ongeveer) de helft van de getallen $1,2,\dots ,n$. Voor toenemende $n$ ligt de verhouding steeds dichter bij 1/2. Daarom is de asymptotische dichtheid 1/2.

Van een deelverzameling $A$ binnen de positieve gehele getallen behoort een aantal $a(n)$ tot de verzameling $\{1,\dots ,n\}$ Als de verhouding $a(n)/n$ convergeert naar een bepaalde limietwaarde, wordt deze limiet de asymptotische dichtheid van $A$ genoemd.

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

De asymptotische dichtheid is niet voor alle deelverzamelingen van $\mathbb{N}$ gedefinieerd.

Definitie

Van een deelverzameling $A\subseteq {\mathbb{N}}_{+}$ binnen de positieve gehele getallen is $a(n)$ het aantal elementen in $A\cap \{1,\dots ,n\}$.

Als het quotiënt $a(n)/n$ convergeert voor toenemende $n$, heet de limiet

$\alpha =\underset{n\to \mathrm{\infty }}{\lim }\frac{a(n)}{n}$

de asymptotische dichtheid (of natuurlijke dichtheid) van $A$.

Bovendichtheid en onderdichtheid

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

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

$\bar{d}(A)=\underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}\frac{a(n)}{n}$

waarbij lim sup de limes superior is.

Evenzo wordt $\underset{\_}{d}(A)$, de onderdichtheid van $A$ gedefinieerd door

$\underset{\_}{d}(A)=\underset{n\to \mathrm{\infty }}{\mathrm{lim\; inf}}\frac{a(n)}{n}$

met lim inf de limes inferior.

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

De definitie kan ook als volgt worden geformuleerd:

$d(A)=\underset{n\to \mathrm{\infty }}{\lim }\frac{a(n)}{n}$

mits deze limiet bestaat.

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<\dots <a_n<\dots ;n\in {\mathbb{N}}_{+}\}$

dan

$\underset{\_}{d}(A)=\underset{n\to \mathrm{\infty }}{\mathrm{lim\; inf}}\frac{n}{a_n}$,

$\bar{d}(A)=\underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}\frac{n}{a_n}$

en

$d(A)=\underset{n\to \mathrm{\infty }}{\lim }\frac{n}{a_n}$

indien de limiet bestaat.

Opmerking

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

$d^{*}(A)=\underset{N-M\to \mathrm{\infty }}{\mathrm{lim\; sup}}\frac{|A\bigcap \{M,M+1,\dots ,N\}|}{N-M+1}$

Voorbeelden

• Als d(A) bestaat voor een zekere verzameling A, dan geldt voor het complement van A dat d(A^c) = 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 $\frac{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 _{n=0}^{\mathrm{\infty }}\{2^{2n},\dots ,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

$\bar{d}(A)=\underset{m\to \mathrm{\infty }}{\lim }\frac{1+2^2+\cdots +2^{2m}}{2^{2m+1}-1}=\underset{m\to \mathrm{\infty }}{\lim }\frac{2^{2m+2}-1}{3(2^{2m+1}-1)}=\frac{2}{3}$,

terwijl de onderdichtheid van A gelijk is aan

$\underset{\_}{d}(A)=\underset{m\to \mathrm{\infty }}{\lim }\frac{1+2^2+\cdots +2^{2m}}{2^{2m+2}-1}=\underset{m\to \mathrm{\infty }}{\lim }\frac{2^{2m+2}-1}{3(2^{2m+2}-1)}=\frac{1}{3}$.

• Beschouw een equigedistribueerde rij $\{{\alpha }_n{\}}_{n\in \mathbb{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$.

Referenties

• Sjabloon:Cite book
• Sjabloon:Cite book
• Sjabloon:Cite web
• Sjabloon:Cite book