Sumsets in the Hypercube

2024/03/25 by Noga Alon, Or Zamir, Alon, Noga +1
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #Embedded Systems Design Techniques #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems

paper · pdf · doi:10.48550/arxiv.2403.16589

openalex publication_date 2024/03/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

A subset S of the Boolean hypercube \mathbbF₂ⁿ is a sumset if S = A+A = \a + b | a, b∈ A\ for some A ⊆ \mathbbF₂ⁿ. We prove that the number of sumsets in \mathbbF₂ⁿ is asymptotically (2ⁿ-1)2^2^n-1. Furthermore, we show that the family of sumsets in \mathbbF₂ⁿ is almost identical to the family of all subsets of \mathbbF₂ⁿ that contain a complete linear subspace of co-dimension 1.

Related

• Approximating Sumset Size
• Testing Sumsets is Hard
• On sumsets in \Bbb F₂ⁿ
• A result on the size of iterated sumsets in ℤ^d
• The typical approximate structure of sets with bounded sumset