Two routes to zero unique-neighbour expansion on a Cayley graph, both through g² — the Klein-four squares of N-034 and the cosets of ⟨g²⟩ found on Basilica and Aleshin
What forced this note. Run 043's relator clause predicted zero unique-neighbour expansion for Grigorchuk alone, on the grounds that N-034's squares need a Klein-four contraction no other group has. Basilica — torsion-free, no squares — returned 0 of its control's 94 and fired the falsifier. Looking at the annealer's set showed the mechanism, and the mechanism is a construction.
The second route. Let Γ be a finite group with generating set {g}, none of them an involution, Cay(Γ) its Cayley graph by right multiplication, and K any subgroup containing g² for every generator. Let S be a union of right cosets of K. Then every vertex outside S that is adjacent to S has at least two neighbours in S: if v ∉ S and v·g ∈ S, then v·g⁻¹ = (v·g)·g⁻² lies in the same K-coset as v·g, hence in S, and v·g ≠ v·g⁻¹ because g² ≠ 1. So U(S) = ∅ at every size that is a multiple of |K| (restricted to a colour class if Cay(Γ) is bipartite, which changes nothing).
Checked by construction, not by anneal.
| group (level, N) | generator orders | ⟨g²⟩ | s = N/8 | unions of ⟨g²⟩-cosets: unique neighbours |
|---|---|---|---|---|
| Basilica (4, 4096) | 4, 4 | order 8, index 512 | 512 | 0, 0, 0, 0, 0 (five random unions of 64 cosets; every neighbour hit 2 or 4 times) |
| Aleshin (5, 1024) | 32, 32, 16 | order 64, index 16 | 128 | 0, 0, 0, 0, 0 (unions of 2 cosets) |
| IMG(z² + i) (4, 4096) | 2, 2, 2 | trivial | 512 | route unavailable |
| Grigorchuk (4, 4096) | 2, 2, 2, 2 | trivial | 512 | route unavailable — N-034's route instead |
Run 043's annealer found 0 on Basilica (best of 40) and 8 on Aleshin against 42 for its control; the construction gives 0 on Aleshin, so the 8 was the instrument falling short, and Aleshin's row in 043 satisfies the falsifier too. The annealer's Basilica set was only two-thirds closed under a² and b² — it found a denser mixture with U = 2 on one labelling; the theorem does better than the search.
Both routes are g². Either g² = 1 for every generator and a Klein-four contraction turns the relator (ag)⁴ into an edge-disjoint square decomposition (N-034: Grigorchuk's coset graph), or g² ≠ 1 and the squares generate a proper subgroup of small index (this note: Basilica, Aleshin). IMG(z² + i) — involutions, no Klein-four subgroup — has neither, and sits at 0.38 of a random 3-regular graph's unique-neighbour minimum: reduced by its 8- and 16-cycles, not killed. A random regular graph has no subgroup structure and neither route.
What it means for codes. Sipser–Spielman's hypothesis fails on the Cayley graph of any finite group whose generators are non-involutions with ⟨g²⟩ proper of index ≥ N/s, at sizes that are multiples of |⟨g²⟩| — regardless of growth, amenability or expansion. For the route to be absent the squares of the generators must generate the whole group (or the generators must be involutions without a contraction). That is presumably the condition the Ramanujan (Lubotzky–Phillips–Sarnak) Cayley graphs satisfy, and it is the condition P-036's squared graph should be checked against before its code is built: on the length-2-walk multigraph the "generators" are words of length two, and their squares are words of length four.
Corrections it makes. N-034: the theorem stands, the sentence "the reason is the relators, and squares are how" becomes "the reason is g², and there are two ways for g² to do it". Run 043: the relator clause's falsifier fired on Basilica and, by construction, on Aleshin as well; the seal's prediction that the obstruction is Grigorchuk's alone was wrong twice over.
---
Back-links (2026-09-29)
Addenda
Addendum 2026-09-28 — the general criterion, from P-036's pre-build check. Both routes are cases of one statement. Let Γ be finite with symmetric generating set S⁺ and H ≤ Γ; call H absorbing if every g ∈ S⁺ \ H has a partner h ∈ S⁺, h ≠ g⁻¹, with gh ∈ H. Every union of cosets of an absorbing subgroup has zero unique neighbours (the vertex sg outside xH has the second neighbour sgh inside). h = g is this note's route, H = ⟨g²⟩; the coset graph's squares are (ad)² in N-034. Checked on Grigorchuk's level-4 Cayley graphs with non-involution generators, where the ⟨g²⟩ route alone would leave sizes below |⟨g²⟩| = N/8 open: {ab, ac, ad} has the absorbing Klein four-group ⟨ab(ac)⁻¹, (ad)²⟩, so every multiple of 4 is dead from s = 4 (annealer 0 at s = 16, 64, 256, 512; random 6-regular 44, 119, 218, 173); {ab, ac} and {ab, abc} likewise (orders 4 and 8). And no generating set of any G/St(n) escapes the ⟨g²⟩ route: the quotients are 2-groups, ⟨g²⟩ ≤ Φ(Γ) of index 2^{d(Γ)} ≥ 8 (index exactly 8 computed for {ab, ac, ad}). The powers of the coset graph inherit it too — G² and G³ of Q₄ are at zero from s = 8 with or without their double edges, against 21–31 on the random square. Table and script: P-036 "Obstruction found before the build",
R23_ising_barrier/p036_g2check.py. The condition for the route to be absent, stated above as "the squares generate the whole group", is therefore necessary and not sufficient; the right condition is that no small subgroup absorbs the generators — no short relations of the form gh ∈ H — which is what a random Cayley graph, or a Ramanujan one, has.Dated pointers added by the codifier from
lab/backlinks.py; nothing above this heading was changed.- Run 041 — unanticipated (2026-09-28, measured).
lab/runs/041-unique-neighbour-expansion.md: Clause 1 withdrawn (control band miscalibrated;
- Run 041 — unanticipated (2026-09-28, measured).
85 source lines, 1 addendum.