# Large sets $X \subseteq \mathbb{Z}_2^n$ with $X+X \ne \mathbb{Z}_2^n$

I've come across a seemingly natural question in additive combinatorics to which I can't find the answer in the literature. I would like to know if, given an $\alpha > 0$ and large $n$, there are interesting examples of sets $X \subseteq \mathbb{Z}_2^n$ such that $|X| \ge \alpha 2^n$ and $X + X \ne \mathbb{Z_2}^n$.

There are certainly uninteresting examples: say, the set of points in some suitably large proper subspace of $\mathbb{Z_2}^n$, or some union of cosets of such a subspace, etc etc. I would like to know if there are examples that do not have an obvious linear-algebraic structure of this sort. specifically, are there examples that are 'pseudorandom', say such that every codimension-1 subspace contains roughly $|X|/2$ elements of $X$?

In the language of additive theory, we know that $X$ has 'doubling constant' $\frac{|X+X|}{|X|} < \alpha^{-1}$, and there are many results in additive theory describing sets with small doubling constant. However, the same inequality also holds for an arbitrary set strictly larger than $X$, so no result on doubling constant alone will give sensible structure. Is there a well-known theorem or observation somewhere that I'm missing?

• How about fixing a non-zero element $g\in{\mathbb Z}_2^n$ and flipping a coin for each pair of elements that add up to $g$ to choose one for your set $X$? You will get a set of density $\alpha=1/2$ with $g\notin 2X$, and this set will typically be uniformly distributed in subspaces of co-dimension $1$.
– Seva
May 1 '14 at 14:39

Niveau sets fit your description: Theorem 9.4 in http://arxiv.org/abs/math/0409420 is a construction of a set $X\subseteq \mathbb Z_2^n$ having |X| approximately $\frac{1}{4}2^n$ and $X+X$ does not contain a subspace of dimension $n-\sqrt{n}$. The construction is easily adapted to show that for a given $\alpha<1/2$ and $d\in \mathbb N$ there is an $n$ and an $X\subset \mathbb Z_2^n$ having $|X|\geq \alpha 2^n$ such that $X+X$ does not contain a subspace of codimension $d$. Sanders has some sharper results in http://arxiv.org/abs/1003.5649

Your remark about pseudorandomness is apt: EVERY set $X$ of density sufficiently close to 1/2 such that $X+X$ does not contain a coset of a codimension 1 subspace must be pseudorandom, since the density of $X$ on a given codimension 1 subspace cannot exceed 1/2.

• For those in a hurry: A `niveau' set $X \in {\Bbb Z}_2^n$ has about $n/2+\sqrt{n}$ (say) of its coordinates being $1$. Then adding two such elements always produces an element having at least $2\sqrt{n}$ zeros, and so $X+X$ misses a lot of elements. May 1 '14 at 23:20

As a slight extension of my comment, one can fix a (very) small subset $S\subset{\mathbb Z}_2^n$, and consider the addition Cayley graph, say $\Gamma$, induced by $S$ on ${\mathbb Z}_2^n$. (The vertices of $\Gamma$ are the elements of ${\mathbb Z}_2^n$, with two vertices adjacent whenever their sum is in $S$.) Now form an independent set $X\subset {\mathbb Z}_2^n$ by choosing at random, for every edge of $\Gamma$, one of the two vertices incident with this edge, and deleting this vertex from ${\mathbb Z}_2^n$. By the construction, we have $2X\subseteq{\mathbb Z}_2^n\setminus S$; furthermore, the expected density of $X$ is $2^{-|S|}$ and, typically, $X$ will be very uniformly distributed in ${\mathbb Z}_2^n$.

• This construction doubles as a proof of optimality, at least for $|S|=1$. May 3 '14 at 20:51
• @Will Sawin: do not get it; could you expand?
– Seva
May 4 '14 at 6:16
• Your reduction to finding an independent set in some graph is an equivalence - a set satisfies $(X+X ) \cap S = \emptyset$ if and only if it is an independent set in your graph. So the optimal solution is the maximum independent set. If $|S|=1$, your graph is a union of disjoint edges, so a set is maximal independent if and only if it comes from your construction. Because the size of this set does not depend on $S$ as long as $|S|=1$, this is also the best possible among all sets with $X+X \neq (\mathbb Z/2)^n$. May 4 '14 at 21:39