MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
As stated, it is overly optimistic. Take $A$ to be the set of all vertices of the same parity. Then the count is sharp. Now, we can kill one 2-neighbour vertex removing at most $n$ vertices in $A$. But it costs nothing to add $n$ vertices of the opposite parity (in fact, you can add as many as $2^{n-1}/n$ of them without creating new 2-neighbour vertices). So even if the conjecture is true, the cutoff is not at $2^{n-1}$. – fedja Nov 5 '11 at 0:35
@fedja: correct; I should have noticed this... – Seva Nov 5 '11 at 8:44
up vote 7 down vote accepted

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.

share|cite|improve this answer
I am impressed by the fact that there is a progress, but I am afraid I do not understand much in your solution. To begin with, what do you mean by "removing the constant and alternating components"? Exactly how is $g$ defined? And what is "removing an eigenspace"? – Seva Nov 5 '11 at 7:37
The full Fourier system on the cube '$\{-1,1\}^n$' consists of products $\prod_{j\in J}x_j$ with '$J\subset\{1,2,\dots,n\}$'. They are eigenvectors of the averaging operator $Th(x)=\frac 1n\sum_{e\in E}h(x+e)$ with the eigenvalues $1-\frac{2|J|}{n}$. The two bad ones are $J=\varnothing$ (constant, eigenvalue 1) and '$J=\{1,\dots,n\}$' (alternating, eigenvalue -1). $g$ is just $f$ with these two Fourier components removed. Removing an eigenspace is my slang for "restricting the operator to the orthogonal complement of that eigenspace". – fedja Nov 5 '11 at 12:15

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.