On the Sumset Partition Problem

A sequence m1,m2,…,mk of positive integers is n-realizable if there is a partition X1,X2,…,Xk of the set [n] such that the sum of the elements in Xi is mi for each i=1,2,…,k. In this paper we study the n-realizable sequences by adopting a different viewpoint from the one which has been previously used in the literature. We consider the realizability of a sequence in terms of the length k of the sequence or the values of its distinct elements. We characterize all n-realizable sequences with k⩽4 and, for k⩾5, we prove that n⩾4k−1 and mk>4k−1 are sufficient conditions for a sequence to be n-realizable. This sufficient condition complements the one which has been used in connection with the ascending subgraph decomposition conjecture of Alavi et al. [Y. Alavi, A. J.Boals, G. Chartrand, P. Erdős and O. Oellerman. The ascending subgraph decomposition problem. Congressus Numeratium, 58 (1987), 7–14]. We also characterize realizable sequences whose distinct terms grow exponentially. Finally we consider the modular version of the problem and prove that all sequences in Zp of length k⩽(p−1)/2 are realizable for any prime p⩾3. The bound on k is best possible.