Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-23T14:18:28.487Z Has data issue: false hasContentIssue false

k-Sums in Abelian Groups

Published online by Cambridge University Press:  23 April 2012

BENJAMIN GIRARD
Affiliation:
IMJ, Équipe Combinatoire et Optimisation, Université Pierre et Marie Curie (Paris 6), 4 Place Jussieu, 75005 Paris, France (e-mail: [email protected])
SIMON GRIFFITHS
Affiliation:
IMPA, Estrada Dona Castorina 110, Rio de Janeiro, Brasil 22460-320 (e-mail: [email protected])

Abstract

Given a finite subset A of an abelian group G, we study the set kA of all sums of k distinct elements of A. In this paper, we prove that |kA| ≥ |A| for all k ∈ {2,. . .,|A| − 2}, unless k ∈ {2, |A| − 2} and A is a coset of an elementary 2-subgroup of G. Furthermore, we characterize those finite sets AG for which |kA| = |A| for some k ∈ {2,. . .,|A| − 2}. This result answers a question of Diderrich. Our proof relies on an elementary property of proper edge-colourings of the complete graph.

Type
Paper
Copyright
Copyright © Cambridge University Press 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Alon, N. (1999) Combinatorial Nullstellensatz. Combin. Probab. Comput. 8 729.CrossRefGoogle Scholar
[2]Alon, N., Nathanson, M. B. and Ruzsa, I. (1996) The polynomial method and restricted sums of congruence classes. J. Number Theory 56 404417.CrossRefGoogle Scholar
[3]Bollobás, B. and Leader, I. (1999) The number of k-sums modulo k. J. Number Theory 78 2735.Google Scholar
[4]Cauchy, A. (1813) Recherches sur les nombres. J. École Polytechnique 9 99116.Google Scholar
[5]Davenport, H. (1935) On the addition of residue classes. J. London Math. Soc. 10 3032.CrossRefGoogle Scholar
[6]Dias da Silva, J. A. and Hamidoune, Y. O. (1994) Cyclic spaces for Grassmann derivatives and additive theory. Bull. London Math. Soc. 26 140146.CrossRefGoogle Scholar
[7]Diderrich, G. T. (1973) Sums of length t in abelian groups. Israel J. Math. 14 1422.CrossRefGoogle Scholar
[8]Erdős, P., Ginzburg, A. and Ziv, A. (1961) Theorem in the additive number theory. Bull. Res. Council Israel (F) 10 4143.Google Scholar
[9]Erdős, P. and Heilbronn, H. (1964) On the addition of residue classes mod p. Acta Arith. 9 149159.CrossRefGoogle Scholar
[10]Gallardo, L., Grekos, G., Habsieger, L., Hennecart, F., Landreau, B. and Plagne, A. (2002) Restricted addition in /n and an application to the Erdős–Ginzburg–Ziv problem. J. London Math. Soc. 65 513523.CrossRefGoogle Scholar
[11]Gao, W. and Geroldinger, A. (2006) Zero-sum problems in finite abelian groups: A survey. Expo. Math. 24 337369.CrossRefGoogle Scholar
[12]Hamidoune, Y. O. (1998) Adding distinct congruence classes. Combin. Probab. Comput. 7 8187.CrossRefGoogle Scholar
[13]Hamidoune, Y. O., Lladó, A. S. and Serra, O. (2000) On restricted sums. Combin. Probab. Comput. 9 513518.Google Scholar
[14]Lev, V. F. (2002) Three-fold restricted set addition in groups. European J. Combin. 23 613617.CrossRefGoogle Scholar
[15]Lev, V. F. (2005) Restricted set addition in abelian groups: Results and conjectures. J. Théor. Nombres Bordeaux 17 181193.Google Scholar
[16]Mann, H. B. and Olson, J. E. (1967) Sums of sets in the elementary abelian group of type (p, p). J. Combin. Theory 2 275284.Google Scholar
[17]Petridis, G. New proofs of Plünnecke-type estimates for product sets in groups. arXiv:1101.3507 [math.CO]Google Scholar
[18]Ruzsa, I. (2009) Sumsets and structure. In Combinatorial Number Theory and Additive Group Theory (Geroldinger, A. and Ruzsa, I., eds), Birkhäuser, pp. 87210.Google Scholar
[19]Tao, T. and Vu, V. (2006) Additive Combinatorics, Cambridge University Press.CrossRefGoogle Scholar
[20]Wang, G. (2008) On restricted sumsets in abelian groups of odd order. Integers 8 #A22.Google Scholar