Innumber theory,natural density, also referred to asasymptotic density orarithmetic density, is a measure of how "large" asubset of theset ofnatural numbers is. It relies chiefly on theprobability of encountering members of the desired subset when combing through theinterval[1,n] asn grows large.

For example, it may seem intuitively that there are morepositive integers thanperfect 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 areinfinite andcountable and can therefore be put inone-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 (seeSchnirelmann density, which is similar to natural density but defined for all subsets of${\displaystyle \mathbb{N}}$).

If an integer is randomly selected from the interval[1,n], then the probability that it belongs toA is the ratio of the number of elements ofA in[1,n] to the total number of elements in[1,n]. If this probability tends to somelimit asn tends to infinity, then this limit is referred to as the asymptotic density ofA. This notion can be understood as a kind of probability of choosing a number from the setA. Indeed, the asymptotic density (as well as some other types of densities) is studied inprobabilistic number theory.

A subsetA of positive integers has natural densityα if the proportion of elements ofA among allnatural numbers from1 ton converges toα asn tends to infinity.

More explicitly, if one defines for any natural numbern the countingfunctiona(n) as the number of elements ofA less than or equal ton, then the natural density ofA beingα exactly means that^[1]

It follows from the definition that if a setA has natural densityα then0 ≤α ≤ 1.

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

Similarly, define thelower asymptotic density${\displaystyle \underset{\_}{d}(A)}$ of${\displaystyle A}$ (also called the "lower density") by$${\displaystyle \underset{\_}{d}(A)=\underset{n\to \mathrm{\infty }}{lim inf}\frac{a(n)}{n}}$$where lim inf is thelimit inferior. One may say${\displaystyle A}$ has asymptotic density${\displaystyle d(A)}$ if${\displaystyle \underset{\_}{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)=\underset{n\to \mathrm{\infty }}{lim}\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:Then$${\displaystyle \underset{\_}{d}(A)=\underset{n\to \mathrm{\infty }}{lim inf}\frac{n}{a_n},}$$$${\displaystyle \overline{d}(A)=\underset{n\to \mathrm{\infty }}{lim sup}\frac{n}{a_n}}$$and$${\displaystyle d(A)=\underset{n\to \mathrm{\infty }}{lim}\frac{n}{a_n}}$$if the limit exists.

A somewhat weaker notion of density is theupper Banach density${\displaystyle d^{\ast }(A)}$ of a set${\displaystyle A\subseteq \mathbb{N}.}$ This is defined as^{[citation needed]}$${\displaystyle d^{\ast }(A)=\underset{N-M\to \mathrm{\infty }}{lim sup}\frac{|A\cap \{M,M+1,\dots ,N\}|}{N-M+1}.}$$

This sectionneeds additional citations forverification. Please helpimprove this article byadding 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 anyfinite setF of positive integers,d(F) = 0.
• Ifd(A) exists for some setA andA^c denotes itscomplement set with respect to${\displaystyle \mathbb{N}}$, thend(A^c) = 1 −d(A).
  • Corollary: If${\displaystyle F\subset \mathbb{N}}$ is finite (including the case${\displaystyle F=\mathrm{\varnothing }}$),${\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)\}\le d(A\cup B)\le min\{d(A)+d(B),1\}.}$$
• If${\displaystyle A=\{n^2:n\in \mathbb{N}\}}$ is the set of all squares, thend(A) = 0.
• If${\displaystyle A=\{2n:n\in \mathbb{N}\}}$ is the set of all even numbers, thend(A) = 0.5. Similarly, for any arithmetical progression${\displaystyle A=\{an+b:n\in \mathbb{N}\}}$ we get${\displaystyle d(A)=\frac{1}{a}.}$
• For the setP of allprimes we get from theprime number theorem thatd(P) = 0.
• The set of allsquare-free integers has density${\displaystyle \frac{6}{{\pi }^2}.}$ More generally, the set of allnth-power-free numbers for any naturaln has density${\displaystyle \frac{1}{\zeta (n)},}$ where${\displaystyle \zeta (n)}$ is theRiemann zeta function.
• The set ofabundant 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}^{\mathrm{\infty }}\left\{2^{2n},\dots ,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)=\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$${\displaystyle \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 whosedecimal 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] (SeeBenford's law.)
• Consider anequidistributed 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: Then, by definition,${\displaystyle d(A_x)=x}$ for all${\displaystyle x}$.
• IfS is a set of positive upper density thenSzemerédi's theorem states thatS contains arbitrarily large finitearithmetic progressions, and theFurstenberg–Sárközy theorem states that some two members ofS differ by a square number.

Other density functions on subsets of the natural numbers may be defined analogously. For example, thelogarithmic density of a setA is defined as the limit (if it exists)$${\displaystyle \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.

The intuition behind using${\displaystyle \frac{1}{n}}$ in the summand comes from the fact that theharmonic series asymptotically approaches${\displaystyle \log n+\gamma }$, where${\displaystyle \gamma =0.577\dots }$ is theEuler–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, theDavenport–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

• Nathanson, Melvyn B. (2000).Elementary Methods in Number Theory. Graduate Texts in Mathematics. Vol. 195.Springer-Verlag.ISBN 978-0387989129.Zbl 0953.11002.
• Niven, Ivan (1951)."The asymptotic density of sequences".Bulletin of the American Mathematical Society.57 (6):420–434.doi:10.1090/s0002-9904-1951-09543-9.MR 0044561.Zbl 0044.03603.
• Steuding, Jörn (2002)."Probabilistic number theory"(PDF). Archived fromthe original(PDF) on December 22, 2011. Retrieved2014-11-16.
• Tenenbaum, Gérald (1995).Introduction to analytic and probabilistic number theory. Cambridge Studies in Advanced Mathematics. Vol. 46.Cambridge University Press.Zbl 0831.11001.

This article incorporates material from Asymptotic density onPlanetMath, which is licensed under theCreative Commons Attribution/Share-Alike License.

• Number theory
• Combinatorics

• Articles with short description
• Short description is different from Wikidata
• All articles with unsourced statements
• Articles with unsourced statements from May 2024
• Articles with unsourced statements from January 2025
• Articles needing additional references from January 2025
• All articles needing additional references
• Wikipedia articles incorporating text from PlanetMath