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!

15more comments