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-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

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 → +∞.

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.

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$ .

M. Kolibiar, A. Legéň, T. Šalát and Š. Znám (1992). Algebra a príbuzné disciplíny. Alfa, Bratislava (in Slovak). ISBN 80-05-00721-3.

H. H. Ostmann (1956). Additive Zahlentheorie I (in German). Berlin-Göttingen-Heidelberg: Springer-Verlag.

Steuding, Jörn. Probabilistic number theory. Retrieved on 2005-10-06.

G. Tenenbaum (1995). Introduction to analytic and probabilistic number theory. Cambridge: Cambridge Univ. Press.

This article incorporates material from Asymptotic density on PlanetMath, which is licensed under the GFDL.

Retrieved from "http://en.wikipedia.org/wiki/Natural_density"

Categories: Number theory | Combinatorics

Searching reference...

Reference

Sources

Natural density

From Wikipedia, the free encyclopedia

Contents

Top Matching Results

Sponsored Links
This section contains paid listings which have been purchased by companies that want to have their sites appear for specific search terms and related content. These listings are administered, sorted and maintained by a third party and are not endorsed by Search.com.

Search Results

Searching reference...

Reference

Sources

Natural density

From Wikipedia, the free encyclopedia

Contents

Top Matching Results

Sponsored Links This section contains paid listings which have been purchased by companies that want to have their sites appear for specific search terms and related content. These listings are administered, sorted and maintained by a third party and are not endorsed by Search.com.

Search Results

Sponsored Links
This section contains paid listings which have been purchased by companies that want to have their sites appear for specific search terms and related content. These listings are administered, sorted and maintained by a third party and are not endorsed by Search.com.