# Maximal number of binary strings given constraints

Let $k, N, m \in \mathbb{N}$ such that $k \leq N$.

What is the maximal number $e$ of strings $\sigma_1, \sigma_i, \dots, \sigma_e$, each of length $N$ such that $$\forall j < k, \left(\sum_{i=1}^e \sigma_i[j]\right) \leq 2^{N-k}(m-1)$$

For example if $m=3$, $k=4$, $N=5$, we have $e = 14$. An example of such a set is $$\begin{array}{cc} \sigma_1 & \underbrace{\overbrace{0000}^{k}0}_{N}\\\\ \sigma_2 & 00001\\\\ \sigma_3 & 10000\\\\ \sigma_4 & 10001\\\\ \sigma_5 & 01000\\\\ \sigma_6 & 01001\\\\ \sigma_7 & 00100\\\\ \end{array} \hspace{20pt} \begin{array}{cc} \sigma_8 & 00101\\\\ \sigma_9 & 00010\\\\ \sigma_{10} & 00011\\\\ \sigma_{11} & 11000\\\\ \sigma_{12} & 11001\\\\ \sigma_{13} & 00110\\\\ \sigma_{14} & 00111\\\\ \end{array}$$

By a few trials, it seems that the following holds

• If $k \leq m$ then $e = 2^{N-k} + 2^{N-m}k$
• If $k \geq m$ then $e = 2^{N-k} + 2^{N-m}m$

Has this problem been already studied ?

My intuition is that the following exchange lemma holds:

Let $S$ be a set of strings verifying previous properties. Then there exists a set $S'$ of same cardinality such that if $\sigma \in S'$ has $n$ bits at 1 at the $k$'s first positions, then all strings having strictly less than $n$ bits at 1 at the $k$'s first positions are in $S'$.

But I don't know how to prove this.

• Is there no constraint on the last $N-k$ values of the strings? – Douglas Zare Jul 28 '12 at 2:32
• No, there is no constraint on those values. But this parameter is necessary. You can see $N-k$ as the possibility to add a ponderation to the $k$-prefix. – Turingoid Jul 28 '12 at 3:01
• So, your strategy is to include all strings from $C(k,l)$, the $k$-strings with $l$ 1's, until you reach a point where the bound forces you to select a proper subset from $C(k,l)$, while varying the last $N-k$ digits, right? If so, a relevant fact is that for $l > 0$, the full set $C(k,l)$ contributes $\binom{k}{l}/(k/l) = \binom{k-1}{l-1}$ 1's to any given $j$-column per suffix string of $2^{N-k}$. Thus, if your exchange lemma holds, you can get 22 strings for $N = 6, k = 5, m = 4$, instead of 18. – Hugh Denoncourt Jul 29 '12 at 19:47
• I do not understand why you use N=6 when he used N=5 in the example, and so on. So I don't know if the fact that you found 22 instead of 18 has a real meaning here, or if you just did a typo with the numbers. – Arthur MILCHIOR Jul 31 '12 at 2:15
• @Hugo My exchange lemma says that before including strings with $l$ 1's I should first include strings with $l−1$ 1's. However, it doesn't says that the last $l$ is totally filled, so I don't see how you can conclude that it would give another bound. Maybe my "less" was unclear and I should say "strictly less". – Turingoid Jul 31 '12 at 2:17

This is a counterexample to the formula $e = 2^{N-k} + 2^{N-m}m$ for the maximum number of strings satisfying the given constraints. The parameters of the example are $N = 6$, $k = 5$, and $m = 4$. The constraint is that the columns sum to no more than $6$. The conjectured formula predicts that 18 is the maximum number of strings. $$\begin{array}{cc} \sigma_1 & 000000\\\\ \sigma_2 & 000001\\\\ \sigma_3 & 100000\\\\ \sigma_4 & 100001\\\\ \sigma_5 & 010000\\\\ \sigma_6 & 010001\\\\ \sigma_7 & 001000\\\\ \sigma_8 & 001001\\\\ \end{array} \hspace{20pt} \begin{array}{cc} \sigma_9 & 000100\\\\ \sigma_{10} & 000101\\\\ \sigma_{11} & 000010\\\\ \sigma_{12} & 000011\\\\ \sigma_{13} & 110000\\\\ \sigma_{14} & 110001\\\\ \sigma_{15} & 001100\\\\ \sigma_{16} & 001101\\\\ \end{array} \hspace{20pt} \begin{array}{cc} \sigma_{17} & 100010\\\\ \sigma_{18} & 100011\\\\ \sigma_{19} & 011000\\\\ \sigma_{20} & 011001\\\\ \sigma_{21} & 000110\\\\ \sigma_{22} & 000111\\\\ \end{array}$$ If $C(k, \ell)$ denotes the number of $k$-strings with $\ell$ 1's, and all such strings are included with all possible $N-k$ suffixes, then the total contribution to the column sum from $C(k, \ell)$ (when $\ell > 0$) is $2^{N-k}\binom{k-1}{\ell - 1}$. In this example, all strings from $C(5,0)$ and $C(5,1)$ were included, but, not all strings from $C(5,2)$ could be included. If the exchange lemma is correct, this idea can be used to at least predict lower and upper bounds for $e$.
• @Hugh Your interpretation is good. You could as well have given a counter example with N=5 as you duplicate all $k$ prefixes and hence don't "use" the extra N-k bits. I'll try to fix my bound. In fact I don't need to have a tight bound, but just an upper bound in function of $k$ and $m$ so that I can take $m$ and $k$ big enough to make $e$ arbitrarily small. (And sorry for having mistyped your name in my comments) – Turingoid Aug 1 '12 at 23:20
• @Hugh In fact, using my previous comment, I realized that I needed to give an upper bound only to an infinity of $m$. So it suffices to take $m_i$ so that we can put exactly all strings with at most $i$ 1's in the $k$ prefix and all $N-k$ suffixes. I guess it isn't too difficult to prove that the created set is an optimal solution for $m_i$. – Turingoid Aug 2 '12 at 3:53
• @Turingoid: True! And, the number of such strings is a nice simple sum of binomial coefficients times a power of 2. For nice choices of $m$, you get a nice result. I wonder if the optimal number of strings can always be obtained by repeating the strings over all $N-k$ suffixes. I meant to ask: Was there a motivation behind the question, perhaps as part of a larger question, or did it arise out of recreation? – Hugh Denoncourt Aug 2 '12 at 18:50