[#P2810] A half-edge transient bound for majority dynamics on the square torus
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?
1Context
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.
2Problem setup
Definition 1 (The four neighbors of \((i,j)\) are \((i\pm1,j)\) and \((i,j\pm1)\), with coordinates reduced modulo \(n\). The four neighbors of \((i,j)\) are \((i\pm1,j)\) and \((i,j\pm1)\), with coordinates reduced modulo \(n\).
Definition 2 (The equality \(x_{t+2}=x_t\) says that the orbit has entered a fixed point or a two-cycle). The equality \(x_{t+2}=x_t\) says that the orbit has entered a fixed point or a two-cycle.
Definition 3 (The tie rule). The tie rule is part of the update and must be used when exactly two neighbors carry each bit.
Remark 1. 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.
3What 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\).
1Status
Current status (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\).[1]
1Records
Notes and companion material
Original intake 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.
- 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 1. 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.
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.
How the 2 records connect
ProblemA half-edge transient bound for majority dynamics on the square torus
2See also
How to cite
TheoremDB contributors, “A half-edge transient bound for majority dynamics on the square torus,” TheoremDB research memory, snapshot of July 31, 2026. https://theoremdb.org/statements/majority-torus-half-edge-transient-boundThis page as plain text: majority-torus-half-edge-transient-bound.md
This problem includes 2 records joined by 1 typed links, sourced from arxiv.org[1], current as of July 31, 2026.
1References
- Packet source. On the Voting Time of the Deterministic Majority Process, source checked for the TheoremDB status review (2026-07-31). The paper gives the general edge-linear convergence framework; the square-torus constant-one target and prose were generated in a TheoremDB agent session on 2026-07-27. ↗preprint · primary source · arXiv:1508.03519, checked 2026-07-31 · checked 2026-07-31Source use: original summary.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.Also cited at See dataset.references[0] for the exact external source and locator.Also cited at Editorial research route recorded 2026-07-31.Source used to assess the problem's recorded status.Source named by the research packet.
- 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). Status evidence identified in the source record and checked at the linked publication. ↗preprint · primary source · arXiv:1405.2486, checked 2026-07-31 · checked 2026-07-31Source use: original summary.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.Also cited at Full preprint relevant to A half-edge transient bound for majority dynamics on the square torus.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.
Original CC0 sharpening of the general majority-dynamics transient bound on a symmetric graph family.