Asymptotic density

In number theory, asymptotic density is one of the characteristics that helps to estimate how large a subset of the set of natural numbers is. $\mathbb {N}$ ${\ displaystyle \ mathbb {N}}$ $\ mathbb {N}$ .

Intuitively, we feel that there are more “ odd ” numbers than squares ; however, the set of odd numbers is not really “larger” than the set of squares: both sets are infinite and countable , and thus can be brought into correspondence “one to one” with each other. Obviously, to formalize our intuitive concept, we need a better way.

If we randomly select a number from the set $\{1,2,\ldots ,n\}$ ${\ displaystyle \ {1,2, \ ldots, n \}}$ ${\ displaystyle \ {1,2, \ ldots, n \}}$ , then the probability that it belongs to A will be equal to the ratio of the number of elements in the set $A\cap \{1,2,\ldots ,n\}$ ${\ displaystyle A \ cap \ {1,2, \ ldots, n \}}$ ${\ displaystyle A \ cap \ {1,2, \ ldots, n \}}$ to the number n . If this probability tends to a certain limit when n tends to infinity, this limit is called the asymptotic density A. We see that this concept can be considered as the probability of choosing a number from the set A. Indeed, asymptotic density (as well as some other types of density) is studied in probabilistic number theory ( English Probabilistic number theory ).

Asymptotic density differs, for example, from sequence density . The negative side of this approach is that the asymptotic density is not defined for all subsets $\mathbb {N}$ ${\ displaystyle \ mathbb {N}}$ $\ mathbb {N}$ .

Content

1 Definition
- 1.1 Upper and lower asymptotic densities
2 Examples
3 References

Definition

Subset $A$ ${\ displaystyle A}$ positive numbers has an asymptotic density $\alpha$ ${\ displaystyle \ alpha}$ where $0\leqslant \alpha \leqslant 1$ ${\ displaystyle 0 \ leqslant \ alpha \ leqslant 1}$ if the limit of the ratio of the number of elements $A$ ${\ displaystyle A}$ not exceeding $n$ ${\ displaystyle n}$ to $n$ ${\ displaystyle n}$ at $n\to \infty$ ${\ displaystyle n \ to \ infty}$ exists and is equal $\alpha$ ${\ displaystyle \ alpha}$ .

More strictly, if we define for any natural number $n$ ${\ displaystyle n}$ counting function $a(n)$ ${\ displaystyle a (n)}$ as the number of elements $A$ ${\ displaystyle A}$ not exceeding $n$ ${\ displaystyle n}$ , then the equality of the asymptotic density of the set $A$ ${\ displaystyle A}$ the number $\alpha$ ${\ displaystyle \ alpha}$ exactly means that

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

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

.

Upper and Lower Asymptotic Density

Let be $A$ ${\ displaystyle A}$ Is a subset of the set of natural numbers $\mathbb {N} =\{1,2,\ldots \}.$ ${\ displaystyle \ mathbb {N} = \ {1,2, \ ldots \}.}$ For anyone $n\in \mathbb {N}$ ${\ displaystyle n \ in \ mathbb {N}}$ put $A(n)=\{1,2,\ldots ,n\}\cap A$ ${\ displaystyle A (n) = \ {1,2, \ ldots, n \} \ cap A}$ and $a(n)=|A(n)|$ ${\ displaystyle a (n) = | A (n) |}$ .

We determine the upper asymptotic density ${\overline {d}}(A)$ ${\ displaystyle {\ overline {d}} (A)}$ many $A$ ${\ displaystyle A}$ as

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

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

where lim sup is the partial limit of the sequence . ${\overline {d}}(A)$ ${\ displaystyle {\ overline {d}} (A)}$ also known as upper density $A .$ ${\ displaystyle A.}$

We similarly define ${\underline {d}}(A)$ ${\ displaystyle {\ underline {d}} (A)}$ lower asymptotic density $A$ ${\ displaystyle A}$ as

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

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

Will talk, $A$ ${\ displaystyle A}$ has an asymptotic density $d(A)$ ${\ displaystyle d (A)}$ , if ${\underline {d}}(A)={\overline {d}}(A)$ ${\ displaystyle {\ underline {d}} (A) = {\ overline {d}} (A)}$ . In this case, we will assume $d(A)={\overline {d}}(A).$ ${\ displaystyle d (A) = {\ overline {d}} (A).}$

This definition can be reformulated:

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

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

if the limit exists and is finite.

A slightly weaker concept of density = upper Banach density ; take $A\subseteq \mathbb {N}$ ${\ displaystyle A \ subseteq \ mathbb {N}}$ , define $d^{*}(A)$ ${\ displaystyle d ^ {*} (A)}$ as

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

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

If we write a subset $\mathbb {N}$ ${\ displaystyle \ mathbb {N}}$ as an increasing sequence

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

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

then

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

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

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

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

and $d(A)=\lim _{n\rightarrow \infty }{\frac {n}{a_{n}}}$ ${\ displaystyle d (A) = \ lim _ {n \ rightarrow \ infty} {\ frac {n} {a_ {n}}}}$ if limit exists.

Examples

Obviously, d ( $\mathbb {N}$ ${\ displaystyle \ mathbb {N}}$ ) = 1.

If d ( A ) exists for some set A , then for its complement we have d ( A ^c ) = 1 - d ( A ).

For any finite set of positive numbers F, we have d (F) = 0.

If $A=\{n^{2};n\in \mathbb {N} \}$ ${\ displaystyle A = \ {n ^ {2}; n \ in \ mathbb {N} \}}$ Is the set of all squares, then d (A) = 0.

If $A=\{2n;n\in \mathbb {N} \}$ ${\ displaystyle A = \ {2n; n \ in \ mathbb {N} \}}$ Is the set of all even numbers, then d (A) = 1. Similarly, for any arithmetic progression $A=\{an+b;n\in \mathbb {N} \}$ ${\ displaystyle A = \ {an + b; n \ in \ mathbb {N} \}}$ we get d (A) = 1 / a .

For the set P of all primes , we get d (P) = 0 (see Theorem on the distribution of primes ).

The set of all squareless numbers has a density ${\tfrac {6}{\pi ^{2}}}$ ${\ displaystyle {\ tfrac {6} {\ pi ^ {2}}}}$

The density of the set of excess numbers is between 0.2474 and 0.2480.

A bunch of $A=\bigcup \limits _{n=0}^{\infty }\{2^{2n},\ldots ,2^{2n+1}-1\}$ ${\ displaystyle A = \ bigcup \ limits _ {n = 0} ^ {\ infty} \ {2 ^ {2n}, \ ldots, 2 ^ {2n + 1} -1 \}}$ numbers, whose binary representation contains an odd number of digits, is an example of a set that does not have asymptotic density, since the upper density is

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

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

while lower

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

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

Asymptotic density

Content

Definition

Upper and Lower Asymptotic Density

Examples

Links

More articles: