Fact-checked by Grok 2 weeks ago

Natural density

In number theory, the natural density (also known as asymptotic density) of a subset A of the natural numbers \mathbb{N} is a measure of its "size" relative to \mathbb{N}, defined as the limit d(A) = \lim_{n \to \infty} \frac{|A \cap \{1, 2, \dots, n\}|}{n}, provided this limit exists.^[1]^[2] This concept quantifies the proportion of natural numbers up to n that belong to A as n grows arbitrarily large, capturing the intuitive notion of how "dense" A is within the naturals.^[1] Key properties of natural density include that it takes values in [0, 1], with d(\mathbb{N}) = 1 and d(\emptyset) = 0; finite sets have density 0; and if A \subseteq B, then d(A) \leq d(B).^[2] It is invariant under finite symmetric differences, meaning d(A) = d(B) if A and B differ by only finitely many elements, and it is finitely additive for disjoint sets: if A \cap B = \emptyset and the densities exist, then d(A \cup B) = d(A) + d(B).^[1] However, the limit defining d(A) does not always exist, in which case upper and lower densities can be considered as the limsup and liminf, respectively; natural density exists only when these coincide.^[1]^[3] Natural density plays a central role in analytic number theory, often used to study the distribution of primes, square-free integers, and other arithmetic sets.^[3] For instance, the set of square-free natural numbers—those not divisible by any perfect square other than 1—has natural density \frac{6}{\pi^2} \approx 0.6079, a result originally due to Gegenbauer in 1885 and reflecting the probability that a random integer is square-free. When natural density fails to exist, related notions like Dirichlet density provide alternatives, which always agree with natural density when the latter is defined and are crucial for theorems such as the Chebotarev density theorem in algebraic number theory.^[3]

Introduction

Overview

Natural density serves as a fundamental measure for assessing the "size" of subsets of the natural numbers, capturing their relative prevalence in the sequence of positive integers. Intuitively, for a subset A of the natural numbers, the natural density represents the limiting proportion of elements from A that appear among the first n natural numbers as n becomes arbitrarily large. This proportion offers a sense of how densely or sparsely the elements of A are distributed along the number line.^[4] This measure can be interpreted probabilistically: if one selects a natural number uniformly at random from the first n numbers and lets n tend to infinity, the natural density corresponds to the probability that the selected number belongs to A, assuming the limit exists.^[5] In contrast to simple finite counting, which fails to distinguish meaningful sizes for infinite sets, or cardinality, which equates all countably infinite subsets regardless of their distribution, natural density provides a finer asymptotic gauge of relative abundance.^[4] The concept presupposes basic familiarity with the natural numbers and limits from real analysis, employing asymptotic behavior—such as proportions evaluated at large n—without requiring derivations of limiting processes. If the natural density exists for a subset, it necessarily falls within the interval [0, 1]; however, not all subsets possess a natural density, as the relevant proportions may oscillate indefinitely without converging, in which case upper and lower densities offer bounding refinements.^[4]

Historical development

The concept of natural density traces its origins to 19th-century developments in infinite series and Diophantine approximation, where early notions of proportional distribution among natural numbers began to emerge. A pivotal contribution came from Peter Gustav Lejeune Dirichlet in 1849, who computed the probability that two randomly selected natural numbers are coprime as \frac{6}{\pi^2}, introducing density-like ideas in the context of arithmetic progressions and the distribution of integers.^[6] The formalization of asymptotic density occurred in the early 20th century through the lens of probabilistic number theory, pioneered by G. H. Hardy and J. E. Littlewood between 1914 and 1920. Their work in probabilistic number theory during the early 20th century helped formalize the use of asymptotic density, particularly in the context of prime representations, where they employed density to quantify the likelihood of certain prime configurations. Key milestones include Edmund Landau's extension to upper and lower asymptotic densities in his 1909 Handbuch der Lehre von der Verteilung der Primzahlen, which provided tools to handle sets where the standard density limit does not exist. Additionally, the prime number theorem, independently proved by Jacques Hadamard and Charles Jean de la Vallée Poussin in 1896, carried profound density implications by establishing that the proportion of primes up to x is asymptotically \frac{x}{\log x}, implying zero natural density for primes while refining their distribution.^[7] In the modern era, natural density played a central role in Endre Szemerédi's 1975 theorem, which asserts that any subset of the natural numbers with positive upper density contains arbitrarily long arithmetic progressions. Post-2000 applications in ergodic theory have further expanded its scope, as seen in the 2004 Green-Tao theorem, which uses ergodic methods to prove the existence of arbitrarily long arithmetic progressions among primes. The term "natural density" solidified in the mid-20th century, serving to distinguish this combinatorial measure from measure-theoretic densities in broader analysis.^[8]^[9]

Mathematical Foundations

Definition of natural density

In number theory, the natural density of a subset A \subseteq \mathbb{N} of the natural numbers is defined as

d(A) = \lim_{n \to \infty} \frac{|A \cap \{1, 2, \dots, n\}|}{n},

provided that the limit exists.^[10] This limit, when it exists, provides a measure of the asymptotic proportion of natural numbers belonging to A.^[11] To formalize the notation, let a(n) = |A \cap \{1, \dots, n\}| denote the number of elements of A up to n. Then the natural density is given by

d(A) = \lim_{n \to \infty} \frac{a(n)}{n},

if the limit converges.^[11] The existence of this limit is a necessary condition for d(A) to be defined, and when it exists, d(A) is a real number bounded between 0 and 1 inclusive.^[12] If d(A) exists and equals 0, then A is an infinite set that is asymptotically negligible compared to \mathbb{N}, such as sparse sets where elements grow sufficiently rapidly.^[11] Conversely, cofinite sets, which omit only finitely many natural numbers, have natural density 1.^[10] The natural density is translation-invariant under fixed shifts: for any fixed integer k, d(A + k) = d(A), where A + k = \{ a + k : a \in A \}.^[12] However, it is not invariant under arbitrary perturbations, such as scalings or more complex transformations.^[12] When the limit defining d(A) fails to exist, upper and lower asymptotic densities serve as tools to quantify partial sizes of A.^[10]

Upper and lower asymptotic densities

When the natural density of a subset A \subseteq \mathbb{N} fails to exist, the upper and lower asymptotic densities provide measures of its "size" that capture the limiting behavior through the supremum and infimum of the limit points of the proportions |A \cap [1,n]| / n as n \to \infty. Specifically, the upper asymptotic density is defined as

\bar{d}(A) = \limsup_{n \to \infty} \frac{|A \cap [1,n]|}{n},

and the lower asymptotic density as

\underline{d}(A) = \liminf_{n \to \infty} \frac{|A \cap [1,n]|}{n}.

These quantities always satisfy $0 \leq \underline{d}(A) \leq \bar{d}(A) \leq 1, with the natural density existing if and only if \underline{d}(A) = \bar{d}(A).^[13] The difference between \bar{d}(A) and \underline{d}(A) quantifies the oscillation in the growth of |A \cap [1,n]|, highlighting cases where the proportion does not converge. For instance, the set of positive integers whose decimal expansion begins with the digit 1 has no natural density, as its lower and upper asymptotic densities differ, though it possesses a Dirichlet density of \log_{10} 2 \approx 0.3010. Such examples demonstrate how asymptotic densities extend the natural density concept to non-convergent scenarios, where the limsup and liminf detect the range of accumulation points in the sequence of partial proportions.^[13] In analytic number theory, the upper asymptotic density plays a key role in structural theorems; for example, Roth's theorem asserts that any subset of the integers with positive upper density contains a three-term arithmetic progression. Moreover, the upper density furnishes an upper bound on the growth of sets with zero lower density, constraining their possible configurations in problems involving additive structure. Computationally, these densities can be estimated via Cesàro means applied to the sequence of partial proportions a(n)/n, where the summability method aligns with the asymptotic behavior captured by the limsup and liminf.^[14]

Properties

Basic properties

Natural density exhibits several fundamental properties that follow directly from its definition as the limit of the proportion of elements up to n as n approaches infinity. One key property is monotonicity: if A \subseteq B \subseteq \mathbb{N}, and both sets have natural densities, then d(A) \leq d(B).^[15] This arises because the counting function for A is always less than or equal to that for B, preserving the inequality in the limit.^[15] The density of the complement is also well-behaved: if A \subseteq \mathbb{N} has natural density d(A), then its complement A^c = \mathbb{N} \setminus A has natural density d(A^c) = 1 - d(A).^[16] This property ensures that densities sum to 1 for complementary sets, mirroring the total measure of \mathbb{N}. Consequently, any cofinite set (the complement of a finite set) has natural density 1, while finite sets have natural density 0.^[17]^[16] For disjoint sets, natural density is finitely additive under certain conditions: if A and B are disjoint subsets of \mathbb{N} with natural densities d(A) and d(B), and d(A) + d(B) \leq 1, then d(A \cup B) = d(A) + d(B).^[15] This additivity holds for finite collections of disjoint sets whose densities sum to at most 1, reflecting the additive nature of the underlying counting functions. However, natural density is not countably additive, unlike Lebesgue measure on the reals. A counterexample involves the countable disjoint union of singletons \{n\} for n \in \mathbb{N}, each with density 0, whose union is \mathbb{N} with density 1.^[18] This limitation highlights that natural density, while useful for asymptotic behavior, does not form a full measure in the sigma-additive sense.

Properties under union and complement

The natural density behaves in a controlled manner under set operations, though it is not a full probability measure due to lack of countable additivity. When the natural densities d(A) and d(B) exist, the density of their union satisfies the subadditivity inequality d(A \cup B) \leq d(A) + d(B), while the density of their intersection satisfies the superadditivity inequality d(A \cap B) \geq d(A) + d(B) - 1. These bounds follow from the finite additivity of density for disjoint sets and the fact that | (A \cup B) \cap [1,n] | + | (A \cap B) \cap [1,n] | = | A \cap [1,n] | + | B \cap [1,n] |. Combining subadditivity with monotonicity (where A \subseteq A \cup B implies d(A) \leq d(A \cup B)), the density of the union also satisfies \max( d(A), d(B) ) \leq d(A \cup B) \leq \min( d(A) + d(B), 1 ). For finite unions, these properties extend iteratively: for disjoint sets A_1, \dots, A_k with densities, d( \bigcup_{i=1}^k A_i ) = \sum_{i=1}^k d(A_i ), and the subadditivity and monotonicity bounds apply to the general case by repeated application. For sets where the natural density may not exist, the upper and lower asymptotic densities provide extensions of these properties. The upper asymptotic density \bar{d} is subadditive under union: \bar{d}(A \cup B) \leq \bar{d}(A) + \bar{d}(B), and finitely subadditive for multiple sets by iteration. It also inherits monotonicity: A \subseteq B implies \bar{d}(A) \leq \bar{d}(B), yielding \max( \bar{d}(A), \bar{d}(B) ) \leq \bar{d}(A \cup B) \leq \min( \bar{d}(A) + \bar{d}(B), 1 ). The lower asymptotic density \underline{d} is superadditive under union: \underline{d}(A \cup B) \geq \underline{d}(A) + \underline{d}(B), with the bound adjusted to \max( \underline{d}(A), \underline{d}(B) ) \leq \underline{d}(A \cup B) \leq 1 following from monotonicity. For intersections, the upper density satisfies \bar{d}(A \cap B) \leq \min( \bar{d}(A), \bar{d}(B) ), while the lower density obeys \underline{d}(A \cap B) \geq \max( \underline{d}(A) + \underline{d}(B) - 1, 0 ). These extend iteratively to finite collections, preserving the lattice operations of union and intersection within bounds. Under complement, the upper and lower densities relate directly: the upper density of the complement is \bar{d}(A^c) = 1 - \underline{d}(A), and the lower density of the complement is \underline{d}(A^c) = 1 - \bar{d}(A). This relation ensures that the properties under union and intersection are consistent with complements, as A \cap B = (A^c \cup B^c)^c. For the Boolean algebra generated by a family of sets with defined densities, the induced upper and lower densities preserve the distributive lattice properties of unions and intersections via the above inequalities, but they do not form a full measure algebra due to failure of countable additivity and the non-trivial ideal of zero-density sets.

Examples and Illustrations

Arithmetic progressions and simple sets

One of the simplest examples of a set with positive natural density is the set of even natural numbers, A = \{ 2k \mid k \in \mathbb{N} \}. The number of even numbers up to n is \lfloor n/2 \rfloor, so the proportion a(n)/n \approx 1/2 as n \to \infty, yielding d(A) = 1/2.^[19] More generally, consider an infinite arithmetic progression with first term a (where $0 < a \leq d) and common difference d \geq 1, given by B = \{ a + kd \mid k = 0, 1, 2, \dots \}. This is the set of natural numbers congruent to a modulo d. The residues modulo d are uniformly distributed among the natural numbers, so the proportion of elements in B up to n is approximately $1/d. Specifically, the number of terms up to n is \lfloor (n - a)/d \rfloor + 1 \approx n/d, and thus d(B) = 1/d.^[13] This derivation follows from the periodic nature of the progression, where each residue class modulo d occurs equally often in the sequence of natural numbers. In contrast, bounded sets illustrate natural density zero. Any finite set F \subseteq \mathbb{N} has only finitely many elements, so for sufficiently large n, |F \cap \{1, \dots, n\}| is constant while the denominator n grows without bound, giving d(F) = 0.^[20] Sparse sets like the powers of 2, C = \{ 2^k \mid k = 0, 1, 2, \dots \}, also have density zero. The number of such powers up to n is \lfloor \log_2 n \rfloor + 1 \approx \log_2 n, so the proportion |\log_2 n| / n \to 0 as n \to \infty. This sparsity arises because the elements grow exponentially, outpacing linear growth in the denominator.^[19] A key distinction is that every infinite arithmetic progression with fixed difference d has positive density $1/d > 0, due to its periodic structure. This contrasts with non-periodic sets, which may lack density altogether or have density zero despite being infinite, highlighting how regularity enables computability of natural density.^[19]

Sets from number theory

In number theory, the set of prime numbers provides a classic example of a set with natural density zero. The Prime Number Theorem establishes that the number of primes not exceeding n, denoted \pi(n), satisfies \pi(n) \sim \frac{n}{\ln n} as n \to \infty. Consequently, the ratio \frac{\pi(n)}{n} \to 0, confirming that the natural density of the primes is zero.^[21] Square-free integers, which are those not divisible by any perfect square other than 1, exhibit a positive natural density. This density equals \frac{6}{\pi^2} \approx 0.607927, derived from the fact that the proportion of integers avoiding divisibility by p^2 for each prime p is \prod_p (1 - p^{-2}) = \frac{1}{\zeta(2)}, where \zeta(2) = \frac{\pi^2}{6} is the value of the Riemann zeta function at 2. The set of perfect squares also has natural density zero. The count of perfect squares up to n is \lfloor \sqrt{n} \rfloor \sim \sqrt{n}, so the ratio \frac{\sqrt{n}}{n} = n^{-1/2} \to 0 as n \to \infty.^[22] Abundant numbers, defined as positive integers n for which the sum of proper divisors exceeds n (or equivalently, the sum of all divisors \sigma(n) > 2n), possess a positive natural density approximately equal to 0.2476. This value is estimated using generating functions over the divisor sums, with recent computational bounds refining it to $0.247619608 < d < 0.247620004.^[23] As an illustration of exact computation via probabilistic models on digits, consider the set of natural numbers whose base-10 digits sum to an even value. This set has natural density \frac{1}{2}, arising from the equidistribution properties of digit sequences, where the parity of the sum behaves like a fair coin flip in the asymptotic limit. Not all number-theoretic sets admit a natural density; some exhibit oscillation between lower and upper densities. For instance, the set C = \bigcup_{k=1}^\infty [2^{2k}, 2^{2k+1}) \cap \mathbb{N} has lower asymptotic density \frac{1}{3} and upper asymptotic density \frac{2}{3}, so no natural density exists. This follows from evaluating the proportion at points N = 2^{2m} (yielding approximately \frac{1}{3}) and N = 2^{2m+1} (yielding approximately \frac{2}{3}).^[24]

Applications

In analytic number theory

In analytic number theory, natural density plays a central role in quantifying the distribution of primes and integers with specified arithmetic properties, often building on the Prime Number Theorem (PNT), which asserts that the natural density of the set of primes is zero, as the proportion of primes up to x is asymptotically \frac{1}{\log x}.^[25] The PNT provides the foundational asymptotic for \pi(x) \sim \frac{x}{\log x}, enabling relative densities within subsets of integers. A key application arises in Dirichlet's theorem on primes in arithmetic progressions, which, under the prime number theorem for arithmetic progressions (PNAP), implies that for integers a and m with \gcd(a, m) = 1, the set of primes p \equiv a \pmod{m} has natural density \frac{1}{\phi(m)}, where \phi is Euler's totient function.^[25] This relative density \frac{\pi(x; m, a)}{ \pi(x) } \sim \frac{1}{\phi(m)} follows from the PNAP, \pi(x; m, a) \sim \frac{1}{\phi(m)} \frac{x}{\log x}, and underscores the equitable distribution of primes among residue classes modulo m.^[26] Sieve methods extend the classical Sieve of Eratosthenes to estimate densities of integers avoiding certain prime factors, employing inclusion-exclusion principles to count those free of small prime factors. For a parameter y, the density of integers up to x with no prime factors \leq y (known as y-rough numbers) is given by the product \prod_{p \leq y} (1 - \frac{1}{p}), obtained via the inclusion-exclusion formula involving the Möbius function over the primes up to y.^[27] This asymptotic holds as x \to \infty for fixed y, and more refined sieves adjust for growing y to bound counts of primes or prime-like structures, such as in the estimation of \pi(x; k, l), the number of primes up to x congruent to l \pmod{k}, yielding upper bounds like $3y \frac{\phi(k)}{k} \log(y/k) for intervals of length y.^[27] Such densities are pivotal in analytic proofs and heuristics for prime distributions. Brun's sieve provides an upper bound on the density of twin primes, pairs of primes differing by 2, demonstrating that their natural density is zero. Specifically, Brun showed that the count of twin primes up to x, denoted \pi_2(x), satisfies \pi_2(x) < C \frac{x (\log \log x)^2}{(\log x)^2} for some constant C > 0, implying the upper asymptotic density \overline{d}(\{p : p, p+2 \text{ prime}\}) = 0 < 1.^[28] While the exact density remains unknown under the twin prime conjecture, which posits infinitely many such pairs, post-2013 computational verifications of the twin prime constant C_2 \approx 0.6601618158 (from the Hardy-Littlewood conjecture, \pi_2(x) \sim 2 C_2 \int_2^x \frac{dt}{(\log t)^2}) confirm the heuristic scale, with extensive enumerations up to $10^{18} aligning closely with predicted counts. For the Goldbach conjecture, which asserts every even integer greater than 2 is the sum of two primes, natural densities inform heuristic arguments via the circle method and probabilistic models. The Hardy-Littlewood conjecture predicts the number of representations r_2(n) of an even n as p + q with primes p, q satisfies r_2(n) \sim 2 C_2 \prod_{p > 2, p \mid n} \frac{p-1}{p-2} \frac{n}{(\log n)^2}, where the product adjusts for local densities modulo primes dividing n, and C_2 is the twin prime constant; this heuristic, grounded in the PNT's prime densities, suggests r_2(n) \gg \frac{n}{(\log n)^2} on average, supporting the conjecture's validity for large n.^[29]

In additive combinatorics

In additive combinatorics, natural density plays a central role in studying arithmetic structures within subsets of the natural numbers. A foundational result is Szemerédi's theorem, which asserts that any subset of the integers with positive upper asymptotic density contains arithmetic progressions of arbitrary finite length.^[30] This theorem, proved in 1975, resolves a conjecture by Erdős and Turán from 1936 and has profound implications for the distribution of additive patterns in dense sets.^[31] A key special case is Roth's theorem from 1953, which establishes that subsets with positive upper density must contain 3-term arithmetic progressions, with the size of progression-free sets bounded by o(N) up to N. Subsequent improvements have refined the quantitative bounds; for instance, Bourgain in 1999 showed that such sets have size at most N / (\log \log N)^c for some constant c > 0. On the constructive side, Behrend's 1946 construction yields subsets of \{1, \dots, N\} without 3-term arithmetic progressions and with density approximately e^{-c \sqrt{\log N}} for some c > 0, providing a lower bound that remains near-optimal. Recent advances, such as the 2023 result by Kelley and Meka, have tightened the upper bounds on progression-free sets to N / \exp(c (\log N)^{1/12}), narrowing the gap with Behrend's construction but leaving the precise asymptotic unresolved.^[32] Natural density also informs the study of additive bases and sumsets. For a set A \subseteq \mathbb{N} with positive upper density, the sumset A + A = \{a + a' : a, a' \in A\} inherits positive density, reflecting the additive richness expected from dense configurations.^[33] This connects to finite-field analogs like the Cauchy-Davenport theorem in \mathbb{Z}/p\mathbb{Z}, which bounds |A + B| \geq \min(p, |A| + |B| - 1) and inspires structural results for sumsets in the integers via density arguments.^[34] Another application arises in the Furstenberg–Sárközy theorem, which states that any subset of the natural numbers with positive upper density contains two distinct elements whose difference is a perfect square. Proved independently in 1978–1979 using analytic and ergodic methods, this result highlights how density forces intersections with quadratic shifts, extending patterns beyond linear progressions.

Logarithmic density

The logarithmic density of a subset A of the positive integers is defined as

\delta(A) = \lim_{x \to \infty} \frac{1}{\log x} \sum_{\substack{n \in A \\ n \leq x}} \frac{1}{n},

provided the limit exists.^[35] If the limit does not exist, one considers the lower logarithmic density \underline{\delta}(A) = \liminf_{x \to \infty} \frac{1}{\log x} \sum_{\substack{n \in A \\ n \leq x}} \frac{1}{n} and the upper logarithmic density \overline{\delta}(A) = \limsup_{x \to \infty} \frac{1}{\log x} \sum_{\substack{n \in A \\ n \leq x}} \frac{1}{n}.^[35] Unlike the natural density, the logarithmic density always lies in the interval [0, 1] when it exists, as the harmonic sum \sum_{n \leq x} 1/n \sim \log x.^[36] As a weighted analog to the natural density, which uses uniform counting, the logarithmic density emphasizes the "logarithmic size" of sets by weighting smaller elements more heavily via the harmonic measure.^[37] For instance, the set of prime numbers has logarithmic density \delta(P) = 0, since \sum_{p \leq x} 1/p \sim \log \log x, but this divergence captures the slow growth of primes relative to the integers.^[36] When the natural density d(A) exists, the logarithmic density exists and equals it, establishing a compatibility between the two measures for many sets in analytic number theory.^[36] The logarithmic density satisfies monotonicity: if A \subseteq B, then \underline{\delta}(A) \leq \underline{\delta}(B) and \overline{\delta}(A) \leq \overline{\delta}(B).^[35] It is also subadditive for the upper version: \overline{\delta}(A \cup B) \leq \overline{\delta}(A) + \overline{\delta}(B).^[35] Moreover, the inequalities \underline{d}(A) \leq \underline{\delta}(A) \leq \overline{\delta}(A) \leq \overline{d}(A) hold, where d and \bar{d} denote the lower and upper natural densities, respectively.^[38] (Note: PlanetMath is used here for the inequality statement, but verify with primary sources like Kubilius for rigor.) Discrepancies between the measures arise, such as sets with logarithmic density 0 but positive upper natural density greater than 0; these include certain sets constructed with sparse but relatively dense blocks at exponentially growing positions, ensuring the harmonic contributions remain negligible relative to \log x.^[35] Logarithmic density proves useful in the analysis of Dirichlet series, where the abscissa of convergence relates directly to the growth of \sum_{n \in A} 1/n^s, providing a natural measure for sets where uniform density vanishes.^[37] Convergence of the limit defining \delta(A) can be established using Abel partial summation when partial information on the counting function of A is available, linking it to integral estimates over the distribution of elements.^[36]

Banach density

The Banach density provides a measure of the size of a subset A \subseteq \mathbb{N} that is based on uniform densities within arithmetic progressions of integers, offering a refinement of the natural density for applications in combinatorial number theory. The upper Banach density, denoted \bar{d}_B(A), is defined as

\bar{d}_B(A) = \lim_{n \to \infty} \max_{l \geq 0} \frac{|A \cap [l+1, l+n]|}{n},

while the lower Banach density, denoted d_B(A), is

d_B(A) = \lim_{n \to \infty} \min_{l \geq 0} \frac{|A \cap [l+1, l+n]|}{n}.

These limits always exist for any A \subseteq \mathbb{N}, as the respective sequences are monotonic. The Banach density of A exists if and only if d_B(A) = \bar{d}_B(A), in which case it coincides with the natural density when the latter exists.^[39]^[40] The Banach densities satisfy the inequalities

$0 \leq d_B(A) \leq \underline{d}(A) \leq \bar{d}(A) \leq \bar{d}_B(A) \leq 1,

where \underline{d}(A) and \bar{d}(A) are the lower and upper natural densities, respectively. This positioning highlights that Banach densities capture local uniformity: the upper version can exceed the upper natural density, while the lower version is bounded above by the lower natural density. Unlike natural density, Banach densities are invariant under bounded perturbations; if A' differs from A by a set of bounded cardinality (i.e., | (A \setminus A') \cup (A' \setminus A) | < \infty), then d_B(A') = d_B(A) and \bar{d}_B(A') = \bar{d}_B(A), since such changes affect the cardinality in any interval by at most a constant, vanishing in the limit.^[40]^[31] In combinatorial applications, positive upper Banach density ensures the presence of rich additive structure. For instance, any A \subseteq \mathbb{N} with \bar{d}_B(A) > 0 contains finite-dimensional infinite parameter (IP) sets of arbitrary dimension, meaning subsets closed under finite sums from an infinite sequence \{x_k\}_{k=1}^\infty with distinct finite sums. This connects to Hindman's theorem, which guarantees monochromatic IP sets in finite colorings of \mathbb{N}, and its density analogs, where cells of positive upper Banach density inherit such structures. A distinctive feature is that Banach densities exist for every subset of \mathbb{N}, unlike natural densities which may fail to exist. Examples include thick sets, which contain arbitrarily long intervals and thus have \bar{d}_B(A) = 1, yet can be constructed to have \bar{d}(A) = 0 by spacing these intervals sufficiently far apart.^[41]^[31]

References

[1]
Natural Density -- from Wolfram MathWorld
Natural Density. See. Natural Invariant · About MathWorld · MathWorld Classroom · Contribute · MathWorld Book · wolfram.com · 13,279 Entries · Last Updated: Fri ...
[2]
(PDF) Natural Density and The Quantifier Most - ResearchGate
1. kfor k∈N. Deﬁnition 4.2 emphasizes that the natural density is a limit that. may not exist. For this reason, we will continue assuming that each set has a.
[3]
[PDF] Math 676. Dirichlet density for global fields
There is another notion of density that comes to mind, natural density: δnat(Σ) def. = lim. x→∞
[4]
Asymptotic Density and the Theory of Computability: A partial survey
In this article we survey the development of generic and coarse computability and the main results on how classical asymptotic density interacts ...
[5]
[1801.09401] Natural density and probability, constructively - arXiv
Jan 29, 2018 · Abstract:We give here a constructive account of the frequentist approach to probability, by means of natural density.Missing: interpretation | Show results with:interpretation
[6]
[PDF] Counting problems relating to a theorem of Dirichlet*
An old theorem of G. Lejeune Dirichlet, dating back to the year 1849, states that the probability that two integers taken at random are relatively.
[7]
Handbuch der Lehre von der Verteilung der Primzahlen : Landau ...
Dec 2, 2008 · Handbuch der Lehre von der Verteilung der Primzahlen. by: Landau, Edmund, 1877-1938. Publication date: 1909. Topics: Numbers, Prime. Publisher ...Missing: density | Show results with:density
[8]
None
Error: Could not load webpage.<|control11|><|separator|>
[9]
The primes contain arbitrarily long arithmetic progressions - arXiv
We prove that there are arbitrarily long arithmetic progressions of primes. There are three major ingredients. The first is Szemeredi's theorem.Missing: ergodic | Show results with:ergodic
[10]
Asymptotic density - Encyclopedia of Mathematics
Nov 25, 2023 · A variant of the general concept of the density of a sequence of natural numbers; which measures how large a part of the sequence of all ...
[11]
[PDF] Introduction to the Theory of Numbers
Nov 21, 2014 · ... HARDY. AND. E. M. WRIGHT. Principal and Vice-Chancellor of the ... definition and simplest properties of a Farey series. 3.2. The ...
[12]
Density - OeisWiki
Jan 3, 2025 · Asymptotic density (or natural density) is a common way to measure the size of a subset of the natural numbers.Asymptotic density · Logarithmic density · Uniform density · Schnirelmann density
[13]
[PDF] 1 Dirichlet's theorem 2 Asymptotic density and ... - Kiran S. Kedlaya
Many interesting sets fail to have a natural density (e.g., see exercises). We get a less restrictive notion of density by using Dirichlet series. For S ⊆ T two ...
[14]
DENSITIES AND SUMMABILITY - Project Euclid
Certain essential properties of these densities are proved and the "natural density" associated with the lower density is defined. The natural density has some ...
[15]
[PDF] Fine asymptotic densities for sets of natural numbers - unipi
By simply taking a quotient, fine densities yield non-atomic finitely additive measures that – up to infinitesimals – agree with the asymptotic density, and.<|control11|><|separator|>
[16]
https://doi.org/10.1016/0165-4896(94)00772-Z
[17]
[PDF] On the Density Theorem ofˇCebotarev - Ball State University Libraries
Then, we move on to Dirichlet density (and briefly introduce natural density). We prove that if polar density exists, then so does Dirichlet density, and that ...
[18]
[PDF] Mixing - Siamak Taati
Natural density. The upper and the lower density of a set J ⊆ N are defined ... not countably additive, and lacks continuity: • If Jn := {n}, then d(J.
[19]
[PDF] 1 Arithmetic Progressions - Yuval Wigderson
Example. The set of even numbers has density 1/2, as does the set of odd numbers. The set of squares has density 0, since if S is the set of squares, then. | ...Missing: standard book
[20]
[PDF] A Generalization of Natural Density
The concept of natural density is generalized. It is proved that the new theory is consistent with the existing theory in the literature.Missing: term | Show results with:term
[21]
The Classical Proof of the Prime Number Theorem
The first complete proof of the Prime Number Theorem was given (independently) by Hadamard and de la Vallé Poussin in 1896 [1,4]. It was the culmination of work ...Missing: implications | Show results with:implications
[22]
Percentage of natural numbers that are perfect squares?
Dec 12, 2016 · Zero percent of all natural numbers are perfect squares in the sense that the limit of the proportion of the perfect squares to natural numbers is zero.What is the density of "powerful" or "squareful" numbers?What is the probability that a natural number is a sum of two squares?More results from math.stackexchange.com
[23]
On the densities of covering numbers and abundant numbers - arXiv
Jul 30, 2025 · As a byproduct of our methods, we obtain significantly improved bounds for d(\mathcal{A}), the density of abundant numbers, namely 0.247619608 < ...
[24]
Sets with no asymptotical density over N - Math Stack Exchange
Sep 13, 2013 · The set C=⋃nI2n has upper density 23 and lower density 13. Exercise: Modify the example to find a set with upper density 1 and lower density 0.Complements of sets with lower density 0 - Math Stack ExchangeSequences of integers with lower density 0 and upper density 1.More results from math.stackexchange.com
[25]
[PDF] 18 Dirichlet L-functions, primes in arithmetic progressions
Nov 10, 2016 · Dirichlet density 1/φ(m), whereas the prime number theorem for arithmetic progressions states that this set has natural density 1/φ(m). If a ...Missing: 1849 | Show results with:1849
[26]
Chapter 5 Primes in arithmetic progressions - Kiran S. Kedlaya
Of course the upper density is never less than the lower density. If they coincide, we call the common value the natural density (or asymptotic density ) of ...
[27]
[PDF] Sieve Methods - cs.wisc.edu
In this treatise we survey the major sieve methods and their important applications in number theory. We apply sieves to study the distribution of square-free ...
[28]
[PDF] Elementary sieve methods and Brun's theorem on twin primes
Apr 23, 2014 · Concretely, we will study the theorems of the Norwegian mathematician Viggo Brun about the density of twin primes, and the reciprocal sum of ...
[29]
An elementary heuristic for Hardy-Littlewood extended Goldbach's ...
Aug 24, 2015 · The goal of this paper is to describe an elementary combinatorial heuristic that predicts Hardy and Littlewood's extended Goldbach's conjecture.
[30]
On sets of integers containing k elements in arithmetic progression
Szemerédi, E.. "On sets of integers containing k elements in arithmetic progression." Acta Arithmetica 27.1 (1975): 199-245.Missing: paper | Show results with:paper
[31]
[PDF] SZEMERÉDI'S PROOF OF SZEMERÉDI'S THEOREM - Terry Tao
In 1975, Szemerédi famously established that any set of integers of posi- tive upper density contained arbitrarily long arithmetic progressions. The proof was.
[32]
[2302.05537] Strong Bounds for 3-Progressions - arXiv
Feb 10, 2023 · Authors:Zander Kelley, Raghu Meka. View a PDF of the paper titled Strong Bounds for 3-Progressions, by Zander Kelley and 1 other authors. View ...Missing: polymath | Show results with:polymath
[33]
Infinite sumsets in sets with positive density
Aug 11, 2023 · Erd˝os and Graham [7] conjectured that sets of natural numbers with positive upper density contain not only finite arithmetic configurations, ...
[34]
[PDF] Sumsets and structure Imre Z. Ruzsa
The asymptotic density of a set A of integers is defined by d(A) = lim x→∞. A(x)/x, if this limit exists. The lower and upper (asymptotic) densities are ...<|control11|><|separator|>
[35]
https://arxiv.org/pdf/1506.04664.pdf
[36]
[PDF] Probabilistic Number Theory
Theorem 2.4 A sequence A of positive integers has analytic density if and only if. A has logarithmic density; in this case the two densities are equal. A ...
[37]
[PDF] A monad measure space for logarithmic density - UCI Mathematics
• The upper logarithmic density of A is defined to be ld(A) := lim sup n→∞. 1 ln n. X x∈A∩[1,n]. 1 x . • The lower logarithmic density of A is defined to be.
[38]
inequality of logarithmic and asymptotic density - PlanetMath
Mar 24, 2014 · A well-known example of a set having logarithmic density but not having asymptotic density is the set of all numbers with the first digit equal to 1.
[39]
[PDF] On the notions of upper and lower density - arXiv
Abstract. Let P(N) be the power set of N. We say that a function µ* : P(N) → R is an upper density if, for all X, Y ⊆ N and h, k ∈ N+, the following hold: ...
[40]
[PDF] A note on uniform or Banach density - Numdam
Since the notion of Banach density has been introduced prior to the term “uniform density”, we propose to use the term “Banach density”. Acknowledgements ...
[41]
On density analogs of Hindman's finite sums theorem - arXiv
Oct 21, 2025 · Abstract:For any set A of natural numbers with positive upper Banach density, we show the existence of an infinite set B and sequences ...