Topic Coxeter Systems and Bruhat Order
topic admitted

Coxeter Systems and Bruhat Order

A Coxeter system is a group with a presentation by simple reflections and braid relations. The Bruhat order is a canonical partial order on the Coxeter group, encoding "containment" of cells in the Bruhat decomposition. Together they are the combinatorial infrastructure for the entire structure theory of reductive groups.

Coxeter systems

A Coxeter system is a pair \((W, S)\) where \(W\) is a group with a distinguished set \(S \subseteq W\) of generating involutions, presented as: \[ W \;=\; \langle S \mid s^2 = 1 \text{ for } s \in S, \;(st)^{m_{st}} = 1 \text{ for } s \ne t \rangle, \] with \(m_{st} \in \{2, 3, 4, \ldots, \infty\}\) (using \((st)^\infty = 1\) to mean no relation).

The matrix \((m_{st})\) is the Coxeter matrix; the corresponding graph (vertices = \(S\), edges labelled by \(m_{st}\) for \(m_{st} \ge 3\)) is the Coxeter diagram.

Examples

  • Finite Coxeter groups: Weyl groups of finite root systems (types \(A_n, B_n, D_n, E_6, E_7, E_8, F_4, G_2\)), plus non-crystallographic \(H_3, H_4, I_2(p)\).
  • Affine Coxeter groups: extended Weyl groups \(\tilde A_n, \tilde B_n, \ldots, \tilde G_2\); Coxeter graphs are the affine Dynkin diagrams.
  • Hyperbolic Coxeter groups: cocompact reflection groups in hyperbolic space (e.g.\ for the modular group).
  • Symmetric groups: \(S_n\) with simple transpositions \(s_i = (i, i+1)\); Coxeter system of type \(A_{n-1}\).

Length function

For \(w \in W\), the length \(\ell(w)\) is the minimum number of simple reflections needed to write \(w\) as a product: \[ \ell(w) \;=\; \min\{n : w = s_{i_1} \cdots s_{i_n}\}. \]

A product of \(\ell(w)\) simple reflections is a reduced expression.

For Weyl groups: \(\ell(w) = \#\{\alpha \in \Phi^+ : w(\alpha) \in \Phi^-\}\).

Bruhat order

The Bruhat order is the partial order \(\le\) on \(W\) generated by the subword property: \[ v \;\le\; w \;\iff\; \text{there exists a reduced expression of } w \text{ containing a reduced expression of } v \text{ as a subword.} \]

Equivalently (Subword characterisation): \[ v \le w \iff \forall \text{ reduced expression } s_{i_1} \cdots s_{i_n} \text{ of } w, \;v \text{ has a reduced subword.} \]

Properties of Bruhat order

For a Coxeter system \((W, S)\):

  • \((W, \le)\) is a graded poset with rank function \(\ell\);
  • minimum: identity \(e\);
  • if \(W\) is finite: maximum is the longest element \(w_0\);
  • self-duality (for finite \(W\)): \(v \le w \iff w_0 w \le w_0 v\);
  • Chevalley's lifting: if \(v \le w\) and \(v < vs\) for \(s \in S\), then either \(ws < w\) and \(v \le ws\), or \(vs \le w\).

Examples

\(S_3 = W(A_2)\)

Bruhat order: \[ e \;\le\; s_1, s_2 \;\le\; s_1 s_2, s_2 s_1 \;\le\; s_1 s_2 s_1. \] Hasse diagram is a "shifted diamond" with 6 elements.

\(S_4 = W(A_3)\)

24 elements, ranked by length \(\ell = 0, 1, 2, 3, 4, 5, 6\). The Hasse diagram is the "permutahedron" 1-skeleton, with the longest element \(w_0 = 4321\) at the top.

Affine \(\tilde A_1\)

\(W_{\mathrm{aff}} = \langle s_0, s_1 : s_0^2 = s_1^2 = 1\rangle\) (infinite dihedral). Bruhat order is the "zigzag": \(e < s_0, s_1 < s_0 s_1, s_1 s_0 < \ldots\), forming an infinite ladder.

Connection with Bruhat decomposition

For a reductive group \(G\) with Weyl group \(W\): \[ G \;=\; \bigsqcup_{w \in W} BwB, \] the Bruhat decomposition. The closure relations are: \[ \overline{BwB} \;=\; \bigsqcup_{v \le w} BvB, \] with \(\le\) the Bruhat order. This is what gives the Bruhat order its geometric content: it's the order on Schubert cells.

For \(G/B\) the flag variety: the Schubert variety \(X_w = \overline{BwB/B}\) has dimension \(\ell(w)\) and closure \(\bigcup_{v \le w} X_v\).

Connection with Iwahori-Hecke algebra

The Iwahori-Hecke algebra \(\mathcal{H}(W)\) has basis \(\{T_w\}_{w \in W}\) with multiplication \[ T_s T_w \;=\; \begin{cases} T_{sw} & \text{if } \ell(sw) > \ell(w), \\ q T_{sw} + (q-1) T_w & \text{if } \ell(sw) < \ell(w). \end{cases} \]

Kazhdan-Lusztig polynomials \(P_{v, w}(q)\) for \(v \le w\) encode deep representation-theoretic data — they're polynomials with non-negative coefficients (KL positivity, due to Elias-Williamson) and control IC sheaves on Schubert varieties.

Role in Langlands

  • Bruhat decomposition of \(G(F)\) under the Iwahori subgroup: \(G(F) = \sqcup_{\tilde w \in \tilde W} I \tilde w I\).
  • Iwahori-Hecke algebra: convolution algebra \(\mathcal{H}(I \backslash G(F) / I) = \mathcal{H}(\tilde W)\); Kazhdan-Lusztig theory describes its category of modules.
  • Affine flag variety: closure structure of Schubert cells encoded by Bruhat order on \(\tilde W\).
  • \(p\)-adic Langlands: KL polynomials of \(\tilde W\) control composition factors of induced representations.

Mathlib

Mathlib.GroupTheory.Coxeter.* formalises Coxeter groups; Bruhat order infrastructure is partial.

References

  • Bourbaki, Groupes et Algèbres de Lie IV (1968).
  • Humphreys, Reflection Groups and Coxeter Groups (1990).
  • Björner–Brenti, Combinatorics of Coxeter Groups (2005).
  • Kazhdan–Lusztig, Representations of Coxeter groups and Hecke algebras (Invent.\ Math.\ 1979).

Prerequisite Topics

Used by