Natural density

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 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.

DefinitionEdit

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 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[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 densityEdit

Let   be a subset of the set of natural numbers   For any   put   and  .

Define the upper asymptotic density (also called the "upper density")   of   by

 

where lim sup is the limit superior.   is also known simply as the upper density of  

Similarly,  , the lower asymptotic density (also called the "lower density") of  , is defined by

 

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 the limit exists.[2]

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

 

then

 
 

and   if the limit exists.

A somewhat weaker notion of density is the upper Banach density; given a set  , define   as

 

Properties and examplesEdit

  • 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   and   exist, then
 
  • 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) = 0.5. Similarly, for any arithmetical progression   we get  
  • The set of all square-free integers 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 numbers has non-zero density.[3] 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.[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.)
  • Consider an equidistributed sequence   in   and define a monotone family   of sets:
 
Then, by definition,   for all  .

Other density functionsEdit

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 and logarithmic density are equal.[5]

NotesEdit

  1. ^ a b Tenenbaum (1995) p.261
  2. ^ Nathanson (2000) pp.256–257
  3. ^ Hall, Richard R.; Tenenbaum, Gérald (1988). Divisors. Cambridge Tracts in Mathematics. 90. Cambridge: Cambridge University Press. p. 95. ISBN 978-0-521-34056-4. Zbl 0653.10001.
  4. ^ Deléglise, Marc (1998). "Bounds for the density of abundant integers". Experimental Mathematics. 7 (2): 137–143. CiteSeerX 10.1.1.36.8272. doi:10.1080/10586458.1998.10504363. ISSN 1058-6458. MR 1677091. Zbl 0923.11127.
  5. ^ Hall, Richard R. (1996), Sets of multiples, Cambridge Tracts in Mathematics, 118, Cambridge University Press, Cambridge, Theorem 0.2, p. 5, doi:10.1017/CBO9780511566011, ISBN 978-0-521-40424-2, MR 1414678

See alsoEdit

ReferencesEdit

This article incorporates material from Asymptotic density on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.