Let (s_1, \ldots, s_p) and (s'_1, \ldots, s'_q) be reduced decompositions of w and w' respectively. Thus l(w) = p and l(w') = q. Since ww' = s_1 \ldots s_p s'_1 \ldots s'_q, we have l(ww') \leq p + q, proving (1). Since S = S^{-1} and w^{-1} = s_p^{-1} \ldots s_1^{-1}, we have l(w^{-1}) \leq p = l(w). Replacing w by w^{-1} gives the opposite inequality l(w) \leq l(w^{-1}), proving (2). Replacing w by ww'^{-1} in (1) and (2) gives the relations

Exchanging $w$ and $w'$ in (4) gives $l(w') - l(w) \leq l(w{w'}^{-1})$ by (5), proving (3).

By hypothesis, $l(w) \leq p$, $l(w') \leq q$ and $l(ww') = p + q$. By (1), we must have $l(w) = p$ and $l(w') = q$, hence the corollary.

Remark In view of formulas (1) and (2), the formula $d(w, w') = l(w{w'}^{-1})$ defines a distance on $W$, invariant under right translations.

(i) The subgroup $P$ of $W$ generated by $p = ss'$ is normal, and $W$ is the semi-direct product of the subgroup $T = \{1, s\}$ and $P$. Moreover, $(W : P) = 2$.

(ii) Let $m$ be the order (finite or infinite) of $p$. Then $m \geq 2$ and $W$ is of order $2m$. There is a unique isomorphism $\varphi$ from $D_m$ to $W$ such that $\varphi(\rho) = s$ and $\varphi(\rho') = s'$.

(i) We have $sps^{-1} = sss's = s's = p^{-1}$, and hence

for every integer $n$. Since $W$ is generated by $\{ s, s' \}$, and hence by $\{ s, p \}$, the subgroup $P$ is normal. It follows that $TP$ is a subgroup of $W$, and since $TP$ contains $s$ and $s' = sp$, we have $W = TP = P \cup sP$. To prove (i), it is therefore enough to show that $W \neq P$. If $W = P$, the group $W$ would be commutative, so $p^2 = s^2 {s'}^2 = 1$. But then the only elements of $W = P$ would be 1 and $p$, contradicting the hypothesis that $W$ contains at least three elements, namely 1, $s$ and $s'$.

(ii) Since $s \neq s'$, we have $p \neq 1$ and so $m \geq 2$. Since $P$ is of order $m$ and $(W : P) = 2$, the order of $W$ is $2m$. If $m$ is finite (resp. infinite), there exists an isomorphism $\varphi'$ from $\mathbf{Z}/m\mathbf{Z}$ (resp. $\mathbf{Z}$) to $P$ taking $\pi$ to $p$. Moreover, there exists an isomorphism $\varphi''$ from $M = \{ 1, -1 \}$ to $T$ taking $-1$ to $s$. The group $W$ is the semi-direct product of $T$ and $P$. In view of the formulas (9) and $\rho \pi^n \rho^{-1} = \pi^{-n}$, $\varphi'$ and $\varphi''$ induce an isomorphism $\varphi$ from $D_m$ to $W$ such that $\varphi(\rho) = s$ and $\varphi(\pi) = p$, and hence $\varphi(\rho') = s'$. The uniqueness of $\varphi$ follows from the fact that $D_m$ is generated by $\{ \rho, \rho' \}$.

(I) There exists a finite sequence $(s_1, \ldots, s_q)$ of elements of S such that $s_1 = s, s_q = s'$ and $s_j s_{j+1}$ is of finite odd order for $1 \leq j < q$.

Let s and s' in S be such that $p = ss'$ is of finite order $2n + 1$. By (9), $sp^{-n} = p^n s$ hence

and $s'$ is conjugate to s.

For all s in S, let $A_s$ be the set of $s' \in S$ satisfying (I). With the hypotheses in (I), the elements $s_j$ and $s_{j+1}$ are conjugate for $1 \leq j < q$ by the above, hence every element $s'$ of $A_s$ is conjugate to s.

Let $f$ be the map from S to $M = \{1, -1\}$ equal to 1 on $A_s$ and to -1 on $S - A_s$. Let $s'$ and $s''$ in S be such that $s's''$ is of finite order m. Then $f(s') f(s'') = 1$ if $s'$ and $s''$ are both in $A_s$ or both in $S - A_s$. In the other case, $f(s') f(s'') = -1$, but m is even. Thus $(f(s') f(s''))^m = 1$ in all cases. Since (W, S) is a Coxeter system, there exists a homomorphism g from W to M inducing f on S. Let $s'$ be a conjugate of s. Since s belongs to the kernel of g, so does $s'$, hence $f(s') = g(s') = 1$ and finally $s' \in A_s$. Q.E.D.

(ii) For $w \in W$, let $U_w$ be the map from R to itself defined by

The map $w \mapsto U_w$ is a homomorphism from W to the group of permutations of R.

(2) Recall that two elements (resp. two subsets) of a group W are said to be conjugate if there exists an inner automorphism of W that transforms one into the other.

For $s \in S$, define a map $U_s$ from $R$ to itself by

where $\delta_{s,t}$ is the Kronecker symbol. It is immediate that $U_s^2 = \mathrm{Id}_R$, which shows that $U_s$ is a permutation of $R$.

Let $s = (s_1, \ldots, s_q)$ be a sequence of elements of $S$. Put $w = s_q \ldots s_1$ and $U_s = U_{s_q} \ldots U_{s_1}$. We shall show, by induction on $q$, that

This is clear for $q = 0, 1$. If $q > 1$, put $s' = (s_1, \ldots, s_{q-1})$ and Using the induction hypothesis, we obtain But $\Phi(s) = (\Phi(s'), {w'}^{-1} s_q w')$ and $n(s, t) = n(s', t) + \delta_{w', -1} s_q w', t$, proving formula (14).

Now let $s, s' \in S$ be such that $p = ss'$ has finite order $m$. Let $s = (s_1, \ldots, s_{2m})$ be the sequence of elements of $S$ defined by $s_j = s$ for $j$ odd and $s_j = s'$ for $j$ even. Then $s_{2m} \ldots s_1 = p^{-m} = 1$ and formula (11) implies that

Since $p$ is of order $m$, the elements $t_1, \ldots, t_m$ are distinct and $t_{j+m} = t_j$ for $1 \leq j \leq m$. For all $t \in T$, the integer $n(s, t)$ is thus equal to 0 or 2 and (14) shows that $U_s = \mathrm{Id}_R$. In other words, $(U_s U_{s'})^m = \mathrm{Id}_R$. Thus, by the definition of Coxeter systems, there exists a homomorphism $w \mapsto U_w$ from $W$ to the group of permutations of $R$ such that $U_s$ is given by the right-hand side of (13). Then $U_w = U_s$ for every sequence $s = (s_1, \ldots, s_q)$ such that $w = s_q \ldots s_1$ and Lemma 1 follows immediately from (14).

Clearly $T_w \subset \{ t_1, \ldots, t_q \}$. Taking $s$ to be reduced, it follows that $\mathrm{Card}(T_w) \leq l(w)$. Moreover, if the $t_i$ are distinct, then $n(s, t)$ is equal to 1 or 0 according to whether $t$ does or does not belong to $\{ t_1, \ldots, t_q \}$. It follows that $T_w = \{ t_1, \ldots, t_q \}$ and that $q = \mathrm{Card}(T_w) \leq l(w)$, which implies that $s$ is reduced. Suppose finally that $t_i = t_j$ with $i < j$. This gives $s_i = us_j u^{-1}$, with $u = s_{i+1} \ldots s_{j-1}$, hence

This shows that $s$ is not a reduced decomposition of $w$.

Let $p$ be the length of $w$ and $w' = sw$. By the Remark of no. 3, $l(w') \equiv l(w) + 1$ mod. 2. The hypothesis $l(w') \leq l(w)$ and the relation

thus leads to $l(w') = p - 1$. Choose a reduced decomposition

of $w'$ and put $s = (s, s'_1, \ldots, s'_{p-1})$ and $\Phi(s') = (t'_1, \ldots, t'_p)$. It is clear that $s'$ is a reduced decomposition of $w$ and that $t'_1 = s$. The elements $t'_1, \ldots, t'_p$ being distinct by Lemma 2, we have $n(s', s) = 1$. Since $w$ is the product of the sequence $s$, we have $n(s, s) \equiv n(s', s)$ mod. 2 by Lemma 1, hence $n(s, s) \neq 0$. Consequently, $s$ is equal to one of the elements $t_j$ of the sequence $\Phi(s)$, hence the lemma.

a) $l(sw) = l(w) + 1$ and $(s, s_1, \ldots, s_q)$ is a reduced decomposition of $sw$.

b) $l(sw) = l(w) - 1$ and there exists an integer $j$ such that $1 \leq j \leq q$, $(s_1, \ldots, s_{j-1}, s_{j+1}, \ldots, s_q)$ is a reduced decomposition of $sw$ and $(s, s_1, \ldots, s_{j-1}, s_{j+1}, \ldots, s_q)$ is a reduced decomposition of $w$.

Put $w' = sw$. By formula (3) of no. 1, we have

We distinguish two cases:

a) $l(w') > l(w)$. Then $l(w') = q + 1$ and $w' = ss_1 \ldots s_q$, so

is a reduced decomposition of $w'$.

b) $l(w') \leq l(w)$. By (E), there exists an integer $j$ such that $1 \leq j \leq q$ and (16) is satisfied. Then $w = ss_1 \ldots s_{j-1} s_{j+1} \ldots s_q$ and hence

Since $q - 1 \leq l(w') \leq q$, it follows that $l(w') = q - 1$ and that $(s_1, \ldots, s_{j-1}, s_{j+1}, \ldots, s_q)$ is a reduced decomposition of $w'$.

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')$.

If $a(s, s') = a(s', s)$ whenever $s \neq s'$ are in S, there exists a map g from W to M such that

for all $w \in W$ and any reduced decomposition $(s_1, \ldots, s_q)$ of w.

For any $w \in W$, let $D_w$ be the set of reduced decompositions of w and $F_w$ the map from $D_w$ to M defined by

We are going to prove by induction on the length of w that $F_w$ is constant, which will establish Prop. 5. The cases $l(w) = 0, 1$ being trivial, we assume that $q \geq 2$ and that our assertion is proved for the elements w with $l(w) < q$. Let w be of length q and $s, s' \in D_w$; by Lemma 4 it suffices to prove that $F_w(s) = F_w(s')$ in cases a) and b) of that lemma.

a) The formula

for $w' = s_1 \ldots s_{q-1}$ and $w'' = s_2 \ldots s_q$ and the induction hypothesis show that $F_w(s) = F_w(s')$ if $s_1 = s'_1$ or $s_q = s'_q$.

b) Suppose that there exist two elements s and s' of S such that $s_j = s'_k = s$ and $s_k = s'_j = s'$ for j odd and k even. It suffices to treat the case $s \neq s'$. The sequences s and s' are then two distinct reduced decompositions of w in the dihedral group generated by s and s'. By the Remark in no. 2, the order m of ss' is necessarily finite and, in the notation of that remark, $s = s_m$ and $s' = s'_m$. Consequently, $F_w(s) = a(s, s')$ and $F_w(s') = a(s', s)$ and hence