Upper Density
   HOME

TheInfoList



OR:

In
number theory Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers (for example ...
, natural density, also referred to as asymptotic density or arithmetic density, is one method to measure how "large" a
subset In mathematics, a Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they a ...
of the
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
of
natural number In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
s is. It relies chiefly on the
probability Probability is a branch of mathematics and statistics concerning events and numerical descriptions of how likely they are to occur. The probability of an event is a number between 0 and 1; the larger the probability, the more likely an e ...
of encountering members of the desired subset when combing through the interval as grows large. For example, it may seem intuitively that there are more
positive integer In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positiv ...
s than perfect squares, because every perfect square is already positive and yet 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 In mathematics, a Set (mathematics), set is countable if either it is finite set, 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 fro ...
and can therefore be put in
one-to-one correspondence In mathematics, a bijection, bijective function, or one-to-one correspondence is a function between two sets such that each element of the second set (the codomain) is the image of exactly one element of the first set (the domain). Equivale ...
. 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 \mathbb). If an integer is randomly selected from the interval , then the probability that it belongs to is the ratio of the number of elements of in to the total number of elements in . If this probability tends to some limit as tends to infinity, then this limit is referred to as the asymptotic density of . This notion can be understood as a kind of probability of choosing a number from the set . 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, i ...
.


Definition

A subset of positive integers has natural density if the proportion of elements of among all
natural number In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
s from 1 to converges to as tends to infinity. More explicitly, if one defines for any natural number 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-orie ...
as the number of elements of less than or equal to , then the natural density of being exactly means that It follows from the definition that if a set has natural density then .


Upper and lower asymptotic density

Let A be a subset of the set of natural numbers \mathbb=\. For any n \in \mathbb, define A(n) to be the intersection A(n)=\ \cap A, and let a(n)=, A(n), be the number of elements of A less than or equal to n. Define the ''upper asymptotic density'' \overline(A) of A (also called the "upper density") by \overline(A) = \limsup_ \frac 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 ...
. Similarly, define the ''lower asymptotic density'' \underline(A) of A (also called the "lower density") by \underline(A) = \liminf_ \frac 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 A has asymptotic density d(A) if \underline(A)=\overline(A), in which case d(A) is equal to this common value. This definition can be restated in the following way: d(A)=\lim_ \frac if this limit exists. These definitions may equivalently be expressed in the following way. Given a subset A of \mathbb, write it as an increasing sequence indexed by the natural numbers: A = \. Then \underline(A) = \liminf_ \frac, \overline(A) = \limsup_ \frac and d(A) = \lim_ \frac if the limit exists. A somewhat weaker notion of density is the ''upper Banach density'' d^*(A) of a set A \subseteq \mathbb. This is defined as d^*(A) = \limsup_ \frac.


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. Th ...
''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 A^c (or ), is the set of elements not in . When all elements in the universe, i.e. all elements under consideration, are considered to be members of a given set , the absolute complement ...
with respect to \N, then ''d''(''A''c) = 1 − ''d''(''A''). ** Corollary: If F\subset \N is finite (including the case F=\emptyset), d(\N \setminus F)=1. * If d(A), d(B), and d(A \cup B) exist, then \max\ \leq d(A\cup B) \leq \min\. * If A = \ is the set of all squares, then ''d''(''A'') = 0. * If A = \ is the set of all even numbers, then ''d''(''A'') = 0.5. Similarly, for any arithmetical progression A = \ we get d(A) = \tfrac. * 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 In mathematics, the prime number theorem (PNT) describes the asymptotic analysis, asymptotic distribution of the prime numbers among the positive integers. It formalizes the intuitive idea that primes become less common as they become larger by p ...
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-fr ...
s has density \tfrac. More generally, the set of all ''n''th-power-free numbers for any natural ''n'' has density \tfrac, where \zeta(n) is the
Riemann zeta function The Riemann zeta function or Euler–Riemann zeta function, denoted by the Greek letter (zeta), is a mathematical function of a complex variable defined as \zeta(s) = \sum_^\infty \frac = \frac + \frac + \frac + \cdots for and its analytic c ...
. * The set of
abundant number In number theory, an abundant number or excessive number is a positive integer 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 ...
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 A = \bigcup_^\infty \left \ 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 \overline d(A)=\lim_\frac=\lim_ \frac = \frac 23, whereas its lower density is \underline d(A)=\lim_\frac=\lim_ \frac = \frac 13. * 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_\cdots b_0.a_1a_2\cdots Here is the decimal separator ...
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.) * 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 ,1/math> and define a monotone family \_ of sets: A_x:=\. Then, by definition, d(A_x)= x for all x. * If ''S'' is a set of positive upper density then
Szemerédi's theorem In arithmetic combinatorics, Szemerédi's theorem is a result concerning arithmetic progressions in subsets of the integers. In 1936, Erdős and Turán conjectured that every set of integers ''A'' with positive natural density contains a ''k''- ...
states that ''S'' contains arbitrarily large finite
arithmetic progression An arithmetic progression or arithmetic sequence is a sequence of numbers such that the difference from any succeeding term to its preceding term remains constant throughout the sequence. The constant difference is called common difference of that ...
s, and the
Furstenberg–Sárközy theorem In mathematics, a square-difference-free set is a set of natural numbers, no two of which differ by a square number. Hillel Furstenberg and András Sárközy proved in the late 1970s the Furstenberg–Sárközy theorem of additive number theory ...
states that some two members of ''S'' differ by a square number.


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) :\mathbf(A) = \lim_ \frac \sum_ \frac \ . 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, when it exists, is equal to the logarithmic density.


See also

* Dirichlet density *
Erdős conjecture on arithmetic progressions Erdős' conjecture on arithmetic progressions, often referred to as the Erdős–Turán conjecture, is a conjecture in arithmetic combinatorics (not to be confused with the Erdős–Turán conjecture on additive bases). It states that if the sum ...


Notes


References

* * * * {{PlanetMath attribution, id=2861, title=Asymptotic density Number theory Combinatorics