The second question was conjectured by Burr, Erdős, Graham, and Li [BEGL96], who proved it for $\{3,4,7\}$.

The first question was asked separately by Erdős in [Er97] and [Er97e] (although there is some ambiguity over whether he intended $P(d,0)$ or $P(d,1)$ - certainly he mentions no gcd condition). A simple positive proof of the first question was provided (and formalised in Lean) by Aristotle thanks to Alexeev; see the comments for details.

In [BEGL96] they record that Pomerance observed that the condition $\sum 1/(d_i-1)\geq 1$ is necessary (for both questions), but give no details. Tao has sketched an explanation in the comments. It is trivial that $\mathrm{gcd}(d_1,\ldots,d_r)=1$ is a necessary condition in the second question.

Melfi [Me04] gives a construction, for any $\epsilon>0$, of an infinite set of $d_i$ for which every sufficiently large integer can be written as a finite sum of the shape $\sum_i c_ia_i$ where $c_i\in \{0,1\}$ and $a_i\in P(d_i,0)$ and yet $\sum_{i}\frac{1}{d_i-1}<\epsilon$.


See also [125].

View the LaTeX source

This page was last edited 01 December 2025.

• In [BEGL96], the problem is formulated in a way that only allows powers of $d_i$ greater than $d_i^0 = 1$ to be added. However, in [Er97] and [Er97e], it's formulated so that $1$s are allowed. Incidentally, this means that all the proofs in [BEGL96] actually prove slightly stronger statements.

  DesmondWeisenberg — 05:50 on 29 Aug 2025

  👍 1 📝 0 🤖 0

• [Note: this comment was written before 2025/12/01, when the problem text was updated.]
  
  Aristotle from Harmonic has solved this problem all by itself, working only from the formal statement! Type-check it online!
  
  A formal statement of the conjecture was available in the Formal Conjectures project. Unfortunately, there is a typo in that statement, wherein the comment says $\geq 1$ in the display-style equation while the corresponding Lean says "= 1". (That makes the statement weaker.) Accordingly, I have also corrected that issue and included a proof of the corrected statement. Finally, I removed a lot of what I believed were unnecessary aspects of the statement, and Aristotle proved that too. In the end, there are three different versions proven, of which this is my favorite:
  theorem erdos_124 : ∀ k, ∀ d : Fin k → ℕ,
  (∀ i, 2 ≤ d i) → 1 ≤ ∑ i : Fin k, (1 : ℚ) / (d i - 1) →
  ∀ n, ∃ a : Fin k → ℕ,
  ∀ i, ((d i).digits (a i)).toFinset ⊆ {0, 1} ∧
  n = ∑ i, a i
  I believe this is a faithful formalization of (a strengthening of) the conjecture stated on this page.
  
  As mentioned by DesmondWeisenberg above, there's an issue involving the power 1 (which corresponds to the units digit here) that means the conjecture in [BEGL96] differs from this. I believe the version in [Er97] matches the statement here, in part because it lacks a gcd condition that is obviously necessary in [BEGL96]. I do not yet have access to [Er97e] to check the statement there. The subtlety of this issue is unfortunate, given Aristotle's achievement!
  
  Timing-wise, Aristotle took 6 hours and Lean took 1 minute.

  BorisAlexeev — 22:44 on 29 Nov 2025

  👍 3 📝 0 🤖 0

  • This is quite something, congratulations to Boris and Aristotle!
    
    On one hand, as the nice sketch provided below by tsaf confirms, the final proof is quite simple and elementary - indeed, if one was given this problem in a maths competition (so therefore expected a short simple solution existed) I'd guess that something like the below would be produced. On the other hand, if something like this worked, then surely the combined talents of Burr, Erdős, Graham, and Li would have spotted it.
    
    Normally, this would make me suspicious of this short proof, in that there is overlooked subtlety. But (a) I can't see any and (b) the proof has been formalised in Lean, so clearly it just works!
    
    Perhaps this shows what the real issue in the [BEGL96] conjecture is - namely the removal of $1$ and the addition of the necessary gcd condition. (And perhaps at least some subset of the authors were aware of this argument for the easier version allowing $1$, but this was overlooked later by Erdős in [Er97] and [Er97e], although if they were aware then one would hope they'd have included this in the paper as a remark.)
    
    At the moment I'm minded to keep this as open, and add the gcd condition in the main statement, and note in the remarks that the easier (?) version allowing $1$ and omitting the gcd condition, which was also asked independently by Erdős, has been solved.

    (The site has been updated to address this comment.)
    TFBloom — 08:37 on 30 Nov 2025

    👍 3 📝 1 🤖 0

    • My summary is that Aristotle solved "a" version of this problem (indeed, with an olympiad-style proof), but not "the" version.
      
      I agree that the [BEGL96] problem is still open (for now!), and your plan to keep this problem open by changing the statement is reasonable. Alternatively, one could add another problem and link them. I have no preference.

      BorisAlexeev — 11:17 on 30 Nov 2025

      👍 0 📝 0 🤖 0

      • I agree with your description. I also wonder whether this 'easy' version of the problem has actually appeared in some mathematical competition before now, which would of course pollute the training data if Aristotle had seen this solution already written up somewhere. (I only say this in the sense that knowing such a short olympiad-style proof exists makes it a nice competition problem.)
        
        I assume you have also tried giving the harder version to Aristotle?

        TFBloom — 11:40 on 30 Nov 2025

        👍 0 📝 0 🤖 0

  • 6 hours on what hardware? If it's a like a consumer laptop-type, probably it's easy to run at 100x compute at all Erdos problems with some datacenter? Do we have a good understanding of how Aristotle's abilities scales with compute?

    davik — 04:08 on 01 Dec 2025

    👍 0 📝 0 🤖 0

• Aristotle's solution is as follows. It is surprisingly easy.
  
  Let $(a_n)$ be the sequence of powers of $d_i$ (sorted, with multiplicity). For example, if $d_1=2$ and $d_2=3$, then the sequences is: $1,1,2,3,4,8,9,16,27,\ldots$.
  
  We want to show that every positive integer is a subsequence sum. This is equivalent to $a_{n+1} -1 \leq (a_1+\dots +a_n)$. The RHS is $\sum_{i=1}^k (d_i^{e_{i,n}}-1)/(d_i-1)$, where $e_{i,n}$ is the first power of $d_i$ that has not ocurred in the first $n$ terms. This is bounded below by $\min_i (d_i^{e_{i,n}}-1)$. However, $a_{n+1}=\min_i d_i^{e_{i,n}}$. Done.
  
  Note, there is some ambiguity in the definition of $e_{i,n}$. In the example $d_1=2, d_2=3$, we can decide arbitrarily that $a_1$ is a power of $2$ and $a_2$ is a power of $3$, so $e_{2,1}=0$ but $e_{2,2}=1$.

  tsaf — 08:10 on 30 Nov 2025

  👍 5 📝 0 🤖 0

  • Thank you tsaf for deciphering the proof! Interestingly, Theorem 2.3 from this paper could be thought of as a continuous-parameter loose variant of this problem and the basic proof outline (appearing on pages 13-14 in that paper) is the same: aiming to prove that the representations fill in an interval, sorting the sequence, verifying the continuous-parameter variant of condition $a_{n+1}\leq a_1+\cdots+a_n+1$, doing so by considering the first appearing term associated with each $d_i$, etc.
    
    I am not mentioning this to diminish Aristotle's / BorisAlexeev's proof, on the contrary, it is quite beautiful! My point is that basic ideas reappear at many places; humans often fail to realize that they apply in a different setting, while a machine doesn't have this problem! I remember seeing this problem before and thinking about it briefly. I admit that I haven't noticed this connection, which is only now quite obvious to me!

    Vjeko_Kovac — 15:24 on 30 Nov 2025

    👍 0 📝 0 🤖 0

• For what it is worth, the Gemini and ChatGPT deep research tools did not turn up any significant new literature on this problem.
  
  Gemini offered the simple observation that if 1 is omitted then the gcd condition becomes necessary, explained the significance of the $\sum_i \frac{1}{d_i-1} \geq 1$ condition (linking it to some parallel work on Cantor sets, particularly the "Newhouse gap lemma"), but turned up no new direct references for this problem.
  
  ChatGPT used this very web page extensively as the main authoritative source, for instance citing the Aristotle proof, as well as the other papers cited on this page, as well as the page for the related problem [125]. As such, no new information was gleaned, but readers may find the AI-generated summary of the situation to be amusing.

  TerenceTao — 16:22 on 30 Nov 2025

  👍 2 📝 0 🤖 0

  • As a further experiment, I gave this problem (in the weaker, solved formulation) to Gemini Deepthink with a hint to use Brown's criterion. Interestingly, it declared that it was unlikely that Brown's criterion was strong enough to solve this problem. Superficially this is of course a failure on the part of the AI, but an inspection of the reasoning showed that it was a fairly "honorable" mistake. It noted that if one took $d_1=3$ then infinitely often there should be no powers of any of the $d_i$ between $d_1^k$ and $d_1^{k+1}$, so that the ratio between consecutive elements could be as large as $3$. Typically, one needs the ratio of consecutive elements to be $2$ or less on the average for Brown's criterion to apply, so Gemini concluded that heuristically this approach was unlikely to work. This is not a bad analysis actually - it just so happens that the cumulative sum of all the other powers less than $d_1^k$ is (barely) enough to overcome this gap of $3$ and reach $d_1^{k+1}$ after all. I would classify this type of error as one which a human expert could plausibly also make on this problem. Also, I think this analysis also hints at why the stronger version of this problem is more difficult, and unlikely to be resolved by off-the-shelf tests such as Brown's criterion.

    TerenceTao — 19:21 on 30 Nov 2025

    👍 2 📝 0 🤖 0

    • Further update: given the same prompt, ChatGPT Pro located Aristotle's proof (and tsaf's summary) from this very web page and wrote it up nicely in a human-readable form. Possibly there was an option to shut off web search and test the tool's ability to solve the problem independently without contamination, but I did not explore this.

      TerenceTao — 19:47 on 30 Nov 2025

      👍 3 📝 0 🤖 0

• G. Melfi in this paper has given the following related result:
  
  A sequence $S = \{s_1, s_2,...\}$ of positive integers is a complete sequence, if $\Sigma (S) := \Sigma^\infty_{i=1} \epsilon_i s_i$, for $\epsilon_i \in \{0,1\}, \Sigma_{i=1}^\infty \epsilon_i < \infty$ contains all sufficiently large integers. Let $s \geq 1$ and $A$ be a (finite or infinite) set of integers greater than $1$. Let $Pow (A; s)$ be the nondecreasing sequence of positive integers of the form $a^k$ with $a \in A$ and $k \geq s$. for any $s \geq 1$, $Pow (A; s)$ is complete if and $\textbf{only if}$ $\Sigma_{a \in A} 1/(a-1) \geq 1$.
  
  This $\textbf{only if}$ part of their conjecture has been disproved by Melfi in the above discussed paper.
  
  P.S. [BEGL96] also asks the following:
  
  What can we say about lower and upper asymptotic density of $Σ(Pow(A; s))$ when $A$ is finite and $\Sigma_{a \in A} \frac{1}{log a} > \frac{1}{log 2}$?
  (According to page 13 of this paper).

  Alfaiz — 17:02 on 30 Nov 2025

  👍 0 📝 0 🤖 0

  • Just to clarify, Pomerance's observation that Diophantine approximation shows the necessity of $\sum_{a \in A} 1/(a-1) \geq 1$ only applies in the case of finite $A$, whereas Melfi's example is for infinite $A$. (In particular, the description of Pomerance's result in [p. 133, BEGL96] is not quite correct.)
    
    Interestingly, (my reconstruction of) Pomerance's argument is almost identical to Gemini's failed heuristic argument: if $A$ is finite with $\sum_{a \in A} 1/(a-1) < 1$, then there will be infinitely many numbers $n$ that are larger than the sum of all the powers of $a$ preceding it (for this to hold, $n$ has to be slightly less than a power of $a$ for each $a$, which can be accomplished by the Kronecker approximation theorem). Hence $A$ cannot be complete.
    
    This argument shows that the $\sum_{a \in A} 1/(a-1)=1$ case is quite delicate; at a bare minimum, it needs something like Baker's theorem to prevent powers of different $a$ from clustering too close together, which can create potential counterexamples. (And indeed, [p. 137, BEGL96] discusses this issue for specific sets such as {3,4,7}.)

    TerenceTao — 01:28 on 01 Dec 2025

    👍 1 📝 0 🤖 0