How long does it take at most for $k$ boolean variables to map back to themselves with a positive disjunctive update rule?

Question

I have a vector of boolean variables $v=(x_1,\dots,x_k)$. In each step each variable is updated according to a positive disjunction like so:

• $x_1 \leftarrow x_i \vee \dots \vee x_j$
• $\dots$
• $x_k \leftarrow x_m \vee \dots \vee x_n$

This produces a sequence of vectors $\underline{v} = v_1,v_2\dots$. My question is, how long does it take for $\underline{v}$ to reach a cycle, in terms of $k$, for arbitrary $v_1$, that is:

Let $v$ be a $k$-ary boolean vector. Then $f(v)$ denotes the update function for according to those rules. We say $v'$ is in a cycle from $v$ if there is an $n>0$ and $m \geq 0$ such that $f^{(m)}=f^{(m+n)}$. We define the smallest time to reach a cycle as the smallest sum $m+n$ for which the equality holds.

The question is: What is an upper bound for the smallest time to reach a cycle in terms of $k$ that holds for all possible starting vectors $v_1$ and all possible update functions $f$.

---

My idea was to represent the update rules as a dependency graph and look at cycles to form rules such as if $x_i$ is true in $v_y$ and is in a cycle of length $n$, then it will also be true in $v_{y+n}$.

But the best lower bound I could do so far is to construct an example where for even $k=2l$ I construct two cycles of length $l$ and $l+1$ with one common node and start with $v_1$ having exactly one true node. The common node is true every $l$ or $l+1$ steps (depending on in which cycle the first true node was). Since $gcd(l,l+1)=1$, eventually all nodes in the other cycle will be true as well. For this, the common nude must be true $l+1$ or $l$ times, respectively. This yields $O(k^2)$ steps until all nodes are true (and then $\underline{v}$ is trivially cyclic).

Unfortunately, I did not get any upper bound except for the obvious $2^k+1$ since each $v_i$ can only assume one of $2^k$ values.

---

I am not necessarily looking for an exact upper bound if that turns out to be hard, it'd also be sufficient for me to give the upper bound in $O$-notation, or even just show whether the upper bound is polynomial or exponential.

Further, I'm also interested in and extension to the 3-valued case (with 3-valued Kleene disjunction).

Answer 1

This can take exponentially many steps, as Laakeri explained.

You can build a system that cycles with period $p$. In particular, the update rule is $x_i = x_{i-1 \bmod p}$ for all $i$, with variables $x_0,\dots,x_{p-1}$.

Let $p_1,\dots,p_k$ be the first $k$ primes. Concatenate $k$ disjoint systems, each of which cycles with period $p_i$. Then the period of the entire system is the product $p_1 \cdots p_k$. The system involves $p_1+\dots+p_k$ variables.

If you have $n$ variables, then we can take $k$ to be approximately $\sqrt{4n/\log n}$. Now the product of the first $k$ primes is roughly $e^{k \log k}$, or in other words, $e^{\Theta(\sqrt{n/\log n})}$, which is exponential in $n$.

This shows that the period of a system, and thus the time to reach a cycle (by your definition), can be exponential in the number of variables.