# P2712: Two-cycle probability for majority dynamics on the eight torus

- ID: `P2712`
- Reference: `majority-eight-torus-two-cycle-probability`
- Page: https://theoremdb.org/statements/P2712
- Record maturity: Reviewed problem with recorded work

## Problem

Color the vertices of \(C_8\square C_8\) independently and uniformly with two colors. At each synchronous step, every vertex adopts the strict majority color among its four neighbors and retains its color on a tie. Determine the exact probability that the orbit reaches a genuine two-cycle rather than a fixed point.

### Problem setup

- **Definition.** A genuine two-cycle consists of two distinct configurations exchanged by one update.
- **Remark.** The probability should be reported as an integer numerator over 2^64.

### What counts as a solution

- Give the exact numerator and a symmetry-aware basin certificate whose fixed-point and two-cycle counts sum to 2^64.

## Status

A symmetry orbit of one checked two-cycle witness supplies the lower bound, while 510 stripe configurations are fixed and supply the upper bound. [2](#reference-2)

## Work

### Evidence for the current status

**Computation 1 (The exact numerator remains open, with a certified interval of 128 through 18,446,744,073,709,551,106).** A symmetry orbit of one checked two-cycle witness supplies the lower bound, while 510 stripe configurations are fixed and supply the upper bound.

Write \(N_2\) for the number of initial configurations that reach a genuine two-cycle. The current certificate proves
\[
128\leq N_2\leq 2^{64}-510
=18{,}446{,}744{,}073{,}709{,}551{,}106.
\]
The lower bound comes from the 64 translations of the displayed witness and their color complements. The verifier checks that these 128 initial configurations are distinct. Majority update commutes with translations and complementation, so each reaches a genuine two-cycle.

For the upper bound, every configuration whose rows are individually monochromatic is fixed. East and west already give two neighbors of the cell's own color, so the vertical neighbors can never force a strict opposing majority. The same argument applies to monochromatic columns. These two families each contain \(2^8=256\) configurations and intersect in the two constant configurations. Their union therefore contains 510 distinct fixed points.

Color complementation pairs the two-cycle basin without fixed configurations under the pairing, so \(N_2\) is even. Determining it exactly still requires an exhaustive symbolic basin count over all \(2^{64}\) starting states.

### Background and intake notes

A fifty-thousand-state sample places the two-cycle probability near 0.168.

- Original intake status: Novelty remains unverified. No primary-source status audit was completed for this torus size and tie convention.
- The update is synchronous. Updating vertices in place changes both basin sizes and possible periods.
- Color complementation, torus translations, and dihedral symmetries can reduce enumeration, but orbit sizes and stabilizers must be retained.
- A complete solution can count basins by a decision diagram without storing all 2^64 configurations.

- Recorded example: One sampled initial configuration is 01100100/11101001/00100000/01000101/01111000/11001111/00111110/10000111.

### Other known results

- **Proposition 1** (supported): The tie-retaining rule is a symmetric threshold map, so the finite threshold-network period-two theorem applies. [2](#reference-2)
- **Claim 1** (reproduced): The observed proportion was 0.16782, and every sampled orbit settled within 17 updates. [2](#reference-2)

### Prior approaches

- **Route 1** (inconclusive): The audit found the general finite symmetric-threshold theorem and modern majority-dynamics references, with no source reporting this exact numerator. [1](#reference-1)

### Runnable artifacts

- **Artifact 1** (reproduced): A standard-library Python program checks the reported witness, its 128 distinct symmetry images, and all 510 stripe fixed points. [2](#reference-2)

### Computational notes

- With seed 20260724, all 50000 sampled states settled within 17 updates: 41609 reached fixed points and 8391 reached genuine two-cycles. The displayed example reached the alternating pair 11100000/11100000/00100000/01000000/01111100/11111111/00011111/00000111 and 11100000/11100000/01000000/00100000/01111100/11111111/00011111/00000111.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `majority-eight-torus-two-cycle-probability`, 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>Itai Benjamini, Siu-On Chan, Ryan O'Donnell, Omer Tamuz, and Li-Yang Tan, “Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs”. Stochastic Processes and their Applications, Volume 126, Issue 9, September 2016, Pages 2719-2733. DOI 10.1016/j.spa.2016.02.015. arXiv:1405.2486 (2014). Targeted search completed 2026-07-25; finite period theorem at DOI 10.1016/0166-218X(81)90034-2; modern context in arXiv:1405.2486 https://arxiv.org/abs/1405.2486
   - preprint; primary source; arXiv:1405.2486, version checked 2026-07-25; checked 2026-08-01
   - Source use: original_summary
   - For Two-cycle probability for majority dynamics on the eight torus: The period theorem is classical; the size-eight basin count was not located. The audit found the general finite symmetric-threshold theorem and modern majority-dynamics references, with no source reporting this exact numerator.
2. <a id="reference-2"></a>E. Goles and J. Olivos, “Comportement periodique des fonctions a seuil binaires et applications”. Discrete Applied Mathematics 3(2) (1981), 93-105. DOI 10.1016/0166-218X(81)90034-2. Eric Goles and Jorge Olivos, Comportement periodique des fonctions a seuil binaires et applications, Discrete Applied Mathematics 3 (1981), 93-105 https://doi.org/10.1016/0166-218X(81)90034-2
   - Also cited at Bounds and symmetry checks in maj8torus-artifact-witness-and-update-verifier
   - Also cited at api/app/data/agent_candidate_problems_v4.jsonl, record candidate.majority-eight-torus-two-cycle-probability
   - Also cited at Inline Python 3 verifier prepared on 2026-07-25
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - For Two-cycle probability for majority dynamics on the eight torus: The tie-retaining rule is a symmetric threshold map, so the finite threshold-network period-two theorem applies.
   - Source named by the research packet.