2
$\begingroup$

Boolean networks have been extensively studied, however I didn't find a reference to the following problem. May be you can provide one, or give hints to a possible solution.

Define K Boolean variables $x_i \in \{-1, 1 \}$ and a K-ary Boolean function of threshold type, $f(\{x_i\}) = {\rm sign} ({\sum_{i=1}^K w_i x_i})$ with real weights $w_i$.

The iteration over discrete timesteps $t$ of the Boolean variables follows the logic $$ x_1(t+1) = f(\{x_i(t)\})\\ x_i(t+1) =x_{i-1}(t) \quad \forall i \ge 2 $$

The latter conditions may be inserted to give the one-dimensional equation

$$ x_1(t) = {\rm sign} ({\sum_{i=1}^K w_i x_1(t-i)}) $$

and likewise for all other $x_j$.

Question: which cycles of lengths $N$ exist, i.e. $x_i(t+N) =x_{i}(t)$ ?

Clearly, a few observations can be made: the cycles depend on the choice of the weights $w_i$, there may be several cycles with different sets of $\{x_i \}$ and different $N$, and $1 \le N \le 2^K$.

The choice of the Boolean function as a threshold function may lead to an access to the problem, since it offers some special features:

  1. The Boolean function is balanced, i.e. its output yields as many $1$s as $-1$s.

  2. The choice $x_i^* = {\rm sign} (w_i )$ yields the output $1$, and this is the Boolean input vector "around" which all other Boolean input vectors are grouped which also yield the output $1$. This grouping is understood geometrically from the fact that the Boolean threshold function selects a halfspace in $K$-space, or in terms of Hamming distances, selects Boolean input vectors with "small" Hamming distances to $x_i^*$.

$\endgroup$
  • $\begingroup$ I probably cannot help but would like a clarification anyway. Are you asking what $N$-cycles exist when you have free choice of $[w_i]$ and initial $x(0)$? Or are you asking, for a given $[w_i]$, what $N$-cycles exist when you have free choice of $x(0)$? Or even the other way: given an initial $x(0)$, what $N$-cycles exist when you have free choice of $[w_i]$? Also, do you care if the period is actually a proper factor of $N$ or must $N$ be the smallest period? $\endgroup$ – antkam Apr 24 at 12:42
  • $\begingroup$ @antkam Thanks for asking. My original intention was to consider a given set of $\{w_i\}$. Then cycles will arise which go through a time sequence of $\{x_i(t)\}$, where usually the logical update rules should be solved which gives $N$ and the corresponding sequence of $\{x_i(t)\}$. However, I'm also happy if you show a way to find the $\{w_i\}$ corresponding to a time sequence of $\{x_i(t)\}$. Such a solution will not always exist, as the Booelan function is restricted (see text). If $N$ is a period, then multiples of $N$ are as well, so this wouldn't matter. $\endgroup$ – Andreas Apr 24 at 15:06

Your Answer

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

Browse other questions tagged or ask your own question.