[#P2698] Longest rotor-router cover time on the eight by eight grid

Problem. On the \(8\times8\) grid graph, fix at each vertex the clockwise order induced by north, east, south, west after deleting missing boundary neighbors. Starting from any vertex and rotor state, increment the current rotor and follow it. What is the largest number of moves before every vertex has been visited?

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. A rotor index is taken in the listed local cyclic order and is incremented before the move.

Remark 2. The cover time counts moves up to the first visit to the last unvisited vertex.

2What counts as a solution

Give an initial state attaining the maximum and a complete dynamic-programming, branch, or structural upper-bound certificate.

1Status

Saved packet · July 25, 2026

What counts as a solution

Packet-reported status (The worst cover time lies between 1,282 and 3,136 moves). An explicit rotor state gives the lower bound, while the Eulerian-graph excursion theorem gives the upper bound for every state.^[4]

This research-packet status has not passed editorial review.

1Packet records

Show recorded summaries

Record	Kind	Assessment
An explicit rotor state gives the lower bound, while the Eulerian-graph excursion theorem gives the upper bound for every state.	Result	Evidence: Reproduced A replay is recorded for this computation. Inspect the replay record for its procedure and scope.
claim · Computation 1 An explicit rotor state gives the lower bound, while the Eulerian-graph excursion theorem gives the upper bound for every state.^[4] Relevance to this problem For Longest rotor-router cover time on the eight by eight grid, record rr8gc-claim-certified-interval-1282-3136 (“The worst cover time lies between 1,282 and 3,136 moves”) records a bound, answer, status fact, or structural consequence. The record states: An explicit rotor state gives the lower bound, while the Eulerian-graph excursion theorem gives the upper bound for every state. Evidence ReproducedA replay is recorded for this computation. Inspect the replay record for its procedure and scope. Record state established Scope all starting vertices and all initial rotor states on the 8 by 8 grid, using the clockwise local order induced by north, east, south, west and increment-before-move Sources Reference 4 Details Let \(C_8\) be the largest cover time under the convention in the problem. The present certified interval is \[ \boxed{1282\leq C_8\leq3136}. \] The lower bound comes from the row-major rotor vector in the replay record. Start at vertex 56. Exact simulation first visits the last missing vertex, vertex 7, on move 1,282. For the upper bound, replace each of the 112 undirected grid edges by its two orientations. This gives a connected Eulerian directed graph with 224 arcs and diameter 14. Theorem 6.1 of Florescu, Levine, and Peres states that every simple rotor walk on a finite Eulerian graph has vertex cover time at most \(D\|E\|\), for any rotor mechanism and initial rotor configuration. Therefore \[ C_8\leq14\cdot224=3136. \] The problem's clockwise order is one of the mechanisms covered by that theorem. Its retrospective convention also increments the rotor before moving. Open full record →
The sources fix the update convention and prove bounds for every Eulerian graph; the exact 8 by 8 clockwise extremum was absent from the located papers.	Trace	Evidence: Supported Backed by a cited source or by evidence short of a proof.
attempt · Route 1 The sources fix the update convention and prove bounds for every Eulerian graph; the exact 8 by 8 clockwise extremum was absent from the located papers.^[4][1][3][2] Relevance to this problem For Longest rotor-router cover time on the eight by eight grid, record rr8gc-attempt-literature-audit (“General cover-time theorems settle the finite upper bound”) documents a concrete method, search boundary, or failed route. The record states: The sources fix the update convention and prove bounds for every Eulerian graph; the exact 8 by 8 clockwise extremum was absent from the located papers. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state completed Scope No narrower scope recorded Sources Reference 4, Reference 1, Reference 3, Reference 2 What happened Holroyd and Propp describe the retrospective rotor convention on pages 2 and 3: the rotor advances to the next arc and the particle follows that arc. This matches the problem after each boundary vertex receives its shortened clockwise neighbor list. Florescu, Levine, and Peres prove \(t_{\mathrm{vertex}}\leq D\|E\|\) for every finite Eulerian directed graph, arbitrary rotor mechanism, and arbitrary initial configuration. Their proof decomposes the walk into excursions. Applied to the bidirected grid, it gives 3,136. They credit Yanovski, Wagner, and Bruckstein with the earlier edge-cover bound \(2D\|E\|\). Friedrich and Sauerwald give other general vertex and edge cover-time techniques and work out several graph families. Focused searches used `rotor-router cover time grid`, `clockwise rotor walk finite square`, and the exact dimensions 8 by 8. The sources found asymptotic grid results and general finite-graph bounds. None supplied the exact extremum under this boundary-order convention. Novelty of the finite question remains unverified. Related: Computation 1 Open full record →
Single-rotor mutations found a long-lived state concentrated around the lower-left start, while leaving a large certified gap.	Trace	Outcome: Open Evidence: Computational evidence The record reports a computation within its stated scope. Reproduction requires a separate replay.
attempt · Route 2 Single-rotor mutations found a long-lived state concentrated around the lower-left start, while leaving a large certified gap.^[4] Relevance to this problem For Longest rotor-router cover time on the eight by eight grid, record rr8gc-attempt-seeded-local-search (“Seeded local search raises the incumbent from 807 to 1,282”) documents a concrete method, search boundary, or failed route. The record states: Single-rotor mutations found a long-lived state concentrated around the lower-left start, while leaving a large certified gap. Evidence Computational evidenceThe record reports a computation within its stated scope. Reproduction requires a separate replay. Record state in progress Scope the capped deterministic local-search run with seed 2026072508 on the 8 by 8 grid Sources Reference 4 What happened A deterministic C++ search began with the candidate's 807-move state and used `mt19937_64` seed 2026072508. Each proposal changed one rotor. One proposal in 64 changed two rotors, one in 1,024 changed four, and one in 2,048 also changed the start vertex. Nondecreasing moves were accepted, with a rare random escape. Random restarts were interleaved with restarts at the incumbent. The run produced the 1,282-move configuration preserved in the replay record. This search certifies only the lower bound supplied by its saved state. The raw search space has \[ 64\cdot2^4\cdot3^{24}\cdot4^{36} =1{,}365{,}745{,}435{,}494{,}690{,}943{,}435{,}859{,}428{,}192{,}026{,}624 \] start-and-rotor states. A complete computation can quotient the four rotations of the square, branch on the exit sequences actually used before a proposed deadline, and prune at 3,136 using the excursion bound. Per-target rotor-potential bounds may lower that deadline before branching. Related: Artifact 1 Open full record →
Standard-library Python fixes every ordering convention, validates the rotor vector, and replays all 1,282 moves.	Artifact	Evidence: Executable material Executable source is recorded. Inspect its inputs and instructions before attempting a replay.
artifact · Artifact 1 Standard-library Python fixes every ordering convention, validates the rotor vector, and replays all 1,282 moves. Relevance to this problem For Longest rotor-router cover time on the eight by eight grid, record rr8gc-artifact-1282-move-replay (“Exact replay of the 1,282-move initial state”) supplies evidence or a replay used to check the packet. The record states: Standard-library Python fixes every ordering convention, validates the rotor vector, and replays all 1,282 moves. Evidence Executable materialExecutable source is recorded. Inspect its inputs and instructions before attempting a replay. Record state available Scope the stated start vertex and one complete 64-rotor initial state on the 8 by 8 grid Entry point `join source_lines with newline and run with python3` Runtime CPython 3, standard library only Details Vertices are numbered row-major from 0 through 63. At each vertex, form its local neighbor list by taking north, east, south, west in that order and deleting directions that leave the grid. A rotor index points into this shortened list. On each move the index is incremented modulo the local degree, then the walker follows the selected edge. Start at vertex 56 with rotor indices ``` [1,0,0,0,0,0,0,0, 0,1,1,1,1,1,1,0, 0,1,1,1,1,1,3,0, 0,1,1,1,1,1,0,0, 0,1,1,1,1,1,0,0, 1,2,1,1,1,1,0,0, 1,1,1,1,1,0,0,0, 0,1,1,1,1,0,0,0] ``` The walk reaches 63 vertices by move 1,063. Vertex 7 remains unseen until move 1,282. The trajectory uses 221 of the 224 directed arcs. The canonical report has SHA-256 digest `b070c0e29fe515ae5ccd7d3a2e2eb159b6b819efd0b35737c073e5736211ab8d`. Related: Computation 1 Open full record →
No records match these filters.

Notes and companion material

A seeded search gives a cover time of at least 807 moves.

Original intake status. Novelty remains unverified. Rotor walks are well studied, and no primary-source status audit was completed for this exact grid and convention.

A state consists of the current vertex, visited mask, and mixed-radix rotor vector. Search should hash only states that improve the visited mask or elapsed-time bound.
Changing increment-before-move to move-before-increment changes the numeric answer. Certificates must state the convention and local boundary orders.
General polynomial cover-time bounds leave a large gap and do not identify the worst initial rotor state.

Recorded example 1. Number vertices row-major from 0 through 63. One incumbent starts at vertex 39 with rotor-index vector listed in the computation field.

Computational notes

Fifty thousand initial states from seed 20260724 were simulated exactly. The best took 807 moves from vertex 39 with row-major rotor indices [0,2,0,2,1,2,2,1,0,0,1,1,0,0,0,2,1,3,3,1,0,2,2,0,0,0,0,2,0,0,1,1,1,0,1,1,1,3,0,2,1,3,0,3,2,0,1,1,0,2,3,1,3,1,0,0,1,1,0,0,1,0,1,0]. A replay visited the 64th vertex on move 807.

How the 4 records connect

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

ProblemLongest rotor-router cover time on the eight by eight grid

All 3 recorded relations between these records and the problem

2See also

Merging of orbits under adding the product of nonzero digitsdiscrete dynamical systems
Maximum cycle length of cyclic Rule 30 on 24 cellsdiscrete dynamical systems
First recurrence of Langton's ant on the 7 by 7 torusdiscrete dynamical systems

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Longest rotor-router cover time on the eight by eight grid.” TheoremDB. P2698. Problem statement; statement text SHA-256 587bed0f4d8933d2e7c147bf755f2b77a7d16402e33678a7e7ef23c3dbe98263. https://theoremdb.org/statement/?ref=P2698

BibTeX

@misc{theoremdb-problem-587bed0f4d8933d2e7c147bf755f2b77a7d16402e33678a7e7ef23c3dbe98263,
  title = {{Longest rotor-router cover time on the eight by eight grid}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 587bed0f4d8933d2e7c147bf755f2b77a7d16402e33678a7e7ef23c3dbe98263},
  url = {https://theoremdb.org/statement/?ref=P2698}
}

Plain text: Built Markdown snapshot

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

1Lean verification

1References

Alexander E. Holroyd and James Propp, “Rotor Walks and Markov Chains”. arXiv:0904.4507 (2009). arXiv:0904.4507, pages 2-3 for the retrospective update convention. ↗preprint · reference source · arXiv:0904.4507, checked 2026-08-01 · checked 2026-07-25Source use: citation only.For Longest rotor-router cover time on the eight by eight grid, the reviewed source scope is arXiv:0904.4507, pages 2-3 for the retrospective update convention. The packet makes no inference beyond that cited scope.
Vladimir Yanovski, Israel A. Wagner, and Alfred M. Bruckstein, “A Distributed Ant Algorithm for\protect Efficiently Patrolling a Network”. Algorithmica 37(3) (2003), 165-186. DOI 10.1007/s00453-003-1030-9. Algorithmica 37(3), 165-186 (2003). ↗scholarly publication · reference source · checked 2026-08-01Source use: citation only.For Longest rotor-router cover time on the eight by eight grid, the reviewed source scope is Algorithmica 37(3), 165-186 (2003). The packet makes no inference beyond that cited scope.
Tobias Friedrich and Thomas Sauerwald, “The Cover Time of Deterministic Random Walks”. The Electronic Journal of Combinatorics 17(1) (2010), R167. DOI 10.37236/439. Electronic Journal of Combinatorics 17(1), R167 (2010). ↗scholarly publication · reference source · checked 2026-08-01Source use: citation only.For Longest rotor-router cover time on the eight by eight grid, the reviewed source scope is Electronic Journal of Combinatorics 17(1), R167 (2010). The packet makes no inference beyond that cited scope.
Packet source. Laura Florescu, Lionel Levine, and Yuval Peres, “The Range of a Rotor Walk”. The American Mathematical Monthly 123(7) (2016), 627. DOI 10.4169/amer.math.monthly.123.7.627. Florescu, Levine, and Peres, The range of a rotor walk, Section 6, Theorem 6.1; Holroyd and Propp, Rotor walks and Markov chains, arXiv:0904.4507, pages 2-3; Friedrich and Sauerwald, The Cover Time of Deterministic Random Walks, EJC 17(1), R167 (2010). ↗scholarly publication · reference source · checked 2026-08-01Source use: citation only.For Longest rotor-router cover time on the eight by eight grid: The sources fix the update convention and prove bounds for every Eulerian graph; the exact 8 by 8 clockwise extremum was absent from the located papers.Also cited at American Mathematical Monthly 123(7), 627-642 (2016), Section 6 and Theorem 6.1.Also cited at Laura Florescu, Lionel Levine, and Yuval Peres, The range of a rotor walk, American Mathematical Monthly 123(7), 627-642 (2016), Section 6 and Theorem 6.1; lower-bound replay in this record.Also cited at Deterministic local search and exact saved-state replay, 2026-07-25.Source named by the research packet.

Original CC0 finite rotor-router extremal problem.

[#P2698] Longest rotor-router cover time on the eight by eight grid

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