Pulse Graphs: Prime-Activated Boolean Dynamics on Directed Graphs

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-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\ge 6$, the construction is loopless, has maximum in-degree five, and uses only $O(n)$ edges. For odd $n\ge 7$, a period-3 control module improves the lower bound to \[ 3(2^{n-4}-1). \] 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 ρ_\ast\approx0.368241, \] with local bistability immediately above the threshold.

20 pages, 6 figures. Strengthened the upper bound, added an improved construction for odd n, expanded the related-work discussion, and streamlined the exposition