Natural density

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]

It follows from the definition that if a set A has natural density α then 0 ≤ α ≤ 1.

Let ${\displaystyle A}$ be a subset of the set of natural numbers ${\displaystyle \mathbb {N} =\{1,2,\ldots \}.}$ For any ${\displaystyle n\in \mathbb {N} }$, define ${\displaystyle A(n)}$ to be the intersection ${\displaystyle A(n)=\{1,2,\ldots ,n\}\cap A,}$ and let ${\displaystyle a(n)=|A(n)|}$ be the number of elements of ${\displaystyle A}$ less than or equal to ${\displaystyle n}$.

Define the upper asymptotic density ${\displaystyle {\overline {d}}(A)}$ of ${\displaystyle A}$ (also called the "upper density") by $${\displaystyle {\overline {d}}(A)=\limsup _{n\rightarrow \infty }{\frac {a(n)}{n}}}$$ where lim sup is the limit superior.

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

This definition can be restated in the following way: $${\displaystyle d(A)=\lim _{n\rightarrow \infty }{\frac {a(n)}{n}}}$$ if this limit exists.^[2]

These definitions may equivalently^{[citation needed]} be expressed in the following way. Given a subset ${\displaystyle A}$ of ${\displaystyle \mathbb {N} }$, write it as an increasing sequence indexed by the natural numbers: $${\displaystyle A=\{a_{1}<a_{2}<\ldots \}.}$$ Then $${\displaystyle {\underline {d}}(A)=\liminf _{n\rightarrow \infty }{\frac {n}{a_{n}}},}$$ $${\displaystyle {\overline {d}}(A)=\limsup _{n\rightarrow \infty }{\frac {n}{a_{n}}}}$$ and $${\displaystyle d(A)=\lim _{n\rightarrow \infty }{\frac {n}{a_{n}}}}$$ if the limit exists.

A somewhat weaker notion of density is the upper Banach density ${\displaystyle d^{*}(A)}$ of a set ${\displaystyle A\subseteq \mathbb {N} .}$ This is defined as^{[citation needed]} $${\displaystyle d^{*}(A)=\limsup _{N-M\rightarrow \infty }{\frac {|A\cap \{M,M+1,\ldots ,N\}|}{N-M+1}}.}$$

This section needs additional citations for verification. Please help improve this article by adding citations to reliable sources in this section. Unsourced material may be challenged and removed. Find sources: "Natural density" – news · newspapers · books · scholar · JSTOR (January 2025) (Learn how and when to remove this message)

• 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 ${\displaystyle \mathbb {N} }$, then d(A^c) = 1 − d(A).
  • Corollary: If ${\displaystyle F\subset \mathbb {N} }$ is finite (including the case ${\displaystyle F=\emptyset }$), ${\displaystyle d(\mathbb {N} \setminus F)=1.}$
• If ${\displaystyle d(A),d(B),}$ and ${\displaystyle d(A\cup B)}$ exist, then $${\displaystyle \max\{d(A),d(B)\}\leq d(A\cup B)\leq \min\{d(A)+d(B),1\}.}$$
• If ${\displaystyle A=\{n^{2}:n\in \mathbb {N} \}}$ is the set of all squares, then d(A) = 0.
• If ${\displaystyle A=\{2n:n\in \mathbb {N} \}}$ is the set of all even numbers, then d(A) = 0.5. Similarly, for any arithmetical progression ${\displaystyle A=\{an+b:n\in \mathbb {N} \}}$ we get ${\displaystyle d(A)={\tfrac {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 ${\displaystyle {\tfrac {6}{\pi ^{2}}}.}$ More generally, the set of all nth-power-free numbers for any natural n has density ${\displaystyle {\tfrac {1}{\zeta (n)}},}$ where ${\displaystyle \zeta (n)}$ 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 is between 0.2474 and 0.2480.^[4]
• The set $${\displaystyle A=\bigcup _{n=0}^{\infty }\left\{2^{2n},\ldots ,2^{2n+1}-1\right\}}$$ 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 $${\displaystyle {\overline {d}}(A)=\lim _{m\to \infty }{\frac {1+2^{2}+\cdots +2^{2m}}{2^{2m+1}-1}}=\lim _{m\to \infty }{\frac {2^{2m+2}-1}{3(2^{2m+1}-1)}}={\frac {2}{3}},}$$ whereas its lower density is $${\displaystyle {\underline {d}}(A)=\lim _{m\to \infty }{\frac {1+2^{2}+\cdots +2^{2m}}{2^{2m+2}-1}}=\lim _{m\to \infty }{\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.^[1] (See Benford's law.)
• Consider an equidistributed sequence ${\displaystyle \{\alpha _{n}\}_{n\in \mathbb {N} }}$ in ${\displaystyle [0,1]}$ and define a monotone family ${\displaystyle \{A_{x}\}_{x\in [0,1]}}$ of sets: $${\displaystyle A_{x}:=\{n\in \mathbb {N} :\alpha _{n}<x\}.}$$ Then, by definition, ${\displaystyle d(A_{x})=x}$ for all ${\displaystyle 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 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) $${\displaystyle \mathbf {\delta } (A)=\lim _{x\to \infty }{\frac {1}{\log x}}\sum _{n\in A,n\leq x}{\frac {1}{n}}.}$$

Upper and lower logarithmic densities are defined analogously.

The intuition behind using ${\displaystyle {\tfrac {1}{n}}}$ in the summand comes from the fact that the harmonic series asymptotically approaches ${\displaystyle \log n+\gamma }$, where ${\displaystyle \gamma =0.577\ldots }$ is the Euler–Mascheroni constant. Thus, this definition ensures that the logarithmic density of the natural numbers is ${\displaystyle 1}$.

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.^[5]

• Dirichlet density
• Erdős conjecture on arithmetic progressions