# Generating sets of all binary strings of a fixed size

Consider the set $\Sigma^n$ of all binary strings of length $n$.

Consider some set $S_k \subseteq \Sigma^k$ of binary strings of length $k$. We call $S_k$ a `generating set' of $\Sigma^n$ if for any string $s \in \Sigma^n$, there exists a string $s' \in S_k$ such that $s'$ is a (not necessarily contiguous) substring of $s$. For example, the set $\Sigma^3 = \{111, 110, 101, 100, 011, 010, 001, 000 \}$ has a generating set $S_2 = \{11, 00\}$.

What is the smallest possible set $S_{n-1}$ that generates $\Sigma^n$?

• This was already asked either here or at cstheory, sorry, but I don't remember more details. – domotorp Nov 23 '13 at 19:30
• A simple lower bound is 2^n/2n . As any two basis elements which have their numbers of 0 bits differ by 2 will generate disjoint sets (and one can easily generalize this condition), I expect ceiling of the lower bound to be acheivable for almost all n. (Actually, the bound can be improved to have the denominator be cn for some c not far from 1. That is the bound to target.) – The Masked Avenger Nov 23 '13 at 21:30