Natural density

Template:Short descriptionIn 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 Template:Math as Template:Mvar grows large.

For example, it may seem intuitively that there are more positive integers 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 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 $\mathbb{N}$).

If an integer is randomly selected from the interval Template:Math, then the probability that it belongs to Template:Mvar is the ratio of the number of elements of Template:Mvar in Template:Math to the total number of elements in Template:Math. If this probability tends to some limit as Template:Mvar tends to infinity, then this limit is referred to as the asymptotic density of Template:Mvar. This notion can be understood as a kind of probability of choosing a number from the set Template:Mvar. Indeed, the asymptotic density (as well as some other types of densities) is studied in probabilistic number theory.

Definition

A subset Template:Mvar of positive integers has natural density Template:Mvar if the proportion of elements of Template:Mvar among all natural numbers from 1 to Template:Mvar converges to Template:Mvar as Template:Mvar tends to infinity.

More explicitly, if one defines for any natural number Template:Mvar the counting function Template:Math as the number of elements of Template:Mvar less than or equal to Template:Mvar, then the natural density of Template:Mvar being Template:Mvar exactly means that

It follows from the definition that if a set Template:Mvar has natural density Template:Mvar then Template:Math.

Upper and lower asymptotic density

Let $A$ be a subset of the set of natural numbers $\mathbb{N}=\{1,2,\dots \}.$ For any $n\in \mathbb{N}$, define $A(n)$ to be the intersection $A(n)=\{1,2,\dots ,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 $\bar{d}(A)$ of $A$ (also called the "upper density") by $$\bar{d}(A)=\underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}\frac{a(n)}{n}$$ where lim sup is the limit superior.

Similarly, define the lower asymptotic density $\underset{\_}{d}(A)$ of $A$ (also called the "lower density") by $$\underset{\_}{d}(A)=\underset{n\to \mathrm{\infty }}{\mathrm{lim\; inf}}\frac{a(n)}{n}$$ where lim inf is the limit inferior. One may say $A$ has asymptotic density $d(A)$ if $\underset{\_}{d}(A)=\bar{d}(A)$, in which case $d(A)$ is equal to this common value.

This definition can be restated in the following way: $$d(A)=\underset{n\to \mathrm{\infty }}{\lim }\frac{a(n)}{n}$$ if this limit exists.

These definitions may equivalentlyTemplate:Citation needed be expressed in the following way. Given a subset $A$ of $\mathbb{N}$, write it as an increasing sequence indexed by the natural numbers: $$A=\{a_1<a_2<\dots \}.$$ Then $$\underset{\_}{d}(A)=\underset{n\to \mathrm{\infty }}{\mathrm{lim\; inf}}\frac{n}{a_n},$$ $$\bar{d}(A)=\underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}\frac{n}{a_n}$$ and $$d(A)=\underset{n\to \mathrm{\infty }}{\lim }\frac{n}{a_n}$$ if the limit exists.

A somewhat weaker notion of density is the upper Banach density $d^{*}(A)$ of a set $A\subseteq \mathbb{N}.$ This is defined asTemplate:Citation needed $$d^{*}(A)=\underset{N-M\to \mathrm{\infty }}{\mathrm{lim\; sup}}\frac{|A\cap \{M,M+1,\dots ,N\}|}{N-M+1}.$$

Properties and examples

• For any finite set F of positive integers, d(F) = 0.
• If d(A) exists for some set A and A^c denotes its complement set with respect to $\mathbb{N}$, then d(A^c) = 1 − d(A).
  • Corollary: If $F\subset \mathbb{N}$ is finite (including the case $F=\mathrm{\varnothing }$), $d(\mathbb{N}\setminus F)=1.$
• If $d(A),d(B),$ and $d(A\cup B)$ exist, then $$\max \{d(A),d(B)\}\le d(A\cup B)\le \min \{d(A)+d(B),1\}.$$
• If $A=\{n^2:n\in \mathbb{N}\}$ is the set of all squares, then d(A) = 0.
• If $A=\{2n:n\in \mathbb{N}\}$ is the set of all even numbers, then d(A) = 0.5. Similarly, for any arithmetical progression $A=\{an+b:n\in \mathbb{N}\}$ we get $d(A)=\frac{1}{a}.$
• For the set P of all primes we get from the prime number theorem that d(P) = 0.
• The set of all square-free integers has density $\frac{6}{{\pi }^2}.$ More generally, the set of all n^th-power-free numbers for any natural n has density $\frac{1}{\zeta (n)},$ where $\zeta (n)$ is the Riemann zeta function.
• The set of abundant numbers 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 _{n=0}^{\mathrm{\infty }}\{2^{2n},\dots ,2^{2n+1}-1\}$$ 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 $$\bar{d}(A)=\underset{m\to \mathrm{\infty }}{\lim }\frac{1+2^2+\cdots +2^{2m}}{2^{2m+1}-1}=\underset{m\to \mathrm{\infty }}{\lim }\frac{2^{2m+2}-1}{3(2^{2m+1}-1)}=\frac{2}{3},$$ whereas its lower density is $$\underset{\_}{d}(A)=\underset{m\to \mathrm{\infty }}{\lim }\frac{1+2^2+\cdots +2^{2m}}{2^{2m+2}-1}=\underset{m\to \mathrm{\infty }}{\lim }\frac{2^{2m+2}-1}{3(2^{2m+2}-1)}=\frac{1}{3}.$$
• 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. (See Benford's law.)
• Consider an equidistributed sequence $\{{\alpha }_n{\}}_{n\in \mathbb{N}}$ in $[0,1]$ and define a monotone family $\{A_x{\}}_{x\in [0,1]}$ of sets: $$A_x:=\{n\in \mathbb{N}:{\alpha }_n<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 states that S contains arbitrarily large finite arithmetic progressions, and the Furstenberg–Sárközy theorem 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)

$\mathit{\delta }(A)=\underset{x\to \mathrm{\infty }}{\lim }\frac{1}{\log x}\sum _{n\in A,n\le x}\frac{1}{n}.$

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

References

• Template:Cite book
• Template:Cite journal
• Template:Cite web
• Template:Cite book