Fabian Arevalo

Erdős problem #475 · additive combinatorics · session 2026-08-30

Graham's rearrangement conjecture, certified for every prime up to 37

Nearly two billion dilation orbits decided exhaustively, a witness ordering for every one of them, zero failures. The published record was an uncertified 2016 random search through order 25; the smallest undecided prime is now 41.
30 August 2026 · AI-assisted (Claude), see disclosure · code, data and certificates

Start here, no maths required

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.

Clock 13
The walk, computed in your browser. The dots are the positions 0 to p−1 on the clock. A subset is drawn at random, then laid out in some order, and the arrows trace the running totals from 0. A position visited twice is ringed, and the run is a failure. Random order usually fails once the subset is large. Find a valid order runs the same three-tier search the certified computation uses, shrunk to one set: sixty-four seeded shuffles, then a swap local search, then randomized depth-first search. It has never needed the last tier here, which is exactly what the full run found too.

What this note adds

  1. Every prime clock up to 37 is now settled, with certificates. Every subset of every size, 1,954,471,973 essentially different cases covering 70,066,181,009 subsets, each one given an explicit good order. Nothing failed. The clocks of size 29, 31 and 37 had never been checked by anyone.
  2. One awkward family, cleared out to 61. There is a family of sets that the known explicit construction provably cannot build and that the literature has treated inconsistently: the sets that omit zero and one plus-minus pair, whose entries add to zero. Those are certified for every prime from 7 to 61.
  3. The hard cases are the nearly-full sets, and that is a pattern. Random shuffling settles almost everything. At clock 29 and 31 exactly one set each resists, and it is the full set, the very case Graham proved by hand in 1971. At 37 the resisters number 124 out of 1.9 billion, and they all sit within five of the top.
  4. Half of the next prime is done too. At 41, every subset of size 28 or more is certified, which is 9.1 billion subsets.

Everything below is the technical version. The map in Section 2 is the fastest way to see what moved.

AbstractSummary of results

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

Section 1The statement, and the results

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.

R1 · CERTIFIED

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.

R2 · CERTIFIED

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.

R3 · CERTIFIED

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.

Section 2What moved

hover a cell
The frontier, before and after. One column per prime from 7 to 61, one row per subset size t from 2 to p−1, drawn from the committed 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.

Section 3Method, and the certificate model

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.

porbits decidedneeded the DFS tierfailureswall time
≤ 23209,93100< 1 s
299,587,5781013 s
3135,792,5661058 s
371,908,881,898124091 min
41, t ≥ 28227,999,0524,58402.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.

Section 4Which sets resist

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.

The resistant band, measured. For each subset size, the fraction of orbits that the cheap tiers failed on and that fell through to randomized depth-first search, read from the committed per-layer result files. At p = 29 and 31 the fraction is zero everywhere except at t = p−1, where it is 1: one orbit, the full set Fp*, the case Graham proved by hand in 1971. At p = 37 the band starts at t = p−5 and at p = 41 at t = p−7, so it widens with p while staying a vanishing fraction of all orbits. Note the axis: the tallest bars stand over layers holding a handful of orbits, not billions.

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.

Section 5Caveats

Section 6Open questions

  1. Close p = 41 in the middle. The remaining window is 13 ≤ t ≤ 27 on the refereed record, and the layer counts there are an order of magnitude above the p = 37 peak of 252,088,496 orbits at t = 18.
  2. A uniform construction for the zero-sum p−3 layer. The three natural families are dead and the geometric route is closed, so this needs a genuinely different idea; fifteen certified witnesses are committed as data for whoever wants to guess the pattern.
  3. Explain the resistant band. It begins at t = p−1, p−5, p−7 at p = 31, 37, 41. Whether the offset grows linearly in p or slower is measurable at 43 with about a day of compute.
  4. An effective version of any of the four asymptotic results. That, and not more computing, is what would actually finish the problem.