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?

  • 11
    $\begingroup$ 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$. $\endgroup$ – 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.

| cite | improve this answer | |
  • 5
    $\begingroup$ 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. $\endgroup$ – Lucia 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$.

| cite | improve this answer | |
  • $\begingroup$ This construction doubles as a proof of optimality, at least for $|S|=1$. $\endgroup$ – Will Sawin May 3 '14 at 20:51
  • $\begingroup$ @Will Sawin: do not get it; could you expand? $\endgroup$ – Seva May 4 '14 at 6:16
  • $\begingroup$ 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$. $\endgroup$ – Will Sawin May 4 '14 at 21:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.