# Cycle length of K-ary Boolean function

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

• 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? – antkam Apr 24 at 12:42
• @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. – Andreas Apr 24 at 15:06