Natural density

In number theory, natural density (or asymptotic density or arithmetic density) is one of the possibilities to measure how large a subset of the set of natural numbers is.

Intuitively, it is thought that there are more positive integers than perfect squares, since every perfect square is already positive, and 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.

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.

Asymptotic density contrasts, for example, with the Schnirelmann density. One drawback of asymptotic density is that it is not defined for all subsets of \mathbb{N}.

Definition

A subset A of positive integers has natural density (or asymptotic density) α if the proportion of elements of A among all natural numbers from 1 to n is asymptotic 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[1]

a(n)/n → α as n → +∞.

It follows from the definition that if a set A has natural density α then 0 ≤ α ≤ 1.

Upper and lower asymptotic density

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

Define the upper asymptotic density \overline{d}(A) of A by

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

where lim sup is the limit superior. \overline{d}(A) is also known simply as the upper density of A.

Similarly, \underline{d}(A), the lower asymptotic density of A, is defined by

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

One may say A has asymptotic density d(A) if \underline{d}(A)=\overline{d}(A), in which case d(A) is equal to this common value.

This definition can be restated in the following way:

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

if the limit exists.[2]

It can be proven that the definitions imply that the following also holds. If one were to write a subset of \mathbb{N} as an increasing sequence

 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},
\overline{d}(A) = \limsup_{n \rightarrow \infty} \frac{n}{a_n}

and d(A) = \lim_{n \rightarrow \infty} \frac{n}{a_n} if the limit exists.

Remark

A somewhat weaker notion of density is upper Banach density; given a set A \subseteq \mathbb{N}, define d^*(A) as

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

Properties and examples

\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 23\, ,
whereas its lower density is
\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 13\, .
A_x:=\{n\in\mathbb{N}\,:\, \alpha_n<x \}\, .
Then, by definition, d(A_x)= x for all x.

Other density functions

Other density functions on subsets of the natural numbers may be defined analogously. For example, the logarithmic density of a set A is defined as the limit (if it exists)

\mathbf{\delta}(A) = \lim_{x \rightarrow \infty} \frac{1}{\log x} \sum_{n \in A, n \le x} \frac{1}{n} \ .

Upper and lower logarithmic densities are defined analogously as well.

Notes

  1. 1 2 Tenenbaum (1995) p.261
  2. Nathanson (2000) pp.256–257
  3. Hall, Richard R.; Tenenbaum, Gérald (1988). Divisors. Cambridge Tracts in Mathematics 90. Cambridge: Cambridge University Press. p. 95. ISBN 0-521-34056-X. Zbl 0653.10001.
  4. Deléglise, Marc (1998). "Bounds for the density of abundant integers". Experimental Mathematics 7 (2): 137–143. doi:10.1080/10586458.1998.10504363. ISSN 1058-6458. MR 1677091. Zbl 0923.11127.

References

This article incorporates material from Asymptotic density on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.

This article is issued from Wikipedia - version of the Thursday, March 31, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.