Return to Answer

There is, for $n=3k$, a smallest size $s(n)$ for a set $S$ of strings in $ \{0,1\}^{2k}$ which covers all the strings in $\{0,1\}^n$.

We so far have from the various answers that $1.058 \lt \alpha \lt 6^{1/9}\approx 1.22.$

I thought I had shown $s(12) \le 8$ which would improve the upper bound to $8^{1/12}=2^{1/4}\approx 1.1892$ Then I didn't think so, then I did again and now I don't. At any rate it is close which leaves me optimistic that $10$ would suffice but too discouraged to fully check it. That would make the upper bound $10^{1/12}\approx 1.2115$

To improve on those upper bounds we would need $s(15)\le 13$ or $s(15) \le 16$ (I'd bet on $12$ or $16$, if anything, just because it seems nicer) Taking into account that we must have $0^{10},1^{10}$ (in an obvious notation) and adding the optimistic condition that the set of strings is closed under complements and reversing the order, it might be possible to investigate this by somewhat intelligent brute force. An even more optimistic condition would be that each string of length $2k=10$ is either unchanged or replaced by its complement when reversed. Finally one could add the restriction that each of the non-constant words has five $0$'s and five $1$'s. I can think of some obvious further strings to include but that still leaves much to do.

For $n=12$ the eight strings below ( Walsh sequences ) are (nearly) enough $$00000000,00001111,00110011,00111100$$$$11111111,11110000,11001100,11000011.$$ Here is a sketch:

It remains to consider the case of $7$ $1$'s and $5$ $0$'s with at least $4$ of the $1$'s on the left side. We must delete a single $0$ and three $1$'s. Again, if there are $5$ or $6$ $1$'s on the left side then we can get $11110000$. All that is left is the subcase with $4$ $1$'s on the left. If the left side is $abcde0$ then we can delete the single $0$ among $abcde$ and continue to get $11110000.$ If the left side is $abcd11$ then we can delete the two $1$'s among $abcd$ to get $0011$. So now we have the subsubcase that the left side is $abcd01$ and the right side has $3$ $0$'s and $3$ $1$'s. The four possibilities on the left include $111001$,$110101$ (both of these can be reduced to $1100$ with two deletions). Finally we get the case that the left side is $101101$ or $011101$ and there are three $1$'s on the right side. In some cases we are still covered but $101101010101$ (for example) seems hopeless. Perhaps a couple more words (or a slightly different set of eight) would suffice.

For $n=12$ it is possible to use $10$ strings of length $2k=8.$

There is, for $n=3k$, a smallest size $s(n)$ for a set $S$ of strings in $ \{0,1\}^{2k}$ which covers all the strings in $\{0,1\}^n$.

We so far have from the various answers that $$1.05827 \lt \alpha \lt 6^{1/9}\approx 1.2203.$$

I show below that $s(12) \le 10$ which improves the upper bound to $10^{1/12}\approx 1.2115.$

To improve on this upper bound we would need $s(15) \le 17$ (I'd bet on $16$, if anything, just because it seems nicer.) Taking into account that we must have $0^{10},1^{10}$ (in an obvious notation) and adding the optimistic condition that the set of strings is closed under complements and reversing the order, it might be possible to investigate this by somewhat intelligent brute force. An even more optimistic condition would be that each string of length $2k=10$ is either unchanged or replaced by its complement when reversed. Finally one could add the restriction that each of the non-constant words has five $0$'s and five $1$'s. I can think of some obvious further strings to include but that still leaves much to do.

For $n=12$ the eight strings below ( Walsh sequences ) are (nearly) enough $$00000000,00001111,00110011,00111100$$$$11111111,11110000,11001100,11000011.$$ They are enough with the addition of the two strings $$11101000,00010111$$ Here is a sketch where we avoid using the final two strings as long as possible:

It remains to consider the case of $7$ $1$'s and $5$ $0$'s with at least $4$ of the $1$'s on the left side. We must delete a single $0$ and three $1$'s. Again, if there are $5$ or $6$ $1$'s on the left side then we can get $11110000$. All that is left is the subcase with $4$ $1$'s on the left. If the left side is $abcde0$ then we can delete the single $0$ among $abcde$ and continue to get $11110000.$ If the left side is $abcd11$ then we can delete the two $1$'s among $abcd$ to get $0011$. So now we have the subsubcase that the left side is $abcd01$ and the right side has $3$ $0$'s and $3$ $1$'s. The four possibilities on the left include $111001$,$110101$ (both of these can be reduced to $1100$ with two deletions). Finally we get the case that the left side is $101101$ or $011101$ and there are three $1$'s on the right side. In some cases we are still covered but $101101\ 010101$ (for example) seems hopeless. However for all $30$ of the length 12 strings left uncovered we can delete the first $0$ from the left half and all three $1$'s from the right to get $1110101000.$

I show below that $s(12) \le 8$ which improves the upper bound to $8^{1/12}=2^{1/4}\approx 1.1892$

To improve on that upper bound we would need $s(15)\le 13$ (I'd bet on $12$ just because it seems nicer). Taking into account that we must have $0^{10},1^{10}$ (in an obvious notation) and adding the optimistic condition that the set of strings is closed under complements and reversing the order, it might be possible to investigate this by somewhat intelligent brute force. An even more optimistic condition would be that each string of length $2k=10$ is either unchanged or replaced by its complement when reversed. Finally one could add the restriction that each of the non-constant words has five $0$'s and five $1$'s. I can think of some obvious further strings to include but that still leaves much to do.

For $n=12$ the eight strings below ( Walsh sequences ) are enough $$00000000,00001111,00110011,00111100$$$$11111111,11110000,11001100,11000011.$$ Here is a sketch:

It remains to consider the case of $7$ $1$'s and $5$ $0$'s with at least $4$ of the $1$'s on the left side. We must delete a single $0$ and three $1$'s. Again, if there are $5$ or $6$ $1$'s on the left side then we can get $11110000$. All that is left is the subcase with $4$ $1$'s on the left. If the left side is $abcde0$ then we can delete the single $0$ among $abcde$ and continue to get $11110000.$ If the left side is $abcd11$ then we can delete the two $1$'s among $abcd$ to get $0011$. So now we have the subsubcase that the left side is $abcd01$ and the right side has $3$ $0$'s and $3$ $1$'s. The four possibilities on the left include $111001$,$110101$ (both of these can be reduced to $1100$ with two deletions). Finally, if the left side is $1011101$ or $0111101$ then we can delete a $0$ and a $1$ to get $11110$ and the the three $1$'s on the right are deleted leaving $11110000.$

I thought I had shown $s(12) \le 8$ which would improve the upper bound to $8^{1/12}=2^{1/4}\approx 1.1892$ Then I didn't think so, then I did again and now I don't. At any rate it is close which leaves me optimistic that $10$ would suffice but too discouraged to fully check it. That would make the upper bound $10^{1/12}\approx 1.2115$

To improve on those upper bounds we would need $s(15)\le 13$ or $s(15) \le 16$ (I'd bet on $12$ or $16$, if anything, just because it seems nicer) Taking into account that we must have $0^{10},1^{10}$ (in an obvious notation) and adding the optimistic condition that the set of strings is closed under complements and reversing the order, it might be possible to investigate this by somewhat intelligent brute force. An even more optimistic condition would be that each string of length $2k=10$ is either unchanged or replaced by its complement when reversed. Finally one could add the restriction that each of the non-constant words has five $0$'s and five $1$'s. I can think of some obvious further strings to include but that still leaves much to do.

For $n=12$ the eight strings below ( Walsh sequences ) are (nearly) enough $$00000000,00001111,00110011,00111100$$$$11111111,11110000,11001100,11000011.$$ Here is a sketch:

It remains to consider the case of $7$ $1$'s and $5$ $0$'s with at least $4$ of the $1$'s on the left side. We must delete a single $0$ and three $1$'s. Again, if there are $5$ or $6$ $1$'s on the left side then we can get $11110000$. All that is left is the subcase with $4$ $1$'s on the left. If the left side is $abcde0$ then we can delete the single $0$ among $abcde$ and continue to get $11110000.$ If the left side is $abcd11$ then we can delete the two $1$'s among $abcd$ to get $0011$. So now we have the subsubcase that the left side is $abcd01$ and the right side has $3$ $0$'s and $3$ $1$'s. The four possibilities on the left include $111001$,$110101$ (both of these can be reduced to $1100$ with two deletions). Finally we get the case that the left side is $101101$ or $011101$ and there are three $1$'s on the right side. In some cases we are still covered but $101101010101$ (for example) seems hopeless. Perhaps a couple more words (or a slightly different set of eight) would suffice.

I think I can show that $s(12)=8$ which improves the upper bound to $8^{1/12}=2^{1/4}\approx 1.1892$

To improve on that upper bound we would need $s(15)\le 13$ (I'd bet on $12$ just because it seems nicer). Taking into account that we must have $0^{12},1^{12}$ (in an obvious notation) and adding the optimistic condition that the set of strings is closed under complements and reversing the order, it might be possible to investigate this by somewhat intelligent brute force. An even more optimistic condition would be that each string of length $2k=12$ is either unchanged or replaced by its complement when reversed. Finally one could add the restriction that each of the non-constant words has six $0$'s and six $1$'s

A larger lower bound might (or might not) arise from considering how much overlap there has to be for various "radius $k$" balls. For example each of the six members from the set for $s(9)=6$ covers $130$ of the $512$ strings in $\{0,1\}^{9}$ so on average each string is covered a little over $1.5$ times. Some just once and others, such as $111000111$ as many as three times.

For $n=12$ the eight strings I propose to use are the Walsh sequences $$00000000,00001111,00110011,00111100$$$$11111111,11110000,11001100,11000011.$$ I think I verified this, but will check it.

In general one might reasonably hope to have a covering set where every non-constant string has $k$ $0$'s and hence $k$ $1$'s.

I show below that $s(12) \le 8$ which improves the upper bound to $8^{1/12}=2^{1/4}\approx 1.1892$

To improve on that upper bound we would need $s(15)\le 13$ (I'd bet on $12$ just because it seems nicer). Taking into account that we must have $0^{10},1^{10}$ (in an obvious notation) and adding the optimistic condition that the set of strings is closed under complements and reversing the order, it might be possible to investigate this by somewhat intelligent brute force. An even more optimistic condition would be that each string of length $2k=10$ is either unchanged or replaced by its complement when reversed. Finally one could add the restriction that each of the non-constant words has five $0$'s and five $1$'s. I can think of some obvious further strings to include but that still leaves much to do.

A larger lower bound might (or might not) arise from considering how much overlap there has to be for various "radius $k$" balls. For example each of the six members from the set for $s(9)=6$ covers $130$ of the $512$ strings in $\{0,1\}^{9}$ so on average each string is covered a little over $1.5$ times. Some just once and others, such as $111000111$ as many as three times.

In general one might reasonably hope to have a covering set where every non-constant string has $k$ $0$'s and hence $k$ $1$'s. This has the advantage that one knows for any particular word how many $1$'s and $0$'s must be deleted.

For $n=12$ the eight strings below ( Walsh sequences ) are enough $$00000000,00001111,00110011,00111100$$$$11111111,11110000,11001100,11000011.$$ Here is a sketch:

Thanks to the two constant strings we need only consider length $12$ strings with $5,6$ or $7$ $1$'s. By symmetry and complements we can restrict to either $6$ or $7$ $1$'s with at least as many among the first $6$ locations as the last $6$. Observe that any length $6$ string with $3$ $1$'s can be reduced to $0011$ or $1100$ with two deletions.

Consider first the case of $6$ $1$'s. If $3$ are in the left half (and $3$ on the right) then the previous observation shows that we can get one of the four strings which are not constant on either half. If $5$ or $6$ are on the left then we can get $11110000$.

It remains to consider the case of $7$ $1$'s and $5$ $0$'s with at least $4$ of the $1$'s on the left side. We must delete a single $0$ and three $1$'s. Again, if there are $5$ or $6$ $1$'s on the left side then we can get $11110000$. All that is left is the subcase with $4$ $1$'s on the left. If the left side is $abcde0$ then we can delete the single $0$ among $abcde$ and continue to get $11110000.$ If the left side is $abcd11$ then we can delete the two $1$'s among $abcd$ to get $0011$. So now we have the subsubcase that the left side is $abcd01$ and the right side has $3$ $0$'s and $3$ $1$'s. The four possibilities on the left include $111001$,$110101$ (both of these can be reduced to $1100$ with two deletions). Finally, if the left side is $1011101$ or $0111101$ then we can delete a $0$ and a $1$ to get $11110$ and the the three $1$'s on the right are deleted leaving $11110000.$