Theorem Extremal simple labels on increasing paths
✓ theorem proved

Extremal simple labels on increasing paths

Fix a finite-generator Coxeter system, a simple generator \(s=s_i\), and a ratio order \(O\). Use the avoidance predicate and increasing path sets from the simple-root path definitions.

If \(\alpha_i\) has strictly smaller slope than every other positive root, then:

  • the tail of any nonempty strictly increasing edge list avoids \(\alpha_i\);
  • if \(\ell(sx)<\ell(x)\), every increasing path from \(x\) to any \(y\) avoids \(\alpha_i\).

If \(\alpha_i\) has strictly greater slope than every other positive root and \(s\) is not a left descent at \(y\), meaning \[ \neg\bigl(\ell(sy)<\ell(y)\bigr), \] then every increasing path ending at \(y\) avoids \(\alpha_i\).

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 least label can occur only at the first position

Let \(e::q\) be strictly increasing, and suppose an edge \(h\) in the tail has label \(\alpha_i\). Strict increase gives \[ \operatorname{score}_O(e) <\operatorname{score}_O(h)=\sigma_O(\alpha_i). \] But every edge label has slope at least \(\sigma_O(\alpha_i)\): equality holds for the chosen root, and every other root has larger slope. This contradicts the displayed inequality. Thus the tail avoids \(\alpha_i\).

Step 2. The descent at the initial vertex excludes the first position

Take an increasing path from \(x\) to \(y\) with \(\ell(sx)<\ell(x)\). If it is empty, avoidance is vacuous. If its first edge has label \(\alpha_i\), the label/endpoint identity forces it to be \(x\to sx\). Its upward orientation would give \(\ell(x)<\ell(sx)\), contradicting the hypothesis. Thus the first edge also avoids the label; Step 1 treats every later edge.

Step 3. A greatest label can occur only at the last position

Suppose now that \(\alpha_i\) has greatest slope. If an edge with that label had a later edge in a strictly increasing list, the later score would have to exceed \(\sigma_O(\alpha_i)\). Every positive-root score is at most this maximum, so this is impossible. An occurrence of the chosen label must therefore be last.

Step 4. The final-vertex condition excludes the last position

For an increasing path ending at \(y\), a last edge with label \(\alpha_i\) has target \(y\) and source \(sy\): its endpoint equation is \(y=s\,s(e)\), so \(s(e)=sy\). The upward orientation gives \(\ell(sy)<\ell(y)\). This contradicts the assumed absence of that descent. Step 3 excludes the label at every earlier position, proving avoidance of the whole path.

In the rotated path-sum theorem, the new endpoint is \(sy\), where the original hypothesis \(\ell(sy)<\ell(y)\) implies that \(s\) is not a descent: \(s(sy)=y\) has greater length. The greatest-label assertion therefore applies to every path in the rotated target path set.

References

The local source declarations below give the construction and proof.

Lean formalization

OAI.KLInvariance.AdaptedDyer.nonsimple_of_greatest: DyerPaths.lean:2198.

OAI.KLInvariance.AdaptedDyer.nonsimple_tail_of_least: DyerPaths.lean:2233.

OAI.KLInvariance.AdaptedDyer.nonsimple_of_least_descent: DyerPaths.lean:2247.

Used by