Erdős problem #475 · additive combinatorics · session 2026-08-30
Pick a prime, say 13, and write the numbers 1 to 12 around a clock face with twelve hours. Choose some of them. Now put your chosen numbers in a line, in whatever order you like, and walk around the clock: start at 0, step forward by the first number, then by the second, and so on. You land on a sequence of positions. The question is whether you can always choose the order so that you never land on the same position twice.
Some orders fail. Take 1, 2, 3, 4 on a clock of 5: in that order the running positions are 1, 3, 1, 0, and you hit position 1 twice. Reorder them as 1, 3, 4, 2 and the positions are 1, 4, 3, 0, all different. Ronald Graham asked in 1971 whether a good order always exists, for every prime clock and every choice of numbers. Nobody has found a set that cannot be arranged, and nobody has proved none exists.
The strange thing about this problem is what has been proved. Since 2024 four papers together show the conjecture is true for every large enough prime, but none of them says how large, and the one that does give a number is far too weak to reach any prime you could name. So the small primes, the ones a person would actually try, are exactly the ones the theory cannot touch. Before this session the published record was a 2016 search that got through clock size 25, using random shuffling in Mathematica, storing nothing. The figure below is that walk, live.
Everything below is the technical version. The map in Section 2 is the fastest way to see what moved.
Graham's rearrangement conjecture (Erdős problem #475) states that for a prime p, every subset A ⊆ Fp ∖ {0} can be ordered so that its partial sums are pairwise distinct mod p. It is proved for all sufficiently large p by the combination of four ineffective asymptotic results, and for |A| ≤ 12 (refereed), |A| ≤ 20 (2026 preprint), and for nonzero-sum A of size p−1, p−2, p−3. The largest published per-prime verification was the uncertified 2016 random search of Archdeacon–Dinitz–Mattern–Stinson through cyclic order 25.
This session closes every prime p ≤ 37 by certified exhaustive computation: all 1,954,471,973 dilation orbits of nonempty subsets (70,066,181,009 subsets), every one receiving an explicit witness ordering, with orbit counts matching an independent Burnside computation on all 173 (p,t) cells, zero failures. The smallest prime at which the conjecture is not fully decided, by proof or certified computation, is now 41. Separately the zero-sum size-(p−3) layer, which the Hicks–Ollis–Schmitt construction provably cannot reach and which the published record treats inconsistently, is certified for every prime 7 ≤ p ≤ 61. At p = 41 the dense half t ≥ 28 is also closed (227,999,052 orbits, 9,119,901,052 subsets).
For A = {a1,…,at} ⊆ Fp ∖ {0}, an ordering is valid if the partial sums sm = aσ(1)+⋯+aσ(m) are pairwise distinct in Fp. Zero may occur among them, once. Graham's conjecture: every A has a valid ordering.
For every prime p ≤ 37 and every t with 2 ≤ t ≤ p−1, every A ⊆ Fp ∖ {0} of size t admits a valid ordering. 1,954,471,973 canonical dilation-orbit representatives decided (45,590,075 across p ≤ 31 in 72 s; 1,908,881,898 at p = 37 in 91 min), covering 70,066,181,009 subsets. Every representative received an explicit witness; nothing failed; nothing required the complete-search tier; per-cell representative counts equal the independent Burnside counts exactly on all 173 cells.
For every prime 7 ≤ p ≤ 61, the zero-sum sets of size p−3, precisely the sets Zp ∖ {0, x, −x}, admit valid orderings. One dilation orbit per prime, with the witness for the representative {2,…,p−2} committed and independently re-verified for each p.
At p = 41, every A with |A| ≥ 28 admits a valid ordering: layers t = 28…40 swept in full, 227,999,052 orbits, 9,119,901,052 subsets, Burnside-exact on all 13 cells, zero failures, 2.6 h. This leaves 13 ≤ t ≤ 27 open at p = 41 on the refereed record, or 21 ≤ t ≤ 27 if the 2026 preprint is admitted.
Two elementary lemmas do the heavy lifting. L1 (PROVED). If c ∈ Fp* and an ordering of A is valid, then the same ordering of cA is valid, since partial sums scale by c and distinctness survives. So admissibility is a dilation-orbit invariant and one representative per orbit suffices; that is what turns 70 billion subsets into 2 billion decisions. L2 (PROVED). The sets Zp ∖ {0, x, −x} form a single dilation orbit, represented by {2,…,p−2}; that is what turns fifteen primes of gray zone into fifteen witnesses.
frontier.csv. In Before, solid cells are covered by a
refereed proof, half-tone by the unrefereed 2026 preprint, and empty cells were
open. In After, solid cells are certified by this session's exhaustive
sweep. Flip between the two: everything at p ≤ 37 fills in, the
dense top of p = 41 fills in, and a single cell on the
t = p−3 diagonal fills in at each of 43, 47, 53, 59 and 61. The
open region now begins in the middle of the p = 41 column.The four asymptotic papers of 2024 to 2026 (Kravitz; Bedert–Kravitz; Pham–Sauermann; and the BBKMM line) prove the conjecture for all sufficiently large p, but their constants are ineffective. The one effective bound available, Kravitz's, gives only t ≤ 2 at p = 43. This is why the small primes are the ones that need computing, and why moving from 25 to 37 is worth doing at all.
Transversal. Enumerate the subsets containing 1 and keep A when its bitmask is minimal among the |A| dilations (1/a)·A for a ∈ A, each of which again contains 1. That picks exactly one set per orbit. The implementation's correctness is witnessed by an exact Burnside match on every cell, against (1/(p−1))·∑d | gcd(p−1,t) φ(d)·C((p−1)/d, t/d).
Per-set decision, deterministic given the run seed, in five tiers: 64 seeded shuffles; a swap-move local search minimizing collided partial-sum slots; 16 randomized-order depth-first restarts with growing node budgets; a deeper local search; and finally a complete deterministic search whose exhaustion would exhibit a counterexample. In the entire computation nothing reached the last two tiers. Every returned witness is re-scanned from the definition before being reported.
| p | orbits decided | needed the DFS tier | failures | wall time |
|---|---|---|---|---|
| ≤ 23 | 209,931 | 0 | 0 | < 1 s |
| 29 | 9,587,578 | 1 | 0 | 13 s |
| 31 | 35,792,566 | 1 | 0 | 58 s |
| 37 | 1,908,881,898 | 124 | 0 | 91 min |
| 41, t ≥ 28 | 227,999,052 | 4,584 | 0 | 2.6 h |
What the certificate is, and what it is not. Decisions are deterministic given the committed seed. Roughly 72,000 sampled witnesses, plus every set that reached the DFS tier, are committed and independently re-verified by a clean-room checker sharing no code or move types with the engine. The remaining witnesses are reproducible bit for bit but not stored, because 70 billion orderings would be terabytes. So the claim's strength is exhaustion, plus Burnside-exact orbit counts, plus reproducibility. It is not a per-set witness archive, and this page does not pretend otherwise.
The independent verifier also re-decided random samples across the full previously-open windows from scratch: every layer 13 ≤ t ≤ p−3 at p = 29, 31 and 37, with zero failures anywhere, and self-tests including planted invalid witnesses. A full p = 29 rerun under heavy CPU contention reproduced the result lines identically and the witness-sample file byte for byte.
Almost nothing is hard. Sixty-four random shuffles or a swap local search decide everything except a thin band at the top, and that band is where the structure is.
Two negative results are worth recording, because both close routes that look promising from a distance. Three natural explicit-construction families for the zero-sum p−3 layer are structurally dead: two-block and rotated zigzags admit zero valid parameter choices across all 74 primes below 397. And the geometric-series route is closed by a clean obstruction. The set {2,…,p−2} is the shifted power run {1 − 2i+1} when 2 is a primitive root, but the shift breaks partial-sum injectivity, with the first collision at p = 11, and an unshifted run can never miss the antipodal pair {1, −1}, since 1 and −1 are never consecutive powers of a primitive root for p > 3.