Natural density (source code)

= Natural density
{title2=$d(S)$}
{wiki}

For a <set> $S$ of <nonnegative integers>, its natural density is the limiting proportion of the first $N$ <nonnegative integers> that belong to $S$:
$$
d(S)=\lim_{N\to\infty}\frac{|S\cap\{0,\ldots,N-1\}|}{N},
$$
provided this <limit> exists. Write $C_S(N)=|S\cap\{0,\ldots,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,\ldots\}$, 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,\ldots\}$, the exact count for $N\geq1$ is
$$
C_Q(N)=\lfloor\sqrt{N-1}\rfloor+1,\qquad d(Q)=0.
$$
The <floor function> counts the allowed indices $1,\ldots,\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\to0$. 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>. https://math.mit.edu/classes/18.785/2025/LectureNotes16.pdf[Andrew V. Sutherland, MIT 18.785 lecture 16, Riemann's zeta function and the prime number theorem, 2025]{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.

\Image[/natural-density-samples.png]
{title=Exact proportions below N: even integers, squares, and an alternating-block set}
{description=Every point uses the count in $\{0,\ldots,N-1\}$ divided by $N$, with zero included among the even <integers> and <square numbers>. The right panel marks exact block-boundary counts for a <set without natural density>. Its low and high proportions approach $1/3$ and $2/3$ along different <subsequences>.}