Puzzle on deleting k bits from binary vectors of length 3k

Question

Consider all $2^n$ different binary vectors of length $n$ and assume $n$ is an integer multiple of $3$. You are allowed to delete exactly $n/3$ bits from each of the binary vectors, leaving vectors of length $2n/3$ remaining. The number of distinct vectors remaining depends on which bits you delete. Assuming your aim is to leave as few remaining different vectors as possible, how few can you leave as a function of $n$?

Example, $n=3$. You can leave only the two vectors $11$ and $00$.

Following comments at the math.se site (in particular by Jack D'Aurizio), in general for larger values of $n$ you can replace any block of three consecutive bits by either $00$ or $11$. This gives an upper bound of $2^{n/3}$. Is this in fact the correct answer?

Now I have some code to solve small instances, we can start to fill in a table of optimal results. We use the notation $H(n,b)$ to indicate the smallest number of distinct vectors that results from starting with all vectors of length $n$ and removing $b$ from each.

$$12 \leq H(15,5) \leq17$$

$$H(12,4) = 10$$

For $n=10$ and $b = 1,2,3,4$ we have $\leq140,\leq 31,10, 4$

For $n=9$ and $b = 1,2,3,4$ we have $70,18,6,2$

For $n=8$ and $b = 1,2,3$ we have $40,10,4$

For $n=7$ and $b = 1,2,3$ we have $20,6,2$

For $n=6$ and $b = 1,2$ we have $12,4$

For $n=5$ and $b = 1,2$ we have $6,2$

$$H(4,1) = 4, H(3,1) = 2, H(2,1) = 2$$

If we only allow symmetric solutions then $H(10,2)=32$. This implies (assumnig no error in the calculations) that for some instances there may be no symmetric optimal solutions as we already have $H(10,2) \leq 31$.

Answer 1

I can, at least, answer your question 'Is this in fact the correct answer?' with an affirmative 'no'.

Specifically, we can replace the upper bound $2^{n/3} \approxeq 1.26^n$ with the slightly better bound $6^{n/9} \approxeq 1.22^n$ by applying the same 'separate into independent blocks' construction to the following (conjecturally optimal) covering set for $n = 9$:

$$\{000000, 111111, 111000, 000111, 001100, 110011\}$$

Clearly, $2^{n/3}$ is still optimal for $n = 3$ and indeed (by exhaustive search) $n = 6$.

Answer 2

This is not an answer but rather a long comment. I give an informal argument that suggests what the right answer should be. The proof of the lower bound is rigorous, the proof of the upper bound is not.

Denote $k=n/3$. Let us say that a binary word $y\in\{0,1\}^{2k}$ covers a word $x\in \{0,1\}^n$ if $y$ can be obtained from $x$ by removing $k$ digits. Our goal is to find a set $S \subset \{0,1\}^{2k}$ of smallest possible cardinality that covers all words in $\{0,1\}^n$.

A lower bound on the size of $S$. We will show that every word $y$ covers approximately $2^{nH(1/3)}$ words in $\{0,1\}^n$. Therefore, the size of $|S|$ is at least $2^{n(1-H(1/3))}\approx 2^{0.08\, n}$. Here $H(t)$ is the entropy function $$H(t) = -t \log_2 t - (1-t) \log_2(1-t).$$

Let us fix $y$ and count the number of words $x$ that $y$ covers. To this end, we consider an algorithm that checks whether $y$ covers $x$. This is just a simple greedy algorithm that scans $x$ from left to right and finds indices $i_1 < \dots < i_{2k}$ s.t. $x_{i_r} = y_r$ for $r\in\{1,\dots, 2k\}$: $i_1$ is the first index s.t. $x_{i_1} = y_1$, $i_2$ is the first index after $i_1$ s.t. $x_{i_2} = y_2$ and so on. The algorithm terminates when it defines $i_{2r}$. The algorithm succeeds and finds $i_1< \dots < i_{2r} \leq n$ if and only if $y$ covers $x$.

Let $I_y(x) = \{i_1, \dots, i_{2k}\}$ for given words $x$ and $y$. Note that if $I_y(x') = I_y(x'')$ then the algorithm performs exactly the same steps. In particular, the first $i_{2r}$ digits in $x'$ and $x''$ are equal. Also for every set $I\subset \{1,\dots, n\}$ of size $2k$, there is a word $x$ s.t. $I_y(x) = I$.

Therefore, the number of words $x$ covered by $y$ is equal to sum over all possible values of $j\equiv i_{2r}$ the number of subsets of $\{1,\dots, j\}$ of size $2k$ times the number of possibilities for digits at positions $j+1,\dots, n$. $$\sum_{j=2k}^{n} \binom{j}{2k} 2^{n-j} \approx \sum_{j=2k}^{n} 2^{jH(2k/j)} 2^{n-j}\approx 2^n \sum_{j=2k}^n 2^{(\frac{j}{2k} (H(2k/j)-1))\cdot 2k} = 2^n \sum_{j=2k}^n 2^{f(2k/j)\cdot 2k}.$$ where $f(t) = (H(t)-1)/t$. The function $f(t)$ attains its maximum on $[2/3,1]$ when $t=2/3$. Thus the number of words covered by $y$ is approximately $$2^{n + 2 f(2/3)k} = 2^{nH(1/3)}.$$ We conclude that the set $S$ must contain at least $2^{n}/2^{H(1/3)n}\approx 2^{0.08\, n}$ words.

An upper bound on the optimal size of $S$. Note that this problem is a version of the set cover problem. Thus the size of the optimal set cover (optimal size of $S$) is within a log-factor of the size of the optimal fractional cover. (The log factor is $\log 2^{3n} = O(n)$). So it suffices to get an upper bound on the size of a fractional cover to get an approximate upper bound on the size the optimal set $S$.

Warning: This is not a proof! Some statements below are not correct!

Consider the bipartite graph with words $\{0,1\}^{2k}$ on the left, and words $\{0,1\}^{n}$ on the right, in which $y$ is connected to $x$ if $y$ covers $x$. The graph is “more or less bipartite”. To be precise, it is not regular but it is very close to a regular graph (this is an informal statement that needs justification!). We will pretend nevertheless that the graph is regular. The degree of each vertex on the left is approximately $2^{H(1/3)n}$ as we computed above. Thus we get a fractional cover when we take every string of length $2k$ with weight $2^n / (2^{2k} 2^{H(1/3)n})$. The total weight of all words in the fractional cover is $2^n / (2^{H(1/3)n}) \approx 2^{0.08\, n}$.

Answer: $\approx 2^{(1-H(1/3))n}\approx 2^{0.08n}$.

Answer 3

Here is an exponential lower bound. We begin by determining exactly how many strings $Y$ of length $n$ can be reduced to a given string $X=x_1x_2\cdots x_k$. In general $y$ might contain many copies of $X$, but it contains exactly one left-most copy of $X$; that is, the first $x_1$ then the first $x_2$ and so on. The strings with $X$ as a left-most substring form a regular language of simple form. For example, if $X=101$ then the language is $0^*1 \cdot 1^*0 \cdot 0^*1 \cdot (0+1)^*$. The generating function for $0^*1$ and $1^*0$ is $z/(1-z)$ while the generating function for $(0+1)^*$ is $1/(1-2z)$.

Therefore, the number of $Y$s that contain $X$ is independent of the structure of $X$ and is the coefficient of $z^n$ in $z^k (1-z)^{-k} (1-2z)^{-1}$, namely $$N(n,k) = \sum_{i=0}^{n-k} 2^i\binom{n-i-1}{k-1},$$ which I think doesn't have a closed form.

Therefore, a lower bound for the question is $2^n/N(n,k)$.

For $k=2n/3$, the largest term in the sum is the first one, and the following terms are close to a geometric progression with ratio $2/3$. This gives $$ N(n,2n/3) = (2 + O(1/n)) \binom{n}{2n/3},$$ giving a lower bound of $$ (1+o(1)) \frac{\sqrt{\pi n}}{3} \left(\frac{2^{5/3}}{3}\right)^n. $$ Note that $2^{5/3}/3\approx 1.05826737$.

I think it is most unlikely that this is best possible.

Answer 4

If a vector has $d$ one-entries, and $d\leq n/2$, then delete as many ones as you can, (and further zeros if necessary). Conversely, if a vector has more one entries than zero entries, delete as many zeros as you can, (and further ones if necessary).

Any remaining vector of the first type will have $\max(d-n/3,0)\leq n/6$ ones. The number of such vectors with exactly $n/6$ ones in $2n/3$ positions is $\binom{2n/3}{n/6}$. For the final sum, one needs to sum over bimomial coefficients $2 \sum_{i=0}^{n/6} \binom{2n/3}{i}$ and such a sum can be approximated: Note that the largest entry, with $d=n/6$ gives by far the greatest contribution. The binomial coefficient in this region can be approximated by $\binom{k}{l}=2^{k H(l/k)+o(k)}$, where $H$ denotes the entropy function $H(x)=\frac{-x \log x-(1-x)\log (1-x) }{\log 2}$, (for $x\in [0,1]$, and $\log $ is the natural logarithm).

Edit: In view of Yuri's comment, I correct this: (Thank you, Yuri!)

As $H(1/4)$ is about $0.811$, this is about $2^{2n/3 \times 0.811...+o(1)}=2^{0.54\ldots n}$.

This upper bound is certainly weaker than the bound $2^{n/3}$, but uses a quite different method. It would be interesting to see, whether the "optimum" uses a deterministic construction, or a random construction (like Shannon's bounds in coding theory), or a combination of methods.

Some explanation why the method above gives some saving over the trivial $2^{2n/3}$: most of the original vectors have about $n/2+ O(\sqrt{n})$ zero and one entries. Going away from this symmetric centre reduces (by the binomial distribution) the number of possibilities. In other words the tail of this distibution is small.

Answer 5

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 have $s(n_1)s(n_2)\ge s(n_1+n_2)$ so, by Fekete's Lemma there is a constant $\alpha=\inf {s(n)^{1/n}}$ such that $\lim {s(n)^{1/n}}=\alpha.$

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.

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 (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:

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 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.$

Answer 6

I think it may be helpful and/or intersting to consider the problem for fractions other than $1/3$.

Specifically, if $n$ is a multiple of $q$, let $f(p/q,n)$ be the minimal size of a set of $n- (p/q)n$ bit strings such that deleting $(p/q)n$ bits from each $n$-bit string produces an element of the set. Then set

$$g(p/q) = \lim _{n\to \infty} \frac{\log f\left(\frac{p}{q},n\right)}{n}$$

The limit exists because, by the divide-into-independent-blocks argument, any particular value is a bound for the $\lim\sup$.

It is clear that $g$ is monotonic. It's not immediately obvious to me if we can prove that $g$ is continuous.

Clearly $g(x)=0$ for $x \geq 1/2$.

For a simple upper bound on $g$ for $x<1/2$, we can assume with the loss only of a constant that there are fewer $0$s than $1$s. Then divide the $n$ bits into $q$ equally sized parts, and delete all the $0$s in the $2p$ parts with the fewest ones. This takes $2^{ (1-2p/q)n }$, giving an upper bound $g(x) \leq (1-2x) \log 2$.

Thanks to Brendan McKay and Yury, we have a lower bound on $g$. If I understand this bound correctly, it is that $g(x) \geq \log 2 + x \log x + (1-x) \log(1-x)$. (We can easily check that the maximal term in the $x=1/3$ case remains maximal for all $0<x<1/2$.)

Specific examples, like, Adam Goucher's, can give us tighter upper bounds for specific values of $x$.

Answer 7

This answer is an elaboration on the idea of Christian Elsholtz. Like that answer, this answer does not beat $2^{n/3}$.

As noted by Christian, by symmetry it suffices to deal with vectors that contain at most $n/2$ ones. By left-right symmetry, it suffices to deal with vectors of at most $n/4$ ones among the first $n/2$ positions. Remove the first $n/3$ ones. That leaves a vector of length $2n/3$ with at most $n/6$ ones that starts with a string of $n/4$ zeros. There are approximately $\binom{2n/3-n/4}{n/6}\approx 2^{5n/12\times H(2/5)}=2^{0.40455n}$, which is still worse than $2^{n/3}$.

One can improve this a bit. Namely, after deleting all the ones from the first half of string, we choose whether to remove ones from third or four quarter. It appears that in the worse case (non-rigorously!) we end up with a string of length $2n/3$ that contains $n/6$ ones among which $n/24$ are in the third quarter and $n/8$ are in the fourth quarter. There are approximately $\binom{n/6}{n/24}\binom{n/4}{n/8}\approx 2^{0.385n}$ of them.

Answer 8

For each $\ n=9\cdot m + 3\cdot k\ $ one gets a bound of $\ 6^m\cdot 2^k\ =\ 6^{\frac n9}\cdot 2^k\ $ for every $\ m=0\ 1\ \ldots\ $ and $\ k\in\{0\ 1\ 2\}$.

A hand justification below of the result by @Adam P. Goucher (and a computer) indicates a further possible progress along a similar line. I'll explicitly associate binary sequences of length $\ 9\ $ with the respective Goucher's sequences.

I'll provide a simpler derivation below, and will leave the previous one at the bottom.

---

Let $\ b_0\ldots b_8\ $ be a bit string.

Case A:   Let $\ b_0b_1b_2b_3\ $ have (at least) three same bits, say $\ x$.   Then $\ b_4b_5b_6b_7b_8\ $ bits contain (at least) three bits say $\ y$ (the majority of five),   where values $\ x\ y\ $ are different or the same. In either case by leaving the two groups of three bits we get one of the four strings of length 6:

$$ 000000\quad 000111\quad 111000\quad 111111$$

Case A':   Consider $\ b_5b_6b_7b_8\ $ -- everything is symmetric.

From now on let's assume that the distribution of bits in $\ b_0b_1b_2b_3\ $ is two bits of each, and the same for $\ b_5b_6b_7b_8$.

Case B:   $b_3=b_5$,   and say $\ b_3=b_5=x$.   Then remove one of bits of value $\ 1-x\ $ from $\ b_0b_1b_2\ $ and from $\ b_6b_7b_8\ $ and remove also bit $\ b_4$.   We are left with one of the strings:

$$ 001100\qquad 110011$$

Case C:   $b_3=b_4\ne b_5$,   and say $\ b_3=x$.   Then remove the one bit of value $\ x\ $ from $\ b_0b_1b_2$,   and the two more bits $\ x\ $ from $\ b_6b_7b_8$.   We are left with one of the two 6-strings as the above.

Case C':   $b_3\ne b_4= b_5$ -- symmetry.

END of PROOF

---

(Back to the old argument)

Let's refer to the six Goucher's sequences as of the type $\ 6\ \ 3\!+\!3\ \ 2\!+\!2\!+\!2$,   where each type addresses the consecutive two sequences by Goucher.

Case 1: one of the bit values of a binary sequence $\ b_0\ldots b_8\ $ occurs at least $\ 6\ $ times. Then we may leave a six of them to produce a 6-sequence of type $\ 6$.   Now we may restrict ourselves to the cases when each bit value of a 9-sequence $\ b_0\ldots b_8\ $ occurs $\ 4\ $ or $\ 5\ $ times.

Let the bit value $\ x\ $ be the value of the majority of $\ b_6b_7b_8$,   and $\ y\ $ be the value of the majority of $\ b_0b_1b_2$. (Values $ x\ y\ $ can be equal or different).

Case 2:   $b_6=b_7=b_8=x\ $ or $\ b_0=b_1=b_2=y$. It's enough to consider just the earlier option, about $\ x$.   Then there are three bits among $\ b_0\ldots b_5\ $ which have the same value.   These three bits together with $\ b_6b_7b_8\ $ form a 6-sequence of type $\ 6\ $ or $\ 3+3$. The latter option, about $\ y$,   is proved similarly.

Now we may assume that exactly two bits of $\ b_6b_7b_8\ $ have value $\ x$,   and exactly two of $\ b_0b_1b_2\ $ have value $\ y$.

Case 3:   $x=y$.   Then if at least $\ 2\ $ of the bits of $\ b_3b_4b_5\ $ have value $\ x\ $ then we leave these two $x$-bits together with two of the $x$-bits of $\ b_0b_1b_2\ $ and another two $x$-bits of $\ b_6b_7b_8\ $ to produce a 6-sequence of type $\ 6$.   Otherwise two bits of $\ b_3b_4b_5\ $ are different from $\ x=y$.   Then two (middle) non-x bits together with the 2+2 bits from $\ b_0b_1b_2\ $ and $\ b_6b_7b_8\ $ form a 6-sequence of type $\ 2+2+2$.

Case 4:   $x\ne y$.   The three bits $\ b_3b_4b_5\ $ cannot have the same value or else there would be $\ 6\ $ bits of the same value in the whole 9-sequence. Next, if there are integers $\ r\ s\ $ such that $\ 3\le r<s\le 5\ $ and $\ b_r=y\ $ and $\ b_s=x\ $ then we would get a 6-sequence of type $\ 3+3$.   Otherwise $\ b_3=x\ $ and $\ b_5=y$. Let's assume that $\ b_4=x\ $ (the case $\ b_4=y\ $ is symmetric). The the two of $y$-bits of $\ b_0b_1b_2\ $ together with $\ b_3b_4b_5\ $ and the single $y$-bit of $\ b_6b_7b_8\ $ form a 6-sequence of type $\ 2+2+2$.

END of PROOF