Asymptotisk tæthed

I talteorien er asymptotisk tæthed en af de karakteristika, der hjælper med at estimere, hvor stor en delmængde af mængden af naturlige tal er . $\mathbb {N}$

Intuitivt føler vi, at der er "flere" ulige tal end kvadrater ; men sættet af ulige tal er ikke rigtig "større" end sættet af kvadrater: begge sæt er uendelige og tællelige og kan således bringes i en-til-en-korrespondance med hinanden. For at formalisere vores intuitive koncept har vi naturligvis brug for en bedre måde.

Hvis vi tilfældigt vælger et tal fra mængden , så vil sandsynligheden for, at det hører til A , være lig med forholdet mellem antallet af elementer i mængden og tallet n . Hvis denne sandsynlighed tenderer til en vis grænse, da n har tendens til uendelig, kaldes denne grænse for den asymptotiske tæthed af A . Vi ser, at dette begreb kan betragtes som sandsynligheden for at vælge et tal fra mængden A . Faktisk studeres asymptotisk tæthed (såvel som nogle andre typer tæthed ) i sandsynlig talteori . $\{1,2,\ldots ,n\}$ $A\cap \{1,2,\ldots ,n\}$

Den asymptotiske tæthed er for eksempel forskellig fra sekvensdensiteten . Ulempen ved denne tilgang er, at den asymptotiske tæthed ikke er defineret for alle delmængder af . $\mathbb {N}$

Definition

Delmængden af positive tal har en asymptotisk tæthed , hvor , hvis grænsen for forholdet mellem antallet af elementer, der ikke overstiger , til for eksisterer og er lig med . $EN$ $\alfa$ $0\leqslant \alpha \leqslant 1$ $EN$ $n$ $n$ $n\til\infty$ $\alfa$

Mere strengt, hvis vi definerer tællefunktionen for et hvilket som helst naturligt tal som antallet af elementer, der ikke overstiger , så betyder ligheden mellem den asymptotiske tæthed af mængden og tallet nøjagtigt, at $n$ $a(n)$ $EN$ $n$ $EN$ $\alfa$

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

Øvre og nedre asymptotiske tætheder

Lad være en delmængde af mængden af naturlige tal. For enhver , sætter vi og . $EN$ $\mathbb {N} =\{1,2,\ldots \}.$ $n\in \mathbb {N}$ $A(n)=\{1,2,\ldots ,n\}\cap A$ $a(n)=|A(n)|$

Vi definerer den øvre asymptotiske tæthed af et sæt som ${\overline {d}}(A)$ $EN$

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

hvor lim sup er en delvis grænse for sekvensen . også kendt som topdensitet ${\overline {d}}(A)$ $EN.$

På samme måde definerer vi , den lavere asymptotiske tæthed som ${\underline {d}}(A)$ $EN$

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

Vi vil sige har en asymptotisk tæthed hvis . I dette tilfælde vil vi antage $EN$ $d(A)$ ${\underline {d}}(A)={\overline {d}}(A)$ $d(A)={\overline {d}}(A).$

Denne definition kan omformuleres:

d(A)=\lim _{n\højrepil \infty }{\frac {a(n)}{n))

hvis grænsen eksisterer og er endelig.

En noget svagere forestilling om tæthed = øvre Banach-tæthed ; tage , definere som $A\subseteq \mathbb {N}$ $d^{*}(A)$

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

Hvis vi skriver en delmængde som en stigende sekvens $\mathbb {N}$

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

derefter

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

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

og hvis grænsen eksisterer. ${\displaystyle d(A)=\lim _{n\højrepil \infty }{\frac {n}{a_{n))))$

Eksempler

Det er klart, d( ) $\mathbb {N}$ = 1.

Hvis der for nogle mængder A findes d ( A ), så har vi for dets komplement d ( A c ) = 1 - d ( A ).

For ethvert endeligt sæt af positive tal F har vi d(F) = 0.

Hvis er mængden af alle kvadrater, så er d(A) = 0. ${\displaystyle A=\{n^{2};n\in \mathbb {N} \))$

Hvis er mængden af alle lige tal, så er d(A) = 1/2. Tilsvarende får vi for enhver aritmetisk progression d(A) = 1/ a . ${\displaystyle A=\{2n;n\in \mathbb {N} \))$ ${\displaystyle A=\{an+b;n\in \mathbb {N} \))$

For mængden P af alle primtal får vi d(P) = 0 (se Primtalsfordelingssætning ).

Mængden af alle kvadratløse tal har tæthed ${\displaystyle {\tfrac {6}{\pi ^{2))))$

Tætheden af sættet af overskydende tal er mellem 0,2474 og 0,2480.

Det sæt af tal, hvis binære repræsentation indeholder et ulige antal cifre, er et eksempel på et sæt, der ikke har en asymptotisk tæthed, da den øvre tæthed er ${\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øjrepil \infty }{\frac {2^{2m+2}-1}{3(2^{2m+1}-1)))={\ frac {2}{3}}\,,

mens bunden

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

Asymptotisk tæthed

Definition

Øvre og nedre asymptotiske tætheder

Eksempler

Links