Nonrepetitive colouring · lattices
Colour the points of a grid. Now walk along the grid, one step at a time, never visiting a point twice, and write down the colours as you go. If the first half of what you wrote repeats exactly in the second half, like red blue, red blue, the colouring has failed. A colouring that no walk can ever catch out this way is called nonrepetitive.
How many colours do you need? For the ordinary square grid, somewhere between 6 and 12, and nobody knows where. The lower bounds come from a brute-force fact: find one finite patch of the grid that cannot be coloured with k colours, and k+1 colours are forced everywhere.
A paper from October 2025 pushed these bounds up for three lattices by counting colourings of growing patches until the count hit zero. This session rebuilt that computation as a satisfiability problem with machine-checkable refutations, and the answer came out in three parts: one of their theorems is confirmed, one is confirmed but by a different patch than the one they report, and one has no valid proof, because the patch their table says cannot be coloured with 8 colours can be.
The figure is that patch, with the 8-colouring their table says does not exist.
Everything below is the technical version. Section 3 is the audit; section 5 says what the method could not reach.
A vertex colouring is nonrepetitive if no simple path on an even number of vertices reads as a square ww in the colours, and π(G) is the least number of colours of such a colouring. For the square grid P□P, the king's graph P⊠P and the triangular lattice T₃, the best published lower bounds are 6, 9 and 9, due to Tao, Zhang, Zhang and Toole (arXiv:2510.11263, October 2025), obtained by counting nonrepetitive colourings of growing patches until the count reaches zero.
This note re-derives those questions as SAT instances whose path constraints are generated lazily from counterexample colourings, certifies every refutation with a DRUP proof checked by two independent checkers, and verifies every witness by exhaustive path enumeration. The outcome: π(P□P) ≥ 6 confirmed as a rediscovery of their Theorem 1.8, with a certificate; π(P⊠P) ≥ 9 confirmed by an independent proof on a 23-vertex patch, while their Table 2's death index of 20 is wrong, since the 20- and 22-vertex patches are 8-colourable; their π(T₃) ≥ 9 has no valid proof, because the 23-vertex patch their Table 3 declares uncolourable admits nonrepetitive 8-colourings under both embeddings, as do the 5×5 blocks containing it; and, new, π(T₃) ≥ 8 certified, from a 37-vertex hexagon with no nonrepetitive 7-colouring.
Upper bounds are Tao (2026) and Kündgen-Pelsmajer (2008) as cited in arXiv:2510.11263, both secondary here. The triangular upper bound is inherited from the king's graph.
Each vertex gets one variable per colour with an exactly-one constraint. For each pair {u, v} that occurs as a matched pair (vi, vk+i) of some path there is an equality variable Euv, forced true when u and v share a colour, and a path on 2k vertices contributes the single clause saying that not all k matched pairs are equal. Colour symmetry is broken by fixing the colour of a central vertex and of two of its neighbours. Every clause is a necessary condition, so a refutation of any subset of the path clauses proves the patch has no nonrepetitive colouring, while a satisfying assignment only says the encoded paths are not repetitive.
That asymmetry is what makes lazy generation work. Paths up to 6 or 8 vertices are encoded eagerly; the solver returns a colouring; a separate program lists every repetitively coloured path of that colouring up to twice the target length; those clauses are added and the solver runs again. For the 5-colour square-grid instance this needed 906 lazily added clauses instead of the 109,048 eager clauses for all 10-vertex paths on the 7×7 grid, and ran in 1 second instead of 11.
Everything that matters is checked twice. The CNF is validated by a program written separately from the encoder, which rebuilds the graph and confirms that every path clause corresponds to a genuine simple path. Every refutation is re-solved by Glucose 4.2 with proof logging, and the DRUP proof is checked both by drat-trim and by this repository's own from-the-definition checker. Every witness is checked by enumerating all simple paths of the patch, billions of them, with a program sharing no code with the one used inside the lazy loop.
The 41-vertex spiral patch of the square grid has no nonrepetitive 5-colouring, and the 40-vertex one has one. Hence π(P□P) ≥ 6. This is Theorem 1.8 of arXiv:2510.11263, found again here; the contribution is the certificate, not the bound.
859 variables, 20,251 clauses of which 1,792 path clauses were generated lazily; DRUP proof 62,807 lines, verified by both checkers in about a second each. The 40-vertex witness was checked by enumerating 5,214,680,104 directed simple paths with zero repetitions. The counting replication reproduces the paper's death index exactly: n(40) = 1, n(41) = 0.
The 23-vertex spiral patch of the king's graph has no nonrepetitive 8-colouring, so π(P⊠P) ≥ 9. The 20- and 22-vertex patches do have nonrepetitive 8-colourings, so the death index 20 printed in Table 2 of arXiv:2510.11263 is wrong. The theorem it supports is true; the computation reported for it does not support it.
435 variables, 43,838 clauses, 9,596 of the path clauses lazy; proof 740,087 lines, trimmed to 666,403, verified by both checkers. The witnesses at 20 and 22 vertices survive enumeration of 659,935,616 and 3,980,417,538 directed simple paths. The replication gives n(20) = 186, n(21) = 278, n(22) = 32, n(23) = 0, and the SAT pipeline independently gives satisfiable at 22 and unsatisfiable at 23.
The hexagon of radius 3 in the triangular lattice, 37 vertices and 90 edges, has no nonrepetitive 7-colouring. Hence π(T₃) ≥ 8. The radius-2 hexagon already rules out 6 colours, giving π(T₃) ≥ 7 in a tenth of a second.
925 variables and 265,459 clauses, of which 241,053 path clauses were added lazily over 193 iterations; Glucose refutes it in 198 seconds with a proof of 2,605,263 lines, verified by drat-trim in 234 seconds and by the repository's checker in 762 seconds. That proof is 25 MB even trimmed and compressed, too large to commit, so it is reproducible rather than downloadable: the committed CNF regenerates it in about four minutes. The unsatisfiable core, 22,121 clauses, is committed as well. Before this, the only lower bound for T₃ with a valid proof was the 6 inherited from the square grid.
The 23-vertex spiral patch of T₃ admits a nonrepetitive 8-colouring under both natural embeddings of the paper's vertex order, and so do the two 5×5 blocks containing it. Table 3 of arXiv:2510.11263 records n(23) = 0 for this configuration, and Theorem 1.9, π(T₃) ≥ 9, rests on that zero, so that theorem has no valid proof. It is not refuted: π(T₃) ≥ 9 may well be true, and nothing here says otherwise.
| patch | vertices | edges | directed simple paths enumerated | repetitions |
|---|---|---|---|---|
| 23-vertex prefix, offset embedding | 23 | 51 | 194,113,939 | 0 |
| 23-vertex prefix, sheared embedding | 23 | 50 | 119,984,959 | 0 |
| 5×5 block, sheared | 25 | 56 | 898,699,089 | 0 |
| 5×5 block, offset | 25 | 56 | 871,141,833 | 0 |
All four counts were reproduced on 20 September 2026 by a checker written independently for this page, digit for digit, with zero repetitions in every case. Since the 23-vertex prefix lies inside a 5×5 block however the rows are shifted, and both embeddings of that block are 8-colourable, no placement of the paper's vertex order can give n(23) = 0.
The source of the discrepancy is not identified. The authors' code was not reachable from the machine that ran this, and the counts in their Table 3 fall below the canonical counts from i = 15 onwards, which cannot happen for the same graph, since their convention only inflates counts. A denser graph than T₃ would produce an earlier death.
Three colourings mark the edge of what the lazy loop reached. On the 10×10 square grid there is a 6-colouring with no repetition on any path of at most 18 vertices, though it does have repetitions at 20 and 24, so a proof of π(P□P) ≥ 7 within this method has to use paths that long. A 30-vertex king patch has a 9-colouring clean to 16 vertices. The radius-3 triangular hexagon has an 8-colouring clean to 16 vertices, and on the radius-4 hexagon the loop was stopped after 1,161 iterations and 5.75 million lazy clauses with every iteration still producing about 5,000 new repetitive paths.
These are numerical: statements about the reach of the method, not about the true values. None of them is a nonrepetitive colouring of its patch.
The obstruction is not solver speed. It is the growth of the set of relevant repetitive paths with patch size and colour count, and the observed repetition lengths, up to 24 vertices on a 10×10 grid, suggest that a further bound needs either much larger patches or a structural lemma about which repetitions can matter.