Finiteness of Bruhat intervals
Every interval \([u,b]\) in an arbitrary Coxeter system is finite. The set of simple generators need not be finite.
Proof
Step 1. Bound the immediate reflection predecessors
Choose a reduced word \(\omega\) for \(b\). If \(x\to b\) is a reflection edge, write \(b=tx\), so \(x=tb\) and \(\ell(tb)<\ell(b)\). Strong exchange places \(t\) in the finite inversion list of \(\omega\). Thus every such \(x\) belongs to \(\{tb:t\text{ occurs in that finite list}\}\). There are therefore finitely many immediate reflection predecessors, even if the ambient generating set is infinite.
Step 2. Decompose the entire lower ideal
Let \(L(b)=\{x:x\le b\}\). By the definition of Bruhat order as the reflexive transitive closure of upward reflection steps, a comparison \(x\le b\) is either \(x=b\), or has a last step \(z\to b\), preceded by \(x\le z\). Consequently \[ L(b)\subseteq\{b\}\cup\bigcup_{z\to b}L(z). \]
Step 3. Induct on the top length
Use strong induction on \(\ell(b)\). Each predecessor \(z\to b\) has \(\ell(z)<\ell(b)\), so its lower ideal \(L(z)\) is finite by the induction hypothesis. Step 1 gives only finitely many such \(z\). A finite union of finite sets, together with the singleton \(\{b\}\), is finite. Step 2 shows that \(L(b)\) is a subset of this finite set.
At length zero, there are no predecessors, and the same argument leaves only the identity element.
Step 4. Pass to an interval
The interval \([u,b]\) is the subset of \(L(b)\) consisting of elements also above \(u\). A subset of a finite set is finite. This proves interval finiteness without any finite-rank hypothesis.
References
2. Real realizations and moment-graph sheaves.
Lean formalization
OAI.KLInvariance.interval_finite: Bruhat.lean:106.
OAI.KLInvariance.finite_bruhat_lower: Bruhat.lean:86.
Used by
- The reciprocity defect on a proper upper interval
- The reciprocal convolution identity for R-polynomials
- The normalization data for ordinary R and KL polynomials
- Inverse bar coefficients and the R-value kernel identity
- Lower-interval Hecke sums and their correction vectors
- Uniqueness of a normalized polynomial-family pair
- Bruhat support and bar reciprocity for positive Hecke words
- The recursive polynomial family on Bruhat intervals
- The increasing Bruhat path polynomial of a ratio order
- Bruhat endpoint bounds and the selected increasing paths
- Existence of normalized boundary sheaves on finite ordered graphs