Erdős Problem #346

Erdős Problem #346: robust completeness and the golden ratio

Partial necessary conditions and a deletion criterion, 24 September 2026.

1) Statement

Let $A=\{a_1<a_2<\cdots\}\subseteq\mathbb N$. Assume deleting any finite subset leaves a complete sequence, whereas deleting any infinite subset leaves a sequence which is not complete. Here complete means that every sufficiently large integer is a sum of distinct remaining terms. If $a_{n+1}/a_n\ge1+\epsilon$ uniformly for some $\epsilon>0$, must the ratios tend to $\phi=(1+\sqrt5)/2$? The source records a counterexample; the argument below isolates what each deletion hypothesis actually requires, without claiming to reconstruct that counterexample.

2) Finite-deletion completeness forces a divergent surplus

Put $S_n=\sum_{i\le n}a_i$. Fix $m$. Completeness of the tail $\{a_{m+1},a_{m+2},\ldots\}$ implies \[a_{n+1}\le S_n-S_m+1\quad\text{for every sufficiently large }n. \tag{1}\] Otherwise the integer $S_n-S_m+1$ is too large to be a sum of the tail elements at most $a_n$, but smaller than every later element. If $1$ failed for infinitely many $n$, these missing integers would tend to infinity, contradicting tail completeness.

Since $1$ holds for every fixed $m$ and $S_m\to\infty$, it follows that \[S_n-a_{n+1}\longrightarrow\infty.\tag{2}\] This is a necessary condition, not a sufficient one: it says nothing by itself about which residues or intervals are attained by the subset sums.

For example, a uniform ratio bound $a_{n+1}\ge q a_n$ with $q\ge2$ is impossible. If $q=2$, then $a_i\le a_n2^{-(n-i)}$ and $S_n<2a_n\le a_{n+1}$, contradicting $2$. For $q>2$ the same contradiction follows by replacing $q$ by 2. Thus the exponential lower bound allowed by the first hypothesis must be strictly below two.

3) Infinite-deletion failure is automatic above $\phi$

Suppose more strongly that $a_{n+1}\ge q a_n$ for every $n$, with a fixed $q>\phi$. Then \[S_{n-1}\le\frac{q}{q-1}a_{n-1},\qquad a_{n+1}\ge q^2a_{n-1}. \] The difference between the right sides is a fixed positive multiple of $a_{n-1}$, since $q^2>q/(q-1)$ is equivalent to $q^2-q-1>0$. Hence eventually \[a_{n+1}>S_{n-1}+1.\tag{3}\] If an infinite set of indices is deleted, consider any sufficiently large deleted index $n$. Every retained term below $a_{n+1}$ is among $a_1,\ldots,a_{n-1}$; all of their subset sums are at most $S_{n-1}$. By $3$, the integer $S_{n-1}+1$ cannot be a sum of retained terms. These missing integers are unbounded as the deleted indices tend to infinity. Thus every infinite deletion destroys completeness.

The same conclusion holds if the ratio bound starts only after a fixed initial segment: the initial sum contributes a fixed additive constant, while the positive margin in $3$ grows without bound. Consequently $\liminf a_{n+1}/a_n>\phi$ is already sufficient for the infinite-deletion condition. It does not establish finite-deletion completeness.

4) A precise sufficient mechanism for completing a tail

An elementary interval-extension lemma shows one route to proving the missing property. Suppose subset sums of a finite group of available terms contain every integer in $[u,u+L]$. Let the remaining terms be $b_1,b_2,\ldots$, disjoint from that group, and assume \[b_j\le L+1+\sum_{i<j}b_i\qquad\text{for every }j. \] Inductively, adding $b_j$ to the current interval gives a translated interval which overlaps or touches it, so all integers in \[\left[u,u+L+\sum_{i\le j}b_i\right] \] are attained. Since the total tends to infinity, that tail is complete. A proof of robustness must produce such a seed or another adequate covering mechanism after every finite deletion. The surplus condition $2$ alone does not provide a seed interval.

5) Outcome and source

UNRESOLVED in this attempt. The necessary divergent-surplus condition, the exclusion of a uniform ratio at least two, the sufficient infinite-deletion obstruction above $\phi$, and the interval-extension mechanism are proved. A sequence satisfying finite-deletion completeness and the specified irregular ratios, together with verification of every tail, is still missing.

Source: https://www.erdosproblems.com/346, checked 24 September 2026, which reports a counterexample by GPT Pro prompted by Price. That construction is not asserted to have been verified here. These reductions also clarify the source's observation about ratios above the golden ratio. No novelty or formal verification is claimed.

The estimate measures progress toward constructing and verifying a full counterexample.

6) COMPLETION ESTIMATE

COMPLETION: 35%

Erdős problem #346

1) FORMAL RESTATEMENT. We consider an increasing sequence $A=\{a_1<a_2<\cdots\}\subseteq\mathbb{N}$ and its subset-sum set \[ P(A)=\left\{\sum_{n\in B} n:\ B\subseteq A\ \text{finite}\right\}. \] A sequence $A$ is complete if every sufficiently large integer lies in $P(A)$. The problem asks whether there exists a sequence $A$ such that:

1. $1$ For every finite subset $B\subseteq A$, the set $A\setminus B$ is complete.
2. $2$ For every infinite subset $B\subseteq A$, the set $A\setminus B$ is not complete.

The statement reports that Graham exhibited an example with these properties. It further asks: if additionally $a_{n+1}/a_n\ge 1+\varepsilon$ for all $n$, must one have \[ \lim_{n\to\infty}\frac{a_{n+1}}{a_n}=\frac{1+\sqrt5}{2}=:\varphi\ ? \] It also notes that if $a_{n+1}/a_n>\varphi$ for all $n$, then property $2$ is "easy".

2) QUICK LITERATURE/CONTEXT CHECK. We do not use Graham's result beyond acknowledging it is asserted in the statement. We focus on proving the "easy" implication about ratios.

3) ATTACK PLAN.

• Prove a standard gap lemma: if a term exceeds $1+$ the sum of all previous terms, completeness fails.
• Use the ratio hypothesis $a_{n+1}\ge c a_n$ with $c>\varphi$ to force such a gap in any subsequence obtained by deleting infinitely many terms.
• Do a small numerical sanity check illustrating the gap phenomenon.

4) WORK.

Lemma 346.1 (gap obstruction to completeness). Let $B=\{b_1<b_2<\cdots\}\subseteq\mathbb{N}$ and let $S_m:=\sum_{i=1}^m b_i$. If for some $m$ one has \[ b_{m+1} > S_m+1, \] then $B$ is not complete. Indeed, every integer in the interval $(S_m,\,b_{m+1})$ fails to lie in $P(B)$.

Proof. Any subset sum of elements among $\{b_1,\dots,b_m\}$ is at most $S_m$. Any subset sum that uses $b_{m+1}$ is at least $b_{m+1}$. Therefore no subset sum can lie strictly between $S_m$ and $b_{m+1}$. In particular, the integers $S_m+1,\dots,b_{m+1}-1$ are missing from $P(B)$, so $B$ cannot be complete. $\square$

Proposition 346.2 (uniform ratio $>\varphi$ forces property $2$). Assume $A=\{a_1<a_2<\cdots\}$ satisfies a uniform ratio bound \[ \frac{a_{n+1}}{a_n} \ge c\quad\text{for all }n, \] for some constant $c>\varphi$. Then for every infinite subset $B\subseteq A$, the set $A\setminus B$ is not complete. Equivalently: deleting infinitely many terms from $A$ always destroys completeness.

Proof. Let $C:=A\setminus B=\{b_1<b_2<\cdots\}$ be the remaining infinite subsequence. Since $C$ is a subsequence of $A$, it also satisfies $b_{i+1}/b_i\ge c$ for all $i$. Hence for each $m$, \[ \sum_{i=1}^m b_i \le b_m\sum_{j=0}^{m-1} c^{-j} \le b_m\cdot \frac{c}{c-1}. \] Now, because $B$ is infinite, there are infinitely many indices $m$ such that at least one term of $A$ lies strictly between $b_m$ and $b_{m+1}$; in particular, for infinitely many $m$ we have $b_{m+1}\ge c^2 b_m$ (skipping at least one ratio-$\ge c$ step multiplies by at least $c^2$). Fix such an $m$. Then \[ b_{m+1} \ge c^2 b_m. \] Since $c>\varphi$ is equivalent to $c^2>\frac{c}{c-1}$ (because $c^2>\frac{c}{c-1}\iff c^2-c-1>0$), we have \[ b_{m+1} - \sum_{i=1}^m b_i \ge c^2 b_m - \frac{c}{c-1}b_m = b_m\left(c^2-\frac{c}{c-1}\right) >0. \] For all sufficiently large such $m$, the right-hand side exceeds $1$, hence $b_{m+1} > \sum_{i=1}^m b_i + 1$. Applying Lemma 346.1 shows that $C$ is not complete. $\square$

FAST REALITY CHECK (illustration with a toy ratio). Take a toy geometric sequence $a_n=\lceil c^n\rceil$ with $c=1.7>\varphi$. If we delete every other term, the remaining subsequence has ratio about $c^2\approx 2.89$, and Lemma 346.1 predicts large gaps in subset sums. A small computation for the first few terms indeed shows missing intervals once a big ratio jump occurs (not included here as a theorem).

5) VERIFICATION. Lemma 346.1 is a standard and fully explicit gap argument. Proposition 346.2 is a direct inequality manipulation that uses the equivalence $c>\varphi\iff c^2>c/(c-1)$.

6) FINAL.

UNRESOLVED

(i) Strongest fully proved partial result obtained here. We proved the "easy" direction stated in the problem: if $a_{n+1}/a_n\ge c>\varphi$ uniformly, then deleting infinitely many terms necessarily destroys completeness (Proposition 346.2).

(ii) Exact first gap. The main open component here is the converse-type question: under the weaker hypothesis $a_{n+1}/a_n\ge 1+\varepsilon$, does the existence of a sequence satisfying $1$--$2$ force $a_{n+1}/a_n\to\varphi$? We have no argument establishing such a limiting ratio.

(iii) Top 3 next moves (concrete targets).

1. Prove a stability version of Proposition 346.2: if deletions always destroy completeness, show that ratios cannot stay bounded away from $\varphi$ on either side.
2. Analyze Graham's claimed example (as given in the statement) and compute its ratio behavior to see whether it converges to $\varphi$; then attempt to extract a general mechanism.
3. Establish necessary conditions for property $1$ (robust completeness under finite deletions), perhaps in terms of lower bounds on local additive coverage or on $\sum 1/a_n$.

(iv) Minimal counterexample structure. A counterexample to "ratio must tend to $\varphi$" would be a sequence satisfying $1$--$2$ and $a_{n+1}/a_n\ge 1+\varepsilon$ but with $\limsup a_{n+1}/a_n>\varphi+\delta$ or $\liminf a_{n+1}/a_n<\varphi-\delta$ for some $\delta>0$. Such a sequence would have to balance being complete after any finite deletion with being fragile under any infinite deletion, yet without the Fibonacci-like ratio.