In
number theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Mat ...
, 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 number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''cardinal ...
s is. It relies chiefly on the
probability
Probability is the branch of mathematics concerning numerical descriptions of how likely an event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and 1, where, roughly speakin ...
of encountering members of the desired subset when combing through the
interval 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
Infinite may refer to:
Mathematics
* Infinite set, a set that is not a finite set
*Infinity, an abstract concept describing something without any limit
Music
*Infinite (group), a South Korean boy band
*''Infinite'' (EP), debut EP of American m ...
and
countable
In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers ...
and can therefore be put in
one-to-one correspondence
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...
. 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
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 Lev Schnirelmann, who was the first to study it.Schnirelmann, L.G. (1930).On the ...
, which is similar to natural density but defined for all subsets of
).
If an integer is randomly selected from the interval , then the probability that it belongs to ''A'' is the ratio of the number of elements of ''A'' in to the total number of elements in . 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
In mathematics, Probabilistic number theory is a subfield of number theory, which explicitly uses probability to answer questions about the integers and integer-valued functions. One basic idea underlying it is that different prime numbers are, in ...
.
Definition
A subset ''A'' of positive integers has natural density ''α'' if the proportion of elements of ''A'' among all
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''cardinal ...
s from 1 to ''n'' converges to ''α'' as ''n'' tends to infinity.
More explicitly, if one defines for any natural number ''n'' the counting
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
''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 be a subset of the set of natural numbers For any , define the set as follows: Furthermore, define .
Define the ''upper asymptotic density'' (also called the "upper density") of by
:
where lim sup is the limit superior
In mathematics, the limit inferior and limit superior of a sequence can be thought of as limiting (that is, eventual and extreme) bounds on the sequence. They can be thought of in a similar fashion for a function (see limit of a function). For a ...
. is also known simply as the upper density of
Similarly, , the ''lower asymptotic density'' (also called the "lower density") of , is defined by
:
where lim inf is the limit inferior
In mathematics, the limit inferior and limit superior of a sequence can be thought of as limiting (that is, eventual and extreme) bounds on the sequence. They can be thought of in a similar fashion for a function (see limit of a function). For ...
. One may say has asymptotic density if , in which case is equal to this common value.
This definition can be restated in the following way:
:
if this limit exists.
It can be proven that the definitions imply that the following also holds. If one were to write a subset of 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''; given a set , define as
:
Properties and examples
* For any finite set
In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,
:\
is a finite set with five elements. T ...
''F'' of positive integers, ''d''(''F'') = 0.
* If ''d''(''A'') exists for some set ''A'', and ''A''c denotes its complement set
In set theory, the complement of a set , often denoted by (or ), is the set of elements not in .
When all sets in the universe, i.e. all sets under consideration, are considered to be members of a given set , the absolute complement of is t ...
with respect to then ''d''(''A''c) = 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
* For the set ''P'' of all prime
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s we get from the prime number theorem that ''d''(''P'') = 0.
* The set of all square-free integer
In mathematics, a square-free integer (or squarefree integer) is an integer which is divisible by no square number other than 1. That is, its prime factorization has exactly one factor for each prime that appears in it. For example, is square-f ...
s has density More generally, the set of all ''n''th-power-free numbers for any natural ''n'' has density where is the Riemann zeta function.
* The set of abundant number
In number theory, an abundant number or excessive number is a number for which the sum of its proper divisors is greater than the number. The integer 12 is the first abundant number. Its proper divisors are 1, 2, 3, 4 and 6 for a total of 16. Th ...
s 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 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
A decimal representation of a non-negative real number is its expression as a sequence of symbols consisting of decimal digits traditionally written with a single separator:
r = b_k b_\ldots b_0.a_1a_2\ldots
Here is the decimal separator, i ...
begins with the digit 1 similarly has no natural density: the lower density is 1/9 and the upper density is 5/9.[Tenenbaum (1995) p.261] (See Benford's law
Benford's law, also known as the Newcomb–Benford law, the law of anomalous numbers, or the first-digit law, is an observation that in many real-life sets of numerical data, the leading digit is likely to be small.Arno Berger and Theodore ...
.)
* Consider an equidistributed sequence In mathematics, a sequence (''s''1, ''s''2, ''s''3, ...) of real numbers is said to be equidistributed, or uniformly distributed, if the proportion of terms falling in a subinterval is proportional to the length of that subinterval. Such sequences ...
in