Burr–Erdős (1981) open problems on the stability of completeness and subcompleteness of integer sequences under perturbation

Burr and Erdős, 'Completeness properties of perturbed sequences', Journal of Number Theory 13 (1981), 446–455, founded the systematic study of how subset-sum representation properties of an integer sequence survive perturbation. For a sequence $S$ of positive integers, $P(S)$ denotes the set of sums of distinct terms of $S$; $S$ is complete if $P(S)$ contains all sufficiently large integers, subcomplete if $P(S)$ contains an infinite arithmetic progression, and strongly complete if it stays complete after any finite deletion of terms; an X-perturbation replaces each term $s_n$ by a $t_n$ lying between $s_n$ and $s_n+x_n$ (either sign). The paper proved two opposing phenomena: summably small perturbations ($Σ1/|x_n|$ below an explicit constant) can destroy subcompleteness of any sequence, while constant-size perturbations turn every smoothly growing sequence with $s_{n+2}≤2s_n$ into a strongly complete one. Its closing section poses six interlinked questions, open ever since: (1) the sharp perturbation size for the destruction theorems — is mere convergence of $Σ1/|x_n|$ enough, and how far toward $x_n=O(n)$ can one go, given that $x_n=O(n^{1-ε})$ is impossible? (2) does a single super-polynomially growing sequence exist of which every $O(n^{1-ε})$-perturbation is subcomplete? (3) are the exponential-ratio thresholds $λ=2^{1/2}$ and $λ=2^{1/3}$ of the construction theorems critical — the authors expect the critical value for 1-perturbations to be either $√2$ or the golden ratio $φ$? (4) how essential is smoothness of growth? (5) how essential is the sign of the perturbations? (6) which construction results survive when completeness is replaced by subcompleteness — e.g., is there a subcomplete sequence growing slower than $2^n$ that no 1-perturbation makes complete?

Background

For a sequence $S={s_1,s_2,…}$ of positive integers, write $P(S)$ for the set of all integers representable as a sum of distinct terms of $S$ (distinct indices, so a repeated value may be used as often as it occurs). $S$ is called complete if $P(S)$ contains all sufficiently large integers, and entirely complete if $P(S)$ contains every positive integer. Completeness of sparse sequences has been studied since the 1960s: Folkman (1966) proved that sequences growing at most like $n^α$ with $α<1$ are subcomplete — meaning that $P(S)$ contains an infinite arithmetic progression — a robustness notion introduced precisely because completeness itself is fragile: deleting a few terms, or shifting terms by bounded amounts, easily destroys it. A sequence is strongly complete if it remains complete after removal of any finite number of terms, and strongly subcomplete if it remains subcomplete after any finite removal. A sequence is precomplete if $P(S)$ contains arbitrarily long runs of consecutive integers.

Burr and Erdős (1981) made perturbation-stability itself the object of study. Given sequences $S={s_n}$ and $X={x_n}$, where the $x_n$ may be negative or zero, a sequence $T={t_n}$ is an X-perturbation of $S$ if each $t_n$ lies between $s_n$ and $s_n+x_n$. Prior work of Burr (1979), building on Folkman, set one boundary of the theory: if $x_n=O(n^α)$ with $α<1$, then every X-perturbation of the values of a polynomial of degree at least one is subcomplete, so perturbations of polynomial size $n^{1-ε}$ can never be guaranteed to destroy subcompleteness. The introduction of the 1981 paper states that the authors 'have not been able to deal with the case $a=1$' (perturbations of order $n$), and proves results only for $a>1$, i.e. summably small perturbations.

Destruction (Section 2 of the paper). The principal theorem states that if $Σ1/|x_n|$ is sufficiently small then any sequence whatsoever is X-perturbable into a sequence that is not subcomplete (Theorem 2.1). A stronger form uses two lemmas: first, a classical diophantine-approximation lemma in the tradition of Cassels (1960) — if $\|αs_i\|$, the distances from $αs_i$ to the nearest integer, satisfy $Σ\|αs_i\|=γ<1/2$ for an irrational $α$, then $P(S)$ has density at most $2γ$ in every infinite arithmetic progression; second, a lemma providing reals $α,δ$ (any $α$ whose continued fraction has bounded partial quotients; for the golden ratio $φ$ one may take $δ=2$) such that any $m$ consecutive integers contain an $n$ with $\|αn\|<δ/m$. Together they yield Theorem 2.2: if $Σ1/|x_n|<1/(2δ)$, then any sequence is X-perturbable so that $P(S)$ has density strictly below 1 in every arithmetic progression; and Theorem 2.3: if $Σ1/|x_n|$ merely converges, then any sequence is X-perturbable into one that is not strongly subcomplete. These results sit exactly against the $n^{1-ε}$ barrier of Burr (1979) and Folkman (1966), leaving the border between 'summably small' and 'order $n$' unexplored.

Construction (Section 3 of the paper). In the opposite direction, the paper shows that incompleteness is even more fragile than completeness: every sequence satisfying $s_{n+2}≤2s_n$ for all large $n$ is 1-perturbable (each term shifted by at most 1) into a strongly complete sequence (Theorem 3.1), and every sequence satisfying $s_{n+3}≤2s_n$ is X-perturbable into a strongly complete sequence for any $X$ with infinitely many nonzero terms, the perturbations being of either sign (Theorem 3.2). Writing $λ=\lim s_{n+1}/s_n$ for the exponential growth ratio, these theorems apply whenever $λ<2^{1/2}$ and $λ<2^{1/3}$ respectively, while for $λ>2$ a counting argument shows the sequence cannot even be subcomplete — the authors call the interval between these thresholds 'a considerable amount of interesting unexplored territory'. The upper end is governed by Fibonacci-type behavior (Theorem 3.5): a sequence with $2<s_1<s_2$ and $s_n≥s_{n-1}+s_{n-2}$ is never complete, and a sequence with $\lim s_{n+1}/s_n>φ$, where $φ=(1+√5)/2$, cannot be strongly complete. At exactly $λ=φ$ the situation is delicate: for Fibonacci numbers $f_n$, the sequence ${f_n+c}$ is strongly complete for every $c>0$, ${f_n-c}$ is not, and by a result of Graham ${f_n-(-1)^n}$ is strongly complete but becomes incomplete after removal of any infinite subsequence. Theorem 3.6 exhibits the contrast with the construction theorems: for any $β<φ$ and $X={[β^n]}$ (integer parts), some sequence with ratio exactly $φ$ admits no X-perturbation that is complete. The construction machinery also isolates a quantitative smoothness notion: for a constant $\gamma$, a sequence is a γ-sequence if $s_{n+1}-\gamma s_n<b$ for some constant $b$ — that is, its successive ratios stay at most $\gamma$ up to bounded error. Lemma 3.4 shows that every γ-sequence is 1-perturbable into a strongly precomplete sequence (one that remains precomplete after any finite deletion of terms), and Theorem 3.7 shows that the positivity of that perturbation is essential: the sequence ${k,2k,4k,8k,…}$ ($k$ times the powers of $2$), $k>3$, cannot be $(2-k)$-perturbed (a negative constant perturbation) into a precomplete sequence. Theorem 3.8 shows that a sequence containing all large powers of 2 together with any infinite sequence of odd integers is strongly complete — so at growth rate 2 strong completeness is possible, but only through non-smooth growth; the relative smoothness of the ratio is thus itself a load-bearing hypothesis.

Later literature bifurcated into lines adjacent to, but distinct from, these questions: Ramsey-complete sequences (Burr–Erdős 1985, solved in their aspects by Conlon–Fox–Pham 2021); P-perturbations of sequences viewed as asymptotic bases and subbases of order $h$ — representations as sums of $h$ not-necessarily-distinct terms (Burke–Webb 1988, Fang 2018); multiplicative scalings $S_α={⌊αs_n⌋}$ and the set of good factors $α$ (Burr–Erdős–Graham–Li 1996, Hegyvári 2000, Fang 2020); and the 2020s revival of complete-sequence questions (Fan 2026 on strong completeness, van Doorn 2026 on Graham's $⌊tα^n⌋$ problem). None of these lines treats additive perturbations of distinct-term subset-sum systems.

Problem Statement

The problem is the cluster of six open questions posed in Section 4 ('Open Problems') of Burr and Erdős (1981). Their common objective is to determine the true boundary between the destruction regime of the paper's Section 2 and the construction regime of its Section 3 — that is, which perturbation sizes, growth rates, growth regularities, and perturbation signs allow or forbid preserving, destroying, or creating completeness and subcompleteness of integer sequences, where throughout $P(S)$ is the set of sums of distinct terms of $S$; 'complete', 'subcomplete', 'strongly complete', 'strongly subcomplete', 'precomplete' are as defined in the Background; and $T={t_n}$ is an X-perturbation of $S={s_n}$ when each $t_n$ lies between $s_n$ and $s_n+x_n$ ($x_n$ of either sign). Each of the six questions below stands on its own: a resolution of any one of them is complete for that question, while the stated objective is the resolution of the cluster as a whole.

(1) Perturbation-size threshold for destruction. Can the hypothesis of Theorems 2.1/2.2 — that $Σ1/|x_n|$ be smaller than an explicit constant — be weakened to mere convergence of $Σ1/|x_n|$? Can the admissible perturbation growth be pushed as far as $x_n=O(n)$? It is known (Burr 1979; Folkman 1966) that the theorems are false for $x_n=O(n^{1-ε})$, $ε>0$, so the answer determines the sharp threshold between the two regimes; the authors note that a weakening to $x_n=O(n)$ 'would probably require a completely new approach, if such a result were true at all'.

(2) Uniform resistance. Does there exist a single sequence $S$, growing faster than every polynomial, such that whenever $x_n=O(n^{1-ε})$, every X-perturbation of $S$ is subcomplete? (Known: for each fixed admissible $X$ one can build such an $S$, growing faster than every polynomial; open when $S$ must be chosen first, uniformly over all such $X$.) The paper also poses the variant in which 'subcomplete' is replaced by '$P(S)$ has density 1 in some arithmetic progression'.

(3) Critical exponential ratios. For sequences with $s_{n+1}/s_n→λ$, determine the largest $λ$ up to which the construction theorems hold: Theorem 3.1 makes every such sequence 1-perturbable into a strongly complete one for $λ<2^{1/2}$, Theorem 3.2 makes every such sequence X-perturbable (any $X$ with infinitely many nonzero terms, either sign) for $λ<2^{1/3}$, while for $λ>2$ no such sequence is even subcomplete and a sequence with $\lim s_{n+1}/s_n>φ=(1+√5)/2$ is not itself strongly complete (Theorem 3.5). Are $2^{1/2}$ and $2^{1/3}$ actually critical? In particular, the authors expect the critical $λ$ for Theorem 3.1 to be either $√2$ or $φ$, and not any value in between; decide this.

(4) Smoothness. To what extent is smoothness of growth (regularity of the ratios $s_{n+1}/s_n$) essential to the positive perturbation-to-completeness results — given that smooth Fibonacci-type growth obstructs completeness (Theorem 3.5) while non-smooth growth at rate 2 still permits strong completeness (Theorem 3.8)?

(5) Sign of perturbations. Is the sign of the permitted perturbations essential in general — given that every γ-sequence is 1-perturbable into a strongly precomplete sequence (Lemma 3.4) while the sequence ${k,2k,4k,8k,…}$ ($k$ times the powers of $2$), $k>3$, cannot be $(2-k)$-perturbed (a negative constant perturbation) into a precomplete sequence (Theorem 3.7)?

(6) Subcomplete analogues. Which of the Section 3 construction results survive when 'complete' is replaced by 'subcomplete'? Specifically: does Theorem 3.6 hold with 'complete' replaced by 'subcomplete' — i.e., for every $β<φ$, does there exist a sequence $S$ with $\lim s_{n+1}/s_n=φ$ such that no X-perturbation of $S$ with $X={[β^n]}$ is subcomplete? And does there exist a subcomplete sequence growing more slowly than ${2^n}$ that is not 1-perturbable into a complete sequence (the authors conjecture that such a sequence exists)?

References

1. Stefan A. Burr and Paul Erdős, Completeness properties of perturbed sequences, Journal of Number Theory 13 (1981), no. 4, 446–455, DOI 10.1016/0022-314X(81)90036-6, https://doi.org/10.1016/0022-314X(81)90036-6 (primary source)
2. Stefan A. Burr, On the completeness of sequences of perturbed polynomial values, Pacific Journal of Mathematics 85 (1979), 355–360, DOI 10.2140/pjm.1979.85.355, https://doi.org/10.2140/pjm.1979.85.355
3. Jon Folkman, On the representation of integers as sums of distinct terms from a fixed sequence, Canadian Journal of Mathematics 18 (1966), 643–655, DOI 10.4153/CJM-1966-065-2, https://doi.org/10.4153/CJM-1966-065-2
4. J. W. S. Cassels, On the representation of integers as the sums of distinct summands taken from a fixed set, Acta Scientiarum Mathematicarum (Szeged) 21 (1960), 111–124, zbMATH 0217.32102
5. Stefan A. Burr and Paul Erdős, A Ramsey-type property in additive number theory, Glasgow Mathematical Journal 27 (1985), 5–10, DOI 10.1017/S0017089500006029, https://doi.org/10.1017/S0017089500006029
6. John R. Burke and William A. Webb, Sums of perturbed sequences of integers, Journal of Number Theory 29 (1988), no. 3, 264–270, DOI 10.1016/0022-314X(88)90105-9, https://doi.org/10.1016/0022-314X(88)90105-9
7. Stefan A. Burr, Paul Erdős, Ronald L. Graham, and W. Wen-Ching Li, Complete sequences of sets of integer powers, Acta Arithmetica 77 (1996), no. 2, 133–138, DOI 10.4064/aa-77-2-133-138, https://doi.org/10.4064/aa-77-2-133-138
8. Norbert Hegyvári, Subset sums in ℕ², Combinatorics, Probability and Computing 5 (1996), no. 4, 393–402, DOI 10.1017/S0963548300002145, https://doi.org/10.1017/S0963548300002145
9. Norbert Hegyvári, On the representation of integers as sums of distinct terms from a fixed set, Acta Arithmetica 92 (2000), no. 2, 99–104, DOI 10.4064/aa-92-2-99-104, https://doi.org/10.4064/aa-92-2-99-104
10. Vitaly Bergelson and David Simmons, New examples of complete sets, with connections to a Diophantine theorem of Furstenberg, arXiv:1507.02208 (2015, v2 2016), https://arxiv.org/abs/1507.02208 (published as Acta Arithmetica 177 (2017), no. 2, 101–131, DOI 10.4064/aa8221-10-2016)
11. Chris Fuller and Robert H. Nichols Jr., Generalized anti-Waring numbers, Journal of Integer Sequences 18 (2015), no. 10, Article 15.10.5, https://geodesic.mathdoc.fr/item/JIS_2015__18_10_a5/
12. Jin-Hui Fang, Stability of perturbed sequences as a subbasis, Publicationes Mathematicae Debrecen 92 (2018), no. 3–4, 453–458, DOI 10.5486/PMD.2018.8026, https://doi.org/10.5486/PMD.2018.8026
13. Jinhui Fang, Note on the completeness of perturbed sequences, Chinese Annals of Mathematics, Series A 41 (2020), no. 3, 279–282 (in Chinese, with English summary), DOI 10.16205/j.cnki.cama.2020.0019, https://doi.org/10.16205/j.cnki.cama.2020.0019
14. David Conlon, Jacob Fox, and Huy Tuan Pham, Subset sums, completeness and colorings, arXiv:2104.14766 (2021), https://arxiv.org/abs/2104.14766
15. Steve Fan, Strongly complete sets and a conjecture of Erdős, arXiv:2607.14071 (2026), https://arxiv.org/abs/2607.14071
16. Wouter van Doorn, Completeness of exponentially increasing sequences, arXiv:2602.23394 (2026), https://arxiv.org/abs/2602.23394
17. T. F. Bloom (ed.), The Erdős Problems, Problem 348 (robustness of complete sequences under deletion) and Problem 349 (completeness of $⌊tα^n⌋$), https://www.erdosproblems.com/348 and https://www.erdosproblems.com/349