Question

Fix integer $n\ge 1$, and let $E=\{e_1,...,e_n\}$ denote the standard basis of the vector space ${\mathbb F}_2^n$. Thus, for a set $A\subset{\mathbb F}_2^n$, the sumset $A+E:=\{a+e\colon a\in A,\ e\in E\}$ consists of all those elements of ${\mathbb F}_2^n$ which are at Hamming distance $1$ from an element of $A$. Now I wonder,

How small can $|A+E|$ be in terms of $|A|$? How to choose a set $A$ of prescribed size to minimize the size of $A+E$?

I would expect the answer to be well-known -- any reference?

Somewhat closer to what I actually need is the situation where $A$ consists of even vectors only; that is, of vectors orthogonal to $e_1+\dotsb+e_n$. How to choose $A$ (of prescribed size) under this additional constrain to minimize $|A+E|$?

Answer 1

If $E$ consists not only of unit vectors, but also of the zero vector, then according to Alon & Spencer ``Probabilistic method'' chapter 7, the sharp isoperimetric inequality was proved by Harper. It asserts that the Hamming ball minimizes $A+E$. In that chapter they show how to get a very good asymptotic bound for the same problem.