Natural density
Encyclopedia
In number theory
, asymptotic density (or natural density or arithmetic density) is one of the possibilities to measure how large
a subset
of the set of natural number
s is.
Intuitively, we think that there are "more" positive integers than perfect square
s, since every perfect square is already positive, and many other positive integers exist besides. However, the set of positive integers 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 an integer
from the set [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 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 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
.
if the proportion of elements of A among all natural number
s 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
be a subset of the set of natural numbers 
For any 
put 
and 
.
Define the upper asymptotic density
of 
by
where lim sup is the limit superior.
is also known simply as the upper density of 
Similarly, we define
, the lower asymptotic density of 
, by
One may say
has asymptotic density 
if 
, in which case we put 
This definition can be restated in the following way:
if the limit exists.
A somewhat weaker notion of density is upper Banach density; given a set
, define 
as
If one were to write a subset of
as an increasing sequence
then
and
if the limit exists.
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
, asymptotic density (or natural density or arithmetic density) is one of the possibilities to measure how large
Large set (Ramsey theory)
In Ramsey theory, a set S of natural numbers is considered to be a large set if and only if Van der Waerden's theorem can be generalized to assert the existence of arithmetic progressions with common difference in S...
a subset
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
of the set of natural number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s is.
Intuitively, we think that there are "more" positive integers than perfect square
Square number
In mathematics, a square number, sometimes also called a perfect square, is an integer that is the square of an integer; in other words, it is the product of some integer with itself...
s, since every perfect square is already positive, and many other positive integers exist besides. However, the set of positive integers 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
Bijection
A bijection is a function giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements...
. Clearly, we need a better way to formalize our intuitive notion.
If we pick randomly an integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
from the set [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 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 probabilistic number theory
Probabilistic number theory
Probabilistic number theory is a subfield of number theory, which explicitly uses probability to answer questions of number theory. One basic idea underlying it is that different prime numbers are, in some serious sense, like independent random variables...
.
Asymptotic density contrasts, for example, with the Schnirelmann density
Schnirelmann density
In additive number theory, the Schnirelmann density of a sequence of numbers is a way to measure how "dense" the sequence is. It is named after Russian mathematician L.G...
.
A drawback of this approach is that the asymptotic density is not defined for all subsets of
.Definition
A subset A of positive integers has natural density (or asymptotic density) α, where- 0 ≤ α ≤ 1,
if the proportion of elements of A among all natural number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s from 1 to n is asymptotic
Asymptotic analysis
In mathematical analysis, asymptotic analysis is a method of describing limiting behavior. The methodology has applications across science. Examples are...
to α as n tends to infinity.
More explicitly, if one defines for any natural number n the counting function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
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 → +∞.
Upper and lower asymptotic density
Let be a subset of the set of natural numbers For any put and .Define the upper asymptotic density
of bywhere lim sup is the limit superior.
is also known simply as the upper density of Similarly, we define
, the lower asymptotic density of , byOne may say
has asymptotic density if , in which case we put This definition can be restated in the following way:
if the limit exists.
A somewhat weaker notion of density is upper Banach density; given a set
, define asIf one were to write a subset of
as an increasing sequencethen
and
if the limit exists.
Examples
- If d(A) exists for some set A, then for the complement setComplement (set theory)In set theory, a complement of a set A refers to things not in , A. The relative complement of A with respect to a set B, is the set of elements in B but not in A...
we have d(Ac) = 1 - d(A). - Obviously, d(N) = 1.
- For any finite set F of positive integers, d(F) = 0.
- If
is the set of all squares, then d(A) = 0. - If
is the set of all even numbers, then d(A) = 1/2. Similarly, for any arithmetical progression 
we get d(A) = 1/a. - For the set P of all primePrime numberA prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
s we get from the prime number theoremPrime number theoremIn number theory, the prime number theorem describes the asymptotic distribution of the prime numbers. The prime number theorem gives a general description of how the primes are distributed amongst the positive integers....
d(P) = 0. - The set of all square-free integerSquare-free integerIn mathematics, a square-free, or quadratfrei, integer is one divisible by no perfect square, except 1. For example, 10 is square-free but 18 is not, as it is divisible by 9 = 32...
s has density
- The density of the set of abundant numbers is known to be between 0.2474 and 0.2480.
- 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
- Consider an equidistributed sequence
in 
and define a monotone family 
of sets :
- Then, by definition,
for all 
.