This site is supported by donations to The OEIS Foundation.

# Complete sequences

Please do not rely on any information it contains.

A sequence of natural numbers is complete when all positive integers can be represented as the sum of some finite subsequence of the sequence. A sequence is weakly complete (often simply complete in recent literature) when all sufficiently large numbers can be so represented. If the sum of finite subsequences contains some infinite arithmetic progression the sequence is called subcomplete. The same terminology is used for sets and multisets.

## Definition

Given a sequence S of positive integers, let P(S) be the set of numbers which can be represented as the sum of a finite subsequence of S. Then S is complete if (and only if)

$P(S)=\mathbb {N} ,$ weakly complete if (and only if)

$\mathbb {N} \setminus P(S)$ is finite, and subcomplete if and only if there are positive integers m and n such that

$\{mk+n:k\in \mathbb {N} \}\subset P(S).$ A necessary and sufficient condition for a sequence of positive integers to be complete is that the smallest term is 1 and the sum of the smallest n terms is greater than the n+1-st term. Hence the sequence of the powers of 2 is a term-by-term upper bound on any complete sequence.

## Relationship between complete and subcomplete

For every subcomplete set, the addition of finitely many elements can transform it into a complete set. (The same holds trivially for subcomplete sequences and multisets.) The reverse is also true: removing any finite number of elements from a complete sequence yields a subcomplete sequence.

A subcomplete sequence S is weakly complete if and only if for all n, P(S) has an element in all residue classes mod n.

## Density

Paul Erdős conjectured that $a(n+1)/a(n)\to 1$ was sufficient for a set to be subcomplete, but Cassels showed that even $a(n+1)/a(n)<1+a_{n}^{-1/2+\varepsilon }$ is not sufficient for subcompleteness.

Erdős then proved a minimal density, which was improved by Folkman Hegyvári, Łuczak & Schoen, and finally Szemerédi & Vu who showed that (with $A(x)=\left|\{s\in S:s\leq x\}\right|$ ) there is a constant c such that if

$A(n)>c{\sqrt {n}}$ for all n then S is subcomplete. There are sequences with

$A(n)>{\sqrt {2n}}$ which are not subcomplete, so the result is the best possible up to the constant.

The analogous result for multisets and sequences was proved by Folkman and improved by Szemerédi & Vu who show that that (with $A^{*}(x)$ being the number of elements of S up to x, with multiplicity) there is a constant c such that if

$A^{*}(n)>cn$ for all sufficiently large n then S is subcomplete.

## Polynomials

Roth & Szekeres showed that if a polynomial with real coefficients maps integers to integers, a necessary and sufficient condition for the range of the polynomial p to be weakly complete is that the leading coefficient is positive and for any prime p there is an integer m such that p does not divide f(m).

Graham re-proves the theorem by a different technique and gives an alternate necessary and sufficient criterion. Write $f(x)=c_{0}+c_{1}{x \choose 1}+\cdots +c_{n}{x \choose n},$ then $f(\mathbb {N} )$ is weakly complete if and only if $c_{n}>0$ and $\operatorname {gcd} (N(c_{i}))=1$ where N finds the numerator in lowest terms (or gives 0 if the number is irrational).

Alternately, if a (rational) polynomial maps positive integers to positive integers, its image is subcomplete. Burr extends this theorem to perturbed polynomials: if f is a polynomial of positive degree, $\alpha <1,$ and $s_{n}=f(n)+O(n^{\alpha })$ is a sequence of positive integers, then $\{a_{1},a_{2},\ldots \}$ is subcomplete. He also proves a version allowing noninteger exponents in the 'polynomial'.