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 as grows large.

For example, it may seem intuitively that there are more positive integers than perfect squaress, 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).

If an integer is randomly selected from the interval , then the probability that it belongs to is the ratio of the number of elements of in to the total number of elements in . If this probability tends to some limit as tends to infinity, then this limit is referred to as the asymptotic density of . This notion can be understood as a kind of probability of choosing a number from the set . Indeed, the asymptotic density (as well as some other types of densities) is studied in probabilistic number theory.

Definition

A subset of positive integers has natural density if the proportion of elements of among all natural numbers from to converges to as tends to infinity.

More explicitly, if one defines for any natural number the counting function as the number of elements of less than or equal to , then the natural density of being exactly means that

It follows from the definition that if a set has natural density then .

Upper and lower asymptotic density

.

Define the upper asymptotic density where lim sup is the limit superior.

Similarly, define the lower asymptotic density where lim inf is the limit inferior is equal to this common value.

if this limit exists.

These definitions may equivalently if the limit exists.

A somewhat weaker notion of density is the upper Banach density This is defined as

Properties and examples

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

If d(A) exists for some set A and Ac denotes its complement set, then d(Ac) = 1 − d(A).

• is the set of all squares, then d(A) = 0.

• is the set of all even numbers, then d(A

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

• The set of all square-free integers More generally, the set of all nth-power-free numbers for any natural n is the Riemann zeta function.

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

• 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. (See Benford's law.)

• Consider an equidistributed sequence.

• 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

Upper and lower logarithmic densities are defined analogously.

in the summand comes from the fact that the harmonic series is the Euler–Mascheroni constant.

For the set of multiples of an integer sequence, the Davenport–Erdős theorem states that the natural density, when it exists, is equal to the logarithmic density.

See also

• Dirichlet density

• Erdős conjecture on arithmetic progressions

Notes

References