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

Question

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?

Answer 1

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.

Answer 2

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