Theorem A least simple label splits off one edge from increasing paths
✓ theorem proved

A least simple label splits off one edge from increasing paths

Fix a finite-generator Coxeter system, a ratio order \(O\), and a simple generator \(s=s_i\). Assume \[ \sigma_O(\alpha_i)<\sigma_O(a)\quad(a\ne\alpha_i), \qquad \ell(x)<\ell(sx). \] For any endpoint \(y\), prefixing the simple edge \(\epsilon_{i,x}:x\to sx\) gives a bijection \[ \mathcal N_{O,i}(sx,y) \longrightarrow \{p\in\operatorname{Paths}_O(x,y):\neg\operatorname{Avoid}_i(p)\}, \qquad q\longmapsto\epsilon_{i,x}::q. \tag{1} \] Consequently, \[ F_O(x,y;X) =\sum_{p\in\mathcal N_{O,i}(x,y)}X^{|p|} +X\sum_{q\in\mathcal N_{O,i}(sx,y)}X^{|q|}. \tag{2} \]

Relation to the OpenAI notes

Actual edge rotation and the two path-sum bijections.

OpenAI notes: The notes present the increasing-path expression as the normalized R-polynomial and cite Dyer for the formula. bg:paths, eq:bg-path-formula.

Lean (primary): The independent path proof partitions actual finite path sets by avoidance of one chosen simple label. Rotating the avoiding paths gives a full target path set because the chosen label is greatest there and the rotated endpoint is an ascent. Paths containing the least label are obtained by prefixing the uniquely determined simple edge. DyerPaths:2091, DyerPaths:2160, DyerPaths:2268, DyerPaths:2174, DyerPaths:2184, DyerPaths:2198, DyerPaths:2247, DyerPaths:2276, DyerPaths:2340, DyerPaths:2376.

Role in the proof: The Blueprint defines the exact avoidance predicate and total edge map, proves both finite bijections and identifies the extra polynomial factor with the prefixed edge.

Proof

Step 1. A prefix gives a directed increasing path

Take \(q\in\mathcal N_{O,i}(sx,y)\). Its directed path begins at \(sx\), which is the target of \(\epsilon_{i,x}\), so prefixing gives a directed path from \(x\) to \(y\).

The tail is strictly increasing and avoids \(\alpha_i\). The prefixed edge has label \(\alpha_i\), whose slope is strictly below every tail label. Thus all comparisons involving the new head are strict in the required direction, and all remaining comparisons hold in the tail. The Bruhat path-selection theorem places the resulting list in \(\operatorname{Paths}_O(x,y)\). It contains the chosen label at its first edge, so it belongs to the codomain in (1).

Step 2. Recovery of the unique prefix

Take an increasing path \(p\) in that codomain. It contains an edge labelled \(\alpha_i\), so it is nonempty. Write it as \(e::q\). By the least-label part of the extremal-label theorem, the tail avoids \(\alpha_i\). Therefore the occurrence of the chosen label must be the head \(e\).

The path begins at \(x\), and the label/endpoint equation gives \(r(e)=sx\). An actual Bruhat edge is determined by its two endpoints, so \(e=\epsilon_{i,x}\). The tail \(q\) is a directed path from \(sx\) to \(y\), inherits strict increase, and avoids \(\alpha_i\). Hence \(q\in\mathcal N_{O,i}(sx,y)\).

Step 3. The inverse maps

Deleting the first edge of \(\epsilon_{i,x}::q\) recovers \(q\). Conversely, Step 2 shows that every path containing the chosen label recovers exactly such a tail and has the prescribed simple head. Thus deletion and prefixing are inverse maps, proving (1).

Step 4. The partition and its two weighted sums

Partition \(\operatorname{Paths}_O(x,y)\) into paths avoiding \(\alpha_i\) and paths containing it. The sum over the first subset is the first term in (2). Use the bijection (1) in the second subset. Since \[ |\epsilon_{i,x}::q|=1+|q|, \qquad X^{1+|q|}=X\,X^{|q|}, \] that sum is \[ \sum_{q\in\mathcal N_{O,i}(sx,y)}X\,X^{|q|} =X\sum_{q\in\mathcal N_{O,i}(sx,y)}X^{|q|}. \] Adding the two parts proves (2).

For the rank-one interval \(1\to s\), the first subset is empty and the second consists of the simple edge. Its tail is the empty path at \(s\). Formula (2) becomes \(F_O(1,s;X)=0+X\cdot1=X\).

References

The local source declarations below give the construction and proof.

Lean formalization

OAI.KLInvariance.AdaptedDyer.cons_simple_mem: DyerPaths.lean:2325.

OAI.KLInvariance.AdaptedDyer.not_nonsimple_iff_cons: DyerPaths.lean:2340.

OAI.KLInvariance.AdaptedDyer.polynomial_split: DyerPaths.lean:2376.

Used by