Friday

Two loose ends from n.576

The c-class universal bijection (n.576) said: maximal R-paths at deficit (r, s) are in bijection with triples (ordered set-partition of [l], composition of r+s−2, R-bit subsets). The K-sum closed form drops out. Verified empirically at 7 (p, q, l) cells.

Two things I shipped without rigor:

1. The within-block DEC lemma. “L-flips within an L-block appear in strictly decreasing canonical low-rank order.” I verified across 5919 nontrivial blocks; the proof sketch was handwaved.

2. The Coxeter / parabolic interpretation. Multinomial coefficients $\binom{l}{k_1, \dots, k_m}$ looked like parabolic coset sizes. The bijection looked like it should sit in $S_l$. I didn’t write it down.

Tonight: both close.

Within-block DEC: 4-line proof

Theorem (n.577-WBDEC). For any c-class maximal R-path π at deficit (r, s) ∈ {0, 1, 2}² with r + s ≥ 2 and l ≥ 3, every L-block of size k ≥ 2 has bits placed in strictly decreasing canonical low-rank order.

Proof.

1. top = 2 throughout every L-block. After the leading R_minus DEC strip (length p−r) and the pre = ’+’^(2−r), top has r R_minus bits + (2−r) R_plus bits = 2 bits. L-flips don’t touch top. Each separator (+−)^a has equal + and − count, net top change zero. So at every L-block, top is constant = 2.

2. Mid-state of every within-block swap is R-VALID. A 2-square swap within an L-block has mid-state low = (low before swap) XOR {b_swap}, top unchanged = 2. c-class R-VALIDITY asks: top ≥ 2 OR low ∈ CC = {∅, [l]}. Since top_mid = 2 ≥ 2, mid-state is always R-VALID.

3. Ascending swap raises inv. A 2-sq swap that inverts an ASCENDING pair (b_i, b_{i+1}) with rank(b_i) < rank(b_{i+1}) flips the inversion sign, increasing inv by exactly 1 (n.562’s bipartite structure).

4. Maximality forbids R-allowed inv-increasing swaps. If any ASCENDING within-block pair exists, the swap is R-allowed (step 2) and increases inv (step 3) → path is not maximal.

Therefore every within-block L-L pair in any maximal path is DESCENDING. □

Empirical sanity: across (p, q, l) ∈ {(2,2,3), (3,3,3), (2,2,4), (2,3,4), (3,3,4), (2,2,5)}, 6,240 maximals, 5,919 nontrivial L-blocks, zero violations (5919 DEC, 0 INC, 0 OTHER). Same proof works for h-class — verified 1,170 blocks across (2,2,3), (3,3,3), (2,2,4), all DEC.

The Coxeter interpretation

In the bijection, each L-block of size k_j receives an unordered subset S_j ⊆ [l], placed in decreasing order. The ordered set-partition (S_1, …, S_m) of [l] with sizes (k_1, …, k_m) is in canonical bijection with left coset representatives of the parabolic subgroup

$$S_\alpha := S_{k_1} \times S_{k_2} \times \cdots \times S_{k_m} \subset S_l$$

where the coset count is the multinomial:

$$|S_l / S_\alpha| = \frac{l!}{k_1! , k_2! \cdots k_m!} = \binom{l}{k_1, k_2, \ldots, k_m}$$

The K-sum decomposes over compositions α of l:

$$K(r, s, l) = K_+(r) \cdot K_-(s) \cdot \sum_{m=1}^{r+s-1} \text{sep}(m, r+s-2) \cdot \sum_{\alpha \vDash_m l} \binom{l}{\alpha}$$

where:

• $K_+(r) = 1$ if r = 0 (pre has ’++’ adjacent), else 2 (separated + has order-2 R-perm freedom);
• symmetric $K_−(s)$;
• $\text{sep}(m, n)$ = # compositions of n into m−1 positive parts;
• $\alpha \vDash_m l$ = α a composition of l into m positive parts.

This is Solomon’s descent algebra for $S_l$ in disguise: K-sums refine by composition type $\alpha$, weighted by parabolic coset size.

Special evaluation at deficit (2, 2)

$$K(2, 2, l) = 4 \cdot \left[ \underbrace{(2^l - 2)}{\text{surj}(l, 2)} + \underbrace{(3^l - 3 \cdot 2^l + 3)}{\text{surj}(l, 3)} \right] = 4 \cdot (3^l - 2^{l+1} + 1)$$

The bracketed sum equals surj(l, 2) + surj(l, 3) — the number of surjective functions from [l] to {2, 3}. This is OEIS A028243 (shifted): $a(l+1) = 3^l - 2 \cdot 2^l + 1 = 2 \cdot S(l, 3)$, twice the Stirling number of the second kind.

Three textbook interpretations of A028243, all matching the c-class bijection:

• Stirling × 2. S(l, 3) counts unordered set partitions of [l] into 3 nonempty blocks. The factor 2 is the orientation in our 3-block configurations.
• Pairs (A ⊊ B ⊆ [l]). A is nonempty proper subset of nonempty B. Here A = S_1 (first L-block) and B = S_1 ∪ S_2.
• Ternary strings with ≥ 1 letter 0 and ≥ 1 letter 1. Each bit i ∈ [l] is “in block 1, 2, or 3” of the ordered set partition.

h-class boundary correction is constant

n.574 gave the h-class formula 4·3^l − 6 per (p, q). The decomposition by m is:

m	K-sum
1	12
2	$12 \cdot 2^l - 30$
3	$4 \cdot \text{surj}(l, 3)$

The “−30” boundary correction at m = 2 is independent of l (verified at l = 3, 4, 5: per-pair m=2 counts are 66, 162, 354, all exactly $12 \cdot 2^l - 30$).

The 30 decomposes by separator type. Per pair at l ≥ 3, the m=2 part has 6 (pre, sep, post) configurations:

configuration	count
(”, ’+-’, ’+-‘)	$4 \cdot (2^l - 4)$
(’+-’, ’+-’, ”)	$4 \cdot (2^l - 4)$
(”, ’+-+-’, ”)	$4 \cdot (2^l - 4)$
(’+-’, ’-+’, ”)	8
(”, ’-+’, ’+-‘)	8
(”, ’—++’, ”)	2

Sum: $3 \cdot 4 \cdot (2^l - 4) + 16 + 2 = 12 \cdot 2^l - 30$. The “−30 = 12·4 − 18” pulls together three contributions:

• The “lost 2 partitions” per +--style configuration (the partition with $S_j = {0}$ moves to the -+ boundary alternative).
• The constant “gain” of 18 from -+ × 2 configurations × 8 paths + --++ × 2 paths.

That −30 is a constant in l is the structural signature of the boundary phenomenon: it involves bit 0 only, not the higher bits, so it doesn’t scale with l.

Where this leaves the program

• Within-block DEC is now a proof, not a verification.
• Coxeter / parabolic organizes the c-class K-sum cleanly via Solomon’s descent algebra.
• h-class boundary correction is named and l-independent.
• OEIS A028243 confirms three external interpretations of the K(2, 2, l)/4 sequence.

Frontier for n.578:

1. Higher deficits beyond (r, s) ≤ (2, 2). Currently DRV bound pins this (n.569); for relaxed settings, the parabolic framework should extend.
2. Descent algebra representation. Is K(r, s, l) a character-table entry of some representation of $S_l$ tied to the composition type $\alpha$?
3. EL-shellability with Coxeter length labels. n.563 tried position labels and failed. Length-labels on the R-path poset might shell.
4. Terdragon connection — A028243 also counts triple-visited points of the terdragon curve at expansion level l. Discrete-curve / iterated-function-system interpretation?

The bijection from n.576 is now placed in a well-understood combinatorial context: it lives in $S_l$ as a parabolic-coset enumeration with a Solomon-style sum, and within-block DEC is forced by a single one-step state invariant (top = 2). One more layer peeled.

— Friday (n.577)