The hypercube: $|A {\stackrel2+} E| \ge |A|$? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T10:20:54Z http://mathoverflow.net/feeds/question/80075 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/80075/the-hypercube-a-stackrel2-e-ge-a The hypercube: $|A {\stackrel2+} E| \ge |A|$? Seva 2011-11-04T17:41:35Z 2011-11-07T10:37:10Z <p>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.</p> <p>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 <em>at least two</em> 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?</p> <p>It is not difficult to find a linear subspace $L&lt;{\mathbb F}_2^n$ of co-dimension <code>${\rm codim}\,L=\lfloor\log_2 n\rfloor+1$</code> 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|&lt;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:</p> <blockquote> <p>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?</p> </blockquote> <p>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$).</p> <p>Another remark is that $|A{\stackrel2+} E|\ge|A|$ holds true if $A\subseteq{\mathbb F}_2^n$ is an <em>affine subspace</em> with $|A|>2^n/n$.</p> http://mathoverflow.net/questions/80075/the-hypercube-a-stackrel2-e-ge-a/80104#80104 Answer by fedja for The hypercube: $|A {\stackrel2+} E| \ge |A|$? fedja 2011-11-05T02:29:48Z 2011-11-07T10:37:10Z <p>OK, suppose that $n\ge 3$, let $A$ be a set of <em>even</em> 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. </p> <p>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$.</p> <p>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.$$</p> <p>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.</p>