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

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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].

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you. Unfortunately, there is no way to recall now what for I needed it some 7+ years ago... $\endgroup$
    – Seva
    Commented Jun 12, 2019 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.

Improve this answer
$\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
    Commented Sep 22, 2011 at 10:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .