Fixed points of Boolean networks with sparse connections
Pith reviewed 2026-05-15 18:43 UTC · model grok-4.3
The pith
Boolean networks on sparse random graphs have a finite number of fixed points except at phase transitions where the count becomes singular.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
In the large-N limit the first and second moments of the number of fixed points remain finite away from transitions but become singular at the transitions, with the form of the singularity governed by mean-field dynamics or the distance between replicated copies. Fixed points organize into clusters of configurations that agree except on finitely many sites, with a single cluster in the frozen phase and possibly multiple clusters separated by extensive distances in the fluctuating phase. The full distribution of the number of fixed points is obtained in the frozen phase.
What carries the argument
The first and second moments of the number of fixed points, together with the clustering of fixed points into groups that differ on only finitely many sites.
If this is right
- The location of the phase transition can be read off from the divergence of the mean or variance of the number of fixed points.
- In the fluctuating phase, fixed points belonging to different clusters differ on a macroscopic number of sites.
- Differences inside a cluster are produced by local changes near short cycles whose effect remains bounded.
- The full probability distribution of the number of fixed points is available throughout the frozen phase.
Where Pith is reading between the lines
- Away from transitions the finite expected number of fixed points suggests that exhaustive enumeration remains feasible for moderately large networks.
- The cluster structure implies that the set of fixed points has a tree-like organization in which local flips near cycles generate the variants inside each cluster.
- The same moment calculation may extend to counting periodic orbits by replacing the fixed-point condition with a period-k closure.
Load-bearing premise
The large-N limit on random sparse graphs produces well-defined phase transitions whose character is captured by mean-field dynamics or the distance between replicated copies of the system.
What would settle it
In a large finite network, count the fixed points on either side of the predicted transition point and check whether their average and variance remain bounded or diverge exactly where the mean-field calculation says they should.
Figures
read the original abstract
We study fixed points of cellular automata with $N$ sites on random sparse graphs. In the large $N$ limit such models are known to exhibit phase transitions, from a ``frozen'' phase, where at most a finite number of sites fluctuate at long times, to a ``fluctuating'' phase where a finite fraction of sites fluctuate. We consider several models, calculating the first and second moments of the number of fixed points, and find that these moments remain finite in the large $N$ limit, except at the transitions where they become singular. The singularities can take several forms, including divergence of the mean or variance of the number of fixed points, on one or both sides of the transition. The type of singularity is related to properties of the mean field dynamics or dynamics of the distance between copies of the system. In configuration space, we find that fixed points are organized into clusters, each consisting of sets of fixed points that agree with one another except for on a finite number of sites. In the frozen phase there is only one cluster, while in the fluctuating phase there may be multiple clusters. If there are multiple clusters, the distance between fixed points in different clusters is extensive. We show that the differences within the clusters correspond to local changes near short cycles in the directed graph of connections whose influence is eventually limited. In the frozen phase, we calculate the full distribution of the number of fixed points.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript studies fixed points of Boolean networks (cellular automata) with N sites on random sparse graphs. In the large-N limit, it computes the first and second moments of the number of fixed points for several models, finding these moments finite away from phase transitions between a frozen phase (at most finitely many fluctuating sites) and a fluctuating phase (finite fraction fluctuating). Singularities appear at the transitions, taking forms such as divergence of the mean or variance on one or both sides, linked to properties of mean-field dynamics or distances between replicated copies. Fixed points organize into clusters differing on finitely many sites; intra-cluster differences arise from local changes near short cycles. The frozen phase has one cluster and admits a full distribution of the number of fixed points; the fluctuating phase may have multiple clusters with extensive inter-cluster distances.
Significance. If the central calculations hold, the work supplies a controlled characterization of fixed-point statistics and their singularities in sparse Boolean networks, directly relating moment divergences to dynamical quantities and clarifying the cluster structure in configuration space. This strengthens the statistical-mechanics understanding of phase transitions in networked automata and supplies falsifiable predictions for the form of singularities.
major comments (1)
- [§4.2] §4.2, around Eq. (15): the second-moment calculation via replicated-system distance assumes the tree-like limit and does not bound the O(1) correction from short-cycle statistics; if these cycles induce an extra diverging contribution to the variance near the transition, the reported singularity type (e.g., divergence of variance on one side only) would change, and an explicit estimate or finite-N check is required.
minor comments (2)
- [§2] §2 should list the concrete Boolean functions and update rules for each of the 'several models' mentioned in the abstract.
- [Figure 3] Figure 3 caption: add a note on how the plotted moments were obtained (analytic vs. simulation) and include a small-N comparison panel.
Simulated Author's Rebuttal
We thank the referee for the detailed and constructive report. We address the single major comment below and have revised the manuscript to incorporate a clarification.
read point-by-point responses
-
Referee: [§4.2] §4.2, around Eq. (15): the second-moment calculation via replicated-system distance assumes the tree-like limit and does not bound the O(1) correction from short-cycle statistics; if these cycles induce an extra diverging contribution to the variance near the transition, the reported singularity type (e.g., divergence of variance on one side only) would change, and an explicit estimate or finite-N check is required.
Authors: We agree that the second-moment calculation is performed under the tree-like approximation valid in the large-N limit. Short cycles are present with O(1) total number in the ensemble and contribute O(1) corrections to the number of fixed points. These corrections arise from local rearrangements whose spatial extent is bounded by the cycle length (typically O(log N) with exponentially small probability) and do not couple to the diverging fluctuations of the replicated distance that produce the singularity. Consequently, they remain finite on both sides of the transition and cannot alter the functional form of the divergence in the variance. We have added a short paragraph in §4.2 that explicitly bounds the cycle contribution by the maximum local neighborhood size and notes consistency with the finite-N numerics already shown in the appendix. A full finite-N scaling analysis of cycle effects lies outside the present scope but is not expected to change the leading singularity. revision: partial
Circularity Check
No circularity: moments and cluster structure derived directly from model dynamics on sparse graphs
full rationale
The paper defines Boolean networks on random sparse graphs and computes the first and second moments of fixed-point counts via mean-field dynamics and replicated-copy distances. These quantities are obtained from the transition rules and graph ensemble without fitting parameters to the target moments or reducing them to prior self-citations that carry the central claim. Cluster organization follows from local cycle perturbations whose influence remains finite, again without self-referential closure. The singularities at phase transitions emerge from the same dynamical equations rather than being presupposed. No load-bearing step equates an output to an input by construction.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption In the large-N limit on random sparse graphs the models exhibit a sharp frozen-to-fluctuating phase transition whose character is captured by mean-field dynamics or the distance between replicated copies.
Lean theorems connected to this paper
-
IndisputableMonolith/Cost/FunctionalEquation.leanwashburn_uniqueness_aczel unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
ϕ_{t+1}=q(ϕ_t) with q(ϕ)=½[1+e^{C(ϕ−1)}]; saddle-point evaluation of ⟨Ω⟩ and ⟨Ω²⟩ via A(ϕ)
-
IndisputableMonolith/Foundation/AlexanderDuality.leanalexander_duality_circle_linking unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
fixed points organized into clusters differing on finite sets of sites near short cycles; full P(Ω) from Poisson cycle counts in frozen phase
What do these tags mean?
- matches
- The paper's claim is directly supported by a theorem in the formal canon.
- supports
- The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
- extends
- The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
- uses
- The paper appears to rely on the theorem as machinery.
- contradicts
- The paper's claim conflicts with a theorem or certificate in the canon.
- unclear
- Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.
Reference graph
Works this paper leans on
-
[1]
The graph structure of sites differing between FPs Suppose we have two FPs,x,y, that differ from each other on a finite subsetIof sites. The graph onIhas a special structure, illustrated in Fig. 3(A). To see the structure, start from some sitei∈I. Sincexi̸=yi, there must be a 8 A B Figure 3.Distribution of the number of FPs in the frozen phase.(A) Example...
-
[2]
The number of FPs on a finite cycle We can now count the number of fixed points, by considering only the number of FPs in the simplified graph. We will find that it is related to the number of short cycles of certain types. (Ref. [22] found bounds on the number of fixed points in the fluctuating phase using cycles in a similar way.) Although the simplifie...
-
[3]
The full FP number distribution in the frozen phase We consider a cycle in the graph describing the system, of lengthn. What is the probability that it is in the reduced graph, and that it has 0 or 2 fixed points? Every site that gives an input to the cycle will be eliminated during the reduction process3, so the values of these inputs are fixed. So we ca...
-
[4]
The structure of FPs in the fluctuating phase Some of the ideas just considered are also helpful for understanding fixed points in the fluctuating phase, although they do not lead to the full distribution function. The two contributions to⟨Ω2⟩, namely⟨Ω2⟩near and⟨Ω2⟩far,count pairs of fixed points with a full overlap or a partial overlap ofϕ∗respectively....
-
[5]
Dynamics Letψn be the mean magnetization (fraction of variables withxi = 1) at timen. The dynamical update rule reads ψt+1 = ∞∑ k=0 Pk [ 1−(1−ψt)k−kψt (1−ψt)k−1 ] , whereP k is the probability forkincoming edges. For a Poisson distribution,Pk =e−CCk/k!, so ψt+1 =q(ψt) = 1−e−Cψt (Cψt + 1) This always has a fixed-point solution. ForC < Ccrit≃3.35, theψ= 0so...
-
[6]
Counting FPs The first moment,⟨Ω⟩, is given by ⟨Ω⟩= ∞∑ N1=0 ( N N1 ) [ (1−C/N)N1 +N 1 C N (1−C/N)N1−1 ]N−N1 [ 1−(1−C/N)N1 −N1 (1−C/N)N1−1C N ]N1 ≡ ∞∑ N1=0 ΩN1 The first two terms are to be interpreted asΩN∗=0 = 1andΩ N∗=1 = 0. As in the last section, this formula assumes multiple edges are not allowed, although this does not change the results forN >>1. W...
-
[7]
Remove all sitesithat have no incoming edges, and all outgoing edges from these sites (including the vertices that they point toward). This can be done because a siteiwith no inputs will havexi = 1at all FPs, and if siteiis an input to sitejthen at all FPsx j = 0, so sitejdoes not affect any other site
-
[8]
Remove all sites that have no outgoing edges
-
[9]
A site that is on will stay on if all inputs are off
1st moment Consider a configuration withN1 sites that are on andN−N1 that are off, and determine the probability that it will be a fixed point when the connections are assigned. A site that is on will stay on if all inputs are off. The probability is ( 1−N1 N )k when there arekinputs. Hence q(ψ) = ∞∑ k=0 e−CCk k! (1−N1 N )k =e−Cψ.(G1) (This assumes the gr...
-
[10]
2nd moment Take two configurations, withN00,N 10,N 01,N 11 the numbers of sites with the pairs of values00,10,01,11. Also letψ00 = N00 N etc. The probability that this is a fixed point isqN00 00 qN01 01 qN10 10 qN11 11 whereq 00 is the probability that the inputs to a site would cause it to become 00 at the next step, etc. Then q11 = ∞∑ k=0 e−CCk k! ψk 00...
-
[11]
The time dependence of the magnetization changes its behavior atCcrit
Dynamics Now we consider the dynamics briefly. The time dependence of the magnetization changes its behavior atCcrit. To see this, note that a fixed pointψ∗ofψ→q(ψ)is attractive if|q′(ψ∗)|<1. Calculatingq′(ψ∗)from Eq. (G1) and the value ofψ∗, one sees that the deriveq′(ψ∗)is between−1and 0 whenC < eand is less than -1 whenC > e. Hence the fixed point begi...
-
[12]
World Scientific Publishing Co
Marc Mézard, Giorgio Parisi, and Miguel Virasoro.Spin Glass Theory and Beyond: An Introduction to the Replica Method and Its Applications, volume 9. World Scientific Publishing Co. Inc., 1987
work page 1987
-
[13]
S. A. Kauffman. Metabolic stability and epigenesis in randomly constructed genetic nets.Journal of Theoretical Biology, 22(3):437–467, March 1969
work page 1969
-
[14]
Homeostasis and differentiation in random genetic control networks.Nature, 224(5215):177–178, 1969
Stuart Kauffman. Homeostasis and differentiation in random genetic control networks.Nature, 224(5215):177–178, 1969
work page 1969
- [15]
-
[16]
Charles K. Fisher and Pankaj Mehta. The transition between the niche and neutral regimes in ecology.PNAS, 111(36):13111–13116, September 2014
work page 2014
-
[17]
Dynamical phase transition in nonsymmetric spin glasses.J
B Derrida. Dynamical phase transition in nonsymmetric spin glasses.J. Phys. A: Math. Gen., 20(11):L721–L725, August 1987
work page 1987
-
[18]
U. Bastolla and G. Parisi. Relevant elements, magnetization and dynamical properties in Kauffman networks: A numerical study.Physica D: Nonlinear Phenomena, 115(3):203–218, May 1998
work page 1998
-
[19]
James F. Lynch. On the threshold of chaos in random Boolean cellular automata.Random Structures & Algorithms, 6(2-3):239–260, 1995
work page 1995
-
[20]
B. Derrida and G. Weisbuch. Evolution of overlaps between configurations in random Boolean networks.J.de Physique, 47:1297, 1986
work page 1986
-
[21]
B. Derrida and H. Flyvbjerg. Distribution of local magnetisations in random networks of automata.J. Phys. A, 20:L1107, 1987
work page 1987
- [22]
-
[23]
U. Bastolla and G. Parisi. The modular structure of Kauffman networks.Physica D, 115:219, 1997
work page 1997
-
[24]
J.E.S. Socolar and S.A. Kauffman. Scaling in ordered and critical random Boolean networks.Physical Review Letters, 90:068702, 2003
work page 2003
-
[25]
Björn Samuelsson and Carl Troein. Superpolynomial growth in the number of attractors in kauffman networks.Physical Review Letters, 90(9):098701, 2003
work page 2003
-
[26]
Stable and unstable attractors in Boolean networks.Physical Review E, 72(5):055101, November 2005
Konstantin Klemm and Stefan Bornholdt. Stable and unstable attractors in Boolean networks.Physical Review E, 72(5):055101, November 2005
work page 2005
-
[27]
Florian Greiland BarbaraDrossel. Dynamicsofcritical Kauffmannetworksunder asynchronous stochasticupdate.Physical Review Letters, 95(4):048701, July 2005
work page 2005
-
[28]
Basin entropy in Boolean network ensembles.Physical Review Letters, 98(15):158701, April 2007
Peter Krawitz and Ilya Shmulevich. Basin entropy in Boolean network ensembles.Physical Review Letters, 98(15):158701, April 2007
work page 2007
-
[29]
Scaling in critical random Boolean networks.Physical Review E, 72:046124, 2005
Viktor Kaufman, Tamara Mihaljev, and Barbara Drossel. Scaling in critical random Boolean networks.Physical Review E, 72:046124, 2005
work page 2005
-
[30]
Scaling in a general class of critical random Boolean networks.Phys
Tamara Mihaljev and Barbara Drossel. Scaling in a general class of critical random Boolean networks.Phys. Rev. E, 74:046101, 2006
work page 2006
-
[31]
T. M. A. Fink and F. C. Sheldon. Number of attractors in the critical kauffman model is exponential.Phys. Rev. Lett., 131:267402, Dec 2023
work page 2023
-
[32]
Yael Fried, Nadav M. Shnerb, and David A. Kessler. Alternative steady states in ecological networks.Phys. Rev. E, 96:012412, July 2017
work page 2017
-
[33]
Julio Aracena. Maximum number of fixed points in regulatory Boolean networks.Bulletin of Mathematical Biology, 70:1398, 2008
work page 2008
-
[34]
Random networks of automata: A simple annealed approximation.Europhys
B Derrida and Y Pomeau. Random networks of automata: A simple annealed approximation.Europhys. Lett., 1(2):45–49, January 1986
work page 1986
-
[35]
Number 73 in Cambridge Studies in Advanced Mathematics
Béla Bollobás.Random Graphs. Number 73 in Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge; New York, 2nd edition, 2001
work page 2001
- [36]
- [37]
-
[38]
Béla Bollobás. Random graphs. InModern graph theory, pages 215–252. Springer, 2011
work page 2011
-
[39]
Boris Pittel, Joel Spencer, and Nicholas Wormald. Sudden emergence of a giant k-core in a random graph.Journal of Combinatorial Theory, Series B, 67:111, 1996
work page 1996
-
[40]
Tobias Johnson, Moumanti Podder, and Fiona Skerman. Random tree recursions: Which fixed points correspond to tangible sets of trees?Random Structures and Algorithms, 56:796, 2020
work page 2020
-
[41]
F. Greil and B. Drossel. Kauffman networks with threshold functions.Eur. Phys. J. B, 57:109–113, 2007
work page 2007
-
[42]
Ari M. Turner. Fixed points of networks with sparse connections: The hybrid method (in preparation)
-
[43]
R.M. Corless, G.H. Gonnet, D.E.G. Hare, D.J. Jeffrey, and D.E. Knuth. On the LambertWfunction.Advances in Computational Mathematics, 5:326, 1996
work page 1996
-
[44]
Melzak.Companion to Concrete Mathematics
Z.A. Melzak.Companion to Concrete Mathematics. John Wiley and Sons, New York, 1st edition, 1973
work page 1973
-
[45]
G. Pólya and R.C. Read.Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds. Springer Verlag, New York, 1st ed. edition, 1987
work page 1987
-
[46]
AMS CHelsea Publishing, Providence, 2nd edition, 2007
László Lovász.Combinatorial Problems and Exercises. AMS CHelsea Publishing, Providence, 2nd edition, 2007. 29
work page 2007
-
[47]
Spencer.The Probabilistic Method
Noga Alon and Joel H. Spencer.The Probabilistic Method. John Wiley and Sons, New York, 2nd ed. edition, 2000
work page 2000
-
[48]
Paul D. Hanna. Online Encyclopedia of Integer Sequences, sequence A134095.https://oeis.org/A134095
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.