Hostname: page-component-745bb68f8f-5r2nc Total loading time: 0 Render date: 2025-02-07T04:54:29.506Z 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: chaim.evenzohar@mail.huji.ac.il)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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

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