In number theory, natural density, also referred to as asymptotic density or arithmetic density, is a measure of how "large" a subset of the set of natural numbers is. It relies chiefly on the probability of encountering members of the desired subset when combing through the interval [1, n] as n grows large. For example, it may seem intuitively that there are more positive integers than perfect squares, because every perfect square is already positive and yet many other positive integers exist besides. However, the set of positive integers is not in fact larger than the set of perfect squares: both sets are infinite and countable and can therefore be put in one-to-one correspondence. Nevertheless if one goes through the natural numbers, the squares become increasingly scarce. The notion of natural density makes this intuition precise for many, but not all, subsets of the naturals (see Schnirelmann density, which is similar to natural density but defined for all subsets of N {\displaystyle \mathbb {N} } ). If an integer is randomly selected from the interval [1, n], then the probability that it belongs to A is the ratio of the number of elements of A in [1, n] to the total number of elements in [1, n]. If this probability tends to some limit as n tends to infinity, then this limit is referred to as the asymptotic density of A. This notion can be understood as a kind of probability of choosing a number from the set A. Indeed, the asymptotic density (as well as some other types of densities) is studied in probabilistic number theory.
Definition A subset A of positive integers has natural density α if the proportion of elements of A among all natural numbers from 1 to n converges to α as n tends to infinity. More explicitly, if one defines for any natural number n the counting function a(n) as the number of elements of A less than or equal to n, then the natural density of A being α exactly means that
It follows from the definition that if a set A has natural density α then 0 ≤ α ≤ 1.
Upper and lower asymptotic density Let A {\displaystyle A} be a subset of the set of natural numbers N = { 1 , 2 , … } . {\displaystyle \mathbb {N} =\{1,2,\ldots \}.} For any n ∈ N {\displaystyle n\in \mathbb {N} } , define A ( n ) {\displaystyle A(n)} to be the intersection A ( n ) = { 1 , 2 , … , n } ∩ A , {\displaystyle A(n)=\{1,2,\ldots ,n\}\cap A,} and let a ( n ) = | A ( n ) | {\displaystyle a(n)=|A(n)|} be the number of elements of A {\displaystyle A} less than or equal to n {\displaystyle n} . Define the upper asymptotic density d ¯ ( A ) {\displaystyle {\overline {d}}(A)} of A {\displaystyle A} (also called the "upper density") by
d ¯ ( A ) = lim sup n → ∞ a ( n ) n {\displaystyle {\overline {d}}(A)=\limsup _{n\rightarrow \infty }{\frac {a(n)}{n}}}
where lim sup is the limit superior. Similarly, define the lower asymptotic density d _ ( A ) {\displaystyle {\underline {d}}(A)} of A {\displaystyle A} (also called the "lower density") by
d _ ( A ) = lim inf n → ∞ a ( n ) n {\displaystyle {\underline {d}}(A)=\liminf _{n\rightarrow \infty }{\frac {a(n)}{n}}}
where lim inf is the limit inferior. One may say A {\displaystyle A} has asymptotic density d ( A ) {\displaystyle d(A)} if d _ ( A ) = d ¯ ( A ) {\displaystyle {\underline {d}}(A)={\overline {d}}(A)} , in which case d ( A ) {\displaystyle d(A)} is equal to this common value. This definition can be restated in the following way:
d ( A ) = lim n → ∞ a ( n ) n {\displaystyle d(A)=\lim _{n\rightarrow \infty }{\frac {a(n)}{n}}}
if this limit exists. These definitions may equivalently be expressed in the following way. Given a subset A {\displaystyle A} of N {\displaystyle \mathbb {N} } , write it as an increasing sequence indexed by the natural numbers:
… excerpt ends here. Continue reading the full article.
