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)$

Statement

(Verbatim, erdosproblems.com/1196.) Is it true that, for any $x$, if $A\subset[x,\infty)$ is a primitive set of integers (no distinct elements of $A$ divide each other) then $$\sum_{a\in A}\frac{1}{a\log a} < 1+o(1),$$ where the $o(1)$ term $\to 0$ as $x\to\infty$?

This is the "large numbers" refinement of the more famous Erdős primitive set conjecture (Erdős #164 — primes maximize the primitive-set sum Σ1/(n log n)): that $\sum_{a\in A}1/(a\log a)$ over *all* primitive sets $A\subset\mathbb N$ (the $x=1$ case) is maximized by $A=$ the set of primes. Problem #1196 asks whether, once you restrict to elements $a>x$, the same threshold-$1$ bound survives *uniformly* as $x\to\infty$ — i.e. whether "almost all of the mass" any primitive set can carry above $x$ is capped by the tail contribution the primes themselves would carry.

Facts

- Origin: a conjecture of Erdős, Sárközy, Szemerédi, "On divisibility properties of sequences of integers" [ESS68b] (published 1970, pp. 35–49, MR279064; commonly dated "1966" in secondary literature — the exact submission/announcement date was not independently re-verified here), also stated in Erdős's 1980 survey "A survey of problems in combinatorial number theory," Ann. Discrete Math., p.101 [Er80]. - Companion problem, same family: Erdős #164 — primes maximize the primitive-set sum Σ1/(n log n), the $x=1$ special case — "is $\sum_{n\in A}1/(n\log n)$ maximised over primitive sets by the set of primes?" Erdős himself [Er35, 1935] proved the sum always *converges* for any primitive set (the foundational finiteness result the whole family sits on top of), but the extremality claim stayed open for 88 years. - Partial progress before the full solution: - Jared D. Lichtman, "A proof of the Erdős primitive set conjecture" [Li23], arXiv:2202.02384 (2023) — proved Erdős #164 — primes maximize the primitive-set sum Σ1/(n log n) in full (primes are extremal), and as a corollary obtained the tail bound $\sum_{a\in A,\,a>x}1/(a\log a) < e^\gamma\pi/4+o(1)\approx 1.399+o(1)$ for #1196 — a valid but *not* tight upper bound (target constant is $1$). - Lichtman, "Almost primes and the Banks–Martin conjecture" [Li20], J. Number Theory (2020) — showed the bound can't be pushed below $1$ too fast: for $A_k=$ integers with exactly $k$ prime factors (a primitive set $\subset[2^k,\infty)$), $\sum_{a\in A_k}1/(a\log a)\ge 1+O(k^{-1/2+o(1)})$, and conjectured the true decay rate is $O(2^{-k})$. - Gorodetsky, Lichtman, Wong, "On Erdős sums of almost primes" [GLW24], C. R. Math. Acad. Sci. Paris (2024) — pinned the $A_k$ example down exactly: $\sum_{a\in A_k}1/(a\log a) = 1-(c+o(1))k^2 2^{-k}$ for an explicit constant $c\approx0.0656$, confirming the threshold really is $1$ and that convergence to it is fast. - Full solution: erdosproblems.com's status badge reads "PROVED (LEAN)". The site credits the resolution to GPT-5.4 Pro, prompted by (co-author) Liam Price, which proved the sharp form: for any primitive set $A\subset\mathbb N$, $$\sum_{\substack{a\in A\\ a>x}}\frac{1}{a\log a} \le 1+O\!\left(\frac{1}{\log x}\right).$$ A full written account of the proof and method is given in B. Alexeev, K. Barreto, Y. Li, J. D. Lichtman, L. Price, J. I. Shah, Q. Tang, T. Tao, "Primitive sets and von Mangoldt chains: Erdős Problem #1196 and beyond," arXiv:2605.00301 [ABLLPSTT26] (submitted 1 May 2026). The problem is formalised in Lean (google-deepmind/formal-conjectures, FormalConjectures/ErdosProblems/1196.lean, linked directly from the problem page). - The same paper reuses its method to also resolve: 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 (divisibility chains, another 1966/1968 ESS conjecture), gives a short, simpler re-proof of Erdős #164 — primes maximize the primitive-set sum Σ1/(n log n) (the Erdős primitive set conjecture, already proved by Lichtman via a different route), and settles a revised Banks–Martin conjecture, described by the authors as a long-standing unifying "master theorem" for this whole area — i.e. one new technique cracked four related open problems in the same paper. - Why this is notable as a moat/technique event, not just a result: the abstract states plainly that the Markov-chain-with-von-Mangoldt-weights method "seems to have been overlooked by the prior literature since Erdős's seminal 1935 paper" — a 90-year-old elementary reframing, missed by the entire sieve-theory literature on this exact problem family, surfaced by an LLM's suggested proof strategy and then written up rigorously by human co-authors (including Terence Tao). This wiki's sibling page Erdős #143 — integer dilations $|kx-y|\\geq1$ force sparsity? independently documents (via the teorth/erdosproblems GitHub "AI contributions" wiki) that this is explicitly credited as GPT-5.4-Pro-seeded.

Solution

Answer: YES. For any primitive set $A\subset\mathbb N$, $\displaystyle\sum_{a\in A,\,a>x}\frac1{a\log a}\le 1+O(1/\log x)\to 1$ as $x\to\infty$ — matching the conjectured threshold exactly, with the $O(1/\log x)$ rate; the [Li20]/[GLW24] almost-prime examples show the threshold $1$ itself cannot be lowered.

**The transferable technique — turn a global extremal-combinatorics bound over *all* primitive sets into a single potential-theory computation for one auxiliary Markov chain:**

1. Encode "no element divides another" as "meets each random divisor-chain at most once." Define, on the positive integers, the von Mangoldt downward chain: from state $n\ge2$, transition to $n/q$ with probability $\mathbb P(n\downarrow n/q) = \Lambda(q)/\log n$ for each divisor $q\mid n$, where $\Lambda$ is the von Mangoldt function ($\Lambda(p^k)=\log p$, else $0$). This is a genuine probability distribution because $\sum_{q\mid n}\Lambda(q)=\log n$ — the classical identity $\Lambda * 1 = \log$. Each sample path of this chain is a strictly decreasing divisibility chain $n=n_0 \mid$-chain$\downarrow n_1\downarrow\cdots\downarrow 1$. Because a primitive set by definition contains no two elements where one divides the other, any single such chain can pass through at most one element of $A$ — this one observation is the entire combinatorial content of "primitive." 2. Push a mass distribution through the chain and track where it lands ("downward hitting mass"). Assign an initial mass $b(n_0)$ to integers (chosen to match the Erdős-sum weights $1/(n\log n)$ being bounded), and define $h_{b\downarrow}(n)=$ the total mass of chain trajectories (started anywhere) that ever pass through state $n$. Because each trajectory can hit $A$ at most once (step 1), summing this hitting mass over $A$ can never double-count a trajectory's mass: $$\sum_{n\in A} h_{b\downarrow}(n) \;\le\; \sum_{n_0} b(n_0).$$ This single inequality is the whole engine: it converts "bound a sum over an *arbitrary, adversarially chosen* primitive set" — a genuinely hard extremal-combinatorics question, since $A$ ranges over an unbounded family of antichains-under-divisibility — into "bound the total mass of one fixed, explicitly constructed random process," which is an ordinary (if delicate) analytic/Dirichlet-series computation. 3. Choose the initial mass to make the two sides of the inequality literally equal the target sum. By picking $b(n)$ as a divisor-sum correction of the natural weight $\nu_0(n)=1/(n\log n)$ (a "sub-invariant measure" for the chain — its total mass doesn't increase as it's pushed forward), a downward-induction argument shows $h_{b\downarrow}(n)=\nu_0(n)$ exactly on the range of interest. Plugging this into step 2's inequality and evaluating the right-hand side (now a concrete double sum over $n<x$ and divisors/prime-powers $q$, weighted by $\Lambda(q)/(q\log^2(nq))$) reduces the *entire open conjecture* to bounding one explicit analytic sum — closed by a routine (if careful) estimate, giving exactly the $1+O(1/\log x)$ bound. 4. The same chain, re-plumbed, is a "master key" for the whole problem family. Absorbing the chain at primes instead of at $1$, and using sub-invariance of $\nu_0$ again but with the *adjoint* (upward) chain started with mass on the primes, reproves Erdős #164 — primes maximize the primitive-set sum Σ1/(n log n) (primes are the extremal primitive set) in a few lines — a short re-proof of a result that originally took Lichtman a much longer sieve-theoretic argument. Restricting the chain to divide only by primes, with an adjusted weight $\beta_p=p/(p-2)$, resolves the Banks–Martin "master conjecture" the same way. A contrapositive/hitting-probability version of the same chain settles 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 (divisibility chains). 5. Portable lesson for downstream open problems: whenever a problem quantifies over "all antichains/primitive sets under a partial order" (here: divisibility) and asks for an extremal bound on a weighted sum, check whether the order admits a natural random walk that visits each chain-respecting object at most once. If so, the extremal bound over the whole (unbounded, combinatorially wild) family of antichains collapses to one potential/hitting-mass computation for a single fixed stochastic process — turning a sieve-theory problem into a Markov-chain problem. This is the reusable move, and per the authors it had simply never been tried on this 90-year-old problem before an LLM suggested it.

Related

- Erdős #164 — primes maximize the primitive-set sum Σ1/(n log n) — the $x=1$ special case, the original Erdős primitive set conjecture ("primes maximize $\sum 1/(n\log n)$ over primitive sets"); first proved by Lichtman (arXiv:2202.02384) via a longer sieve argument, then reproved with a short proof by the same von-Mangoldt-chain method that solves this page. - 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, another 1966/1968-era ESS problem, proved in the same paper (arXiv:2605.00301) via a contrapositive/hitting-probability variant of the same chain. - Erdős #143 — integer dilations $|kx-y|\\geq1$ force sparsity? — the real-valued "integer dilation approximation" generalization of the primitive-set family; sibling wiki page independently documenting arXiv:2605.00301's chain method and its GPT-5.4-Pro-seeded provenance (via the teorth/erdosproblems GitHub "AI contributions" wiki), plus a *different* still-open sub-question in the same family (solved there via GCD-graph machinery, not this chain). - Primitive sets (antichains in the divisibility poset: no element divides another) — the core object (no element divides another / antichain under divisibility) common to this whole problem cluster (#164, #1196, #1217, #143, Banks–Martin). - Von Mangoldt-weighted Markov chains for primitive-set (Erdős) sums — the reusable Markov-chain-with-$\Lambda$-weights technique itself: state space $\mathbb N$, transition $\mathbb P(n\downarrow n/q)=\Lambda(q)/\log n$, validity from $\sum_{q\mid n}\Lambda(q)=\log n$, and the "hits any primitive set at most once" potential-bound argument that is this page's transferable idea. - GCD graphs (Koukoulopoulos–Maynard graph-theoretic sieve) — the Duffin–Schaeffer-derived graph-theoretic technique used for the still-*open* first sub-question of Erdős #143 — integer dilations $|kx-y|\\geq1$ force sparsity?; a useful contrast for which of the two primitive-set toolkits (chains vs. GCD graphs) applies to a given downstream question. - Lean 4 formalization of constructions and conditional reductions (Erdős-problem context) — this problem carries a completed Lean formalisation (google-deepmind/formal-conjectures, FormalConjectures/ErdosProblems/1196.lean), one of the concrete AI-assisted formal-verification data points in that concept page.