The Typical Approximate Structure of Sets with Bounded Sumset

DOI10.1137/22M1511801MaRDI QIDQ6170439zbMATH OpenFDO

Authors Marcelo Campos, Matthew Coulson, Oriol Serra, Maximilian Wötzel

Publication date 10 August 2023

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2108.06253

zbMATH Keywords

additive combinatoricshypergraph containerssumsets

Mathematics Subject Classification ID

Hypergraphs (05C65) Arithmetic combinatorics; higher degree uniformity (11B30) Inverse problems of additive number theory, including sumsets (11P70)

Abstract: Let $A_1$ and $A_2$ be randomly chosen subsets of the first $n$ integers of cardinalities $s_{2}geq{s}_1=Omega(s_2)$, such that their sumset $A_1+A_2$ has size $m$. We show that asymptotically almost surely $A_1$ and $A_2$ are almost fully contained in arithmetic progressions $P_1$ and $P_2$ with the same common difference and cardinalities approximately $s_{i}m/(s_1+s_2)$. We also prove a counting theorem for such pairs of sets in arbitrary abelian groups. The results hold for $s_i=omega(lo{g}^{3}n)$ and $s_1+s_{2}leqm=o(s_2/lo{g}^{3}n)$. Our main tool is an asymmetric version of the method of hypergraph containers which was recently used by Campos to prove similar results in the special case $A=B$.

Recommendations

• An efficient container lemma
• The number of Bh‐sets of a given cardinality
• Sum-free sets and related sets
• The Erdős-Moser sum-free set problem
• On the number of B_h-sets
• Online containers for hypergraphs, with applications to linear equations
• Simple containers for simple hypergraphs
• Counting configuration-free sets in groups
• The number of maximal sum-free subsets of integers
• On the number of graphs without large cliques

Cites work

• A Brunn-Minkowski inequality for the integer lattice
• A Generalisation of the Theorem of Cauchy and Davenport
• A generalization of Kneser's addition theorem
• A new proof of Szemerédi's theorem for arithmetic progressions of length four
• A refinement of the Cameron-Erdős conjecture
• A robust version of Freiman's $3k-4$ theorem and applications
• A statistical theorem of set addition
• Abschätzung der asymptotischen Dichte von Summenmengen
• Counting sets with small sumset and applications
• Freiman's theorem in an arbitrary abelian group
• scientific article; zbMATH DE number 3425719 (Why is no real title available?)
• Hypergraph containers
• Independent sets in hypergraphs
• On addition of two distinct sets of integers
• On addition of two distinct sets of integers
• On an almost all version of the Balog-Szemerédi-Gowers theorem
• On sums of dilates
• On the number of sets with a given doubling constant
• Restricted Set Addition in Groups I: The Classical Setting
• Restricted set addition in groups. III: Integer sumsets with generic restrictions
• Structure theorem for multiple addition and the Frobenius problem
• Sum of sets in several dimensions
• The structure of approximate groups.
• The typical structure of sets with small sumset

This page was built for publication: The Typical Approximate Structure of Sets with Bounded Sumset

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6170439)