<p>I've rethought this and my initial bound was correct. In the worst case, $|S| = \Theta(m \; 2^\frac{m}{\lg m})$</p>

<p>Proof is in two parts. Firstly, $|S| = O(m \; 2^\frac{m}{\lg m})$. Consider the possible values of $s$ of a trajectory which ends at $v_x$. Every bit $s[j]$ for $j \ge x$ is 0, and every bit $s[j]$ for $j &lt; x - \frac{m}{\lg m}$ is 1. Therefore there are only $2^\frac{m}{\lg m}$ values which $s$ can take. Multiply up by the number of $v_x$ and we have the upper bound.</p>

<p>Secondly, consider</p>

<pre>
    <i>0</i> 1 1 1 0 <i>1 1 1 1 1 1 1 1 1 1 1 1</i>
    <i>0 0</i> 1 1 1 0 <i>1 1 1 1 1 1 1 1 1 1 1</i>
    <i>0 0 0</i> 1 1 <b>1 0 <i>1</i></b><i> 1 1 1 1 1 1 1 1 1</i>
    <i>0 0 0 0</i> 1 <b>1 1 0</b><i> 1 1 1 1 1 1 1 1 1</i>
    <i>0 0 0 0 0</i> <b>1 1 1</b> 0<i> 1 1 1 1 1 1 1 1</i>
    <i>0 0 0 0 0 0</i> 1 1 1 0 <i>1 1 1 1 1 1 1</i>
    ...
    <i>0 0 0 0 0 0 0 0 0 0 0 0</i> 1 1 1 0 <i>1</i>
    <i>0 0 0 0 0 0 0 0 0 0 0 0 0</i> 1 1 1 0
    <i>0 0 0 0 0 0 0 0 0 0 0 0 0 0</i> 1 1 1
    <i>0 0 0 0 0 0 0 0 0 0 0 0 0 0 0</i> 1 1
    <i>0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0</i> 1

</pre>

<p>I assert that this scheme gives you $|S| = \Omega(m \; 2^\frac{m}{\lg m})$. For each column $v_x$ consider also the $(\frac{m}{\lg m}-2)$ columns to its right. Each of the $2^{\frac{m}{\lg m}-2}$ combinations of them gives a different $s$, and in each of those $s$ the top set bit is the top set bit of $v_x$, so there is no double-counting between different $v_x$.</p>

CC BY-SA 3.0
2011-09-29T08:22:48.637Z
Thanks for your answer. Do you have any clue whether the third constraint (i.e. not more than $12$ zeros) makes any difference? In other words, do you believe that restricting the zeros to at most $12$ implies that the number of different values introduced by trajectories ending at $v_x$ is much less than $2^{m/logm}$ (by _"much less"_ I mean not exponential in ${m/logm}$)? My sensation is that it doesn't make any difference: even if we allow at most $1$ zero it seems that we may generate $2^{m/logm}$ different values for at least one $v_x$.
Giorgio Camerani
CC BY-SA 3.0
2011-09-29T08:26:06.683Z
@WalterBishop, my example uses not more than 1 zero.
Peter Taylor
CC BY-SA 3.0
2011-09-29T09:01:48.103Z
Sorry I've parsed both the answer and the example too fast.
Giorgio Camerani
CC BY-SA 3.0
2011-09-30T16:16:35.437Z
@WalterBishop, although if you restrict the number of 1s instead (no more than $k$ of the free values in a vector can be 1) you get $|S| = O(m^{k+1})$
Peter Taylor
CC BY-SA 3.0
2011-10-02T18:36:38.217Z
How do you derive $|S|=O(m^{k+1})$ in such case? To me, it seems that in such case we would have $|S|=O(m \cdot 2^{k})=O(m)$ (since $k$ is constant). Because AND-ing 2 vectors, a $1$ may become a $0$ but a $0$ can't become a $1$: thus, regardless of the fact that our _"sliding window"_ has $m/logm$ vectors, we may generate at most $2^k$ different vectors for each of the $m$ position of the _"sliding window"_. Am I missing something?
Giorgio Camerani
CC BY-SA 3.0
2011-10-02T21:34:23.227Z
@WalterBishop, it's certainly a loose bound. I can tighten it to $O(m (\frac{m}{\lg m})^k)$ as an equivalent expression to $O\left(m \binom{m / \lg m}{k}\right)$. But yes, I agree that your bound is good because there are only $2^k$ set free variables in $v_x$ to be masked away.
Peter Taylor
CC BY-SA 3.0
2011-09-28T23:00:42.403Z
2011-09-29T07:27:59.753Z
2011-09-29T07:27:59.753Z
Peter Taylor
<p>I have $m$ bit vectors, each of which is composed by $m$ bits. Let's denote with $v_i[j]$ the $j$-th bit of the $i$-th vector, $i,j \in [1, m]$. Each bit vector $v_i$ is subject to the following 2 restrictions:</p>

<ol>
<li>$v_i[j] = 0\ \forall j \geq i$.</li>
<li>$v_i[j] = 1\ \forall j &lt; i - \frac{m}{log(m)}$.</li>
<li>Those bits that do not fall in the restrictions above can be either $0$ or $1$, but in such case the number of $0$'s can be at most $12$.   </li>
</ol>

<p>Now I have another bit vector $s$, of $m$ bits: initially all the $m$ bits of $s$ are set to $1$. By <em>"applying $v_i$ to $s$"</em> I mean performing a bitwise AND between $s$ and $v_i$, and then storing the result in $s$. I'm interested in the evolution of $s$ after repeated applications of the vectors $v_1, ..., v_m$ given in input.  </p>

<p>Let's call those <em>"repeated applications"</em> a <strong>trajectory</strong>, and let's define such trajectory more formally. A trajectory is a sequence composed by at most $m$ vectors (selected from those $v_1, ..., v_m$ given in input) such that if $v_i$ is in the sequence, then all the $v_j$ after it must have $j &lt; i$. So, for example, $&lt;v_8, v_3&gt;$ is a trajectory, while $&lt;v_3, v_8, v_7&gt;$ is not (because $8\geq3$).  </p>

<p>Clearly, there are $2^m$ different trajectories. Let $S=\emptyset$. Suppose to take $s = 1^m$ and to let it undergo a trajectory $T_1$: for <strong>each step</strong> of the trajectory $T_1$, put the new value taken by $s$ in $S$. Then repeat the same process for another trajectory $T_2$ (always starting from $s=1^m$, and always putting every new value of $s$ in $S$). Then again, until you tried all the possible $2^m$ trajectories. At the end, the set $S$ will contain all the possible values that $s$ may ever assume given the vectors in input.  </p>

<blockquote>
  <p><strong>Questions</strong>   </p>
  
  <ol>
  <li>I have $v_i, ..., v_m$ in input. I want to know $|S|$, i.e. how many distinct values may $s$ ever assume. Of course, I want to compute $|S|$ efficiently, i.e. without trying all the possible trajectories one by one. </li>
  <li>Suppose to remove the 2<sup>nd</sup> restriction on the vectors in input. How doing so affects $|S|$?  </li>
  <li><b>More importantly, what I most care about is how $|S|$ grows with $m$. Is $|S|$ at most polynomial in $m$? Is $|S|$ at most sub-exponential in $m$? Or do there exist bad instances on which $|S|$ is necessarily exponential in $m$?</b></li>
  </ol>
</blockquote>

<p>The following figure is an example with $m=17$:
<img src="https://i.sstatic.net/O4vne.jpg" alt="Example"></p>

<p>I'm collecting experimental data in order to try to figure out which is the relationship between $m$ and $|S|$. So far, experiments seems to suggest that $|S|$ grows faster than $m^3$ and slower than $m^4$. However, for the moment those data have not much significance: I was only able to make tests up to $m = 90$, so there may be a big hidden constant or some other factor that lets an exponential law look like a polynomial law for small $m$. I need help in figuring out the asymptotic behaviour of $|S|$ with respect to $m$.  </p>

CC BY-SA 3.0
2011-09-26T20:08:42.723Z
@Downvoter: Why downvoting? Please motivate.
Giorgio Camerani
CC BY-SA 3.0
2011-09-27T22:18:19.797Z
Aren't the trajectories overcomplicating it? You could just talk about subsets of $\{1\ldots m\}$
Peter Taylor
CC BY-SA 3.0
2011-09-28T08:28:51.267Z
@Peter: Yes a trajectory is nothing more than a subset of $\{1, ..., m\}$. I've just thought that talking about trajectories would have given a more intuitive, _"visual"_ picture of the problem. I wanted to put the accent on the evolution of the vector $s$, to stress the fact that I'm interested in how many different values can $s$ assume during all its possible evolutions.
Giorgio Camerani
CC BY-SA 3.0
2011-09-29T16:12:07.040Z
@Walter:  One possible reason for the downvotes is the title of the question, which is of no help.  You may want to rephrase it so that it does not contain "help" and maybe hint at the objects you want to count.  Cheers!
Michaël Cadilhac
CC BY-SA 3.0
2011-09-29T17:55:45.970Z
@MichaëlCadilhac: Yes, admittedly the title is very generic. Probably I will change it to something more _"attractive"_. Thanks for your hint, cheers!
Giorgio Camerani
CC BY-SA 3.0
2011-10-03T11:12:30.407Z
I agree with Michaël; the only useful information in the current title is “combinatorial,” and it is fairly broad.  You should be able to give a much better title.
Tsuyoshi Ito
<co.combinatorics>
Help on the following combinatorial problem?
Giorgio Camerani
# Help on the following combinatorial problem?

(Asked by: username_0 on 2011-09-26)

I have $m$ bit vectors, each of which is composed by $m$ bits. Let's denote with $v\_i[j]$ the $j$-th bit of the $i$-th vector, $i,j \in [1, m]$. Each bit vector $v\_i$ is subject to the following 2 restrictions:

1. $v\_i[j] = 0\ \forall j \geq i$.
2. $v\_i[j] = 1\ \forall j < i - \frac{m}{log(m)}$.
3. Those bits that do not fall in the restrictions above can be either $0$ or $1$, but in such case the number of $0$'s can be at most $12$.

Now I have another bit vector $s$, of $m$ bits: initially all the $m$ bits of $s$ are set to $1$. By *"applying $v\_i$ to $s$"* I mean performing a bitwise AND between $s$ and $v\_i$, and then storing the result in $s$. I'm interested in the evolution of $s$ after repeated applications of the vectors $v\_1, ..., v\_m$ given in input.

Let's call those *"repeated applications"* a **trajectory**, and let's define such trajectory more formally. A trajectory is a sequence composed by at most $m$ vectors (selected from those $v\_1, ..., v\_m$ given in input) such that if $v\_i$ is in the sequence, then all the $v\_j$ after it must have $j < i$. So, for example, $$ is a trajectory, while $$ is not (because $8\geq3$).

Clearly, there are $2^m$ different trajectories. Let $S=\emptyset$. Suppose to take $s = 1^m$ and to let it undergo a trajectory $T\_1$: for **each step** of the trajectory $T\_1$, put the new value taken by $s$ in $S$. Then repeat the same process for another trajectory $T\_2$ (always starting from $s=1^m$, and always putting every new value of $s$ in $S$). Then again, until you tried all the possible $2^m$ trajectories. At the end, the set $S$ will contain all the possible values that $s$ may ever assume given the vectors in input.

> **Questions**
>
> 1. I have $v\_i, ..., v\_m$ in input. I want to know $|S|$, i.e. how many distinct values may $s$ ever assume. Of course, I want to compute $|S|$ efficiently, i.e. without trying all the possible trajectories one by one.
> 2. Suppose to remove the 2nd restriction on the vectors in input. How doing so affects $|S|$?
> 3. **More importantly, what I most care about is how $|S|$ grows with $m$. Is $|S|$ at most polynomial in $m$? Is $|S|$ at most sub-exponential in $m$? Or do there exist bad instances on which $|S|$ is necessarily exponential in $m$?**

The following figure is an example with $m=17$:
![Example](https://i.sstatic.net/O4vne.jpg)

I'm collecting experimental data in order to try to figure out which is the relationship between $m$ and $|S|$. So far, experiments seems to suggest that $|S|$ grows faster than $m^3$ and slower than $m^4$. However, for the moment those data have not much significance: I was only able to make tests up to $m = 90$, so there may be a big hidden constant or some other factor that lets an exponential law look like a polynomial law for small $m$. I need help in figuring out the asymptotic behaviour of $|S|$ with respect to $m$.

**Tags:** co.combinatorics

> **Comments:**
> **username_0**: @Downvoter: Why downvoting? Please motivate.  
> **username_1**: Aren't the trajectories overcomplicating it? You could just talk about subsets of $\{1\ldots m\}$  
> **username_0**: @Peter: Yes a trajectory is nothing more than a subset of $\{1, ..., m\}$. I've just thought that talking about trajectories would have given a more intuitive, _"visual"_ picture of the problem. I wanted to put the accent on the evolution of the vector $s$, to stress the fact that I'm interested in how many different values can $s$ assume during all its possible evolutions.  
> **username_2**: @Walter:  One possible reason for the downvotes is the title of the question, which is of no help.  You may want to rephrase it so that it does not contain "help" and maybe hint at the objects you want to count.  Cheers!  
> **username_0**: @MichaëlCadilhac: Yes, admittedly the title is very generic. Probably I will change it to something more _"attractive"_. Thanks for your hint, cheers!  
> **username_3**: I agree with Michaël; the only useful information in the current title is “combinatorial,” and it is fairly broad.  You should be able to give a much better title.  

---

## 1 answers

### Answer by username_1 on 2011-09-28. Score: 8 | Accepted answer

I've rethought this and my initial bound was correct. In the worst case, $|S| = \Theta(m \; 2^\frac{m}{\lg m})$
Proof is in two parts. Firstly, $|S| = O(m \; 2^\frac{m}{\lg m})$. Consider the possible values of $s$ of a trajectory which ends at $v_x$. Every bit $s[j]$ for $j \ge x$ is 0, and every bit $s[j]$ for $j < x - \frac{m}{\lg m}$ is 1. Therefore there are only $2^\frac{m}{\lg m}$ values which $s$ can take. Multiply up by the number of $v_x$ and we have the upper bound.
Secondly, consider

    0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1
    0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
    0 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1
    0 0 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1
    0 0 0 0 0 1 1 1 0 1 1 1 1 1 1 1 1
    0 0 0 0 0 0 1 1 1 0 1 1 1 1 1 1 1
    ...
    0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1
    0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1


I assert that this scheme gives you $|S| = \Omega(m \; 2^\frac{m}{\lg m})$. For each column $v_x$ consider also the $(\frac{m}{\lg m}-2)$ columns to its right. Each of the $2^{\frac{m}{\lg m}-2}$ combinations of them gives a different $s$, and in each of those $s$ the top set bit is the top set bit of $v_x$, so there is no double-counting between different $v_x$.

> **Comments:**
> **username_0**: Thanks for your answer. Do you have any clue whether the third constraint (i.e. not more than $12$ zeros) makes any difference? In other words, do you believe that restricting the zeros to at most $12$ implies that the number of different values introduced by trajectories ending at $v_x$ is much less than $2^{m/logm}$ (by _"much less"_ I mean not exponential in ${m/logm}$)? My sensation is that it doesn't make any difference: even if we allow at most $1$ zero it seems that we may generate $2^{m/logm}$ different values for at least one $v_x$.  
> **username_1**: @WalterBishop, my example uses not more than 1 zero.  
> **username_0**: Sorry I've parsed both the answer and the example too fast.  
> **username_1**: @WalterBishop, although if you restrict the number of 1s instead (no more than $k$ of the free values in a vector can be 1) you get $|S| = O(m^{k+1})$  
> **username_0**: How do you derive $|S|=O(m^{k+1})$ in such case? To me, it seems that in such case we would have $|S|=O(m \cdot 2^{k})=O(m)$ (since $k$ is constant). Because AND-ing 2 vectors, a $1$ may become a $0$ but a $0$ can't become a $1$: thus, regardless of the fact that our _"sliding window"_ has $m/logm$ vectors, we may generate at most $2^k$ different vectors for each of the $m$ position of the _"sliding window"_. Am I missing something?  
> **username_1**: @WalterBishop, it's certainly a loose bound. I can tighten it to $O(m (\frac{m}{\lg m})^k)$ as an equivalent expression to $O\left(m \binom{m / \lg m}{k}\right)$. But yes, I agree that your bound is good because there are only $2^k$ set free variables in $v_x$ to be masked away.  

---

