Openai/692c9ea1-b3cc-800e-94da-4224ac78a36a

This conversation was exported from ChatGPT

gpt-5-1-pro

User: I am wondering if the following problem can be attacked using Brown's criterion.

I am wondering if the following problem can be attacked using Brown's criterion. Could you explore this possibility?

--

Let $3\leq d_1<d_2<\cdots <d_k$ be integers such that\[\sum_{1\leq i\leq k}\frac{1}{d_i-1}\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$ has only the digits $0,1$ when written in base $d_i$?

Conjectured by Burr, Erd\H{o}s, Graham, and Li \cite{BEGL96}. Pomerance observed that the condition $\sum 1/(d_i-1)\geq 1$ is necessary. In \cite{BEGL96} they prove the property holds for $\{3,4,7\}$.

See also [125].

References

[BEGL96] Burr, S. A. and Erd\H{o}s, P. and Graham, R. L. and Li, W. Wen-Ching, Complete sequences of sets of integer powers. Acta Arith. (1996), 133-138.

Assistant: Yes – and in fact, for the version you wrote down with 1’s allowed Brown’s criterion gives a very clean solution.

Yes – and in fact, for the version you wrote down (with 1’s allowed) Brown’s criterion gives a very clean solution. The subtlety is that this is now understood to be the “easy” variant of the Burr–Erdős–Graham–Li problem; the original BEGL formulation is slightly different (it removes the 1’s and adds a gcd condition), and that version is still open and much harder. Let me walk through how Brown’s criterion fits in.

1. Brown’s criterion in a nutshell

Brown’s criterion says the following.

Let (νn)n≥1(\nu_n)_{n\ge1}(νn​)n≥1​ be a nondecreasing sequence of positive integers. Write

Sn=ν1+⋯+νn.S_n = \nu_1+\dots+\nu_n.Sn​=ν1​+⋯+νn​. Then (νn)(\nu_n)(νn​) is complete (every positive integer is a sum of a finite subsequence with coefficients in {0,1}\{0,1\}{0,1}) iffMathWorld

1. ν1=1\nu_1 = 1ν1​=1, and
2. for all k≥2k\ge2k≥2, Sk−1  ≥  νk−1.S_{k-1} \;\ge\; \nu_k - 1.Sk−1​≥νk​−1.

Equivalently: sorting the sequence and letting SnS_nSn​ be the sum of the first nnn terms, there are no “gaps” if each new term is at most Sn−1+1S_{n-1}+1Sn−1​+1.

For weak completeness (all sufficiently large integers are representable) you need the inequality to hold from some index onward; if it fails infinitely often you get infinitely many large gaps.

2. Rephrasing the problem in terms of powers

For each base did_idi​, write

S(di)={∑jεi,jdij:εi,j∈{0,1}}S(d_i) = \left\{\sum_j \varepsilon_{i,j} d_i^j : \varepsilon_{i,j}\in\{0,1\}\right\}S(di​)={j∑​εi,j​dij​:εi,j​∈{0,1}} (the integers whose base-did_idi​ expansion uses only digits 0 and 1).

Your question is:

Given

3

≤

𝑑

1

<

⋯

<

𝑑

𝑘

3≤d

1

​

<⋯<d

k

​

with

∑

𝑖

=

1

𝑘

1

𝑑

𝑖

−

1

  

≥

1

,

i=1

∑

k

​

d

i

​

−1

1

​

≥1,

can every sufficiently large integer

𝑁

N be written as

𝑁

=

∑

𝑡

𝑐

𝑡

𝑎

𝑡

,

𝑐

𝑡

∈

{

0

,

1

}

,

N=

t

∑

​

c

t

​

a

t

​

,c

t

​

∈{0,1},

where each

𝑎

𝑡

∈

𝑆

(

𝑑

𝑖

)

a

t

​

∈S(d

i

​

) for some

𝑖

i (i.e. each summand has only 0–1 digits in its base

𝑑

𝑖

d

i

​

)?

The key observation:

If we can represent every

𝑁

N as a sum of distinct powers

𝑑

𝑖

𝑗

d

i

j

​

, then we automatically get a representation of the required form by grouping powers with the same base.

Indeed, suppose we have

N=∑i=1k∑j≥0εi,jdij,εi,j∈{0,1}.N = \sum_{i=1}^k \sum_{j\ge0} \varepsilon_{i,j} d_i^j,\qquad \varepsilon_{i,j}\in\{0,1\}.N=i=1∑k​j≥0∑​εi,j​dij​,εi,j​∈{0,1}. For each base did_idi​ set

Ai:=∑j≥0εi,jdij.A_i := \sum_{j\ge0} \varepsilon_{i,j} d_i^j.Ai​:=j≥0∑​εi,j​dij​. Then each AiA_iAi​ has only 0/1 digits in base did_idi​, and

N=∑i:Ai>0Ai.N = \sum_{i: A_i>0} A_i.N=i:Ai​>0∑​Ai​. So the original problem reduces to:

Is the sequence of all pure powers of the

𝑑

𝑖

d

i

​

a complete sequence?

This is exactly the setting where Brown’s criterion shines.

3. Constructing the “power sequence” and applying Brown

Form the multiset of all powers of the did_idi​:

P={die:1≤i≤k, e≥0}.\mathcal{P} = \{d_i^e : 1\le i\le k,\ e\ge0\}.P={die​:1≤i≤k, e≥0}. Sort it in nondecreasing order (with multiplicity if the same integer occurs as a power of two different bases), and call the resulting sequence

a1≤a2≤a3≤…a_1 \le a_2 \le a_3 \le \dotsa1​≤a2​≤a3​≤… We clearly have a1=1a_1 = 1a1​=1 (some di0=1d_i^0=1di0​=1), so condition (1) of Brown’s criterion holds.

Fix nnn. For each base did_idi​, let ei,ne_{i,n}ei,n​ be the smallest exponent such that diei,nd_i^{e_{i,n}}diei,n​​ has not yet appeared among a1,…,ana_1,\dots,a_na1​,…,an​. Then:

• The powers of did_idi​ that have appeared are exactly di0,…,diei,n−1d_i^0,\dots,d_i^{e_{i,n}-1}di0​,…,diei,n​−1​,
• so the contribution of base did_idi​ to the partial sum Sn=a1+⋯+anS_n = a_1+\dots+a_nSn​=a1​+⋯+an​ is at least 1+di+⋯+diei,n−1  =  diei,n−1di−1.1 + d_i + \dots + d_i^{e_{i,n}-1} \;=\; \frac{d_i^{e_{i,n}}-1}{d_i-1}.1+di​+⋯+diei,n​−1​=di​−1diei,n​​−1​.

Summing over all bases,

Sn  ≥  ∑i=1kdiei,n−1di−1.(★)S_n \;\ge\; \sum_{i=1}^k \frac{d_i^{e_{i,n}}-1}{d_i-1}. \tag{★}Sn​≥i=1∑k​di​−1diei,n​​−1​.(★) On the other hand, the next term an+1a_{n+1}an+1​ must be the smallest unused power among all bases, so

an+1=min⁡1≤i≤kdiei,n.a_{n+1} = \min_{1\le i\le k} d_i^{e_{i,n}}.an+1​=1≤i≤kmin​diei,n​​. Call this minimum MMM. Then for every iii we have diei,n≥Md_i^{e_{i,n}}\ge Mdiei,n​​≥M, and so

diei,n−1di−1  ≥  M−1di−1.\frac{d_i^{e_{i,n}}-1}{d_i-1} \;\ge\; \frac{M-1}{d_i-1}.di​−1diei,n​​−1​≥di​−1M−1​. Plugging this into (★),

Sn  ≥  (M−1)∑i=1k1di−1  ≥  (M−1)if∑i=1k1di−1≥1.S_n \;\ge\; (M-1)\sum_{i=1}^k \frac{1}{d_i-1} \;\ge\; (M-1) \quad\text{if}\quad \sum_{i=1}^k \frac{1}{d_i-1}\ge1 .Sn​≥(M−1)i=1∑k​di​−11​≥(M−1)ifi=1∑k​di​−11​≥1. But M=an+1M=a_{n+1}M=an+1​, so we have exactly Brown’s inequality

Sn  ≥  an+1−1for all n.S_n \;\ge\; a_{n+1}-1 \quad\text{for all }n.Sn​≥an+1​−1for all n. Thus Brown’s criterion is satisfied (and we also have gcd=1=1=1 because 1 is in the sequence), so the power sequence (an)(a_n)(an​) is complete: every positive integer is a sum of distinct powers died_i^edie​.MathWorld

As explained in §2, grouping powers by base turns this into exactly the representation you want, with each summand having only 0/1 digits in its own base.

So:

For the version of the problem that allows the

𝑑

𝑖

0

=

1

d

i

0

​

=1 terms, the condition

∑

𝑖

1

𝑑

𝑖

−

1

≥

1

∑

i

​

d

i

​

−1

1

​

≥1 and Brown’s criterion give a short, completely elementary proof that every integer (not just sufficiently large ones) has a representation of the required form.

This argument is essentially the one written down in the Erdős Problem #124 discussion and formalised in Lean (“Aristotle’s” proof).Erdős Problems

4. Where the real BEGL difficulty is

The original BEGL paper works with sequences of pure powers

Pow⁡(A;s):=sorted {ak:a∈A, k≥s}\operatorname{Pow}(A;s) := \text{sorted }\{a^k : a\in A,\ k\ge s\}Pow(A;s):=sorted {ak:a∈A, k≥s} for some s≥1s\ge1s≥1 and a set AAA of integers >1>1>1. They conjectured (roughly) that for finite AAA, Pow⁡(A;s)\operatorname{Pow}(A;s)Pow(A;s) is complete iffRivMat

1. ∑a∈A1a−1≥1\displaystyle \sum_{a\in A} \frac{1}{a-1}\ge1a∈A∑​a−11​≥1, and
2. gcd⁡{a:a∈A}=1\gcd\{a:a\in A\}=1gcd{a:a∈A}=1.

Melfi later gave counterexamples for infinite AAA, showing that this “if and only if” cannot hold in full generality, though the finite-AAA case remains open.RivMat

Crucially, BEGL’s hard version of your problem:

• removes the term 1=a01=a^01=a0 from the allowed powers (i.e. uses s≥1s\ge1s≥1), and
• adds a gcd condition instead.

Once you throw away all the 1’s, the neat Brown argument above breaks: the sequence no longer starts at 1, and the initial partial sums are too small. One could try to “shift” or rescale the sequence and reapply Brown, or to extract a clever subsequence that does satisfy Brown’s inequality, but that becomes just as hard as the original conjecture.

So, to answer your original meta‑question:

• Yes, Brown’s criterion absolutely attacks (and essentially solves) the version of the problem you wrote down, where 1’s are allowed. You take the union of all powers of the did_idi​, check Brown’s inequality via the sum ∑1/(di−1)≥1\sum 1/(d_i-1)\ge1∑1/(di​−1)≥1, and then group by base to get the desired “digits 0/1” representation.
• For the sharper BEGL version (no 1’s, gcd condition, completeness of Pow⁡(A;s)\operatorname{Pow}(A;s)Pow(A;s) for s≥1s\ge1s≥1), Brown’s criterion in this simple form no longer suffices, and the problem is still open for finite sets AAA. Brown’s framework is still conceptually useful—you can phrase the conjecture as “does the Brown inequality eventually hold for this power sequence?”—but proving that inequality is exactly the deep part.

If you’d like, next step could be to write out a fully rigorous Brown‑criterion proof for the “with 1’s” version in your favourite level of detail, or to look at small concrete examples (like {3,4,7}\{3,4,7\}{3,4,7}) and see the inequality at work by hand.