# P2810: A half-edge transient bound for majority dynamics on the square torus

- ID: `P2810`
- Reference: `majority-torus-half-edge-transient-bound`
- Page: https://theoremdb.org/statements/P2810
- Record maturity: Reviewed problem with recorded work

## Problem

For \(n\ge3\), put a bit at each vertex of \((\mathbb Z/n\mathbb Z)^2\). At each synchronous update a vertex adopts the strict majority of its four nearest neighbors, retaining its current bit when the vote is tied. For an initial configuration \(x\), let \(\tau(x)\) be the least \(t\ge0\) for which \(x_{t+2}=x_t\). Is \(\tau(x)\le n^2\) for every \(n\ge3\) and every initial configuration?

### Remarks

- **Remark.** The four neighbors of \((i,j)\) are \((i\pm1,j)\) and \((i,j\pm1)\), with coordinates reduced modulo \(n\).
- **Remark.** The equality \(x_{t+2}=x_t\) says that the orbit has entered a fixed point or a two-cycle.
- **Remark.** The tie rule is part of the update and must be used when exactly two neighbors carry each bit.

### What counts as a solution

- Prove \(\tau(x)\le n^2\) for all \(n\ge3\) and all \(x\), or give a configuration whose complete replay has \(\tau(x)>n^2\).

## Status

UNKNOWN as of 2026-07-31. General majority dynamics reaches period at most two in \(O(|E|)\) rounds, but the checked sources do not settle the proposed \(n^2=|E|/2\) bound for square tori. Prove \(\tau(x)\le n^2\) for all \(n\ge3\) and all \(x\), or give a configuration whose complete replay has \(\tau(x)>n^2\). [1](#reference-1)

## Work

### Evidence for the current status

**Claim 1 (Current status and unresolved remainder).** UNKNOWN as of 2026-07-31. General majority dynamics reaches period at most two in \(O(|E|)\) rounds, but the checked sources do not settle the proposed \(n^2=|E|/2\) bound for square tori. Prove \(\tau(x)\le n^2\) for all \(n\ge3\) and all \(x\), or give a configuration whose complete replay has \(\tau(x)>n^2\).

UNKNOWN as of 2026-07-31. General majority dynamics reaches period at most two in \(O(|E|)\) rounds, but the checked sources do not settle the proposed \(n^2=|E|/2\) bound for square tori.

A complete resolution must satisfy this condition: Prove \(\tau(x)\le n^2\) for all \(n\ge3\) and all \(x\), or give a configuration whose complete replay has \(\tau(x)>n^2\).

### Background and intake notes

The general convergence theorem already restricts every orbit to a fixed point or two-cycle. This target asks whether the local geometry of the square torus cuts the general edge-based transient allowance in half.

- Original intake status: UNKNOWN as of 2026-07-27. General majority dynamics reaches period at most two in \(O(|E|)\) rounds, but the checked sources do not settle the proposed \(n^2=|E|/2\) bound for square tori.
- 2026-07-27 prior-art search checked deterministic majority voting time, potential-function bounds, majority cellular automata, and toroidal majority dynamics; the exact constant-one vertex bound was not found.
- The standard energy argument gives a bound proportional to the \(2n^2\) edges. Reaching \(n^2\) requires using bipartiteness when \(n\) is even or a different torus-specific invariant when \(n\) is odd.
- A long orbit certificate should record the initial bit string and every state through the first repeated parity class; a proof artifact can record the energy drop and the configurations attaining each small-case maximum.

- Recorded example: Complete state-graph enumeration gives maximum transient 3 on the \(3\times3\) torus and 4 on the \(4\times4\) torus under the stated tie rule.

### Open directions

- **Route 1** (reported): Prove \(\tau(x)\le n^2\) for all \(n\ge3\) and all \(x\), or give a configuration whose complete replay has \(\tau(x)>n^2\). [1](#reference-1)

### Computational notes

- All \(2^9\) states for \(n=3\) and all \(2^{16}\) states for \(n=4\) were replayed until a state repeated. Witnesses attaining transients 3 and 4 were found, and every eventual period was one in these two enumerations.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `majority-torus-half-edge-transient-bound`, 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 entry has incomplete source metadata. Each affected row names the fields that still need editorial review.

1. <a id="reference-1"></a>Status assessment source See dataset.references[0] for the exact external source and locator. https://arxiv.org/abs/1508.03519
   - Also cited at Editorial research route recorded 2026-07-31
   - preprint; reference source; checked 2026-07-31
   - Source metadata incomplete: publication-style citation, source version.
   - Source use: citation_only
   - Source used to assess the problem's recorded status.
   - Source named by the research packet.
2. <a id="reference-2"></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). Full preprint relevant to A half-edge transient bound for majority dynamics on the square torus. https://arxiv.org/abs/1405.2486
   - preprint; reference source; arXiv:1405.2486, checked 2026-07-31; checked 2026-07-31
   - Source use: citation_only
   - Source used to assess the problem's recorded status.
   - For A half-edge transient bound for majority dynamics on the square torus: UNKNOWN as of 2026-07-27. General majority dynamics reaches period at most two in \(O(|E|)\) rounds, but the checked sources do not settle the proposed \(n^2=|E|/2\) bound for square tori.