RAF Theory

Reflexively Autocatalytic, Food-generated Sets — A Formal Review

1. The Computational Surprise

The naïve approach to detecting self-sustaining subsets of a reaction network requires checking all 2|R| subsets—exponential in the number of reactions. Each subset must be tested for simultaneous F-generation and autocatalysis, properties that depend on the closure operator, itself iterative.

Hordijk & Steel (2004) showed this collapses to polynomial time. The mechanism: a fixed-point pruning algorithm that iteratively removes reactions failing the RAF conditions. Because each iteration removes at least one reaction, and removal is monotone (removing a reaction can only shrink the closure, never enlarge it), the algorithm converges in at most |R| iterations.

The transition from 2|R| to O(|R|2 · |X|) is not merely an optimisation. It means the question "does this system sustain itself?" is tractable—a structural property of the RAF definition, not an algorithmic trick.

The monotonicity is essential: if R′ ⊆ R″ then clR′(F) ⊆ clR″(F). This makes the pruning operator a monotone map on a finite lattice, guaranteeing a unique greatest fixed point—the maxRAF.

2. Formal Framework

Definition 1 (Catalytic Reaction System)

A CRS is a triple Q = (X, R, C) where:

Definition 2 (Food Set)

F ⊆ X is a designated subset of molecule types assumed freely available from the environment. Food molecules are never consumed—they constitute the boundary conditions of the system.

Definition 3 (Closure)

Given R′ ⊆ R, the closure clR′(F) is the smallest superset of F closed under reactions in R′. Constructively:

W0 = F
Wi+1 = Wi ∪ { π(r) : r ∈ R′, ρ(r) ⊆ Wi }
clR′(F) = ∪i≥0 Wi

Convergence in at most |X| steps (each step adds ≥1 molecule type, or terminates).

Definition 4 (RAF)

A subset R′ ⊆ R is a Reflexively Autocatalytic, F-generated set (RAF) if:

  1. F-generated: ∀ r ∈ R′ : ρ(r) ⊆ clR′(F)
  2. Reflexively autocatalytic: ∀ r ∈ R′ : ∃ x ∈ clR′(F) such that (x, r) ∈ C

Both conditions reference the same closure—this is the self-referential character that makes RAF detection non-trivial.

3. Example CRS

Consider the following system with X = {f1, f2, a, b, c, p, q}, food F = {f1, f2}:

ReactionReactantsProductsCatalyst
r1f1 + f2ab
r2aba
r3f1ca
r4pqq

Analysis

Closure: clR(F) = {f1, f2, a, b, c}. Reaction r4 requires p ∈ ρ(r4), but p ∉ clR(F)—it cannot fire.

maxRAF = {r1, r2, r3}. All three are F-generated and catalyzed within the closure.

irrRAF = {r1, r2}. This is the autocatalytic core: r1 produces a (catalyzed by b), r2 produces b (catalyzed by a). Mutual dependency — neither alone is a RAF.

Piggybacking: r3 is in the maxRAF but not in any irrRAF. It depends on molecule a (as catalyst) produced by the core, but contributes nothing back. Remove it and {r1, r2} remains a RAF.

f₁ f₂ r₁ a r₂ b r₃ c p r₄ q NOT F-GENERATED maxRAF = {r₁, r₂, r₃} Legend Food Product Reaction Catalysis

4. The Detection Algorithm

The maxRAF algorithm is a greatest fixed-point computation. Starting from the full reaction set, it iteratively prunes reactions that violate RAF conditions:

function maxRAF(X, R, C, F):
    R' ← R                          // start with all reactions
    repeat:
        changed ← false
        W ← closure(R', F)          // compute cl_{R'}(F)
        for each r ∈ R':
            if ρ(r) ⊄ W:              // not F-generated
                R' ← R' \ {r}
                changed ← true
            else if ∄ x ∈ W : (x,r) ∈ C:  // no catalyst available
                R' ← R' \ {r}
                changed ← true
    until ¬changed
    return R'                        // maxRAF (possibly ∅)

function closure(R', F):
    W ← F
    repeat:
        W' ← W ∪ { π(r) : r ∈ R', ρ(r) ⊆ W }
        if W' = W: return W
        W ← W'

Complexity: The outer loop runs at most |R| times (each pass removes ≥1 reaction or terminates). Each pass computes closure in O(|R| · |X|) and checks each reaction in O(|X|). Total: O(|R|2 · |X|).

Algorithm Step-Through

Step 0
Click "Next Step" to begin the algorithm on the example CRS.
r₁ f₁ + f₂ → a cat: b r₂ a → b cat: a r₃ f₁ → c cat: a r₄ p → q cat: q Closure: {f₁, f₂} R′: {r₁, r₂, r₃, r₄}

5. Key Theorems

Theorem 1 (Uniqueness of maxRAF)

Every CRS (X, R, C) with food set F has a unique maximal RAF (possibly empty).

Proof sketch: Let R1, R2 both be RAFs. Then R1 ∪ R2 is also a RAF: clR1∪R2(F) ⊇ clRi(F) for each i, so all reactants remain available and all catalysts remain in the closure. The union of all RAFs is therefore the unique maximum. □

Theorem 2 (Polynomial Detection)

The maxRAF of a CRS can be found in O(|R|2 · |X|) time.

Proof: The pruning algorithm makes at most |R| passes (removing ≥1 reaction per pass). Each pass: closure computation in O(|R| · |X|), plus checking each reaction against the closure in O(|X|). Correctness: the algorithm computes the greatest fixed point of the operator Φ(R′) = {r ∈ R′ : ρ(r) ⊆ clR′(F) ∧ ∃x ∈ clR′(F), (x,r) ∈ C}. By monotonicity (Tarski), this fixed point equals the maxRAF. □

Theorem 3 (Phase Transition)

In a random CRS with n molecule types and catalysis probability p (each molecule catalyzes each reaction independently with probability p):

P(RAF exists) transitions sharply from ≈0 to ≈1 at p ∼ 1/n

In the binary polymer model with maximum length t: threshold at p ∼ 1/(n · √|R|).

This is Kauffman's (1986) original conjecture, proved rigorously by Mossel & Steel (2005) for certain model classes and by simulation for others. The sharpness of the transition increases with n.

Theorem 4 (Sub-RAF Lattice)

The collection of all RAFs of a CRS forms a partially ordered set under set inclusion, with the maxRAF as the unique maximum element. The minimal non-empty elements are the irreducible RAFs (irrRAFs).

Definition 5 (Irreducible RAF)

A RAF R′ is irreducible (an irrRAF) if it contains no proper non-empty sub-RAF. Equivalently: removing any single reaction from R′ destroys the RAF property.

Definition 6 (Constructively Autocatalytic F-generated set — CAF)

A RAF R′ is a CAF if there exists an ordering r1, r2, …, rk of R′ such that for each i:

  1. ρ(ri) ⊆ F ∪ ∪j<i π(rj)
  2. ∃ x ∈ F ∪ ∪j<i π(rj) with (x, ri) ∈ C

Every CAF is a RAF. Not every RAF is a CAF—a RAF may require circular catalytic dependencies that have no constructive unfolding. CAFs avoid the "chicken-and-egg" problem: each reaction can fire using only products of earlier reactions plus food.

In the example: {r1, r2} is a RAF but NOT a CAF (r1 needs b as catalyst, which requires a, which requires r1). This mutual dependency is exactly the autocatalytic cycle.

Sub-RAF Lattice for the Example

maxRAF {r₁, r₂, r₃} irrRAF {r₁, r₂} ∅ r₃ piggybacks: in maxRAF, not in any irrRAF

6. Phase Transition Demo

Adjust the catalysis probability p to observe the sharp transition. At low p, no RAF exists. Near the threshold (~0.10–0.15 for this network), a RAF suddenly emerges and grows. This is the Kauffman phase transition in miniature.

0.000
maxRAF: 0/20 reactions

7. The 11-Domain Instance

Application of RAF theory to an 11-domain scientific network. The question: which subsets of domains form self-sustaining intellectual ecosystems, where each domain's development is catalyzed by insights from other domains within the closure?

1 Topology 2 TQFT 3 Condensed Matter 4 TQC 5 Solitons 6 Criticality 7 Autocatalysis KEYSTONE 8 Autopoiesis 9 Cellular Automata 10 Parallel Computation 11 Materials min RAF {1,6,7} min RAF {6,7,9} Cluster A: {1,2,3,4} 5/5 internal reactions

Results Summary

PropertyValue
Full network RAF10/10 reactions in maxRAF
Minimal non-trivial RAFs{1, 6, 7} and {6, 7, 9}
Keystone domain7 (Autocatalysis) — removal collapses ALL non-trivial RAFs
Cluster A internal RAF{1, 2, 3, 4} — 5/5 reactions, self-contained cycle

Emergent Property Stack

LoopDomainsEmergent Property
Dynamics triad{6, 7, 9} + 8, 10Spontaneous computation
Core triad{1, 6, 7} + 5Protected self-organization
Topological cycle{1, 2, 3, 4}Topological computation
Instantiation+ 11Physical reality
Full stackAll 11Conditions for the Flat
Domain 7 (Autocatalysis) appears in both minimal RAFs. Its removal disconnects the catalytic support for every non-trivial self-sustaining subset. This is the formal expression of "keystone" — a single-point-of-failure in the RAF lattice.

8. References

  1. Kauffman, S. A. (1971). Cellular Homeostasis, Epigenesis and Replication in Randomly Aggregated Macromolecular Systems. J. Cybernetics 1(1): 71–96.
  2. Kauffman, S. A. (1986). Autocatalytic sets of proteins. J. Theoretical Biology 119: 1–24.
  3. Kauffman, S. A. (1993). The Origins of Order: Self-Organization and Selection in Evolution. Oxford University Press.
  4. Hordijk, W. & Steel, M. (2004). Detecting autocatalytic, self-sustaining sets in chemical reaction systems. J. Theoretical Biology 227: 451–461.
  5. Hordijk, W., Steel, M. & Kauffman, S. (2010). The structure of autocatalytic sets: Evolvability, enablement, and emergence. Acta Biotheoretica 67: 269–281.
  6. Steel, M. (2000). The emergence of a self-catalysing structure in abstract origin-of-life models. Applied Mathematics Letters 3: 91–95.
  7. Mossel, E. & Steel, M. (2005). Random biochemical networks: The probability of self-sustaining autocatalysis. J. Theoretical Biology 233: 327–336.
RAF Tutorial — Self-contained review for the working physicist. No external dependencies.