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

Technische Samenvatting: Zombie-composities in Assemblage-algebraën en een Bovenwaartse Grens op de Grootte van de Chemische Ruimte

Probleemstelling
Het artikel behandelt de fundamentele vraag hoe het aantal constructeerbare objecten groeit met de constructiecomplexiteit, een probleem dat relevant is voor de moleculaire chemie, combinatorisch ontwerp en circuitcomplexiteit. Specifiek bekritiseert het de bestaande methodologie voor het schatten van de omvang van de chemische ruimte, met name het werk van Morales Parra et al. [7], dat een dubbel-exponentiële bovengrens stelt op het aantal moleculen ($N(a)$) met assemblage-index $a$. De auteurs stellen dat de eerder gefitte groeiexponent van ongeveer 0,73 de omvang van de chemische ruimte overschat omdat het geen rekening houdt met het feit dat een overweldigende meerderheid van de combinatorisch geldige composities fysiek onrealiseerbaar is vanwege valentie- en connectiviteitsbeperkingen.

Methodologie
De auteurs introduceren een algemeen algebraïsch kader genaamd constructiesystemen, gedefinieerd als tupels $(X, BB, \oplus, \nu)$ bestaande uit een verzameling objecten $X$, bouwstenen $BB$, een assemblage-operatie $\oplus$ en een verbindingsveelvoud $\nu$. De methodologie verloopt via drie hoofdzakelijke algebraïsche en combinatorische stappen:

1. Torische Meetkunde en Matroïden: Het assemblageproces wordt in kaart gebracht als een torische ideaal $I_A$ en een torische variëteit $X_A$. De "regels" van elk specifiek systeem (chemisch, fysiek of logisch) worden gecodeerd als de binomiale relaties binnen dit ideaal. De auteurs associëren een torische matroïde $M$ en een blokmatroïde $M^*$ met het systeem, waarbij de rang van de matroïde overeenkomt met het aantal algebraïsch onafhankelijke bouwsteencoördinaten. Beperkingen op bouwstenen blijken te corresponderen met matroïde-operaties (restrictie en deletie).
2. Analytische Grenzen: Gebruikmakend van de design-signatuur $(m, \nu, n_0)$ en de matroïde-rang, leiden de auteurs analytische grenzen af voor $N(a)$ zonder te vertrouwen op geënumereerde databases. Zij stellen vast dat de groeiexponent $\rho$ begrensd wordt door $\log 2$.
3. De Compositie-polytoop en Zombie-uitsluiting: Voor systemen met getypeerde bouwstenen en valentiebeperkingen definiëren de auteurs een compositie-polytoop $P_{val} \subset \mathbb{R}^m$. Deze polytoop legt de haalbaarheidsbeperkingen vast via een enkele lineaire ongelijkheid betreffende graad-eisen en valentielimieten. Composities buiten deze polytoop worden "zombies" genoemd: ze zijn combinatorisch geldig (voldoen aan de stars-and-bars telling), maar fysiek onmogelijk. De auteurs maken gebruik van Ehrhart-quasi-polynomen om de gehele punten binnen $P_{val}$ te tellen, wat een exacte telling van haalbare composities oplevert.

Belangrijkste Bijdragen

• Algebraïsch Kader: Het artikel formaliseert constructiesystemen als objecten in de torische meetkunde, en toont aan dat de "regels" die het bestaan van objecten sturen, intrinsiek zijn aan het torische ideaal in plaats van externe beperkingen. Het stelt vast dat beperkingen op bouwstenen corresponderen met matroïde-operaties op de blokmatroïde.
• Exacte Groeiexponent: De auteurs bewijzen dat voor systemen met vertex-identificatie verbinding (waar $\nu(n_1, n_2) = n_1 n_2$) de exacte dubbel-exponentiële groeiexponent $\rho = \log 2 \approx 0,693$ is. Dit is afgeleid door een bovengrens uit binaire assemblagebomen te matchen met een ondergrens verkregen via Pólya-enumeratie van bomen, waarbij de eerder gefitte waarde van 0,73 wordt vervangen.
• Zombie-classificatie en Soundness: Het artikel introduceert het concept van "zombie-composities" en bewijst dat de classificatie sound is (nul fout-positieven): elke compositie die als zombie wordt aangemerkt, is gegarandeerd fysiek onrealiseerbaar. De classificatie is ook conservatief, wat betekent dat de werkelijke onhaalbaarheidsgraad minstens zo hoog is als de polytoop voorspelt.
• Verfijnde Bovengrens: Door de naïeve stars-and-bars telling te vervangen door de Ehrhart-telling van de compositie-polytoop, leiden de auteurs een strikter hogere grens af voor $N(a)$.

Resultaten

• Moleculaire Graaf Systeem ($m=19$): Bij het toepassen van het kader op het moleculaire graaf-assemblagesysteem (19 bindingstypen, 5 atoomtypen met valenties 1–4), identificeren de auteurs dat 9 van de vingertien bindingstypen "zombie-generatoren" zijn (die meer valentiecapaciteit consumeren dan de connectiviteitsgrens toelaat).
• Zombie-fractie: De asymptotische fractie van zombie-composities wordt berekend als 94,1% ($z_\infty \approx 0,941$). Dit impliceert dat slechts ongeveer 6% van de compositieruimte chemisch realiseerbaar is.
• Numerieke Impact: Het verschil tussen de gefitte exponent (0,73) en de exacte exponent ($\log 2 \approx 0,693$) resulteert in een enorme overschatting in het dubbel-exponentiële regime. Bij een assemblage-index van $a=10$ overschrijdt de vorige bovengrens de verfijnde bovengrens met een factor $10^{198}$. Bij $a=30$ heeft de overschatting 942 miljoen cijfers.
• Computationele Verificatie: De auteurs hebben het exacte aantal haalbare composities ($EP(S)$) berekend voor matchen $S=1$ tot $48$ met behulp van dynamisch programmeren op de plafond-residuen van de Ehrhart-quasi-polynoom (periode 12, graad 18). Deze resultaten bevestigen de snelle convergentie van de zombie-fractie.

Significantie
Het artikel beweert dat de compositie-polytoop een aanzienlijk nauwkeurigere en strakkere bovengrens biedt op de omvang van de chemische ruimte dan eerdere methoden. Door te identificeren dat 94% van de compositieruimte uit "zombies" bestaat, corrigeert het kader de overschatting die inherent is aan het tellen van alle combinatorische composities. Het resultaat dat de groeiexponent exact $\log 2$ is, lost de kloof tussen de onder- en bovengrens op, waarbij wordt aangetoond dat de exponent intrinsiek is aan het binaire assemblage-model en onafhankelijk is van gefitte parameters. De auteurs benadrukken dat hun kader algemeen toepasbaar is op elk constructiesysteem met eindige bouwstenen en binaire assemblage, inclusief bioorthogonale click-chemie systemen en combinatorisch circuitontwerp. Het werk concludeert dat het "zombie-fenomeen" een gevolg is van elementaire valentie-arithmetica, en geen computationeel artefact.