Erdős #123 — three coprime bases give a d-complete set?

Statement

Let $a,b,c\geq 1$ (per the site's forum comments and the Lean formalization, this should read $a,b,c>1$ — with $a=1$ allowed the answer is trivially no, e.g. $a=b=1$) be three pairwise coprime integers. Is every large integer the sum of distinct integers of the form $a^kb^lc^m$ ($k,l,m\geq 0$), none of which divide any other?

Equivalently: is the set $\{a^kb^lc^m : k,l,m\geq 0\}$ $d$-complete, where a set $A\subseteq\mathbb N$ is $d$-complete if every sufficiently large integer is a sum of distinct elements of $A$ forming an antichain under divisibility?

Facts

- Prize \$250; status open, marked by the site owner as "cannot be resolved with a finite computation" (it quantifies over all large $n$ *and* all pairwise-coprime triples $(a,b,c)$). - Falsifiable: no — needs a genuine proof (or a proof that some specific triple fails, which itself would need an infinitary non-representability argument, not a finite counterexample). - Origin: conjectured by Erdős and Lewin [ErLe96] (Math. Comp. 64 (1996), 837–840); restated in [Er92b] (Matematiche (Catania), 1992), [Er97] (New Zealand J. Math., 1997), [Er97e] (Math. Japon., 1997). - Known results (verified triples/families), taken directly from erdosproblems.com/123's own literature summary (cross-checked against the underlying papers' bibliographic metadata via Semantic Scholar): - $a=3,b=5,c=7$: fully $d$-complete — Erdős & Lewin [ErLe96], the founding paper. - $a=2,b=5,c\in\{7,11,13,17,19\}$: Erdős & Lewin [ErLe96]. - $a=2,b=5,c\in\{9,21,23,27,29,31\}$, and more generally any $a=2,b=5,c>6$ with $\gcd(c,10)=1$ satisfying a checkable representability criterion on the interval $(N,25cN)$: Ma & Chen [MaCh16], J. Number Theory 164 (2016), 1–12. - $a=2,b=5,3\leq c\leq 87$ with $\gcd(c,10)=1$; $a=2,b=7,3\leq c\leq 33$ with $\gcd(c,14)=1$; $a=3,b=5,2\leq c\leq 14$ with $\gcd(c,15)=1$: Chen & Yu [ChYu23b], "On $d$-complete sequences of integers, II," Acta Arith. 207 (2023), 161–181 — the current record, confirmed as "most recent results" by a 2025-10-24 forum comment (user Woett) that the site owner marked as incorporated. - An earlier paper by the same second author, Yu & Chen, "On a conjecture of Erdős and Lewin," J. Number Theory 238 (2022) (DOI 10.1016/J.JNT.2021.09.018) — title/venue confirmed via Semantic Scholar citation graph of [ErLe96]; abstract not accessible (paywalled), presumably a precursor to [ChYu23b] but content unverified. - No triple outside these explicit families (in particular no triple with three *distinct* prime-power bases larger than these bounds, and no general-$(a,b,c)$ argument) is known to be resolved. - Stronger form (Erdős, [Er92b]): for $a=2,b=3,c=5$, conjectures that for any $\epsilon>0$ all large $n$ can be written as a sum of distinct $b_1<\cdots<b_t$ of the form $2^k3^l5^m$ with $b_t<(1+\epsilon)b_1$ (a "snug" / tightly-clustered representation) — strictly stronger than plain $d$-completeness. This exact statement is formalized (unproved, sorry) as erdos_123.variants.powers_2_3_5_snug in the Lean file below. - Formalized in Lean: yes — google-deepmind/formal-conjectures/FormalConjectures/ErdosProblems/123.lean states the general conjecture erdos_123 (sorry), the Erdős–Lewin $(3,5,7)$ special case erdos_123.variants.erdos_lewin_3_5_7 (tagged research solved but the Lean *proof* is still sorry — i.e. only the informal math is done, not machine-checked), the folklore two-power base case erdos_123.variants.powers_2_3 ($\{2^k3^l\}$ is $d$-complete, sorry), and the snug $2,3,5$ variant above (sorry). - Related problems: erdos/845, erdos/1110.

Literature state

Not resolved in general. The problem is a genuinely open ~30-year-old conjecture of Erdős and Lewin. What the literature search establishes: - The *only* fully-general-triple case proved is $(3,5,7)$ [ErLe96]. All other progress is restricted to two fixed bases ($a=2$ or $a=3$ paired with $b=5$ or $b=7$) with the third base $c$ ranging over a bounded, explicit, checkable interval, extended stepwise by three papers over 27 years (1996 → 2016 → 2023). This is a classic "chip away at small cases with an explicit representability criterion, then computer-verify the finitely many remaining $c$" pattern, not a structural proof of the general conjecture — each paper's technique is: reduce $d$-completeness of $\{2^k5^lc^m\}$ (say) to representability of all integers in a *bounded* interval $(N,\text{const}\cdot N)$ by $\{2^k3^lc^m\}$-type sums, then check that interval directly. No asymptotic/density argument covering all triples $(a,b,c)$ exists yet. - The two-base sub-problem is fully resolved: $\{2^k3^l\}$ is $d$-complete via a two-line induction (folklore, attributed to "Jansen and several others" by Erdős in [Er92b]: if $n$ even recurse on $n/2$ doubled, if odd subtract the largest power of $3$ below $n$ and recurse). Erdős & Lewin [ErLe96] generalize this completely: for coprime $p<q$, $\{p^\alpha q^\beta\}$ is $d$-complete iff $(p,q)=(2,3)$ — this full two-base classification is the base case the three-base conjecture #123 sits on top of, and is *not* itself open. - Directly adjacent problems, both with recent movement: - erdos/845 (two-power "snug"/bounded-ratio version: can $C\leq$ const work for $\{2^k3^l\}$ sums with ratio $b_t/b_1<C$?) — DISPROVED and Lean-verified by Wouter van Doorn & Anneroos Everts, "Smooth sums with small spacings," arXiv:2511.04585 (Nov 2025, read in full): they show $C=6$ suffices (contradicting the folklore belief that no small constant works), generalize to arbitrary odd $p$ via an explicit "positional digit" greedy algorithm building on Blecksmith–McCallum–Selfridge (Amer. Math. Monthly 105 (1998), 529–543 — cited as [5] in vDEv25, proved $\{2^k3^l\}$ stays $d$-complete after deleting any finite subset, with a fully explicit construction). This is the closest genuinely *solved* sibling problem and its technique (explicit greedy digit-representation across geometrically shrinking "intervals" $I_k$, each covered by a small ratio-bounded multiset $S_k$) is a plausible template to try to extend to three bases. - erdos/1110 (two-power density/finiteness question for general coprime $p>q\geq2$: is the set of non-representable — as antichain sums — integers finite, or what is its density?) — partially resolved: [ErLe96] prove the non-representable set is finite iff $\{p,q\}=\{2,3\}$; the density question for other pairs remains open. - A separate, currently very active cluster of papers concerns the Birch–Erdős theorem, a *weaker* cousin: Birch (Math. Proc. Camb. Phil. Soc. 55 (1959), 370–373) proved Erdős's conjecture that every large $n$ is a sum of distinct terms from $\{p^\alpha q^\beta\}$ without the antichain (no-summand-divides-another) condition. This weaker representability question has seen a 2025–2026 burst: Ding–Liu–Wang, "Note on a theorem of Birch and Erdős," arXiv:2503.11676 (read in full — gives the precise asymptotic count $f_{p,q}(n)=2^{\frac{(\log n)^2}{2\log p\log q}(1+O(\log\log n/\log n))}$ of such representations, plus a connection to $m$-ary partitions); Yu–Chen–Chen, "A generalization of the Erdős–Birch theorem," European J. Combin. (2025), DOI 10.1016/j.ejc.2025.104187, generalizes Birch's theorem from 2 to $k\geq2$ arbitrary pairwise-coprime bases (title/venue confirmed, abstract not retrieved — unverified content, but per web-search summaries it proves all sufficiently large $n$ representable, without the antichain condition, for $k$ general bases); Honghu Liu, "The Birch–Erdős theorem on exponential type sequences," Period. Math. Hungar. (2026), DOI 10.1007/s10998-026-00707-y, refines this with an explicit spacing bound $cn(\log n)^{\log k/\log 2+\epsilon}$ (title/result summary via web search, abstract not directly retrieved — unverified content, flagged accordingly). None of these papers impose the antichain condition that defines $d$-completeness, so none of them resolve #123 — they solve the "Birch" (representability-only) analogue for arbitrarily many bases $k$, which #123's three-base *antichain* version does not reduce to. This is an important distinction: the machinery that scales cleanly to many bases (density/counting arguments à la Birch) is precisely the machinery that does not carry the antichain constraint; the antichain constraint is what keeps #123 stuck at explicit-finite-range results. - No AI/automated-theorem-proving contribution to #123 was found: the GitHub teorth/erdosproblems wiki's "AI contributions to Erdős problems" page has no entry for #123 (checked directly), and the Lean formalization has every relevant theorem sorryd, including the already-known-true $(3,5,7)$ case. - No solution or partial-solution claim exists in the erdosproblems.com forum thread (4 comments, all read): they only clarify the $a,b,c>1$ vs. $\geq1$ typo and confirm the Ma–Chen/Chen–Yu literature is already incorporated into the site remarks.

Attack surface

- Mode: literature-resolution + derivation (not finite-search for the general conjecture — it quantifies over infinitely many triples and all large $n$; but each *specific* triple $(a,b,c)$ is individually a finite-computation-flavored sub-problem once reduced, à la Ma–Chen/Chen–Yu, to a bounded-interval representability check). - Concrete first experiment: reproduce the Chen–Yu [ChYu23b] reduction technique computationally — for a new fixed pair, e.g. $a=2,b=11$ (untouched by any paper found), derive (from the Ma–Chen [MaCh16] general criterion sketch on erdosproblems.com/123) the analogous bounded interval $(N,K\cdot N)$ whose full antichain-sum representability must be checked, and brute-force-verify it by computer for a range of $c$ coprime to $22$ — this would extend the explicit-family record and is a genuinely finite, runnable, and citable sub-task even though it does not touch the general conjecture. - A second, more structural experiment: attempt to port the explicit greedy "digit representation across shrinking geometric intervals" algorithm of van Doorn–Everts (arXiv:2511.04585, used to resolve the two-power sibling erdos/845) from two bases to three — i.e. try to build an explicit induction/greedy construction for $\{a^kb^lc^m\}$ analogous to the Blecksmith–McCallum–Selfridge / van Doorn–Everts one for $\{2^kp^l\}$. This is the most promising *derivation* angle found: the two-power case's full resolution (both plain $d$-completeness [ErLe96] and the snug/bounded-ratio strengthening [vDEv25]) came from an explicit constructive algorithm, not a probabilistic/density argument, and three-base explicit constructions have not been tried in any paper found. - Oracle: for the general conjecture, none (unfalsifiable by finite means). For sub-experiments: mechanical — a claimed antichain-sum representation for a specific $n$ is checked by direct verification (compute the multiset of $a^kb^lc^m$ values, check divisibility antichain condition, check the sum); a claimed general criterion (as in Ma–Chen/Chen–Yu) reduces to checking finitely many residues/intervals by computer. - Feasibility: honest read — hard but has a concrete "extend the known-triples table" path plus a genuinely untried structural angle. Full resolution (all pairwise-coprime triples) has resisted three papers over 27 years and looks structurally hard (each extension needed new case-specific number-theoretic input, not a uniform argument). However: (a) extending the explicit-family table (à la Chen–Yu) to new $(a,b)$ pairs is mechanical, finite, and directly citable, and (b) the 2025 breakthrough on the sibling two-power "snug" problem erdos/845 (previously believed hopeless, until van Doorn–Everts found an explicit greedy construction beating the naive belief) is fresh evidence that this problem family responds to explicit constructive/algorithmic attacks that had not been tried — a genuine derivation opportunity, not yet exploited for the three-base case.

Related

- erdos/845 — two-power "snug" spacing version for $\{2^k3^l\}$: DISPROVED, Lean-verified (van Doorn & Everts, arXiv:2511.04585, 2025), via an explicit greedy digit-representation algorithm generalizing Blecksmith–McCallum–Selfridge (1998). The clearest evidence that this problem family yields to explicit constructive techniques, and the most promising technique to try to port to three bases. - erdos/1110 — two-power density/finiteness of non-representable integers for general coprime $p>q\geq2$: partially resolved — [ErLe96] show the exceptional set is finite iff $\{p,q\}=\{2,3\}$; general density otherwise open. - concept/d-completeness — the core object: a set is $d$-complete if every large integer is an antichain-under-divisibility sum of distinct elements. Fully classified for two prime-power bases ($\{p^\alpha q^\beta\}$ $d$-complete iff $(p,q)=(2,3)$, [ErLe96]); open in general for three bases (#123 itself). - concept/greedy-digit-representation-induction — the explicit constructive technique (folklore induction for $\{2^k3^l\}$; Blecksmith–McCallum–Selfridge's finite-deletion-robust version; van Doorn–Everts' generalization to $\{2^kp^l\}$ with bounded-ratio "snug" sums) that has been the only technique to fully resolve any member of this problem family, including disproving a long-standing belief on erdos/845. - concept/birch-erdos-theorem — the weaker "representability without antichain condition" cousin (Birch 1959, generalized to $k\geq2$ bases by Yu–Chen–Chen 2025 and refined by Liu 2026): a currently very active but *structurally different* line (density/counting, not antichain-constrained) that does not directly attack #123 but delineates exactly which part of the difficulty (the antichain constraint) is Erdős–Lewin/#123-specific versus which part (mere representability) is already well understood for arbitrarily many bases. - Lean 4 formalization of constructions and conditional reductions (Erdős-problem context) — google-deepmind/formal-conjectures project; #123's statement and all known special-case theorems are stated but every proof is sorry, including the already-published $(3,5,7)$ result — a concrete, currently-unclaimed formalization target independent of resolving the open conjecture.