Complete minus finite sets, incomplete minus infinite sets: must $a_{n+1}/a_n\to(1+\sqrt5)/2$? (Erdős #346)
Statement
Call a sequence of integers complete if every sufficiently large integer is a sum of distinct members of it. Let $A=\{1\leq a_1< a_2<\cdots\}$ be a set of integers such that (1) $A\setminus B$ is complete for every FINITE subset $B\subseteq A$, and (2) $A\setminus B$ is not complete for every INFINITE subset $B\subseteq A$. Is it true that if additionally $a_{n+1}/a_n \geq 1+\epsilon$ for some $\epsilon>0$ and all $n$, then$$\lim_n \frac{a_{n+1}}{a_n}=\frac{1+\sqrt{5}}{2}?$$
Acceptance. FULLY RESOLVES: a proof that every sequence satisfying (1), (2), and $a_{n+1}/a_n\geq 1+\epsilon$ has $a_{n+1}/a_n\to(1+\sqrt5)/2$; OR an explicit counterexample — a sequence (given by a formula or algorithm) together with proofs of properties (1) and (2), verification of the growth hypothesis, and a proof that the ratio does not converge to $\varphi$. Machine-checkable (Lean/Coq) proof preferred — a Lean statement already exists in the formal-conjectures repository — else a complete written proof; note a counterexample still requires proof of the infinitary properties (1) and (2), not just numerics. ADVANCES: prove the conjecture under a stronger growth hypothesis (e.g. ratios eventually in a neighbourhood of $\varphi$, or monotone ratios); prove that $\liminf a_{n+1}/a_n \leq \varphi \leq \limsup a_{n+1}/a_n$ under the stated hypotheses; classify which limit points the ratio sequence can have; or construct new explicit families beyond Graham's $F_n-(-1)^n$ satisfying (1) and (2) with proofs, mapping the boundary. Deliver the proof file or Lean sources, or the counterexample construction with its proofs and any supporting verification code.
Background
Posed by Erdős and Graham [ErGr80, p.57]; listed as open on erdosproblems.com/346 (fetched 2026-07-13, status 'open'). Sequences satisfying (1) and (2) sit exactly on the boundary of completeness: robust to every finite deletion, destroyed by every infinite one. Graham [Gr64d] proved that the perturbed Fibonacci sequence $a_n=F_n-(-1)^{n}$ (where $F_n$ is the $n$th Fibonacci number) has both properties — and its ratio tends to the golden ratio $\varphi=(1+\sqrt5)/2$, motivating the conjecture that under a bounded-growth hypothesis this limit is forced. Erdős and Graham record two structural facts: if $a_{n+1}/a_n>\varphi$ for all $n$ then property (2) is automatic (the sequence is so sparse that any infinite deletion breaks completeness), and without any growth hypothesis the conjecture fails in spirit — it is not hard to construct very irregular sequences satisfying (1) and (2), which is why the hypothesis $a_{n+1}/a_n\geq 1+\epsilon$ is imposed. The statement has been formalised in Lean in Google DeepMind's formal-conjectures repository. Closely related venue neighbour: the problem on Erdős #347, a sequence with $a_{n+1}/a_n\to 2$ whose every cofinite subsequence has density-1 subset sums, comes from the same complete-sequences cluster of [ErGr80] but asks a different question. The attacker's tool: two-sided — for a refutation, computer-assisted design of a candidate sequence with ratios bounded in $(1+\epsilon,2)$ but not converging to $\varphi$ (completeness of explicit sequences can be certified by finite verification plus an inductive closure argument, Brown's criterion style); for a proof, growth/greedy analysis showing that ratio persistently away from $\varphi$ forces either an infinite deletable set (violating (1)'s tightness) or failure of (2).
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #346 (T. F. Bloom) | website |
| REF-02 | Lean formalisation of Erdős #346 (formal-conjectures, Google DeepMind) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.