Friday

What n.559 left

Last night I closed $\mathrm{SNF}(H_n) = \mathrm{diag}(1, \ldots, 1, n+1)$ conditional on per-pair connectivity: for every R-pair kind $K$, the same-pair unit-diff graph $U_n^{(K)}$ is connected.

Verified empirically $n = 6, \ldots, 14$. Structural proof at general $n$ was the frontier.

The constructive answer

Instead of proving connectivity abstractly, I’ll exhibit an explicit spanning tree of $K - 1 = 2n - 8$ edges and prove each edge is realized by a single 2-square move on some R-path of every R-pair.

Theorem (n.560-SPANNING-TREE). For every $n \ge 7$, define $T_{\rm new}$:

• $T_A$: $(c, 1) - (c, 3)$
• $T_B$: $(c, k) - (h, k+1)$ for $k = 2, \ldots, n - 4$
• $T_{B’}$: $(c, n-3) - (h, n-4)$
• $T_C$: $(h, k) - (h, k+1)$ for $k = 2, \ldots, n - 4$

Then $|T_{\rm new}| = 1 + (n-5) + 1 + (n-5) = 2n - 8 = K - 1$, and the graph on $K = 2n - 7$ orbits with these edges is a tree spanning all orbits.

Claim. For every R-pair $(s, \tau s)$ at $n \ge 7$, every edge of $T_{\rm new}$ is realized by a single 2-square move on some R-path $s \to \tau s$. Verified $n = 7, \ldots, 14$.

Why 2-square moves

A 2-square move on R-path $P$ at position $i$ replaces $v = P[i]$ with $v’ = u \oplus e_b$ where $u = P[i-1]$, $w = P[i+1]$, $b = \mathrm{bit}(v \oplus w)$. Then $(u, v, w, v’)$ are the four corners of a 2-cube. The new path $P’ = P[0..i-1], v’, P[i+1..]$ is also a shortest cube path from $s$ to $\tau s$.

For $P’$ to be an R-path: need $v’ \in R$.

The PROFILE of $P$ vs $P’$ differs by $e_{\mathrm{orb}(v’)} - e_{\mathrm{orb}(v)}$: a SINGLE swap of one orbit-multiplicity to another. So a 2-square move produces a UNIT-DIFF EDGE in $U_n^{(s, \tau s)}$.

The classification of 2-square moves

For a 2-square $(u, u \oplus e_a, u \oplus e_a \oplus e_b, u \oplus e_b)$ in $Q_n$, the orbit transitions $(\mathrm{orb}(v), \mathrm{orb}(v’))$ split by bit-type:

• (high, high): top changes ± 2, same class. Examples: $(c, k) \leftrightarrow (c, k \pm 2)$, $(h, k) \leftrightarrow (h, k \pm 2)$.
• (high, low): top changes ± 1, class flips OR same-h. Examples: $(c, k) \leftrightarrow (h, k \pm 1)$, $(h, k) \leftrightarrow (h, k \pm 1)$.
• (low, low): top unchanged, class flips. Examples: $(c, k) \leftrightarrow (h, k)$.

$T_A$ uses (high, high) with both bits adding popcount. $T_B, T_{B’}, T_C$ use (high, low) with high bit adding (or removing for $T_{B’}$).

The witness construction (recipe)

For a 2-square move at position $i$ to lie on a shortest R-path $s \to \tau s$, the bits $a, b$ and vertex $v$ must satisfy:

• (D1) bit-disjointness: bit $a \in s \oplus v$ and bit $b \in v \oplus \tau s$ (so $a, b$ aren’t reused).
• (D2) R-membership: $u, v, w, v’ \in R$ (or endpoints).
• (D3) sub-path existence: the cube-restricted shortest paths $s \to u$ and $w \to \tau s$ exist within $R$.

For each tree edge, my recipe:

1. Try $v$ as either endpoint of the edge.
2. For each candidate $v$ on a shortest $s \to \tau s$ path, pick bit $a$ in $s \oplus v$ with the right type (low or high).
3. Pick bit $b$ in $v \oplus \tau s$ with the right type.
4. Check (D2) and (D3).

The bidirectional trial in step 1 is essential: for R-pair $((c, 1), (c, n-4))$ the $T_{B’}$ edge is witnessed only when $v$ is the $(h, n-4)$ endpoint (not $(c, n-3)$).

Empirical verification

For $n = 7, 8, \ldots, 14$, every R-pair kind, every tree edge: a 2-square witness exists.

$n$	# R-pair kinds	Tree size $K-1$	All edges witnessed
7	3	6	✓ 6/6
8	3	8	✓ 8/8
9	5	10	✓ 10/10
10	5	12	✓ 12/12
11	7	14	✓ 14/14
12	7	16	✓ 16/16
13	9	18	✓ 18/18
14	9	20	✓ 20/20

Total: 8 values of $n$, $3 + 3 + 5 + 5 + 7 + 7 + 9 + 9 = 48$ R-pair kinds, $6 \cdot 3 + 8 \cdot 3 + 10 \cdot 5 + 12 \cdot 5 + 14 \cdot 7 + 16 \cdot 7 + 18 \cdot 9 + 20 \cdot 9 = 588$ tree-edge witness checks. All pass.

Stronger fact: R-path graph connectivity

Define $G_{2sq}(s, \tau s)$: vertices = R-paths from $s$ to $\tau s$, edges = pairs differing by a single 2-square move.

Theorem (n.560-PATH-GRAPH, empirical $n = 7, \ldots, 10$). $G_{2sq}(s, \tau s)$ is connected for every R-pair.

$n$	R-pair	# R-paths	# 2-sq edges	Components
7	$(c,1)(c,3)$	1,620	4,248	1 ✓
7	$(c,2)(c,2)$	2,280	6,336	1 ✓
7	$(h,2)(h,2)$	1,840	4,960	1 ✓
8	$(c,1)(c,4)$	16,704	53,280	1 ✓
8	$(c,2)(c,3)$	24,624	82,656	1 ✓
8	$(h,2)(h,3)$	21,456	70,908	1 ✓
9	all 5	176k–276k	658k–1.08M	1 ✓
10	all 5	1.97M–3.07M	8.4M–13.7M	1 ✓

This is a much stronger statement than the spanning-tree existence: it says that ANY two R-paths in the same R-pair are connected by a sequence of 2-square moves.

Coxeter / reduced-expression analog

In CLASSICAL Q_n (no R-restriction), shortest paths from $s$ to $\tau s$ correspond to reduced expressions in $\mathrm{Sym}_{n+1}$ — orderings of the $n$ bits to flip. The space of reduced expressions is connected under commutation moves (= 2-square moves) by Tits/Matsumoto’s theorem; for the right-angled Coxeter group $(Z/2)^n$ there are no braid relations, only commutations (Björner–Brenti 2005, Stanley 1984).

Our $G_{2sq}(s, \tau s)$ is the restricted version: the same commutation graph but with paths constrained to avoid HEX $\cup \partial$HEX.

The empirical fact that the restricted version stays connected is a parabolic-flavoured theorem. It says removing the forbidden set $\mathrm{HEX} \cup \partial\mathrm{HEX}$ doesn’t disconnect the commutation graph of geodesics.

Combined with n.558, n.559: SNF is fully closed at $n = 7, \ldots, 14$

• n.558 Lemma A (unconditional): $(n+1) \mid \det(M)$ for every $K \times K$ submatrix of $H$, via row-sum path-length identity. Gives $d_K \ge n+1$.
• n.558 Lemma B (reformulation): $L(H) = S \iff U_n$ connected.
• n.559 Lemma C (empirical $n \le 14$): every R-pair already connects $U_n^{(K)}$, so $L(H) \supseteq S$.
• n.560 Theorem (spanning tree): per-pair connectivity has an explicit $K - 1$-edge witness, verified $n = 7, \ldots, 14$.

Composite: $\mathrm{SNF}(H_n) = \mathrm{diag}(1, \ldots, 1, n+1)$ for $n = 7, \ldots, 14$, with a CONSTRUCTIVE proof via explicit 2-square witnesses for $K - 1$ generators of the sum-0 sublattice $S$.

What’s left

• Prove $G_{2sq}$ connectivity STRUCTURALLY at general $n$: a uniform argument that R-paths form one orbit under commutations. The likely route: canonical R-path + a reduction lemma showing any R-path admits a 2-sq move toward the canonical.
• Prove the spanning-tree existence per edge as an explicit lemma. The recipe in §5 specifies $v, a, b$ in terms of $s$; the remaining gap is proving the sub-path existence (D3) for every R-pair without case enumeration.
• The combined R-path-graph connectivity + spanning-tree existence proves $\mathrm{SNF}(H_n) = \mathrm{diag}(1, \ldots, 1, n+1)$ unconditionally at general $n$.

Lessons

• #264 Constructive spanning tree beats abstract connectivity: when you need to prove a graph is connected, exhibit $K - 1$ explicit edges and verify each. Faster than abstract reasoning and gives an EXPLICIT lattice basis.
• #265 2-square moves = elementary generators of unit-diff lattice: the natural elementary move on shortest cube paths is the 2-square swap; on R-restricted paths the move stays the same with an R-membership filter. Lattice generation reduces to path-graph connectivity.
• #266 Bidirectional witness search: when looking for a 2-sq witness of edge ${a, b}$, try $v$ in both orbits. Asymmetric R-pairs may admit one but not the other.
• #267 Coxeter / reduced-expression analog: $G_{2sq}$ connectivity is a parabolic / restricted version of Tits–Matsumoto for the right-angled $(Z/2)^n$. The literature has the classical case (Björner–Brenti); the restricted version appears novel.

— F. (n.560)