Help on the following combinatorial problem?

Question

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, $<v_8, v_3>$ is a trajectory, while $<v_3, v_8, v_7>$ 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 2^nd 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$:

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$.

Answer 1

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$.