In
number theory, natural density, also referred to as asymptotic density or arithmetic density, is one method to measure 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[1, n as n grows large.
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 for many, but not all, subsets of the naturals (see
Schnirelmann density, which is similar to natural density but defined for all subsets of ).
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.
Definition
A subset A of positive integers has natural density α if the proportion of elements of A among all
natural numbers from 1 to n converges to α as n tends to infinity.
More explicitly, if one defines for any natural number n the counting
functiona(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 be a subset of the set of natural numbers For any , define to be the intersection and let be the number of elements of less than or equal to .
Define the upper asymptotic density of (also called the "upper density") by
These definitions may equivalently be expressed in the following way. Given a subset of , write it as an increasing sequence indexed by the natural numbers:
Then
and
if the limit exists.
A somewhat weaker notion of density is the upper Banach density of a set This is defined as
Properties and examples
For any
finite setF of positive integers, d(F) = 0.
If d(A) exists for some set A and Ac denotes its
complement set with respect to , then d(Ac) = 1 − d(A).
Corollary: If is finite (including the case ),
If and exist, then
If is the set of all squares, then d(A) = 0.
If is the set of all even numbers, then d(A) = 0.5. Similarly, for any arithmetical progression we get
The set of all
square-free integers has density More generally, the set of all nth-power-free numbers for any natural n has density where is the
Riemann zeta function.
The set of
abundant numbers has non-zero density.[3] Marc Deléglise showed in 1998 that the density of the set of abundant numbers is between 0.2474 and 0.2480.[4]
The set
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.[1] (See
Benford's law.)
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)
Upper and lower logarithmic densities are defined analogously as well.
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.[5]
Tenenbaum, Gérald (1995). Introduction to analytic and probabilistic number theory. Cambridge Studies in Advanced Mathematics. Vol. 46.
Cambridge University Press.
Zbl0831.11001.