Logarithmic density: the $1/n$-weighted density that survives when natural density doesn't

Statement

For $A\subseteq\mathbb N$, the logarithmic density of $A$ is $$\delta(A) \;=\; \lim_{x\to\infty}\frac{1}{\log x}\sum_{\substack{n\in A\\ n\le x}}\frac1n,$$ when the limit exists. When it doesn't, one still has the upper and lower logarithmic densities $$\overline\delta(A)=\limsup_{x\to\infty}\frac1{\log x}\sum_{n\in A,\,n\le x}\frac1n, \qquad \underline\delta(A)=\liminf_{x\to\infty}\frac1{\log x}\sum_{n\in A,\,n\le x}\frac1n,$$ which always exist (in $[0,1]$) since the summand is bounded. The $1/n$ weight is exactly what makes $\delta(\mathbb N)=1$: it compensates the fact that $\sum_{n\le x}1/n\sim\log x+\gamma$ (en.wikipedia.org/wiki/Natural_density).

Relation to natural (asymptotic) density $d(A)=\lim_x |A\cap[1,x]|/x$. For every $A\subseteq\mathbb N$, $$\underline d(A)\ \le\ \underline\delta(A)\ \le\ \overline\delta(A)\ \le\ \overline d(A).$$ Consequently, if the natural density $d(A)$ exists, the logarithmic density $\delta(A)$ exists and $\delta(A)=d(A)$ — but the converse fails: there are sets with a logarithmic density and no natural density at all. This is why logarithmic density is the strictly weaker, strictly more permissive notion: it is a partial-summation/Abel-type smoothing of the counting function, so it survives oscillations that kill the ordinary Cesàro-type limit defining $d(A)$.

Canonical example (Benford's law). Let $A=\{n : \text{leading decimal digit of }n\text{ is }1\}$. Then $A$ has no natural density ($\underline d(A)=1/9$, $\overline d(A)=5/9$, oscillating forever as $x$ ranges over powers of 10), but $\delta(A)=\log_{10}2\approx0.301$ exists and matches the Benford frequency $\log_{10}(1+1/d)$ for leading digit $d$ (en.wikipedia.org/wiki/Natural_density). This is the standard demonstration that logarithmic density is a genuinely different (weaker, more robust) tool, not just an equivalent restatement of natural density.

Facts

- Davenport–Erdős theorem (1936). For $A\subseteq\mathbb N$ and $M(A)=\{ka : k\ge1,\,a\in A\}$ its set of multiples, three a priori different density notions of $M(A)$ all coincide: the (lower) natural density, the logarithmic density, and the sequential density (the limit, as $i\to\infty$, of the natural densities of $M(\{a_1,\ldots,a_i\})$ for finite truncations of $A$ — these finite unions decompose into arithmetic progressions with computable densities via inclusion–exclusion). H. Davenport & P. Erdős, "On sequences of positive integers," *Acta Arithmetica* 2 (1936), 147–151 (original proof via the Hardy–Littlewood Tauberian theorem); an elementary, Tauberian-free reproof followed in *J. Indian Math. Soc.* (N.S.) 15 (1951), 19–24 (en.wikipedia.org/wiki/Davenport–Erdős_theorem). A sequence $A$ for which all three densities of $M(A)$ equal $1$ is called a Behrend sequence. - Quantitative strengthening: Erdős–Sárközy–Szemerédi (1966) / doubly-logarithmic density. ESS asked (and it was proved only in 2026) that if $A\subset\mathbb N$ has positive upper doubly logarithmic density $\Delta=\limsup_{x\to\infty}\frac1{\log\log x}\sum_{n\in A\cap[2,x]}\frac1{n\log n}>0$ — a hypothesis on a *sparser* scale than positive logarithmic density itself — then $A$ contains an infinite divisibility chain whose own counting function grows at essentially the same doubly-log rate. This is exactly the Davenport–Erdős theorem's conclusion (existence of an infinite divisibility chain) recovered from a weaker, quantitatively matched hypothesis than "positive logarithmic density," solved via a von Mangoldt-weighted Markov chain method in arXiv:2605.00301 (2026) — see Erdős #1217 — Erdős–Sárközy–Szemerédi (1966) divisibility-chain density conjecture, solved 2026 via the von Mangoldt/zeta Markov-chain method. - Used as the load-bearing hypothesis, not just a background fact, in a live 2025 unconditional result. Koukoulopoulos–Lamzouri–Lichtman (arXiv:2502.09539, Feb 2025) prove: if a real set $A\subset\mathbb R_{\ge1}$ has $\overline\delta(A)=\limsup_{x\to\infty}\frac1{\log x}\sum_{a\in A\cap[1,x]}\frac1a>0$, then infinitely many pairs $\alpha\ne\beta\in A$ satisfy $|n\alpha-\beta|<\varepsilon$ for some positive integer $n$, for every $\varepsilon>0$ — the contrapositive resolves half of Erdős's \$500 integer/real dilation-approximation problem. See Erdős #143 — integer dilations $|kx-y|\\geq1$ force sparsity?. - **Used as the *conclusion* scale, not the hypothesis, when natural density is dynamically unreachable. T. Tao's theorem on the Collatz map (arXiv:1909.03562, 2019) — for every function $f:\mathbb N\to\mathbb R$ with $f(N)\to\infty$, $\mathrm{Col}_{\min}(N)\le f(N)$ for almost all $N$ in the sense of logarithmic density** — is deliberately stated with logarithmic, not natural, density. Tao's own explanation (terrytao.wordpress.com/2019/09/10): iterating a local-in-time "almost all $N$ in $[1,x]$" statement (natural-density flavor, à la Terras 1976 / Korec 1994) across many scales fails because, by the time an orbit reaches a smaller range, its distribution is no longer close to uniform on that range — natural density is not preserved by the Collatz map's dynamics. The logarithmic-density/renewal-process framework composes across scales where the natural-density one does not. See Erdős #1135 — the Collatz (3x+1) conjecture. - Logarithmic averaging resolved the Erdős discrepancy problem. Tao & Teräväinen's proof of the logarithmically averaged two-point Chowla/Elliott conjectures for multiplicative functions (arXiv:1509.05422, 2015) — i.e. controlling $\frac1{\log x}\sum_{n\le x}\frac{f(n)g(n+h)}n$ rather than the ordinary Cesàro average $\frac1x\sum_{n\le x}f(n)g(n+h)$ — was the key unconditional input Tao used to fully resolve the Erdős discrepancy problem (arXiv:1509.05363, 2015): every $\pm1$-sequence has unbounded discrepancy along homogeneous arithmetic progressions. Logarithmic averaging was the technical device that made an otherwise-conditional (Elliott-conjecture-dependent) argument unconditional in the two-point case (terrytao.wordpress.com/2015/09/11 and 2015/09/18). This is the largest-impact instance of "swap the natural/Cesàro average for the logarithmic one to make an otherwise out-of-reach statement provable" in the whole Erdős-problems ecosystem — not independently re-verified beyond abstracts/blog posts here, flagged as a high-value lead. - Existence of sets with no natural density at all (so that logarithmic density is not merely "sometimes easier to compute" but genuinely necessary) traces to Besicovitch (1935), cited via en.wikipedia.org/wiki/Davenport–Erdős_theorem.

Technique

How "switch to logarithmic density" is used as a transferable move (two directions):

1. **Hypothesis-weakening direction: relax "positive natural density" to "positive logarithmic density" (or further, to positive *doubly*-logarithmic density) to broaden a theorem's applicability to sparser sets.** Because $\underline d(A)\le\underline\delta(A)$, a set can fail to have positive natural density yet still have positive logarithmic density (or the ESS 1966 doubly-log density, an even sparser scale) — so any theorem provable from a logarithmic-density hypothesis is *automatically* a strengthening of the same theorem stated with a natural-density hypothesis. This is exactly the ladder in Erdős #1217 — Erdős–Sárközy–Szemerédi (1966) divisibility-chain density conjecture, solved 2026 via the von Mangoldt/zeta Markov-chain method/concept/davenport-erdos-theorem: Davenport–Erdős (natural-density-flavored, via all three coinciding densities) $\to$ ESS 1966 (a genuine positive-logarithmic-density hypothesis suffices for a divisibility chain to exist) $\to$ the 2026 quantitative doubly-logarithmic-density theorem (an even sparser sufficient hypothesis, with a matched growth-rate conclusion). The same move underlies Erdős #143 — integer dilations $|kx-y|\\geq1$ force sparsity?: KLL25's unconditional dilation-approximation result is stated and proved directly from the $\overline\delta(A)>0$ hypothesis, which is weaker than requiring $A$ to have positive natural (or Schnirelmann) density, so the theorem covers a strictly larger class of sequences than a natural-density version would. 2. Conclusion-weakening direction: prove an "almost all" statement in the logarithmic-density sense when the natural-density version is unreachable because the underlying dynamics don't preserve uniform distribution. This is Tao's Collatz move: instead of trying to show $\mathrm{Col}_{\min}(N)\le f(N)$ for $100\%$ of $N\in[1,x]$ in the ordinary counting sense (which would require controlling the *exact* distribution of orbits at every scale simultaneously), it suffices — and is provable — to control the *logarithmically weighted* proportion, because the $1/n$-weighted measure interacts better with the multiplicative/renewal structure of the map's dynamics across scales. The price is that a logarithmic-density-1 "almost all" theorem is strictly weaker than a natural-density-1 one (see Statement: $\overline\delta\le\overline d$ only gives an implication one way), and gives no information about any single orbit. 3. Mechanically, why the $1/n$ weight interacts well with multiplicative structure. Writing $x=e^y$, the sum $\frac1{\log x}\sum_{n\le x, n\in A}1/n$ becomes (up to normalization) a Cesàro-type average of the indicator of $\{\log n : n\in A\}$ on the *additive* scale $y=\log n$. This turns multiplicatively-defined objects — divisibility chains, GCD relations, multiples/dilations $n\mapsto kn$ — into translation-type objects on the log scale, which is exactly why logarithmic density (rather than natural density) is the natural hypothesis/conclusion currency for divisibility-chain existence (Davenport–Erdős, ESS, Erdős #1217 — Erdős–Sárközy–Szemerédi (1966) divisibility-chain density conjecture, solved 2026 via the von Mangoldt/zeta Markov-chain method), GCD-graph/dilation-approximation arguments (Erdős #143 — integer dilations $|kx-y|\\geq1$ force sparsity?), and logarithmically-averaged multiplicative-function correlation sums (Chowla/Elliott, Erdős discrepancy problem). 4. WHEN to reach for this technique. (a) A "does $A$ contain structure $X$" theorem you want to prove from as weak a density hypothesis as possible — try logarithmic (or doubly-logarithmic, etc.) density before assuming positive natural density; the Davenport–Erdős/ESS/2026-chain ladder is the template. (b) An "almost all $n$" theorem about a multiplicatively-defined dynamical process (digit expansions, Collatz-type maps, GCD/divisibility processes) where natural density is provably not preserved step-to-step — state and prove the result in logarithmic density instead, following Tao's Collatz template. (c) Correlation-sum/multiplicative-function problems where the ordinary Cesàro average $\frac1x\sum_{n\le x}f(n)g(n+h)$ resists an unconditional bound but the logarithmically-averaged version $\frac1{\log x}\sum_{n\le x}f(n)g(n+h)/n$ does not (Chowla/Elliott $\to$ Erdős discrepancy problem). 5. WHAT it does NOT give you. A logarithmic-density statement does not automatically upgrade to a natural-density statement (the inequality only goes $\underline d\le\underline\delta\le\overline\delta\le\overline d$, i.e. natural density is the *stronger*, harder-to-establish notion) — do not cite a logarithmic-density-1 "almost all" result as if it settled the natural-density (still less the pointwise/every-single-element) version of the same question. Tao's Collatz theorem is explicit that it says nothing about individual orbits, only the $1/n$-weighted proportion.

Related

- Erdős #1217 — Erdős–Sárközy–Szemerédi (1966) divisibility-chain density conjecture, solved 2026 via the von Mangoldt/zeta Markov-chain method — Erdős–Sárközy–Szemerédi (1966) doubly-logarithmic-density divisibility-chain conjecture; the direct quantitative strengthening of the Davenport–Erdős theorem, solved 2026 via a von Mangoldt-chain Markov method (arXiv:2605.00301). - Erdős #143 — integer dilations $|kx-y|\\geq1$ force sparsity? — Erdős's integer/real dilation-approximation problem; Koukoulopoulos–Lamzouri–Lichtman (arXiv:2502.09539) prove the key unconditional result directly from a positive-upper-logarithmic-density hypothesis via GCD-graph machinery. - Erdős #1135 — the Collatz (3x+1) conjecture — Collatz conjecture; Tao's strongest known partial result (arXiv:1909.03562) is stated in the sense of logarithmic density, not natural density, because natural density is not preserved by the map's dynamics across scales. - concept/davenport-erdos-theorem — forward-reference: the classical 1936 ancestor theorem (Davenport & Erdős, *Acta Arithmetica* 2) proving natural, logarithmic, and sequential density all coincide for sets of multiples $M(A)$; this concept page is the general density-notion whose specific application-to-multiples *is* that theorem. - Landau–Ramanujan theorem: the density of sums of two squares is $\\Theta(x/\\sqrt{\\log x})$ — a structurally different but adjacent density-asymptotics result (ordinary/natural density with a $\log$-power correction $x/\sqrt{\log x}$, rather than a $1/n$-weighted logarithmic density); useful contrast for distinguishing "density decaying like a power of $\log x$" from "density measured on the logarithmic/$1/n$-weighted scale." - E. Landau/S. Ramanujan sums-of-two-squares theorem — see Landau–Ramanujan theorem: the density of sums of two squares is $\\Theta(x/\\sqrt{\\log x})$ for the sibling notion. - T. Tao & J. Teräväinen, "The logarithmically averaged Chowla and Elliott conjectures for two-point correlations," arXiv:1509.05422 (2015), and T. Tao, "The Erdős discrepancy problem," arXiv:1509.05363 (2015) — the highest-impact application of logarithmic averaging adjacent to Erdős's own work; not independently read beyond abstracts/blog posts here, flagged as a lead for any future page on the Erdős discrepancy problem itself.