Zombie Compositions in Assembly Algebras and an Upper Bound on the Size of Chemical Space

Technical Summary: Zombie Compositions in Assembly Algebras and an Upper Bound on the Size of Chemical Space

Problem Statement
The paper addresses the fundamental question of how the number of constructible objects grows with construction complexity, a problem relevant to molecular chemistry, combinatorial design, and circuit complexity. Specifically, it critiques the existing framework for estimating the size of chemical space, notably the work of Morales Parra et al. [7], which posits a doubly-exponential upper bound on the number of molecules ($N(a)$) with assembly index $a$. The authors argue that the previously fitted growth exponent of approximately 0.73 overestimates the size of chemical space because it fails to account for the fact that a vast majority of combinatorially valid compositions are physically unrealizable due to valence and connectivity constraints.

Methodology
The authors introduce a general algebraic framework called construction systems, defined as tuples $(X, BB, \oplus, \nu)$ comprising a set of objects $X$, building blocks $BB$, an assembly operation $\oplus$, and a joining multiplicity $\nu$. The methodology proceeds through three main algebraic and combinatorial steps:

1. Toric Geometry and Matroids: The assembly process is mapped to a toric ideal $I_A$ and a toric variety $X_A$. The "rules" of any specific system (chemical, physical, or logical) are encoded as the binomial relations within this ideal. The authors associate a toric matroid $M$ and a block matroid $M^*$ to the system, where the rank of the matroid corresponds to the number of algebraically independent building block coordinates. Constraints on building blocks are shown to correspond to matroid operations (restriction and deletion).
2. Analytical Bounds: Using the design signature $(m, \nu, n_0)$ and the matroid rank, the authors derive analytical bounds on $N(a)$ without relying on enumerated databases. They establish that the growth exponent $\rho$ is bounded by $\log 2$.
3. The Composition Polytope and Zombie Exclusion: For systems with typed building blocks and valence bounds, the authors define a composition polytope $P_{val} \subset \mathbb{R}^m$. This polytope captures feasibility constraints via a single linear inequality involving degree demands and valence limits. Compositions outside this polytope are termed "zombies": they are combinatorially valid (satisfying the stars-and-bars count) but physically impossible. The authors utilize Ehrhart quasi-polynomials to count the integer points within $P_{val}$, providing an exact count of feasible compositions.

Key Contributions

• Algebraic Framework: The paper formalizes construction systems as objects in toric geometry, demonstrating that the "rules" governing object existence are intrinsic to the toric ideal rather than external constraints. It establishes that constraints on building blocks correspond to matroid operations on the block matroid.
• Exact Growth Exponent: The authors prove that for systems with vertex-identification joining (where $\nu(n_1, n_2) = n_1 n_2$), the exact doubly-exponential growth exponent is $\rho = \log 2 \approx 0.693$. This is derived by matching an upper bound from binary assembly trees with a lower bound obtained via Pólya enumeration of trees, replacing the previously fitted value of 0.73.
• Zombie Classification and Soundness: The paper introduces the concept of "zombie compositions" and proves the classification is sound (zero false positives): any composition declared a zombie is guaranteed to be physically unrealizable. The classification is also conservative, meaning the true infeasibility rate is at least as high as the polytope predicts.
• Refined Upper Bound: By replacing the naive stars-and-bars count with the Ehrhart count of the composition polytope, the authors derive a strictly tighter upper bound on $N(a)$.

Results

• Molecular Graph System ($m=19$): Applying the framework to the molecular graph assembly system (19 bond types, 5 atom types with valences 1–4), the authors identify that 9 of the 19 bond types are "zombie generators" (consuming more valence capacity than the connectivity bound allows).
• Zombie Fraction: The asymptotic fraction of zombie compositions is calculated to be 94.1% ($z_\infty \approx 0.941$). This implies that only about 6% of the composition space is chemically realizable.
• Numerical Impact: The difference between the fitted exponent (0.73) and the exact exponent ($\log 2 \approx 0.693$) results in a massive overcount in the doubly-exponential regime. At an assembly index of $a=10$, the previous bound exceeds the refined bound by a factor of $10^{198}$. At $a=30$, the overcount has 942 million digits.
• Computational Verification: The authors computed the exact number of feasible compositions ($EP(S)$) for sizes $S=1$ to $48$ using dynamic programming on the ceiling residues of the Ehrhart quasi-polynomial (period 12, degree 18). These results confirm the rapid convergence of the zombie fraction.

Significance
The paper claims that the composition polytope provides a substantially tighter and more accurate upper bound on the size of chemical space than previous methods. By identifying that 94% of the composition space consists of "zombies," the framework corrects the overestimation inherent in counting all combinatorial compositions. The result that the growth exponent is exactly $\log 2$ resolves the gap between lower and upper bounds, showing that the exponent is intrinsic to the binary assembly model and independent of fitted parameters. The authors emphasize that their framework is general, applicable to any construction system with finite building blocks and binary assembly, including bioorthogonal click-chemistry systems and combinatorial circuit design. The work concludes that the "zombie phenomenon" is a consequence of elementary valence arithmetic, not a computational artifact.