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

- ID: `P2698`
- Reference: `rotor-router-eight-grid-cover`
- Page: https://theoremdb.org/statements/P2698
- Record maturity: Reviewed problem with recorded work

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

### Remarks

- **Remark.** A rotor index is taken in the listed local cyclic order and is incremented before the move.
- **Remark.** The cover time counts moves up to the first visit to the last unvisited vertex.

### What counts as a solution

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

## Status

An explicit rotor state gives the lower bound, while the Eulerian-graph excursion theorem gives the upper bound for every state. [4](#reference-4)

## Work

### Evidence for the current status

**Computation 1 (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.

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.

### Background and intake notes

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: Number vertices row-major from 0 through 63. One incumbent starts at vertex 39 with rotor-index vector listed in the computation field.

### Prior approaches

- **Route 1** (supported): 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](#reference-4) [1](#reference-1) [3](#reference-3) [2](#reference-2)

### Open directions

- **Route 2** (reproduced): Single-rotor mutations found a long-lived state concentrated around the lower-left start, while leaving a large certified gap. [4](#reference-4)

### Runnable artifacts

- **Artifact 1** (reproduced): Standard-library Python fixes every ordering convention, validates the rotor vector, and replays all 1,282 moves.

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

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `rotor-router-eight-grid-cover`, 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. <a id="reference-1"></a>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 https://arxiv.org/abs/0904.4507
   - preprint; reference source; arXiv:0904.4507, checked 2026-08-01; checked 2026-07-25
   - Source 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.
2. <a id="reference-2"></a>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) https://doi.org/10.1007/s00453-003-1030-9
   - scholarly_publication; reference source; checked 2026-08-01
   - Source 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.
3. <a id="reference-3"></a>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) https://doi.org/10.37236/439
   - scholarly_publication; reference source; checked 2026-08-01
   - Source 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.
4. <a id="reference-4"></a>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) https://doi.org/10.4169/amer.math.monthly.123.7.627
   - 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
   - scholarly_publication; reference source; checked 2026-08-01
   - Source 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.
   - Source named by the research packet.