Subset sums in abelian groups

Abstract : Denoting by Sigma(S) the set of subset sums of a subset S of a finite abelian group G, we prove that |Sigma(S)| >= |S|(|S|+2)/4-1 whenever S is symmetric, |G| 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 |G| 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.
Complete list of metadatas

https://hal.sorbonne-universite.fr/hal-00649593
Contributor : Benjamin Girard <>
Submitted on : Thursday, December 8, 2011 - 11:40:03 AM
Last modification on : Wednesday, May 15, 2019 - 3:44:10 AM
Long-term archiving on : Friday, March 9, 2012 - 2:31:04 AM

Files

Subset_sums_in_abelian_groups....
Files produced by the author(s)

Identifiers

Citation

Eric Balandraud, Benjamin Girard, Simon Griffiths, Yahya Ould Hamidoune. Subset sums in abelian groups. European Journal of Combinatorics, Elsevier, 2013, 34 (8), pp.1269-1286. ⟨10.1016/j.ejc.2013.05.009⟩. ⟨hal-00649593⟩

Share

Metrics

Record views

296

Files downloads

250