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.

  • $\begingroup$ Is there no constraint on the last $N-k$ values of the strings? $\endgroup$ – Douglas Zare Jul 28 '12 at 2:32
  • $\begingroup$ 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. $\endgroup$ – Turingoid Jul 28 '12 at 3:01
  • $\begingroup$ 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. $\endgroup$ – Hugh Denoncourt Jul 29 '12 at 19:47
  • $\begingroup$ 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. $\endgroup$ – Arthur MILCHIOR Jul 31 '12 at 2:15
  • $\begingroup$ @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". $\endgroup$ – 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$.

| cite | improve this answer | |
  • $\begingroup$ @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) $\endgroup$ – Turingoid Aug 1 '12 at 23:20
  • $\begingroup$ True. I think I was trying to stay as close as possible to your original example. Anyway, no problem on the mistype. $\endgroup$ – Hugh Denoncourt Aug 2 '12 at 0:52
  • $\begingroup$ @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$. $\endgroup$ – Turingoid Aug 2 '12 at 3:53
  • $\begingroup$ @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? $\endgroup$ – Hugh Denoncourt Aug 2 '12 at 18:50
  • $\begingroup$ I guess the general problem is harder than just repeating an efficient set of strings over suffixes. If we take a set of strings where the column sums are equal to the bound except in some of the spots, there is sometimes a way to get larger sets of strings satisfying the constraints. (I'm sure you've seen this already!) $\endgroup$ – Hugh Denoncourt Aug 2 '12 at 19:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.