Return to Answer

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 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. On the other hand, 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 $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}$.

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

This is not an answer but rather a long comment. I give an informal argument that suggests what the right answer should be.

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

We can check whether $y$ covers $x$ by running a 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\}$. For every $y$, the probability over $x$ that the algorithm finds a given set of indices $I=\{i_1,\dots, i_{2k}\}$ is $1/2^{i_{2k}}$. W.h.p. $i_{2k}\approx n$ and the number of subsets $I$ is approximately $\binom{3k}{2k} \approx 2^{H(1/3)n}$. Thus every $y$ covers approximately $2^{H(1/3)n}$ words. 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 $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}$.

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 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. On the other hand, 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 $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}$.

This is not an answer but rather a long comment. I give an informal argument that suggests what the right answer should be.

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

We can check whether $y$ covers $x$ by running a 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\}$. The probability (over $x$) that the algorithm finds a given set of indices $I=\{i_1,\dots, i_{2k}\}$ is $1/2^{i_{2k}}$. W.h.p. $i_{2k}\approx n$ and the number of subsets $I$ is approximately $\binom{3k}{2k} \approx 2^{H(1/3)n}$. Thus every $y$ covers approximately $2^{H(1/3)n}$ words. 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 $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}$.

This is not an answer but rather a long comment. I give an informal argument that suggests what the right answer should be.

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

We can check whether $y$ covers $x$ by running a 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\}$. For every $y$, the probability over $x$ that the algorithm finds a given set of indices $I=\{i_1,\dots, i_{2k}\}$ is $1/2^{i_{2k}}$. W.h.p. $i_{2k}\approx n$ and the number of subsets $I$ is approximately $\binom{3k}{2k} \approx 2^{H(1/3)n}$. Thus every $y$ covers approximately $2^{H(1/3)n}$ words. 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 $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}$.