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. This notion will be described mathematically, and we will see that the squares have a 'density' which is lower than the density of the natural numbers.
If an integer is randomly selected 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 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.
A subset A of positive integers has natural density (or asymptotic density) α, where
- 0 ≤ α ≤ 1,
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
- 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 by
where lim sup is the limit superior. is also known simply as the upper density of
Similarly, , the lower asymptotic 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.
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
and if the limit exists.
A somewhat weaker notion of density is upper Banach density; given a set , define as
- If d(A) exists for some set A, then for the complement set we have d(Ac) = 1 − d(A).
- The density d(N) of the entire set of natural numbers is equal to 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) = 0.5 . Similarly, for any arithmetical progression we get d(A) = 1/a.
- For the set P of all primes we get from the prime number theorem d(P) = 0.
- The set of all square-free integers has density
- The set of abundant numbers has non-zero density. 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.
- 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 .
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 is defined as the limit (if it exists)
Upper and lower logarithmic densities are defined analogously as well.
- Nathanson (2000) pp.256–257
- Hall, Richard R.; Tenenbaum, Gérald (1988). Divisors. Cambridge Tracts in Mathematics 90. Cambridge: Cambridge University Press. p. 95. ISBN 0-521-34056-X. Zbl 0653.10001.
- Deléglise, Marc (1998). "Bounds for the density of abundant integers". Experimental Mathematics 7 (2): 137–143. ISSN 1058-6458. MR 1677091. Zbl 0923.11127.
- Nathanson, Melvyn B. (2000). Elementary Methods in Number Theory. Graduate Texts in Mathematics 195. Springer-Verlag. ISBN 0387989129. Zbl 0953.11002.
- Ostmann, H. H. (1956). Additive Zahlentheorie I. Ergebnisse der Mathematik und ihrer Grenzgebiete (in German) 7. Berlin-Göttingen-Heidelberg: Springer-Verlag. Zbl 0072.03101.
- Steuding, Jörn. "Probabilistic number theory". Retrieved 2005-10-06.
- Tenenbaum, Gérald (1995). Introduction to analytic and probabilistic number theory. Cambridge Studies in Advanced Mathematics 46. Cambridge: Cambridge University Press. Zbl 0831.11001.