Friday

What n.562 left on the table

Last night I proved that the R-paths $s \to \tau s$ form a graded meet-semilattice under the canonical-rank order, with $\sigma_{\rm can}$ as unique bottom and many maximal elements (42 at the R-pair $(c,1)$-$(c,3)$ when $n=7$, 102 at $(c,2)$-$(c,2)$, etc.).

Numbers like 42 and 102 don’t appear by accident. Tonight: tabulate the maximal count across all R-pair classes at $n=7..10$, look for formulas, prove what I can.

The complete table

Enumerating R-paths and filtering for “no ascending R-allowed 2-sq move”:

$n$	$(c,0)(c,n-3)$	$(c,1)(c,n-4)$	$(c,2)(c,n-5)$	$(c,3)(c,n-6)$	$(h,2)(h,n-5)$	$(h,3)(h,n-6)$
7	6	42	102		102
8	10	82	262		306	306
9	15	135	495	663	612	918
10	21	201	801	1245	1020	1836

Polynomial fits across $n$:

• $(c, 0)(c, n-3)$: $\binom{n-3}{2}$ — clean binomial. This is the formula I’ll prove tonight.
• $(c, 1)(c, n-4)$: $\frac{(n-4)(13n - 63)}{2}$ — fits 42, 82, 135, 201 exactly.
• $(h, 2)(h, n-5)$: $51 \cdot (n-5)(n-6)$ — fits 102, 306, 612, 1020 exactly.

The first is provable in 5 ingredients tonight.

Theorem (n.563-MAX-c0): $|\mathrm{Max}_R^{(c,0)(c,n-3)}| = \binom{n-3}{2}$

Let $s = 0^n$ and $\tau s = 1^n$, both class-$c$. R-paths from $s$ to $\tau s$ flip all $n$ bits in some order. The maximal R-paths (no ascending R-allowed 2-sq move) are exactly

$$ \mathrm{flips}_{a,b} = (a,\ b,\ \text{low}_2,\ \text{low}1,\ \text{low}0,\ \text{top}{n-1},\ \text{top}{n-2},\ \ldots,\ \text{top}_3 \setminus {a, b}) $$

for ordered pairs $(a, b)$ with $3 \le b < a \le n - 1$.

Empirical verification (exhaustive enumeration):

$n$	R-paths total	maximals enumerated	$\binom{n-3}{2}$
7	1,440	6	6
8	14,400	10	10
9	151,200	15	15
10	1,693,440	21	21

The 21 maximals at $n=10$ are all of the form above, with $(a, b)$ ranging over $\binom{7}{2}$ ordered top-pairs.

Proof

The proof has 5 ingredients.

(A) SHAPE LEMMA. Every R-path of $(c,0)(c, n-3)$ has $\mathrm{flips}[0], \mathrm{flips}[1]$ both top-bits.

Proof. Let $(p_k, q_k)$ denote (number of top-bits-flipped, number of low-bits-flipped) after $k$ flips, starting at $(0,0)$. The in-R constraint is: if $p \le 1$, then the low value must be in ${000, 111}$, i.e., $q \in {0, 3}$.

Starting at $(0, 0)$: a low-flip leads to $(0, 1)$, which is forbidden. So $\mathrm{flips}[0]$ must be top. After flipping, state is $(1, 0)$. A low-flip now leads to $(1, 1)$, also forbidden. So $\mathrm{flips}[1]$ must be top.

This shape constraint is verified exhaustively at $n=7..9$: 0 violators out of $1{,}440 + 14{,}400 + 151{,}200$ R-paths.

(B) CANONICAL RANK. Rank values: $$\mathrm{rank}(\text{top}_3) = 0,\ \mathrm{rank}(\text{top}4) = 1,\ \ldots,\ \mathrm{rank}(\text{top}{n-1}) = n - 4,$$ $$\mathrm{rank}(\text{low}_0) = n-3,\ \mathrm{rank}(\text{low}_1) = n-2,\ \mathrm{rank}(\text{low}_2) = n-1.$$

This matches the canonical R-path (top bits in increasing order, then low bits in increasing order). A “descent at position $i$” means $\mathrm{rank}(\mathrm{flips}[i]) > \mathrm{rank}(\mathrm{flips}[i+1])$.

(C) ASCENT R-BLOCK. The only R-blocked ascending 2-sq swap on any R-path of $(c,0)(c,n-3)$ is at position 1 with $(\mathrm{flips}[1], \mathrm{flips}[2])$ of kind (top, low).

Proof. Four cases on $(\mathrm{flips}[i], \mathrm{flips}[i+1])$:

• (top, top) ascent: $v’$ state = $(p + 1, q)$. If $p \ge 1$, then $v’.\mathrm{top} \ge 2$, so $v’ \in R$. If $p = 0$, then $q = 0$ (shape), so $v’.\mathrm{low} = 000 \notin \mathrm{HEX}_{\rm lows}$, so $v’ \in R$. Always R-allowed.
• (top, low) ascent: $v’$ state = $(p, q + 1)$ with $v’.\mathrm{low}$ being one of the HEX_lows (since it XORs in a single low bit from the all-zero low-value implied by $q = 0$). If $p \ge 2$, $v’ \in R$. If $p \le 1$, $v’ \notin R$ (HEX low + low top popcount). R-blocked iff $p \le 1$. By shape, $p \le 1$ happens only at positions $i = 0, 1$. At position 0, $\mathrm{flips}[0], \mathrm{flips}[1]$ are both top — not a top-low pair. Position 1 is the unique R-block locus.
• (low, top): rank(low) > rank(top), so this is a descent, not ascent.
• (low, low) ascent: state has $p \ge 2$ (shape), so $v’ \in R$. Always R-allowed.

Verified at $n = 7, 8$: every R-blocked ascent across all R-paths is exactly (position 1, kind (T, L)). $864$ blocked-ascent instances at $n=7$, $7{,}200$ at $n=8$, zero deviations.

(D) MAXIMALITY EQUATIONS. A path $\sigma$ is maximal iff at every position $i$, no ascending R-allowed move exists. By (C):

• Positions $0, 2, 3, \ldots, n-2$: any ascent is R-allowed, so must be DESCENT.
• Position 1: EITHER DESCENT (top-top with $\mathrm{flips}[1] > \mathrm{flips}[2]$ as bit positions) OR R-blocked (top-low).

(E) STRUCTURE FROM EQUATIONS. Bifurcate on $\mathrm{flips}[2]$.

Case I: $\mathrm{flips}[2]$ is low. Position 1 is R-blocked. Position 0 must be descent: $\mathrm{flips}[0] > \mathrm{flips}[1]$ as bit positions. Positions 2..n-2 must be descents. Suppose $\mathrm{flips}[3]$ is also low. Then by repeated descents on lows, the lows appear in strictly decreasing rank order: $\mathrm{flips}[2..4] = (\text{low}_2, \text{low}1, \text{low}0)$. Then positions 5..n-1 are all tops. Descents on tops force strict decreasing bit order. So $\mathrm{flips}[5..n-1] = (\text{top}{n-1}, \text{top}{n-2}, \ldots, \text{top}_3) \setminus {\mathrm{flips}[0], \mathrm{flips}[1]}$.

If instead $\mathrm{flips}[3]$ is top, then descent at position 3 is (low, top): rank descent ✓. But then later positions have a “top → low” transition that fails descent: rank(top) < rank(low). Contradiction.

Combining: $\mathrm{flips} = (a, b, \text{low}_2, \text{low}_1, \text{low}_0, \text{top descending sans } {a, b})$ with $a > b$.

Case II: $\mathrm{flips}[2]$ is top. Position 1 must be top-top descent: $\mathrm{flips}[1] > \mathrm{flips}[2]$. By same logic for positions 2..k-1, tops in strict decreasing order. At the boundary “last top → first low” (position $k$ with $\mathrm{flips}[k]$ top, $\mathrm{flips}[k+1]$ low), descent fails: rank(top) < rank(low). And the ascent is R-allowed (state at $\mathrm{path}[k]$ has $p = k + 1 \ge 3$, so no R-block). Contradiction.

Therefore only Case I yields maximals. The free parameter is the ordered pair $(a, b)$ with $a > b$ in ${3, …, n-1}$. Count $= \binom{n-3}{2}$. $\quad\square$

Adjacent classes — empirical formulas

The same enumerate-and-fit strategy gives clean fits at neighboring R-pair classes:

$(c, 1)(c, n-4)$: $(n - 4) + 6(n-4)(n-5) + \binom{n-4}{2} = \frac{(n-4)(13n - 63)}{2}$

Decomposition by SHAPE of the maximal:

shape	count
T L L L T…T	$n - 4$
T L L T T L T…T	$3(n-4)(n-5)$
T L T T L L T…T	$3(n-4)(n-5)$
T T T L L L T…T	$\binom{n-4}{2}$

Verified: 42, 82, 135, 201 at $n = 7..10$.

$(h, 2)(h, n-5)$: $51 \cdot (n-5)(n-6) = 3 \cdot 17 \cdot (n-5)(n-6)$

The $3 \cdot 17$ factorization is suggestive of “3 low-rotation patterns × 17 something”. Not investigated further tonight.

Verified: 102, 306, 612, 1020 at $n = 7..10$.

EL-shellability: position-labels fail

For an EL-labeling, every interval would have a unique strictly-increasing maximal chain. Natural label: position $i \in {0, …, n-2}$ of the 2-sq swap.

Tested at $n = 7$, $(c, 0)(c, 4)$: for each of the 6 maximals $m$, count chains $\sigma_{\rm can} \to m$ with strictly-increasing position-labels:

$m_{\rm inv}$	#increasing chains
11	0
12	0
13	0
13	0
14	0
15	0

Zero everywhere. Position-labels are too restrictive — chain length up to 15, label range 0..5.

The right labeling probably mixes positional and structural information (which bit, which canonical rank). Defer to n.564.

Methodological lessons

#276 Formulas first, structure second. Polynomial fits across $n$ pointed me at $\binom{n-3}{2}$, which immediately suggested “ordered pair of two things” — and that led to the explicit bijection.

#277 State-graph reduction. R-paths of $(c, 0)(c, n-3)$ reduce to lattice walks in 2D $(p, q)$-space with a forbidden corner. The combinatorial structure that looked $n!$-large collapses to a 2-state-variable problem.

#278 Canonical rank converts ascent to local check. Once rank is fixed, “ascent at position $i$” is a 2-bit local property. R-block check is a single cube-membership query. The combination forces structural form.

#279 Negative shellability result still informative. Position-label EL failure tells us the right labeling mixes structural data with positional data — pushing toward CL-shellability or subword-complex framework.

Frontier for n.564

(1) Prove $(c, 1)(c, n-4)$ formula structurally, mirroring the (c,0) argument with 4 shape cases.

(2) Prove $(h, 2)(h, n-5) = 51(n-5)(n-6)$. The 51 = 3·17 factorization should match (3 low-bit rotations) × (17 boundary patterns).

(3) Total maximal count $\sum_{\text{class}} |\mathrm{Max}^{\text{class}}| \cdot |\text{class}|$ — asymptotic in $n$?

(4) EL-shellability via richer labels or via Coxeter-theoretic embedding into $\mathrm{Sym}_{n+1}$ weak Bruhat. Björner-Wachs 1988 EL is the target.