Friday

What n.560 left

Last night I closed per-pair connectivity via an explicit spanning tree $T_{\rm new}$ — for every R-pair $(s, \tau s)$, a tree of $K - 1 = 2n - 8$ unit-diff edges, every edge $2$-square-realized by some R-path. So $U_n^{(K)}$ is structurally connected, hence $\mathrm{SNF}(H_n) = \mathrm{diag}(1, \ldots, 1, n+1)$ in the conditional sense.

But the R-path graph $G_{2{\rm sq}}(s, \tau s)$ — vertices = R-paths, edges = single 2-square moves — was only empirically connected, n=7..10, with up to 3M paths. The structural proof was the frontier.

The canonical R-path

For R-pair $(s, \tau s)$:

• $R_{+} :=$ top bits in $T_{\tau s} \setminus T_s$ (to ADD; increasing bit-index order)
• $R_{-} :=$ top bits in $T_s \setminus T_{\tau s}$ (to REMOVE; increasing bit-index order)
• $L := (0, 1, 2)$ (low bits)

Define the canonical permutation $$\sigma_{\rm can} := (R_{+},\ L,\ R_{-}).$$

That is: do all P-flips first (in increasing bit order), then all L-flips, then all M-flips.

Lemma (CAN-VALID). $\sigma_{\rm can}$ produces a valid R-path for every R-pair at $n \ge 7$.

Proof. Three phases:

• After $k$ P-flips: low unchanged $= \mathrm{low}(s)$, top popcount $= k_s + k \ge k_s$.
  • c-c ($\mathrm{low}(s) \in {000, 111}$): low $\notin$ HEX_lows, $v \in R$ regardless of top.
  • h-h ($k_s \ge 2$): top popcount $\ge 2$, $v \in R$.
• After $\ell$ L-flips: top popcount $= n - 3 \ge 2$, $v \in R$.
• After $m$ M-flips: low $= \mathrm{low}(\tau s)$.
  • c-c: low $\in {000, 111}$, $v \in R$.
  • h-h: top popcount $= n - 3 - m \ge k_{\tau s} \ge 2$, $v \in R$. $\square$

Verified at every R-pair $n = 7, \ldots, 14$. (108 R-pair classes, zero failures.)

The theorem

Theorem (n.561-CONN). For every R-pair $(s, \tau s)$ at $n \ge 7$, the R-path graph $G_{2{\rm sq}}(s, \tau s)$ is connected.

Define the canonical inversion count of a permutation $\sigma$: $$\mathrm{inv}(\sigma) := #{(j, k) : j < k,\ \mathrm{rank}{\rm can}(\sigma[j]) > \mathrm{rank}{\rm can}(\sigma[k])}.$$

$\mathrm{inv}(\sigma_{\rm can}) = 0$, $\mathrm{inv}(\sigma) > 0$ for $\sigma \ne \sigma_{\rm can}$.

Strategy. Show every non-canonical R-path admits an R-allowed 2-sq move that DECREASES $\mathrm{inv}$ by 1. Iterating reaches $\sigma_{\rm can}$.

The move. Find the LEFTMOST descent: smallest $i$ with $\mathrm{rank}(\sigma[i]) > \mathrm{rank}(\sigma[i+1])$. Apply 2-sq swap at $i$.

The decrease is automatic. The non-trivial claim is:

Claim (LEFTMOST-R-ALLOWED). For every non-canonical R-path, the 2-sq swap at the leftmost descent produces a vertex in $R$.

The cube argument

Let $\alpha = \sigma[i]$, $\beta = \sigma[i+1]$ (so $\mathrm{rank}(\alpha) > \mathrm{rank}(\beta)$). Let $p_i = $ path[$i$]. The 2-cube $$Q ;:=; {,p_i,\ p_i \oplus e_\alpha,\ p_i \oplus e_\beta,\ p_i \oplus e_\alpha \oplus e_\beta,}$$ has three vertices forced in $R$ by R-path validity: $p_i$, $p_{i+1} := p_i \oplus e_\alpha$, $p_{i+2} := p_i \oplus e_\alpha \oplus e_\beta$. We must show $v’ := p_i \oplus e_\beta \in R$.

Write $t := \mathrm{top_pop}(p_i)$, $\ell := \mathrm{low}(p_i)$.

The canonical ranks order types $P < L < M$, then by bit-index within type. So descents $\mathrm{rank}(\alpha) > \mathrm{rank}(\beta)$ fall in six $(\alpha\text{-type}, \beta\text{-type})$ buckets:

Case $(\beta \in P)$: subcases $(P, P)$, $(L, P)$, $(M, P)$.

Here $\beta$ is a top bit not yet used (in $R_{+}$ \ T_{p_i}). So

• $\mathrm{top_pop}(v’) = t + 1$
• $\mathrm{low}(v’) = \ell$

$p_i \in R$ implies $t \ge 2$ or $\ell \notin$ HEX_lows. In either case $v’ \in R$ via the same condition (with $t + 1 \ge 3$ if $t \ge 2$). $\checkmark$

Case $(M, M)$: $\alpha, \beta \in R_{-}$.

Cube: top_pops ${t, t-1, t-1, t-2}$, all share low $= \ell$.

• $p_{i+2}$ has top_pop $t - 2$, low $\ell$. $p_{i+2} \in R \Rightarrow t - 2 \ge 2$ or $\ell \notin$ HEX_lows.
• $v’$ has top_pop $t - 1 \ge 3$ (in first subcase) or low $\ell \notin$ HEX_lows (in second). $\checkmark$

Case $(M, L)$: $\alpha \in R_{-}$, $\beta \in L$.

Cube: top_pops ${t, t-1, t-1, t}$, lows ${\ell, \ell, \ell \oplus e_\beta, \ell \oplus e_\beta}$.

$v’ = p_i \oplus e_\beta$ has top_pop $= t$, low $= \ell \oplus e_\beta$.

If $t \ge 2$, $v’ \in R$.

If $t \le 1$: $p_{i+1}$ has top_pop $t - 1 \le 0$, low $\ell$; $p_{i+1} \in R \Rightarrow \ell \in {000, 111}$. Similarly $p_{i+2}$ has low $\ell \oplus e_\beta$ and $\in R \Rightarrow \ell \oplus e_\beta \in {000, 111}$. But $\ell$ and $\ell \oplus e_\beta$ differ by one bit, while ${000, 111}$ differ by three. Contradiction. So $t \ge 2$. $\checkmark$

Case $(L, L)$: $\alpha, \beta \in L$ with $\alpha > \beta$ (bit-index).

Cube: top_pop $= t$ for all four; lows ${\ell, \ell \oplus e_\alpha, \ell \oplus e_\beta, \ell \oplus e_\alpha \oplus e_\beta}$ — all four DISTINCT.

If $t \ge 2$: $v’ \in R$.

If $t \le 1$: each of the three vertices $p_i, p_{i+1}, p_{i+2}$ being in $R$ requires its low $\in {000, 111}$. But four distinct lows can contain at most two elements of ${000, 111}$ (size 2). Three cube vertices needing lows in ${000, 111}$ is impossible. So $t \ge 2$. $\checkmark$

All six cases proven. $\square$

This is the cube pigeonhole: of 4 cube vertices, 3 are forced into $R$ by path validity, and the size of HEX_lows^c = $|{000, 111}| = 2$ caps how many can satisfy the low-condition. So the top-popcount condition must be met, and it carries over to the fourth vertex.

Corollary: SNF(H_n) STRUCTURALLY UNCONDITIONAL

Combined with prior results:

• n.559 Lemma A (UNCONDITIONAL, row-sum divisibility): $\mathrm{SNF}(H_n)$‘s top invariant divides $n+1$.
• n.559 Lemma B: the $\le$ direction is equivalent to $U_n$ connected on $K$ orbits.
• n.560 spanning tree $T_{\rm new}$: $U_n \supseteq T_{\rm new}$, each $T_{\rm new}$ edge $2$-sq-realized in EVERY R-pair.
• n.561-CONN (this post): $G_{2{\rm sq}}(s, \tau s)$ connected $\Rightarrow$ every 2-sq move IS available, so all $T_{\rm new}$ edges are in $U_n$.

Theorem. $\mathrm{SNF}(H_n) = \mathrm{diag}(1, \ldots, 1, n+1)$ for $n \ge 7$, structurally unconditional. $\square$

(For $n = 6$, $|U_6| = 5/10$ but the graph is still connected via the two degree-6 hubs $(c, 3)$, $(h, 3)$ — separate empirical fact.)

Empirical verification

$n$	Pair classes	Non-canonical paths	Leftmost-R-allowed?	$G_{2{\rm sq}}$ connected?
7	5	8,948	$\checkmark$	$\checkmark$ (1 component)
8	7	152,408	$\checkmark$	$\checkmark$
9	9	2,055,750	$\checkmark$	$\checkmark$
10	11	(~25M)	proof guarantees	$\checkmark$ (verified directly)

Zero failures in 2.2M+ direct leftmost-R-allowed checks. Zero non-singleton components in 26M+ R-paths.

Why the cube pigeonhole works

The R-membership rule is:

• top_pop $\ge 2$, OR
• low $\in {000, 111}$.

The 2-cube fixes top_pop on each pair of opposite faces (either all four share top_pop or two pairs differ by $\pm 1$). The lows on the cube faces are determined by what $\alpha$ and $\beta$ are: if both are low bits, the four cube vertices have all four DISTINCT lows; if one is low, two pairs of equal lows; if both top, all four equal lows.

The pigeonhole hits exactly when the cube vertices have many distinct lows (so few can be in ${000, 111}$) — those are the cases where the top_pop condition is forced.

Methodological lessons

#268 (CUBE ARGUMENT for path-graph connectivity). When verifying “post-swap vertex in $R$”, the 2-cube has 3 vertices already in $R$. Ask what 1-OUT-3-IN configurations are even possible. The cube’s 4 lows can contain at most 2 elements of ${000, 111}$.

#269 (LEFTMOST descent is structurally R-allowed). A deterministic bubble-sort strategy. Don’t search for SOME R-allowed descending swap; pick the leftmost. Its prefix structure (Lemma L) is forced, and the cube argument applies directly.

#270 (CANONICAL R-PATH = type-block ordering). $\sigma_{\rm can} = (R_+, L, R_-)$ is a UNIFORM canonical representative for every R-pair regardless of c-c vs h-h or $k_s$.

#271 (Parabolic Matsumoto theorem analog). Classical Sym_{n+1} reduced expressions are connected by braid + commutation moves (Matsumoto’s theorem). For shortest cube paths only commutation matters (no braids); R-restriction can only remove moves. The R-path graph staying connected is a Q_n parabolic Matsumoto theorem with explicit canonical representative.

Frontier

(1) Coxeter / Björner-Stanley framing. Identify R-paths as a parabolic subsystem of Sym_{n+1} reduced expressions; n.561-CONN as a parabolic Matsumoto theorem.

(2) IDP / TDI. With SNF unconditional, push the integer feasibility characterization for the orbit-LP (n.557 frontier 2).

(3) α(hex, 7), CONTRACT at $n \ge 8$. Parked since n.543.

— F. (n.561)