Repeats of all binary strings of length k

The question seems like it should be known, but I was not able to find it anywhere.

How many binary strings of length $n$ are required so that for every $k$ positions in these strings, all $2^k$ possible subsequences occur?

For example, suppose $n=3$, and $k=2$. We want a set of binary strings of length $3$ so that if you look at the first and third symbols (or first two, or last two), you will see all $4$ patterns $00$, $01$, $10$, and $11$. For example, the strings with an even number of $1$s $\{ 000, 011, 110, 101\}$ induce all subsequences on each set of two positions.

Let $f(n,k)$ be the minimum number. Trivially, $f(n,k) \ge 2^k$ so $f(3,2)=4$.

I am interested in precise upper and lower bounds for $f(n,k)$. Bounds that are within a constant of each other (independent of $n$ and $k$) suffice for my purposes.

• The quantifiers are not clear to me. – Anthony Quas Aug 31 '15 at 21:01
• consider m strings of length n of zeros and ones. Say we arrange them in m rows. Resulting in an $m\times n$ matrix. The question is what is the minimum m so that for every k columns all possible 2^k binary combinations appear in the rows. I am interested in results of the form $f(n,k)\le m \le c f(n,k)$ with c a fixed numerical constant independent of n and k. For example obviously m must be bigger than $2^k$ – Anahita Aug 31 '15 at 21:03
• You are supposed to be able to pick any k columns; not just adjacent columns? – Anthony Quas Aug 31 '15 at 23:40
• I also don't exactly understand what you want, but probably this might help. link – Dongryul Kim Aug 31 '15 at 23:54
• Can you edit your question to clarify it? It should be understandable for readers who do not look at the comments. – Joonas Ilmavirta Sep 1 '15 at 12:01

Orthogonal arrays were mentioned in another answer, but you are not requiring that each $k$-tuple occurs exactly once in every set of $k$ columns, but rather that each $k$-tuple occurs at least once in every set of $k$ columns.

What you are looking for is called a covering array. In the usual notation for covering and orthogonal arrays, $v$ is the size of the alphabet ($2$ in this case), $k$ corresponds to your $n$, and $t$ corresponds to your $k$. Some known upper bounds for the number of rows for small values of $t,k,v$ are listed in http://www.public.asu.edu/~ccolbou/src/tabby/catable.html - you are interested in the numbers for $(t,k,2)$.

Definition: A $t-(v,k,\lambda)$ orthogonal array ($t \leq k$) (also called an orthogonal array of power/strength $t$) is a $λv^t × k$ array whose entries are chosen from a set $X$ with $v$ points such that in every subset of $t$ columns of the array, every $t-$tuple of points of $X$ appears in exactly $λ$ rows. I have used the standard notation for letters.

It seems to me the OP is looking for orthogonal arrays with minimal number of rows over the set $X=\{0,1\}$ with $k=n,\lambda=1,$ and $t=k$ because he wants every $k-$tuple to occur in every possible $k$ positions.

There are literally hundreds of papers and tens of constructions in this area. There are some lower bounds known for existence. I suggest he start with reading the Wikipedia entry and then moving on to tutorial papers of which there are plenty. Happy googling!

• Also, orthogonal arrays for $\lambda=1$, $v=2$ exist only when $k=t$, $k=t+1$ or $t=1$. – Janne Kokkala Sep 1 '15 at 11:59
• Sorry, fixed. You're right in OA notation his $n$ (length of sequence) is their $k.$ I wasn't aware of the existence restraint you stated. – kodlu Sep 1 '15 at 22:21
• Thanks these are great refs. It seems though orthogonal array means every combination appears exactly once. Is there some thing more specific if we want at least once? – Anahita Sep 4 '15 at 18:16
• @Anahita, you can choose $\lambda\geq 1$ and have everything appear at exactly $\lambda$ times. The other answer is more directly relevant to what you asked. On the other hand, I am unsure if any infinite families of covering arrays are known. – kodlu Sep 5 '15 at 2:02