On a question of Erdös on subsequence sums

Abstract

Paul Erdös asked how dense a sequence of integers, none of which is the sum of a consecutive subsequence, can be. In other words, let 〈x1,...,xm〉 be an increasing sequence of integers in [1,n], such that there do not exist i, j, and k, with 0 < i < j < k ≤ m and xi + xi+1 + ⋯ + xj = xk. Erdös asked if m > n/2 + 1 is possible. A simple argument shows that m > 2n/3 + O(log n) is impossible. Freud recently constructed a sequence with m = 19n/36. This note constructs a sequence with m = 13n/24 - O(1) and extends the simple upper bound to show that m > (2/3 - ∈)n + (log n) is impossible for ∈= 1/512.