Feeds:
Posts

## The strong exchange condition

It’s nice that Weyl groups are Coxeter groups and all, but the definition of a Coxeter group as a group with a particular kind of representation doesn’t immediately tell us why this is the appropriate level of generalization (although the faithfulness of the geometric representation is a good sign). It turns out there is a structural property, the strong exchange condition, which completely characterizes Coxeter groups among groups generated by involutions. Today we will prove this property.

Recall that we showed that the roots $\Phi$ of a Coxeter system $(W, S)$ can be divided into the positive roots $\Phi^{+}$ and the negative roots $\Phi^{-}$.

Proposition: a) Any simple reflection $s \in S$ sends $\alpha_s$ to its negative and permutes the remaining positive roots. b) $\ell(w)$ equals the number of positive roots sent by $w \in W$ to negative roots.

Proof. a) If $\alpha = \sum_t c_t \alpha_t$ is a positive root not equal to $\alpha_s$, then it has non-negative coefficients and some $c_t > 0$. Applying $s$ doesn’t change the coefficient $c_t$, so the root $s \alpha$, which cannot be equal to $\alpha_s$, must be positive.

b) Let $N(w)$ denote the set of positive roots sent by $w$ to negative roots. If $\ell(ws) = \ell(w) + 1$, then $w(\alpha_s) > 0$, so $N(ws) = s N(w) \cup \{ \alpha_s \}$. Similarly, if $\ell(ws) = \ell(w) - 1$, then $w(\alpha_s) < 0$, so $N(ws) = s( N(w) - \{ \alpha_s \})$. It follows by induction that $|N(w)| = \ell(w)$ for all $w$.

Corollary: If $W$ is infinite, then the length function takes arbitrarily large values, hence $\Phi$ is infinite. If $W$ is finite, then $W$ has a unique element $w_0$ of maximal length, the longest element, hence $\Phi$ is finite.

Proof. Since $W$ has finitely many generators, there are only finitely many words of a given length, so the length function (and hence the number of positive roots which can be sent to negative roots) is unbounded if and only if $W$ is infinite. If $w_0, w_1$ are two elements of maximal length with $W$ finite, then $\ell(w_i s) < \ell(w_i)$ for all $s$, so each $w_i$ sends all positive roots to negative roots. (In particular, there are at most $\ell(w_i)$ positive roots.) It follows that $w_0 w_1^{-1}$ sends every positive root to a positive root, hence has length zero and must be the identity.

Example. In the symmetric group $S_n$, the longest element is the permutation $n (n-1) (n-2) ... 3 2 1$ in one-line notation. It has length ${n \choose 2}$, as can be deduced from an enumeration of the positive roots. The geometric representation can be placed in the hyperplane $x_1 + ... + x_n = 0$, on which $S_n$ acts by permutation. The simple roots are the vectors of the form $\langle 0, 0, ... 0, 1, -1, 0, ... \rangle$, and the positive roots are their images under permutation in which the $1$ occurs before the $-1$.

Associated to any positive root $\alpha = w(\alpha_s)$ there is a reflection $wsw^{-1}$ conjugate to a simple reflection which negates $\alpha$. A short computation shows that

$wsw^{-1}(v) = v - 2B(v, \alpha) \alpha$

hence that the behavior of $wsw^{-1}$ doesn’t depend on a choice of $w, s$, but only on the root $\alpha$; we will therefore denote this reflection by $s_{\alpha}$. More generally, if $\beta = w(\alpha)$ where $\alpha, \beta$ are two roots, then $ws_{\alpha}w^{-1} = s_{\beta}$. It follows that we may freely identify the set

$\displaystyle T = \bigcup_{w \in W, s \in S} wsw^{-1}$

of conjugates of simple reflections with the set of positive roots.

Proposition: Let $\alpha$ be a positive root. If $\ell(ws_{\alpha}) > \ell(w)$, then $w(s_{\alpha}) > 0$.

Proof. Again we proceed by induction. If $\ell(w) = 0$ the result is clear. If $\ell(w) > 0$, then pick $s$ such that $\ell(sw) < \ell(w)$. Then

$\ell(sws_{\alpha}) \ge \ell(ws_{\alpha}) - 1 > \ell(w) - 1 = \ell(sw)$.

By the inductive hypothesis, $sw(\alpha) > 0$. If $w(\alpha) < 0$, then since $s$ sends exactly one root to its negative we must have $w(\alpha) = -\alpha_s$, hence $sw(\alpha) = \alpha_s$. This implies that $sw s_{\alpha} (sw)^{-1} = s$, hence that $ws_{\alpha} = sw$. But we know that $\ell(ws_{\alpha}) > \ell(w) > \ell(sw)$; contradiction. Hence $w(\alpha) > 0$.

The strong exchange condition

The following theorem completely characterizes Coxeter groups among groups generated by involutions.

Theorem (strong exchange): Let $w = s_1 ... s_r$ where $s_i \in S$ (not necessarily a reduced expression). Suppose $t \in T$ satisfies $\ell(wt) < \ell(w)$. Then there exists an index $i$ such that $wt = s_1 ... \hat{s_i} ... s_r$ (where the hat indicates that a factor has been omitted). If $\ell(w) = r$, then $i$ is unique.

Proof. Let $t = s_{\alpha}$. Since $\ell(wt) < \ell(w)$, we know that $w(\alpha) < 0$. Since $\alpha > 0$, there exists some index $i$ such that $s_{i+1} ... s_r(\alpha) > 0$ but $s_i s_{i+1} ... s_r(\alpha) < 0$. Since the only positive root that $s_i$ negates is $\alpha_{s_i}$, it follows that $s_{i+1} ... s_r(\alpha) = \alpha_{s_i}$, hence that

$s_{i+1} ... s_r t s_r ... s_{i+1} = s_i$

hence that $wt = s_1 ... \hat{s_i} ... s_r$ as desired. A short computation now shows that if $wt = s_1 ... \hat{s_i} ... s_r = s_1 ... \hat{s_j} ... s_r$, then $w = s_1 ... \hat{s_i} ... \hat{s_j} ... s_r$, which is impossible when $\ell(w) = r$.

Corollary (deletion): Suppose $w = s_1 ... s_r$ with $\ell(w) < r$. Then there exist indices $i < j$ such that $w = s_1 ... \hat{s_i} ... \hat{s_j} ... s_r$.

Proof. If $s_1 ... s_r$ is not a reduced expression, then there exists $j$ such that $\ell(s_1 ... s_{j-1}) > \ell(s_1 ... s_j)$. The exchange condition then implies that $s_1 ... s_j = s_1 ... \hat{s_i} ... s_{j-1}$.

On the other hand, Humphreys shows in Chapter 1 that any group generated by involutions satisfying the deletion condition must be a Coxeter group. So the strong exchange and deletion conditions must, in principle, be enough to answer any question one could ask of an arbitrary Coxeter group.