For a set $C\subseteq \mathbb F\_2^n$, let $2C=C+C:=\{\alpha+\beta\colon \alpha,\beta\in C\}$.
I want to find $C$ of the smallest possible size such that $2C=\mathbb F\_2^n$. Let $m(n)$ be the size of a minimal $C$. I have found the following bounds:
 $$m(n) \ge B(n):=\frac{1+\sqrt{2^{n+3}-7}}{2} $$
and
 $$ m(n) \le A(n) := \left\{\begin{array}{ll} 2^{\frac{n+2}{2}}-2 & {\rm if}\, n\ge4\,{\rm is}\, {\rm even},\\
2^{\frac{n+1}{2}}+2^{\frac{n-1}{2}}-2 & {\rm if}\, n\ge5\,{\rm is}\, {\rm odd}.
\end{array}\right. $$


It is easy to see that $$\lim\_{n\rightarrow\infty}{\frac{A(2n)}{B(2n)}=\sqrt{2}},\quad\lim\_{n\rightarrow\infty}{\frac{A(2n+1)}{B(2n+1)}}=\frac{3}{2}.$$The last equations show that there might be some improvements for lower or/and upper bounds. 


Also I have found the following results if it can help:$$m(1)=1,m(2)=3,m(3)=5,m(4)=6,m(5)=10,m(6)\in\{12,13,14\}.$$


With great probability $m(6)=14$ (actually I am using randomized algorithm to find possible solutions and it didn't find better results for $n=6$ than 14)․ This
sequence could be either <https://oeis.org/A099190> or <https://oeis.org/A176747>. But unfortunately both are excluded, because for $n=7$ they can't match with it. Also I would like to mention that upper bounds are not the best. For example for $n=7$ computer found $C$ such that $|C|=20$. Also better results were found for $n=8,9,10$.


Actually this problem is related with my thesis and I understand that I should do it myself but I have been thinking about it for about two months and I can't find any clever method to get better bounds. Any hints and suggestions would be very appreciated.


Thanks!



Minimal "sumset basis" in the discrete linear space $\mathbb F_2^n$
This is an open problem well known in coding theory. 


Let $m:=|C|$, and write the vectors of your set $C$ as columns of a matrix, say $M\_C$. Your condition $C+C={\mathbb F}\_2^n$ translates as follows: for any non-zero vector $z\in{\mathbb F}\_2^n$, there exists a vector $x\in{\mathbb F}\_2^m$ of weight $|x|=2$ such that $M\_Cx=z$. As a result, the (linear) code $K\_C$ with the parity check matrix $M\_C$ (that is, $K\_C:=\ker M\_C<{\mathbb F}\_2^m$) has covering radius $2$: for any given $y\in{\mathbb F}\_2^m$, either $y\in K\_C$, or one can find $x\in{\mathbb F}\_2^m$ with $|x|=2$ and $M\_Cx=M\_Cy$, and then $M\_C(x+y)=0$, showing that $y$ differs from $x+y\in K\_C$ in exactly two coordinates. It is also easy to see that the rows of $M\_C$ must be linearly independent, so that $K\_C$ has co-dimension $m$.


This argument is reversible and it shows that the quantity you are interested in is the smallest possible length of a (linear) code with covering radius $2$ and co-dimension $m$. Denote it by $\ell(m)$. Here is a selection of bounds that can be found in *Covering Codes* by Cohen, Honkala, Litsyn, and Lobstein (Elsevier 1997):


* $\ell(2m)\le 27\cdot 2^{m-4}-1$ for $m\ge 4$ (Theorem 5.4.27);
* $\ell(2m+1)\le 5\cdot2^{m-1}-1$ for $m\ge 1$ (Theorem 5.4.27);
* $\ell(2m+1) \ge 2^{m+1}+1$ for $m\ge 2$ (Theorem 7.2.16).


I am not sure whether any of these estimates have been improved over the last two decades, and also whether any non-trivial lower bound for $\ell(2m)$ is known.


