Minimal "sumset basis" in the discrete linear space $\mathbb F_2^n$

Question

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!

Answer 1

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.