Lemma 4

Let $w \in W$ have length $q \geq 1$, let D be the set of reduced decompositions of $w$, and let F be a map from D to a set E. Assume that $F(s) = F(s')$ if the elements $s = (s_1, \ldots, s_q); s' = (s'_1, \ldots, s'_q)$ of D satisfy one of the following hypotheses:

a) $s_1 = s'_1$ or $s_q = s'_q$. b) There exist s and $s'$ in S such that $s_j = s'_k = s$ and $s_k = s'_j = s'$ for $j$ odd and $k$ even.

Then F is constant.

A) Let $s, s' \in D$ and put $t = (s'_1, s_1, \ldots, s_{q-1})$. We are going to show that if $F(s) \neq F(s')$ then $t \in D$ and $F(t) \neq F(s)$. Indeed, $w = s'_1 \ldots s'_q$ and hence $s'_1 w = s'_2 \ldots s'_q$ is of length $< q$. By Prop. 4, there exists an integer $j$ such that $1 \leq j \leq q$ and the sequence $u = (s'_1, s_1, \ldots, s_{j-1}, s_{j+1}, \ldots, s_q)$ belongs to D. We have $F(u) = F(s')$ by condition a); if $j \neq q$ we would have $F(s) = F(u)$ for the same reason, and hence $F(s) = F(s')$ contrary to our hypothesis. Thus $j = q$ and hence $t = u \in D$ and $F(t) = F(s') \neq F(s)$.

B) Let s and $s'$ belong to D. For any integer $j$ with $0 \leq j \leq q + 1$ define a sequence $s_j$ of q elements of S as follows:

for $q - k$ even and $0 \leq k \leq q$ for $q - k$ odd and $0 \leq k \leq q$.

Denote by (H_j) the assertion "s_j \in D, s_{j+1} \in D \text{ and } F(s_j) \neq F(s_{j+1})". By A), (H_j) \implies (H_{j+1}) for $0 \leq j < q$, and (H_q) is not satisfied by condition b). Hence, (H_0) is not satisfied. Since $s_0 = s'$ and $s_1 = s$, it follows that $F(s) = F(s')$.