Sumsets in the hypercube
In this paper, the authors study which sets in the Boolean cube \( \mathbb{F}_2^n \) can be written as sumsets. More precisely, given a set \( A \subseteq \mathbb{F}_2^n \), they look at the set\N\[\NA + A = \{a + b : a, b \in A\},\N\]\Nwhere addition is done modulo 2 in each coordinate. The main question they ask is: how many different sets can appear in this way? And what do these sets look like?\N\NTheir main result gives a sharp estimate: the number of sumsets is asymptotically equal to\N\[\N(2^n - 1) \cdot 2^{2^{n-1}},\N\]\NThey also show that almost every such sumset contains a linear subspace of codimension 1. This idea lets them describe most sumsets as unions of large structured subsets. They give a lower bound by constructing many such examples and an upper bound using ideas from entropy and additive combinatorics.
- A combinatorial problem; stability and order for models and theories in infinitary languages
- A refinement of the Cameron-Erdős conjecture
- A threshold phenomenon for random independent sets in the discrete hypercube
- Additive combinatorics
- Additive combinatorics: with a view towards computer science and cryptography -- an exposition
- An entropy approach to the hard-core model on bipartite graphs
- Correlation inequalities on some partially ordered sets
- Counting sets with small sumset and applications
- Counting sets with small sumset, and the clique number of random Cayley graphs
- Counting sumsets and differences in an abelian group.
- Counting sumsets and sum-free sets modulo a prime
- Covering the edges of a random graph by cliques
- Families of Non-disjoint subsets
- Finite field models in additive combinatorics
- Green's sumset problem at density one half
- scientific article; zbMATH DE number 3833857 (Why is no real title available?)
- scientific article; zbMATH DE number 4177149 (Why is no real title available?)
- scientific article; zbMATH DE number 3425719 (Why is no real title available?)
- scientific article; zbMATH DE number 2053394 (Why is no real title available?)
- scientific article; zbMATH DE number 3198427 (Why is no real title available?)
- Independent sets in the hypercube revisited
- Note on the number of balanced independent sets in the Hamming cube
- On the Bogolyubov-Ruzsa lemma
- On the density of families of sets
- On the number of sets with a given doubling constant
- Repeated communication and Ramsey graphs
- Shattering news
- Strong bounds for 3-progressions
- The chromatic number of random Cayley graphs
- The collected works of Wassily Hoeffding. Ed. by N. I. Fisher and P. K. Sen
- The number of sumsets in a finite field
- The number of sumsets in abelian group
- The probabilistic method
This page was built for publication: Sumsets in the hypercube
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7030692)
