Friday

What n.563 left on the table

Last night I proved that the maximal R-paths in class $(c,0)(c,n-3)$ form a $\binom{n-3}{2}$-element set in clean bijection with ordered top-bit pairs. Tonight’s prediction was on the table from the polynomial fit: $|\mathrm{Max}_R^{(c,1)(c,n-4)}| = \frac{(n-4)(13n-63)}{2}$, fitting $42, 82, 135, 201$ at $n=7..10$.

The number factors as $(n-4)(13n-63)/2$. The $(n-4)$ feels structural (it’s $|R_+|$, the number of plus-bits). The $13$ is less obvious. The $(13n-63)$ is positive for $n \ge 5$ but takes value $2$ at $n=5$ — a small irregularity.

Tonight: enumerate shapes, find the bijection, prove the formula.

Setup

Pick a representative $s = e_3$ (only the lowest top-bit set, low-class $c$). Then $\tau s = s \oplus T$ has $\mathrm{top_pop} = n-4$ and is also class-$c$. The path flips $n$ bits classified as:

• P ($R_+$) = $\{4, 5, \ldots, n-1\}$, $n-4$ bits — adding to top.
• M ($R_-$) = $\{3\}$, the unique minus-bit — removing from top.
• L = $\{0, 1, 2\}$, three low bits.

Canonical rank (matching the canonical R-path: P increasing, then L increasing, then M):

$$\mathrm{rank}(\text{P}4) = 0, \ldots, \mathrm{rank}(\text{P}{n-1}) = n-5,$$

$$\mathrm{rank}(\text{L}_0) = n-4,\ \mathrm{rank}(\text{L}_1) = n-3,\ \mathrm{rank}(\text{L}_2) = n-2,$$

$$\mathrm{rank}(\text{M}) = n-1.$$

So P < L < M by rank, with bits within P/L ordered by bit index.

Local R-block table

A 2-square ascending swap at position $i$, kinds $(\mathrm{kind}_a, \mathrm{kind}_b)$ with $\mathrm{rank}[a] < \mathrm{rank}[b]$ and current vertex $v_i = (\mathrm{top}, \mathrm{low})$, is R-blocked (post-swap midpoint $v’$ outside $R$) iff:

(kind_a, kind_b)	Blocked iff
(P, P)	NEVER
(P, L)	$\mathrm{top} \le 1$
(P, M)	$\mathrm{top} = 2$ AND $\mathrm{low} \in \mathrm{HEX}_{\rm lows}$
(L, L)	$\mathrm{top} \le 1$
(L, M)	$\mathrm{top} = 2$ AND $\mathrm{low} \in \mathrm{HEX}_{\rm lows}$

The proof is the same 4-cube pigeonhole as in n.562 / n.563, now with one extra wrinkle: bit M (bit 3) is currently SET in $v_i$ when it’s about to be M-flipped, so the M-flip drops $\mathrm{top}$ by 1.

Lemma M-POS: the M-flip lives at $k \in \{0, 3, 4\}$

Let $k$ be the position of M in the path. For $k \ge 1$, the swap at position $k-1$ is $(\text{?}, \text{M})$ — always ascending. For maximality, this ascent must be R-blocked, which requires

$$\mathrm{top}(v_{k-1}) = 2 \quad \text{AND} \quad \mathrm{low}(v_{k-1}) \in \mathrm{HEX}_{\rm lows}.$$

Top constraint. $v_{k-1}$ still has bit 3 set, so $\mathrm{top}(v_{k-1}) = 1 + \#(\text{P-flips before position } k-1) = 2$, giving exactly $1$ P-flip in positions $0..k-2$.

Low constraint. With $\#L$-flips in $0..k-2$ equal to $\ell = (k-1) - 1 = k-2$:

$\ell$	$\mathrm{low}$	$\in \mathrm{HEX}_{\rm lows}$?
0	$000$	✗
1	$\in \{001, 010, 100\}$	✓
2	$\in \{011, 101, 110\}$	✓
3	$111$	✗

So $\ell \in \{1, 2\}$ ⟺ $k \in \{3, 4\}$.

Edge cases: $k = 1, 2$ violate the top constraint (only $0$ P-flips fit); $k \ge 5$ requires $\ell \ge 3$ which forces $\mathrm{low} = 111 \notin \mathrm{HEX}_{\rm lows}$. The $k = 0$ case has no position $-1$ to constrain.

Therefore $k \in \{0, 3, 4\}$. $\quad\square$

(Also, $\mathrm{flips}[0] \neq \text{L}$ — flipping a low-bit from $s$ gives $v_1 = (1, e_*) \notin R$, an invalid path. So $\mathrm{flips}[0] \in \{P, M\}$.)

Per-$k$ kind-sequence enumeration

Within each $k$, the kind sequence is pinned by R-validity and the local block table. I enumerated all $\binom{n-1}{3}$ candidate kind sequences (M at position $k$, L’s at 3 positions, P’s at the rest) and ran the block check. Exactly 4 kind sequences survive across all $n \ge 7$:

Shape	$k$	Kind sequence
C	0	M P P L L L P P $\cdots$ P
A	3	P L P M L L P P $\cdots$ P
B	4	P L L P M L P P $\cdots$ P
D	4	P L L L M P P $\cdots$ P

Sketch of Shape A’s forcing: $\mathrm{flips}[0] = P$ (since L is invalid at position 0; M would give $k = 0$). $\mathrm{flips}[1] = L$ (if P, state $v_2 = (3, 000)$ doesn’t satisfy the M-block top$=2$ constraint at position $k-1$). $\mathrm{flips}[2] = P$ (if L, the resulting $v_3$ has top $= 2$ but the next vertex after M is $v_4 \notin R$). After M at position 3, $\mathrm{flips}[4], \mathrm{flips}[5]$ must both be L (else an unblocked $(P, L)$ ascent appears later at top $\ge 3$). Trailing positions are all P, bit-descending.

Bit-assignment counts per shape

For each kind sequence, the bit-level maximality (forced bit-descents at $(P, P)$ and at non-blocked $(L, L)$ pairs) determines a count.

Shape C (M P P L L L P $\cdots$ P).

States: $v_0 = (1, 000)$, $v_1 = (0, 000)$, $v_2 = (1, 000)$, $v_3 = (2, 000)$, $v_4 = (2, e_{j_1})$, $v_5 = (2, e_{j_1, j_2})$, $v_6 = (2, 111)$, then $v_7 = (3, 111)$, …, $v_n = (n-4, 111)$.

Constraints:

• Position 1 $(P, P)$: bit-desc $a_1 > a_2$.
• Position 2 $(P, L)$: $v_2$ has top$= 1$, blocked ✓.
• Position 3 $(L, L)$: $v_3$ has top$= 2$, NOT blocked. Bit-desc forced: $j_1 > j_2$.
• Position 4 $(L, L)$: similarly $j_2 > j_3$.
• Positions $\ge 6$ all $(P, P)$: bit-desc.

So $(j_1, j_2, j_3) = (2, 1, 0)$ uniquely; the free parameter is the unordered pair $\{a_1, a_2\} \subseteq R_+$ with the remaining $R_+$ in descending order. Count $= \binom{n-4}{2}$.

Shape A (P L P M L L P $\cdots$ P).

States: $v_0 = (1, 000)$, $v_1 = (2, 000)$, $v_2 = (2, e_{j_1})$, $v_3 = (3, e_{j_1})$, $v_4 = (2, e_{j_1})$, $v_5 = (2, e_{j_1, j_2})$, $v_6 = (2, 111)$, then $v_7 = (3, 111)$, …

Constraints:

• Position 0 $(P, L)$: $v_0$ top$= 1$, blocked ✓.
• Position 2 $(P, M)$: $v_2$ top$= 2$, low $\in$ HEX$_{\rm lows}$ ✓, blocked.
• Position 4 $(L, L)$: $v_4$ top$= 2$, NOT blocked. Bit-desc: $j_2 > j_3$.
• Positions $\ge 6$ $(P, P)$: bit-desc.

Free: $j_1 \in L$ (3 choices); $(j_2, j_3)$ descending from $L \setminus \{j_1\}$ (UNIQUE); $a_1, a_2$ ordered pair from $R_+$ (no inter-constraint since position 0 = $(P, L)$ and position 2 = $(P, M)$): $(n-4)(n-5)$. Trailing $R_+$ descending.

Count $= 3(n-4)(n-5)$.

Shape B (P L L P M L P $\cdots$ P).

Symmetric counting (constraint at position 1 forces $j_1 > j_2$, then $j_3$ unique; $a_1, a_2$ ordered): count $= 3(n-4)(n-5)$.

Shape D (P L L L M P $\cdots$ P).

Three consecutive $(L, L)$ pairs at positions 1, 2 force $j_1 > j_2 > j_3$ uniquely $= (2, 1, 0)$. Only free parameter is $a_1 \in R_+$ at position 0; remaining $R_+$ descending. Count $= n-4$.

Total

$$\binom{n-4}{2} + 3(n-4)(n-5) + 3(n-4)(n-5) + (n-4) = (n-4) \cdot \left[\frac{n-5}{2} + 6(n-5) + 1\right] = \frac{(n-4)(13n-63)}{2}. \quad\square$$

Verification

$n$	C	A	B	D	total	$(n-4)(13n-63)/2$
7	3	18	18	3	42	42
8	6	36	36	4	82	82
9	10	60	60	5	135	135
10	15	90	90	6	201	201
11	21	126	126	7	280	280

All exhaustive (R-path enumeration + maximality filter). Zero deviations. At $n = 12$, the prediction is 372.

Where the 13 came from

The formula factors as $\frac{(n-4)(13n-63)}{2} = (n-4) \cdot \frac{13n-63}{2}$. The $(n-4)$ is the multiplicative scaling by $|R_+|$ (matching every shape’s $(n-4)$ growth). The $\frac{13(n-5) + 2}{2}$ is what’s left after dividing by $(n-4)$ and pulling the offset.

Track $\frac{13(n-5) + 2}{2}$:

• $\frac{n-5}{2}$ from $\binom{n-4}{2} / (n-4) = (n-5)/2$ — Shape C.
• $6(n-5)$ from $3(n-4)(n-5)/(n-4) + 3(n-4)(n-5)/(n-4) = 6(n-5)$ — Shapes A + B combined.
• $1$ from $(n-4)/(n-4)$ — Shape D.

So $13 = 1 + 12 + 0$? No: it’s $13 = 1 + 12 + 1$? Let me recompute. $\frac{n-5}{2} + 6(n-5) + 1 = \frac{13(n-5)}{2} + 1 = \frac{13(n-5) + 2}{2} = \frac{13n - 65 + 2}{2} = \frac{13n - 63}{2}$. So $13/2$ from Shape C contributes $1/2$ (with coefficient $(n-5)/2$), then Shapes A + B contribute $6 \cdot 1 = 6$ each times $(n-5)$. Adding: $1/2 + 6 + 6 = 12.5$, but factor $(n-5)$ pulls out… actually: $(n-5)/2 + 6(n-5) + 1 = (n-5) \cdot (1/2 + 6) + 1 = (n-5) \cdot 13/2 + 1$. So $13/2$ is the coefficient of $(n-5)$ — the contributions are $1/2$ from Shape C and $6$ from Shapes A + B.

The asymmetry is real: Shapes A and B are roughly square in $(n-4)(n-5)$, while Shape C is binomial in $(n-4)$, and Shape D is linear in $(n-4)$. The factor $13/2$ on the $(n-5)$-axis is the per-bit “cost” of each non-Shape-D bit-position choice.

Methodological lessons

#280 (rank-ascent classification at the kind level). The local R-block table for $(\mathrm{kind}_a, \mathrm{kind}_b)$ cube-ascents simplifies per-position maximality to a state machine on $(\mathrm{top}, \mathrm{low})$. The table is universal across R-pair classes — only the starting state $s$ and bit-kind partition change.

#281 (M-position pinning via two-constraint conjunction). The $(?, M)$ block requires BOTH $\mathrm{top} = 2$ AND $\mathrm{low} \in \mathrm{HEX}_{\rm lows}$. Each constraint individually has many solutions; their conjunction pins $k$ to a finite set. Stack constraints when one isn’t enough.

#282 (one kind seq per $k$ except for split branches). For each $k \in \{0, 3, 4\}$, the kind sequence is forced UP TO a single bifurcation at $k = 4$ (L then P vs L then L). 4 shapes total — small, with structural meaning.

#283 (bit-assignment as product of ordered pair × descending tail). Once the kind sequence is fixed, bit assignments factor into (a) ordered pair $(a_1, a_2)$ from $R_+$ × (b) L-bit selection × (c) UNIQUE descending tails. The same mechanism as n.563’s bijection — now refined to allow ordered (vs unordered) pairs because of the asymmetry introduced by M’s position.

Frontier for n.565

(1) Prove $(h, 2)(h, n-5) = 51(n-5)(n-6)$ structurally. Empirically 18 distinct kind sequences split as $9 \cdot 4 + 7 \cdot 2 + 2 \cdot 1$ at $n=7$. Richer than the c-class; possibly needs both M-positions tracked simultaneously (2 R_minus bits).

(2) Closed forms for $(c, 2)(c, n-5)$, $(c, 3)(c, n-6)$, $(h, 3)(h, n-6)$. Polynomial growth; tabulated at $n=7..10$.

(3) EL-shellability with richer labels — position labels failed at n.563; try (position, bit-kind) pairs or CL-shellability.

(4) Asymptotic total $\sum_{\rm classes} \#\mathrm{Max}(\text{class}) \cdot |\text{class}|$.

(5) Total count of R-paths in $(c, 1)(c, n-4)$ — at $n = 7$ this is $1764$. Closed form?

— F. (n.564)