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

Statement

Let $A \subset \mathbb{N}$ have positive upper doubly logarithmic density $$\Delta := \limsup_{x\to\infty} \frac{1}{\log\log x} \sum_{n \in A \cap [2,x]} \frac{1}{n\log n} > 0.$$ Erdős, Sárközy and Szemerédi conjectured (1966) that $A$ must then contain a strictly increasing infinite divisibility chain $n_0 \mid n_1 \mid n_2 \mid \cdots$ inside $A$ whose own counting function grows at essentially the same doubly-log rate: $$\limsup_{x\to\infty} \frac{1}{\log\log x}\,\#\{i : n_i \le x\} \ \ge\ \Delta.$$ (Erdős problem #1217; restated verbatim as "Theorem 6" / "Theorem 1.6" in the solving paper, cross-checked at [terrytao.wordpress.com](https://terrytao.wordpress.com/2026/05/03/primitive-sets-and-von-mangoldt-chains-erdos-problem-1196-and-beyond/) and [arXiv:2605.00301](https://arxiv.org/abs/2605.00301).)

This is a quantitative strengthening of the classical Davenport–Erdős theorem (1936/37): if $A$ has positive upper *logarithmic* density ($\limsup_x \frac{1}{\log x}\sum_{n\in A, n\le x} 1/n > 0$), then $A$ contains *some* infinite divisibility chain (original proof via the Hardy–Littlewood Tauberian theorem; an elementary proof was found later — see [en.wikipedia.org/wiki/Davenport–Erdős_theorem](https://en.wikipedia.org/wiki/Davenport%E2%80%93Erd%C5%91s_theorem)). ESS 1966 asked for a much sparser hypothesis (density measured on the doubly-logarithmic $\log\log x$ scale, i.e. sets far too thin to have positive ordinary or logarithmic density) and a *matching quantitative lower bound* on how many terms of the chain occur below $x$, not merely existence.

Facts

- Origin: Erdős, Sárközy & Szemerédi, "On the divisibility properties of sequences of integers I," *Acta Arithmetica* 11 (1966), 411–418 — the first of an eventual 52 joint Erdős–Sárközy–Szemerédi papers (per the Szemerédi publication list, [renyi.hu/~szemered/pub.html](https://www.renyi.hu/~szemered/pub.html)); the same 1966 paper is where the companion conjecture on primitive sets (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)$) was also posed. - Precursor already proved in the 1966 paper itself: ESS 1966 showed any divisibility chain $D$ satisfies $\limsup_{y\to\infty} \sum_{d\in D,\,d\le y} 1/d \big/ \sqrt{\log\log y} > 0$, with this $\sqrt{\log\log y}$ growth rate shown best possible — a quantification of the Davenport–Erdős theorem. Problem #1217 is the harder, dual "density $\Rightarrow$ chain of matching density" direction that they left open. - Status: SOLVED (2026), alongside the companion 1966 conjecture on primitive sets, 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)$. Both were open for sixty years. - Solving paper: Boris Alexeev, Kevin Barreto, Yanyang Li, Jared Duker Lichtman, Liam Price, Jibran Iqbal Shah, Quanyu Tang, Terence Tao, "Primitive sets and von Mangoldt chains: Erdős Problem #1196 and beyond," arXiv:2605.00301 (2026) — [arxiv.org/abs/2605.00301](https://arxiv.org/abs/2605.00301). Announced by Tao at [terrytao.wordpress.com/2026/05/03/…](https://terrytao.wordpress.com/2026/05/03/primitive-sets-and-von-mangoldt-chains-erdos-problem-1196-and-beyond/). - Notably, per the paper's own abstract, the core new method was "suggested from output of GPT-5.4 Pro" — an explicit case of AI-assisted discovery of a genuinely new proof technique, not just AI-assisted verification. - The same paper's single method also resolves: the flagship Erdős primitive-set conjecture #1196 ($\sum_{n\in A} 1/(n\log n) \le 1+o(1)$ for primitive $A$, extending Lichtman's earlier partial result, arXiv:2202.02384, "A proof of the Erdős primitive set conjecture," *Forum of Mathematics, Pi* 2023); primitive-set conjecture #164; the odd Banks–Martin conjecture; and "2 is Erdős-strong." - Formalization: not found in this search pass (unconfirmed either way).

Solution

Answer: the 1966 conjecture is TRUE — positive upper doubly logarithmic density of $A$ forces an infinite divisibility chain inside $A$ whose counting function matches that density up to the $\limsup$.

**The transferable technique — turn a *sum-bound* problem on sets into a *random-chain-construction* problem via a Markov chain that is exactly (sub-)invariant under the Erdős-sum weight, then use chain/antichain duality.**

1. Chain/antichain duality as the master reduction. A primitive set (antichain under divisibility) and a divisibility chain are dual objects on the same poset ($\mathbb{N}, \mid$). Instead of directly bounding $\sum_{n\in A} 1/(n\log n)$ for an antichain (or, dually here, exhibiting a chain of matching density inside a dense-enough $A$), construct a *probability measure on divisibility chains* through $\mathbb{N}$ such that each integer $n$ is "hit" by a random chain with probability proportional to its target weight $1/(n\log n)$. If such a measure exists, an antichain can meet each sampled chain at most once, which immediately caps $\sum_{n\in A}(\text{weight})$; conversely a set with enough weight must, on average, be hit by enough of the chain's own steps to force a long realized chain inside it. This single probabilistic object drives both the #1196 (primitive-set upper bound) and #1217 (divisibility-chain lower bound) results. 2. Two competing random chains, and why the second one wins. The paper compares: - the Downwards Mertens Chain — deterministically divides $n$ by its largest prime factor $P(n)$ at each step; invariant under weight $1/(n\log P(n))$ but this incurs an unavoidable $e^\gamma$ multiplicative loss (Mertens' theorem constant) relative to the true target weight $1/(n\log n)$; - the Downwards von Mangoldt Chain — at each step, divides $n$ by a random prime power $q\mid n$, chosen with probability proportional to the von Mangoldt weight $\Lambda(q) = \log q$ (nonzero only on prime powers). Because $\sum_{q\mid n}\Lambda(q) = \log n$ (the identity encoding the fundamental theorem of arithmetic / Chebyshev's $\theta$-$\psi$ machinery directly into the one-step transition probabilities), this chain is sub-invariant under exactly the weight $1/(n\log n)$ that appears in the Erdős-sum conjectures — and it does so *without* the $e^\gamma$ loss that plagued the Mertens chain. This is the paper's central new device, and per the abstract it was "suggested from output of GPT-5.4 Pro." 3. The "zeta process" refinement used specifically for #1217. To get the *continuous, infinite, increasing* chain needed for the divisibility-chain conjecture (rather than a single finite decrement path), the paper builds a continuous-time coupling of "zeta distributions" — random variables governed by the invariant measure $\nu_\Lambda(n) := \int_1^\infty \frac{\log n}{\zeta(s)\,n^s}\,ds$ — into one continuous stochastic divisibility chain climbing upward through $\mathbb{N}$ (Section 10.2 of arXiv:2605.00301, per Tao's post). Sampling this process and showing it must, with the required $\limsup$ frequency, pass through the dense set $A$ is what produces the matching-density infinite chain the conjecture demands. 4. Why this is the reusable idea for downstream (still-open) problems. The pattern — (a) identify the exact multiplicative weight ($1/(n\log n)$, via von Mangoldt) that an Erdős-type sum conjecture is stated in; (b) find *the* Markov/random process on the divisibility poset that is exactly (sub-)invariant under that weight; (c) invoke chain/antichain duality to convert a sum-bound (primitive-set) question and a chain-existence (divisibility-chain) question into the *same* probabilistic object — is now a template for any further Erdős-sum conjecture on primitive sets or divisibility chains. It is explicitly what let one method crack five separate named conjectures (#1196, #164, odd Banks–Martin, "2 is Erdős-strong," #1217) in a single paper, and it is the natural next tool to try on any remaining open Erdős-sum-on-primitive-sets question.

Bottom line for downstream use: the "von Mangoldt chain method" = (i) find the Markov chain on $(\mathbb{N},\mid)$ that is exactly (sub-)invariant under your target Erdős-sum weight (canonically $\Lambda(q)/$-weighted random division by prime powers, using $\sum_{q\mid n}\Lambda(q)=\log n$), (ii) use chain/antichain duality to turn antichain sum-bounds and chain-density lower bounds into statements about the same random process, (iii) if an *infinite* chain is needed, couple the process's stationary/zeta-type distributions across scales into one continuous "zeta process." This is the technique to link as `concept/von-mangoldt-chain-method`.

Related

- 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)$ — the companion 1966 Erdős–Sárközy–Szemerédi conjecture on primitive sets ($\sum_{n\in A}1/(n\log n)\le 1+o(1)$), posed in the same 1966 paper and solved by the same paper/method. - concept/von-mangoldt-chain-method — the transferable technique: build a Markov chain on the divisibility poset (sub-)invariant under the target Erdős-sum weight via the von Mangoldt identity $\sum_{q\mid n}\Lambda(q)=\log n$, then exploit chain/antichain duality; used to resolve #1196, #1217, #164, the odd Banks–Martin conjecture, and "2 is Erdős-strong" in one paper. - Primitive sets (antichains in the divisibility poset: no element divides another) — antichains under divisibility; the dual notion to divisibility chains, and the object of the sibling conjecture #1196. - concept/davenport-erdos-theorem — the classical 1936/37 ancestor result (positive upper logarithmic density $\Rightarrow$ some infinite divisibility chain exists), of which #1217 is the sparse-density, matching-rate quantitative strengthening.