In number theory, asymptotic density is one of the characteristics that helps to estimate how large a subset of the set of natural numbers is. .
Intuitively, we feel that there are more “ odd ” numbers than squares ; however, the set of odd numbers is not really “larger” than the set of squares: both sets are infinite and countable , and thus can be brought into correspondence “one to one” with each other. Obviously, to formalize our intuitive concept, we need a better way.
If we randomly select a number from the set , then the probability that it belongs to A will be equal to the ratio of the number of elements in the set to the number n . If this probability tends to a certain limit when n tends to infinity, this limit is called the asymptotic density A. We see that this concept can be considered as the probability of choosing a number from the set A. Indeed, asymptotic density (as well as some other types of density) is studied in probabilistic number theory ( English Probabilistic number theory ).
Asymptotic density differs, for example, from sequence density . The negative side of this approach is that the asymptotic density is not defined for all subsets .
- 1 Definition
- 1.1 Upper and lower asymptotic densities
- 2 Examples
- 3 References
Subset positive numbers has an asymptotic density where if the limit of the ratio of the number of elements not exceeding to at exists and is equal .
More strictly, if we define for any natural number counting function as the number of elements not exceeding , then the equality of the asymptotic density of the set the number exactly means that
Upper and Lower Asymptotic Density
Let be Is a subset of the set of natural numbers For anyone put and .
We determine the upper asymptotic density many as
where lim sup is the partial limit of the sequence . also known as upper density
We similarly define lower asymptotic density as
Will talk, has an asymptotic density , if . In this case, we will assume
This definition can be reformulated:
if the limit exists and is finite.
A slightly weaker concept of density = upper Banach density ; take , define as
If we write a subset as an increasing sequence
and if limit exists.
- Obviously, d ( ) = 1.
- If d ( A ) exists for some set A , then for its complement we have d ( A c ) = 1 - d ( A ).
- For any finite set of positive numbers F, we have 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. Similarly, for any arithmetic progression we get d (A) = 1 / a .
- For the set P of all primes , we get d (P) = 0 (see Theorem on the distribution of primes ).
- The set of all squareless numbers has a density
- The density of the set of excess numbers is between 0.2474 and 0.2480.
- A bunch of numbers, whose binary representation contains an odd number of digits, is an example of a set that does not have asymptotic density, since the upper density is
- while lower