Pulse Graphs: Prime-Activated Boolean Dynamics on Directed Graphs
July 11, 2026
Abstract
We study synchronous Boolean dynamics on finite loopless directed graphs in which a vertex is active at the next time step exactly when its number of active in-neighbors is prime. We call these systems Pulse Graphs. Let \(L(n)\) denote the largest attractor period realizable on \(n\) vertices. Exhaustive enumeration gives \[L(1),\ldots,L(5)=1,1,1,3,9.\] Our main result determines the exponential order of the maximum period: \[2^{n-3}-1\leq L(n)\leq2^n-1 \qquad(n\geq5).\] The lower bound is obtained by implementing a maximal-length affine feedback register using prime-count logic gates. For \(n\geq6\), the construction is loopless, has maximum in-degree five, and uses only \(O(n)\) edges.
For complete directed graphs, we derive an exact update formula, classify all attractors as fixed points or complement two-cycles, prove that every orbit reaches its eventual attractor within three updates, and count the attractors explicitly. We also derive the activation probability under independent random inputs. For sparse random directed graphs, the associated prime-Poisson mean-field map undergoes a nondegenerate fold at \[c_\ast\approx3.824963, \qquad \rho_\ast\approx0.368241,\] with local bistability immediately above the threshold.
1 Introduction↩︎
Boolean networks are finite-state dynamical systems in which interacting components take values in \(\{0,1\}\) and update according to prescribed local rules. They have been studied as abstract models of regulatory, computational, and network dynamics since the early work of Kauffman [1]. Their behavior depends on the directed graph, the local update functions, and the update schedule.
In this paper, we choose the prime numbers as the activating input counts. This gives a simple arithmetic rule that is nonmonotone: for example, a vertex receiving three active inputs becomes active, whereas one receiving four active inputs becomes inactive. More generally, increasing the number of active inputs can switch the output between active and inactive. Prime activation therefore provides a natural setting for studying how an elementary arithmetic condition can generate nontrivial global dynamics on a directed graph.
The rule is totalistic because the next state of a vertex depends only on the number of its active in-neighbors, rather than on their identities. Totalistic rules on general graphs have been studied as extensions of cellular-automaton dynamics [2], [3].
Pulse Graphs differ from traditional monotone threshold systems. For symmetric threshold networks updated synchronously, periodic attractors have period at most two [4]. Kuhlman et al.obtained a similar restriction for synchronous bi-threshold systems, while showing that asynchronous bi-threshold systems may have longer periodic orbits [5]. The prime-activation rule is nonmonotone and does not satisfy the assumptions of those results. This leads to the extremal question that motivates the present paper: how large can an attractor period be on \(n\) vertices?
The central question of this paper is how much dynamical complexity can be generated by this single arithmetic update rule, and how strongly that complexity depends on the underlying graph. We approach this question from two complementary directions. On general directed graphs, prime activation can implement Boolean operations and feedback mechanisms that produce very long periodic orbits. On highly symmetric graphs like complete graphs, however, the same rule can collapse to much simpler dynamics. This contrast shows that the behavior of Pulse Graphs is governed not only by the nonmonotonicity of prime activation, but also by the underlying substrate structure through which that rule is coupled.
Definition 1. A Pulse Graph* is a finite directed graph \(G=(V,E)\) with no self-loops, together with Boolean states \[x_t:V\to\{0,1\}, \qquad t=0,1,2,\dots.\] For \(v\in V\), let \[N^-(v)=\{u\in V:(u,v)\in E\}, \qquad k_t(v)=\sum_{u\in N^-(v)}x_t(u).\] Thus \(k_t(v)\) is the number of active in-neighbors of \(v\) at time \(t\).*
The update rule is \[x_{t+1}(v)= \begin{cases} 1, & \text{if } k_t(v) \text{ is prime},\\ 0, & \text{otherwise}. \end{cases}\]
A state \(x\) is a fixed point* if applying the Pulse update leaves every vertex unchanged. An attractor of period \(p\) is a periodic sequence of \(p\) distinct states. Thus a fixed point is an attractor of period \(1\), while an attractor of period at least \(2\) is called a nontrivial attractor.*
Proposition 1 (Basic fixed-point facts). Let \(G=(V,E)\) be a Pulse Graph.
If \(N^-(v)=\varnothing\), then \(x_{t+1}(v)=0\) for all \(t\).
The all-ones state is a fixed point if and only if every vertex has prime in-degree.
For every \(n\ge3\), there exists a Pulse Graph on \(n\) vertices whose all-ones state is fixed.
Without self-loops, \(n=3\) is the smallest number of vertices for which the all-ones state can be fixed.
Proof. If \(N^-(v)=\varnothing\), then \(k_t(v)=0\), and \(0\) is not prime.
For the all-ones state, each vertex \(v\) sees exactly \(|N^-(v)|\) active in-neighbors. Hence the all-ones state is fixed exactly when every \(|N^-(v)|\) is prime.
For existence when \(n\ge3\), take the bidirected cycle on \(n\) vertices: \[v_i\leftrightarrow v_{i+1} \qquad (\text{indices mod }n).\] Each vertex has exactly two incoming neighbors, and \(2\) is prime.
Finally, if \(n=1\), every vertex has in-degree \(0\). If \(n=2\), every vertex has in-degree at most \(1\). Neither \(0\) nor \(1\) is prime. Hence \(n=3\) is minimal. ◻
Remark 1. If self-loops are allowed, then \(2\) vertices suffice: let each vertex point to itself and to the other vertex.
2 Small Pulse Graphs↩︎
We begin by examining Pulse Graphs on at most five vertices. Because the state space is finite and the update rule is deterministic, every orbit eventually becomes periodic. Exhaustive enumeration then determines the largest possible attractor period for each \(n\leq5\).
2.1 Eventual Periodicity↩︎
Proposition 2. For every finite Pulse Graph, every initial state eventually enters an attractor.
Proof. Let \(n=|V|\). Since each vertex is either active or inactive, the system has exactly \(2^n\) possible states.
Starting from any initial state, consider the orbit \[x_0,x_1,x_2,\dots.\] Among the first \(2^n+1\) states, at least two must be equal. Because the Pulse update is deterministic, once a state repeats, all subsequent states repeat in the same order. Therefore every orbit eventually enters a periodic attractor. ◻
2.2 Exhaustive Enumeration↩︎
Definition 2. Let \(L(n)\) denote the maximum attractor period among all labeled directed loopless Pulse Graphs on \(n\) vertices.
Proposition 3 (Exact results for \(n\leq5\)). The maximum attractor periods for Pulse Graphs on at most five vertices are \[\begin{array}{c|r|c} n & \text{number of labeled loopless directed graphs} & L(n)\\ \hline 1 & 1 & 1\\ 2 & 4 & 1\\ 3 & 64 & 1\\ 4 & 4{,}096 & 3\\ 5 & 1{,}048{,}576 & 9 \end{array}\]
Proof. For each \(n\leq5\), all \(2^{n(n-1)}\) labeled loopless directed graphs were enumerated. For every graph, each of its \(2^n\) initial states was iterated until repetition, and the largest resulting attractor period was recorded. Taking the maximum over all graphs gives the values in the table. ◻
Thus \(n=4\) is the first size at which a nontrivial attractor appears.
2.3 Examples for Four and Five Vertices↩︎
2.3.1 A Period-\(3\) Attractor on Four Vertices↩︎
The graph consists of three bidirected edges incident to \(v_2\) and the directed cycle \[v_1\to v_0\to v_3\to v_1.\] Its edge set is \[\begin{align} E=\{& v_2\leftrightarrow v_0,\;v_2\leftrightarrow v_1,\;v_2\leftrightarrow v_3,\\ & v_1\to v_0,\;v_0\to v_3,\;v_3\to v_1 \}. \end{align}\]
Under the Pulse update rule, \[1110\longmapsto1011\longmapsto0111\longmapsto1110.\]
Throughout this orbit, \(v_2\) remains active. Among the three outer vertices, exactly one is inactive, and the inactive position moves around the directed cycle \[v_3\longrightarrow v_1\longrightarrow v_0\longrightarrow v_3.\] The three displayed states are distinct, so this is an attractor of exact period \(3\).
2.3.2 A Period-\(9\) Attractor on Five Vertices↩︎
The graph contains a bidirected \(K_{2,2}\) between \(\{v_1,v_2\}\) and \(\{v_3,v_4\}\). Its edge set is \[\begin{align} E=\{& v_1\leftrightarrow v_3,\;v_1\leftrightarrow v_4,\;v_2\leftrightarrow v_3,\;v_2\leftrightarrow v_4,\\ & v_1\to v_0,\;v_2\to v_0,\;v_1\to v_2,\;v_0\to v_3,\;v_0\to v_4,\;v_3\to v_4 \}. \end{align}\]
The corresponding period-\(9\) orbit is \[\begin{align} 00011 &\longmapsto 01100 \longmapsto 10011 \longmapsto 01101 \longmapsto 10111\\ &\longmapsto 01111 \longmapsto 11111 \longmapsto 11110 \longmapsto 10110 \longmapsto 00011. \end{align}\]
All nine states are distinct, so the orbit has exact period \(9\).
The indegrees of \(v_0,\dots,v_4\) are \[2,2,3,3,4,\] respectively. In particular, from the all-ones state, the first four vertices remain active because they receive either \(2\) or \(3\) active inputs, while \(v_4\) turns off because it receives \(4\) active inputs: \[11111\longmapsto11110.\] This transition shows the nonmonotonicity of prime activation: increasing the number of active inputs from \(3\) to \(4\) changes the output from active to inactive.
In ordinary threshold systems, additional active inputs generally do not suppress activation [3]. Pulse Graphs do not have this property.
3 Long Attractor Periods↩︎
Theorem 4 (Rotating-register lower bound).
For every \(n\ge 5\), \[L(n)\ge n-3.\] In particular, \(L(n)\) is unbounded: there is no constant \(M\) such that every Pulse Graph, on every number of vertices, has attractor period at most \(M\).
Proof. Let \(n\geq5\) and set \(\ell=n-3\), the number of signal vertices. Take three control vertices \(c_0,c_1,c_2\), with both directed edges between every pair. Add a directed signal cycle \[s_0\to s_1\to\cdots\to s_{\ell-1}\to s_0,\] together with the edges \[c_0\to s_i \qquad (0\leq i<\ell).\]
Consider the initial state in which all three control vertices and \(s_0\) are active, while all other signal vertices are inactive. Each control vertex receives exactly two active inputs from the other control vertices. Consequently, all three control vertices remain active at every subsequent time step.
Each signal vertex \(s_i\) receives one permanently active input from \(c_0\) and one input from \(s_{i-1}\), with indices taken modulo \(\ell\). Therefore \[k_t(s_i)=1+x_t(s_{i-1}).\] Since \(1\) is not prime and \(2\) is prime, \[x_{t+1}(s_i)=x_t(s_{i-1}).\] Thus the signal state rotates by one position at every update, as illustrated in Figure 4 for \(\ell=4\).
The initial signal state \(10\cdots0\) returns to itself after exactly \(\ell\) updates. Hence the graph has an attractor of period \(\ell=n-3\), and therefore \[L(n)\geq n-3.\] It follows that \(L(n)\) is unbounded. ◻
3.1 Prime-Count Logic Gates↩︎
The rotating-register construction uses one permanently active input to copy a signal. More generally, fixed active inputs allow the prime-count rule to realize several standard Boolean functions directly.
Proposition 5 (Prime-count logic gates).
Suppose that a vertex receives two variable inputs \(x,y\in\{0,1\}\) and \(q\) inputs from vertices that remain permanently active. Let \[F_q(x,y)= \begin{cases} 1, & q+x+y \text{ is prime},\\ 0, & q+x+y \text{ is not prime}. \end{cases}\] For \(0\leq q\leq 4\), the resulting functions are \[\begin{array}{c|ccc|c} q & F_q(0,0) & F_q(0,1)=F_q(1,0) & F_q(1,1) & \text{Boolean function}\\ \hline 0 & 0 & 0 & 1 & x\wedge y\\ 1 & 0 & 1 & 1 & x\vee y\\ 2 & 1 & 1 & 0 & \operatorname{NAND}(x,y)\\ 3 & 1 & 0 & 1 & \operatorname{XNOR}(x,y)\\ 4 & 0 & 1 & 0 & x\oplus y \end{array}\] With one variable input \(x\), one permanently active input computes \(x\), while three permanently active inputs compute \(\neg x\).
Proof. For two variable inputs, the displayed table is obtained directly by testing primality of \(q+x+y\) for the three possible values \(x+y=0,1,2\).
For one variable input, the counts \(1+x\) are \(1\) and \(2\), so the output equals \(x\). The counts \(3+x\) are \(3\) and \(4\), so the output equals \(\neg x\). ◻
Remark 2. A bidirected triangle initialized in the all-ones state supplies three permanently active control vertices: each control receives exactly two active inputs from the other controls. In particular, Proposition 5 shows that Pulse Graphs can implement NAND gates and therefore arbitrary feedforward Boolean circuits when inputs are held fixed.
The exponential-period construction below requires only the copy and XNOR identities.
3.2 Exponential Attractor Periods↩︎
Maximal-length linear feedback registers constructed from primitive polynomials are classical [6]. Related finite-field constructions have also been used to realize a fixed point together with a cycle through all remaining configurations in general bounded-degree automata networks [7]. The issue here is different: the local functions cannot be chosen freely, since every vertex must obey the same prime-count activation rule.
The rotating register proves that \(L(n)\) is unbounded. By adding affine feedback, the same three control vertices can instead produce a cycle through all but one of the \(2^{n-3}\) signal states.
Theorem 6 (Exponential attractor periods). For every \(n\geq 5\), \[2^{n-3}-1\leq L(n)\leq 2^n-1.\] Consequently, \[L(n)=\Theta(2^n).\]
For \(n\geq 6\), the lower bound can be realized by a loopless Pulse Graph with maximum in-degree at most five and at most \(5n-15\) directed edges.
Proof. The all-zero state is fixed in every Pulse Graph, since every vertex then receives zero active inputs. Hence a nontrivial attractor can use at most the remaining \(2^n-1\) states. A fixed-point attractor has period one, so in all cases \[L(n)\leq 2^n-1.\]
For the lower bound, the case \(n=5\) follows from the exact value \[L(5)=9>2^{5-3}-1.\]
Now suppose \(n\geq 6\), and put \[m=n-3.\] Work over the field \(\mathbb{F}_2\). By Cohen’s prescribed-trace theorem [8], there exists, for every \(m\geq3\), a primitive element \[\alpha\in\mathbb{F}_{2^m}\] with \[\operatorname{Tr}_{\mathbb{F}_{2^m}/\mathbb{F}_2}(\alpha)=0.\] Let \[p(z)=z^m+a_{m-1}z^{m-1}+\cdots+a_1z+1\] be the minimal polynomial of \(\alpha\) over \(\mathbb{F}_2\). Since \(\alpha\) is primitive, \(p\) is a primitive polynomial of degree \(m\). Moreover, in characteristic two, the coefficient \(a_{m-1}\) equals the trace of \(\alpha\), and hence \[a_{m-1}=0.\] This zero coefficient will prevent a self-loop at the final register stage.
Let \(A:\mathbb{F}_2^m\to\mathbb{F}_2^m\) be the companion transformation defined by \[(Ax)_0=x_{m-1}\] and \[(Ax)_i=x_{i-1}+a_i x_{m-1}, \qquad 1\leq i<m.\] The characteristic polynomial of \(A\) is \(p\). Because \(p\) is primitive, \(A\) has multiplicative order \[2^m-1.\] Equivalently, after identifying \(\mathbb{F}_2^m\) with \(\mathbb{F}_{2^m}\), the transformation \(A\) is multiplication by a primitive element. It fixes \(0\) and permutes all \(2^m-1\) nonzero vectors in one cycle.
Example 1 (A tap pattern for \(m=3\)). For \(m=3\), the primitive polynomial \(p(z)=z^3+z+1\) gives \(a_1=1\) and \(a_2=0\). The linear register \[y_0'=y_2,\qquad y_1'=y_0+y_2,\qquad y_2'=y_1\] has the \(7=2^3-1\) cycle \[100\to010\to001\to110\to011\to111\to101\to100.\] The Pulse implementation replaces the tapped XOR stage by XNOR: \[x_0'=x_2,\qquad x_1'=1+x_0+x_2,\qquad x_2'=x_1,\] which is an affine translate of the same maximum-period register.
Figure 5 gives a graph-level schematic of the affine feedback mechanism used below.
This construction uses the same control triangle and \(c_0\)-bias mechanism as the rotating register; the only new feature is that tapped stages receive the extra inputs \(c_1,c_2\), and \(s_{m-1}\), causing them to compute XNOR.
We now explicitly realize an affine version of \(A\) as a Pulse Graph. Take three control vertices \(c_0,c_1,c_2\) and signal vertices \(s_0,\ldots,s_{m-1}\). Join every pair of distinct controls in both directions and initialize all controls active. Each control then receives exactly two active inputs, so all controls remain active because \(2\) is prime.
Give \(s_0\) inputs \(c_0\) and \(s_{m-1}\). Then \[x_{t+1}(s_0)=x_t(s_{m-1}).\] For \(1\le i<m\), if \(a_i=0\), give \(s_i\) inputs \(c_0\) and \(s_{i-1}\), so \[x_{t+1}(s_i)=x_t(s_{i-1}).\] If \(a_i=1\), give \(s_i\) inputs \(c_0,c_1,c_2,s_{i-1},s_{m-1}\). Its active-input count is \[3+x_t(s_{i-1})+x_t(s_{m-1}),\] so, since \(3,5\) are prime and \(4\) is not, \[x_{t+1}(s_i)=1+x_t(s_{i-1})+x_t(s_{m-1}) \qquad \text{in }\mathbb{F}_2.\] Thus tapped stages compute XNOR. Since \(a_{m-1}=0\), the final stage is not tapped, so no self-loop is needed.
Writing \[x_t= \bigl( x_t(s_0),\ldots,x_t(s_{m-1}) \bigr)^{\mathsf{T}},\] the signal update is the affine transformation \[x_{t+1}=T(x_t)=Ax_t+b,\] where \[b=(0,a_1,\ldots,a_{m-1})^{\mathsf{T}}.\]
Since \(p\) is primitive and \(m\geq 3\), the number \(1\) is not a root of \(p\). Hence \[\det(I-A)=p(1)\neq 0,\] so \(I-A\) is invertible. There is a unique vector \(z\in\mathbb{F}_2^m\) such that \[(I-A)z=b.\]
Set \[y_t=x_t+z.\] Since \(Az+b=z\), we obtain \[\begin{align} y_{t+1} &=x_{t+1}+z\\ &=A(y_t+z)+b+z\\ &=Ay_t. \end{align}\] Thus \(T\) is conjugate by translation to \(A\).
The affine map \(T\) therefore has one fixed point and one cycle containing all its other \[2^m-1\] states. With the controls fixed, the Pulse Graph has an attractor of exact period \[2^m-1=2^{n-3}-1.\] This proves the lower bound.
Every signal vertex has in-degree either two or five, while every control vertex has in-degree two. If \[r=\bigl|\{i:1\leq i<m,\;a_i=1\}\bigr|,\] then \(r\leq m-2\), since \(a_{m-1}=0\). The graph has six edges in the control triangle, \(m\) copy-bias edges from \(c_0\), \(m\) register edges, and \(3r\) additional XNOR inputs. Thus its number of edges is \[\begin{align} 6+m+m+3r &\leq 6+2m+3(m-2)\\ &=5m\\ &=5n-15. \end{align}\]
Finally, for \(n\geq 5\), \[2^{n-3}-1\geq 2^{n-4}=\frac{1}{16}2^n.\] Together with the upper bound, this proves \[L(n)=\Theta(2^n).\] ◻
4 Complete Directed Pulse Graphs↩︎
Let \(K_n^\rightarrow\) denote the complete directed graph on \(n\) vertices with no self-loops: for every pair \(u\neq v\), the edge \(u\to v\) is present.
Theorem 7 (Complete graph update formula). Let \(S_t\subseteq V\) be the active set at time \(t\), and let \(m=|S_t|\). In \(K_n^\rightarrow\), the next active set is \[S_{t+1} = \begin{cases} V, & \text{if } m-1 \text{ is prime and } m \text{ is prime},\\ S_t, & \text{if } m-1 \text{ is prime and } m \text{ is not prime},\\ V\setminus S_t, & \text{if } m-1 \text{ is not prime and } m \text{ is prime},\\ \varnothing, & \text{if } m-1 \text{ is not prime and } m \text{ is not prime}. \end{cases}\]
Proof. If \(v\in S_t\), then \(v\) has exactly \(m-1\) active in-neighbors, since self-loops are excluded. Hence active vertices remain active exactly when \(m-1\) is prime.
If \(v\notin S_t\), then \(v\) has exactly \(m\) active in-neighbors. Hence inactive vertices become active exactly when \(m\) is prime.
Combining these two facts gives the four cases. ◻
Theorem 8 (Attractor classification for complete Pulse Graphs). In \(K_n^\rightarrow\), every orbit eventually enters either a fixed point or a complement two-cycle \[S \longleftrightarrow V\setminus S.\]
Proof. By the complete graph update formula, every active set \(S\subseteq V\) maps to exactly one of \[\varnothing,\qquad S,\qquad V\setminus S,\qquad V.\] Hence the only possible attractors are fixed points and complement two-cycles.
The fixed points are exactly:
the empty state \(\varnothing\), which is always fixed;
the all-ones state \(V\), which is fixed exactly when \(n-1\) is prime;
proper nonempty sets \(S\subsetneq V\) satisfying \[|S|-1 \text{ is prime} \qquad\text{and}\qquad |S| \text{ is not prime}.\]
The complement two-cycles are exactly those \[S \longleftrightarrow V\setminus S\] where \[|S| \text{ and } |V\setminus S| \text{ are prime,}\] and neither size equals \(3\).
Indeed, \(S\mapsto V\setminus S\) occurs exactly when inactive vertices turn on and active vertices turn off. In \(K_n^\rightarrow\), this means \[|S| \text{ is prime} \qquad\text{and}\qquad |S|-1 \text{ is not prime}.\] For prime \(|S|\), the second condition fails only when \(|S|=3\). Applying the same condition to \(V\setminus S\) gives the stated condition for a complement two-cycle. ◻
Definition 3. Fix \(K_n^\rightarrow\) and an initial active set \(S_0\subseteq V\). Starting from \(S_0\), the Pulse update produces a sequence \[S_0,S_1,S_2,\dots.\] Since there are only finitely many possible active sets, this sequence eventually repeats.
The transient time* \(t(S_0)\) is the number of steps before the sequence reaches its eventual repeating part. Equivalently, \(t(S_0)\) is the first time \(t\) such that \(S_t\) belongs to the final periodic orbit.*
The maximum transient time* is \[T(n)=\max_{S_0\subseteq V} t(S_0).\] Thus \(T(n)\) is the worst-case number of steps needed, over all initial active sets, before the dynamics reach their eventual fixed point or cycle.*
Theorem 9 (Constant transient bound for complete Pulse Graphs). For the complete directed loopless Pulse Graph \(K_n^\rightarrow\), \[T(n)\leq 3.\] Thus the maximum transient time is bounded independently of \(n\). In particular, \[T(n)=O(1).\]
Proof. Let \(S_0\subseteq V\) be arbitrary. By the complete graph update formula, \[S_1\in\{\varnothing,S_0,V\setminus S_0,V\}.\]
We consider the four possibilities.
Case 1: \(S_1=\varnothing\). The empty state is fixed, since every vertex sees \(0\) active in-neighbors and \(0\) is not prime. Hence the orbit has entered an attractor at time \(1\).
Case 2: \(S_1=S_0\). Then \(S_0\) is a fixed point. Hence the orbit was already on an attractor at time \(0\).
Case 3: \(S_1=V\). If \(n-1\) is prime, then \(V\) is fixed, so the orbit enters an attractor at time \(1\). If \(n-1\) is not prime, then \(V\mapsto\varnothing\), and \(\varnothing\) is fixed. Hence the orbit enters an attractor by time \(2\).
Case 4: \(S_1=V\setminus S_0\). Apply the complete graph update formula again: \[S_2\in\{\varnothing,V\setminus S_0,S_0,V\}.\]
If \(S_2=\varnothing\), then the orbit enters the fixed point \(\varnothing\) at time \(2\).
If \(S_2=V\setminus S_0\), then \(V\setminus S_0\) is fixed, so the orbit enters an attractor at time \(1\).
If \(S_2=S_0\), then \[S_0\longmapsto V\setminus S_0\longmapsto S_0,\] so the orbit is on a two-cycle from time \(0\).
If \(S_2=V\), then either \(V\) is fixed or \(V\mapsto\varnothing\). Therefore the orbit enters an attractor by time \(3\).
Thus every orbit enters a fixed point or a two-cycle after at most three updates. ◻
4.1 Counting Attractors in Complete Pulse Graphs↩︎
The classification theorem also gives explicit formulas for the number of attractors in \(K_n^\rightarrow\).
Let \[F(n)=\text{number of fixed points of }K_n^\rightarrow,\] \[C(n)=\text{number of complement two-cycles of }K_n^\rightarrow,\] and \[A(n)=\text{total number of attractors of }K_n^\rightarrow.\]
Proposition 10 (Fixed-point count). For the complete directed loopless Pulse Graph \(K_n^\rightarrow\), \[F(n) = 1 + \begin{cases} 1, & \text{if } n-1 \text{ is prime},\\ 0, & \text{otherwise}, \end{cases} + \sum_{\substack{1\leq m\leq n-1\\ m-1\text{ is prime}\\ m\text{ is not prime}}} \binom{n}{m}.\]
Proof. The empty state \(\varnothing\) is always fixed, giving the first term \(1\).
The full state \(V\) contributes \[\begin{cases} 1, & \text{if } n-1 \text{ is prime},\\ 0, & \text{otherwise}. \end{cases}\]
For a proper nonempty active set \(S\), let \(m=|S|\). Such a set is fixed exactly when \[m-1 \text{ is prime} \qquad\text{and}\qquad m \text{ is not prime}.\] For each allowed size \(m\), there are \(\binom{n}{m}\) choices of \(S\). Summing over all such \(m\) gives the formula. ◻
Proposition 11 (Two-cycle count). The number of complement two-cycles in \(K_n^\rightarrow\) is \[C(n) = \frac{1}{2} \sum_{\substack{0\leq m\leq n\\ m\text{ prime}\\ n-m\text{ prime}\\ m\neq 3,\;n-m\neq 3}} \binom{n}{m}.\]
Proof. A complement two-cycle has the form \[S\longleftrightarrow V\setminus S.\] By the attractor classification theorem, this occurs exactly when \(|S|\) and \(|V\setminus S|\) are both prime, and neither size equals \(3\).
If \(|S|=m\), then \(|V\setminus S|=n-m\). There are \(\binom{n}{m}\) choices for \(S\). The restrictions in the sum enforce the conditions that \(m\) and \(n-m\) are prime and neither equals \(3\).
Finally, each two-cycle is counted twice: once by \(S\), and once by \(V\setminus S\). Therefore we divide by \(2\). ◻
Corollary 1 (Total attractor count). The total number of attractors of \(K_n^\rightarrow\) is \[A(n)=F(n)+C(n).\]
The first 10 values are: \[\begin{array}{c|cccccccccc} n & 1&2&3&4&5&6&7&8&9&10\\ \hline F(n) & 1&1&2&2&6&17&43&100&220&466\\ C(n) & 0&0&0&3&0&0&21&0&36&126\\ A(n) & 1&1&2&5&6&17&64&100&256&592 \end{array}\]
5 Local Activation Probability and Mean-Field Heuristic↩︎
5.1 Local Activation Probability↩︎
For a vertex of indegree \(d\), suppose each incoming neighbor is independently active with probability \(\rho\). Then the number of active in-neighbors is binomial: \[X\sim \operatorname{Binomial}(d,\rho).\] Hence the probability that the vertex turns on is \[P_d(\rho) = \mathbb{P}(X\text{ is prime}) = \sum_{\substack{0\leq k\leq d\\ k\text{ prime}}} \binom{d}{k}\rho^k(1-\rho)^{d-k}.\] In the uniform case \(\rho=1/2\), \[P_d(1/2) = \frac{1}{2^d} \sum_{\substack{0\leq k\leq d\\ k\text{ prime}}} \binom{d}{k}.\] For example, \[P_1(1/2)=0,\qquad P_2(1/2)=\frac{1}{4},\qquad P_3(1/2)=\frac{1}{2},\qquad P_4(1/2)=\frac{5}{8}.\]
5.2 Sparse Random Pulse Graph Mean-field Heuristic↩︎
Let \(G\) be a random directed graph on \(n\) vertices with no self-loops. Each possible directed edge appears independently with probability \(c/n\). Since there are \(n-1\) possible incoming edges to each vertex, the expected indegree of one vertex is \[(n-1)\frac{c}{n} \approx c.\] Thus \(c\) represents the average indegree.
Let \(\rho_t\) be the fraction of active vertices at time \(t\). For example, \(\rho_t=0.25\) means that about \(25\%\) of the vertices are active.
Fix a typical vertex \(v\). A different vertex \(u\) gives an active input to \(v\) when \(u\) is active and the edge \(u\to v\) exists. This has probability approximately \[\rho_t\frac{c}{n}.\] Since there are about \(n-1\) possible choices of \(u\), the active in-neighbor count is approximately \[\operatorname{Binomial}\left(n-1,\frac{c\rho_t}{n}\right).\] For large \(n\), this is approximately \[\operatorname{Poisson}(c\rho_t).\]
Define \(\lambda=c\rho_t.\) Here \(\lambda\) is the expected number of active in-neighbors of a typical vertex.
Since a vertex turns on exactly when its number of active in-neighbors is prime, the next active density is approximately \[\rho_{t+1}=Q(c\rho_t),\] where \[Q(\lambda) = \mathbb{P}(\operatorname{Poisson}(\lambda)\text{ is prime}) = e^{-\lambda}\sum_{p\;\mathrm{prime}}\frac{\lambda^p}{p!}.\]
Near \(\rho=0\), the first prime contribution is \(p=2\), so \[Q(c\rho) \sim \frac{(c\rho)^2}{2}.\] Therefore very small activity tends to shrink rather than grow. In the mean-field model, the all-zero state is locally stable for every finite \(c\).
A nonzero fixed active density satisfies \[\rho=Q(c\rho).\] Writing \[\lambda=c\rho,\] we get \[\rho=Q(\lambda), \qquad c=\frac{\lambda}{Q(\lambda)}.\]
Theorem 12 (Mean-field threshold for positive fixed points).
Define \[\Phi(\lambda)=\sum_{p\;\mathrm{prime}}\frac{\lambda^p}{p!}, \qquad Q(\lambda)=e^{-\lambda}\Phi(\lambda), \qquad c(\lambda)=\frac{\lambda}{Q(\lambda)} \quad (\lambda>0).\] Then \(c(\lambda)\) has a unique global minimizer \[\lambda_\ast\approx 1.408509.\] At this point, \[\rho_\ast=Q(\lambda_\ast) \approx 0.368241, \qquad c_\ast=c(\lambda_\ast) \approx 3.824963.\] Equivalently, \(c_\ast\) is the global threshold for the existence of a positive solution of the mean-field fixed-point equation \[\rho=Q(c\rho).\] The minimizer is unique, although \(c(\lambda)\) may have additional critical points for larger values of \(\lambda\).
Proof sketch. By the preceding parameterization, the threshold is the global minimum of \(c(\lambda)\). Differentiation shows that its critical points satisfy \[\Omega(\lambda)= \lambda\Phi'(\lambda)-(1+\lambda)\Phi(\lambda)=0.\] One proves that \(\Omega\) has a unique zero in \((1,2)\), that this zero gives the global minimum, and that no \(\lambda\geq5\) gives a smaller value because \(c(\lambda)>\lambda\). The numerical values follow from solving the critical-point equation. Full details are given in Appendix 7. ◻
Remark 3. The theorem proves the global minimum of \(c(\lambda)\), not that \(\lambda_\ast\) is the only critical point on \((0,\infty)\). Additional critical points at larger \(\lambda\) do not affect the global threshold for positive fixed points of the mean-field map, because \(c(\lambda)\geq\lambda\).
Since \[c(\lambda)\to\infty \quad\text{as }\lambda\downarrow0 \qquad\text{and}\qquad c(\lambda)\to\infty \quad\text{as }\lambda\to\infty,\] continuity and the uniqueness of the global minimum imply that the mean-field fixed-point equation has no positive solution when \(c<c_\ast\), exactly one positive solution when \(c=c_\ast\), and at least two positive solutions when \(c>c_\ast\). The stability of these positive fixed points is not determined by the existence argument alone.
Proposition 13 (Local bistability above the threshold).
Let \[f_c(\rho)=Q(c\rho).\] There exists \(\varepsilon>0\) such that, for every \[c_\ast<c<c_\ast+\varepsilon,\] the map \(f_c\) has two positive fixed points near \(\rho_\ast\). The smaller branch is unstable, while the larger branch is locally asymptotically stable. Since \(\rho=0\) is also locally asymptotically stable, the mean-field map is bistable in this parameter range.
Proof sketch. At the threshold, the positive fixed point has multiplier \(1\), and the parameterization \(c=c(\lambda)\) has a nondegenerate local minimum. Consequently, two nearby positive branches appear for \(c>c_\ast\). The multiplier can be written as \[f_c'(\rho) = 1+\frac{\Omega(\lambda)}{\Phi(\lambda)}.\] Its sign relative to \(1\) shows that the lower branch is unstable and the upper branch is locally stable. The complete argument appears in Appendix 7. ◻
6 Conclusion↩︎
Pulse Graphs show that a single arithmetic totalistic rule can produce sharply different dynamical regimes depending on the underlying directed graph. Suitable sparse graphs support exponentially long attractors, while complete directed graphs collapse to fixed points and complement two-cycles with uniformly bounded transient time.
Several open problems remain. One is to narrow the gap between \[2^{n-3}-1 \leq L(n)\leq 2^n-1.\] Other questions include determining the exact values of \(L(n)\) for \(n\geq6\), describing the full set of periods realizable at fixed \(n\), and identifying graph structures that force either short or long attractors. On the probabilistic side, an important next step is to determine when the prime-Poisson approximation accurately predicts the finite-time behavior of sparse random Pulse Graphs.
Acknowledgments↩︎
I thank Professor Thotsaporn Thanatipanonda for helpful comments on an earlier draft.
7 Details of the Mean-Field Analysis↩︎
7.1 Proof of the mean-field threshold theorem↩︎
Proof of Theorem 12. Since \[c(\lambda)=\frac{\lambda e^\lambda}{\Phi(\lambda)},\] differentiation gives \[\begin{align} c'(\lambda) &= \frac{e^\lambda(1+\lambda)\Phi(\lambda) -\lambda e^\lambda \Phi'(\lambda)}{\Phi(\lambda)^2} \\ &= -\frac{e^\lambda}{\Phi(\lambda)^2} \left[ \lambda \Phi'(\lambda)-(1+\lambda)\Phi(\lambda) \right]. \end{align}\] Define \[\begin{align} \Omega(\lambda) &= \lambda \Phi'(\lambda)-(1+\lambda)\Phi(\lambda) \\ &= \sum_{p\;\mathrm{prime}} \lambda \, p\frac{\lambda^{p-1}}{p!} - \sum_{p\;\mathrm{prime}} (1+\lambda)\frac{\lambda^p}{p!}\\ &= \sum_{p\;\mathrm{prime}} (p-1-\lambda)\frac{\lambda^p}{p!}. \end{align}\] Then \[c'(\lambda) = -\frac{e^\lambda}{\Phi(\lambda)^2}\Omega(\lambda).\] Thus, \(c'(\lambda)\) has the opposite sign from \(\Omega(\lambda)\).
For \(0<\lambda\leq1\), every summand of \(\Omega(\lambda)\) is nonnegative, and the \(p=3\) summand is strictly positive. Hence \[\Omega(\lambda)>0 \qquad (0<\lambda\leq1),\] so \(c'(\lambda) < 0\) and \(c\) is strictly decreasing there.
We next prove that \(\Omega\) is strictly decreasing on \([1,5]\). For an integer \(k\geq1\), define \[g_k(\lambda) = \left(k-1-\lambda-\frac{\lambda}{k}\right) \frac{\lambda^{k-1}}{(k-1)!}.\] Then \[\Omega'(\lambda)=\sum_{p\;\mathrm{prime}}g_p(\lambda).\] For \(1\leq\lambda\leq5\) and \(k\geq7\), \[k-1-\lambda-\frac{\lambda}{k} \geq k-6-\frac{5}{k} \geq \frac{2}{7}>0.\] Therefore \(g_k(\lambda)\geq0\) for all \(k\geq7\), and hence \[\Omega'(\lambda) \leq g_2(\lambda)+g_3(\lambda)+g_5(\lambda) +\sum_{k=7}^{\infty}g_k(\lambda).\] If all positive integers are included instead of only primes, then \[\sum_{k=1}^{\infty}g_k(\lambda)=1-e^\lambda.\] Consequently, \[\Omega'(\lambda) \leq 1-e^\lambda+2\lambda-g_4(\lambda)-g_6(\lambda).\] Using \[e^\lambda\geq \sum_{j=0}^{6}\frac{\lambda^j}{j!},\] we obtain \[\Omega'(\lambda) \leq \frac{\lambda}{120}H(\lambda),\] where \[H(\lambda) = \lambda^5-6\lambda^4+20\lambda^3 -80\lambda^2-60\lambda+120.\]
Now we show \(H(\lambda)<0\) on \([1,5]\). For \(1\leq\lambda\leq5\), we have \[\lambda^2-6\lambda+20= (\lambda-3)^2+11 \leq15.\] Therefore \[\begin{align} H(\lambda) &= \lambda^3(\lambda^2-6\lambda+20) -80\lambda^2-60\lambda+120\\ &\leq 15\lambda^3-80\lambda^2-60\lambda+120\\ &= -5+(\lambda-1)(15\lambda^2-65\lambda-125). \end{align}\] Since \(0<\lambda\leq5\), we have \(\lambda^2\leq5\lambda\), and hence \[15\lambda^2-65\lambda-125 \leq 75\lambda-65\lambda-125= 10\lambda-125 \leq -75<0.\] Also, \(\lambda-1\geq0\). Consequently, \[(\lambda-1)(15\lambda^2-65\lambda-125)\leq0,\] so \[H(\lambda)\leq-5<0 \qquad(1\leq\lambda\leq5).\] Therefore \[\Omega'(\lambda)<0 \qquad(1\leq\lambda\leq5).\]
We have \(\Omega(1)>0\). Also, \[\Omega(2) = -2+ \sum_{\substack{p\geq5\\p\;\mathrm{prime}}} (p-3)\frac{2^p}{p!}.\] All terms in the remaining sum are nonnegative, so enlarging the sum to all integers \(k\geq4\) gives \[\Omega(2) \leq -2+\sum_{k=4}^{\infty}(k-3)\frac{2^k}{k!} = 7-e^2<0.\] Hence, because \(\Omega\) is strictly decreasing on \([1,5]\), it has a unique zero \[\lambda_\ast\in(1,2).\] This shows that \(c\) is strictly decreasing on \((0,\lambda_\ast)\) and strictly increasing on \((\lambda_\ast,5]\).
Finally, since \(Q(\lambda)\) is a probability, \[0<Q(\lambda)<1 \qquad(\lambda>0).\] Therefore \[c(\lambda)=\frac{\lambda}{Q(\lambda)}>\lambda.\]
Thus, \(c(\lambda)>5\) for every \(\lambda\geq5\). On the other hand, \[Q(1)=e^{-1}\sum_{p\;\mathrm{prime}}\frac{1^p}{p!}> e^{-1}\left(\frac{1}{2!}+\frac{1}{3!}\right) = \frac{2}{3e},\] so \[c(\lambda_\ast)< c(1)<\frac{3e}{2}<5.\] Therefore, no \(\lambda\geq5\) can satisfy \(c(\lambda)\leq c(\lambda_\ast)\). Hence \(\lambda_\ast\) is the unique global minimizer of \(c(\lambda)\). ◻
7.2 Proof of local bistability↩︎
Proof of Proposition 13. First, \(\rho=0\) is locally asymptotically stable. Indeed, \[Q(z)=\frac{z^2}{2}+O(z^3) \qquad (z\to 0),\] so \[f_c'(0)=cQ'(0)=0.\] Hence \[\lvert f_c'(0)\rvert<1.\]
Positive fixed points are parameterized by \[\rho(\lambda)=Q(\lambda), \qquad c(\lambda)=\frac{\lambda}{Q(\lambda)}.\] At \(\lambda=\lambda_\ast\), \[c'(\lambda_\ast)=0.\] Moreover, \[c'(\lambda) = -\frac{e^\lambda}{\Phi(\lambda)^2}\Omega(\lambda).\] Differentiating and using \(\Omega(\lambda_\ast)=0\) gives \[c''(\lambda_\ast) = -\frac{e^{\lambda_\ast}}{\Phi(\lambda_\ast)^2} \Omega'(\lambda_\ast).\] Since \(\Omega'(\lambda_\ast)<0\), \[c''(\lambda_\ast)>0.\] Thus \(c(\lambda)\) has a nondegenerate local minimum at \(\lambda_\ast\). Consequently, for every \(c>c_\ast\) sufficiently close to \(c_\ast\), there are two nearby solutions \[\lambda_-(c)<\lambda_\ast<\lambda_+(c)\] of \[c=c(\lambda).\] They produce two positive fixed points \[\rho_-(c)=Q(\lambda_-(c)), \qquad \rho_+(c)=Q(\lambda_+(c)).\]
To determine their stability, compute the fixed-point multiplier: \[\begin{align} f_c'(\rho) &=cQ'(\lambda) \\ &=\frac{\lambda Q'(\lambda)}{Q(\lambda)}. \end{align}\] Since \[Q(\lambda)=e^{-\lambda}\Phi(\lambda),\] we have \[\frac{Q'(\lambda)}{Q(\lambda)} = \frac{\Phi'(\lambda)}{\Phi(\lambda)}-1.\] Therefore \[\begin{align} f_c'(\rho) &= \lambda\frac{\Phi'(\lambda)}{\Phi(\lambda)}-\lambda \\ &= 1+\frac{\Omega(\lambda)}{\Phi(\lambda)}. \end{align}\]
At \(\lambda=\lambda_\ast\), \[f_{c_\ast}'(\rho_\ast)=1.\]
On the lower branch, \(\lambda_-<\lambda_\ast\), so \[\Omega(\lambda_-)>0.\] Hence \[f_c'(\rho_-) = 1+\frac{\Omega(\lambda_-)}{\Phi(\lambda_-)} >1,\] and \(\rho_-\) is unstable.
On the upper branch, \(\lambda_+>\lambda_\ast\), so \[\Omega(\lambda_+)<0,\] and therefore \[f_c'(\rho_+)<1.\] Because the multiplier is continuous and equals \(1\) at \(\lambda_\ast\), for \(\lambda_+\) sufficiently close to \(\lambda_\ast\) we also have \[-1<f_c'(\rho_+)<1.\] Thus \(\rho_+\) is locally asymptotically stable.
Therefore, for \(c>c_\ast\) sufficiently close to \(c_\ast\), both \(\rho=0\) and \(\rho=\rho_+(c)>0\) are locally stable, while the intermediate positive branch is unstable. Hence the mean-field map is locally bistable. ◻