<p>This can take exponentially many steps, as <a href="https://cstheory.stackexchange.com/questions/48667/how-long-does-it-take-at-most-for-k-boolean-variables-to-map-back-to-themselve/48673#comment108343_48667">Laakeri explained</a>.</p>
<p>You can build a system that cycles with period <span class="math-container">$p$</span>.  In particular, the update rule is <span class="math-container">$x_i = x_{i-1 \bmod p}$</span> for all <span class="math-container">$i$</span>, with variables <span class="math-container">$x_0,\dots,x_{p-1}$</span>.</p>
<p>Let <span class="math-container">$p_1,\dots,p_k$</span> be the first <span class="math-container">$k$</span> primes.  Concatenate <span class="math-container">$k$</span> disjoint systems, each of which cycles with period <span class="math-container">$p_i$</span>.  Then the period of the entire system is the product <span class="math-container">$p_1 \cdots p_k$</span>.  The system involves <span class="math-container">$p_1+\dots+p_k$</span> variables.</p>
<p>If you have <span class="math-container">$n$</span> variables, then we can take <span class="math-container">$k$</span> to be approximately <span class="math-container">$\sqrt{4n/\log n}$</span>.  Now the product of the first <span class="math-container">$k$</span> primes is roughly <span class="math-container">$e^{k \log k}$</span>, or in other words, <span class="math-container">$e^{\Theta(\sqrt{n/\log n})}$</span>, which is exponential in <span class="math-container">$n$</span>.</p>
<p>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.</p>

CC BY-SA 4.0
2021-03-25T08:01:25.480Z
Can you specify what you mean by "concatenate"? Adding one transition from a cycle induced by $p_i$ to the cycle of length $p_{i+1}$?  If yes, this does not hold, as I said in response to Laakeri's comment. For $k=2$ we have some constant $t$ as the maximum number of steps required for $(x_1,\dots,x_5)$ to cycle. within that vector cycle we must have $x_3=x_4=x_5=\text{true}$. As I outlined in my comment, from there on adding a $p_k$ cycle results in $p_k$ more steps until you $\underline{v}$ reaches a cycle. This means in your construction the bound is $t+\sum_{i=2}^k p_k$, i.e., linear.
PattuX
CC BY-SA 4.0
2021-03-25T08:03:09.070Z
@PattuX, no, each system is disjoint.  Variables $x_0,\dots,x_{p_1-1}$ are in the first system, $x_{p_1},\dots,x_{p_1+p_2-1}$ are in the second system, and so on.  Each update rule only mentions variables within the system, there is no propagation between systems.  Each system evolves independently, in parallel.  I'm proposing something different than you proposed, so your response to Laakeri is irrelevant (I suspect you misunderstood what Laakeri had in mind too).
D.W.
CC BY-SA 4.0
2021-03-25T08:19:04.653Z
Oh, now I see, thank you!
PattuX
CC BY-SA 4.0
2021-03-25T01:43:12.907Z
2021-03-25T08:02:04.020Z
2021-03-25T08:02:04.020Z
D.W.
<p>I have a vector of boolean variables <span class="math-container">$v=(x_1,\dots,x_k)$</span>. In each step each variable is updated according to a positive disjunction like so:</p>
<ul>
<li><span class="math-container">$x_1 \leftarrow x_i \vee \dots \vee x_j$</span></li>
<li><span class="math-container">$\dots$</span></li>
<li><span class="math-container">$x_k \leftarrow x_m \vee \dots \vee x_n$</span></li>
</ul>
<p>This produces a sequence of vectors <span class="math-container">$\underline{v} = v_1,v_2\dots$</span>. My question is, how long does it take for <span class="math-container">$\underline{v}$</span> to reach a cycle, in terms of <span class="math-container">$k$</span>, for arbitrary <span class="math-container">$v_1$</span>, that is:</p>
<p>Let <span class="math-container">$v$</span> be a <span class="math-container">$k$</span>-ary boolean vector. Then <span class="math-container">$f(v)$</span> denotes the update function for  according to those rules. We say <span class="math-container">$v'$</span> is in a cycle from <span class="math-container">$v$</span> if there is an <span class="math-container">$n&gt;0$</span> and <span class="math-container">$m \geq 0$</span> such that <span class="math-container">$f^{(m)}=f^{(m+n)}$</span>. We define the smallest time to reach a cycle as the smallest sum <span class="math-container">$m+n$</span> for which the equality holds.</p>
<p>The question is: What is an upper bound for the smallest time to reach a cycle in terms of <span class="math-container">$k$</span> that holds for all possible starting vectors <span class="math-container">$v_1$</span> and all possible update functions <span class="math-container">$f$</span>.</p>
<hr />
<p>My idea was to represent the update rules as a dependency graph and look at cycles to form rules such as if <span class="math-container">$x_i$</span> is true in <span class="math-container">$v_y$</span>  and is in a cycle of length <span class="math-container">$n$</span>, then it will also be true in <span class="math-container">$v_{y+n}$</span>.</p>
<p>But the best lower bound I could do so far is to construct an example where for even <span class="math-container">$k=2l$</span> I construct two cycles of length <span class="math-container">$l$</span> and <span class="math-container">$l+1$</span> with one common node and start with <span class="math-container">$v_1$</span> having exactly one true node. The common node is true every <span class="math-container">$l$</span> or <span class="math-container">$l+1$</span> steps (depending on in which cycle the first true node was). Since <span class="math-container">$gcd(l,l+1)=1$</span>, eventually all nodes in the other cycle will be true as well. For this, the common nude must be true <span class="math-container">$l+1$</span> or <span class="math-container">$l$</span> times, respectively. This yields <span class="math-container">$O(k^2)$</span> steps until all nodes are true (and then <span class="math-container">$\underline{v}$</span> is trivially cyclic).</p>
<p>Unfortunately, I did not get any upper bound except for the obvious <span class="math-container">$2^k+1$</span> since each <span class="math-container">$v_i$</span> can only assume one of <span class="math-container">$2^k$</span> values.</p>
<hr />
<p>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 <span class="math-container">$O$</span>-notation, or even just show whether the upper bound is polynomial or exponential.</p>
<p>Further, I'm also interested in and extension to the 3-valued case (with 3-valued Kleene disjunction).</p>

CC BY-SA 4.0
2021-03-24T18:01:17.333Z
I'm not sure what your question is.  Are you looking for an efficient algorithm that, given the update rules, computes the time to cycle?  Are you looking for a mathematical upper bound on the time to cycle as a function of $n$, that will hold for all update rules?  Something else?  Can you [edit] your question to clarify?
D.W.
CC BY-SA 4.0
2021-03-24T18:02:16.890Z
Can you define more precisely what it means to "reach a cycle"?  If you are already "in" a cycle of length $\ell$, does it take $\ell$ time to reach a cycle, or 0?
D.W.
CC BY-SA 4.0
2021-03-24T18:20:57.907Z
I'm searching for theoretical bounds that hold for all $k$, i.e., whether it's worst case polynomial or exponential. For your second question: It takes $l$ time, so essentially I'm asking when you'll encounter a vector $v_i$ that you've already seen.
PattuX
CC BY-SA 4.0
2021-03-24T18:36:07.150Z
That still doesn't answer my questions about what it means to reach a cycle.  Let me propose some definitions.  If $x$ is a state (boolean vector), let $f(x)$ denote the next step according to the update rules, and let $f^{(n)}(x)$ denote the result of applying $f$ $n$ times. We could define that $x$ is in a cycle if there exists $n>0$ such that $f^{(n)}(x)=x$, that the period of the cycle is the smallest such $n$, that the time it takes for $x$ to reach a cycle is the smallest $n$ such that $f^{(n)}$ is in a cycle, and that the cycle time of $x$ is the smallest $n>0$ such that $f^{(n)}(x)=x$.
D.W.
CC BY-SA 4.0
2021-03-24T18:37:23.683Z
If you accept those definitions, are you asking for an upper bound on the period of any cycle?  on the time it takes to reach a cycle?  the cycle time of any state?  Please [edit] the question to define all concepts precisely and be precise about what you want answered.
D.W.
CC BY-SA 4.0
2021-03-24T20:33:33.730Z
Edited my post, hope this makes it clear.
PattuX
CC BY-SA 4.0
2021-03-24T22:21:38.587Z
Can't you generalize the gcd construction to more than two cycles? To me it seems that if you have cycles of coprime lengths then the common cycle length is the product of their lengths. I think this gives at least $2^{k / \log k}$ lower bound
Laakeri
CC BY-SA 4.0
2021-03-25T00:35:18.260Z
I think this does not work. Say for two joined cycles it takes at least $t$ time steps for all variables to be true. Then if we add a cycle of length $l$ (or any graph structure with a a simple path of length $l$ for that matter), we can still say the two initial cycles are entirely true after $t$ steps (possibly even earlier) since we're only dealing with positive disjunctions. From there it only takes $l$ more steps to propagate "true" through all nodes of the added cycle.
PattuX
CC BY-SA 4.0
2021-03-25T00:40:50.950Z
Intuitively, the issue is that we can't look at common cycle length. The reason is that while we can start with one truth value, every a node that is present in multiple cycles is true, it potentially propagates the true value into *both* cycles. This means we have more true nodes and thus potentially more of those splits. In the extreme case where one cycle is eventually entirely true it acts as a "true-source", setting every node reachable within distance $d$ from the cycle to true in at most $d$ time steps.
PattuX
CC BY-SA 4.0
2021-03-26T09:32:16.240Z
Why the "linear logic" tag?  I don't see how this question relates to linear logic...
Damiano Mazza
<graph-theory><lo.logic>
How long does it take at most for $k$ boolean variables to map back to themselves with a positive disjunctive update rule?
PattuX
# How long does it take at most for $k$ boolean variables to map back to themselves with a positive disjunctive update rule?

(Asked by: username_0 on 2021-03-24)

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

**Tags:** graph-theory, lo.logic

> **Comments:**
> **username_1**: I'm not sure what your question is.  Are you looking for an efficient algorithm that, given the update rules, computes the time to cycle?  Are you looking for a mathematical upper bound on the time to cycle as a function of $n$, that will hold for all update rules?  Something else?  Can you [edit] your question to clarify?  
> **username_1**: Can you define more precisely what it means to "reach a cycle"?  If you are already "in" a cycle of length $\ell$, does it take $\ell$ time to reach a cycle, or 0?  
> **username_0**: I'm searching for theoretical bounds that hold for all $k$, i.e., whether it's worst case polynomial or exponential. For your second question: It takes $l$ time, so essentially I'm asking when you'll encounter a vector $v_i$ that you've already seen.  
> **username_1**: That still doesn't answer my questions about what it means to reach a cycle.  Let me propose some definitions.  If $x$ is a state (boolean vector), let $f(x)$ denote the next step according to the update rules, and let $f^{(n)}(x)$ denote the result of applying $f$ $n$ times. We could define that $x$ is in a cycle if there exists $n>0$ such that $f^{(n)}(x)=x$, that the period of the cycle is the smallest such $n$, that the time it takes for $x$ to reach a cycle is the smallest $n$ such that $f^{(n)}$ is in a cycle, and that the cycle time of $x$ is the smallest $n>0$ such that $f^{(n)}(x)=x$.  
> **username_1**: If you accept those definitions, are you asking for an upper bound on the period of any cycle?  on the time it takes to reach a cycle?  the cycle time of any state?  Please [edit] the question to define all concepts precisely and be precise about what you want answered.  
> **username_0**: Edited my post, hope this makes it clear.  
> **username_2**: Can't you generalize the gcd construction to more than two cycles? To me it seems that if you have cycles of coprime lengths then the common cycle length is the product of their lengths. I think this gives at least $2^{k / \log k}$ lower bound  
> **username_0**: I think this does not work. Say for two joined cycles it takes at least $t$ time steps for all variables to be true. Then if we add a cycle of length $l$ (or any graph structure with a a simple path of length $l$ for that matter), we can still say the two initial cycles are entirely true after $t$ steps (possibly even earlier) since we're only dealing with positive disjunctions. From there it only takes $l$ more steps to propagate "true" through all nodes of the added cycle.  
> **username_0**: Intuitively, the issue is that we can't look at common cycle length. The reason is that while we can start with one truth value, every a node that is present in multiple cycles is true, it potentially propagates the true value into *both* cycles. This means we have more true nodes and thus potentially more of those splits. In the extreme case where one cycle is eventually entirely true it acts as a "true-source", setting every node reachable within distance $d$ from the cycle to true in at most $d$ time steps.  
> **username_3**: Why the "linear logic" tag?  I don't see how this question relates to linear logic...  

---

## 1 answers

### Answer by username_1 on 2021-03-25. Score: 2 | Accepted answer

This can take exponentially many steps, as [username_2 explained](https://cstheory.stackexchange.com/questions/48667/how-long-does-it-take-at-most-for-k-boolean-variables-to-map-back-to-themselve/48673#comment108343_48667).

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.

> **Comments:**
> **username_0**: Can you specify what you mean by "concatenate"? Adding one transition from a cycle induced by $p_i$ to the cycle of length $p_{i+1}$?  If yes, this does not hold, as I said in response to username_2's comment. For $k=2$ we have some constant $t$ as the maximum number of steps required for $(x_1,\dots,x_5)$ to cycle. within that vector cycle we must have $x_3=x_4=x_5=\text{true}$. As I outlined in my comment, from there on adding a $p_k$ cycle results in $p_k$ more steps until you $\underline{v}$ reaches a cycle. This means in your construction the bound is $t+\sum_{i=2}^k p_k$, i.e., linear.  
> **username_1**: @username_0, no, each system is disjoint.  Variables $x_0,\dots,x_{p_1-1}$ are in the first system, $x_{p_1},\dots,x_{p_1+p_2-1}$ are in the second system, and so on.  Each update rule only mentions variables within the system, there is no propagation between systems.  Each system evolves independently, in parallel.  I'm proposing something different than you proposed, so your response to username_2 is irrelevant (I suspect you misunderstood what username_2 had in mind too).  
> **username_0**: Oh, now I see, thank you!  

---

