Asymptotic density

The asymptotic density is a number-theoretic limit that indicates the proportion of a subset of natural numbers in the set of natural numbers.

Simple definition

One calls the limit value

${\displaystyle \lim _{n\rightarrow \infty }{\frac {a(n)}{n}}}$

the asymptotic density of a subset . It is the counting function of . This indicates how many elements from are not larger than . It applies . ${\displaystyle d(A)}$ ${\displaystyle A\subseteq \mathbb {N} }$ ${\displaystyle a(n)}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle n}$ ${\displaystyle 0\leq d(A)\leq 1}$

Upper and lower asymptotic density

For any one be and . ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle A(n)=\{1,2,\dotsc ,n\}\cap A}$ ${\displaystyle a(n)=|A(n)|}$

The upper asymptotic density of is then through ${\displaystyle {\overline {d}}(A)}$ ${\displaystyle A}$

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

defined, where lim sup is the limes superior . Likewise, it 's through ${\displaystyle {\underline {d}}(A)}$

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

defined lower asymptotic density of . has an asymptotic density only if holds. In this case the limit exists ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle d(A)}$ ${\displaystyle {\underline {d}}(A)={\overline {d}}(A)}$

${\displaystyle \lim _{n\rightarrow \infty }{\frac {a(n)}{n}}={\underline {d}}(A)={\overline {d}}(A)=\colon d(A)}$

and therefore can be defined by him . ${\displaystyle d(A)}$

Examples

• If exists for the set , then for the complementary set : ${\displaystyle d(A)}$ ${\displaystyle A}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle {\overline {A}}}$ ${\displaystyle d({\overline {A}})=1-d(A)}$
• ${\displaystyle d(\mathbb {N} )=1}$
• For any finite set of natural numbers we have: ${\displaystyle E}$ ${\displaystyle d(E)=0}$
• The following applies to the set of all square numbers : ${\displaystyle A=\{n^{2};n\in \mathbb {N} \}}$ ${\displaystyle d(A)=0}$
• The following applies to the set of all even numbers: ${\displaystyle A=\{2n;n\in \mathbb {N} \}}$ ${\displaystyle d(A)=1/2}$
• More generally applies to every arithmetic sequence with a positive : ${\displaystyle A=\{an+b;n\in \mathbb {N} \}}$ ${\displaystyle a}$ ${\displaystyle d(A)=1/a}$
• For the set of all prime numbers one obtains due to the prime number theorem : ${\displaystyle P}$ ${\displaystyle d(P)=0}$
• The set of all square-free natural numbers has the density with the Riemann zeta function . ${\displaystyle 6/\pi ^{2}=1/\zeta (2)}$ ${\displaystyle \zeta }$
• The density of abundant numbers is between 0.2474 and 0.2480.
• The set of all numbers whose binary representation has an odd number of digits is an example of a set with no asymptotic density. In this case, the following applies to the lower and upper asymptotic density: ${\displaystyle A=\bigcup \limits _{n=0}^{\infty }\left\{2^{2n},\dotsc ,2^{2n+1}-1\right\}}$

${\displaystyle {\underline {d}}(A)=\lim _{m\rightarrow \infty }{\frac {1+2^{2}+\dotsb +2^{2m}}{2^{2m+2}-1}}=\lim _{m\rightarrow \infty }{\frac {2^{2m+2}-1}{3(2^{2m+2}-1)}}={\frac {1}{3}}}$

${\displaystyle {\overline {d}}(A)=\lim _{m\rightarrow \infty }{\frac {1+2^{2}+\dotsb +2^{2m}}{2^{2m+1}-1}}=\lim _{m\rightarrow \infty }{\frac {2^{2m+2}-1}{3(2^{2m+1}-1)}}={\frac {2}{3}}}$

swell

• Melvyn B. Nathanson: Elementary methods in number theory (=  Graduate Texts in Mathematics . Volume 195 ). Springer, New York 2000, ISBN 0-387-98912-9 (English, zbmath.org ).
• Hans-Heinrich Ostmann: Additive number theory (=  results of mathematics and its border areas . Volume 7 ). Part One: General Investigations . Springer-Verlag, Berlin / Göttingen / Heidelberg 1956, ISBN 978-3-662-11030-0 ( books.google.de - reading sample).
• Jörn Steuding: Probabilistic number theory. (PDF) In: psu.edu. citeseerx.ist.psu.edu, accessed February 7, 2016 . 
• Gérald Tenenbaum: Introduction to analytic and probabilistic number theory (=  Cambridge studies in advanced mathematics . Volume 46 ). Cambridge university press, Cambridge 1995, ISBN 0-521-41261-7 (French, zbmath.org ).