Math Mapgenerated 2026-10-25 · a354234
PUBLIC BUILD

run 041Settled

Run 036 measured edge expansion of the ⟨b,c,d⟩-coset graph at 0.78 of a random 4-regular graph's at s = N/8, and P-026 read the intermediate cell's code ceiling from it. But the quantity every expander-code decoder actually consumes — Sipser–Spielman's bit-flipping guarantee, Tanner's — is unique-neighbour expansion — the number of vertices outside S with exactly one neighbour in S — and a Tanner code on a 4-regular graph is degenerate anyway (rate-positive local codes on four bits have distance 2). So the sealable code question is the theorem's hypothesis, not the code: does the host have unique-neighbour expansion at all, at any level, and does the random control keep it?

slug
unique-neighbour-expansion
state
run
created
2026-09-27
sealed
2026-09-27
statistic
The coset graph is bipartite (the a-count mod 2 is a homomorphism killing b, c, d), so S lives in one colour class, as variables do in a Tanner graph. u_G(s) = min over |S| = s within one class of |U(S)|, U(S) = {v ∉ S : |N(v) ∩ S| = 1}, by simulated annealing on |U| with swap moves at fixed |S| (β from 0.3 to 8 over 60 steps, 100·s proposals per step), best of 20 seeds; script R23_ising_barrier/uniq.c, driver R23_ising_barrier/uniq.py. Clause 1: level 4 (N = 1024, 512 per class) at s = 8, 16, 32, 64, 128, 256 and level 3 (N = 32) at s = 2, 4, 8, against random (4,4)-biregular bipartite graphs of the same N (configuration model, simple, seed 1). ρ_U(s) = u_coset(s)/u_rand(s). Clause 2 (M5): level 5 (N = 2²⁰, 2¹⁹ per class) at s = 2¹⁹/8 = 65,536 and 2¹⁹/32, same schedule, best of 20, random (4,4)-bipartite control at the same N. Clause 3 (M5, run 036's instrument extended): the edge-expansion ratio ρ_Φ(N/8) at level 5 — Φ = min |∂S|/|S| over |S| = N/8 by fixed-magnetisation Kawasaki anneal, best of 20 (ising_fe kaw mode, the sealed parameters of run 036) — coset graph against a random 4-regular graph at N = 2²⁰ (the one built for run 040 clause 2 serves).
script
R23_ising_barrier/uniq.c
artifacts
[R23_ising_barrier/uniq.json, R23_ising_barrier/uniq.log, R23_ising_barrier/rb4_32.edges, R23_ising_barrier/rb4_1024.edges]
measured
2026-09-28
outcome
unanticipated
builds_on
[036, P-026]
concepts
[growth-of-groups, graph-theory, information-theory]
programme
PG-02
source
../lab/runs/041-unique-neighbour-expansion.md

PredictionClause 1 — ρ_U(128) ∈ [0.05, 0.40] and u_coset(128) ≤ 60, against u_rand(128) ∈ [80, 260]: the host's unique-neighbour expansion is a small fraction of the random graph's, far below its edge-expansion ratio of 0.78, because the (ad)⁴ relator puts every vertex on 4-cycles whose opposite corners share both neighbours. The Sipser–Spielman condition |U(S)| > 2|S| = 256 at s = 128 fails on the host by a factor of four or more. Level 3: u_coset(4) = 0. Clause 2 — ρ_U(65,536) ∈ [0.02, 0.40] at level 5; the failure is structural, not a small-N effect. Clause 3 — ρ_Φ(N/8) at level 5 ∈ [0.55, 0.85]: edge expansion loses at most 0.25 of its ratio per level, which is "graceful" in P-026's sense (slower than 1/log N would require going 0.78 → 0.39).

FalsifierClause 1 — ρ_U(128) ≥ 0.70 or u_coset(128) ≥ 200: unique-neighbour expansion tracks edge expansion after all and the 4-cycle argument does not bite. Clause 2 — ρ_U(65,536) ≥ 0.70. Clause 3 — ρ_Φ(N/8) ≤ 0.35 at level 5: edge expansion collapses between levels 4 and 5, faster than 1/log N, and the code ceiling read in P-026 is wrong in the direction of optimism. Control: u_rand(128) outside [80, 260] withdraws clause 1 (the annealer is not finding minima on the graph it should find them on).

VerdictClause 1 withdrawn (control band miscalibrated; the zero stands as the theorem N-034). Clause 2 moot (zero at every level by construction). Clause 3 UNANTICIPATED — ρ_Φ(N/8) at level 5 = 0.4233 (coset |∂S| = 59,716, Φ = 0.4556; random 4-regular at N = 2²⁰ |∂S| = 141,064, Φ = 1.0762; best of 20, run 036's instrument unchanged), below the predicted [0.55, 0.85] and above the falsifier's 0.35. The ratio fell 0.357 in one level against the sealed 'at most 0.25'; the 1/log N rate the seal called the pessimistic direction would have given 0.39. Graceful in the weak sense only: ρ_Φ·log₂N is 7.8 at level 4 and 8.5 at level 5, so the decay is consistent with 1/log N, not slower.

Sealed 2026-09-27 (codifier), with one pre-seal glimpse recorded. Before this seal was written the annealer was sanity-tested: level 3, s = 4, both classes, returned 0 unique neighbours (random bipartite: 2); one quick, unconverged anneal on level 4 at s = 128 (20 steps, 20 sweeps, one seed) returned 20 unique neighbours with vertex boundary 234 and edge boundary 512. The prediction was written knowing those two numbers; it would have been written differently without them (the first draft expected unique-neighbour expansion to track edge expansion at 0.6–0.95). That is why the seal says what it says, and it is recorded so the score is read with it. Between prediction and falsifier is unanticipated.

Why this retires two list items. "Tanner code on the coset graph" (list item 4) cannot be built at degree 4: the only rate-positive local codes on four bits have distance 2, the Tanner code is the cycle space, and its distance is the girth — 4, by the (ad)⁴ relator. The Sipser–Spielman distance bound needs λ/d below the local relative distance, and for a random 4-regular graph λ/d ≈ 0.87, so the theorem is vacuous for the control as well. What can be sealed is the theorem's hypothesis. "Level-5 s\*(N)" (list item 5) is clause 3 here in its cleaner form: not the size at which the ratio halves (it never halves at level 4) but the ratio at a fixed fraction of the graph, one level up.

What the relators do. In the Cayley graph, (ad)⁴ = 1 is an 8-cycle alternating a and d edges. Contracting each ⟨b,c,d⟩-coset to a point keeps the four a-edges and identifies the d-edge endpoints, so it becomes a 4-cycle of the coset graph. Two vertices at distance 2 on such a square share both neighbours; a set built from opposite corners of squares has no unique neighbours at all. This is a property of the group's relators, present at every level, and it is orthogonal to amenability — an expander with 4-cycles would have the same defect. The edge-expansion profile (run 036) never saw it because an edge counted twice into the same vertex is still two boundary edges.

If clause 1 confirms, the code reading of the host changes. The bound in P-026 (distance ~ expansion × N ~ N/log N) assumed the Tanner machinery applies with a constant-factor loss. It does not apply at all, at any N, for the same reason the girth is 4. Whatever code the intermediate cell can carry is not an expander code on this graph; the G² construction (P-036) is the next thing to test, because squaring the graph removes the 4-cycles' effect on the local code while keeping the host's expansion.

---

Clause 1, measured the same evening — WITHDRAWN as sealed, and a theorem found

graphs = 8163264128256
coset, level 4 — u(s)000000
random (4,4)-bipartite, N = 1024 — u(s)8101918100
ρ_U(s)00000—

Level 3: coset 0, 0, 0 at s = 2, 4, 8; random 2, 2, 0.

Scored as written. The control clause fires: u_rand(128) = 10 lies outside the sealed band [80, 260], and the seal says that withdraws clause 1. The band was miscalibrated — estimated from a random set rather than the minimum over sets, and at degree 4 the minimum over sets is small on every graph — so the withdrawal is the codifier's error, not the annealer's. Recorded as such; the clause is not scored. The prediction, had it been scored, would have been unanticipated: ρ_U = 0.000 lies below the band [0.05, 0.40], and u_coset(128) = 0 ≤ 60.

Why zero is exact, not an anneal result (N-034). The coset graph's edges are exactly 512 edge-disjoint squares (each a-edge on exactly one (ad)⁴ square). Each left vertex is on two squares, so left vertices and squares form cycles — all of length 8 at level 4, 4 at level 3, 2ⁿ⁻¹ in general. The left vertices of one cycle have every neighbour hit exactly twice: U = ∅ at |S| = 2ⁿ⁻¹ and at every multiple of it, which is precisely the set of sizes the annealer returned zero on. Verified by explicit construction at both levels.

Clause 2 withdrawn as moot: the theorem holds at every level; there is nothing to measure at level 5. Clause 3 stands — the edge-expansion ratio at level 5, run 036's instrument — and is the one measurement left in this run, for the M5. State stays open for it.

What changes. Not "the host's expander-code ceiling is a constant factor below random's" but "there is no expander code on this graph, at any N, and the reason is the relators, not the growth". The code question moves to the squared graph, P-036.

Clause 3 scored 2026-09-28 (lab chat measured at a0a5acd, R23_ising_barrier/phi5.py and phi5.json; codifier scores). ρ_Φ(N/8) = 59,716/141,064 × (same s) = 0.4233: unanticipated, between the prediction [0.55, 0.85] and the falsifier ≤ 0.35. Two readings under the seal. (1) The decay from level 4 (0.78) is at the 1/log N rate, not the graceful one: ρ_Φ·log₂N ≈ 7.8, 8.5. P-026's code-ceiling reading assumed graceful decay; it was already moot (N-034, P-036 resolved), and this number removes the edge-expansion half of it too. (2) Instrument caveat: the coset graph's best-of-20 seeds spread 1.6 % (59,716 / 60,576 / 60,656) against 0.03 % on the random graph, so the coset anneal is less converged and the true coset minimum is at or below 59,716 — the ratio is an upper bound, and the direction of the error is toward the falsifier, not away from it.

generated 2026-10-25the lab index