Subset sums

Research output: Contribution to journalArticle

31 Scopus citations

Abstract

Suppose ε > 0 and k > 1. We show that if n > n0(k, ε) and A ⊆ Zn satisfies |A| > (( 1 k) + ε)n then there is a subset B ⊆ A such that 0 < |B| ≤ k and Σb∈Bb = 0 (in Zn). The case k = 3 solves a problem of Stalley and another problem of Erdös and Graham. For an integer m > 0, let snd(m) denote the smallest integer that does not divide m. We prove that for every ε > 0 there is a constant c = c(ε) > 1, such that for every n > 0 and every m, n1 + ε ≤ m ≤ n2 log2n every set A ⊆ {1, 2,..., n} of cardinality |A| > c · n snd(m) contains a subset B ⊆ A so that Σb∈Bb = m. This is best possible, up to the constant c. In particular it implies that for every n there is an m such that every set A ⊆ {1,...,n} of cardinality |A| > cn log n contains a subset B ⊆ A so that Σb∈Bb = m, thus settling a problem of Erdös and Graham.

Original languageEnglish (US)
Pages (from-to)196-205
Number of pages10
JournalJournal of Number Theory
Volume27
Issue number2
DOIs
StatePublished - Oct 1987

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory

Fingerprint Dive into the research topics of 'Subset sums'. Together they form a unique fingerprint.

  • Cite this