# P2726: Exact spanning-set count for two-neighbor bootstrap percolation on the eight grid

- ID: `P2726`
- Reference: `bootstrap-percolation-eight-count`
- Page: https://theoremdb.org/statements/P2726
- Record maturity: Reviewed problem with recorded work

## 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.

### Remarks

- **Remark.** Boundary vertices retain their smaller grid degree.
- **Remark.** Monotonicity makes synchronous and asynchronous update orders yield the same closure.

### What counts as a solution

- Give the exact count with an independently checkable transfer-state certificate; a full count by initial cardinality is preferred.

## Status

Explicit spanning families give the lower bound, while four stable vacant boundary lines give the upper bound. [1](#reference-1)

## Work

### Evidence for the current status

**Computation 1 (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.

Let \(B_8\) denote the requested number. The certified result is
\[
177{,}024{,}301{,}925{,}259{,}284
\leq B_8\leq
18{,}161{,}310{,}923{,}858{,}378{,}752.
\]

For the lower bound, either long diagonal is a spanning set. A full occupied row together with a full occupied column also spans: each of the four resulting rectangles fills by induction on distance from the row-column cross. Inclusion-exclusion over these 66 sufficient patterns gives the displayed lower endpoint.

For the upper bound, an entirely vacant outer row or outer column remains vacant forever. Inclusion-exclusion over the four boundary lines shows that 285,433,149,851,172,864 initial sets have at least one such obstruction. Subtracting these from \(2^{64}\) gives the upper endpoint.

The exact value remains undetermined by this certificate.

### Background and intake notes

Exhaustive bitboard closure supplies exact values through board side four.

- Original intake status: Novelty remains unverified. No primary-source status audit was completed for the exact eight-board count.
- A transfer state must remember enough closure information across the frontier; recording only occupied boundary bits loses delayed infections.
- Complement symmetry supplies no relation between spanning and nonspanning sets.
- The size-refined polynomial provides stronger checksum data than the total alone.

- Recorded example: Every initial set containing all vertices trivially spans.

### Other known results

- **Theorem 1** (established): These finite families turn monotonicity into certified lower and upper counts. [1](#reference-1)

### Prior approaches

- **Route 1** (inconclusive): 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. [1](#reference-1)

### Runnable artifacts

- **Artifact 1** (reproduced): Standard-library Python checks every base pattern, evaluates the certified bounds, and reproduces the exact counts through side four. [1](#reference-1)

### 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.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `bootstrap-percolation-eight-count`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>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 https://doi.org/10.1088/0305-4470/21/19/017
   - 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
   - journal_article; primary source; version of record; checked 2026-08-01
   - Source use: original_summary
   - 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.