14
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ You might analyze further (for small n) what prevents B(n) from being the bound, and seeing if such an obstacle scales. Then you might get a tighter result. $\endgroup$ – The Masked Avenger Dec 3 '14 at 18:44
  • 1
    $\begingroup$ I don't know what $\oplus$ means. $\endgroup$ – Gerry Myerson Dec 3 '14 at 22:41
  • 1
    $\begingroup$ $\bar\alpha \oplus \bar\beta=(\alpha_1+\beta_1,\ldots ,\alpha_n+\beta_n)(\mod2)$ $\endgroup$ – pointer Dec 3 '14 at 22:48
  • 2
    $\begingroup$ Can you find the minimum of $|C|$ for a few small values of $n$, and then consult the Online Encyclopedia of Integer Sequences? Also, it seems to me that when $n=3$ your formulas give $|C|\le A(3)=4<B(3)\le|C|$, contradiction. $\endgroup$ – Gerry Myerson Dec 4 '14 at 1:47
  • 3
    $\begingroup$ Nice question. Let me rephrase it: You want to find the asymptotic exponent of the minimal set system $C$ on an $n$ element set, such that every subset of $[n]$ is the symmetric difference of two sets from $C$. $\endgroup$ – Daniel Soltész Dec 6 '14 at 17:16
7
+150
$\begingroup$

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.

$\endgroup$

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.