Math Mapgenerated 2026-10-25 · a354234
PUBLIC BUILD

run 031Settled

Does the minimum bisection of Cay(G/St(n)) track the Schreier-fibre count |G_n|/2^n — a separator of order n/log n whose exponent climbs toward 1 — or does the exponent 0.76 measured between n = 128 and n = 4096 (run 030) hold? Decides whether the intermediate-growth host beats a 3D lattice as a classical memory beyond n ~ 10^5–10^6.

slug
grig5-bisection
state
run
created
2026-09-27
sealed
2026-09-27
measured
2026-09-27
statistic
b5 = the smallest balanced edge bisection (each side exactly n/2 vertices) of Cay(G/St(5)), n = 4,194,304, generators {a, b, c, d}, found by the procedure named below — METIS (≥ 8 seeds, ufactor 1, ncuts ≥ 4), greedy balanced pair-swap refinement, and a Kawasaki quench (β = 8, ≥ 10^4 sweeps) from each of the METIS cut and the two fibre-aligned seeds; the smallest cut over all of these.
outcome
confirmed
script
R24_grig5_bisection/grig_build.c, R24_grig5_bisection/coset_build.c, R24_grig5_bisection/refine.c, R24_grig5_bisection/analyze.c, R24_grig5_bisection/lift.c, R24_grig5_bisection/project.c, R24_grig5_bisection/collect.py, R24_grig5_bisection/run_metis5.sh, R24_grig5_bisection/run_quench5.sh
artifacts
[R24_grig5_bisection/results/summary.md, R24_grig5_bisection/best5.bits, R24_grig5_bisection/best4.bits, R24_grig5_bisection/best3.bits, R24_grig5_bisection/results/structure.txt, R24_grig5_bisection/results/L5/metis_cuts.txt, R24_grig5_bisection/results/L5/metis_extra_cuts.txt, R24_grig5_bisection/results/L5/metis_rm_cuts.txt, R24_grig5_bisection/results/L5/metis_rm_cuts_2.txt, R24_grig5_bisection/results/L5/metis_rand_cuts.txt, R24_grig5_bisection/results/Q5/metis_cuts.txt, R24_grig5_bisection/results/Q5/metis_more_cuts.txt, R24_grig5_bisection/results/L4/metis_many_cuts.txt, R24_grig5_bisection/results/Q4/metis_cuts.txt]
builds_on
[030]
concepts
[growth-of-groups, graph-theory]
programme
PG-02
source
../lab/runs/031-grig5-bisection.md

Predictionb5 ∈ [65,000, 140,000] — the found cut was 1.00× |G_3|/2^3 = 16 at level 3 and 0.77× |G_4|/2^4 = 256 at level 4, so it tracks the fibre count |G_5|/2^5 = 131,072 to within a factor of two; the level 4 → 5 exponent is ≥ 0.85 and the separator is n/log n, climbing

Falsifierb5 ≤ 40,000 — the exponent ≤ 0.77 held and the host is a ~3D lattice for memories; the fibre structure is not what the cut sees

VerdictCONFIRMED — scored 2026-09-27 (codifier). b5 = 90,112 lies in the sealed band [65,000, 140,000]; the falsifier (≤ 40,000) did not fire. The exact value was predicted under the seal at 18:16 MST, before the quenches finished, and hit: 90,112 = (11/16)·|G₅|/2⁵, the same constant as level 4 (176 = (11/16)·256). The sealed mechanism paragraph (fibre-aligned cut) was wrong — every minimum cuts a-edges only, lengthwise — and the number it predicted was right anyway, because the lengthwise minimum tracks the fibre count with a constant. Recorded as the run's own lesson: a correct number from a wrong mechanism is scored as confirmed and flagged, not celebrated. Claude Code's measurement below; the level-5 spectral test of the constant is in N-028. Original measurement line follows. MEASURED 2026-09-27, unscored — b5 = 90,112 = 0.6875 × |G_5|/2^5 (131,072), inside the sealed band [65,000, 140,000], 2.25× the falsifier's 40,000, 6.7× the Cheeger floor 13,464. Level 4 → 5 exponent log(b5/b4)/log 1024 = 0.900 with b4 = 176 (level 3 → 4: 0.692). Found by the coset-graph route the second note names: METIS on the full graph with random matching or a random initial partition (recursive bisection, ufactor 1, ncuts 4, niter 100; 633 level-5 runs, floor 90,144 — every default-option seed returns exactly 131,072, a symmetric a-edge cut that splits every fibre 50/50 and is not the fibre-aligned cut), the three best cuts (90,144 flat, 90,144 ramp, 90,440) projected onto the ⟨b,c,d⟩-coset graph (they cross no b/c/d edge), then greedy coset swaps (90,134 / 90,136 / 90,338) and a Kawasaki quench on the coset graph (β = 8, 20,000 sweeps): all three reach exactly 90,112, three distinct partitions; lifted to the full graph and recounted, 90,112, a-edges only, exactly balanced. The full-graph greedy pair swap and β = 8 quench from that lift (12,000 sweeps, 515 s) find nothing and stay at 90,112. On the full graph the named refinements add nothing: greedy pair swaps find no improving swap on any METIS cut at any level, and the β = 8 quench (13,500–15,000 sweeps per seed, 3000–3300 s each, nine seeds) leaves 131,072 at 131,072 and 90,144 at 90,144; the fibre-aligned seeds quench to 133,138 (middle double edge, from 262,144, still descending at the cap) and 172,202 (a-edge cut one fibre off, rebalanced, stuck). METIS directly on the level-5 coset graph is worse than on the full graph (668 of 672 runs at 131,072–131,3xx; best 102,676). Validation: level 3 = 16 by every method; level 4 = 180 on the full graph (1,024 seeds) and 176 on the coset graph (18 of 320) — both below run 030's '≤ 198', which is revised to b4 ≤ 176, c4 = 0.6875. 90,112 = 11/16 × 131,072 and 176 = 11/16 × 256: the same fraction of the fibre count at levels 4 and 5, from cuts of the same shape (a ramp in the fibre profile), so the 4 → 5 exponent is log 512 / log 1024 = 0.900 exactly. Every minimum found at every level cuts a-edges only. Graph: 4,194,304 elements (closed form), 8,388,608 edges, no loops or duplicate edges at levels 3–5.

run 031 — sealed bands, data on top

Sealed before the graph was built (2026-09-27, codifier). One statistic, closed constants. Between 40,000 and 65,000 is unanticipated. The Cheeger floor from the measured gap (λ₂/deg = 0.00321 at this quotient) is b5 ≥ λ₂·vol/4 ≈ 13,500; anything below that is an error.

Why the fibre count is the prediction, held with conviction. The Schreier graph of the Grigorchuk group on level n is a path on 2^n leaves — a-edges alternating with b/c/d double edges — and the Cayley graph of G/St(n) covers it, with |G_n|/2^n vertices over every leaf. Cutting the path in the middle costs one or two fibres of edges: |G_n|/2^n or twice that. That is an upper bound on the bisection, exact at level 3 (16) and beaten by 23% at level 4 (≤ 198 against 256), where the optimal cut is not fibre-aligned. So b_n ≈ c·|G_n|/2^n with c ∈ [0.5, 1], and since log₂|G_n| = (5/8)·2^n + 2, the separator is b_n ≈ c·5n/(8(log₂ n − 2)) — of order n/log n, with a local exponent 0.8 (level 3→4), 0.9 (4→5), climbing to 1. Run 030's 0.76 was the level 3→4 step read off two tiny quotients. This is the concrete form of N-026's "n/polylog", and it is why the number matters: the k = 1 memory's barrier is ≈ 0.7·b_n (2D wall entropy, run 030), so against the 3D torus's 2n^{2/3} the host loses at n = 4096 (198 vs 512), and wins by 2× at n = 4.2M if the prediction holds (≈ 100,000 vs 52,000). The 4D torus (2n^{3/4} ≈ 184,000) still wins at this size.

Noted under the seal, not in it (same evening). The Schreier path's a-edges are a perfect matching, so the middle edge of a 32-leaf path is a b/c/d double edge and the balanced fibre-aligned cut costs two fibres, 262,144; one fibre (131,072) is the a-edge cut one fibre off balance. Levels 3 and 4 nevertheless reached 1.00× and 0.77× of one fibre with exact balance, by cuts that thread through the fibre. The band's top, 1.07× one fibre, is therefore a bet that threading keeps working at level 5; a balanced minimum between one and two fibres would score unanticipated, and would say the threading was a small-quotient accident.

Second note under the seal (run 032, same evening). The mechanism paragraph above is wrong: the level-3 and level-4 minima are not fibre-aligned at all — they cut a-edges only, spread over every a-step of the path, every fibre split in half: bisections of the ⟨b,c,d⟩-coset graph (N/4 vertices, 4-regular). Bisecting that graph directly gives 16 at level 3 and 176 at level 4 (the validation threshold "≤ 224" stands; the best known level-4 value is now 176, c₄ = 0.69). The empirical scaling b_n ≈ c·|G_n|/2ⁿ with c ∈ [0.5, 1] still fits both levels, so the band stands as sealed — but the codifier's expectation has moved to its lower half: the a-edge fraction cut fell 25% → 8.6% between levels 3 and 4, and if it falls by the same factor again b₅ ≈ 62,000, just under the band; if it tracks 2/2ⁿ, b₅ ≈ 131,000. The Cheeger floor from the coset graph's own gap (path-like, ~0.019 at level 5) is b₅ ≥ ~20,000. Procedure unchanged, with one addition: also bisect the coset graph directly (N/4 = 1,048,576 vertices), which is where the minimum was found at level 4.

Third note under the seal — a prediction on the exact value, made 2026-09-27 18:15 MST, before the level-5 quenches finish (Claude Code's summary at this moment: METIS floor 90,144; quenches running). Bisecting the level-4 coset graph gives 176 = (11/16)·256 exactly, and 90,144 = (11/16)·131,072 + 32. The codifier predicts the level-5 minimum is 90,112 = (11/16)·|G₅|/2⁵ exactly, i.e. the a-edge fraction cut is 11/2^{n+3} for n ≥ 4 and the constant c = 11/16 is structural, not a glass. The level-4 optimum has the structure to match: it cuts 24, 20, 20, 24, 24, 20, 20, 24 a-edges at the eight a-steps of the Schreier path, and the fraction of each K-coset block on the + side runs 11/16, 11/16, 41/64, 19/32, 1/2, 13/32, 23/64, 5/16, 5/16 from one end of the path to the other — a tilted cut, neither crosswise nor lengthwise, symmetric about the middle. If the quench lands on 90,112, N-028's last standing sentence ("the error term is a glass, not a zeta function") falls on its first half: the minimum is crystalline; only the landscape above it is glassy. If it lands elsewhere, the 11/16 is a level-4 accident. Not a seal — a dated prediction recorded so that the result cannot be read back into it.

Validation. Level 3 must return 16 and level 4 must return ≤ 224 (METIS, run 030); if the procedure finds below 198 at level 4, report it — it revises run 030's "≤ 198" and the c above.

Sizing. Build the Cayley graph in C: BFS over G/St(5) with elements stored as their permutation of the 32 leaves (32 bytes), right-multiplication by a generator = index permutation, a hash table of 4.2M keys; 8.4M edges to a METIS graph file (~100 MB). gpmetis or pymetis at that size is minutes and ~2 GB. Port the action from R22_grigorchuk_cell/grig.py (a flips the first bit; b = (a,c), c = (a,d), d = (1,b) on the tail). Fibre-aligned seeds: partition by the position of g's image of leaf 0 on the Schreier path (positions 0–15 vs 16–31, and the a-edge-shifted 0–14 vs 15–31 rebalanced by moving the fewest vertices).

Measured, same day

b5 = 90,112 = 0.6875 × |G_5|/2^5 = 131,072 — inside the sealed band, 2.25× the falsifier's 40,000, 6.7× the Cheeger floor 13,464. Level 4 → 5 exponent log(b5/b4)/log 1024 = 0.900 with b4 = 176; level 3 → 4, log(176/16)/log 32 = 0.692. Unscored — outcome: is the codifier's. Everything below is in R24_grig5_bisection/ (README, results/summary.md, the best partition per level as a bit vector).

What was built

Cay(G/St(n)) for n = 3, 4, 5 in C (grig_build.c; the action ported from R22_grigorchuk_cell/grig.py, elements as permutations of the 2^n leaves, BFS from the identity in generator order a, b, c, d, a hash table of 4.2M keys): 128, 4,096 and 4,194,304 elements, each equal to the closed form 2^(5·2^(n−3)+2); the level-5 BFS takes 1.1 s and 295 MB. The graph is 4-regular and simple at all three levels — zero loops and zero duplicate edges dropped — with 256, 8,192 and 8,388,608 edges. The Schreier graph on the leaves is a path with the a-edges at even steps and b/c/d double edges at odd steps (position 0 = the leaf 1^n); the covering used for the fibre seeds is g ↦ g⁻¹(0), the map that intertwines right multiplication with the Schreier action ("g's image of leaf 0" in the left-Cayley-graph convention), and every fibre has exactly |G_n|/2^n vertices. Per the second note under the seal, also the ⟨b,c,d⟩-coset graph Q (coset_build.c; N/4 vertices, 4-regular, simple at all three levels): a balanced bisection of Q is a balanced a-edge-only bisection of the full graph with the same cut, and every Q result was lifted and recounted on the full graph (lift.c, analyze.c).

The procedure, stage by stage
stagelevel 3 (fibre 16)level 4 (fibre 256)level 5 (fibre 131,072)
METIS, full graph, default options (rb and k-way, shem; ufactor 1, ncuts 4, niter 100), 32 seeds16194–256131,072, all 32 seeds
METIS, full graph, more seeds and options16180 (1,024 seeds; 2 at 180)90,144 (633 runs; rb + random matching: 80 of 480 in 90,440–91,000; rb + random initial partition: 2 of 121 at 90,144)
rebalance to exactly n/2exact already≤ 16 movesMETIS output already exactly balanced
greedy balanced pair swaps on the METIS cuts0 swaps0 swaps0 swaps
Kawasaki quench β = 8 from the METIS cuts16180 (8 runs × 2×10⁶ sweeps)90,144 stays 90,144; 131,072 stays 131,072 (9 seeds, 13,500–15,000 sweeps, 3000–3300 s each)
fibre seed, middle double edge (T15) → quench32 → 16512 → 262262,144 → 133,138 (13,785 sweeps, still descending at the cap)
fibre seeds, a-edge one fibre off (T14, T16) → rebalanced → greedy → quench16 (48:80) → 20 → 20256 → 322 → 322131,072 (15:17) → 172,202 → 172,202, stuck
coset graph Q: METIS on Q (320 / 320 / 672 runs)16, every run176 (18 runs; k-way ≥ 240)102,676 (1 run); 668 runs at 131,072–131,3xx
Q: fibre seeds T14 / T16 rebalanced by cosets → quench on Q——130,820 → 130,734; 131,022 → 131,022
Q: the best full-graph METIS cuts projected → greedy coset swaps → quench on Q (20,000 sweeps)——90,144 → 90,134 → 90,112; 90,144 → 90,136 → 90,112; 90,440 → 90,338 → 90,112
lifted to the full graph and recounted; full-graph greedy + quench from the lift16176 → 176 (2×10⁶ sweeps)90,112 → 90,112 (12,000 sweeps)
smallest balanced cut16 = 1.000 × fibre176 = 0.6875 × fibre90,112 = 0.6875 × fibre
Validation

Level 3 returns 16 by every method. Level 4 is ≤ 224 as required, and the procedure finds 180 on the full graph and 176 on the coset graph — below run 030's "≤ 198", which is revised: b4 ≤ 176, c4 = 176/256 = 0.6875, and the prediction line's "0.77× at level 4" reads 0.69×. The Kawasaki port was checked against R23_ising_barrier/ising_fe.c (kaw mode) on the level-3 graph at β = 0.3, 0.6, 1.0: mean cuts 75.46 / 75.47, 30.51 / 30.41, 16.80 / 16.90 over 2×10⁵ sweeps. Every saved partition's cut and balance were recounted from scratch (refine verifies before writing; analyze recounts a bit vector independently).

What the numbers say, without scoring
run 031 — sealed bands, data on top

generated 2026-10-25the lab index