This site is supported by donations to The OEIS Foundation.

# Complete sequences

This article is **under construction**.

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.^{[1]} 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.

## Contents

## 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)

weakly complete if (and only if)

is finite, and subcomplete if and only if there are positive integers *m* and *n* such that

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.^{[2]} 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 was sufficient for a set to be subcomplete, but Cassels^{[3]} showed that even is not sufficient for subcompleteness.

Erdős^{[4]} then proved a minimal density, which was improved by Folkman^{[5]} Hegyvári^{[6]}, Łuczak & Schoen^{[7]}, and finally Szemerédi & Vu^{[8]} who showed that (with ) there is a constant *c* such that if

for all *n* then *S* is subcomplete. There are sequences with

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^{[5]} and improved by Szemerédi & Vu^{[9]} who show that that (with being the number of elements of S up to x, with multiplicity) there is a constant *c* such that if

for all sufficiently large *n* then *S* is subcomplete.

## Polynomials

Roth & Szekeres^{[10]} 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^{[11]} re-proves the theorem by a different technique and gives an alternate necessary and sufficient criterion. Write then is weakly complete if and only if and 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^{[12]} extends this theorem to perturbed polynomials: if *f* is a polynomial of positive degree, and is a sequence of positive integers, then is subcomplete. He also proves a version allowing noninteger exponents in the 'polynomial'.

## References

- ↑ V. E. Hoggatt and Charles King, Problem for Solution: E1424,
*The American Mathematical Monthly***67**:6 (Jun.-Jul. 1960), p. 593. - ↑ J. L. Brown, Jr., Note on complete sequences of integers,
*The American Mathematical Monthly***68**:6 (Jun.-Jul. 1961), pp. 557-560. - ↑ J. W. S. Cassels, On the representation of integers as sums of distinct summands taken from a fixed set,
*Acta Scientiarum Mathematicarum (Szeged)***21**(1960), pp. 111–124. - ↑ Paul Erdős, On the representation of large integers as sums of distinct summands taken from a fixed set,
*Acta Arithmetica***7**:4 (1962), pp. 345-354. - ↑
^{5.0}^{5.1}J. Folkman, On the representation of integers as sums of distinct terms from a fixed sequence,*Canad. J. Math.***18**(1966), pp. 643–655. - ↑ Norbert Hegyvári, On the representation of integers as sums of distinct terms from a fixed set,
*Acta Arithmetica***92**:2 (2000), pp. 99-104. - ↑ Tomasz Łuczak and Tomasz Schoen, On the maximal density of sum-free sets,
*Acta Arithmetica***95**:3 (2000), pp. 225-229. - ↑ E. Szemerédi and V. H. Vu, Finite and infinite arithmetic progressions in sumsets,
*Annals of of Mathematics*(2)**163**:1 (2006), pp. 1-35] - ↑ E. Szemerédi and V. Vu, Long arithmetic progressions in sumsets: thresholds and bounds,
*J. Amer. Math. Soc.***19**:1 (2006), pp. 119–169. See also the preprint arXiv:math/0507539 though this does not contain the result in question. - ↑ K. R. Roth and G. Szekeres, Some asymptotic formulae in the theory of partitions,
*Quarterly J. Math.***5**(1954), pp. 241-259. - ↑ R. L. Graham, Complete sequences of polynomial values,
*Duke Math. J.***31**(1964), pp. 275-285. - ↑ Stefan A. Burr, On the completeness of sequences of perturbed polynomial values,
*Pacific J. Math.***85**:2 (1979), pp. 355-360.

## Cite this page as

Charles R Greathouse IV, *Complete sequences*. — From the On-Line Encyclopedia of Integer Sequences® (OEIS®) wiki. (Available at https://oeis.org/wiki/Complete_sequences)