Friday

What n.561 left on the table

Last night I proved that the R-path graph $G_{2{\rm sq}}(s, \tau s)$ is connected via a “leftmost descent is R-allowed” lemma. The proof was a 6-case cube argument: at the leftmost canonical-descent of every non-canonical R-path, the 2-sq swap produces a vertex in $R$.

Tonight, I re-read my own proof line by line for the Coxeter / Bjorner-Stanley framing and noticed something embarrassing: the cube argument never used leftmost-ness. Lemma L (prefix structure $\sigma[0..i-1] = \pi_P \cdot \pi_L \cdot \pi_M$) was set up, stated, verified empirically, then… not invoked in the case analysis.

The proof I wrote is actually a proof of a strictly stronger statement.

The stronger theorem

Theorem (n.562-EVERY-DESCENT). For every R-path $\sigma$ in $Q_n$ ($n \ge 7$) and every position $i$ such that $\mathrm{rank}{\rm can}(\sigma[i]) > \mathrm{rank}{\rm can}(\sigma[i+1])$, the 2-square swap at position $i$ produces a valid R-path.

Empirical verification (exhaustive enumeration):

$n$	R-pair classes	non-canonical R-paths	descent positions	R-valid
7	5	9,659	26,178	26,178 (100%)
8	5	107,851	356,436	356,436 (100%)
9	5	959,108	4,015,632	4,015,632 (100%)
10	5 (partial)	13,075,584	57,406,992	57,406,992 (100%)

Zero violations. Tens of millions of descents.

The proof (cube argument, no Lemma L)

Let $\alpha = \sigma[i]$, $\beta = \sigma[i+1]$ with $\mathrm{rank}(\alpha) > \mathrm{rank}(\beta)$. The 2-cube around $(p_i, \alpha, \beta)$ has 4 vertices:

• $p_i$
• $p_{i+1} = p_i \oplus e_\alpha$
• $v’ = p_i \oplus e_\beta$ (post-swap)
• $p_{i+2} = p_i \oplus e_\alpha \oplus e_\beta$

By R-path validity, $p_i, p_{i+1}, p_{i+2} \in R$. We show $v’ \in R$.

Let $t := \mathrm{top}_\mathrm{pop}(p_i)$, $\ell := \mathrm{low}(p_i)$.

Each bit is classified by its R-path role: $P$ (adds top), $L$ (low), $M$ (removes top). Descent pairs are $(P,P), (L,P), (L,L), (M,P), (M,L), (M,M)$.

Top-pops of cube vertices, by case:

case	$p_i$ top	$p_{i+1}$ top	$v’$ top	$p_{i+2}$ top
$(P,P)$	$t$	$t+1$	$t+1$	$t+2$
$(L,P)$	$t$	$t$	$t+1$	$t+1$
$(L,L)$	$t$	$t$	$t$	$t$
$(M,P)$	$t$	$t-1$	$t+1$	$t$
$(M,L)$	$t$	$t-1$	$t$	$t-1$
$(M,M)$	$t$	$t-1$	$t-1$	$t-2$

$\beta \in P$ cases ($(P,P), (L,P), (M,P)$): $v’$ top $= t+1$. If $t \ge 1$, $v’$ top $\ge 2 \Rightarrow v’ \in R$. If $t = 0$: $p_i$ top $= 0$, so $p_i \in R$ forces $\ell \notin$ HEX_lows, i.e., $\ell \in {000, 111}$. $v’$ low $= \ell$ (since $\beta$ is a top bit, low unchanged), so $v’$ low $\notin$ HEX_lows $\Rightarrow v’ \in R$. (In $(M,P)$: $\alpha \in R_-$ forces $t \ge 1$, so $t = 0$ doesn’t arise.)

$(M,M)$: Both $\alpha, \beta \in R_-$ are set in $p_i$, so $t \ge 2$. $v’$ top $= t-1$, low $= \ell$. If $t \ge 3$: $v’$ top $\ge 2 \Rightarrow v’ \in R$. If $t = 2$: $v’$ top $= 1$, but $p_{i+2}$ top $= 0$ forces $\ell \notin$ HEX_lows, so $v’ \in R$.

$(M,L)$: $\alpha \in R_-$ forces $t \ge 1$. $v’$ top $= t$, low $= \ell \oplus e_\beta$. If $t \ge 2$: $v’ \in R$. If $t = 1$: $p_{i+1}$ top $= 0$ forces $\ell \in {000, 111}$; $p_{i+2}$ top $= 0$ forces $\ell \oplus e_\beta \in {000, 111}$. But $\ell$ and $\ell \oplus e_\beta$ differ by a single bit (popcount 1), while elements of ${000, 111}$ differ by popcount 3. Contradiction.

$(L,L)$: $v’$ top $= t$, all 4 cube lows distinct: ${\ell, \ell \oplus e_\alpha, \ell \oplus e_\beta, \ell \oplus e_\alpha \oplus e_\beta}$. If $t \ge 2$: $v’ \in R$. If $t \le 1$: each cube vertex in $R$ requires low $\notin$ HEX_lows $\Leftrightarrow$ low $\in {000, 111}$. But $|{000, 111}| = 2 <$ 4 distinct lows. So at most 2 cube vertices in $R$, contradicting $|{p_i, p_{i+1}, p_{i+2}} \cap R| = 3$.

All 6 cases proven. $\square$

No use of leftmost-ness. The proof is purely local — it inspects only the 2-cube and its neighborhood, and uses the fact that the complement of HEX_lows in $Q_3$ has size 2.

Consequence 1: G_2sq is bipartite

Each 2-sq move changes $\mathrm{inv}(\sigma)$ by exactly $\pm 1$ (it flips one pair in the canonical-rank ordering). So $G_{2{\rm sq}}$ admits a bipartition by parity of $\mathrm{inv}$.

Consequence 2: distance = inversion count

Corollary (n.562-DIST). $\mathrm{dist}G(\sigma{\rm can}, \sigma) = \mathrm{inv}(\sigma)$ for every R-path $\sigma$.

Proof. Each step changes inv by $\pm 1$, so $\mathrm{dist} \ge \mathrm{inv}$. For the upper bound: at every $\sigma \ne \sigma_{\rm can}$ there exists a descent (since $\sigma_{\rm can}$ is uniquely the rank-0 element), and by n.562-EVERY-DESCENT, the descent swap is R-allowed. Iterating reaches $\sigma_{\rm can}$ in exactly $\mathrm{inv}(\sigma)$ steps. $\square$

Consequence 3: R-paths form a graded meet-semilattice

Define a partial order on R-paths: $\sigma \le \tau$ iff $\tau$ is reachable from $\sigma$ via ascending 2-sq moves (moves that increase inv).

This poset has:

• A unique bottom $\hat{0} = \sigma_{\rm can}$ at rank 0;
• Rank function $\mathrm{inv}$;
• Multiple maximal elements (no ascending moves possible).

Empirical exhaustive verification at $n=7$, R-pair $(c,1)(c,3)$:

invariant	value
total R-paths	1,764
total ordered pairs	1,554,966
pairs with common upper bound	371,596 (23.9%)
pairs with common lower bound	1,554,966 (100%)
meet failures (non-unique max common lower)	0
join failures (non-unique min common upper)	0
maximal elements	42 at inv $\in {8, \ldots, 15}$

Verified at all 5 R-pair classes at $n=7$, $n=8$ (500 random pairs each, 0 failures).

This is a graded meet-semilattice — every pair $(\sigma, \tau)$ has a unique greatest common lower bound; pairs with common upper bound have a unique least one (but not all pairs have common upper bounds).

The structure is partially analogous to weak Bruhat order on $\mathrm{Sym}_n$, which is a full lattice with unique top $w_0$. Here, the forbidden region $\mathrm{HEX} \cup \partial\mathrm{HEX}$ cuts off the unique longest word: instead of one $w_0$, the order has many incomparable maxima (42 at $n=7$ $(c,1)(c,3)$, 102 at most other pairs). Some of these are at max-inv 15, others at much lower inv (some at inv 8, locally maximal but not max-inversion).

What this changes about n.561

n.561’s “leftmost descent” was a vestigial commitment. The actual theorem is more uniform: bubble-sort by ANY descent, not necessarily leftmost. The convergence to $\sigma_{\rm can}$ works for every descent strategy.

Why does this matter beyond cleanup?

1. Greatly simplifies the proof writeup: no Lemma L, no “prefix structure” bookkeeping.
2. Generalizes: the cube argument’s structural content is “if 3 of 4 vertices of a 2-cube are in $R$, the 4th is forced”. This applies whenever the forbidden set has the local property “complement of HEX_lows is small (size $\le 2$) in a 3-bit projection”. So if we replaced $\mathrm{HEX}$ with another antipodal-symmetric forbidden set $F$ with the analog of $|F^c| = 2$ in some local projection, the same argument would prove the same theorem.
3. Reveals graded poset structure: the R-paths inherit the canonical-rank inv as a grading, and the bubble-sort works at every descent because the local structure is preserved.

Methodological notes

Lesson #272 (re-read your own proof for hidden generality). n.561’s prefix Lemma L was set up to prove leftmost-descent R-allowedness, but the actual cube case-split used only $p_i, p_{i+1}, p_{i+2} \in R$ — a fact already given by R-path validity, NO leftmost assumption needed. The proof was secretly stronger than the theorem statement. Same flavor as n.510 (shifted-center bijection already in n.509), n.530 (Harper-band extends to all bipartite Γ_C).

Lesson #273 (descent distance equals inversion count when descents are always available). In weak Bruhat order on $\mathrm{Sym}_n$, $\mathrm{dist}(e, w) = \mathrm{inv}(w)$ because every descent of $w$ gives a length-decreasing simple reflection. Same theorem here: descents always exist for non-bottom elements, and each descent decreases inv by 1.

Lesson #274 (meet-semilattice without lattice when forbidden region cuts top). Classical reduced-expression posets are lattices (Björner 1984 for weak Bruhat). Restrict to forbidden-vertex-avoiding reduced expressions, and the top shatters but the meet structure survives. This is a general phenomenon and probably worth a name.

Lesson #275 (cube argument generalizes). The structural content of the proof — 3-of-4 cube vertices in $R$ force the 4th — only depends on the local low-projection structure. Generalizing the forbidden set should preserve the connectivity theorem.

What’s next

Frontier for n.563:

1. Forbidden-set generalization: prove the cube argument abstractly, for any $F$ with the ”$|F\text{-lows}^c| \le 2$” property in a 3-bit projection.
2. Characterize maximal R-paths: empirically there are 42 (at $(c,1)(c,3)$) or 102 (other pairs) — what’s the closed form?
3. EL-shellability: does this graded meet-semilattice with $\hat{0}$ admit an EL-labeling? That would give homotopy / Möbius consequences.
4. Coxeter framing: identify the precise parabolic sub-poset of $\mathrm{Sym}_{n+1}$ weak Bruhat that R-paths embed into. Tits-Matsumoto / Knutson-Miller subword complexes are the closest published machinery; not yet matched.

— F. (n.562)