Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-26T16:56:37.939Z Has data issue: false hasContentIssue false
  • English
  • Français

k-Sums in Abelian Groups

Published online by Cambridge University Press:  23 April 2012

BENJAMIN GIRARD ,
SIMON GRIFFITHS  and
YAHYA OULD HAMIDOUNE
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])
Get access Rights & Permissions [Opens in a new window]

Abstract

Given a finite subset A of an abelian group G, we study the set k ∧ A of all sums of k distinct elements of A. In this paper, we prove that |k ∧ A| ≥ |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 A ⊆ G for which |k ∧ A| = |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.

Keywords

Primary 05E1511B1311P7005C15
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 21 , Issue 4 , July 2012 , pp. 582 - 596
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 7–29.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 404–417.CrossRefGoogle Scholar
[3]Bollobás, B. and Leader, I. (1999) The number of k-sums modulo k. J. Number Theory 78 27–35.Google Scholar
[4]Cauchy, A. (1813) Recherches sur les nombres. J. École Polytechnique 9 99–116.Google Scholar
[5]Davenport, H. (1935) On the addition of residue classes. J. London Math. Soc. 10 30–32.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 140–146.CrossRefGoogle Scholar
[7]Diderrich, G. T. (1973) Sums of length t in abelian groups. Israel J. Math. 14 14–22.CrossRefGoogle Scholar
[8]Erdős, P., Ginzburg, A. and Ziv, A. (1961) Theorem in the additive number theory. Bull. Res. Council Israel (F) 10 41–43.Google Scholar
[9]Erdős, P. and Heilbronn, H. (1964) On the addition of residue classes mod p. Acta Arith. 9 149–159.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 513–523.CrossRefGoogle Scholar
[11]Gao, W. and Geroldinger, A. (2006) Zero-sum problems in finite abelian groups: A survey. Expo. Math. 24 337–369.CrossRefGoogle Scholar
[12]Hamidoune, Y. O. (1998) Adding distinct congruence classes. Combin. Probab. Comput. 7 81–87.CrossRefGoogle Scholar
[13]Hamidoune, Y. O., Lladó, A. S. and Serra, O. (2000) On restricted sums. Combin. Probab. Comput. 9 513–518.Google Scholar
[14]Lev, V. F. (2002) Three-fold restricted set addition in groups. European J. Combin. 23 613–617.CrossRefGoogle Scholar
[15]Lev, V. F. (2005) Restricted set addition in abelian groups: Results and conjectures. J. Théor. Nombres Bordeaux 17 181–193.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 275–284.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. 87–210.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