Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|$?

share|improve this question
add comment

1 Answer

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.

share|improve this answer
Well, I actually was aware of the "classical" version with the unit ball instead of $E$ (which is why I am speaking about "an isoperimetric problem"). However, not including zero in $E$ can, potentially, change the things, and I wonder whether anything is known for this specific version of the problem - let alone, about the situation where $A$ consists of even vectors only. Thanks for the exact reference, anyway! –  Seva Sep 22 '11 at 10:00
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.