Erdős #164 — primes maximize the primitive-set sum Σ1/(n log n)

Statement

A set $A\subset\mathbb N_{>1}$ is primitive if no member of $A$ divides another (i.e. $A$ is an antichain in the divisibility poset $(\mathbb N,\mid)$). Erdős proved in 1935 [Er35] that $$f(A):=\sum_{a\in A}\frac{1}{a\log a}$$ is uniformly bounded over all primitive sets $A$. In 1986 [Er86] (also [Er76g], [Va99,1.12]) he asked: is this universal bound attained by the set of primes $\mathcal P$? I.e., does $$f(A)\le f(\mathcal P)=\sum_{p}\frac{1}{p\log p}\approx 1.6366\ldots$$ hold for every primitive set $A$? (erdosproblems.com/164)

Facts

- Status per erdosproblems.com/164: PROVED (LEAN) — solved in the affirmative, formally verified in Lean 4. - Origin: Erdős [Er76g], [Er86], restated in Erdős's own problem list [Va99, §1.12]; the underlying boundedness-of-$f(A)$ fact is Erdős 1935 [Er35]. - First proof: Jared Duker Lichtman, "A proof of the Erdős primitive set conjecture," arXiv:2202.02384 (Feb 2022, published *Forum of Mathematics, Pi* 11 (2023), e18, doi:10.1017/fmp.2023.16) — answered yes, by hand, no AI involvement (dated before the LLM era of this problem's later work). - Second, simpler, unifying proof: 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 (May 2026) — reproves #164 as one of several corollaries of a single new method (§5 of that paper), explicitly credited on erdosproblems.com as "[ABLLPSTT26]." - Background bound history on $f(A)$ for general primitive $A$ (WebSearch-sourced only, not independently primary-verified this session): trivial-argument bound $\approx e^\gamma\approx 1.781$ implicit already in Erdős's 1935 method; Erdős–Zhang (1993) improved to $f(A)<1.84$; Lichtman–Pomerance (2019) sharpened back to $f(A)\le e^\gamma\approx 1.781$; the true target $f(\mathcal P)\approx1.6366$ remained open until Lichtman 2022/2023 closed the gap. - Related/adjacent Erdős problems, all now touched by the same 2026 paper: 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 1968 conjecture that $\sum_{a\in A,\,a>x}1/(a\log a)<1+o(1)$ for primitive $A\subset[x,\infty)$ as $x\to\infty$ (the "large numbers" / tail refinement of #164, with $x=1$ recovering #164 itself); status PROVED (LEAN), first solved by an autonomous GPT-5.4 Pro query (prompted by paper co-author Liam Price), per erdosproblems.com/1196. Also mentioned there: Erdős–Sárközy–Szemerédi divisibility-chain conjecture #1217, the "Odd Banks–Martin" conjecture, and "$2$ is Erdős-strong" — all proved by the same von Mangoldt-Markov-chain method in arXiv:2605.00301.

Solution

Answer: yes — primes maximize $f(A)$ among all primitive sets. Two independent proofs exist; the second is the one worth generalizing.

1. Lichtman's original proof (2022/2023) — refining Erdős's 1935 disjoint-density argument. Erdős's 1935 method: for $a\in A$ write $P(a)$ for its largest prime factor, and note $a^{-1}\prod_{p<P(a)}(1-1/p)$ equals the natural density of $\mathrm L_a:=\{ba : p\mid b\Rightarrow p\ge P(a)\}$, the set of "lexicographic multiples" of $a$. Primitivity of $A$ forces the $\mathrm L_a$ to be pairwise disjoint, so their densities sum to $\le1$; combined with Mertens' theorem this gives the classical bound $f(A)<e^\gamma$ but nothing sharper — it treats every $a\in A$ as if it were prime, losing a factor $\log P(a)/\log a$ whenever $a$ is composite. Lichtman's key new ingredient (his Proposition 3.3) shows that when $P(a)^{1+v}>a$ uniformly across $A$, the sum of the $\mathrm L_a$-densities is in fact $\le\sqrt v$ rather than the trivial $1$ — proved by observing that not just the $\mathrm L_a$ but also $\mathrm L_{ac}$ for a whole range of auxiliary $c$ must stay disjoint, and these dilated sets are self-similar to the originals, forcing the extra $\sqrt v$-type saving. Integrating this saving over $v\in(0,1)$ produces an overall improvement factor of $\pi/4$ on the composite-only contribution; since $e^\gamma\pi/4\approx1.399<f(\mathcal P)\approx1.6366$, composite elements can never help beat the all-primes configuration, settling the conjecture. (arXiv:2202.02384, §1.1.)

2. The transferable technique (2026) — chain/antichain duality via a von Mangoldt-weighted Markov chain. This is the reusable idea worth extracting for other problems. A primitive set is an *antichain* in the divisibility poset $(\mathbb N,\mid)$; the *dual* objects are *divisibility chains* $n_0\mid n_1\mid n_2\mid\cdots$. By a Stanley chain-polytope / LP-duality argument (Stanley's theorem on antichain-indicator convex hulls, cf. Farkas' lemma), a weight $\nu:\mathbb N\to[0,\infty)$ satisfies $\sum_{n\in A}\nu(n)\le M$ for every antichain $A$ if and only if there is a probability distribution over divisibility chains such that each $n$ lies on the chain with probability $\ge \nu(n)/M$ — because a chain meets any given antichain in at most one point, so $\mathbb E[\sum_{n\in A}\mathbf 1_{n\in\text{chain}}]\le1$ automatically bounds the weighted antichain sum. The paper's specific realization: define the von Mangoldt downward Markov chain on $\mathbb N_{\ge1}$, where $n$ transitions to $n/q$ with probability $\Lambda(q)/\log n$ ($\Lambda$ = von Mangoldt function) — a valid Markov chain precisely because $\sum_{q\mid n}\Lambda(q)=\log n$. The weight $\nu_0(n)\asymp 1/(n\log n)$ (the *doubly-harmonic weight*, exactly the summand of $f$) turns out to be sub-invariant under this chain (Lemma 5.1: a direct computation using $\sum_q \Lambda(q)/(q\log^2(mq))\le1$, with a prime-power correction term bounded separately). Sub-invariance of $\nu_0$ lets one build an adjoint upward chain started with mass $\nu_0(p)$ at each prime $p$ (using primes as absorbing states going downward), and a short induction shows the resulting "hitting function" $h(n)=\nu_0(n)$ exactly, for every $n\ge1$. Plugging into the duality inequality immediately gives $\sum_{n\in A}\nu_0(n)\le\sum_p\nu_0(p)$ for every primitive $A$ — i.e. $f(A)\le f(\mathcal P)$, a five-page proof of the full conjecture, versus Lichtman's original ~20-page argument with its bespoke $\sqrt v$-saving calculus. Why this is the transferable engine: the *same* single Markov-chain machine (only the choice of transition rule and absorbing-state set changes) is reused in the same paper to prove #1196 (large-number tail sums), #1217 (Erdős–Sárközy–Szemerédi divisibility chains), the "Odd Banks–Martin" conjecture, "$2$ is Erdős-strong," and to reprove an Ahlswede–Khachatrian–Sárközy inequality — the authors explicitly note the method "seems to have been overlooked by the prior literature since Erdős' seminal 1935 paper" despite unifying five-plus previously-separate extremal results. The generalizable recipe for a new primitive-set/divisibility-poset problem: (i) identify the target weight $\nu$ (usually the summand of the extremal sum in question); (ii) find or construct a downward Markov chain on the poset for which $\nu$ is invariant or sub-invariant; (iii) take the adjoint upward chain from the desired absorbing set (e.g. primes, or a fixed prime-count layer $\mathbb N_k$); (iv) chain/antichain duality then hands you the extremal inequality for free. AI-involvement, on record (arXiv:2605.00301, §11, "Acknowledgments and AI disclosure," read verbatim): the paper's Theorem 1.1 (#1196) was first proved by a fully autonomous run of GPT-5.4 Pro, and GPT-5.4 Pro also supplied the initial proof draft of Theorem 1.2 (the #164 reproof in Section 5 above), with the *named* human contribution being specifically "the downward divisor chain and suggesting Lemmas 3.2 and 3.3(ii) to establish the sub-invariance property." A Lean 4 formalization of Erdős #164 itself exists at github.com/plby/lean-proofs (commit a9d31bc, Mathlib v4.29.0), built with OpenAI's Codex; a second, independent Lean formalization used Math Inc.'s "Gauss" system. This is a directly-documented case of an LLM finding the seed idea for a technique that then got reused across an entire cluster of previously-open Erdős problems — a strong positive precedent for "derivation via AI-suggested reusable machinery," not just recombination of known results.

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)$ — Erdős–Sárközy–Szemerédi 1968 "large numbers" tail-sum refinement of #164; first solved by an autonomous GPT-5.4 Pro query, then folded into the same unifying Markov-chain paper; the $x=1$ case degenerates to #164 itself. - Erdős #165 — asymptotic formula for the Ramsey number R(3,k) — the $R(3,k)$ Ramsey problem; unrelated subject matter, but a useful methodological contrast: still open after 65 years despite comparable 2025–2026 AI-adjacent activity (Lean autoformalization only, no new AI-generated mathematics found), whereas #164's neighborhood (#164, #1196, #1217, Banks–Martin) was fully cracked by an AI-suggested unifying technique in the same period — evidence that "how amenable is the *technique layer*" (LP/chain duality here vs. genuinely open extremal-graph-theory constructions there) matters more than problem age or fame for near-term AI tractability. - concept/chain-antichain-duality — the Stanley chain-polytope / LP-duality principle: a weighted antichain bound $\sum_{n\in A}\nu(n)\le M$ holds for all antichains iff a probability distribution over chains hits each $n$ with probability $\ge\nu(n)/M$. The general engine behind this page's Solution §2; directly reusable for any extremal-antichain problem in a poset, not just divisibility. - concept/von-mangoldt-markov-chain — the specific downward chain $P(n\searrow n/q)=\Lambda(q)/\log n$ on the divisibility poset, and the sub-invariance-of-$\nu_0(n)\asymp1/(n\log n)$ trick that makes it the right chain for primitive-set sum problems; documented in full technical detail (transition rule, sub-invariance proof, adjoint-upward-chain construction) in this page's Solution §2. - concept/l-primitive-sets — Lichtman's original (2022) weaker-than-primitive notion and the disjoint-lexicographic-multiples ($\mathrm L_a$) machinery with the $\sqrt v$-saving Proposition 3.3; the first (harder, hand-proved) route to #164, superseded in simplicity but not chronological priority by the 2026 Markov-chain proof. - concept/lean-autoformalization-agent — two independent Lean 4 formalizations of #164 exist (OpenAI Codex at github.com/plby/lean-proofs commit a9d31bc; Math Inc.'s Gauss), both referenced in arXiv:2605.00301's bibliography — direct machine-checked confirmation of the human-reviewed AI-suggested proof.