This site is supported by donations to The OEIS Foundation.

Complete sequences

From OeisWiki
Jump to: navigation, search


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.

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

  1. V. E. Hoggatt and Charles King, Problem for Solution: E1424, The American Mathematical Monthly 67:6 (Jun.-Jul. 1960), p. 593.
  2. J. L. Brown, Jr., Note on complete sequences of integers, The American Mathematical Monthly 68:6 (Jun.-Jul. 1961), pp. 557-560.
  3. 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.
  4. 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. 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.
  6. 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.
  7. Tomasz Łuczak and Tomasz Schoen, On the maximal density of sum-free sets, Acta Arithmetica 95:3 (2000), pp. 225-229.
  8. 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]
  9. 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.
  10. K. R. Roth and G. Szekeres, Some asymptotic formulae in the theory of partitions, Quarterly J. Math. 5 (1954), pp. 241-259.
  11. R. L. Graham, Complete sequences of polynomial values, Duke Math. J. 31 (1964), pp. 275-285.
  12. 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)