On Sums of Generating Sets in ℤ<sub>2</sub><sup><i>n</i></sup>

Type: Article

Publication Date: 2012-08-03

Citations: 15

DOI: https://doi.org/10.1017/s0963548312000351

Abstract

Let A and B be two affinely generating sets of (Z_2)^n. 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 (Z_2)^n. 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 (Z_2)^n, with an optimal upper bound. Denote by F(K) the maximal spanning constant |<A>|/|A|, over all subsets A of (Z_2)^n with doubling constant |A+A|/|A| < K. We explicitly calculate F(K), and in particular show that 4^K / 4K < F(K) (1+o(1)) < 4^K / 2K. This improves the estimate F(K) = poly(K) 4^K, found recently by Green and Tao and by Konyagin.

Locations

  • arXiv (Cornell University) - View - PDF
  • DataCite API - View
  • Combinatorics Probability Computing - View

Similar Works

Action Title Year Authors
+ A note on the Freiman and Balog-Szemeredi-Gowers theorems in finite fields 2007 Ben Green
Terence Tao
+ PDF Chat Brunn-Minkowski type estimates for certain discrete sumsets 2024 Albert Lopez Bruch
Yifan Jing
Akshat Mudgal
+ PDF Chat A NOTE ON THE FREIMAN AND BALOG–SZEMERÉDI–GOWERS THEOREMS IN FINITE FIELDS 2009 Ben Green
Terence Tao
+ On Small Sumsets in (Z/2Z) n 2004 Jean-Marc Deshouillérs
Fran�ois Hennecart
Alain Plagne
+ On Sub-critical Sums of Generating Sets in (Z_2)^n (Note) 2011 Chaim Even‐Zohar
+ On Minkowski Sums of Many Small Sets 2018 Maria Roginskaya
Victor S. Shulman
+ PDF Chat Freiman's Theorem in Finite Fields via Extremal Set Theory 2009 Ben Green
Terence Tao
+ Small Sumsets in Free Products of $$\mathbb{Z}/2\mathbb{Z}$$ 2010 Shalom Eliahou
Cédric Lecouvey
+ On sets with small sumset in the circle 2017 Pablo Candela
Anne de Roton
+ Freiman's theorem in finite fields via extremal set theory 2007 Ben Green
Terence Tao
+ Unification of zero-sum problems, subset sums and covers of ℤ 2003 Zhi‐Wei Sun
+ PDF Chat COMPRESSIONS, CONVEX GEOMETRY AND THE FREIMAN–BILU THEOREM 2006 B. Green
Terence Tao
+ PDF Chat A Geometric Approach for the Upper Bound Theorem for Minkowski Sums of Convex Polytopes 2016 Menelaos I. Karavelas
Eleni Tzanaki
+ PDF Chat The Spherical Kakeya Problem in Finite Fields 2020 Mehdi Makhul
Audie Warren
Arne Winterhof
+ New bounds in the Bogolyubov-Ruzsa lemma 2023 Tomasz Kosciuszko
Tomasz Schoen
+ The Spherical Kakeya Problem in Finite Fields 2020 Mehdi Makhul
Audie Warren
Arne Winterhof
+ The Spherical Kakeya Problem in Finite Fields 2020 Mehdi Makhul
Audie Warren
Arne Winterhof
+ PDF Chat Inverse additive problems for Minkowski sumsets I 2012 Gregory A. Freiman
David J. Grynkiewicz
Oriol Serra
Yonutz V. Stanchescu
+ A Weighted Prékopa–Leindler Inequality and Sumsets with Quasicubes 2022 Ben Green
Dávid Matolcsi
Imre Z. Ruzsa
George Shakan
Dmitrii Zhelezov
+ PDF Chat If (<i>A</i>+<i>A</i>)/(<i>A</i>+<i>A</i>) is small, then the ratio set is large 2016 Oliver Roche‐Newton