The hypercube: $|A {\stackrel2+} E| \ge |A|$?

2011-11-04T17:41:35Z

I have a good motivation to ask the question below, but since the post is already a little long, and the problem looks rather natural and appealing (well, to me, at least), I'd rather go straight to the point.

Let $n\ge 3$ be an integer. If $E$ denotes the standard basis of the vector space ${\mathbb F}_2^n$, then for any subset $A\subset{\mathbb F}_2^n$ we have $|A+E|\ge|A|$. This trivial estimate is easy to improve in various ways, but this is not my concern here. What I am interested in instead is the sumset $A{\stackrel2+} E$ consisting of all those vectors of ${\mathbb F}_2^n$ with at least two representations as $a+e$, where $a\in A$ and $e\in E$; that is, vectors at Hamming distance $1$ from at least two elements of $A$. How small can this sumset be?

It is not difficult to find a linear subspace $L<{\mathbb F}_2^n$ of co-dimension ${\rm codim}\,L=\lfloor\log_2 n\rfloor+1$ such that every two elements of $L$ are at least distance $3$ from each other. Clearly, $L{\stackrel2+} E$ is empty, showing that if $|A|<2^n/n$, then, in general, no lower bound for $|A{\stackrel2+} E|$ can be obtained. Let's assume, however, that $A$ is large; what can be said in this case? A simple double counting shows that $$ |A{\stackrel2+} E| > \Big( 1-\frac{2^n}{n|A|} \Big) |A|. $$ My question is: assuming that $A$ is large enough (say, $|A|=2^{n-1}$), can this estimate be improved to $|A{\stackrel2+} E|\ge|A|$? Here is a way to put it in a particularly simple, notation-free form:

Suppose that half of the vertices of the $n$-dimensional hypercube are colored, say, red. Is it true that under any such coloring, at least half of the vertices have two (or more) red neighbors?

Notice that, if true, the estimate $|A{\stackrel2+}E|\ge|A|$ is best possible: equality is attained, for instance, if $A$ is the set of all vectors of the same parity (alternatively, all vectors with the first coordinate equal to $0$, or all vectors with the sum of all coordinates, but the first one, equal to $0$).

Another remark is that $|A{\stackrel2+} E|\ge|A|$ holds true if $A\subseteq{\mathbb F}_2^n$ is an affine subspace with $|A|>2^n/n$.

Answer by fedja for The hypercube: $|A {\stackrel2+} E| \ge |A|$?

2011-11-05T02:29:48Z

OK, suppose that $n\ge 3$, let $A$ be a set of even vertices of cardinatily $2^n\mu\ge 2^{n-2}$ (so $\mu\ge \frac 14$), and write $B:=A{\stackrel2+}E$; that is, $B$ is the set of odd vertices with at least two neighbors in $A$. Assume that $|B|=2^n\xi$. Our aim is to show that $\xi\ge\mu$. Let us consider the action of the averaging (over neighbors) operator $T$ in $L^2$ with respect to the Haar measure.

Let $f$ be the characteristic function of $A$. Let $g$ be $f$ with the constant and the alternating components removed; thus, $g(z)=f(z)-2\mu$ if $z$ is even, and $g(z)=0$ if $z$ is odd. Then $\|g\|_2^2=\mu-2\mu^2$ and, thereby, $\|Tg\|_2^2\le (1-\frac 2n)^2(\mu-2\mu^2)$ because we removed the eigenspaces corresponding to the eigenvalues $\pm 1$ and every other eigenvalue is at most $1-\frac 2n$.

On the other hand, we know that $Tg\le \frac 1n-2\mu$ on the complement of $B$ in the set of odd vertices. To balance it to the average $0$, we should have $Tg$ at least $\frac{\frac 12-\xi}{\xi}(2\mu-\frac 1n)$ on $B$ on average and, since the quadratic average can be only larger, we get $$ \|Tg\|_2^2\ge \left[(\frac 12-\xi)+\xi\left(\frac{\frac 12-\xi}{\xi}\right)^2\right] (2\mu-\frac 1n)^2=\frac 12\frac{\frac 12-\xi}{\xi}(2\mu-\frac 1n)^2 $$ Thus $$ \frac 12(\frac 12-\xi)(2\mu-\frac 1n)^2\le \xi(1-\frac 2n)^2(\mu-2\mu^2) $$ Now, $2\mu-\frac 1n=2\mu(1-\frac{2}{4\mu n})\ge 2\mu(1-\frac 2n)$ under our assumption $\mu\ge \frac 14$. So, we get $$ \frac 12(\frac 12-\xi)4\mu^2 \le \xi(\mu-2\mu^2) $$ or, equivalently, $$ (1-2\xi)\mu\le (1-2\mu)\xi $$ i.e., $$ \mu\le\xi. $$

I hope I haven't made a stupid mistake anywhere though I do not really like this proof: it works for $\stackrel{2}+$, but not for $\stackrel{4}+$ and you are, probably, interested in $\stackrel{K}+$ for all fixed $K$ as $n\to\infty$. Anyway, it gives the desired cutoff at $1/2$ for fixed parity and, thereby, the cutoff at $\frac 34$ in general.

The hypercube: $|A {\stackrel2+} E| \ge |A|$? - MathOverflow

The hypercube: $|A {\stackrel2+} E| \ge |A|$?

Answer by fedja for The hypercube: $|A {\stackrel2+} E| \ge |A|$?