Sums of distinct powers from several bases: the Burr–Erdős–Graham–Li completeness conjecture (Erdős #124)
Statement
For any $d\geq 1$ and $k\geq 0$ let $P(d,k)$ be the set of integers which are the sum of distinct powers $d^i$ with $i\geq k$. Let $3\leq d_1<d_2<\cdots<d_r$ be integers such that $$\sum_{1\leq i\leq r}\frac{1}{d_i-1}\geq 1\qquad\text{and}\qquad \gcd(d_1,\ldots,d_r)=1.$$ For any $k\geq 1$, can all sufficiently large integers be written as a sum of the shape $\sum_i c_ia_i$ where $c_i\in\{0,1\}$ and $a_i\in P(d_i,k)$? (The companion question — the same representation with $k=0$ and without the gcd condition — has been answered positively; see background. The general $k\geq 1$ conjecture is what remains open.)
Acceptance. FULLY RESOLVES: a proof that for EVERY system $3\leq d_1<\cdots<d_r$ satisfying $\sum_i 1/(d_i-1)\geq 1$ and $\gcd(d_1,\ldots,d_r)=1$, and every $k\geq 1$, all sufficiently large integers are representable as $\sum_i c_ia_i$ with $c_i\in\{0,1\}$, $a_i\in P(d_i,k)$; or a disproof exhibiting a specific qualifying system and $k\geq 1$ together with a proof that infinitely many integers are not representable (finitely many exceptions never suffice). Machine-checkable (Lean/Coq) proof preferred — the formal-conjectures statement can host it — else a complete written proof. ADVANCES: a proof of the conjecture for new explicit systems beyond the $\{3,4,7\}$ case stated in the background (computer-assisted is welcome: finite representability certificate + induction argument, with code and machine-checkable verification), or for a natural infinite family of systems, or for all $k$ up to some bound for a class of systems; a rigorous published write-up (or Lean formalization) of Pomerance's necessity observation; or a Lean formalization of the [BEGL96] $\{3,4,7\}$ theorem. Deliver the proof file, or per-system certificates + verification code + the induction write-up.
Background
The $k\geq 1$ question was conjectured by Burr, Erdős, Graham, and Li [BEGL96], who proved it for the single system $\{3,4,7\}$; listed as open on erdosproblems.com/124 (fetched 2026-07-13, status 'open', tagged 'number theory | base representations | complete sequences'). The companion $k=0$ question was asked separately by Erdős [Er97, p.156] [Er97e, p.533] (with some ambiguity over $P(d,0)$ vs $P(d,1)$, and no gcd condition); per the site, a simple positive proof of that first question was provided — and formalized in Lean — by Aristotle (Harmonic's automated prover), credited via Alexeev, with details in the problem's comment thread. Structural facts: Pomerance observed that $\sum_i 1/(d_i-1)\geq 1$ is necessary for both questions ([BEGL96] record this without details; Tao has sketched the argument in the site comments), and $\gcd(d_1,\ldots,d_r)=1$ is trivially necessary in the $k\geq 1$ question (all elements of $P(d_i,k)$ share divisibility obstructions otherwise). For infinite base sets the density condition is not needed: Melfi [Me04] constructs, for any $\epsilon>0$, an infinite set of $d_i$ with $\sum_i 1/(d_i-1)<\epsilon$ for which every sufficiently large integer is a finite sum $\sum_i c_ia_i$, $a_i\in P(d_i,0)$. See also Erdős #125 (erdosproblems.com/125). The statement is formalized in the google-deepmind/formal-conjectures repository. The attacker's tools: completeness-of-sequences arguments in the [BEGL96] style, where specific systems reduce to a finite representability check plus an induction — making computer-assisted proofs for new explicit systems $\{d_1,\ldots,d_r\}$ and small $k$ a realistic target, with dynamic-programming representability verification supplying the finite certificates.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #124 (T. F. Bloom) | website |
| REF-02 | Lean formalization of Erdős #124 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.