Sumsets in the Hypercube

Abstract

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