Erdős #858 — max Erdős-sum over sets avoiding \"a·t=b, spf(t)>a\" chains

Statement

Let $A\subseteq\{1,\ldots,N\}$ be such that there is no solution to $$at=b,\qquad a,b\in A,\ \text{smallest prime factor of } t > a.$$ (I.e. $A$ contains no pair $a,b$ with $b/a=t$ an integer whose least prime factor exceeds $a$ itself — a condition strictly weaker than the classical *primitive-set* condition "no element of $A$ divides another.") Estimate the maximum of $$\frac{1}{\log N}\sum_{n\in A}\frac{1}{n}.$$

Source: [Er70, p.128]; erdosproblems.com/858.

Facts

- Status: SOLVED, but erdosproblems.com tags it with its "resolved in some other way than a proof or disproof" badge rather than "PROVED (LEAN)" — the community-vetted writeup exists in a forum thread and companion informal notes, with a *partial* Lean formalization (2 remaining sorrys: a Mertens'-theorem estimate and one other standard analytic fact) rather than a fully machine-checked proof. - This condition is a genuine weakening of "primitive" (no element divides another). The classical primitive-set bound is due to Behrend [Be35]: if $A$ is primitive then $\frac1{\log N}\sum_{n\in A}\frac1n \ll \frac1{\sqrt{\log\log N}}$, witnessed by $A=\{$ integers in $[N^{1/2},N]$ divisible by some prime $>N^{1/2}\}$. - Under the *weaker* #858 condition, Alexander [Al66] and Erdős–Sárközy–Szemerédi [ESS68] had shown only that for any fixed infinite such $A$, $\sum_{n\in A\cap[1,N]}1/n=o(\log N)$ (rate depending on $A$), while the *supremum* over all valid finite $A\subseteq\{1,\ldots,N\}$ stays bounded away from $0$ as $N\to\infty$ — i.e. the qualitative decay-to-zero was known, but not the sharp constant. (Terence Tao's comment on the thread flags that the main writeup's phrasing of this prior result needed correction: the convergence to $0$ is *not* uniform in $A$, which is exactly why $\sup_A$ stays bounded away from $0$ even though each fixed infinite $A$ individually satisfies $o(\log N)$.) - **See also Erdős #143 — integer dilations $|kx-y|\\geq1$ force sparsity? — Erdős's still-open** \$500 problem asking whether an even *stronger* metric condition ($|kx-y|\ge1$ for all $x\ne y\in A$, integers $k\ge1$) forces $A$ sparse / forces $\sum 1/(x\log x)<\infty$; #858's condition and #143's are both weakenings/variants of the primitive-set hierarchy that Behrend's bound was the first result on. - **See also 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 Erdős–Sárközy–Szemerédi conjecture that primitive sets satisfy $\sum_{a\in A}1/(a\log a)<1+o(1)$; this was *itself* solved (also credited to "GPT-5.4 Pro," prompted by Liam Price) shortly before #858, and #858's solver explicitly describes #858 as "the cleanest application of ideas from [1196]'s solution with sub-Markov chains." The full method (for #1196, #858, and further primitive-set problems) is written up in Alexeev, Barreto, Li, Lichtman, Price, Shah, Tang, Tao, "Primitive sets and von Mangoldt chains: Erdős Problem #1196 and beyond," arXiv:2605.00301 [ABLLPSTT26]. - The named human contributors on the #858 thread are Przemek Chojecki (posted the solution, 15–24 Apr 2026) and Nat Sothanaphan (independent correctness checks that surfaced "minor issues" through several revision rounds) and Terence Tao (gave the clean flow-network restatement of the proof and corrected the historical attribution).

Solution

Answer. For large $N$, $$\max_{A}\sum_{n\in A}\frac1n=(c+o(1))\log N,\qquad c\approx0.6187712111\ldots,$$ the maximum over all $A\subseteq\{1,\ldots,N\}$ satisfying the stated chain-avoidance condition. Equivalently $\frac1{\log N}\sum_{n\in A}\frac1n\to c$ (compare Behrend's $O(1/\sqrt{\log\log N})\to0$ bound for the *strictly stronger* primitive condition — the weaker #858 hypothesis allows a genuine positive-density-in-$\log$ answer instead of decay to $0$).

The transferable technique — encode the chain relation as a functional flow network, then use the discrete divergence theorem to turn a global extremal-antichain problem into a local sign computation via Mertens' theorem. (Terence Tao's summary comment on the thread, condensed.)

1. Build a flow (a "sub-Markov chain" / von Mangoldt-weighted functional graph) on $\{1,\ldots,N\}$. For $n<p_1\le p_2\le\cdots\le p_k$ primes such that $n\,p_1\cdots p_{i-1}<p_i$ fails to hold for every $1<i\le k$ (a canonical "first-violation" factorization rule), put a directed edge of weight $$w\bigl(n\,p_1\cdots p_k \to n\bigr)=\frac1{n\,p_1\cdots p_k}.$$ Because the rule picks out a *unique* such factorization for each integer $m=n p_1\cdots p_k>1$, every $m$ has exactly one outgoing edge — this is what makes it a *functional* graph (a forest of chains, i.e. a sub-Markov / absorbing-chain structure), and consequently the total outflow at any node $1<n\le N$ sums telescopically to exactly $1/n$. 2. The chain-avoidance hypothesis becomes an antichain condition on the flow. By construction, downward flow starting from any $n$ eventually reaches smaller integers exactly along solutions of $a t=b$ with spf$(t)>a$-type steps; the hypothesis on $A$ says precisely that flow originating in $A$ can never terminate in another element of $A$. So $A$ sits as an *antichain* with respect to this flow order — the discrete analogue of "primitive." 3. Apply the discrete divergence theorem. Let $U_A\subseteq\{1,\ldots,N\}$ be the "upset" of $A$ — all integers whose flow eventually reaches an element of $A$. Since every unit of outflow from $A$ is "captured" (never re-enters $A$), $\sum_{n\in A}1/n$ can be rewritten as the sum, over $U_A$, of the *local divergence* (outflow − inflow) at each node — a purely algebraic identity converting a global sum-over-an-extremal-set into a sum of local quantities. 4. Compute the sign of the local divergence via Mertens' theorem. Routine prime-density (Mertens-type) asymptotics show the divergence at $n$ is positive (net source — more mass flows out of $n$ than into it) once $n>N^{\alpha_2+o(1)}$, and negative (net sink) once $n<N^{\alpha_2-o(1)}$, for an explicit threshold constant $$\alpha_2=0.28043830989\ldots$$ 5. Read off the extremal $A$ and the constant. Because divergence is positive above the threshold and negative below it, the sum $\sum_{n\in U_A}\mathrm{div}(n)$ (hence $\sum_{n\in A}1/n$) is maximized by taking $A$ to be (essentially) the elements above $N^{\alpha_2}$ whose flow lands below $N^{\alpha_2}$ — i.e. greedily keep every positive-divergence node and cut the flow exactly at the sign change. Carrying out the resulting Mertens'-theorem sum gives the stated constant $$c=c_2=0.6187712111\ldots$$ 6. Why this generalizes. The same three-step skeleton — (a) find a canonical unique-parent/unique-successor rule turning the divisibility/chain relation into a *functional* flow graph so outflow-per-node telescopes to a simple closed form ($1/n$ here); (b) rewrite the extremal-antichain sum via the discrete divergence theorem as a sum of *local* signed quantities over the associated upset; (c) determine the sign-change threshold of the local divergence using classical multiplicative-number-theory density estimates (Mertens' theorem / von Mangoldt weights) — is exactly the method introduced to crack the harder Erdős–Sárközy–Szemerédi conjecture 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)$ (primitive sets, $\sum1/(a\log a)<1+o(1)$), and #858 is presented by its solver as the "cleanest" template application of it. This is the reusable idea for other primitive-set-type Erdős-sum problems: turn "no chain from $A$ to $A$" into "$A$ is a cut of a flow network," then compute the extremal cut by a local Mertens'-theorem sign flip instead of a global combinatorial argument.

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 Erdős–Sárközy–Szemerédi primitive-set conjecture $\sum_{a\in A}1/(a\log a)<1+o(1)$; source of the "Markov chain with von Mangoldt weights" / sub-Markov-chain technique that #858 reapplies in its cleanest form. Also solved by GPT-5.4 Pro (prompted by Liam Price); write-up Alexeev–Barreto–Li–Lichtman–Price–Shah–Tang–Tao, arXiv:2605.00301. - Erdős #143 — integer dilations $|kx-y|\\geq1$ force sparsity? — open, \$500: does the stronger metric condition $|kx-y|\ge1$ force $A$ sparse? erdosproblems.com cross-links #858 and #143 to each other; both sit in the same primitive-set/Behrend-bound hierarchy, and a sharpened flow/divergence argument in the #858 style is a natural next thing to try there. - Primitive sets (antichains in the divisibility poset: no element divides another) — the classical divisibility-antichain condition (Behrend 1935 upper bound $O(1/\sqrt{\log\log N})$; sum-of-reciprocals convergence Erdős 1935) that #858's hypothesis weakens. - concept/discrete-divergence-theorem — the flow/mass-transport identity (local outflow−inflow summed over an upset equals the boundary sum) that is the technical engine of the proof. - concept/mertens-theorem — supplies the prime-density asymptotics used to locate the sign-change threshold $\alpha_2\approx0.2804\ldots$ of the local divergence. - Lean 4 formalization of constructions and conditional reductions (Erdős-problem context) — a streamlined version of the #858 argument was partially formalized by "Aristotle," handling the sub-Markov-chain/dynamic-programming combinatorics cleanly but leaving 2 sorrys (a Mertens'-theorem estimate and one other analytic fact) not yet in mathlib.