Cultivating the Garden of Eden
Randall D. Beer · arXiv (Cornell University) · 2022
A finite pattern is a Garden of Eden for a cellular automaton if no configuration maps onto it in one step. This deposit contains a complete enumeration: exactly 342 of the patterns in an 11 x 11 box that are invariant under the full dihedral group D4 are Gardens of Eden for Conway's Life (B3/S23). The number resolves a discrepancy that Randall Beer records but leaves unexplained in "Cultivating the Garden of Eden" (Complex Systems 32(1):1-17, 2023; arXiv:2210.07837). Beer reports 41,702 sigma-90-symmetric 11 x 11 Gardens of Eden, "342 fewer than the 42,044 reported by HHKN" (Hartman, Heule, Kwekkeboom and Noels, Electron. J. Combin. 20(3) (2013), #P16), and separately notes that his D4-orbit-reduced count of 21,022 is "exactly half" of the HHKN figure. Those two observations are the same fact. Reducing the sigma-90-symmetric set S by the residual order-2 action (the diagonal reflection) gives, by Burnside's lemma, #orbits = (|S| + |Fix|)/2, where Fix is the fully D4-symmetric subset. With |S| = 41,702 and |Fix| = 342 both identities hold: 41,702 + 342 = 42,044 and (41,702 + 342)/2 = 21,022. So the figure 42,044 equals |S| + |Fix|. Whether that is an arithmetic slip or a different counting convention is not determined here. The alternative reading is refuted by Beer's own second number: had he omitted 342 patterns, his set would contain no fixed points and would reduce to 41,702/2 = 20,851 orbits, not the 21,022 he reports. The contribution is the direct enumeration of Fix, not the arithmetic. Imposing D4 symmetry on an 11 x 11 grid leaves 21 free cell orbits, so the space has 2^21 = 2,097,152 members; each was decided by one incremental SAT call against the 13 x 13 predecessor window, which is the complete finite encoding. Verification. The verifier passes its own calibration before judging: n = 8 and n = 9 both yield 0 D4-symmetric Gardens of Eden, matching the published statement that none exist, and the empty 11 x 11 pattern is correctly found reachable. For 200 sampled non-Gardens-of-Eden the predecessor returned by the solver was replayed through an independent, SAT-free Life simulator and reproduced the pattern in 200 cases out of 200 — an encoder reporting "no predecessor" too eagerly could not do that. As an unprompted cross-check, the sparsest of the 342 has exactly 45 live cells, matching the long-standing record value for fewest live cells in an 11 x 11 box. Populations run from 45 to 93, mean 72.0. No record is claimed: greedy minimisation of these 342 bottoms out at 113 specified cells, short of the standing 88. The counts 41,702 and 42,044 are quoted from the literature and are not re-derived.