Von Mangoldt-weighted Markov chains for primitive-set (Erdős) sums

Statement

Setting. A set $A\subset\mathbb N_{>1}$ is primitive if no element of $A$ divides another — i.e. $A$ is an antichain in the divisibility poset $(\mathbb N,\mid)$. The Erdős sum of $A$ is $$f(A):=\sum_{a\in A}\nu_0(a),\qquad \nu_0(a):=\frac{1}{a\log a}$$ (the "doubly harmonic," or "doubly logarithmic," weight). Erdős proved in 1935 that $f(A)$ is uniformly bounded over *all* primitive sets $A$; the extremal-value and refined-tail questions this bounds (which set maximizes $f$? does the tail beyond $x$ stay capped by $1$?) were open for up to 90 years. arXiv:2605.00301 introduces a technique — von Mangoldt-weighted Markov chains — that resolves several of these at once.

The von Mangoldt downward chain. State space $\mathbb N_{\ge1}$ with absorbing state $\{1\}$ (or a different absorbing set, see below). From $n\ge2$, transition to $n/q$ for each divisor $q\mid n$ with probability $$\mathbb P(n\searrow n/q) \;:=\; \frac{\Lambda(q)}{\log n},$$ where $\Lambda$ is the von Mangoldt function ($\Lambda(p^k)=\log p$ for prime powers, $\Lambda=0$ otherwise). This is a genuine probability distribution over the divisors of $n$ because of the classical convolution identity $\Lambda * 1 = \log$, i.e. $\sum_{q\mid n}\Lambda(q)=\log n$. A sample path is a strictly decreasing divisibility chain $n=n_0\searrow n_1\searrow n_2\searrow\cdots\searrow1$, and at each step the chain is exactly as likely to "jump down" through a prime-power divisor as the classical $\Lambda$-weighting of the integers dictates.

Sub-invariance of the doubly-harmonic weight. The weight $\nu_0(n)=1/(n\log n)$ is sub-invariant for the downward chain: $$\sum_{q>1}\nu_0(nq)\,\mathbb P(nq\searrow n)\;\le\;\nu_0(n).$$ (I.e. pushing the weight one step down the chain never increases its total mass at a given target state — a discrete analogue of a supermartingale/superharmonic condition.)

Downward hitting mass and the core antichain inequality. For an initial mass distribution $b$ on $\mathbb N$, define the downward hitting mass at $n$, $$h_{b\searrow}(n) := \sum_{n_0} b(n_0)\sum_{k=0}^\infty \mathbb P_{n_0\searrow}(n_k=n),$$ i.e. the total initial mass of chain trajectories that ever pass through $n$. Because a primitive set $A$ meets any single divisibility chain in at most one point (two elements of the same chain are divisibility-comparable, and $A$ is an antichain), the hitting-mass contributions to distinct elements of $A$ never double-count a trajectory's mass, giving the master inequality $$\sum_{n\in A} h_{b\searrow}(n) \;\le\; \sum_{n_0} b(n_0) \qquad\text{for every primitive set }A.$$ Choosing $b$ so that $h_{b\searrow}(n)=\nu_0(n)$ (or a suitable variant weight, see below) turns this into the target extremal bound $f(A)=\sum_{a\in A}\nu_0(a)\le\sum_{n_0}b(n_0)$ directly.

The adjoint upward chain. From a downward chain with sub-invariant weight $\nu$, an adjoint upward chain is built by $$\mathbb P(n\nearrow m) := \frac{\nu(m)}{\nu(n)}\,\mathbb P(m\searrow n), \qquad \mathbb P(n\nearrow\infty) := 1-\sum_{m\ne n}\frac{\nu(m)}{\nu(n)}\mathbb P(m\searrow n)\ \ (\text{escape probability}),$$ i.e. time-reversal of the downward chain weighted by $\nu$. The upward hitting mass $h_{b\nearrow}$ satisfies the parallel bound $\sum_{n\in A}h_{b\nearrow}(n)\le\sum_{n_0}b(n_0)$, and starting the upward chain with mass concentrated on a natural "boundary" set (e.g. the primes, for the extremal question "which primitive set maximizes $f$") is what lets the method pin down not just an upper bound but the exact extremizer.

Main theorems proved by this method (arXiv:2605.00301): - Thm 1.1 (Erdős–Sárközy–Szemerédi, Erdős problem #1196). If $A$ is primitive and $A\subset[x,\infty)$, then $f(A)=\sum_{a\in A}1/(a\log a)\le 1+O(1/\log x)$. - Thm 1.2 (Erdős primitive set conjecture, Erdős problem #164). For *any* primitive set $A$, $f(A)\le f(\mathbb N_1)=f(\text{primes})\approx1.6366\ldots$ — primes are the extremal primitive set. (Proved via a modified downward chain with prime absorbing states, §5.) - Thm 1.3 ("Odd Banks–Martin"). For $k\ge1$, primitive $A\subset\mathbb N_{\ge k}$, and restriction to odd primes $\mathcal Q$: $f(A(\mathcal Q))\le f(\mathbb N_k(\mathcal Q))$ — proved via a chain restricted to odd-prime divisor steps, with weights $\beta_p:=p/(p-2)$ (§6). Described by the authors as resolving a revised form of a long-standing "master theorem" conjecture (Banks–Martin) for this problem area. - Thm 1.4 ("2 is Erdős-strong"). An analogous bound for primitive sets of even numbers, proved using a rescaled weight $\nu_2(n):=1/(n\log(2n))$ (§7). - Thm 1.6 (Erdős–Sárközy–Szemerédi, Erdős problem #1217). Sets with positive doubly-logarithmic density contain infinite divisibility chains of matching density — proved via a contrapositive/hitting-probability variant of the same chain machinery.

Facts

- Historical gap. Erdős proved boundedness of $f(A)$ in 1935; the extremal-set question (#164) stayed open until Jared D. Lichtman's 2022/2023 proof (arXiv:2202.02384, *Forum of Mathematics, Pi* 11 (2023) e18) — a much longer (~20-page) sieve-theoretic argument refining Erdős's original 1935 "disjoint lexicographic-multiples" density method, with a bespoke $\sqrt v$-saving proposition. The von Mangoldt-chain method gives a five-page reproof of the same result (§5 of arXiv:2605.00301). - Why the naive alternative ("downwards Mertens chain") is worse. T. Tao's blog exposition (terrytao.wordpress.com, 2026-05-03) explains that the prior natural candidate divides $n$ by its *largest* prime factor at each step (a "Mertens chain"). That chain introduces an $e^\gamma$ loss factor because it "biases towards numbers whose largest prime factor is small." The von Mangoldt weighting fixes this: choosing the divisor $q$ proportional to $\Lambda(q)$ (rather than deterministically taking the largest prime factor) removes that bias, because $1/(n\log n)$ is exactly sub-invariant under the $\Lambda$-weighted step (not under the largest-prime-factor step). This is the crux of why von Mangoldt, specifically, is the right weighting — it is the unique choice making $\Lambda * 1=\log n$ do double duty as both a normalizing identity and the source of the sub-invariance computation. - A further-refined, exactly invariant weight exists. Beyond mere sub-invariance of $\nu_0$, Tao's post notes the paper constructs a modified weight $\nu_\Lambda(n)$ that is exactly invariant (not just sub-invariant) under the chain, via a "zeta process" — a coupling of Gamma-distributed random variables across different primes/parameters — giving the sharper, non-asymptotic control needed for the $x$-uniform tail bound in Theorem 1.1. - Prior partial results this superseded/interfaced with. - Lichtman [Li23] (arXiv:2202.02384) obtained, as a corollary of the #164 proof, the weaker tail bound $f(A)$ for $a>x$ $<e^\gamma\pi/4+o(1)\approx1.399+o(1)$ — valid but not tight (target is $1$). - Lichtman, "Almost primes and the Banks–Martin conjecture," *J. Number Theory* (2020): for $A_k=\{n: n\text{ has exactly }k\text{ prime factors}\}$ (a primitive set $\subset[2^k,\infty)$), showed $\sum_{a\in A_k}1/(a\log a)\ge1+O(k^{-1/2+o(1)})$, conjecturing the true decay is $O(2^{-k})$. - Gorodetsky–Lichtman–Wong, "On Erdős sums of almost primes," *C.R. Acad. Sci. Paris* (2024): pinned the $A_k$ example exactly, $\sum_{a\in A_k}1/(a\log a)=1-(c+o(1))k^22^{-k}$, $c\approx0.0656$ — confirming the threshold in Theorem 1.1 really is $1$ and that convergence is fast, i.e. the almost-primes are near-extremal examples for the *tail* problem the way ordinary primes are extremal for the *global* problem. - AI provenance, on record. The method was "suggested from output of GPT-5.4 Pro" (paper abstract). Per the paper's §11 acknowledgments/AI-disclosure section (as reported by the sibling wiki page wiki/problems/164.md, itself sourced from a direct WebFetch read of that section): Theorem 1.1 (#1196) was first proved by a fully autonomous run of GPT-5.4 Pro; GPT-5.4 Pro also supplied the initial draft proof of Theorem 1.2 (#164); the named human co-author contribution was specifically constructing the downward divisor chain and suggesting the lemmas establishing sub-invariance. The abstract states the method "seems to have been overlooked by the prior literature since Erdős' seminal 1935 paper" — i.e. a 90-year-old elementary reframing (a Markov chain on the divisibility poset) that the entire prior sieve-theory literature on this problem family had not tried. - Formal verification. Both #164 and #1196 carry completed Lean 4 formalizations (per sibling pages: google-deepmind/formal-conjectures/FormalConjectures/ErdosProblems/1196.lean; and for #164, an independent formalization at github.com/plby/lean-proofs commit a9d31bc using Mathlib, built with OpenAI Codex, plus a second independent formalization using Math Inc.'s "Gauss" system). - The underlying general principle has a name: chain–antichain duality. A weight $\nu:\mathbb N\to[0,\infty)$ satisfies $\sum_{n\in A}\nu(n)\le M$ for *every* antichain $A$ in a poset if and only if there is a probability distribution over chains such that each $n$ lies on a sampled chain with probability $\ge\nu(n)/M$ — a form of Stanley's chain-polytope duality / LP (Farkas) duality for posets: since a chain meets any given antichain in at most one point, $\mathbb E[\#(\text{chain}\cap A)]\le1$ for the LHS event automatically converts into the weighted-antichain bound. The von Mangoldt chain is a specific, explicit, computable realization of the "hitting distribution over chains" side of this duality for the divisibility poset, with $\nu=\nu_0$ (or the exactly-invariant $\nu_\Lambda$) as the certifying weight.

Technique

When it applies. The target is an extremal bound $\sum_{n\in A}\nu(n)\le M$ (or an existence-of-comparable-density statement) that must hold uniformly over an unbounded, adversarially-chosen family of antichains in a poset with a rich multiplicative/arithmetic structure — canonically, primitive sets (antichains under divisibility) and weighted Erdős-type sums like $f(A)=\sum_a 1/(a\log a)$. It is the right tool exactly when: 1. The poset has enough arithmetic structure to define a natural "one small step down" transition (here: divide by a divisor $q$), and 2. There is an arithmetic identity normalizing that step into a genuine probability distribution (here: $\sum_{q\mid n}\Lambda(q)=\log n$, i.e. $\Lambda*1=\log$), and 3. The target weight $\nu$ is (sub-)invariant, or can be made (sub-)invariant after a suitable normalization/rescaling, under the resulting chain.

Why it works — the mechanism. 1. Antichain-hits-a-chain-at-most-once is the entire combinatorial content of "primitive." Two elements on the same divisibility chain are divisibility-comparable by construction, so a primitive (antichain) set $A$ can contain at most one element from any single sampled chain trajectory. This one observation converts "sum a weight over an adversarially-chosen antichain" into "sum a hitting-probability over one fixed stochastic process" — no case analysis on the structure of $A$ is needed at all, because the bound holds *trajectory by trajectory*, uniformly over every possible $A$ simultaneously. 2. Von Mangoldt weighting is the specific choice that makes the natural target weight ($1/(n\log n)$) (sub-)invariant. Any downward chain on the divisibility poset gives *some* antichain bound this way (e.g. the naive "divide by largest prime factor" Mertens chain), but the resulting bound is only as sharp as the invariance of $\nu$ under that particular chain. Von Mangoldt's $\Lambda$ is singled out because $\Lambda*1=\log$ is exactly the identity that makes a *direct estimate* of $\sum_q \nu_0(nq)\mathbb P(nq\searrow n)$ collapse to (essentially) $\nu_0(n)$ itself — i.e. the arithmetic of $\Lambda$ was "designed" (via its role as the logarithmic derivative of $\zeta$) to interact correctly with the $1/(n\log n)$ weight that Erdős's sum uses. 3. Sub-invariance + the antichain-hits-once fact deliver the master inequality "for free," no adversarial-A structure required. Once $\nu$ (or an $h_{b\searrow}$ built from it) is shown (sub-)invariant, the chain of inequalities $\sum_{n\in A}\nu(n)\le\sum_{n\in A}h_{b\searrow}(n)\le\sum_{n_0}b(n_0)$ closes the whole extremal problem — the middle inequality is the "hits at most once" observation, the outer equality/inequality is a routine (if occasionally delicate) potential-theory or analytic-number-theory computation localized to the *chain*, not to the antichain family. 4. The adjoint (upward) chain identifies the extremizer, not just the bound. Running the time-reversed, $\nu$-weighted chain starting from a candidate extremal boundary set (e.g. the primes) and checking that its hitting mass matches $\nu$ exactly is what promotes a mere upper bound into an equality-at-the-extremizer statement (Theorem 1.2, primes maximize $f$) — this is the potential-theoretic analogue of verifying a proposed optimal dual solution in a linear program. 5. The same machine re-plumbs for related problems by changing only three knobs: (i) which absorbing/boundary state set is used (all of $1$; the primes; a fixed prime-count layer $\mathbb N_k$), (ii) which sub-poset of divisors the chain is allowed to step through (all divisors; odd-prime divisors only, with corrective weights $\beta_p=p/(p-2)$, for Odd Banks–Martin), and (iii) which target weight is being certified as (sub-)invariant ($\nu_0(n)=1/(n\log n)$; the rescaled $\nu_2(n)=1/(n\log 2n)$ for "2 is Erdős-strong"). This is why one technique cracked #164, #1196, #1217, and Banks–Martin in a single paper.

The reusable recipe (for a new problem in this family, or a structurally analogous poset/antichain extremal question): 1. Identify the poset (here: divisibility on $\mathbb N$) and confirm the target quantity is a weighted sum over an antichain (primitive set) in that poset. 2. Look for a natural "elementary step down" with an accompanying arithmetic normalizing identity that turns it into a Markov transition (here: divide by $q\mid n$ weighted by $\Lambda(q)$, normalized by $\Lambda*1=\log$). If the poset is not divisibility, look for the structurally analogous convolution/normalizing identity. 3. Test (sub-)invariance of the target weight $\nu$ under the chain by direct computation; if it fails, try rescaling $\nu$ or restricting the allowed steps (e.g. odd-prime-only steps with corrective weights, as in Odd Banks–Martin) until it succeeds. 4. Invoke chain–antichain duality (a hitting chain meets any antichain at most once) to get $\sum_{n\in A}\nu(n)\le\sum_{n_0}b(n_0)$ for free, for every antichain $A$ simultaneously. 5. If an exact extremizer (not just an upper bound) is wanted, build the adjoint upward chain from the conjectured extremal boundary set and verify its hitting mass matches $\nu$ exactly. 6. Watch for uniformity/tail refinements (Theorem 1.1's $x\to\infty$ tail bound): these typically require upgrading a merely sub-invariant weight to an *exactly* invariant one (the paper's $\nu_\Lambda$ "zeta process" construction) to get error terms that shrink rather than just a qualitative bound.

Related

- Erdős #164 — primes maximize the primitive-set sum Σ1/(n log n) — the Erdős primitive set conjecture ("primes maximize $f(A)=\sum1/(n\log n)$ over primitive sets"); first proved by Lichtman via sieve theory (arXiv:2202.02384), reproved in five pages by this chain method (Theorem 1.2). - Erdős–Sárközy–Szemerédi (1966/1970) — primitive sets of large numbers: the tail Erdős-sum bound $\sum_{a\in A,\,a>x}1/(a\log a) < 1+o(1)$ — Erdős–Sárközy–Szemerédi tail-sum conjecture ($f(A)\le1+o(1)$ for primitive $A\subset[x,\infty)$ as $x\to\infty$); the flagship application (Theorem 1.1), first solved by an autonomous GPT-5.4 Pro run. - 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 divisibility-chains conjecture, resolved (Theorem 1.6) via a contrapositive/hitting-probability variant of the same chain. - concept/chain-antichain-duality — the general Stanley chain-polytope / LP-duality principle (a weighted-antichain bound holds for all antichains iff a chain-hitting-distribution certifies it) underlying why "meets a chain at most once" suffices; the von Mangoldt chain is this page's explicit, computable realization of that abstract principle for the divisibility poset. - Primitive sets (antichains in the divisibility poset: no element divides another) — the core combinatorial object (antichain under divisibility) that this whole technique and problem cluster (#164, #1196, #1217, Banks–Martin, "2 is Erdős-strong") is about. - Random-set construction + Janson's inequality / Vu concentration (the Poisson paradigm) — a structurally different but comparably "one auxiliary random process settles an extremal-combinatorics family" technique (Janson's inequality / Poisson paradigm for existence/concentration of random constructions); useful contrast in the same wiki for how randomized potential-theoretic machinery recurs across very different Erdős-problem clusters.