Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-27T07:13:28.588Z Has data issue: false hasContentIssue false
  • English
  • Français

On Sums of Generating Sets in ℤ2n

Published online by Cambridge University Press:  03 August 2012

CHAIM EVEN-ZOHAR
CHAIM EVEN-ZOHAR*
Affiliation:
Einstein Institute of Mathematics, The Hebrew University, Jerusalem 91904, Israel (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Let A and B be two affinely generating sets of ℤ2n. As usual, we denote their Minkowski sum by A+B. How small can A+B be, given the cardinalities of A and B? We give a tight answer to this question. Our bound is attained when both A and B are unions of cosets of a certain subgroup of ℤ2n. These cosets are arranged as Hamming balls, the smaller of which has radius 1.

By similar methods, we re-prove the Freiman–Ruzsa theorem in ℤ2n, with an optimal upper bound. Denote by F(K) the maximal spanning constant |〈 A 〉|/|A| over all subsets A ⊆ ℤ2n with doubling constant |A+A|/|A| ≤ K. We explicitly calculate F(K), and in particular show that 4K/4K ≤ F(K)⋅(1+o(1)) ≤ 4K/2K. This improves the estimate F(K) = poly(K)4K, found recently by Green and Tao [17] and by Konyagin [23].

Keywords

Primary 11P70
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 21 , Issue 6 , November 2012 , pp. 916 - 941
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]Bollobás, B. and Leader, I. (1996) Sums in the grid. Discrete Math. 162 31–48.Google Scholar
[2]Cauchy, A. L. (1813) Recherches sur les nombres. J. École Polytechnique 9 99–123.Google Scholar
[3]Cohen, G. and Zémor, G. (1999) Subset sums and coding theory. Astérisque 258 327–339.Google Scholar
[4]Davenport, H. (1935) On the addition of residue classes. J. London Math. Soc. 1 30.Google Scholar
[5]Deshouillers, J. M., Hennecart, F. and Plagne, A. (2004) On small sumsets in (ℤ/2ℤ)n. Combinatorica 24 53–68.Google Scholar
[6]Diao, H. (2009) Freiman–Ruzsa-type theory for small doubling constant. Math. Proc. Camb. Phil. Soc. 146 269–276.Google Scholar
[7]Eliahou, S. and Kervaire, M. (1998) Sumsets in vector spaces over finite fields. J. Number Theory 71 12–39.Google Scholar
[8]Eliahou, S. and Kervaire, M. (2005) Minimal sumsets in infinite abelian groups. J. Algebra 287 449–457.Google Scholar
[9]Eliahou, S. and Kervaire, M. (2005) Old and new formulas for the Hopf–Stiefel and related functions. Expositiones Mathematicae 23 127–145.Google Scholar
[10]Eliahou, S., Kervaire, M. and Plagne, A. (2003) Optimally small sumsets in finite abelian groups. J. Number Theory 101 338–348.Google Scholar
[11]Frankl, P. (1984) A new short proof for the Kruskal–Katona theorem. Discrete Math. 48 327–329.Google Scholar
[12]Frankl, P. (1987) The shifting technique in extremal set theory. In Surveys in Combinatorics 1987 (Whitehead, C., ed.), Vol. 123 of London Mathematical Society Lecture Notes, Cambridge University Press, pp. 81–110.Google Scholar
[13]Frankl, P. (1989) A lower bound on the size of a complex generated by an antichain. Discrete Math. 76 51–56.Google Scholar
[14]Freiman, G. A. (1973) Foundations of a Structural Theory of Set Addition (translated from the Russian), Vol. 37 of Translations of Mathematical Monographs, AMS.Google Scholar
[15]Gardner, R. J. and Gronchi, P. (2001) A Brunn–Minkowski inequality for the integer lattice. Trans. Amer. Math. Soc. 353 3995–4024.Google Scholar
[16]Green, B. and Ruzsa, I. Z. (2006) Sets with small sumset and rectification. Bull. London Math. Soc. 38 43.Google Scholar
[17]Green, B. and Tao, T. (2009) Freiman's theorem in finite fields via extremal set theory. Combin. Probab. Comput. 18 335–355.Google Scholar
[18]Harper, L. H. (1966) Optimal numberings and isoperimetric problems on graphs. J. Combin. Theory 1 385–393.Google Scholar
[19]Hennecart, F. and Plagne, A. (2003) On the subgroup generated by a small doubling binary set. Europ. J. Combin. 24 5–14.Google Scholar
[20]Hopf, H. (1940) Ein toplogischer Beitrag zur reellen Algebra. Comment. Math. Helv. 13 219–239.Google Scholar
[21]Katona, G. O. H. (1964) Intersection theorems for systems of finite sets. Acta Math. Hungar. 15 329–337.Google Scholar
[22]Katona, G. O. H. (1975) The Hamming-sphere has minimum boundary. Studia Sci. Math. Hungar. 10 131–140.Google Scholar
[23]Konyagin, S. V. (2008) On the Freiman theorem in finite fields. Math. Notes 84 435–438.Google Scholar
[24]Kruskal, J. B. (1963) The number of simplices in a complex. In Mathematical Optimization Techniques (Bellman, R., ed.), University of California Press, pp. 251–278.Google Scholar
[25]Lev, V. F. (2003) Generating binary spaces. J. Combin. Theory Ser. A 102 94–109.Google Scholar
[26]Lev, V. F. (2006) Critical pairs in abelian groups and Kemperman's structure theorem. Internat. J. Number Theory 2 379–396.Google Scholar
[27]Pfjster, A. (1965) Zur Darstellung von -1 als Summe von Quadraten in einem Körper. J. London Math. Soc. 1 159.Google Scholar
[28]Ruzsa, I. Z. (1992) Arithmetical progressions and the number of sums. Periodica Math. Hungar. 25 105–111.Google Scholar
[29]Ruzsa, I. Z. (1994) Generalized arithmetical progressions and sumsets. Acta Math. Hungar. 65 379–388.Google Scholar
[30]Ruzsa, I. Z. (1994) Sum of sets in several dimensions. Combinatorica 14 485–490.Google Scholar
[31]Ruzsa, I. Z. (1999) An analog of Freiman's theorem in groups. Astérisque 258 323–326.Google Scholar
[32]Sanders, T. (2008) A note on Freiman's theorem in vector spaces. Combin. Probab. Comput. 17 297–305.Google Scholar
[33]Schneider, R. (1993) Convex Bodies: The Brunn–Minkowski Theory, Vol. 44, Cambridge University Press.Google Scholar
[34]Shapiro, D. B. (2000) Compositions of Quadratic Forms, De Gruyter.Google Scholar
[35]Stiefel, E. (1940) Über Richtungsfelder in den projektiven Räumen und einen Satz aus der reellen Algebra. Comment. Math. Helv. 13 201–218.Google Scholar
[36]Tao, T. and Vu, V. (2006) Additive Combinatorics, Vol. 105 of Cambridge Studies in Advanced Mathematics, Cambridge University Press.Google Scholar
[37]Viola, E. (2007) Selected results in additive combinatorics: An exposition. In Electronic Colloquium on Computational Complexity (ECCC) 14.Google Scholar
[38]Vosper, A. G. (1956) The critical pairs of subsets of a group of prime order. J. London Math. Soc. 1 200.Google Scholar
[39]Yuzvinsky, S. (1981) Orthogonal pairings of Euclidean spaces. Michigan Math. J. 28 131–145.Google Scholar
[40]Zémor, G. (1992) An extremal problem related to the covering radius of binary codes. In Algebraic Coding, Vol. 573 of Lecture Notes in Computer Science, Springer, pp. 42–51.Google Scholar
[41]Zémor, G. (1992) Subset sums in binary spaces. Europ. J. Combin. 13 221–230.Google Scholar