[#P2726] Exact spanning-set count for two-neighbor bootstrap percolation on the eight grid
Problem. On \(P_8\square P_8\), begin with an occupied set \(S\) and repeatedly occupy each vacant vertex having at least two occupied neighbors. Determine the exact number of initial sets whose closure is the entire board.
1Context
Exhaustive bitboard closure supplies exact values through board side four.
2Remarks
Remark 1. Boundary vertices retain their smaller grid degree.
Remark 2. Monotonicity makes synchronous and asynchronous update orders yield the same closure.
3What counts as a solution
- Give the exact count with an independently checkable transfer-state certificate; a full count by initial cardinality is preferred.
1Status
Current status (The spanning-set count lies between 177,024,301,925,259,284 and 18,161,310,923,858,378,752). Explicit spanning families give the lower bound, while four stable vacant boundary lines give the upper bound.[1]
1Records
Notes and companion material
Original intake status. UNKNOWN as of 2026-07-25. Explicit spanning families give the lower bound, while four stable vacant boundary lines give the upper bound. The checked sources do not settle the full acceptance condition.
- The dated packet audit checked the exact title, parameter, and the terminology used by the cited primary literature.
- The strongest recorded neighboring result is: Explicit spanning families give the lower bound, while four stable vacant boundary lines give the upper bound.
- The controlled TheoremDB corpus was checked for equivalent formulations and contains no duplicate published target.
Recorded example 1. Every initial set containing all vertices trivially spans.
Computational notes
- Exhaustive enumeration gave B_1=1, B_2=7, B_3=312, and B_4=50637. For the four by four board, the spanning counts by initial size 0 through 16 were 0,0,0,0,130,1464,4568,8408,10926,10564,7744,4320,1816,560,120,16,1; these sum to 50637.
How the 4 records connect
ProblemExact spanning-set count for two-neighbor bootstrap percolation on the eight grid
- Computation 1The spanning-set count lies between 177,024,301,925,259,284 and 18,161,310,923,858,378,752in this packetReproduced
- Theorem 1Two diagonals and 64 crosses span, while each vacant outer line is stablesupportsEstablished
- Artifact 1Deterministic closure verifier and inclusion-exclusion certificatesupportsReproduced
- Route 1The audit found asymptotic theory and no published exact eight-board countinformsInconclusive
2See also
How to cite
TheoremDB contributors, “Exact spanning-set count for two-neighbor bootstrap percolation on the eight grid,” TheoremDB research memory, snapshot of July 25, 2026. https://theoremdb.org/statements/bootstrap-percolation-eight-countThis page as plain text: bootstrap-percolation-eight-count.md
This problem includes 4 records joined by 4 typed links, sourced from doi.org[1], current as of July 25, 2026.
1References
- Packet source. M Aizenman and J L Lebowitz, “Metastability effects in bootstrap percolation”. Journal of Physics A: Mathematical and General 21(19) (1988), 3801-3813. DOI 10.1088/0305-4470/21/19/017. Aizenman and Lebowitz, Journal of Physics A 21 (1988), 3801-3813; Holroyd, Probability Theory and Related Fields 125 (2003), 195-224; Morris, Electronic Journal of Combinatorics 16 (2009), R2; targeted exact-count search completed 2026-07-25. ↗journal article · primary source · version of record · checked 2026-07-25Source use: original summary.The audit found asymptotic theory and no published exact eight-board count. Classical papers study finite-volume thresholds and internally spanned rectangles; a projected exact row transfer was stopped after its state count grew to 5,968.Also cited at Certified constructions and inclusion-exclusion in bpe8c-artifact-closure-and-bound-verifier.Also cited at Elementary induction and stability argument, replayed on every base pattern by bpe8c-artifact-closure-and-bound-verifier.Also cited at Inline CPython standard-library verifier prepared and executed on 2026-07-25.For Exact spanning-set count for two-neighbor bootstrap percolation on the eight grid: The audit found asymptotic theory and no published exact eight-board count. Classical papers study finite-volume thresholds and internally spanned rectangles; a projected exact row transfer was stopped after its state count grew to 5,968.Source named by the research packet.
Original CC0 finite percolation count.