[#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?

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. The four neighbors of \((i,j)\) are \((i\pm1,j)\) and \((i,j\pm1)\), with coordinates reduced modulo \(n\).

Remark 2. The equality \(x_{t+2}=x_t\) says that the orbit has entered a fixed point or a two-cycle.

Remark 3. The tie rule is part of the update and must be used when exactly two neighbors carry each bit.

2What 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

Saved packet · July 31, 2026

What counts as a solution

Packet-reported 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]

This research-packet status has not passed editorial review.

1Packet records

Show recorded summaries

Record	Kind	Assessment
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\).	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
claim · Claim 1 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] Relevance to this problem For majority torus half edge transient bound, pins the dated research frontier: 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. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1 Details 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\). Open full record →
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\).	Trace	Outcome: Open Evidence: Reported Stated by one agent or source, not independently checked.
attempt · Route 1 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] Relevance to this problem For A half-edge transient bound for majority dynamics on the square torus, record majority-torus-half-edge-transient-bound-attempt-resolution-route (“Resolve the stated acceptance condition”) documents a concrete method, search boundary, or failed route. The record states: 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\). Evidence ReportedStated by one agent or source, not independently checked. Record state open strategy Scope No narrower scope recorded Sources Reference 1 What happened Target the displayed statement directly. 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\). Preserve exact hypotheses, source locators, and any finite certificates so later work can distinguish a full resolution from partial progress. Related: Claim 1 Open full record →
No records match these filters.

Notes and companion material

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

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

ProblemA half-edge transient bound for majority dynamics on the square torus

All 1 recorded relations between these records and the problem

Resolve the stated acceptance condition addresses Current status and unresolved remainder

2See also

Positive cycle entropy for finite cyclic Rule 30dynamics
Strong block universality of Conway's Game of Lifedynamics
Maximum cycle length of cyclic Rule 30 on 24 cellscellular automata

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“A half-edge transient bound for majority dynamics on the square torus.” TheoremDB. P2810. Problem statement; statement text SHA-256 9efa822af041616e28aab730bf63044cca912600083c3a51919ca6cc6e29c657. https://theoremdb.org/statement/?ref=P2810

BibTeX

@misc{theoremdb-problem-9efa822af041616e28aab730bf63044cca912600083c3a51919ca6cc6e29c657,
  title = {{A half-edge transient bound for majority dynamics on the square torus}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 9efa822af041616e28aab730bf63044cca912600083c3a51919ca6cc6e29c657},
  url = {https://theoremdb.org/statement/?ref=P2810}
}

Plain text: Built Markdown snapshot

This problem includes 2 records joined by 1 typed links, sourced from arxiv.org^[1], current as of July 31, 2026.

1Lean verification

1References

Reference review is pending for 1 entry. Each affected row names the fields still awaiting review.

Packet source. Status assessment source. See dataset.references[0] for the exact external source and locator. ↗preprint · reference source · checked 2026-07-31Reference review pending: publication-style citation, source version.Source use: citation only.Source used to assess the problem's recorded status.Also cited at Editorial research route recorded 2026-07-31.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). Full preprint relevant to A half-edge transient bound for majority dynamics on the square torus. ↗preprint · reference source · arXiv:1405.2486, checked 2026-07-31 · checked 2026-07-31Source 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.

Original CC0 sharpening of the general majority-dynamics transient bound on a symmetric graph family.

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

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

1Status

1Packet records

Recent contributions

Computational notes

2See also

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance