Deletion thresholds and exponential examples for complete sequences

Abstract

We prove that the pairs of integers $0\le m<n$ for which a nondecreasing integer sequence can remain complete after every deletion of $m$ terms and become incomplete after every deletion of $n$ terms are exactly those with $m\le 1$. Here a sequence is complete if every sufficiently large integer is a finite sum of terms with distinct indices. This answers Erdős Problem 348, posed by Graham and later included in the book of Erdős and Graham. The proof uses a central-interval theorem: if a complete nondecreasing positive integer sequence $(a_i)$ has prefix sums $S_j$ with $S_j-a_{j+1}\to \infty$, then each sufficiently long prefix represents every integer from any fixed completeness threshold $T$ to $S_j-T$. We also refute Graham's conjecture, later repeated by Erdős and Graham, that $(\lfloor t{\gamma }^n\rfloor {)}_{n\ge 1}$ is complete for every $t>0$ and $1<\gamma <(1+\sqrt{5})/2$. We obtain the counterexample by combining Dubickas's fractional-part theorem with an elementary sign adjustment. For a common base in this range, we further construct two such sequences whose interleaving is incomplete and whose coefficient ratio is not a rational multiple of any integer power of the base.