Natural density

From Wikipedia, the free encyclopedia

In number theory, asymptotic density or natural density is one of the possibilities to measure how large is a subset of the set of natural numbers $\mathbb{N}$ .

Intuitively, we feel that there are "more" odd numbers than perfect squares; however, the set of odd numbers is not in fact "bigger" than the set of perfect squares: both sets are infinite and countable and can therefore be put in one-to-one correspondence. Clearly, we need a better way to formalize our intuitive notion.

If we pick randomly a number from the set $\{1,2,\ldots,n\}$ , then the probability that it belongs to A is the ratio of the number of elements in the set $A\cap\{1,2,\ldots,n\}$ and n. If this probability tends to some limit as n tends to infinity, then we call this limit the asymptotic density of A. We see that 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 the probabilistic number theory.

Asymptotic density contrasts, for example, with the Schnirelmann density. A drawback of this approach is that the asymptotic density is not defined for all subsets of $\mathbb{N}$ . Asymptotic density is also called arithmetic density.

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

[edit] Definition

A sequence

a₁, a₂, ... , a_n, .....

with the a_j positive integers and

a_j < a_j+1 for all j,

has natural density (or asymptotic density) α, where

0 ≤ α ≤ 1,

if the proportion of natural numbers included as some a_j is asymptotic to α.

More formally, if we define the counting function A(x) as the number of a_j's with

a_j < x

then we require that

A(x) ~ αx as x → +∞.

[edit] 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.$

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

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

$\overline{d}(A)$ is also known simply as the upper density of $A .$ Similarly, we define $\underline{d}(A)$ , the lower asymptotic density of $A$ , by

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

We say $A$ has asymptotic density $d (A)$ if $\underline{d}(A)=\overline{d}(A)$ , in which case we put $d(A)=\overline{d}(A).$

This definition can be restated in the following way:

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

if the limit exists.

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

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

If we 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.

[edit] Examples

Obviously, d(N) = 1.

For any finite set F of positive integers, d(F) = 0.

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

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

For the set P of all primes we get from the prime number theorem d(P) = 0.

The set of all square free integers has density 6/(pi^2).

The set $A=\bigcup\limits_{n=0}^\infty \{3^{2n},\ldots,3^{2n+1}-1\}$ is an example of a set which does not have asymptotic density, since the upper density of this set is $\overline d(A)=\frac 23$ and the lower density is $\underline d(A)=\frac 13$ .