Aszimptotikus sűrűség

A számelméletben az aszimptotikus sűrűség az egyik olyan jellemző, amely segít megbecsülni, hogy mekkora a természetes számok halmazának egy részhalmaza . $\mathbb {N}$

Intuitív módon úgy érezzük, hogy "több" páratlan szám van, mint négyzet ; azonban a páratlan számok halmaza nem igazán "nagyobb", mint a négyzetek halmaza: mindkét halmaz végtelen és megszámlálható , így egy az egyhez megfeleltetésbe hozható egymással. Nyilvánvalóan az intuitív koncepciónk formalizálásához jobb módszerre van szükségünk.

Ha véletlenszerűen választunk ki egy számot a halmazból , akkor annak a valószínűsége, hogy az A -hoz tartozik, egyenlő lesz a halmaz elemeinek számának az n számhoz viszonyított arányával . Ha ez a valószínűség egy bizonyos határig tart, miközben n a végtelen felé hajlik, ezt a határt A aszimptotikus sűrűségének nevezzük . Látjuk, hogy ez a fogalom az A halmazból való szám kiválasztásának valószínűségeként tekinthető . Valójában az aszimptotikus sűrűséget (valamint néhány más típusú sűrűséget) a valószínűségi számelmélet tanulmányozza . $\{1,2,\ldots ,n\}$ $A\cap \{1,2,\ldots ,n\}$

Az aszimptotikus sűrűség különbözik például a szekvencia sűrűségétől . Ennek a megközelítésnek az a hátránya, hogy az aszimptotikus sűrűség nincs meghatározva az összes részhalmazra . $\mathbb {N}$

Definíció

A pozitív számok részhalmazának aszimptotikus sűrűsége van , ahol , ha a -t meg nem haladó elemek számának a határa létezik, és egyenlő a -val . $A$ $\alpha$ $0\leqslant \alpha \leqslant 1$ $A$ $n$ $n$ $n\to\infty$ $\alpha$

Szigorúbban, ha bármely természetes számra a számláló függvényt a -t meg nem haladó elemszámként definiáljuk , akkor a halmaz aszimptotikus sűrűségének a számmal való egyenlősége pontosan azt jelenti, hogy $n$ $a(n)$ $A$ $n$ $A$ $\alpha$

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

Felső és alsó aszimptotikus sűrűség

Legyen egy részhalmaza a természetes számok halmazának. Bármely , beállítjuk és . $A$ $\mathbb {N} =\{1,2,\ldots \}.$ $n\in \mathbb {N}$ $A(n)=\{1,2,\ldots ,n\}\cap A$ $a(n)=|A(n)|$

Egy halmaz felső aszimptotikus sűrűségét így definiáljuk ${\overline {d}}(A)$ $A$

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

ahol a lim sup a sorozat részleges határértéke . más néven felső sűrűség ${\overline {d}}(A)$ $A.$

Hasonlóképpen definiáljuk az alacsonyabb aszimptotikus sűrűséget mint ${\underline {d}}(A)$ $A$

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

Azt mondjuk , hogy aszimptotikus sűrűsége van, ha . Ebben az esetben feltételezzük $A$ $d(A)$ ${\underline {d}}(A)={\overline {d}}(A)$ $d(A)={\overline {d}}(A).$

Ez a meghatározás újrafogalmazható:

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

ha a határ létezik és véges.

A sűrűség valamivel gyengébb fogalma = felső Banach-sűrűség ; venni , definiálni mint $A\subseteq \mathbb {N}$ $d^{*}(A)$

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

Ha egy részhalmazt növekvő sorozatként írunk fel $\mathbb {N}$

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

akkor

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

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

és ha létezik a határ. ${\displaystyle d(A)=\lim _{n\rightarrow \infty }{\frac {n}{a_{n))))$

Példák

Nyilvánvaló, hogy d( ) $\mathbb {N}$ = 1.

Ha valamelyik A halmazra létezik d ( A ), akkor annak komplementerére d ( A c ) = 1 - d ( A ).

Az F pozitív számok bármely véges halmazára d(F) = 0.

Ha az összes négyzet halmaza, akkor d(A) = 0. ${\displaystyle A=\{n^{2};n\in \mathbb {N} \))$

Ha az összes páros szám halmaza, akkor d(A) = 1/2. Hasonlóképpen, bármilyen aritmetikai progresszió esetén d(A) = 1/ a . ${\displaystyle A=\{2n;n\in \mathbb {N} \))$ ${\displaystyle A=\{an+b;n\in \mathbb {N} \))$

Az összes prím P halmazára d(P) = 0 (lásd Prímszám eloszlás tétel ).

Az összes négyzet nélküli szám halmazának sűrűsége van ${\displaystyle {\tfrac {6}{\pi ^{2))))$

A többletszámok halmazának sűrűsége 0,2474 és 0,2480 között van.

Az a számhalmaz, amelynek bináris reprezentációja páratlan számú számjegyet tartalmaz, példa egy olyan halmazra, amelynek nincs aszimptotikus sűrűsége, mivel a felső sűrűség ${\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}}\,,

míg az alsó

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

Aszimptotikus sűrűség

Definíció

Felső és alsó aszimptotikus sűrűség

Példák

Linkek