Definition Simple-labelled edges, avoidance, and edge rotation
✓ definition formalized

Simple-labelled edges, avoidance, and edge rotation

Fix a finite-generator Coxeter system \(W\), a simple generator \(s=s_i\), and its positive simple root \(\alpha_i\). Use the actual directed reflection-edge graph of \(W\); an edge \(e:x\to y\) has positive left root label \(\alpha_e\).

Edges with the chosen simple label

The label condition is equivalent to an endpoint equation: \[ \alpha_e=\alpha_i\Longleftrightarrow y=sx. \] Indeed, the reflection labelling \(e\) is \(yx^{-1}\). Equality of the roots gives this reflection as \(s\), yielding \(y=sx\). Conversely, \(y=sx\) gives reflection \(s\), whose unique positive root is \(\alpha_i\).

If \(\ell(x)<\ell(sx)\), define the simple edge \[ \epsilon_{i,x}:x\longrightarrow sx. \] It is simpleEdge. Its endpoints and root label are \(x,sx,\alpha_i\), respectively.

The total edge rotation

Define \(g_i:E\to E\) by \[ g_i(e)= \begin{cases} e,&\alpha_e=\alpha_i,\\ (sx\to sy),&\alpha_e\ne\alpha_i,\quad e:x\to y. \end{cases} \] This is rotateEdge. In the second case, the endpoint equation above gives \(y\ne sx\). The simple-edge transport theorem says that an upward reflection edge \(x\to y\) satisfying this inequality is sent to the upward reflection edge \(sx\to sy\). Hence the second case is an actual edge.

The map fixes edges with the chosen simple label. On every other edge it is left multiplication of both endpoints by \(s\). The simple-root path transport theorem proves its involution and root-label formulas.

Lists avoiding the chosen label

For any finite edge list \(q\), define \[ \operatorname{Avoid}_i(q) \Longleftrightarrow \alpha_e\ne\alpha_i\quad\text{for every edge }e\text{ occurring in }q. \] Lean calls this predicate Nonsimple i q. It is a predicate on lists; the directed-path condition is supplied separately. Edges labelled by another simple root are allowed.

For a ratio order \(O\), let \[ \mathcal N_{O,i}(x,y) =\{q\in\operatorname{Paths}_O(x,y):\operatorname{Avoid}_i(q)\}. \] This is the finite set nonsimplePaths. Its membership condition is exactly the conjunction of selected increasing-path membership and avoidance of \(\alpha_i\).

On a list satisfying \(\operatorname{Avoid}_i\), every edge uses the second case of \(g_i\). The endpoint formulas therefore match the same vertex map \(z\mapsto sz\) throughout the list. This lets the edgewise rotation transport a path from \(x\) to \(y\) to one from \(sx\) to \(sy\).

The simple prefix used in path splitting

When \(\alpha_i\) is the least root label and \(\ell(x)<\ell(sx)\), an increasing path containing \(\alpha_i\) begins with \(\epsilon_{i,x}\). Its tail starts at \(sx\), ends at the original endpoint, and avoids the chosen label. The simple-prefix decomposition proves the resulting bijection and accounts for the extra factor \(X\) in the polynomial recursion.

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.

References

The local source declarations below give the construction and proof.

Lean formalization

OAI.KLInvariance.AdaptedDyer.rootLabel_simple_iff: DyerPaths.lean:2078.

OAI.KLInvariance.AdaptedDyer.rotateEdge: DyerPaths.lean:2091.

OAI.KLInvariance.AdaptedDyer.Nonsimple: DyerPaths.lean:2160.

OAI.KLInvariance.AdaptedDyer.nonsimplePaths: DyerPaths.lean:2268.

OAI.KLInvariance.AdaptedDyer.mem_nonsimplePaths: DyerPaths.lean:2271.

OAI.KLInvariance.AdaptedDyer.simpleEdge: DyerPaths.lean:2309.

OAI.KLInvariance.AdaptedDyer.simpleEdge_source: DyerPaths.lean:2313.

OAI.KLInvariance.AdaptedDyer.simpleEdge_target: DyerPaths.lean:2317.

OAI.KLInvariance.AdaptedDyer.simpleEdge_root: DyerPaths.lean:2320.

Used by