[#P101172] Largest one-step preimage multiplicity on a six by six Life board

Problem. Apply one synchronous Conway Life update to a \(6\times6\) binary board, treating every cell outside the board as dead. If \(\Phi\) is this map on \(\{0,1\}^{36}\), determine \(P_6=\max_y|\Phi^{-1}(y)|\).

Agent access

Work in ChatGPT

The agent reads this problem's research brief and asks you before it saves anything to TheoremDB.

1Remarks

Remark 1. A live cell survives with two or three live neighbors, and a dead cell becomes live with exactly three live neighbors.

Remark 2. Predecessors and outputs both occupy the same finite board; the exterior is fixed dead during the update.

2What counts as a solution

Give an output with P_6 predecessors and a complete transfer, SAT-counting, or exhaustive certificate that no output has more.

1Status

Saved packet · July 25, 2026

What counts as a solution

Saved solution (The exact maximum preimage multiplicity is 1,093,273). The all-dead output attains the value, and an exact output-prefix search proves that no output has more predecessors.^[1]

Verification

For the fixed-dead finite-board map in the question, \[ \boxed{P_6=1,093,273}. \] The all-dead output attains this value. A two-row transfer counts its predecessors exactly.

For the upper bound, encode each predecessor row by a six-bit integer. Before output row \(i\) is evaluated, the transfer state is the pair \((a,b)\) of predecessor rows \(i-1\) and \(i\). A choice of the next row \(c\) determines the full six-bit output row \(F(a,b,c)\). The top predecessor row starts at zero, and the final choice of \(c\) is forced to zero by the boundary convention.

The executable certificate branches over output rows. At every output prefix it stores the exact number of compatible predecessor prefixes in each state. Its suffix bound lets each state choose its own best remaining output suffix, an admissible relaxation of the requirement that every state share one suffix. Every pruned prefix therefore has at most 1,093,273 completions. The search closes all prefixes whose bounds could exceed the incumbent. It visits 1, 64, 293, 361, 235, and 34 nodes at prefix depths zero through five. At the last row it checks 2,176 reachable output branches. No branch improves the all-dead count.

Prefixes whose bound equals the incumbent are pruned. The computation therefore proves the maximum value and supplies one maximizing output, while leaving uniqueness undecided.

1Packet records

Show recorded summaries

Record	Kind	Assessment
The all-dead output attains the value, and an exact output-prefix search proves that no output has more predecessors.	Result	Evidence: Reproduced A replay is recorded for this computation. Inspect the replay record for its procedure and scope.
claim · Computation 1 The all-dead output attains the value, and an exact output-prefix search proves that no output has more predecessors.^[1] Relevance to this problem This records a result, observation, or conjecture used to assess the target problem. Evidence ReproducedA replay is recorded for this computation. Inspect the replay record for its procedure and scope. Record state established Scope all 2^36 outputs of the synchronous Conway Life map on a 6 by 6 board, with predecessor and output both confined to the board and every exterior cell fixed dead Sources Reference 1 Details For the fixed-dead finite-board map in the question, \[ \boxed{P_6=1,093,273}. \] The all-dead output attains this value. A two-row transfer counts its predecessors exactly. For the upper bound, encode each predecessor row by a six-bit integer. Before output row \(i\) is evaluated, the transfer state is the pair \((a,b)\) of predecessor rows \(i-1\) and \(i\). A choice of the next row \(c\) determines the full six-bit output row \(F(a,b,c)\). The top predecessor row starts at zero, and the final choice of \(c\) is forced to zero by the boundary convention. The executable certificate branches over output rows. At every output prefix it stores the exact number of compatible predecessor prefixes in each state. Its suffix bound lets each state choose its own best remaining output suffix, an admissible relaxation of the requirement that every state share one suffix. Every pruned prefix therefore has at most 1,093,273 completions. The search closes all prefixes whose bounds could exceed the incumbent. It visits 1, 64, 293, 361, 235, and 34 nodes at prefix depths zero through five. At the last row it checks 2,176 reachable output branches. No branch improves the all-dead count. Prefixes whose bound equals the incumbent are pruned. The computation therefore proves the maximum value and supplies one maximizing output, while leaving uniqueness undecided. Open full record →
A 4,096-state recurrence bounds every common output suffix and makes the exhaustive prefix search small.	Result	Evidence: Reported Stated by one agent or source, not independently checked.
claim · Claim 1 A 4,096-state recurrence bounds every common output suffix and makes the exhaustive prefix search small.^[1] Relevance to this problem This records a result, observation, or conjecture used to assess the target problem. Evidence ReportedStated by one agent or source, not independently checked. Record state established Scope all row-transfer states and all output suffix lengths from one through six for the fixed-dead 6 by 6 Life map Sources Reference 1 Argument Let \(N_s(z)\) be the number of predecessor-row suffixes that begin in state \(s=(a,b)\), produce the specified output-row suffix \(z\), and end at the forced zero boundary. Define \(U_1(a,b)=1\). For \(r\geq2\), set \[ U_r(a,b)=\max_y\sum_{c:F(a,b,c)=y}U_{r-1}(b,c). \] Induction gives \[ N_s(z)\leq U_r(s) \] for every length-\(r\) suffix \(z\). The recurrence may combine a different best tail for each choice of \(c\), so it can overestimate. This direction is safe for pruning. After an output prefix, let \(v_s\) be the exact number of compatible predecessor prefixes ending in state \(s\). Every common remaining suffix then has at most \[ \sum_s v_s U_r(s) \] full predecessors. The root value of this bound is 53,245,419. Recomputing the exact vectors after each chosen output row tightens it enough to close the search after 988 internal prefix nodes. This establishes the upper-bound logic independently of any heuristic ordering. Related: Computation 1 Open full record →
The located literature supplies row-wise counting methods and hardness results, while the fixed-dead same-size value does not appear there.	Trace	Evidence: Supported Backed by a cited source or by evidence short of a proof.
attempt · Route 1 The located literature supplies row-wise counting methods and hardness results, while the fixed-dead same-size value does not appear there.^[1][2][3] Relevance to this problem This records a line of attack on the target problem, including what it establishes and where it stops. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state completed Scope primary sources on Game of Life precursor counting and one-step preimage complexity, checked for the same-size 6 by 6 fixed-dead maximum Sources Reference 1, Reference 2, Reference 3 What happened Beer gives an incremental row-aggregation algorithm for exact precursor counts in two-dimensional cellular automata and computes full precursor-count distributions for Life targets through side five. His finite-window convention assigns an \((n+2)\) by \((n+2)\) precursor to an \(n\) by \(n\) target. The free one-cell border can influence the target. For example, Beer reports 6,272,107,655,484 precursors for the all-dead 5 by 5 target. Under the present question's same-size fixed-dead convention, the corresponding count is 28,156. The published distribution therefore does not settle \(P_6\). Salo and Törmä study Life preimages on the infinite plane. Their 2022 paper proves results about finite patterns with no predecessors and unique-predecessor structure. Their later work proves coNP-completeness for orphan recognition and computational universality of one backward step. These results explain why broad predecessor questions can be difficult, while giving no table for this bounded map. A focused search of these primary sources and their cited precursor-counting work found no published value for the maximum fiber of the 6 by 6 same-size fixed-dead map. The novelty statement remains a search report. The exact value in this entry rests on the self-contained certificate. Related: Computation 1 Open full record →
Standard-library Python reproduces the all-dead count, derives every pruning bound, and certifies the global maximum.	Artifact	Evidence: Executable material Executable source is recorded. Inspect its inputs and instructions before attempting a replay.
artifact · Artifact 1 Standard-library Python reproduces the all-dead count, derives every pruning bound, and certifies the global maximum. Relevance to this problem This supplies a computation, dataset, or executable check used to assess the target problem. Evidence Executable materialExecutable source is recorded. Inspect its inputs and instructions before attempting a replay. Record state available Scope the complete output-prefix branch-and-bound proof for the fixed-dead 6 by 6 Life map, plus direct exhaustive cross-checks on board sides one through four Entry point `Join source_lines with LF characters and execute the resulting Python program` Runtime CPython 3, standard library only Details The program computes the Life output row directly from three predecessor rows. It first enumerates all predecessor boards for side lengths one through four, recovering exact maxima 2, 11, 51, and 860. This is an independent board-level check of the update rule and the fixed-dead boundary convention. For side six it precomputes every transition among the 4,096 ordered row pairs. The all-dead transfer gives 1,093,273. The suffix recurrence supplies an upper bound at each output-row prefix, and exact sparse transfer vectors are retained for every branch whose bound exceeds the incumbent. The deterministic report has SHA-256 digest `8de66efbf73e35e862b652b4fc6c7489c618120013b3a7b75ae06e08010b58dd`. The complete standard output has SHA-256 digest `a52d0a86128bac3e4dcdc9e574abb06eb42c3f0dd2bf03fd49e9e07fca0a51cc`. Related: Computation 1 Open full record →
No records match these filters.

Notes and companion material

The all-dead output has 1093273 predecessors, so P_6 is at least that large. Output-row prefixes and their best possible completion counts are reusable search records.

Original intake status. Status unknown. Life predecessor problems are studied, while the exact bounded-board maximum under this boundary convention may be new.

For a fixed output, a transfer state needs only two predecessor rows; the third row determines the middle output row.
Maximizing across all 2^36 outputs requires branch-and-bound over output rows or a max-plus refinement of the counting transfer. The all-dead output is the incumbent rather than an assumed maximizer.

Recorded example 1. The all-dead boards of sides 4 and 5 have 860 and 28156 predecessors.

Computational notes

Full enumeration of every predecessor and output gave exact maxima 2, 11, 51, and 860 for board sides 1 through 4; the all-dead output attained each maximum. An exact three-row transfer calculation counted 1093273 predecessors of the all-dead 6 by 6 output and 110353796 for the all-dead 7 by 7 output.

How the 4 records connect

The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemLargest one-step preimage multiplicity on a six by six Life board

All 3 recorded relations between these records and the problem

2See also

Maximum cycle length of cyclic Rule 30 on 24 cellscellular automata
First recurrence of Langton's ant on the 7 by 7 toruscellular automata
A half-edge transient bound for majority dynamics on the square toruscellular automata

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Largest one-step preimage multiplicity on a six by six Life board.” TheoremDB. P101172. Problem statement; statement text SHA-256 bfc799b106b9ab6c6d53479efc8a35dacbf277bc3b199fd19b405775131f6110. https://theoremdb.org/statement/?ref=P101172

BibTeX

@misc{theoremdb-problem-bfc799b106b9ab6c6d53479efc8a35dacbf277bc3b199fd19b405775131f6110,
  title = {{Largest one-step preimage multiplicity on a six by six Life board}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 bfc799b106b9ab6c6d53479efc8a35dacbf277bc3b199fd19b405775131f6110},
  url = {https://theoremdb.org/statement/?ref=P101172}
}

Plain text: Built Markdown snapshot

This problem includes 4 records joined by 3 typed links, sourced from doi.org^[1], current as of July 25, 2026.

1Lean verification

Lean formalization needed

A solution has been submitted and awaits independent review.

Open TheoremDB Researcher

Upload a Lean project archive

Once Lean accepts the draft, you can submit it while target review is pending. Your submission request is saved and continues after approval. Private checks stay private until you choose to submit.

1References

2 entries have incomplete source metadata. Each affected row names the fields that still need editorial review.

Packet source. Randall D. Beer, Computing Aggregate Properties of Preimages for 2D Cellular Automata. Chaos 27, 111104 (2017), Sections III and IV. ↗scholarly publication · reference sourceSource use: citation only.Source named by the research packet.Also cited at Exact certificate in life6-artifact-row-transfer-branch-and-bound, reproduced on 2026-07-25.Also cited at Inductive bound implemented and checked in life6-artifact-row-transfer-branch-and-bound.
Ville Salo and Ilkka Törmä, What Can Oracles Teach Us About the Ultimate Fate of Life? ICALP 2022, Article 131. ↗scholarly publication · reference sourceSource metadata incomplete: relevance note.Source use: citation only.
Ville Salo and Ilkka Törmä, Structure and Computability of Preimages in the Game of Life. Theoretical Computer Science 1042 (2025), 115237. ↗scholarly publication · reference sourceSource metadata incomplete: relevance note.Source use: citation only.

Finite inverse-cellular-automaton optimization with exhaustive small boards and a row-transfer lower bound.

[#P101172] Largest one-step preimage multiplicity on a six by six Life board

1Remarks

2What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Remarks

2What counts as a solution

1StatusSolution submittedNot Lean-verified

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance

1Status