pith. sign in

arxiv: 2603.01008 · v2 · submitted 2026-03-01 · ❄️ cond-mat.stat-mech

Fixed points of Boolean networks with sparse connections

Pith reviewed 2026-05-15 18:43 UTC · model grok-4.3

classification ❄️ cond-mat.stat-mech
keywords fixed pointsBoolean networksphase transitionssparse graphscellular automatamean-field dynamicsconfiguration clusters
0
0 comments X

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.

The paper calculates the first and second moments of the number of fixed points in several cellular automata models on random sparse graphs with N sites. These moments stay finite as N grows large except exactly at the known transitions between a frozen phase, where only finitely many sites ever flip, and a fluctuating phase where a finite fraction keep changing. The singularities appear as divergences in the mean or variance on one or both sides of the transition and are tied to the mean-field dynamics or to how two copies of the system separate over time. In configuration space the fixed points form clusters that differ from one another on only a finite number of sites; there is always one cluster in the frozen phase but there can be several in the fluctuating phase, with extensive Hamming distance between different clusters. Within each cluster the differences are localized near short cycles whose influence dies out.

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

These are editorial extensions of the paper, not claims the author makes directly.

  • 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

Figures reproduced from arXiv: 2603.01008 by Ari M. Turner, Bernard Derrida, Guy Bunin, Stav Marcus.

Figure 1
Figure 1. Figure 1: Dynamics of the Kauffman model above and below Ccrit = 2. Simulations with N = 1500. (A) The number of active nodes. For C < Ccrit (here C = 1.5), this number may go to zero if a fixed point is reached, or in this simulation, to a small positive number. For C > Ccrit, it stabilizes on a finite fraction of the nodes. (B) The overlap goes close to ϕt = 1 for C < Ccrit, and for C > Ccrit fluctuates around som… view at source ↗
Figure 2
Figure 2. Figure 2: (A) [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Distribution of the number of FPs in the frozen phase. (A) Example of the subset I, of sites on which assignments change between FPs in the frozen phase. (B) The final P(Ω), theory (blue bars) against exhaustive searches after graph simplification (red points). Both panels are obtained by first applying the simplification algorithm (see main text) for instances with C = 1.5 and N = 5000 sites. site j → i f… view at source ↗
Figure 4
Figure 4. Figure 4: Examples of cycles that may affect the FP number in the Kauffman model. The functions are labeled on the arrows: [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The excitatory model. (A) The function q(ψ) for different values of C, above and below Ccrit = 1. (B) The first moment ⟨Ω⟩. (C) SCCs in the phase C < Ccrit. Each circle denotes an SCC, each containing a finite number of sites. (D) SCCs in the phase C > Ccrit include a giant SCC comprised of a finite fraction of the sites (large circle), and possibly a finite number of SCCs with a finite number of sites (sm… view at source ↗
Figure 6
Figure 6. Figure 6: The double-excitatory model. (A) The saddle-point function for ⟨Ω⟩ as a function of ψ, at C = 2, 3.35, 4. (B) ⟨Ω⟩ for the Double Excitatory model (black curve), and finite-N behavior. Solid curves are calculated from an exact evaluation of ⟨Ω⟩ when expressed as a sum, and crosses (with 1SE error bars) are the results of exhaustive searches at N = 5, 15, each averaged over 1000 disorder realizations. Dashed… view at source ↗
Figure 7
Figure 7. Figure 7: Analytical results for ⟨Ω⟩ and [PITH_FULL_IMAGE:figures/full_fig_p024_7.png] view at source ↗
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.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

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)
  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)
  1. [§2] §2 should list the concrete Boolean functions and update rules for each of the 'several models' mentioned in the abstract.
  2. [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

1 responses · 0 unresolved

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
  1. 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

0 steps flagged

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

0 free parameters · 1 axioms · 0 invented entities

The analysis rests on the standard large-N limit for random sparse graphs and on the existence of a well-defined mean-field description of the dynamics; no new entities are introduced and no parameters appear to be fitted inside the reported calculations.

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.
    This is the foundational setup stated in the abstract for all subsequent moment and cluster calculations.

pith-pipeline@v0.9.0 · 5555 in / 1500 out tokens · 26485 ms · 2026-05-15T18:43:13.318758+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

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

48 extracted references · 48 canonical work pages

  1. [1]

    stable core

    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. [2]

    close on itself

    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. [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. [4]

    off” and “on

    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. [5]

    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

    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. [6]

    As in the last section, this formula assumes multiple edges are not allowed, although this does not change the results forN >>1

    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. [7]

    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

    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. [8]

    Remove all sites that have no outgoing edges

  9. [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. [10]

    Also letψ00 = N00 N etc

    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. [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. [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

  13. [13]

    S. A. Kauffman. Metabolic stability and epigenesis in randomly constructed genetic nets.Journal of Theoretical Biology, 22(3):437–467, March 1969

  14. [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

  15. [15]

    Hopfield

    John J. Hopfield. Neural networks and physical systems with emergent collective computational abilities.Proceedings of the national academy of sciences, 79(8):2554–2558, 1982

  16. [16]

    Fisher and Pankaj Mehta

    Charles K. Fisher and Pankaj Mehta. The transition between the niche and neutral regimes in ecology.PNAS, 111(36):13111–13116, September 2014

  17. [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

  18. [18]

    Bastolla and G

    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

  19. [19]

    James F. Lynch. On the threshold of chaos in random Boolean cellular automata.Random Structures & Algorithms, 6(2-3):239–260, 1995

  20. [20]

    Derrida and G

    B. Derrida and G. Weisbuch. Evolution of overlaps between configurations in random Boolean networks.J.de Physique, 47:1297, 1986

  21. [21]

    Derrida and H

    B. Derrida and H. Flyvbjerg. Distribution of local magnetisations in random networks of automata.J. Phys. A, 20:L1107, 1987

  22. [22]

    Kauffman

    Stuart A. Kauffman. Metabolic stability and epigenesis in randomly constructed genetic nets.Journal of theoretical biology, 22(3):437–467, 1969

  23. [23]

    Bastolla and G

    U. Bastolla and G. Parisi. The modular structure of Kauffman networks.Physica D, 115:219, 1997

  24. [24]

    Socolar and S.A

    J.E.S. Socolar and S.A. Kauffman. Scaling in ordered and critical random Boolean networks.Physical Review Letters, 90:068702, 2003

  25. [25]

    Superpolynomial growth in the number of attractors in kauffman networks.Physical Review Letters, 90(9):098701, 2003

    Björn Samuelsson and Carl Troein. Superpolynomial growth in the number of attractors in kauffman networks.Physical Review Letters, 90(9):098701, 2003

  26. [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

  27. [27]

    Dynamicsofcritical Kauffmannetworksunder asynchronous stochasticupdate.Physical Review Letters, 95(4):048701, July 2005

    Florian Greiland BarbaraDrossel. Dynamicsofcritical Kauffmannetworksunder asynchronous stochasticupdate.Physical Review Letters, 95(4):048701, July 2005

  28. [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

  29. [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

  30. [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

  31. [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

  32. [32]

    Shnerb, and David A

    Yael Fried, Nadav M. Shnerb, and David A. Kessler. Alternative steady states in ecological networks.Phys. Rev. E, 96:012412, July 2017

  33. [33]

    Maximum number of fixed points in regulatory Boolean networks.Bulletin of Mathematical Biology, 70:1398, 2008

    Julio Aracena. Maximum number of fixed points in regulatory Boolean networks.Bulletin of Mathematical Biology, 70:1398, 2008

  34. [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

  35. [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

  36. [36]

    Flyvbjerg

    H. Flyvbjerg. An order parameter for networks of automata.J. Phys. A: Math. Gen., 21:L955, 1988

  37. [37]

    Flyvberg

    H. Flyvberg. Recent results for random networks of automata.Acta Physica Polonica B, 20(4):321

  38. [38]

    Random graphs

    Béla Bollobás. Random graphs. InModern graph theory, pages 215–252. Springer, 2011

  39. [39]

    Sudden emergence of a giant k-core in a random graph.Journal of Combinatorial Theory, Series B, 67:111, 1996

    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

  40. [40]

    Random tree recursions: Which fixed points correspond to tangible sets of trees?Random Structures and Algorithms, 56:796, 2020

    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

  41. [41]

    Greil and B

    F. Greil and B. Drossel. Kauffman networks with threshold functions.Eur. Phys. J. B, 57:109–113, 2007

  42. [42]

    Ari M. Turner. Fixed points of networks with sparse connections: The hybrid method (in preparation)

  43. [43]

    Corless, G.H

    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

  44. [44]

    Melzak.Companion to Concrete Mathematics

    Z.A. Melzak.Companion to Concrete Mathematics. John Wiley and Sons, New York, 1st edition, 1973

  45. [45]

    Pólya and R.C

    G. Pólya and R.C. Read.Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds. Springer Verlag, New York, 1st ed. edition, 1987

  46. [46]

    AMS CHelsea Publishing, Providence, 2nd edition, 2007

    László Lovász.Combinatorial Problems and Exercises. AMS CHelsea Publishing, Providence, 2nd edition, 2007. 29

  47. [47]

    Spencer.The Probabilistic Method

    Noga Alon and Joel H. Spencer.The Probabilistic Method. John Wiley and Sons, New York, 2nd ed. edition, 2000

  48. [48]

    Paul D. Hanna. Online Encyclopedia of Integer Sequences, sequence A134095.https://oeis.org/A134095