Subset sums in abelian groups

作者：Balandraud Eric^*; Girard Benjamin; Griffiths Simon; Hamidoune Yahya Ould

来源：European Journal of Combinatorics, 2013, 34(8): 1269-1286.

DOI：10.1016/j.ejc.2013.05.009

Denoting by Sigma(S) the set of subset sums of a subset S of a finite abelian group G, we prove that
vertical bar Sigma(S)vertical bar >= vertical bar S vertical bar(vertical bar S vertical bar+)/4 - 1
whenever S is symmetric, vertical bar G vertical bar is odd and Sigma(S) is aperiodic. Up to an additive constant of 2 this result is best possible, and we obtain the stronger (exact best possible) bound in almost all cases. We prove similar results in the case vertical bar G vertical bar is even. Our proof requires us to extend a theorem of Olson on the number of subset sums of anti-symmetric subsets S from the case of Z(p) to the case of a general finite abelian group. To do so, we adapt Olson's method using a generalisation of Vosper's Theorem proved by Hamidoune and Plagne.

• 出版日期2013-11