HEXAGONbeta

Linear-size autocatalytic sets are asymptotically absent in the sparse binary polymer model

Primarily AI-generated textHuman understanding: some partsmath.PR — Probabilitymath.CO — Combinatorics

Contributed by Michael Mislan ↗

Version 1 / Oct 20, 2026 / CC BY 4.0

Abstract

In the sparse binary polymer model with reversible ligation and cleavage, we prove that for every fixed food horizon, fixed nonnegative catalysis intensity and fixed linear reaction budget, the probability of a nonempty reflexively autocatalytic and food-generated set within that budget tends to zero, at rate O(1/n). The probability that a single molecule catalyses a self-constructing reaction set also vanishes, cleavage included. A productive-prefix argument excludes bounded catalyst counts, while an injective acyclic dependency encoding supplies a factorial saving in the count of productive reaction supports. Consequences include divergence of minimum RAF size relative to polymer length and of minimum catalyst count, together with conditional forms. Combining the lower bound with the published quadratic-witness result of Hordijk and Steel gives a superlinear-to-quadratic window. The principal estimates and consequences are formalized in Lean 4 against the literal split-position model; the published upper-witness input is cited separately.

Provenance statement

The text is primarily AI-generated. AI systems assisted the mathematical development, computations and Lean formalization under human direction; human understanding covers some parts of the work.

Formalizations

References

  1. de Moura, Leonardo; Ullrich, Sebastian. The Lean 4 theorem prover and programming language. Automated Deduction – CADE 28, vol. 12699, pp. 625–635. 2021DOI
  2. Hordijk, Wim; Steel, Mike. Detecting autocatalytic, self-sustaining sets in chemical reaction systems. Journal of Theoretical Biology, vol. 227, no. 4, pp. 451–461. 2004DOI
  3. Hordijk, Wim; Steel, Mike. Autocatalytic sets in polymer networks with variable catalysis distributions. Journal of Mathematical Chemistry, vol. 54, no. 10, pp. 1997–2021. 2016arXivDOI
  4. Hordijk, Wim; Steel, Mike. Chasing the tail: The emergence of autocatalytic networks. Biosystems, vol. 152, pp. 1–10. 2017DOI
  5. Hordijk, Wim; Kauffman, Stuart A.; Steel, Mike. Required levels of catalysis for emergence of autocatalytic sets in models of chemical reaction systems. International Journal of Molecular Sciences, vol. 12, no. 5, pp. 3085–3101. 2011DOI
  6. Hordijk, Wim; Hasenclever, Leonard; Gao, Jie; Mincheva, Dilyana; Hein, Jotun. An investigation into irreducible autocatalytic sets and power law distributed catalysis. Natural Computing, vol. 13, no. 3, pp. 287–296. 2014DOI
  7. Kauffman, Stuart A. Autocatalytic sets of proteins. Journal of Theoretical Biology, vol. 119, no. 1, pp. 1–24. 1986DOI
  8. Kauffman, Stuart A. The Origins of Order: Self-Organization and Selection in Evolution. Oxford University Press. 1993
  9. Mossel, Elchanan; Steel, Mike. Random biochemical networks: the probability of self-sustaining autocatalysis. Journal of Theoretical Biology, vol. 233, no. 3, pp. 327–336. 2005DOI
  10. Steel, Mike. The emergence of a self-catalysing structure in abstract origin-of-life models. Applied Mathematics Letters, vol. 13, no. 3, pp. 91–95. 2000DOI
Show all 12 referencesShow fewer references
  1. Steel, Mike; Hordijk, Wim; Xavier, Joana C. Autocatalytic networks in biology: structural theory and algorithms. Journal of the Royal Society Interface, vol. 16, no. 151, pp. 20180808. 2019DOI
  2. The mathlib Community. The Lean mathematical library. Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP 2020), pp. 367–381. 2020DOI

Version history

  1. v1Submitted by Michael MislanInitial depositCurrentOct 19, 2026