Natural density ($d(S)$)

For a set $S$ of nonnegative integers, its natural density is the limiting proportion of the first $N$ nonnegative integers that belong to $S$:provided this limit exists. Write $C_S(N)=|S\cap \{0,\dots ,N-1\}|$ for the counting function. The numerator is a finite cardinality; the denominator is exactly $N$, including zero. Every existing natural density lies between zero and one.

For the even nonnegative integers $E=\{0,2,4,\dots \}$, there are $m$ elements below $N=2m$ and $m+1$ below $N=2m+1$. Thus $C_E(N)=\lceil N/2\rceil$ using the ceiling function, and $d(E)=1/2$. For the square numbers $Q=\{0,1,4,9,\dots \}$, the exact count for $N\ge 1$ isThe floor function counts the allowed indices $1,\dots ,\lfloor \sqrt{N-1}\rfloor$, and the extra one counts zero. At $N=10$, the square numbers below ten are $0,1,4,9$, so the proportion is $4/10$; at $N=100$, it is $10/100$. The count grows like the square root of $N$, while the denominator grows like $N$.

The prime numbers also have natural density zero. If $P$ is their set, the Prime number theorem gives $C_P(N)\sim N/\log N$, hence $C_P(N)/N\to 0$. The Prime number theorem is a substantial result about the count, rather than a consequence of the fact that there are infinitely many prime numbers. ^[ref]

Why use natural density when cardinality already measures size? The even nonnegative integers, the square numbers, and the prime numbers all have the same countably infinite cardinality, yet their proportions among large initial integer intervals differ. Natural density distinguishes frequent membership from sparse membership. Equivalently, under a uniform distribution on a finite set of $N$ possible nonnegative integers, $C_S(N)/N$ is the probability of landing in $S$. A set without natural density shows why this limiting proportion need not exist.

Include the positive integers in $[1,2),[4,8),[16,32),[64,128),\dots$, and exclude the intervening integer intervals and zero. Equivalently, include $[2^{2k},2^{2k+1})\cap \mathbb{Z}$ for $k\ge 0$. Each included block is large enough to raise the running proportion; the following excluded block lowers it again.

With $C_A(N)=|A\cap \{0,\dots ,N-1\}|$, the exact boundary counts follow from a geometric series:The first sum is empty at $k=0$. Dividing by the corresponding boundary, rather than using one denominator for both, givesFor example, $C_A(16)=1+4=5$, whereas $C_A(32)=1+4+16=21$, yielding proportions $5/16$ and $21/32$. For $4^k\le N\le 2\cdot 4^k$, the exact count is $(4^k-1)/3+N-4^k$; for $2\cdot 4^k\le N\le 4^{k+1}$ it stays $(4^{k+1}-1)/3$. Hence the proportion increases through each included block and decreases through each excluded block. These boundary subsequences give the actual limit inferior and limit superior:Since these differ, $A$ has no natural density. Its upper asymptotic density still records its largest limiting proportion.

For a subset $A$ of the positive integers, its upper asymptotic density isThe limit superior keeps the largest limiting proportion even when the running proportions oscillate. Because they lie in $[0,1]$, this limit superior always exists in $[0,1]$. If natural density exists, upper asymptotic density equals it.

The convention here uses $1,\dots ,N$, while natural density above uses $0,\dots ,N-1$. Replacing one interval by the other changes a count by at most one, so the proportions differ by at most $1/N$ and have the same limit superior. For the set without natural density above, the count in $\{1,\dots ,16\}$ is six rather than five, because $16$ is included and zero is absent. Nevertheless its upper asymptotic density is exactly $2/3$. The even positive integers have upper asymptotic density $1/2$ and the prime numbers have upper asymptotic density zero.

The useful feature is that a large proportion along arbitrarily large initial integer intervals already supplies structure. The Szemerédi theorem says that positive upper asymptotic density forces arithmetic progressions of every finite length, with positive common difference, even without an existing natural density. Szemerédi's 1975 paper resolved this general finite-length problem; it makes density a bridge from counting to additive structure. ^[ref]

An increasing sequence of integers has full density when its range has natural density one. Convergence in density of a sequence means that, for each fixed tolerance, the exceptional indices have natural density zero.