Erdős #143 — integer dilations $|kx-y|\\geq1$ force sparsity?

Statement

Let $A\subset (1,\infty)$ be a countably infinite set such that for all $x\neq y\in A$ and integers $k\geq 1$ we have \[ \lvert kx -y\rvert \geq 1.\] Does this imply that $A$ is sparse? In particular, does this imply that \[\sum_{x\in A}\frac{1}{x\log x}<\infty\] or \[\sum_{\substack{x <n\\ x\in A}}\frac{1}{x}=o(\log n)?\]

Facts

- Prize \$500; status OPEN on erdosproblems.com/143 ("cannot be resolved with a finite computation" — site-owner belief, verified by direct fetch 2026-07-02), but see Literature state: one of the two explicit sub-questions has been proved unconditionally since that badge was last set. - Falsifiable: no — a positive answer needs a genuine proof for the whole class of sets $A$; there is no single finite witness that resolves it either way (this is an "always true" / "always false" statement over all countably infinite $A\subset(1,\infty)$ satisfying the dilation condition). - Origin: Erdős [Er61], [Er73], [Er77c], [Er80,p.101], [Er92c]; the \$500 offer is from [Er97c] (erdosproblems.com/143, read directly). - Known results / best bounds (erdosproblems.com/143 remarks, read directly, cross-checked against the KLL25 abstract): - If $A$ is restricted to integers, the condition forces $A$ to be a primitive set (no element divides another). For primitive sets, Erdős [Er35] proved $\sum_{n\in A}\frac{1}{n\log n}<\infty$ (uniformly bounded, in fact — this is the setup later completed by Erdős #164 — primes maximize the primitive-set sum Σ1/(n log n)); Behrend [Be35] proved the upper bound $\sum_{x<n,\,n\in A}\frac{1}{n}\ll \frac{\log x}{\sqrt{\log\log x}}$; Erdős, Sárközy & Szemerédi [ESS67] improved this $O(\cdot)$ to $o(\cdot)$. - In [Er73]/[Er77c] Erdős reports an unpublished proof of Haight that $\lim \frac{|A\cap[1,x]|}{x}=0$ holds when the elements of $A$ are independent over $\mathbb{Q}$ — a partial case of the "sparse" question, still unpublished/unverified independently by this search. - [KLL25] — D. Koukoulopoulos, Y. Lamzouri, J. D. Lichtman, "Erdős's integer dilation approximation problem and GCD graphs," arXiv:2502.09539 (Feb 2025) — proved that for every such $A$, $\sum_{x<n,\,x\in A}\frac{1}{x}=o(\log n)$ unconditionally, over the full real-valued (not just integer) class $A\subset\mathbb{R}_{\geq1}$. This is exactly the *second* explicit sub-question in the \$500 statement above, proved in full generality. Equivalently stated in the paper's own abstract: if $\limsup_{x\to\infty}\frac{1}{\log x}\sum_{a\in A\cap[1,x]}\frac1a>0$ then for every $\varepsilon>0$ there exist infinitely many pairs $(\alpha,\beta)\in A^2$, $\alpha\neq\beta$, with $|n\alpha-\beta|<\varepsilon$ for some positive integer $n$ — the contrapositive of the dilation hypothesis. The proof's key tool is the GCD-graph machinery that Koukoulopoulos & Maynard introduced to resolve the Duffin–Schaeffer conjecture (arXiv:1907.04593), repurposed here from Diophantine approximation to this dilation/sparsity setting. - Still open after KLL25: the first sub-question ($\sum_{x\in A}1/(x\log x)<\infty$, a strictly stronger statement than the $o(\log n)$ bound) and the general "is $A$ sparse" question (e.g. $\liminf |A\cap[1,x]|/x=0$), plus the sharper Behrend-motivated rate $\ll \log x/\sqrt{\log\log x}$. - "See also Erdős #858 — max Erdős-sum over sets avoiding \"a·t=b, spf(t)>a\" chains" (erdosproblems.com cross-link, verified): a related but structurally different (finite, extremal-constant) primitive-set-type sum problem, fully solved — max is $(c+o(1))\log N$, $c\approx0.618$ — by Chojecki and GPT-5.4 Pro (per erdosproblems.com/858 remark and the teorth/erdosproblems AI-contributions wiki, both read directly), but via direct finite extremal/optimization analysis, not GCD graphs — a structurally different technique from KLL25's. - Related problems: Erdős #164 — primes maximize the primitive-set sum Σ1/(n log n) (Erdős primitive-set conjecture — primes maximize $\sum 1/(n\log n)$ over primitive sets — proved by Lichtman, arXiv:2202.02384), Erdős #858 — max Erdős-sum over sets avoiding \"a·t=b, spf(t)>a\" chains (solved, see above), 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)$ and 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 (both proved, via the von-Mangoldt-chain Markov method of arXiv:2605.00301, a paper explicitly suggested/co-driven by GPT-5.4 Pro and co-authored by Terence Tao).

Literature state

Partially resolved. The erdosproblems.com page's own OPEN badge has not been updated to reflect this (as of the 2026-07-02 fetch it still reads OPEN, but the remark text itself already documents KLL25's result), so the honest classification is: one of the two explicit numbered sub-questions in the \$500 statement ($\sum_{x<n,x\in A}1/x = o(\log n)$) is now a theorem, proved unconditionally for the full continuous real-valued setting (not merely for integers) by Koukoulopoulos, Lamzouri & Lichtman, arXiv:2502.09539 (Feb 2025), via GCD-graph machinery imported from the Koukoulopoulos–Maynard proof of the Duffin–Schaeffer conjecture (arXiv:1907.04593). The other sub-question ($\sum_{x\in A}1/(x\log x)<\infty$) and the umbrella "is $A$ sparse" question remain fully open — no paper found resolving them. This is squarely inside a hot, currently-productive research vein on primitive sets and Erdős-sum bounds: the discrete analogue (Erdős primitive set conjecture, erdos/164) was fully proved by Lichtman in 2022 (arXiv:2202.02384), and a brand-new (May 2026) paper, arXiv:2605.00301 by Alexeev, Barreto, Li, Lichtman, Price, Shah, Tang & Tao, introduces a von Mangoldt-chain Markov method — explicitly credited as "suggested from output of GPT-5.4 Pro" — that reproves the Erdős primitive set conjecture in a short new way and resolves two more 1966 Erdős–Sárközy–Szemerédi conjectures (erdos/1196, erdos/1217). That paper's abstract does not mention #143 by number and its stated applications are all to the *integer* primitive-set setting, but its method (Markov chains weighted by the von Mangoldt function, bounding Erdős sums) is close enough in spirit to the KLL25 GCD-graph approach that it is worth checking directly for applicability to the still-open first sub-question of #143 — this was not verified beyond the abstract in this pass. No AI system is credited on erdosproblems.com/143 itself (checked directly, and cross-checked against the teorth/erdosproblems "AI contributions" wiki, which has no #143 entry as of Jun 30 2026); the two nearest AI-assisted results in this same problem family are erdos/858 (Chojecki + GPT-5.4 Pro, full solution) and the GPT-5.4-Pro-seeded arXiv:2605.00301 line.

Attack surface

- Mode: literature-resolution (first: read arXiv:2502.09539 and arXiv:2605.00301 in full, not just abstract, to check whether either paper's machinery extends to $\sum_{x\in A}1/(x\log x)<\infty$ or the "sparse" question) + derivation (transplant the von-Mangoldt-chain Markov method of arXiv:2605.00301 into the real-valued GCD-graph setting of KLL25, analogous to how KLL25 itself transplanted Koukoulopoulos–Maynard's Duffin–Schaeffer machinery). - Concrete first experiment: not a finite computation (falsifiability: not-finite). The concrete, checkable first move is a close read of arXiv:2502.09539 section-by-section to isolate exactly which step gives $o(\log n)$ rather than the stronger $\sum 1/(x\log x)<\infty$ — GCD-graph proofs of this type typically lose a log-factor at a union-bound/independence step, and that is the most likely place a strengthening (or a demonstration that it's genuinely a barrier) would live. - Oracle: none mechanical (real-analytic/number-theoretic proof required); correctness of any candidate proof extension would need to be checked against the KLL25 proof structure by a domain expert or, longer-term, formalized against the existing (currently unproved, 2-of-4-parts-only) Lean scaffold at FormalConjectures/ErdosProblems/143.lean. - Feasibility: honest read: research-frontier, not a quick derivation-fuel target for us, but a live one. The problem sits in an unusually active 2025–2026 research vein (KLL25 Feb 2025, Lichtman's primitive-set conjecture proof 2022, the GPT-5.4-Pro-seeded von-Mangoldt-chain paper May 2026, and a full AI-driven solution of the sibling problem erdos/858 in Apr 2026) — meaning genuinely new machinery (GCD graphs; von Mangoldt Markov chains) has been landing on this exact problem family roughly every few months. The realistic path is not a from-scratch attack but tracking/attempting the transplant described above once the two full papers are read.

Related

- Erdős #164 — primes maximize the primitive-set sum Σ1/(n log n) — the discrete/integer Erdős primitive-set conjecture (primes maximize $\sum1/(n\log n)$); proved by Lichtman, arXiv:2202.02384 — the historical anchor result (Erdős 1935 [Er35]) that #143 generalizes to the real-valued dilation setting - Erdős #858 — max Erdős-sum over sets avoiding \"a·t=b, spf(t)>a\" chains — closely related finite/extremal primitive-set-type sum, explicitly cross-linked ("See also") on erdosproblems.com/143; fully solved (Chojecki + GPT-5.4 Pro) with an explicit constant $c\approx0.618$, via direct extremal analysis rather than GCD graphs - 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 1966 conjecture on primitive sets of large numbers; proved by arXiv:2605.00301's von-Mangoldt-chain method - 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 1966 conjecture on divisibility chains; proved by the same arXiv:2605.00301 method - GCD graphs (Koukoulopoulos–Maynard graph-theoretic sieve) — the graph-theoretic machinery (vertices = elements of $A$, edges weighted by GCD-type quantities) introduced by Koukoulopoulos & Maynard for Duffin–Schaeffer and reused verbatim by KLL25 to prove #143's $o(\log n)$ bound - Duffin–Schaeffer conjecture / metric Diophantine approximation (Koukoulopoulos–Maynard theorem) — the metric Diophantine approximation conjecture whose 2019/2020 resolution (Koukoulopoulos–Maynard, arXiv:1907.04593) is the direct technical ancestor of the KLL25 proof - Von Mangoldt-weighted Markov chains for primitive-set (Erdős) sums — the Markov-chain-with-von-Mangoldt-weights method of arXiv:2605.00301 (May 2026), GPT-5.4-Pro-seeded, that resolved erdos/1196, erdos/1217 and reproved erdos/164; the most promising untested transplant target for #143's still-open first sub-question - Primitive sets (antichains in the divisibility poset: no element divides another) — the core object (no element divides another) whose real-valued generalization (integer-dilation separation) is exactly #143's hypothesis - Logarithmic density: the $1/n$-weighted density that survives when natural density doesn't — the $\limsup \frac1{\log x}\sum_{a\in A\cap[1,x]}1/a$ quantity that is the actual hinge of the KLL25 contrapositive statement - Machine formalization of infinitary combinatorics proofs (Isabelle/HOL, Lean) — FormalConjectures/ErdosProblems/143.lean (google-deepmind/formal-conjectures) currently states 2 of the 4 sub-parts as answer(sorry), with a TODO to add the other two; no proof, including KLL25's, has been formalized yet