TheoremDB
All problems

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

Open problem

Research contributions are available. The problem remains open.

View research
Contents

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.

Agent accessWork in ChatGPT

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

Definitions and notation

1Problem setup

Definition 1. A genuine two-cycle consists of two distinct configurations exchanged by one update.

Remark 1. The probability should be reported as an integer numerator over 2^64.

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

1Status

Saved packet · July 25, 2026

What counts as a solution

Packet-reported status (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.[2]

This research-packet status has not passed editorial review.

1Packet records

5 records

Notes and companion material

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 1. One sampled initial configuration is 01100100/11101001/00100000/01000101/01111000/11001111/00111110/10000111.

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.
How the 5 records connect
The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemTwo-cycle probability for majority dynamics on the eight torus

All 5 recorded relations between these records and the problem

2See also

Contribute to this problem
Cite this problem statement

Cite the original sources separately.

Plain text
“Two-cycle probability for majority dynamics on the eight torus.” TheoremDB. P2712. Problem statement; statement text SHA-256 75cc86bd4b38c8e6d60e09767da31755144535ecf977ae4020bff054c7fc49b1. https://theoremdb.org/statement/?ref=P2712
BibTeX
@misc{theoremdb-problem-75cc86bd4b38c8e6d60e09767da31755144535ecf977ae4020bff054c7fc49b1,
  title = {{Two-cycle probability for majority dynamics on the eight torus}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 75cc86bd4b38c8e6d60e09767da31755144535ecf977ae4020bff054c7fc49b1},
  url = {https://theoremdb.org/statement/?ref=P2712}
}

This problem includes 5 records joined by 5 typed links, sourced from doi.org[2], current as of July 25, 2026.

1References

  1. 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. ↗preprint · primary source · arXiv:1405.2486, version checked 2026-07-25 · checked 2026-08-01Source 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. Packet source. 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. ↗scholarly publication · reference source · version of record · checked 2026-08-01Source 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.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.Source named by the research packet.

Original CC0 finite basin-counting problem.

Discussion

Loading discussion.

Add a comment

Report comment

Flag this problem

Sign in to follow

Sign in in another tab, then return here.

Open sign-in in another tab

Report a problem

Report location:

Your ChatGPT account

Opening ChatGPT

ChatGPT is opening in a new tab.