Natural density

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

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 N = { 1 , 2 , … } . For any n ∈ N put A ( n ) = { 1 , 2 , … , n } ∩ A . and a ( n ) = | A ( n ) | .

Define the upper asymptotic density d ¯ ( A ) of A by

d ¯ ( A ) = lim sup n → ∞ a ( n ) n

where lim sup is the limit superior. d ¯ ( A ) is also known simply as the upper density of A .

Similarly, d _ ( A ) , the lower asymptotic density of A , is defined by

d _ ( A ) = lim inf n → ∞ a ( n ) n

One may say A has asymptotic density d ( A ) if d _ ( A ) = 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 → ∞ a ( n ) n

if the limit exists.

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

A = { a 1 < a 2 < … < a n < … ; n ∈ N }

then

d _ ( A ) = lim inf n → ∞ n a n , d ¯ ( A ) = lim sup n → ∞ n a n

and d ( A ) = lim n → ∞ n a n if the limit exists.

Remark

A somewhat weaker notion of density is upper Banach density; given a set A ⊆ N , define d ∗ ( A ) as

d ∗ ( A ) = lim sup N − M → ∞ | A ⋂ { M , M + 1 , … , N } | N − M + 1

Properties and examples

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

If d ( A ) , d ( B ) , and d ( A ∪ B ) exist, then max { d ( A ) , d ( B ) } ≤ d ( A ∪ B ) ≤ min { d ( A ) + d ( B ) , 1 } .

For any two sets A, B we have d _ ( A ) + d ¯ ( B ) ≤ d ¯ ( A ∪ B ) ≤ d ¯ ( A ) + d ¯ ( B ) .

The density d(N) of the entire set of natural numbers is equal to 1.

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

If A = { n 2 ; n ∈ N } is the set of all squares, then d(A) = 0.

If A = { 2 n ; n ∈ N } is the set of all even numbers, then d(A) = 0.5 . Similarly, for any arithmetical progression A = { a n + b ; n ∈ 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 π 2

The set of abundant numbers has non-zero density. Marc Deléglise showed in 1998 that the density of the set of abundant numbers and perfect numbers is between 0.2474 and 0.2480.

The set A = ⋃ n = 0 ∞ { 2 2 n , … , 2 2 n + 1 − 1 } of numbers whose binary expansion contains an odd number of digits is an example of a set which does not have an asymptotic density, since the upper density of this set is

whereas its lower density is

The set of numbers whose decimal expansion begins with the digit 1 similarly has no natural density: the lower density is 1/9 and the upper density is 5/9.

Consider an equidistributed sequence { α n } n ∈ N in [ 0 , 1 ] and define a monotone family { A x } x ∈ [ 0 , 1 ] of sets :

Then, by definition, d ( A x ) = x for all x .

If S is a set of positive upper density then Szemerédi's theorem states that S contains arbitrarily large finite arithmetic progressions, and the Furstenberg–Sárközy theorem states that some two members of S differ by a square number.

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)

δ ( A ) = lim x → ∞ 1 log ⁡ x ∑ n ∈ A , n ≤ x 1 n   .

Upper and lower logarithmic densities are defined analogously as well.