10
$\begingroup$

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

$\endgroup$
6
$\begingroup$

When A consists of even vectors only, the problem was probably solved by Korner and Wei [Odd and even Hamming spheres also have minimum boundary, Discrete Math. 51 (1984), 147–165]. See also Lemma 1.10 in [D. Galvin, On homomorphisms from the Hamming cube to Z, Israel J. of Math 138 (2003), 189-213].

$\endgroup$
1
  • $\begingroup$ Thank you. Unfortunately, there is no way to recall now what for I needed it some 7+ years ago... $\endgroup$
    – Seva
    Jun 12 '19 at 13:01
4
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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! $\endgroup$
    – Seva
    Sep 22 '11 at 10:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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