Asymptotisk täthet

I talteorin är asymptotisk densitet en av de egenskaper som hjälper till att uppskatta hur stor en delmängd av mängden naturliga tal är . $\mathbb {N}$

Intuitivt känner vi att det finns "fler" udda tal än rutor ; uppsättningen udda tal är dock inte riktigt "större" än uppsättningen kvadrater: båda uppsättningarna är oändliga och räknebara och kan därför föras till en-till-en-korrespondens med varandra. Uppenbarligen, för att formalisera vårt intuitiva koncept, behöver vi ett bättre sätt.

Om vi slumpmässigt väljer ett tal från mängden , så kommer sannolikheten att det tillhör A att vara lika med förhållandet mellan antalet element i mängden och antalet n . Om denna sannolikhet tenderar till en viss gräns som n tenderar till oändlighet, kallas denna gräns för den asymptotiska tätheten av A . Vi ser att detta begrepp kan betraktas som sannolikheten för att välja ett tal från mängden A . Faktum är att asymptotisk densitet (liksom vissa andra typer av täthet) studeras i probabilistisk talteori . $\{1,2,\ldots ,n\}$ $A\cap \{1,2,\ldots ,n\}$

Den asymptotiska tätheten skiljer sig till exempel från sekvensdensiteten . Nackdelen med detta tillvägagångssätt är att den asymptotiska tätheten inte är definierad för alla delmängder av . $\mathbb {N}$

Definition

Delmängden positiva tal har en asymptotisk densitet , där , om gränsen för förhållandet mellan antalet element som inte överstiger , till för finns och är lika med . $A$ $\alfa$ $0\leqslant \alpha \leqslant 1$ $A$ $n$ $n$ $n\till\infty$ $\alfa$

Mer strikt, om vi definierar räknefunktionen för ett naturligt tal som antalet element som inte överstiger , så betyder likheten mellan mängdens asymptotiska täthet och antalet exakt att $n$ $a(n)$ $A$ $n$ $A$ $\alfa$

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

Övre och nedre asymptotiska tätheter

Låta vara en delmängd av mängden naturliga tal. För alla ställer vi in och . $A$ $\mathbb {N} =\{1,2,\ldots \}.$ $n\in \mathbb {N}$ $A(n)=\{1,2,\ldots ,n\}\cap A$ $a(n)=|A(n)|$

Vi definierar den övre asymptotiska densiteten för en mängd som ${\overline {d}}(A)$ $A$

{\overline {d}}(A)=\limsup _{n\högerpil \infty }{\frac {a(n)}{n}}

där lim sup är en partiell gräns för sekvensen . även känd som toppdensitet ${\overline {d}}(A)$ $A.$

På samma sätt definierar vi , den lägre asymptotiska densiteten som ${\underline {d}}(A)$ $A$

{\underline {d}}(A)=\liminf _{n\högerpil \infty }{\frac {a(n)}{n}}

Vi kommer att säga har en asymptotisk densitet om . I det här fallet kommer vi att anta $A$ $d(A)$ ${\underline {d}}(A)={\overline {d}}(A)$ $d(A)={\overline {d}}(A).$

Denna definition kan omformuleras:

d(A)=\lim _{n\högerpil \infty }{\frac {a(n)}{n))

om gränsen finns och är ändlig.

En något svagare föreställning om densitet = övre Banach-densitet ; ta , definiera som $A\subseteq \mathbb {N}$ $d^{*}(A)$

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

Om vi skriver en delmängd som en ökande sekvens $\mathbb {N}$

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

sedan

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

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

och om gränsen finns. ${\displaystyle d(A)=\lim _{n\högerpil \infty }{\frac {n}{a_{n))))$

Exempel

Uppenbarligen är d( ) $\mathbb {N}$ = 1.

Om det för någon mängd A finns d ( A ), så har vi för dess komplement d ( A c ) = 1 - d ( A ).

För varje ändlig uppsättning positiva tal F har vi d(F) = 0.

Om är mängden av alla kvadrater, då är d(A) = 0. ${\displaystyle A=\{n^{2};n\in \mathbb {N} \))$

Om är mängden av alla jämna tal, då är d(A) = 1/2. På samma sätt får vi för varje aritmetisk progression d(A) = 1/ a . ${\displaystyle A=\{2n;n\in \mathbb {N} \))$ ${\displaystyle A=\{an+b;n\in \mathbb {N} \))$

För mängden P av alla primtal får vi d(P) = 0 (se Primtalsfördelningssatsen ).

Mängden av alla kvadratlösa tal har densitet ${\displaystyle {\tfrac {6}{\pi ^{2))))$

Tätheten för uppsättningen av överskottstal är mellan 0,2474 och 0,2480.

Mängden tal vars binära representation innehåller ett udda antal siffror är ett exempel på en mängd som inte har en asymptotisk densitet, eftersom den övre densiteten är ${\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\högerpil \infty }{\frac {2^{2m+2}-1}{3(2^{2m+1}-1)))={\ frac {2}{3}}\,,

medan botten

{\underline {d}}(A)=\lim _{m\rightarrow \infty }{\frac {1+2^{2}+\cdots +2^{2m}}{2^{2m +2}-1}}=\lim _{m\högerpil \infty }{\frac {2^{2m+2}-1}{3(2^{2m+2}-1)))={\ frac {1}{3}}\,.

Asymptotisk täthet

Definition

Övre och nedre asymptotiska tätheter

Exempel

Länkar