Deletion thresholds and exponential examples for complete sequences
Abstract
We prove that the pairs of integers 0≤ 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≤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 (ai) has prefix sums Sj with Sj−aj+1→∞, then each sufficiently long prefix represents every integer from any fixed completeness threshold T to Sj−T. We also refute Graham's conjecture, later repeated by Erdős and Graham, that (⌊ tγn⌋)n≥1 is complete for every t>0 and 1<γ<(1+√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.
Related
- Finite deletion-induced saturation for every non-complete graph
- When Listwise Deletion Works: Causal Diagrams and Complete-Case Regression
- Some Remarks on Regular Sequences and Complete Intersections
- An Exponential Deterministic--Randomized Gap in ERM-Oracle Complexity for Thresholds on an Unknown Order
- Those Confounded Examples
BibTeX
@misc{geneson2026deletion,
title = {{Deletion thresholds and exponential examples for complete sequences}},
author = {Jesse Geneson},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.25107},
eprint = {2609.25107},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.25107},
}
RIS
TY - UNPB
TI - Deletion thresholds and exponential examples for complete sequences
AU - Jesse Geneson
PY - 2026
DA - 2026/09/20
PB - arXiv
DO - 10.48550/arxiv.2609.25107
UR - https://arxiv.org/abs/2609.25107
AB - We prove that the pairs of integers 0≤ 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≤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→∞, 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 (⌊ tγ^n⌋)_n≥1 is complete for every t>0 and 1<γ<(1+√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.
ER -