# Geodesic Normal Forms and Hecke Algebras for the Complex Reflection Groups
$G(de,e,n)$

Georges Neaime
Fakultät für Mathematik
Universität Bielefeld
<EMAIL_ADDRESS>
(October 22, 2018)

###### Abstract

We establish geodesic normal forms for the general series of complex
reflection groups $G(de,e,n)$ by using the presentations of Corran-Picantin
and Corran-Lee-Lee of $G(e,e,n)$ and $G(de,e,n)$ for $d>1$, respectively. This
requires the elaboration of a combinatorial technique in order to explicitly
determine minimal word representatives of the elements of $G(de,e,n)$. Using
these geodesic normal forms, we construct natural bases for the Hecke algebras
associated with the complex reflection groups $G(e,e,n)$ and $G(d,1,n)$. As an
application, we obtain a new proof of the BMR freeness conjecture for these
groups.

###### Contents

  1. 1 Introduction
  2. 2 Definitions and preliminaries
  3. 3 Geodesic normal forms for $G(de,e,n)$
  4. 4 The Hecke algebras $H(de,e,n)$
  5. 5 Bases for the Hecke algebras $H(e,e,n)$
  6. 6 The case of $H(d,1,n)$

##  1 Introduction

Complex reflection groups are finite groups generated by complex reflections.
Recall that a complex reflection is a linear transformation of finite order
that fixes a hyperplane pointwise. These groups include finite real relection
groups, also known as finite Coxeter groups. It is well known that every
complex reflection group is a direct product of irreducible ones. The
irreducible complex reflection groups have been classified by Shephard and
Todd [19] in 1954. The classification includes the general $3$-parameter
series $G(de,e,n)$ that can be easily described in terms of monomial matrices
and $34$ exceptional groups denoted by $G_{4}$, $G_{5}$, $\cdots$, $G_{37}$.

Broué, Malle and Rouquier [6] managed to attach a complex braid group to each
complex reflection group. This generalizes the notion of Artin-Tits groups
attached to finite Coxeter groups. Extending earlier results in [5], they also
managed to generalize the definition of the (Iwahori-)Hecke algebra for real
reflection groups to arbitrary complex reflection groups by using their
definition of the complex braid group. Actually, the Hecke algebra is defined
as a quotient of the complex braid group algebra by some polynomial relations.
It is believed that nice properties of these objects in the case of real
reflection groups could be extended to the general case of complex reflection
groups. In [6], it was stated a number of important conjectures about the
complex braid groups and the Hecke algebras.

One of these interesting conjectures is the so-called “BMR freeness
conjecture”. It states that the Hecke algebra is a free module of rank equal
to the order of the associated complex reflection group. This property is
valid for the (Iwahori-)Hecke algebra attached to any finite real reflection
group (see [3]), where a basis is constructed from geodesic normal forms in
the finite Coxeter group due to Matsumoto’s property (see [16]). The BMR
freeness conjecture can be easily reduced to the case of irreducible complex
reflection groups. During the past two decades, a proof of this conjecture for
each case of the classification of Shephard and Todd has been established
involving the results of a number of authors. As we are interested in the case
of the general series of complex reflection groups, we mention that this
conjecture has been established for $G(d,1,n)$ (see Ariki-Koike [2] and
Bremke-Malle [4]) and for $G(de,e,n)$ by Ariki (see [1] and Appendix A.2 of
[18]). A list of references for the proof of the BMR freeness conjecture can
be found in the next section.

An important constraint in the proof of this conjecture, and in the theory of
Hecke algebras for complex reflection groups in general, is the failure of an
analogue of Matsumoto’s property. That is, we do not have any canonical basis
of the Hecke algebra. The proof of the BMR freeness conjecture was obtained by
sometimes tedious and lengthy computations in order to explicitly construct
bases for the Hecke algebras. It is then of importance to find nice bases for
these algebras. In this paper, we construct new and natural bases for the
Hecke algebras attached to the complex reflection groups $G(e,e,n)$ and
$G(d,1,n)$.

In order to establish these bases, our attention is firstly shifted to the
complex reflection groups $G(de,e,n)$. We construct geodesic normal forms for
these groups by using the presentations of Corran-Picantin [10] and Corran-
Lee-Lee [9] of $G(e,e,n)$ and $G(de,e,n)$ for $d>1$, respectively. The
geodesic normal forms are very natural and easy to describe. They generalize
our construction in [17] for $G(e,e,n)$ to all the cases of the general series
of complex reflection groups.

We establish that these geodesic normal forms provide bases for the Hecke
algebras attached to $G(e,e,n)$ and $G(d,1,n)$. Since these bases are
constructed from geodesic normal forms in the complex reflection groups, they
are natural bases for the associated Hecke algebras. Note that the geodesic
normal forms for $G(e,e,n)$ have been already used in our previous work [17]
in order to construct intervals in $G(e,e,n)$ that give rise to nice
combinatorial structures (called interval Garside structures) for the
associated complex braid groups.

The article is organized as follows. In Section 2, we provide a basic
background material and recall the BMR freeness conjecture. The geodesic
normal forms for the complex reflection groups $G(de,e,n)$ are constructed in
Section 3, which sets the stage for our later work. The techniques used are
elementary and the associated combinatorial characterizations are very
explicit. In Section 4, the attention shifts to the Hecke algebras. Actually,
we establish nice presentations for the Hecke algebras attached to
$G(de,e,n)$, by using the presentations of Corran-Picantin and Corran-Lee-Lee
of the associated complex braid groups that we recall in the same section. The
remaining part of the article establishes that the geodesic normal forms
constructed in Section 3 provide natural bases for the Hecke algebras
associated with $G(e,e,n)$ and $G(d,1,n)$. Through these constructions, we
also obtain a new proof of the BMR freeness conjecture for these groups. At
the end of Section 5, we explain why we were not able to establish such
natural bases for the Hecke algebras attached to the other cases of the
general series of complex reflection groups.

##  2 Definitions and preliminaries

Let $W$ be a complex reflection group. Let $\mathcal{A}:=\\{Ker(s-1)$ s.t.
$s\in\mathcal{R}\\}$ be the hyperplane arrangement and
$X:=\mathbb{C}^{n}\setminus\bigcup\mathcal{A}$ be the hyperplane complement.
The complex reflection group $W$ acts naturally on $X$. Let $X/W$ be its space
of orbits. The complex braid group $B$ attached to $W$ is defined as follows.
For details about this definition, we refer to [6].

######  Definition 2.1.

The complex braid group attached to $W$ is the fundamental group

$B:=\pi_{1}(X/W).$

Recall that a complex reflection $s\in W$ is called distinguished if its only
nontrivial eigenvalue is $exp(2i\pi/o(s))$, where $o(s)$ denotes the order of
$s$. For the standard notion of braided reflections that we use in the next
definition, the reader may check [6]. We are ready to define the Hecke algebra
associated with $W$ (see [6] and [14]).

######  Definition 2.2.

Let $R=\mathbb{Z}[a_{s,i},a_{s,0}^{-1},0\leq i\leq o(s)-1]$, where s runs over
the distinguished reflections, with the convention $a_{s,i}=a_{s^{\prime},i}$
if $s$ and $s^{\prime}$ are conjugates in $W$. The Hecke algebra $H(W)$
attached to the complex reflection group $W$ is the quotient of the complex
braid group algebra $RB$ by the relations

$\sigma^{o(s)}-a_{s,o(s)-1}\sigma^{o(s)-1}-\cdots-a_{s,0}=0,$

for each braided reflection $\sigma$ associated with $s$.

Note that it is enough to choose one such relation per conjugacy class of
distinguished reflections, as all the corresponding braided reflections are
conjugates in $B$ (see [6]).

The BMR freeness conjecture proposed by Broué, Malle and Rouquier [6] in 1998
states that the Hecke algebra $H(W)$ attached to $W$ is a free $R$-module of
rank equal to the order of $W$. After two decades, the BMR freeness conjecture
is proven through the results of a number of authors. Thus, we have the
following theorem.

######  Theorem 2.3.

The Hecke algebra $H(W)$ is a free $R$-module of rank $|W|$.

The BMR freeness conjecture can be easily reduced to the case where $W$ is
irreducible. It is true for the (Iwahori-)Hecke algebra attached to any finite
Coxeter group (see Lemma 4.4.3 of [11]). Ariki and Koike [2] proved it for the
case of $G(d,1,n)$. Note that a basis for the Hecke algebra associated with
$G(d,1,n)$ is also given in [4]. Ariki defined in [1] a Hecke algebra for
$G(de,e,n)$ by a presentation with generators and relations. He also proved
that it is a free module of rank $|G(de,e,n)|$. The Hecke algebra defined by
Ariki is isomorphic to the Hecke algebra defined by Broué, Malle, and Rouquier
in [6] for $G(de,e,n)$. The details why this is true can be found in Appendix
A.2 of [18]. Hence one gets a proof of Theorem 2.3 for the general series of
complex reflection groups.

Concerning the exceptional complex reflection groups, Marin proved the
conjecture for $G_{4}$, $G_{25}$, $G_{26}$, and $G_{32}$ in [12] and [13].
Marin and Pfeiffer proved it for $G_{12}$, $G_{22}$, $G_{24}$, $G_{27}$,
$G_{29}$, $G_{31}$, $G_{33}$, and $G_{34}$ in [15]. In her PhD thesis and in
the article that followed (see [7] and [8]), Chavli proved the validity of
this conjecture for $G_{5}$, $G_{6}$, $\cdots$, $G_{16}$. Recently, Marin
proved the conjecture for $G_{20}$ and $G_{21}$ (see [14]) and finally
Tsushioka for $G_{17}$, $G_{18}$ and $G_{19}$ (see [20]). Hence we obtain a
proof of Theorem 2.3 for all the cases of irreducible complex reflection
groups.

##  3 Geodesic normal forms for $G(de,e,n)$

This section sets the stage for our later work by establishing a set of
geodesic normal forms for the complex reflection groups $G(de,e,n)$, using the
generating sets introduced by Corran-Picantin [10] and Corran-Lee-Lee [9] for
$G(e,e,n)$ and $G(de,e,n)$ for $d>1$, respectively. The case of $G(e,e,n)$ has
been already done in our previous work (see Section 3 of [17]). We generalize
the combinatorial techniques used there to the case of $G(de,e,n)$ for $d>1$.
We obtain natural and explicit geodesic normal forms for these groups.

###  3.1 Presentations for $G(de,e,n)$

The complex reflection group $G(de,e,n)$ is the group of monomial matrices
whose nonzero entries are $de$-th roots of unity and their product is a $d$-th
root of unity.

Set $d=1$ and let $e\geq 1$ and $n\geq 2$. Corran-Picantin discovered in [10]
a presentation of the complex reflection group $G(e,e,n)$ that is defined as
follows.

######  Definition 3.1.

The complex reflection group $G(e,e,n)$ is defined by a presentation with
generators: $\\{\textbf{t}_{i}\ |\
i\in\mathbb{Z}/e\mathbb{Z}\\}\cup\\{\textbf{s}_{3},\textbf{s}_{4},\cdots,\textbf{s}_{n}\\}$
and relations:

  1. 1.

$\textbf{t}_{i}\textbf{t}_{i-1}=\textbf{t}_{j}\textbf{t}_{j-1}$ for
$i,j\in\mathbb{Z}/e\mathbb{Z}$,

  2. 2.

$\textbf{t}_{i}\textbf{s}_{3}\textbf{t}_{i}=\textbf{s}_{3}\textbf{t}_{i}\textbf{s}_{3}$
for $i\in\mathbb{Z}/e\mathbb{Z}$,

  3. 3.

$\textbf{s}_{j}\textbf{t}_{i}=\textbf{t}_{i}\textbf{s}_{j}$ for
$i\in\mathbb{Z}/e\mathbb{Z}$ and $4\leq j\leq n$,

  4. 4.

$\textbf{s}_{i}\textbf{s}_{i+1}\textbf{s}_{i}=\textbf{s}_{i+1}\textbf{s}_{i}\textbf{s}_{i+1}$
for $3\leq i\leq n-1$,

  5. 5.

$\textbf{s}_{i}\textbf{s}_{j}=\textbf{s}_{j}\textbf{s}_{i}$ for $|i-j|>1$,

  6. 6.

$\textbf{t}_{i}^{2}=1$ for $i\in\mathbb{Z}/e\mathbb{Z}$ and
$\textbf{s}_{j}^{2}=1$ for $3\leq j\leq n$.

The matrices in $G(e,e,n)$ that correspond to the generators of this
presentation are given by $\mathbf{t}_{i}\longmapsto
t_{i}:=\begin{pmatrix}0&\zeta_{e}^{-i}&0\\\ \zeta_{e}^{i}&0&0\\\
0&0&I_{n-2}\\\ \end{pmatrix}$ for $0\leq i\leq e-1$, and
$\mathbf{s}_{j}\longmapsto s_{j}:=\begin{pmatrix}I_{j-2}&0&0&0\\\ 0&0&1&0\\\
0&1&0&0\\\ 0&0&0&I_{n-j}\\\ \end{pmatrix}$ for $3\leq j\leq n$. To avoid
confusion, we use regular letters for matrices and bold letters for words over
the generating set of the presentation of Corran-Picantin.

This presentation can be described by the following diagram. It is
interpreted, where possible, as a Coxeter diagram. In addition, the dashed
circle describes Relation $1$ of Definition 3.1.

2 $\mathbf{t}_{0}$2 $\mathbf{t}_{1}$2 $\mathbf{t}_{2}$2 $\mathbf{t}_{i}$2
$\mathbf{t}_{e-1}$2 $\mathbf{s}_{3}$2 $\mathbf{s}_{4}$2 $\mathbf{s}_{n-1}$2
$\mathbf{s}_{n}$$\cdots$ Figure 1: Diagram for the presentation of Corran-
Picantin of $G(e,e,n)$.

######  Remark 3.2.

  1. 1.

For $e=1$ and $n\geq 2$, we obtain the classical presentation of the symmetric
group $S_{n}$.

  2. 2.

For $e=2$ and $n\geq 2$, we obtain the classical presentation of the Coxeter
group of type $D_{n}$.

The attention shifts now to the case $d>1$. Let $d>1$, $e\geq 1$ and $n\geq
2$. There exists a presentation of the complex reflection group $G(de,e,n)$
discovered by Corran-Lee-Lee in [9].

######  Definition 3.3.

The complex reflection group $G(de,e,n)$ is defined by a presentation with set
of generators: $\mathbf{X}=\\{\mathbf{z}\\}\cup\\{\mathbf{t}_{i}\ |\
i\in\mathbb{Z}/de\mathbb{Z}\\}\cup\\{\mathbf{s}_{3},\mathbf{s}_{4},\cdots,\mathbf{s}_{n}\\}$
and relations as follows.

  1. 1.

$\mathbf{z}\mathbf{t}_{i}=\mathbf{t}_{i-e}\mathbf{z}$ for
$i\in\mathbb{Z}/de\mathbb{Z}$,

  2. 2.

$\mathbf{z}\mathbf{s}_{j}=\mathbf{s}_{j}\mathbf{z}$ for $3\leq j\leq n$,

  3. 3.

$\mathbf{t}_{i}\mathbf{t}_{i-1}=\mathbf{t}_{j}\mathbf{t}_{j-1}$ for
$i,j\in\mathbb{Z}/de\mathbb{Z}$,

  4. 4.

$\mathbf{t}_{i}\mathbf{s}_{3}\mathbf{t}_{i}=\mathbf{s}_{3}\mathbf{t}_{i}\mathbf{s}_{3}$
for $i\in\mathbb{Z}/de\mathbb{Z}$,

  5. 5.

$\mathbf{s}_{j}\mathbf{t}_{i}=\mathbf{t}_{i}\mathbf{s}_{j}$ for
$i\in\mathbb{Z}/de\mathbb{Z}$ and $4\leq j\leq n$,

  6. 6.

$\mathbf{s}_{i}\mathbf{s}_{i+1}\mathbf{s}_{i}=\mathbf{s}_{i+1}\mathbf{s}_{i}\mathbf{s}_{i+1}$
for $3\leq i\leq n-1$,

  7. 7.

$\mathbf{s}_{i}\mathbf{s}_{j}=\mathbf{s}_{j}\mathbf{s}_{i}$ for $|i-j|>1$,

  8. 8.

$\mathbf{z}^{d}=1$, $\mathbf{t}_{i}^{2}=1$ for $i\in\mathbb{Z}/de\mathbb{Z}$,
and $\mathbf{s}_{j}^{2}=1$ for $3\leq j\leq n$.

The generators of this presentation correspond to the following $n\times n$
matrices. The generator $\mathbf{t}_{i}$ is represented by the matrix
$t_{i}=\begin{pmatrix}0&\zeta_{de}^{-i}&0\\\ \zeta_{de}^{i}&0&0\\\
0&0&I_{n-2}\\\ \end{pmatrix}$ for $i\in\mathbb{Z}/de\mathbb{Z}$, $\mathbf{z}$
by the diagonal matrix $z=Diag(\zeta_{d},1,\cdots,1)$ where
$\zeta_{d}=exp(2i\pi/d)$, and $\mathbf{s}_{j}$ by the transposition matrix
$s_{j}=(j-1,j)$ for $3\leq j\leq n$. To avoid confusion, we use regular
letters for matrices and bold letters for words over $\mathbf{X}$. Denote by
$X$ the set $\\{z,t_{0},t_{1},\cdots,t_{de-1},s_{3},\cdots,s_{n}\\}$.

This presentation can be described by the following diagram. This diagram is
again to be read, where possible, as a Coxeter diagram. In addition, the
dashed circle describes Relation $3$ of Definition 3.3 and the curved arrow
above the node corresponding to $\mathbf{z}$ describes Relation $1$.

$d$$\mathbf{z}$$2$$\mathbf{t}_{0}$$2$$\mathbf{t}_{1}$$2$$\mathbf{t}_{2}$$2$$\mathbf{t}_{i}$$2$$\mathbf{t}_{de-1}$$2$$\mathbf{s}_{3}$$2$$\mathbf{s}_{4}$$2$$\mathbf{s}_{n-1}$$2$$\mathbf{s}_{n}$$\cdots$
Figure 2: Diagram for the presentation of Corran-Lee-Lee of $G(de,e,n)$.

######  Proposition 3.4.

Let $e=1$. The presentation given in Definition 3.3 is equivalent to the
classical presentation of the complex reflection group $G(d,1,n)$ that can be
described by the following well-known diagram.

$d$$\mathbf{z}$$2$$\mathbf{s}_{2}$$2$$\mathbf{s}_{3}$$2$$\mathbf{s}_{n-1}$$2$$\mathbf{s}_{n}$
Figure 3: Diagram for the presentation of $G(d,1,n)$.

###### Proof.

Let $e=1$. Relation $1$ of Definition 3.3 becomes
$\mathbf{z}\mathbf{t}_{1}=\mathbf{t}_{0}\mathbf{z}$, that is
$\mathbf{t}_{1}=\mathbf{z}^{-1}\mathbf{t}_{0}\mathbf{z}$. Also by Relation $3$
of Definition 3.3, we have
$\mathbf{t}_{k}=\mathbf{z}^{-k}\mathbf{t}_{0}\mathbf{z}^{k}$ for $1\leq k\leq
d-1$. If we remove $\mathbf{t}_{1},\cdots,\mathbf{t}_{d-1}$ from the set of
generators and replace every occurrence of $\mathbf{t}_{k}$ in the defining
relations with $\mathbf{z}^{-k}\mathbf{t}_{0}\mathbf{z}^{k}$ for $1\leq k\leq
d-1$, we recover the classical presentation of the complex reflection group
$G(d,1,n)$. Note that we replace $\mathbf{t}_{0}$ by $\mathbf{s}_{2}$ in the
set of generators of this presentation.

∎

######  Remark 3.5.

For $d=2$, the presentation described by the diagram of Figure 3 corresponds
to the presentation of the Coxeter group of type $B_{n}$.

From now on, we set the following convention.

######  Convention 3.6.

A decreasing-index expression of the form
$\mathbf{s}_{i}\mathbf{s}_{i-1}\cdots\mathbf{s}_{i^{\prime}}$ is the empty
word when $i<i^{\prime}$ and an increasing-index expression of the form
$\mathbf{s}_{i}\mathbf{s}_{i+1}\cdots\mathbf{s}_{i^{\prime}}$ is the empty
word when $i>i^{\prime}$. Similarly, in $G(de,e,n)$, a decreasing-index
product of the form $s_{i}s_{i-1}\cdots s_{i^{\prime}}$ is equal to $I_{n}$
when $i<i^{\prime}$ and an increasing-index product of the form
$s_{i}s_{i+1}\cdots s_{i^{\prime}}$ is equal to $I_{n}$ when $i>i^{\prime}$,
where $I_{n}$ is the identity $n\times n$ matrix. We also set that
$\mathbf{z}^{0}$ is the empty word.

###  3.2 Minimal word representatives

Consider the complex reflection group $G(de,e,n)$ with $d>1$, $e>1$ and $n\geq
2$. The case of $G(d,1,n)$ will be established in the next subsection. Recall
that $\mathbf{X}$ denotes the set of the generators of the presentation of
Corran-Lee-Lee of $G(de,e,n)$ and $X$ the set of the corresponding matrices.
Our aim is to represent each element of $G(de,e,n)$ by a reduced word over
$\mathbf{X}$. This requires the elaboration of a combinatorial technique in
order to determine a reduced expression decomposition over $\mathbf{X}$ of an
element of $G(de,e,n)$.

We introduce Algorithm 1 below (see page 8) that produces a word $R\\!E(w)$
over $\mathbf{X}$ for a given element $w$ in $G(de,e,n)$. This algorithm
generalizes the one introduced in Section 3 of our previous work [17] that
corresponds to the case of $G(e,e,n)$. Note that we use Convention 3.6 in the
elaboration of the algorithm. Later on, we prove that its output $R\\!E(w)$ is
a reduced expression over $\mathbf{X}$ of $w\in G(de,e,n)$.

Let $w_{n}:=w\in G(de,e,n)$. For $i$ from $n$ to $2$, the $i$-th step of
Algorithm 1 transforms the block diagonal matrix
$\left(\begin{array}[]{c|c}w_{i}&0\\\ \hline\cr 0&I_{n-i}\end{array}\right)$
into a block diagonal matrix $\left(\begin{array}[]{c|c}w_{i-1}&0\\\ \hline\cr
0&I_{n-i+1}\end{array}\right)\in G(de,e,n)$. Actually, for $2\leq i\leq n$,
there exists a unique $c$ with $1\leq c\leq n$ such that $w_{i}[i,c]\neq 0$.
At each step $i$ of Algorithm 1, if $w_{i}[i,c]=1$, we shift it into the
diagonal position $[i,i]$ by right multiplication by transpositions. If
$w_{i}[i,c]\neq 1$, we shift it into the first column by right multiplication
by transpositions, transform it into $1$ by right multiplication by an element
of $\\{t_{0},t_{1},\cdots,t_{de-1}\\}$, and then shift the $1$ obtained into
the diagonal position $[i,i]$. Finally, we get $w_{1}=\zeta_{d}^{k}$ for some
$0\leq k\leq d-1$, where $\zeta_{d}^{k}$ is equal to the product of the
nonzero entries of $w$. By multiplying $\left(\begin{array}[]{c|c}w_{1}&0\\\
\hline\cr 0&I_{n-1}\end{array}\right)$ on the right by $z^{-k}$, we get the
identity matrix $I_{n}$.

Input : $w$, a matrix in $G(de,e,n)$ with $d>1$, $e>1$, and $n\geq 2$.

Output : $R\\!E(w)$, a word over $\mathbf{X}$.

Local variables: $w^{\prime}$, $R\\!E(w)$, $i$, $U$, $V$, $c$, $k$.

Initialisation: $U:=[1,\zeta_{de},\zeta_{de}^{2},...,\zeta_{de}^{e-1}]$,
$V:=[1,\zeta_{d},\zeta_{d}^{2},\cdots,\zeta_{d}^{d-1}]$, $s_{2}:=t_{0}$,
$\mathbf{s}_{2}:=\mathbf{t}_{0}$, $R\\!E(w):=\varepsilon$: the empty word,
$w^{\prime}:=w$.

for  _$i$ from $n$ down to $2$_ do

$c:=1$; $k:=0$;

while  _$w^{\prime}[i,c]=0$_ do

$c:=c+1$;

end while

#Then $w^{\prime}[i,c]$ is the root of unity on the row $i$;

while  _$U[k+1]\neq w^{\prime}[i,c]$_ do

$k:=k+1$;

end while

#Then $w^{\prime}[i,c]=\zeta_{de}^{k}$.

if  _$k\neq 0$_ then

$w^{\prime}:=w^{\prime}s_{c}s_{c-1}\cdots s_{3}s_{2}t_{k}$; #Then
$w^{\prime}[i,2]=1$;

$R\\!E(w):=\mathbf{t}_{k}\mathbf{s}_{2}\mathbf{s}_{3}\cdots\mathbf{s}_{c}R\\!E(w)$;

$c:=2$;

end if

$w^{\prime}:=w^{\prime}s_{c+1}\cdots s_{i-1}s_{i}$; #Then $w^{\prime}[i,i]=1$;

$R\\!E(w):=\mathbf{s}_{i}\mathbf{s}_{i-1}\cdots\mathbf{s}_{c+1}R\\!E(w)$;

end for

$k:=0$;

while  _$V[k+1]\neq w^{\prime}[1,1]$_ do

$k:=k+1$;

end while

#Then $w^{\prime}[1,1]=\zeta_{d}^{k}$;

$w^{\prime}:=w^{\prime}z^{-k}$; #Then $w^{\prime}=I_{n}$;

if  _$k\neq 0$_ then

$R\\!E(w)=\mathbf{z}^{k}R\\!E(w)$;

end if

Return $R\\!E(w)$;

Algorithm 1 A word over $\mathbf{X}$ corresponding to a matrix $w\in
G(de,e,n)$.

######  Example 3.7.

We apply Algorithm 1 to $w:=\begin{pmatrix}\zeta_{9}&0&0&0\\\ 0&0&1&0\\\
0&0&0&\zeta_{9}\\\ 0&\zeta_{9}&0&0\\\ \end{pmatrix}$ $\in G(9,3,4)$.
Step $1$ $(i=4,k=0,c=1)$:
$w^{\prime}:=ws_{2}=\begin{pmatrix}0&\zeta_{9}&0&0\\\ 0&0&1&0\\\
0&0&0&\zeta_{9}\\\ \zeta_{9}&0&0&0\\\ \end{pmatrix}$, then
$w^{\prime}:=w^{\prime}t_{1}=\begin{pmatrix}\zeta_{9}^{2}&0&0&0\\\ 0&0&1&0\\\
0&0&0&\zeta_{9}\\\ 0&1&0&0\\\ \end{pmatrix}$, then
$w^{\prime}:=w^{\prime}s_{3}s_{4}=\begin{pmatrix}\zeta_{9}^{2}&0&0&0\\\
0&1&0&0\\\ 0&0&\boxed{\zeta_{9}}&0\\\ 0&0&0&\mathbf{1}\\\ \end{pmatrix}$.
Step $2$ $(i=3,k=1,c=3)$:
$w^{\prime}:=w^{\prime}s_{3}s_{2}=\begin{pmatrix}0&\zeta_{9}^{2}&0&0\\\
0&0&1&0\\\ \zeta_{9}&0&0&0\\\ 0&0&0&1\\\ \end{pmatrix}$, then
$w^{\prime}:=w^{\prime}t_{1}=\begin{pmatrix}\zeta_{9}^{3}&0&0&0\\\ 0&0&1&0\\\
0&1&0&0\\\ 0&0&0&1\\\ \end{pmatrix}$, then
$w^{\prime}:=w^{\prime}s_{3}=\begin{pmatrix}\zeta_{9}^{3}&0&0&0\\\
0&\boxed{1}&0&0\\\ 0&0&\mathbf{1}&0\\\ 0&0&0&1\\\ \end{pmatrix}$.
Step $3$ $(i=2,k=0,c=2)$:
$w^{\prime}=\begin{pmatrix}\boxed{\zeta_{9}^{3}}&0&0&0\\\ 0&\mathbf{1}&0&0\\\
0&0&1&0\\\ 0&0&0&1\\\ \end{pmatrix}=\begin{pmatrix}\boxed{\zeta_{3}}&0&0&0\\\
0&\mathbf{1}&0&0\\\ 0&0&1&0\\\ 0&0&0&1\\\ \end{pmatrix}$.
Step $4$ $(k=1)$: $w^{\prime}:=w^{\prime}z^{-1}=I_{4}$.
Hence
$R\\!E(w)=\mathbf{z}\mathbf{s}_{3}\mathbf{t}_{1}\mathbf{s}_{2}\mathbf{s}_{3}\mathbf{s}_{4}\mathbf{s}_{3}\mathbf{t}_{1}\mathbf{s}_{2}=\mathbf{z}\mathbf{s}_{3}\mathbf{t}_{1}\mathbf{t}_{0}\mathbf{s}_{3}\mathbf{s}_{4}\mathbf{s}_{3}\mathbf{t}_{1}\mathbf{t}_{0}$
_(since $\mathbf{s}_{2}=\mathbf{t}_{0}$)_.

The next lemma follows immediately from Algorithm 1. It explains how we can
easily obtain the blocks defined in the algorithm.

######  Lemma 3.8.

For $2\leq i\leq n$, suppose $w_{i}[i,c]\neq 0$. The block $w_{i-1}$ is
obtained by

  * •

removing the row $i$ and the column $c$ from $w_{i}$, then by

  * •

multiplying the first column of the new matrix by $w_{i}[i,c]$.

Moreover, if we denote by $a_{i}$ the unique nonzero entry on the row $i$ of
$w$, we have $w_{1}=\displaystyle\prod_{i=1}^{n}a_{i}=\zeta_{d}^{k}$ for
$0\leq k\leq d-1$.

######  Example 3.9.

Let $w$ be as in Example 3.7, where $n=4$. The block $w_{3}$ is obtained by
removing the row number 4 and the second column from $w_{4}=w$, to obtain
$\begin{pmatrix}\zeta_{9}&0&0\\\ 0&1&0\\\ 0&0&\zeta_{9}\\\ \end{pmatrix}$,
then by multiplying the first column of this matrix by $\zeta_{9}$. The same
can be said for the other block $w_{2}$. Finally, the block $w_{1}$ is equal
to $\zeta_{3}$ which corresponds to the product of the nonzero entries of $w$.

######  Definition 3.10.

Let $1\leq i\leq n$. Let $w_{i}[i,c]\neq 0$ for $1\leq c\leq i$.

  * •

If $w_{1}=\zeta_{d}^{k}$ with $0\leq k\leq d-1$, we define $R\\!E_{1}(w)$ to
be the word $\mathbf{z}^{k}$.

  * •

If $w_{i}[i,c]=1$, we define $R\\!E_{i}(w)$ to be the word
$\mathbf{s}_{i}\mathbf{s}_{i-1}\cdots\mathbf{s}_{c+1}$ (decreasing-index
expression).

  * •

If $w_{i}[i,c]=\zeta_{de}^{k}$ with $k\neq 0$, we define $R\\!E_{i}(w)$ to be
the word
$\mathbf{s}_{i}\cdots\mathbf{s}_{3}\mathbf{t}_{k}$ if $c=1$,
$\mathbf{s}_{i}\cdots\mathbf{s}_{3}\mathbf{t}_{k}\mathbf{t}_{0}$ if $c=2$,
$\mathbf{s}_{i}\cdots\mathbf{s}_{3}\mathbf{t}_{k}\mathbf{t}_{0}\mathbf{s}_{3}\cdots\mathbf{s}_{c}$
if $c\geq 3$.

The output $R\\!E(w)$ of Algorithm 1 is a concatenation of the words
$R\\!E_{1}(w)$, $R\\!E_{2}(w)$, $\cdots$, and $R\\!E_{n}(w)$ obtained at each
step $i$ from $n$ to $1$ of Algorithm 1. Then, we have
$R\\!E(w)=R\\!E_{1}(w)R\\!E_{2}(w)\cdots R\\!E_{n}(w)$.

######  Example 3.11.

Let $w$ be defined as in Example 3.7. We have

$R\\!E(w)=\underset{R\\!E_{1}(w)}{\underbrace{\mathbf{z}}}\hskip
5.69046pt\underset{R\\!E_{3}(w)}{\underbrace{\mathbf{s}_{3}\mathbf{t}_{1}\mathbf{t}_{0}\mathbf{s}_{3}}}\hskip
5.69046pt\underset{R\\!E_{4}(w)}{\underbrace{\mathbf{s}_{4}\mathbf{s}_{3}\mathbf{t}_{1}\mathbf{t}_{0}}}.$

In this example, $R\\!E_{2}(w)$ is the empty word.

######  Proposition 3.12.

Let $w\in G(de,e,n)$. The word $R\\!E(w)$ given by Algorithm 1 is a word
representative over $\mathbf{X}$ of $w\in G(de,e,n)$.

###### Proof.

Let $w\in G(de,e,n)$ such that the product of all the nonzero entries of $w$
is equal to $\zeta_{d}^{k}$ for some $0\leq k\leq d-1$. Algorithm 1 transforms
the matrix $w$ into $I_{n}$ by multiplying it on the right by elements of $X$.
We get $wx_{1}\cdots x_{r-1}x_{r}=I_{n}$, where $x_{1},\cdots,x_{r-1}$ are
elements of $X\setminus\\{z\\}$ and $x_{r}=z^{-k}$. Hence
$w=x_{r}^{-1}x_{r-1}^{-1}\cdots x_{1}^{-1}=z^{k}x_{r-1}\cdots x_{1}$ since
$x_{i}^{2}=1$ for $1\leq i\leq r-1$. The output $R\\!E(w)$ of Algorithm 1 is
$R\\!E(w)=\mathbf{z}^{k}\mathbf{x}_{r-1}\cdots\mathbf{x}_{1}$. Hence it is a
word representative over $\mathbf{X}$ of $w\in G(de,e,n)$.

∎

The following proposition will prepare us to prove that the output of
Algorithm 1 is a reduced expression over $\mathbf{X}$ of a given element $w\in
G(de,e,n)$.

######  Proposition 3.13.

Let $w$ be an element of $G(de,e,n)$. For all $x\in X$, we have

$\boldsymbol{\ell}(R\\!E(xw))\leq\boldsymbol{\ell}(R\\!E(w))+1.$

###### Proof.

For $1\leq i\leq n$, there exists a unique $c_{i}$ such that $w[i,c_{i}]\neq
0$. We denote $w[i,c_{i}]$ by $a_{i}$. We have
$\displaystyle\prod_{i=1}^{n}a_{i}=\zeta_{d}^{k}$ for some $0\leq k\leq d-1$.

Case 1: Suppose $x=s_{i}$ for $3\leq i\leq n$.

A similar case is done in our previous work [17]. We get $(a)$, $(b)$,
$(a^{\prime})$ and $(b^{\prime})$ as in the proof of Proposition 3.11 (Case 1)
in [17]. For completeness, we include this part of the proof in this article.

Set $w^{\prime}:=s_{i}w$. Since the left multiplication by the matrix $x$
exchanges the rows $i-1$ and $i$ of $w$ and the other rows remain the same, by
Definition 3.10 and Lemma 3.8, we have:
$R\\!E_{i+1}(xw)R\\!E_{i+2}(xw)\cdots
R\\!E_{n}(xw)=R\\!E_{i+1}(w)R\\!E_{i+2}(w)\cdots R\\!E_{n}(w)$ and
$R\\!E_{2}(xw)R\\!E_{3}(xw)\cdots
R\\!E_{i-2}(xw)=R\\!E_{2}(w)R\\!E_{3}(w)\cdots R\\!E_{i-2}(w)$.
Then, in order to prove our property, we should compare
$\boldsymbol{\ell}_{1}:=\boldsymbol{\ell}(R\\!E_{i-1}(w)R\\!E_{i}(w))$ and
$\boldsymbol{\ell}_{2}:=\boldsymbol{\ell}(R\\!E_{i-1}(xw)R\\!E_{i}(xw))$.

Suppose $c_{i-1}<c_{i}$, by Lemma 3.8, the rows $i-1$ and $i$ of the blocks
$w_{i}$ and $w^{\prime}_{i}$ are of the form:

$w_{i}$ : |  | $i$$i-1$$..$$c$$..$$c^{\prime}$$..$$i$$b_{i-1}$$a_{i}$
---|---|---
$w^{\prime}_{i}$ : |  | $i$$i-1$$..$$c$$..$$c^{\prime}$$..$$i$$b_{i-1}$$a_{i}$

with $c<c^{\prime}$ and where we write $b_{i-1}$ instead of $a_{i-1}$ since
$a_{i-1}$ may change when applying Algorithm 1 if $c_{i-1}=1$, that is
$a_{i-1}$ on the first column of $w$ (see the second item of Lemma 3.8).

We will discuss different cases depending on the values of $a_{i}$ and
$b_{i-1}$.

  * •

Suppose $a_{i}=1$.

    * –

If $b_{i-1}=1$,
we have
$R\\!E_{i}(w)=\boldsymbol{s}_{i}\cdots\boldsymbol{s}_{c^{\prime}+2}\boldsymbol{s}_{c^{\prime}+1}$
and
$R\\!E_{i-1}(w)=\boldsymbol{s}_{i-1}\cdots\boldsymbol{s}_{c+2}\boldsymbol{s}_{c+1}$.
Furthermore, we have
$R\\!E_{i}(xw)=\boldsymbol{s}_{i}\cdots\boldsymbol{s}_{c+2}\boldsymbol{s}_{c+1}$
and
$R\\!E_{i-1}(xw)=\boldsymbol{s}_{i-1}\cdots\boldsymbol{s}_{c^{\prime}+1}\boldsymbol{s}_{c^{\prime}}$.
It follows that
$\boldsymbol{\ell}_{1}=((i-1)-(c+1)+1)+(i-(c^{\prime}+1)+1)=2i-c-c^{\prime}-1$
and $\boldsymbol{\ell}_{2}=((i-1)-c^{\prime}+1)+(i-(c+1)+1)=2i-c-c^{\prime}$
hence $\boldsymbol{\ell}_{2}=\boldsymbol{\ell}_{1}+1$.

    * –

If $b_{i-1}=\zeta_{de}^{k}$ with $1\leq k\leq de-1$,
we have
$R\\!E_{i}(w)=\boldsymbol{s}_{i}\cdots\boldsymbol{s}_{c^{\prime}+2}\boldsymbol{s}_{c^{\prime}+1}$
and
$R\\!E_{i-1}(w)=\boldsymbol{s}_{i-1}\cdots\boldsymbol{s}_{3}\boldsymbol{t}_{k}\boldsymbol{t}_{0}\boldsymbol{s}_{3}\cdots\boldsymbol{s}_{c}$.
Furthermore, we have
$R\\!E_{i}(xw)=\boldsymbol{s}_{i}\cdots\boldsymbol{s}_{3}\boldsymbol{t}_{k}\boldsymbol{t}_{0}\boldsymbol{s}_{3}\cdots\boldsymbol{s}_{c}$
and $R\\!E_{i-1}(xw)=\boldsymbol{s}_{i-1}\cdots\boldsymbol{s}_{c^{\prime}}$.
It follows that
$\boldsymbol{\ell}_{1}=(((i-1)-3+1)+2+(c-3+1))+(i-(c^{\prime}+1)+1)=2i+c-c^{\prime}-3$
and
$\boldsymbol{\ell}_{2}=((i-1)-c^{\prime}+1)+((i-3+1)+2+(c-3+1))=2i+c-c^{\prime}-2$
hence $\boldsymbol{\ell}_{2}=\boldsymbol{\ell}_{1}+1$.

It follows that

if $a_{i}=1$, then
$\boldsymbol{\ell}(R\\!E(s_{i}w))=\boldsymbol{\ell}(R\\!E(w))+1.\hskip
28.45274pt(a)$

  * •

Suppose now that $a_{i}=\zeta_{de}^{k}$ with $1\leq k\leq de-1$.

    * –

If $b_{i-1}=1$,
we have
$R\\!E_{i}(w)=\boldsymbol{s}_{i}\cdots\boldsymbol{s}_{3}\boldsymbol{t}_{k}\boldsymbol{t}_{0}\boldsymbol{s}_{3}\cdots\boldsymbol{s}_{c^{\prime}}$
and $R\\!E_{i-1}(w)=\boldsymbol{s}_{i-1}\cdots\boldsymbol{s}_{c+1}$.
Also, we have $R\\!E_{i}(xw)=\boldsymbol{s}_{i}\cdots\boldsymbol{s}_{c+1}$ and
$R\\!E_{i-1}(xw)=\boldsymbol{s}_{i-1}\cdots\boldsymbol{s}_{3}\boldsymbol{t}_{k}\boldsymbol{t}_{0}\boldsymbol{s}_{3}\cdots\boldsymbol{s}_{c^{\prime}-1}$.
It follows that
$\boldsymbol{\ell}_{1}=((i-1)-(c+1)-1)+((i-3+1)+2+(c^{\prime}-3+1))=2i-c+c^{\prime}-5$
and
$\boldsymbol{\ell}_{2}=(((i-1)-3+1)+2+((c^{\prime}-1)-3+1))+(i-(c+1)-1)=2i-c+c^{\prime}-6$
hence $\boldsymbol{\ell}_{2}=\boldsymbol{\ell}_{1}-1$.

    * –

If $b_{i-1}=\zeta_{de}^{k^{\prime}}$ with $1\leq k^{\prime}\leq de-1$,
we have
$R\\!E_{i}(w)=\boldsymbol{s}_{i}\cdots\boldsymbol{s}_{3}\boldsymbol{t}_{k}\boldsymbol{t}_{0}\boldsymbol{s}_{3}\cdots\boldsymbol{s}_{c^{\prime}}$
and
$R\\!E_{i-1}(w)=\boldsymbol{s}_{i-1}\cdots\boldsymbol{s}_{3}\boldsymbol{t}_{k^{\prime}}\boldsymbol{t}_{0}\boldsymbol{s}_{3}\cdots\boldsymbol{s}_{c}$.
Also, we have
$R\\!E_{i}(xw)=\boldsymbol{s}_{i}\cdots\boldsymbol{s}_{3}\boldsymbol{t}_{k^{\prime}}\boldsymbol{t}_{0}\boldsymbol{s}_{3}\cdots\boldsymbol{s}_{c}$
and
$R\\!E_{i-1}(xw)=\boldsymbol{s}_{i-1}\cdots\boldsymbol{s}_{3}\boldsymbol{t}_{k}\boldsymbol{t}_{0}\boldsymbol{s}_{3}\cdots\boldsymbol{s}_{c^{\prime}-1}$.
It follows that
$\boldsymbol{\ell}_{1}=((i-1)-3+1)+2+(c-3+1)+(i-3+1)+2+(c^{\prime}-3+1)=2i+c+c^{\prime}-5$
and
$\boldsymbol{\ell}_{2}=((i-1)-3+1)+2+((c^{\prime}-1)-3+1)+(i-3+1)+2+(c-3+1)=2i+c+c^{\prime}-6$
hence $\boldsymbol{\ell}_{2}=\boldsymbol{\ell}_{1}-1$.

It follows that

if $a_{i}\neq 1$, then
$\boldsymbol{\ell}(R\\!E(s_{i}w))=\boldsymbol{\ell}(R\\!E(w))-1.\hskip
28.45274pt(b)$

Suppose, on the other hand, $c_{i-1}>c_{i}$. Recall that $w^{\prime}=s_{i}w$.
If $w^{\prime}[i-1,c^{\prime}_{i-1}]$ and $w^{\prime}[i,c^{\prime}_{i}]$
denote the nonzero entries of $w^{\prime}$ on the rows $i-1$ and $i$,
respectively, we have $w^{\prime}[i-1,c^{\prime}_{i-1}]=a_{i}$ and
$w^{\prime}[i,c^{\prime}_{i}]=a_{i-1}$. For $w^{\prime}$, we have
$c^{\prime}_{i-1}<c^{\prime}_{i}$, in which case the preceding analysis would
give:

if $a_{i-1}=1$, then
$\boldsymbol{\ell}(R\\!E(s_{i}(s_{i}w)))=\boldsymbol{\ell}(R\\!E(s_{i}w))+1$,

if $a_{i-1}\neq 1$, then
$\boldsymbol{\ell}(R\\!E(s_{i}(s_{i}w)))=\boldsymbol{\ell}(R\\!E(s_{i}w))-1$.

Hence, since $s_{i}^{2}=1$, we get the following:

if $a_{i-1}=1$, then
$\boldsymbol{\ell}(R\\!E(s_{i}w))=\boldsymbol{\ell}(R\\!E(w))-1.\hskip
28.45274pt(a^{\prime})$,

if $a_{i-1}\neq 1$, then
$\boldsymbol{\ell}(R\\!E(s_{i}w))=\boldsymbol{\ell}(R\\!E(w))+1.\hskip
28.45274pt(b^{\prime})$.

Case 2: Suppose $x=t_{i}$ for $0\leq i\leq de-1$.

Set $w^{\prime}:=t_{i}w$. By the left multiplication by $t_{i}$, we have that
the last $n-2$ rows of $w$ and $w^{\prime}$ are the same. Hence, by Definition
3.10 and Lemma 3.8, we have:
$R\\!E_{3}(xw)R\\!E_{4}(xw)\cdots R\\!E_{n}(xw)=R\\!E_{3}(w)R\\!E_{4}(w)\cdots
R\\!E_{n}(w)$. In order to prove our property in this case, we should compare
$\boldsymbol{\ell}_{1}:=\boldsymbol{\ell}(R\\!E_{1}(w)R\\!E_{2}(w))$ and
$\boldsymbol{\ell}_{2}:=\boldsymbol{\ell}(R\\!E_{1}(xw)R\\!E_{2}(xw))$.

  * •

Consider the case where $c_{1}<c_{2}$.

Since $c_{1}<c_{2}$, by Lemma 3.8, the blocks $w_{2}$ and $w^{\prime}_{2}$ are
of the form:

$w_{2}=\begin{pmatrix}b_{1}&0\\\ 0&a_{2}\\\ \end{pmatrix}$ and
$w^{\prime}_{2}=\begin{pmatrix}0&\zeta_{de}^{-i}a_{2}\\\
\zeta_{de}^{i}b_{1}&0\\\ \end{pmatrix}$ with $b_{1}$ instead of $a_{1}$ since
$a_{1}$ may change when applying Algorithm 1 if $c_{1}=1$.

    * –

Suppose $a_{2}=1$,
we have $b_{1}=\zeta_{d}^{k}$ hence $\boldsymbol{\ell}_{1}=k$. We also have
$R\\!E_{2}(xw)=\boldsymbol{t}_{i+ke}$ and $R\\!E_{1}(xw)=\mathbf{z}^{k}$.
Hence we get $\boldsymbol{\ell}_{2}=k+1$. It follows that when $c_{1}<c_{2}$,

if $a_{2}=1$, then
$\boldsymbol{\ell}(R\\!E(t_{i}w))=\boldsymbol{\ell}(R\\!E(w))+1.\hskip
28.45274pt(c)$

    * –

Suppose $a_{2}=\zeta_{de}^{k^{\prime}}$ with $1\leq k^{\prime}\leq de-1$,
we have $b_{1}=\zeta_{de}^{ke-k^{\prime}}$. We get
$R\\!E_{2}(w)=\boldsymbol{t}_{k^{\prime}}\boldsymbol{t}_{0}$ and
$R\\!E_{1}(w)=\mathbf{z}^{k}$. Thus, $\boldsymbol{\ell}_{1}=k+2$. We also get
$R\\!E_{2}(xw)=\boldsymbol{t}_{ke+i-k^{\prime}}$ and
$R\\!E_{1}(xw)=\mathbf{z}^{k}$. Thus, $\boldsymbol{\ell}_{2}=k+1$. It follows
that when $c_{1}<c_{2}$,

if $a_{2}\neq 1$, then
$\boldsymbol{\ell}(R\\!E(t_{i}w))=\boldsymbol{\ell}(R\\!E(w))-1.\hskip
28.45274pt(d)$

  * •

Now, consider the case where $c_{1}>c_{2}$.

Since $c_{1}>c_{2}$, by Lemma 3.8, the blocks $w_{2}$ and $w^{\prime}_{2}$ are
of the form:

$w_{2}=\begin{pmatrix}0&a_{1}\\\ b_{2}&0\\\ \end{pmatrix}$ and
$w^{\prime}_{2}=\begin{pmatrix}\zeta_{de}^{-i}b_{2}&0\\\
0&\zeta_{de}^{i}a_{1}\\\ \end{pmatrix}$ with $b_{2}$ instead of $a_{2}$ since
$a_{2}$ may change when applying Algorithm 1 if $c_{2}=1$.

    * –

Suppose $a_{1}\neq\zeta_{de}^{-i}$,
we have $\boldsymbol{\ell}_{1}=k+1$, and since $\zeta_{de}^{i}a_{1}\neq 1$, we
have $\boldsymbol{\ell}_{2}=k+2$. Hence when $c_{1}>c_{2}$,

if $a_{1}\neq\zeta_{de}^{-i}$, then
$\boldsymbol{\ell}(R\\!E(t_{i}w))=\boldsymbol{\ell}(R\\!E(w))+1.\hskip
28.45274pt(e)$

    * –

Suppose $a_{1}=\zeta_{de}^{-i}$, we have $b_{2}=\zeta_{de}^{i+ek}$.
We get $\boldsymbol{\ell}_{1}=k+1$ and $\boldsymbol{\ell}_{2}=k$. Hence when
$c_{1}>c_{2}$,

if $a_{1}=\zeta_{de}^{-i}$, then
$\boldsymbol{\ell}(R\\!E(t_{i}w))=\boldsymbol{\ell}(R\\!E(w))-1.\hskip
28.45274pt(f)$

Case 3: Suppose $x=z$.

Set $w^{\prime}:=zw$. By the left multiplication by $z$, we have that the last
$n-1$ rows of $w$ and $w^{\prime}$ are the same. Hence, by Definition 3.10 and
Lemma 3.8, we have:
$R\\!E_{2}(xw)R\\!E_{3}(xw)\cdots R\\!E_{n}(xw)=R\\!E_{2}(w)R\\!E_{3}(w)\cdots
R\\!E_{n}(w)$. In order to prove our property in this case, we should compare
$\boldsymbol{\ell}_{1}:=\boldsymbol{\ell}(R\\!E_{1}(w))$ and
$\boldsymbol{\ell}_{2}:=\boldsymbol{\ell}(R\\!E_{1}(xw))$.

We get $w_{1}$ is equal to $b_{1}$ and $w^{\prime}_{1}=\zeta_{d}b_{1}$ with
$b_{1}$ instead of $a_{1}$ since $a_{1}$ may change when applying Algorithm 1
if $c_{1}=1$. We have $b_{1}=\displaystyle\prod_{i=1}^{n}a_{i}=\zeta_{d}^{k}$
for some $0\leq k\leq d-1$. Hence if $k\neq d-1$, we get
$\boldsymbol{\ell}_{1}=k$ and $\boldsymbol{\ell}_{2}=k+1$ and if $k=d-1$, we
get $\boldsymbol{\ell}_{1}=d-1$ and $\boldsymbol{\ell}_{2}=0$. It follows that

$\boldsymbol{\ell}(R\\!E(zw))\leq\boldsymbol{\ell}(R\\!E(w))+1.\hskip
28.45274pt(g)$

∎

The next proposition establishes that Algorithm 1 produces geodesic normal
forms for $G(de,e,n)$.

######  Proposition 3.14.

Let $w$ be an element of $G(de,e,n)$. The word $R\\!E(w)$ is a reduced
expression over $\mathbf{X}$ of $w$.

###### Proof.

We must prove that $\ell(w)=\boldsymbol{\ell}(R\\!E(w))$. Let
$\mathbf{x}_{1}\mathbf{x}_{2}\cdots\mathbf{x}_{r}$ be a reduced expression
over $\mathbf{X}$ of $w$. Hence
$\ell(w)=\boldsymbol{\ell}(\mathbf{x}_{1}\mathbf{x}_{2}\cdots\mathbf{x}_{r})=r$.
Since $R\\!E(w)$ is a word representative over $\mathbf{X}$ of $w$, we have
$\boldsymbol{\ell}(R\\!E(w))\geq\boldsymbol{\ell}(\mathbf{x}_{1}\mathbf{x}_{2}\cdots\mathbf{x}_{r})=r$.

We prove that $\boldsymbol{\ell}(R\\!E(w))\leq r$. Write $w$ as
$x_{1}x_{2}\cdots x_{r}$ where $x_{1},x_{2},\cdots,x_{r}$ are the matrices of
$G(e,e,n)$ corresponding to
$\mathbf{x}_{1},\mathbf{x}_{2},\cdots,\mathbf{x}_{r}$. By Proposition 3.13, we
have: $\boldsymbol{\ell}(R\\!E(w))=\boldsymbol{\ell}(R\\!E(x_{1}x_{2}\cdots
x_{r}))\leq\boldsymbol{\ell}(R\\!E(x_{2}x_{3}\cdots
x_{r}))+1\leq\boldsymbol{\ell}(R\\!E(x_{3}\cdots x_{r}))+2\leq\cdots\leq r$.
Hence $\boldsymbol{\ell}(R\\!E(w))$ is equal to $\ell(w)$. This establishes
that $R\\!E(w)$ is a reduced expression over $\mathbf{X}$ of $w$.

∎

######  Remark 3.15.

Geodesic normal forms for the complex reflection groups $G(e,e,n)$ have been
already established in our previous work [17]. They are explicitly defined by
an algorithm (similar to Algorithm 1). Let $w\in G(e,e,n)$. The output of the
algorithm is the word also denoted by $R\\!E(w)$ and defined as a
concatenation of the words $R\\!E_{2}(w)$, $R\\!E_{3}(w)$, $\cdots$,
$R\\!E_{n}(w)$ introduced as in Definition 3.10. It describes a minimal word
representative of the element $w\in G(e,e,n)$.

As a direct consequence of Algorithm 1 and Proposition 3.14, the next
statement characterizes the elements of $G(de,e,n)$ that are of maximal length
over the generating set of Corran-Lee-Lee.

######  Proposition 3.16.

Let $d>1,e>1$ and $n\geq 2$. The maximal length of an element of $G(de,e,n)$
over the generating set of Corran-Lee-Lee is $n(n-1)+d-1$. It is realized for
diagonal matrices $w$ such that for all $2\leq i\leq n$, we have
$w[i,i]=\zeta_{de}^{k_{i}}$ with $1\leq k_{i}\leq de-1$ and
$w[1,1]=\zeta_{de}^{x}$ with $x+(k_{2}\cdots k_{n})=e(d-1)$. A minimal word
representative of such an element is of the form

$\mathbf{z}^{d-1}(\mathbf{t}_{k_{2}}\mathbf{t}_{0})(\mathbf{s}_{3}\mathbf{t}_{k_{3}}\mathbf{t}_{0}\mathbf{s}_{3})\cdots(\mathbf{s}_{n}\cdots\mathbf{s}_{3}\mathbf{t}_{k_{n}}\mathbf{t}_{0}\mathbf{s}_{3}\cdots\mathbf{s}_{n}),$

with $1\leq k_{2},\cdots,k_{n}\leq de-1$. The number of elements that are of
maximal length is then $(de-1)^{(n-1)}$.

###  3.3 The case of $G(d,1,n)$

We establish a similar construction for the case of $G(d,1,n)$ for $d>1$ and
$n\geq 2$. We recall the diagram of the presentation of $G(d,1,n)$:

$d$$\mathbf{z}$$2$$\mathbf{s}_{2}$$2$$\mathbf{s}_{3}$$2$$\mathbf{s}_{n-1}$$2$$\mathbf{s}_{n}$

Denote by $\mathbf{X}$ the set
$\\{\mathbf{z},\mathbf{s}_{2},\cdots,\mathbf{s}_{n}\\}$ of the generators. The
generator $\mathbf{z}$ corresponds to the matrix
$z:=Diag(\zeta_{d},1,\cdots,1)$ in $G(d,1,n)$ with $\zeta_{d}=exp(2i\pi/d)$
and $\mathbf{s}_{j}$ corresponds to the transposition matrix $s_{j}:=(j-1,j)$
for $2\leq j\leq n$. Denote by $X$ the set $\\{z,s_{2},s_{3},\cdots,s_{n}\\}$
of these matrices.

We define Algorithm 2 below that produces a word $R\\!E(w)$ for each matrix
$w$ of $G(d,1,n)$. This Algorithm is different than Algorithm 1. Let us
explain the steps of the algorithm. Let $w_{n}:=w\in G(d,1,n)$. For $i$ from
$n$ to $1$, the $i$-th step of the algorithm transforms the block diagonal
matrix $\left(\begin{array}[]{c|c}w_{i}&0\\\ \hline\cr
0&I_{n-i}\end{array}\right)$ into a block diagonal matrix
$\left(\begin{array}[]{c|c}w_{i-1}&0\\\ \hline\cr
0&I_{n-i+1}\end{array}\right)\in G(d,1,n)$. Let $w_{i}[i,c]\neq 0$ be the
nonzero coefficient on the row $i$ of $w_{i}$. If $w_{i}[i,c]=1$, we shift it
into the diagonal position $[i,i]$ by right multiplication by transpositions.
If $w_{i}[i,c]=\zeta_{d}^{k}$ with $k\geq 1$, we shift it into position
$[i,1]$ by right multiplication by transpositions, followed by a right
multiplication by $z^{-k}$, then we shift the $1$ obtained in position $[i,1]$
into the diagonal position $[i,i]$ by right multiplication by transpositions.
Let us illustrate these operations by the following example.

Input : $w$, a matrix in $G(d,1,n)$, with $d>1$ and $n\geq 2$.

Output : $R\\!E(w)$, a word over $\mathbf{X}$.

Local variables: $w^{\prime}$, $R\\!E(w)$, $i$, $U$, $c$, $k$.

Initialisation: $U:=[1,\zeta_{d},\zeta_{d}^{2},\cdots,\zeta_{d}^{d-1}]$,
$R\\!E(w):=\varepsilon$: the empty word, $w^{\prime}:=w$.

for  _$i$ from $n$ down to $1$_ do

$c:=1$; $k:=0$;

while  _$w^{\prime}[i,c]=0$_ do

$c:=c+1$;

end while

#Then $w^{\prime}[i,c]$ is the root of unity on the row $i$;

while  _$U[k+1]\neq w^{\prime}[i,c]$_ do

$k:=k+1$;

end while

#Then $w^{\prime}[i,c]=\zeta_{d}^{k}$.

if  _$k\neq 0$_ then

$w^{\prime}:=w^{\prime}s_{c}s_{c-1}\cdots s_{3}s_{2}z^{-k}$; #Then
$w^{\prime}[i,2]=1$;

$R\\!E(w):=\mathbf{z}^{k}\mathbf{s}_{2}\mathbf{s}_{3}\cdots\mathbf{s}_{c}R\\!E(w)$;

$c:=1$;

end if

$w^{\prime}:=w^{\prime}s_{c+1}\cdots s_{i-1}s_{i}$; #Then $w^{\prime}[i,i]=1$;

$R\\!E(w):=\mathbf{s}_{i}\mathbf{s}_{i-1}\cdots\mathbf{s}_{c+1}R\\!E(w)$;

end for

Return $R\\!E(w)$;

Algorithm 2 A word over $\mathbf{X}$ corresponding to an element $w\in
G(d,1,n)$.

######  Example 3.17.

Let $w:=\begin{pmatrix}0&\zeta_{3}&0\\\ 0&0&\zeta_{3}^{2}\\\
\zeta_{3}^{2}&0&0\par\end{pmatrix}$ $\in G(3,1,3)$.
Step $1$ $(i=3,k=2,c=1)$: $w^{\prime}:=wz^{-2}=\begin{pmatrix}0&\zeta_{3}&0\\\
0&0&\zeta_{3}^{2}\\\ 1&0&0\par\end{pmatrix}$, then
$w^{\prime}:=w^{\prime}s_{2}s_{3}=\begin{pmatrix}\zeta_{3}&0&0\\\
0&\boxed{\zeta_{3}^{2}}&0\\\ 0&0&\mathbf{1}\par\end{pmatrix}$.
Step $2$ $(i=2,k=2,c=1)$:
$w^{\prime}:=w^{\prime}s_{2}=\begin{pmatrix}0&\zeta_{3}&0\\\
\zeta_{3}^{2}&0&0\\\ 0&0&1\par\end{pmatrix}$, then
$w^{\prime}:=w^{\prime}z^{-2}=\begin{pmatrix}0&\zeta_{3}&0\\\ 1&0&0\\\
0&0&1\par\end{pmatrix}$, then
$w^{\prime}:=w^{\prime}s_{2}=\begin{pmatrix}\boxed{\zeta_{3}}&0&0\\\
0&\mathbf{1}&0\\\ 0&0&1\par\end{pmatrix}$.
Step $3$ $(i=1,k=1,c=1)$: $w^{\prime}:=w^{\prime}z^{-1}=I_{3}$.
Hence
$R\\!E(w)=\mathbf{z}\mathbf{s}_{2}\mathbf{z}^{2}\mathbf{s}_{2}\mathbf{s}_{3}\mathbf{s}_{2}\mathbf{z}^{2}$.

The next lemma follows directly from Algorithm 2.

######  Lemma 3.18.

For $2\leq i\leq n$, let $w_{i}[i,c]\neq 0$ be the nonzero coefficient on the
row $i$ of $w_{i}$. The block $w_{i-1}$ is obtained by removing the row $i$
and the column $c$ from $w_{i}$. Moreover, $w_{1}$ is equal to the nonzero
entry on the first row of $w$.

######  Definition 3.19.

Let $1\leq i\leq n$. Let $w_{i}[i,c]\neq 0$ for $1\leq c\leq i$.

  * •

If $w_{1}=\zeta_{d}^{k}$ for some $0\leq k\leq d-1$ (this is equal to the
nonzero entry on the first row of $w$), we define $R\\!E_{1}(w)$ to be the
word $\mathbf{z}^{k}$.

  * •

If $w_{i}[i,c]=1$, we define $R\\!E_{i}(w)$ to be the word
$\mathbf{s}_{i}\mathbf{s}_{i-1}\cdots\mathbf{s}_{c+1}$ (decreasing-index
expression).

  * •

If $w_{i}[i,c]=\zeta_{d}^{k}$ with $k\neq 0$, we define $R\\!E_{i}(w)$ to be
the word
$\mathbf{s}_{i}\cdots\mathbf{s}_{3}\mathbf{z}^{k}$ if $c=1$,
$\mathbf{s}_{i}\cdots\mathbf{s}_{3}\mathbf{s}_{2}\mathbf{z}^{k}\mathbf{s}_{2}\mathbf{s}_{3}\cdots\mathbf{s}_{c}$
if $c\geq 2$.

As for Algorithm 1, the output of Algorithm 2 is equal to
$R\\!E_{1}(w)R\\!E_{2}(w)\cdots R\\!E_{n}(w)$. In Example 3.17, we have
$R\\!E(w)=\underset{R\\!E_{1}(w)}{\underbrace{\mathbf{z}}}\hskip
5.69046pt\underset{R\\!E_{2}(w)}{\underbrace{\mathbf{s}_{2}\mathbf{z}^{2}\mathbf{s}_{2}}}\hskip
5.69046pt\underset{R\\!E_{3}(w)}{\underbrace{\mathbf{s}_{3}\mathbf{s}_{2}\mathbf{z}^{2}}}$.

The proof of the next proposition is similar to the proof of Proposition 3.12
and is left to the reader.

######  Proposition 3.20.

Let $w\in G(d,1,n)$. The word $R\\!E(w)$ given by Algorithm 2 is a word
representative over $\mathbf{X}$ of $w\in G(d,1,n)$.

The following proposition enables us to prove that the output of Algorithm 2
is a reduced expression over $\mathbf{X}$ of a given element $w\in G(d,1,n)$.

######  Proposition 3.21.

Let $w$ be an element of $G(d,1,n)$. For all $x\in X$, we have

$\boldsymbol{\ell}(R\\!E(xw))\leq\boldsymbol{\ell}(R\\!E(w))+1.$

###### Proof.

Consider $x=s_{i}$ with $2\leq i\leq n$. This case is done in the same way as
Case 1 in the proof of Proposition 3.13. Consider now $x=z$. This case is done
this time as Case 3 of the proof of Proposition 3.13.

∎

Applying the arguments used before in the proof of Proposition 3.14, we deduce
that $R\\!E(w)$ is a reduced expression over $\mathbf{X}$ of $w\in G(d,1,n)$.
Hence Algorithm 2 produces geodesic normal forms for $G(d,1,n)$.

As a direct application, the next statement characterizes the elements of
$G(d,1,n)$ that are of maximal length. Note that this statement was also
observed in [4].

######  Proposition 3.22.

Let $d>1$ and $n\geq 2$. There exists a unique element of maximal length of
$G(d,1,n)$. Its minimal word representative is of the form

$\mathbf{z}^{d-1}(\mathbf{s}_{2}\mathbf{z}^{d-1}\mathbf{s}_{2})(\mathbf{s}_{3}\mathbf{s}_{2}\mathbf{z}^{d-1}\mathbf{s}_{2}\mathbf{s}_{3})\cdots(\mathbf{s}_{n}\cdots\mathbf{s}_{2}\mathbf{z}^{d-1}\mathbf{s}_{2}\cdots\mathbf{s}_{n}).$

Its length is then equal to $n(n+d-2)$.

######  Remark 3.23.

When $d=2$, the group $G(2,1,n)$ is the Coxeter group of type $B_{n}$. By
Proposition 3.22, the longest element is of the form

$\mathbf{z}(\mathbf{s}_{2}\mathbf{z}\mathbf{s}_{2})(\mathbf{s}_{3}\mathbf{s}_{2}\mathbf{z}\mathbf{s}_{2}\mathbf{s}_{3})\cdots(\mathbf{s}_{n}\cdots\mathbf{s}_{2}\mathbf{z}\mathbf{s}_{2}\cdots\mathbf{s}_{n}).$

Its length is equal to $n^{2}$ which is already known for Coxeter groups of
type $B_{n}$, see Example 1.4.6 of [11].

##  4 The Hecke algebras $H(de,e,n)$

The Hecke algebras $H(de,e,n)$ attached to the general series of complex
reflection groups $G(de,e,n)$ are defined as quotients of the corresponding
complex braid group algebras by some polynomial relations. Let $B(de,e,n)$
denotes the complex braid group attached to $G(de,e,n)$, as defined in [6]. We
establish nice presentations for the Hecke algebras $H(de,e,n)$ by using the
presentations of Corran-Picantin [10] and Corran-Lee-Lee [9] of the complex
braid groups $B(e,e,n)$ and $B(de,e,n)$ for $d>1$, respectively.

###  4.1 The Hecke algebras $H(e,e,n)$

Corran-Picantin introduced in [10] a presentation for the complex braid groups
$B(e,e,n)$. Although we are not going to use this result, we mention that they
also established nice combinatorial structures (called Garside structures) for
these groups. The presentation of Corran-Picantin is as follows.

######  Definition 4.1.

Let $e\geq 1$ and $n\geq 2$. The group $B(e,e,n)$ is defined by a presentation
with set of generators: $\\{t_{i}\ |\ i\in\mathbb{Z}/e\mathbb{Z}\\}$
$\cup\\{s_{3},s_{4},\cdots,s_{n}\\}$ and relations:

  1. 1.

$t_{i}t_{i-1}=t_{j}t_{j-1}$ for $i,j\in\mathbb{Z}/e\mathbb{Z}$,

  2. 2.

$t_{i}s_{3}t_{i}=s_{3}t_{i}s_{3}$ for $i\in\mathbb{Z}/e\mathbb{Z}$,

  3. 3.

$s_{j}t_{i}=t_{i}s_{j}$ for $i\in\mathbb{Z}/e\mathbb{Z}$ and $4\leq j\leq n$,

  4. 4.

$s_{i}s_{i+1}s_{i}=s_{i+1}s_{i}s_{i+1}$ for $3\leq i\leq n-1$,

  5. 5.

$s_{i}s_{j}=s_{j}s_{i}$ for $|i-j|>1$.

Adding the quadratic relations to all the generators, we get the presentation
of Corran-Picantin of $G(e,e,n)$ given earlier in Definition 3.1. Similar to
the diagram of Figure 1, the diagram that describes the presentation of
Corran-Picantin of $B(e,e,n)$ is the following.

$t_{0}$$t_{1}$$t_{2}$$t_{i}$$t_{e-1}$$s_{3}$$s_{4}$$s_{n-1}$$s_{n}$$\cdots$
Figure 4: Diagram for the presentation of Corran-Picantin of $B(e,e,n)$.

The next definition establishes a presentation of the Hecke algebra $H(e,e,n)$
attached to the group $G(e,e,n)$, by using the presentation of Corran-Picantin
of the complex braid group $B(e,e,n)$.

######  Definition 4.2.

Let $e\geq 1$ and $n\geq 2$. We exclude the case ($n=2$, $e$ even), see Remark
4.3 below. Let $R_{0}=\mathbb{Z}[a]$. The unitary associative Hecke algebra
$H(e,e,n)$ is defined as the quotient of the group algebra $R_{0}(B(e,e,n))$
by the following relations:

  1. 1.

$t_{i}^{2}-at_{i}-1=0$ for $i\in\mathbb{Z}/e\mathbb{Z}$,

  2. 2.

$s_{j}^{2}-as_{j}-1=0$ for $3\leq j\leq n$,

where $\\{t_{i}\ |\ i\in\mathbb{Z}/e\mathbb{Z}\\}\cup\\{s_{j}\ |\ 3\leq j\leq
n\\}$ is the set of generators of the presentation of Corran-Picantin of
$B(e,e,n)$. Then, a presentation of $H(e,e,n)$ is obtained by adding these
relations to those of the presentation of Corran-Picantin given in Definition
4.1.

######  Remark 4.3.

For the case ($n=2$, $e$ even), there exists two conjugacy classes of the
reflections $t_{i}$, for $i\in\mathbb{Z}/e\mathbb{Z}$ in the complex
reflection group. In this case, we define the Hecke algebra $H(e,e,2)$ in the
same way as in Definition 4.2 over $R_{0}=\mathbb{Z}[a_{1},a_{2}]$ with two
types of polynomial relations for each conjugacy class of the $t_{i}$’s:
$t_{i}^{2}-a_{1}t_{i}-1=0$ for the first conjugacy class and
$t_{j}^{2}-a_{2}t_{j}-1=0$ for the second.

Note that we use the polynomial ring $R_{0}$ instead of the usual Laurent
polynomial ring $R$ introduced in Definition 2.2 and we use normalized
polynomial relations in the definition of $H(e,e,n)$. Actually, by a result of
Marin (see Proposition 2.3 in [14]) applied to the case of $G(e,e,n)$, the BMR
freeness conjecture for this case is equivalent to the fact that $H(e,e,n)$ is
a free $R_{0}$-module of rank equal to the order of $G(e,e,n)$. We will also
use a polynomial ring and normalized relations in the definition of the Hecke
algebras attached to all the groups $G(de,e,n)$ in the next subsection.

###  4.2 The general case

Corran-Lee-Lee [9] established a presentation for the complex braid group
$B(de,e,n)$ that give rise to nice combinatorial structures (called quasi-
Garside structures) for these groups. The presentation is defined as follows.

######  Definition 4.4.

Let $d>1$, $e\geq 1$ and $n\geq 2$. The group $B(de,e,n)$ is defined by a
presentation with set of generators: $\\{z\\}\cup\\{t_{i}\ |\
i\in\mathbb{Z}\\}\cup\\{s_{3},s_{4},\cdots,s_{n}\\}$ and relations:

  1. 1.

$zt_{i}=t_{i-e}z$ for $i\in\mathbb{Z}$,

  2. 2.

$zs_{j}=s_{j}z$ for $3\leq j\leq n$,

  3. 3.

$t_{i}t_{i-1}=t_{j}t_{j-1}$ for $i,j\in\mathbb{Z}$,

  4. 4.

$t_{i}s_{3}t_{i}=s_{3}t_{i}s_{3}$ for $i\in\mathbb{Z}$,

  5. 5.

$s_{j}t_{i}=t_{i}s_{j}$ for $i\in\mathbb{Z}$ and $4\leq j\leq n$,

  6. 6.

$s_{i}s_{i+1}s_{i}=s_{i+1}s_{i}s_{i+1}$ for $3\leq i\leq n-1$,

  7. 7.

$s_{i}s_{j}=s_{j}s_{i}$ for $|i-j|>1$.

Note that $B(de,e,n)$ is isomorphic to $B(2e,e,n)$ for $d>1$. The parameter
$d$ makes an appearance when it comes to the complex reflection group
$G(de,e,n)$. Adding the relation $z^{d}=1$ and the quadratic relations to all
the other generators of the presentation of Corran-Lee-Lee of $B(de,e,n)$, we
obtain the presentation of $G(de,e,n)$ given earlier in Definition 3.3.
Actually, with the additional relation $z^{d}=1$, we have
$t_{i+de}=z^{d}t_{i+de}=t_{i}z^{d}=t_{i}$ for all $i\in\mathbb{Z}$.

Corran-Lee-Lee proposed in [9] the following diagram to describe their
presentation of $B(de,e,n)$. The nodes are the generators of the presentation.
Relation 1 of definition 4.4 is described by the curved arrow. Relation 3 is
described by the vertical line such that the nodes $t_{i}$’s are tangent to
this line. All the other edges follow the standard conventions of type
$A_{n-1}$ Artin groups.

$\textstyle{z}$$\textstyle{\vdots}$$\textstyle{\vdots}$$\textstyle{\dots}$$\textstyle{t_{2}}$$\textstyle{t_{1}}$$\textstyle{t_{0}}$$\textstyle{t_{-1}}$$\textstyle{t_{-2}}$$\textstyle{s_{3}}$$\textstyle{s_{4}}$$\textstyle{s_{5}}$$\textstyle{s_{n}}$
Figure 5: Diagram for the presentation of Corran-Lee-Lee of $B(de,e,n)$.

Note that for $e=1$, it is readily checked that the presentation of Corran-
Lee-Lee is equivalent to the classical presentation of $B(d,1,n)$ that is
isomorphic to $B(2,1,n)$ for $d>1$. Note that we replace $t_{0}$ by $s_{2}$ in
the set of generators. The (well-known) diagram that describes the classical
presentation of $B(d,1,n)$ is the following.

$z$$s_{2}$$s_{3}$$s_{n-1}$$s_{n}$

We are ready to establish a presentation of the Hecke algebra $H(de,e,n)$
attached to the group $G(de,e,n)$, by using the presentation of Corran-Lee-Lee
of the complex braid group $B(de,e,n)$. Similarly to the case of $H(e,e,n)$,
we also define the Hecke algebra $H(de,e,n)$ over a polynomial ring $R_{0}$
and use normalized polynomial relations.

######  Definition 4.5.

Let $d>1$, $e\geq 1$ and $n\geq 2$. We exclude the case ($n=2$, $e$ even), see
Remark 4.6 below. Let $R_{0}=\mathbb{Z}[a,b_{1},b_{2},\cdots,b_{d-1}]$. The
unitary associative Hecke algebra $H(de,e,n)$ is defined as the quotient of
the group algebra $R_{0}(B(de,e,n))$ by the following relations:

  1. 1.

$z^{d}-b_{1}z^{d-1}-b_{2}z^{d-2}-\cdots-b_{d-1}z-1=0$,

  2. 2.

$t_{i}^{2}-at_{i}-1=0$ for $i\in\mathbb{Z}$,

  3. 3.

$s_{j}^{2}-as_{j}-1=0$ for $3\leq j\leq n$,

where $\\{z\\}\cup\\{t_{i}\ |\ i\in\mathbb{Z}\\}\cup\\{s_{j}\ |\ 3\leq j\leq
n\\}$ is the set of generators of the presentation of Corran-Lee-Lee of
$B(de,e,n)$. Then, a presentation of $H(de,e,n)$ is obtained by adding these
relations to those given in Definition 4.4.

######  Remark 4.6.

When ($n=2$, $e$ even), the Hecke algebra $H(de,e,2)$ can be defined over
$R_{0}[a_{1},a_{2},b_{1},b_{2},\cdots,b_{d-1}]$ in the same way as in the
previous definition, but with two types of polynomial relations for the
$t_{i}$’s $($due to the existence of two conjugacy classes of the $t_{i}$’s in
$G(de,e,2))$, as established before in Remark 4.3.

##  5 Bases for the Hecke algebras $H(e,e,n)$

The Hecke algebra $H(e,e,n)$ is described in Definition 4.2 by a presentation
with generating set $\\{t_{0},t_{1},\cdots,t_{e-1},s_{3},\cdots,s_{n}\\}$. It
is defined over $R_{0}=\mathbb{Z}[a]$. Note that we will replace $t_{0}$ by
$s_{2}$ in some cases in order to simplify notations. Using the geodesic
normal forms of $G(e,e,n)$ introduced in Section 3, we construct a natural
basis for $H(e,e,n)$ that is different from the one introduced by Ariki in
[1].

Let us define the following subsets of $H(e,e,n)$:

$\Lambda_{2}$ | $=$ | $\\{1,$ |
---|---|---|---
|  | $\ \ t_{k}$ | for $0\leq k\leq e-1$,
|  | $\ \ t_{k}t_{0}$ | for $1\leq k\leq e-1\\}$,

and for $3\leq i\leq n$,

$\Lambda_{i}$ | $=$ |  $\\{1$, |
---|---|---|---
|  | $\ \ s_{i}\cdots s_{i^{\prime}}$ | for $3\leq i^{\prime}\leq i$,
|  | $\ \ s_{i}\cdots s_{3}t_{k}$ | for $0\leq k\leq e-1$,
|  | $\ \ s_{i}\cdots s_{3}t_{k}s_{2}\cdots s_{i^{\prime}}$ | for $1\leq k\leq e-1$ and $2\leq i^{\prime}\leq i\\}.$

Define $\Lambda=\Lambda_{2}\cdots\Lambda_{n}$ to be the set of the products
$a_{2}\cdots a_{n}$, where $a_{2}\in\Lambda_{2},\cdots,a_{n}\in\Lambda_{n}$.
Remark that this set corresponds to all the reduced words $R\\!E(w)$ of the
form $R\\!E_{2}(w)R\\!E_{3}(w)\cdots R\\!E_{n}(w)$ introduced in Section 3
(see Definition 3.10 and Remark 3.15). Recall that $R_{0}=\mathbb{Z}[a]$ (see
Definition 4.2). The aim of this section is to establish the following.

######  Theorem 5.1.

The set $\Lambda$ provides an $R_{0}$-basis of the Hecke algebra $H(e,e,n)$.

In order to prove this theorem, it is shown in Proposition 2.3$(i)$ of [14]
that it is enough to find a spanning set of $H(e,e,n)$ over $R_{0}$ of
$|G(e,e,n)|$ elements. This is a general fact about Hecke algebras associated
to complex reflection groups. We have $|\Lambda_{2}|=2e$, $|\Lambda_{3}|=3e$,
$\cdots$, and $|\Lambda_{n}|=ne$ by the definition of $\Lambda_{2}$, $\cdots$,
and $\Lambda_{n}$. Thus, $|\Lambda|$ is equal to $e^{n-1}n!$ that is the order
of $G(e,e,n)$. If we manage to prove that $\Lambda$ is a spanning set of
$H(e,e,n)$ over $R_{0}$, then we get Theorem 5.1. Denote by Span$(S)$ the
sub-$R_{0}$-module of $H(e,e,n)$ generated by $S$.

We prove Theorem 5.1 by induction on $n\geq 2$. Propositions 5.4 and 5.6 below
correspond to the cases $n=2$ and $n=3$, respectively. Suppose that
$\Lambda_{2}\cdots\Lambda_{n-1}$ is an $R_{0}$-basis of $H(e,e,n-1)$. As
mentioned before, in order to prove that
$\Lambda=\Lambda_{2}\cdots\Lambda_{n}$ is an $R_{0}$-basis of $H(e,e,n)$, it
is enough to show that it is an $R_{0}$-generating set of $H(e,e,n)$, that is
$\Lambda$ stable under left multiplication by $t_{0},\cdots,t_{e-1},s_{3}$,
$\cdots$, $s_{n}$. Since $\Lambda_{2}\cdots\Lambda_{n-1}$ is an $R_{0}$-basis
of $H(e,e,n-1)$, the set $\Lambda_{2}\cdots\Lambda_{n}$ is stable under left
multiplication by $t_{0},\cdots,t_{e-1},s_{3}$, $\cdots$, $s_{n-1}$. We prove
that it is stable under left multiplication by $s_{n}$, that is
$s_{n}(a_{2}\cdots a_{n})=a_{2}\cdots a_{n-2}s_{n}(a_{n-1}a_{n})$ belongs to
Span$(\Lambda)$ for $a_{2}\in\Lambda_{2}$, $\cdots$, $a_{n}\in\Lambda_{n}$ by
checking all the different possibilities for $a_{n-1}\in\Lambda_{n-1}$ and
$a_{n}\in\Lambda_{n}$.

Assume $n>3$. If $a_{n-1}=1$ or $a_{n}=1$, it is readily checked that
$s_{n}(a_{n-1}a_{n})$ belongs to Span$(\Lambda_{n-1}\Lambda_{n})$. If
$a_{n-1}=s_{n-1}\cdots s_{i}$ for $2\leq i\leq n-1$, we distinguish $3$
different cases for $a_{n}$ that belongs to $\Lambda_{n}$. This is done in
Lemmas 5.8, 5.9 and 5.10 below. If $a_{n-1}=s_{n-1}\cdots s_{3}t_{k}$ for
$0\leq k\leq e-1$, we also distinguish $3$ different cases for
$a_{n}\in\Lambda_{n}$. This is done in Lemmas 5.11, 5.12 and 5.13. Finally, if
$a_{n-1}=s_{n-1}\cdots s_{3}t_{k}s_{2}\cdots s_{i}$ for $1\leq k\leq e-1$ and
$2\leq i\leq n-1$, we also have $3$ different cases for $a_{n}\in\Lambda_{n}$
(see Lemmas 5.14, 5.15 and 5.16 below).

Let us start by establishing the following two preliminary lemmas.

######  Lemma 5.2.

For $i,j\in\mathbb{Z}/e\mathbb{Z}$, we have $t_{j}t_{i}\in$
Span$(\Lambda_{2})$.

###### Proof.

If $i=j$, then we have $t_{i}^{2}=at_{i}+1\in$ Span$(\Lambda_{2})$. Suppose
$i\neq j$. We have
$t_{i}t_{i-1}=t_{j}t_{j-1}$. If we multiply by $t_{j}$ on the left and by
$t_{i-1}$ on the right, we get
$t_{j}t_{i}t_{i-1}^{2}=t_{j}^{2}t_{j-1}t_{i-1}$. Using the quadratic
relations, we have
$t_{j}t_{i}(at_{i-1}+1)=(at_{j}+1)t_{j-1}t_{i-1}$, that is
$at_{j}t_{i}t_{i-1}+t_{j}t_{i}=at_{j}t_{j-1}t_{i-1}+t_{j-1}t_{i-1}$.
Replacing $t_{i}t_{i-1}$ by $t_{j}t_{j-1}$ and $t_{j}t_{j-1}$ by
$t_{i}t_{i-1}$, we get
$at_{j}^{2}t_{j-1}+t_{j}t_{i}=at_{i}t_{i-1}^{2}+t_{j-1}t_{i-1}$. Using the
quadratic relations, we have
$a(at_{j}+1)t_{j-1}+t_{j}t_{i}=at_{i}(at_{i-1}+1)+t_{j-1}t_{i-1}$, that is
$a^{2}t_{1}t_{0}+at_{j-1}+t_{j}t_{i}=a^{2}t_{1}t_{0}+at_{i}+t_{j-1}t_{i-1}$.
Simplifying this relation, we get

$t_{j}t_{i}=t_{j-1}t_{i-1}+a(t_{i}-t_{j-1})$.

Now, we apply the same operations to compute $t_{j-1}t_{i-1}$ and so on until
we arrive to a term of the form $t_{k}t_{0}$ for some
$k\in\mathbb{Z}/e\mathbb{Z}$. Thus, if $i\neq j$, then $t_{j}t_{i}$ belongs to
Span$(\Lambda_{2}\setminus\\{1\\})$.

∎

######  Lemma 5.3.

For $1\leq k\leq e-1$, we have $t_{k}t_{0}\in
R_{0}(t_{1}t_{0})+R_{0}(t_{1}t_{0})^{2}+\cdots+R_{0}(t_{1}t_{0})^{k}+R_{0}t_{1}+R_{0}t_{2}+\cdots+R_{0}t_{k-1}$.

###### Proof.

We prove the property by induction on $k$. The property is clearly satisfied
for $k=1$. Let $k\geq 2$. Suppose $t_{k-1}t_{0}\in
R_{0}(t_{1}t_{0})+R_{0}(t_{1}t_{0})^{2}+\cdots+R_{0}(t_{1}t_{0})^{k-1}+R_{0}t_{1}+R_{0}t_{2}+\cdots+R_{0}t_{k-2}$.
We have that $t_{k+1}t_{k}=t_{k}t_{k-1}$. Multiplying by $t_{k+1}$ on the left
and by $t_{0}$ on the right, we get
$t_{k+1}^{2}t_{k}t_{0}=t_{k+1}t_{k}t_{k-1}t_{0}$. Using the quadratic
relations and replacing $t_{k+1}t_{k}$ with $t_{1}t_{0}$, we get
$(at_{k+1}+1)t_{k}t_{0}=t_{1}t_{0}t_{k-1}t_{0}$. After simplifying this
relation, we have $t_{k}t_{0}=t_{1}t_{0}(t_{k-1}t_{0})-a(t_{1}t_{0})t_{0}$.
Using the induction hypothesis, we replace $t_{k-1}t_{0}$ by its value and we
get $t_{k}t_{0}\in
t_{1}t_{0}(R_{0}(t_{1}t_{0})+R_{0}(t_{1}t_{0})^{2}+\cdots+R_{0}(t_{1}t_{0})^{k-1}+R_{0}t_{1}+R_{0}t_{2}+\cdots+R_{0}t_{k-2})+R_{0}(t_{1}t_{0})t_{0}$.
This is equal to
$R_{0}(t_{1}t_{0})^{2}+R_{0}(t_{1}t_{0})^{3}+\cdots+R_{0}(t_{1}t_{0})^{k}+R_{0}(t_{1}t_{0})t_{1}+R_{0}(t_{1}t_{0})t_{2}+\cdots+R_{0}(t_{1}t_{0})t_{k-2}+R_{0}(t_{1}t_{0})t_{0}$.
Now $(t_{1}t_{0})t_{m}$ is equal to $t_{m+1}t_{m}t_{m}\in
R_{0}t_{1}t_{0}+R_{0}t_{m+1}$ for $1\leq m\leq k-2$ and $(t_{1}t_{0})t_{0}\in
R_{0}(t_{1}t_{0})+R_{0}t_{1}$. It follows that $t_{k}t_{0}\in
R_{0}(t_{1}t_{0})+R_{0}(t_{1}t_{0})^{2}+\cdots+R_{0}(t_{1}t_{0})^{k}+R_{0}t_{1}+R_{0}t_{2}+\cdots+R_{0}t_{k-1}$.

∎

As a direct consequence of Lemma 5.2, we have the following.

######  Proposition 5.4.

Let $x=t_{l}$ with $l\in\mathbb{Z}/e\mathbb{Z}$. For all
$a_{2}\in\Lambda_{2}$, we have $xa_{2}$ belongs to Span$(\Lambda_{2})$.

######  Remark 5.5.

Recall that we excluded the case ($n=2$, $e$ even) in Definition 4.2 (see
Remark 4.3). Consider the Hecke algebra $H(e,e,2)$ with $e$ even. Similarly to
Proposition 5.4, one shows that $\Lambda_{2}$ is stable under left
multiplication by all the $t_{i}$’s for $i\in\mathbb{Z}/e\mathbb{Z}$. Then,
applying Proposition (2.3) (i) of [14], we also get that $\Lambda_{2}$ is an
$R_{0}$-basis of $H(e,e,2)$ for the case $e$ even.

######  Proposition 5.6.

For all $a_{2}\in\Lambda_{2}$ and $a_{3}\in\Lambda_{3}$, the element
$s_{3}(a_{2}a_{3})$ belongs to Span$(\Lambda_{2}\Lambda_{3})$.

###### Proof.

The case where $a_{1}\in\Lambda_{1}$ and $a_{2}=1$ is obvious. The case where
$a_{1}=1$ and $a_{2}\in\Lambda_{2}$ is also obvious.

_Case 1_. Suppose $a_{2}=t_{k}$ for $0\leq k\leq e-1$ and $a_{3}=s_{3}$.
We have $s_{3}t_{k}s_{3}=t_{k}\underline{s_{3}t_{k}}\in$
Span$(\Lambda_{2}\Lambda_{3})$.

_Case 2_. Suppose $a_{2}=t_{k}$ for $0\leq k\leq e-1$ and $a_{3}=s_{3}t_{l}$
for $0\leq l\leq e-1$.
We have $\underline{s_{3}t_{k}s_{3}}t_{l}=t_{k}s_{3}t_{k}t_{l}$. After
replacing $t_{k}t_{l}$ by its decomposition over $\Lambda_{2}$ (see Lemma
5.2), we directly have $s_{3}t_{k}s_{3}t_{l}\in$
Span$(\Lambda_{2}\Lambda_{3})$.

_Case 3_. Suppose $a_{2}=t_{k}$ for $0\leq k\leq e-1$ and
$a_{3}=s_{3}t_{l}t_{0}$ or $a_{3}=s_{3}t_{l}t_{0}s_{3}$ for $1\leq l\leq e-1$.
We have
$\underline{s_{3}t_{k}s_{3}}t_{l}t_{0}s_{3}=t_{k}s_{3}t_{k}t_{l}t_{0}s_{3}$.
By replacing $t_{k}t_{l}$ by its value (see Lemma 5.2), we obviously have
$s_{3}t_{k}s_{3}t_{l}t_{0}$ and $s_{3}t_{k}s_{3}t_{l}t_{0}s_{3}$ belong to
Span$(\Lambda_{2}\Lambda_{3})$.

_Case 4_. Suppose $a_{2}=t_{k}t_{0}$ for $1\leq k\leq e-1$ and $a_{3}=s_{3}$.
We have $s_{3}(a_{2}a_{3})=s_{3}t_{k}t_{0}s_{3}\in$
Span$(\Lambda_{2}\Lambda_{3})$.

_Case 5_. Suppose $a_{2}=t_{k}t_{0}$ with $1\leq k\leq e-1$ and
$a_{3}=s_{3}t_{l}$ with $0\leq l\leq e-1$.
We have $s_{3}(a_{2}a_{3})=s_{3}t_{k}t_{0}s_{3}t_{l}$. Recall that by Lemma
5.3, we have $t_{k}t_{0}\in
R_{0}(t_{1}t_{0})+R_{0}(t_{1}t_{0})^{2}+\cdots+R_{0}(t_{1}t_{0})^{k}+R_{0}t_{1}+R_{0}t_{2}+\cdots+R_{0}t_{k-1}$.
Replacing $t_{k}t_{0}$ by its value, we have to deal with the following two
terms:
$s_{3}t_{x}s_{3}t_{l}$ with $1\leq x\leq k-1$ and
$s_{3}(t_{1}t_{0})^{x}s_{3}t_{l}$ with $1\leq x\leq k$.
The first term is done in Case 2. For the second term, we decrease the power
of $(t_{1}t_{0})$ and use $t_{1}t_{0}=t_{l+1}t_{l}$ to get
$s_{3}(t_{1}t_{0})^{x-1}t_{l+1}\underline{t_{l}s_{3}t_{l}}$. We apply a braid
relation and then get $s_{3}(t_{1}t_{0})^{x-1}t_{l+1}s_{3}t_{l}s_{3}$. Again,
we decrease the power of $(t_{1}t_{0})$ and use $t_{1}t_{0}=t_{l+2}t_{l+1}$.
We get $s_{3}(t_{1}t_{0})^{x-2}t_{l+2}t_{l+1}^{2}s_{3}t_{l}s_{3}\in
R_{0}s_{3}(t_{1}t_{0})^{x-2}t_{l+2}t_{l+1}s_{3}t_{l}s_{3}+R_{0}s_{3}(t_{1}t_{0})^{x-2}t_{l+2}s_{3}t_{l}s_{3}$.
We continue by decreasing the power of $(t_{1}t_{0})$ and we get in the next
step that $s_{3}(a_{2}a_{3})$ belongs to
$R_{0}s_{3}(t_{1}t_{0})^{x-3}t_{l+1}s_{3}t_{l}s_{3}^{3}$
$+R_{0}s_{3}(t_{1}t_{0})^{x-3}t_{l+2}s_{3}t_{l}s_{3}^{2}$
$+R_{0}s_{3}(t_{1}t_{0})^{x-3}t_{l+1}s_{3}t_{l}s_{3}^{2}$
$+R_{0}s_{3}(t_{1}t_{0})^{x-3}t_{l+3}s_{3}t_{l}s_{3}$. Inductively, we arrive
to terms of the form
$s_{3}t_{1}t_{0}t_{x^{\prime}}s_{3}t_{l}(s_{3})^{x^{\prime\prime}}$ ($0\leq
x^{\prime}\leq e-1$ and $x^{\prime\prime}\in\mathbb{N}$). Replace $t_{1}t_{0}$
by $t_{x^{\prime}+1}t_{x^{\prime}}$, we get
$s_{3}t_{x^{\prime}+1}(t_{x^{\prime}})^{2}s_{3}t_{l}(s_{3})^{x^{\prime\prime}}$
which belongs to
$R_{0}s_{3}t_{x^{\prime}+1}t_{x^{\prime}}s_{3}t_{l}(s_{3})^{x^{\prime\prime}}$
$+R_{0}s_{3}t_{x^{\prime}+1}s_{3}t_{l}(s_{3})^{x^{\prime\prime}}$. Replacing
$t_{x^{\prime}+1}t_{x^{\prime}}$ by $t_{l+1}t_{l}$ and applying a braid
relation in the first term, we get
$R_{0}s_{3}t_{l+1}s_{3}t_{l}(s_{3})^{x^{\prime\prime}+1}$
$+R_{0}s_{3}t_{x^{\prime}+1}s_{3}t_{l}(s_{3})^{x^{\prime\prime}}$. Since
$s_{3}^{2}=as_{3}+1$, it remains to deal with these $2$ terms:

$s_{3}t_{x}s_{3}t_{l}$ and $s_{3}t_{x}s_{3}t_{l}s_{3}$, for some $0\leq x\leq
e-1$.

It is readily checked that these terms belong to
Span$(\Lambda_{2}\Lambda_{3})$.

_Case 6_. Suppose $a_{2}=t_{k}t_{0}$ and $a_{3}=s_{3}t_{l}t_{0}$ or
$a_{3}=s_{3}t_{l}t_{0}s_{3}$ ($1\leq k,l\leq e-1$).
By Case 5, we get two terms of the form $s_{3}t_{x}s_{3}t_{l}$ and
$s_{3}t_{x}s_{3}t_{l}s_{3}$. Multiplying them on the right by $t_{0}$ then by
$s_{3}$, we get that $s_{3}(a_{2}a_{3})$ obviously belongs to
Span$(\Lambda_{2}\Lambda_{3})$.

∎

In the sequel, we will indicate by (1) the operation that shifts the
underlined letters to the left, by (2) the operation that applies braid
relations, and by (3) the one that applies quadratic relations. The following
lemma is useful in the proofs of Lemmas 5.13, 5.15 and 5.16 below. Denote by
$S_{n-1}^{*}$ the set of the words over
$\\{t_{0},\cdots,t_{e-1},s_{3},\cdots,s_{n-1}\\}$.

######  Lemma 5.7.

Let $3\leq i\leq n$. We have $s_{n}\cdots s_{4}s_{3}^{2}s_{4}\cdots s_{i}$
belongs to Span$(S_{n-1}^{*}\Lambda_{n})$.

###### Proof.

If $i=3$, we have $s_{n}\cdots s_{4}s_{3}^{2}\in R_{0}s_{n}\cdots
s_{4}s_{3}+R_{0}s_{n}\cdots s_{4}$ (the last term is equal to $1$ if $n=3$).
If $i=4$, we have $s_{n}\cdots s_{4}s_{3}^{2}s_{4}\in R_{0}s_{n}\cdots
s_{4}s_{3}s_{4}+R_{0}s_{n}\cdots s_{4}^{2}\in R_{0}s_{3}s_{n}\cdots
s_{3}+R_{0}s_{n}\cdots s_{4}+R_{0}s_{n}\cdots s_{5}$. The last term is equal
to $1$ if $n=4$. Let $i\geq 5$. We have $s_{n}\cdots s_{4}s_{3}^{2}s_{4}\cdots
s_{i}$ belongs to $R_{0}s_{n}\cdots s_{4}s_{3}s_{4}\cdots
s_{i}+R_{0}s_{n}\cdots s_{5}s_{4}^{2}s_{5}\cdots s_{i}$. We apply the
quadratic relation $s_{4}^{2}=as_{4}+1$ to the second term and get
$R_{0}s_{n}\cdots s_{5}s_{4}s_{5}\cdots s_{i}+R_{0}s_{n}\cdots
s_{6}s_{5}^{2}s_{6}\cdots s_{i}$. And so on, we apply quadratic relations. We
get terms of the form $s_{n}\cdots s_{k+1}s_{k}s_{k+1}\cdots s_{i}$ with
$k+1\leq i$ and a term of the form $s_{n}\cdots s_{i+1}s_{i}s_{i-1}^{2}s_{i}$.
We have $s_{n}\cdots s_{i+1}s_{i}s_{i-1}^{2}s_{i}$ belongs to
$R_{0}s_{n}\cdots s_{i+1}s_{i}s_{i-1}s_{i}+R_{0}s_{n}\cdots
s_{i+1}s_{i}+R_{0}s_{n}\cdots s_{i+1}\subseteq\\\ R_{0}s_{i-1}s_{n}\cdots
s_{i-1}+R_{0}s_{n}\cdots s_{i+1}s_{i}+R_{0}s_{n}\cdots s_{i+1}$ (the last term
is equal to $1$ if $i=n$). Hence it belongs to Span$(S_{n-1}^{*}\Lambda_{n})$.
The other terms are of the form $s_{n}\cdots s_{k+1}s_{k}s_{k+1}\cdots s_{i}$
($k+1\leq i$). We have
$\begin{array}[]{ll}s_{n}\cdots\underline{s_{k+1}s_{k}s_{k+1}}\cdots
s_{i}&\stackrel{{\scriptstyle(2)}}{{=}}\\\ s_{n}\cdots
s_{k+2}\underline{s_{k}}s_{k+1}s_{k}\underline{s_{k+2}}\cdots
s_{i}&\stackrel{{\scriptstyle(1)}}{{=}}\\\
s_{k}s_{n}\cdots\underline{s_{k+2}s_{k+1}s_{k+2}}s_{k}s_{k+3}\cdots
s_{i}&\stackrel{{\scriptstyle(2)}}{{=}}\\\
s_{k}s_{n}\cdots\underline{s_{k+1}}s_{k+2}s_{k+1}s_{k}s_{k+3}\cdots
s_{i}&\stackrel{{\scriptstyle(1)}}{{=}}\end{array}$
$\begin{array}[]{l}s_{k}s_{k+1}s_{n}\cdots
s_{k+2}s_{k+1}s_{k}\underline{s_{k+3}}\cdots\underline{s_{i-1}}s_{i}.\end{array}$
We apply the same operations to $\underline{s_{k+3}}$, $\cdots$,
$\underline{s_{i-1}}$ and get
$\begin{array}[]{ll}s_{k}s_{k+1}\cdots s_{i-2}s_{n}\cdots
s_{k}\underline{s_{i}}&\stackrel{{\scriptstyle(1)}}{{=}}\\\ s_{k}s_{k+1}\cdots
s_{i-2}s_{n}\cdots\underline{s_{i}s_{i-1}s_{i}}s_{i-2}\cdots
s_{k}&\stackrel{{\scriptstyle(2)}}{{=}}\\\ s_{k}s_{k+1}\cdots
s_{i-2}s_{n}\cdots s_{i+1}\underline{s_{i-1}}s_{i}s_{i-1}s_{i-2}\cdots
s_{k}&\stackrel{{\scriptstyle(1)}}{{=}}\\\ s_{k}s_{k+1}\cdots
s_{i-1}s_{n}s_{n-1}\cdots s_{k},&\end{array}$
which belongs to Span$(S_{n-1}^{*}\Lambda_{n})$.

∎

######  Lemma 5.8.

If $a_{n-1}=s_{n-1}s_{n-2}\cdots s_{i}$ with $3\leq i\leq n-1$ and
$a_{n}=s_{n}s_{n-1}\cdots s_{i^{\prime}}$ with $3\leq i^{\prime}\leq n$, then
$s_{n}(a_{n-1}a_{n})$ belongs to Span$(\Lambda_{n-1}\Lambda_{n})$.

###### Proof.

_Suppose $i<i^{\prime}$._ We have $s_{n}(a_{n-1}a_{n})$ is equal to
$\begin{array}[]{ll}s_{n}s_{n-1}s_{n-2}\cdots
s_{i}\underline{s_{n}}s_{n-1}\cdots
s_{i^{\prime}}&\stackrel{{\scriptstyle(1)}}{{=}}\\\
\underline{s_{n}s_{n-1}s_{n}}s_{n-2}\cdots s_{i}s_{n-1}\cdots
s_{i^{\prime}}&\stackrel{{\scriptstyle(2)}}{{=}}\\\
s_{n-1}s_{n}s_{n-1}s_{n-2}\cdots s_{i}\underline{s_{n-1}}\cdots
s_{i^{\prime}}&\stackrel{{\scriptstyle(1)}}{{=}}\\\
s_{n-1}s_{n}\underline{s_{n-1}s_{n-2}s_{n-1}}\cdots s_{i}s_{n-2}\cdots
s_{i^{\prime}}&\stackrel{{\scriptstyle(2)}}{{=}}\\\
s_{n-1}s_{n}\underline{s_{n-2}}s_{n-1}s_{n-2}\cdots s_{i}s_{n-2}\cdots
s_{i^{\prime}}&\stackrel{{\scriptstyle(1)}}{{=}}\end{array}$
$\begin{array}[]{l}s_{n-1}s_{n-2}s_{n}s_{n-1}s_{n-2}\cdots
s_{i}\underline{s_{n-2}}\cdots\underline{s_{i^{\prime}}}.\end{array}$
We apply the same operations to the underlined letters
$\underline{s_{n-2}}\cdots\underline{s_{i^{\prime}}}$ in order to get
$s_{n-1}s_{n-2}\cdots s_{i^{\prime}-1}s_{n}s_{n-1}\cdots s_{i}$ which belongs
to Span$(\Lambda_{n-1}\Lambda_{n})$.

_Suppose $i\geq i^{\prime}$._ We have $s_{n}(a_{n-1}a_{n})$ is equal to
$s_{n}s_{n-1}\cdots s_{i}\underline{s_{n}}s_{n-1}\cdots s_{i^{\prime}}$. We
apply the operations (1) and (2) and get $s_{n-1}s_{n}s_{n-1}\cdots
s_{i}\underline{s_{n-1}}\cdots s_{i^{\prime}}$. Then we apply the same
operations to $\underline{s_{n-1}}$ and get $s_{n-1}s_{n-2}s_{n}s_{n-1}\cdots
s_{i}\underline{s_{n-2}\cdots s_{i^{\prime}}}$. Since $i\geq i^{\prime}$, we
write $s_{i+2}s_{i+1}s_{i}$ in $\underline{s_{n-2}\cdots s_{i^{\prime}}}$ and
get $s_{n-1}s_{n-2}s_{n}s_{n-1}\cdots
s_{i}\underline{s_{n-2}}\cdots\underline{s_{i+2}}s_{i+1}s_{i}\cdots
s_{i^{\prime}}$. Similarly, we apply the same operations to
$\underline{s_{n-2}}$, $\cdots$, $\underline{s_{i+2}}$ and get
$\begin{array}[]{ll}s_{n-1}\cdots
s_{i+1}s_{n}\cdots\underline{s_{i+1}s_{i}s_{i+1}}s_{i}\cdots
s_{i^{\prime}}&\stackrel{{\scriptstyle(2)}}{{=}}\\\ s_{n-1}\cdots
s_{i+1}s_{n}\cdots s_{i+2}\underline{s_{i}}s_{i+1}s_{i}^{2}s_{i-1}\cdots
s_{i^{\prime}}&\stackrel{{\scriptstyle(1)}}{{=}}\\\ s_{n-1}\cdots
s_{i}s_{n}\cdots s_{i+2}s_{i+1}\underline{s_{i}^{2}}s_{i-1}\cdots
s_{i^{\prime}}&\stackrel{{\scriptstyle(3)}}{{=}}\end{array}$
$\begin{array}[]{l}as_{n-1}\cdots s_{i}s_{n}\cdots s_{i+1}s_{i}s_{i-1}\cdots
s_{i^{\prime}}+s_{n-1}\cdots s_{i}s_{n}\cdots
s_{i+2}s_{i+1}\underline{s_{i-1}}\cdots\underline{s_{i^{\prime}}}.\end{array}$
The first term belongs to Span$(\Lambda_{n-1}\Lambda_{n})$. For the second
term, the underlined letters commute with $s_{n}\cdots s_{i+2}s_{i+1}$ hence
they are shifted to the left. We thus get $s_{n}(a_{n-1}a_{n})$ is equal to
$as_{n-1}\cdots s_{i}s_{n}\cdots s_{i^{\prime}}+s_{n-1}\cdots
s_{i^{\prime}}s_{n}\cdots s_{i+1}$ which belongs to
Span$(\Lambda_{n-1}\Lambda_{n})$.

∎

######  Lemma 5.9.

If $a_{n-1}=s_{n-1}\cdots s_{i}$ with $3\leq i\leq n-1$ and $a_{n}=s_{n}\cdots
s_{3}t_{k}$ with $0\leq k\leq e-1$, then $s_{n}(a_{n-1}a_{n})$ belongs to
Span$(\Lambda_{n-1}\Lambda_{n})$.

###### Proof.

This corresponds to the case $i^{\prime}=3$ in the proof of Lemma 5.8 with a
right multiplication by $t_{k}$ for $0\leq k\leq e-1$. Since $i\geq 3$, by the
case $i\geq i^{\prime}$ of Lemma 5.8, we have
$s_{n}(a_{n-1}a_{n})=as_{n-1}\cdots s_{i}s_{n}\cdots s_{3}t_{k}+s_{n-1}\cdots
s_{3}s_{n}\cdots s_{i+1}t_{k}$. In the second term, $t_{k}$ commutes with
$s_{n}\cdots s_{i+1}$ hence it is shifted to the left. We get
$s_{n}(a_{n-1}a_{n})=as_{n-1}\cdots s_{i}s_{n}\cdots s_{3}t_{k}+s_{n-1}\cdots
s_{3}t_{k}s_{n}\cdots s_{i+1}$ which belongs to
Span$(\Lambda_{n-1}\Lambda_{n})$.

∎

######  Lemma 5.10.

If $a_{n-1}=s_{n-1}\cdots s_{i}$ with $3\leq i\leq n-1$ and $a_{n}=s_{n}\cdots
s_{3}t_{k}s_{2}s_{3}\cdots s_{i^{\prime}}$ with $1\leq k\leq e-1$ and $2\leq
i^{\prime}\leq n$, then $s_{n}(a_{n-1}a_{n})$ belongs to
Span$(\Lambda_{n-1}\Lambda_{n})$.

###### Proof.

According to Lemma 5.9, we have
$s_{n}(a_{n-1}a_{n})=as_{n-1}\cdots s_{i}s_{n}\cdots s_{3}t_{k}s_{2}\cdots
s_{i^{\prime}}+s_{n-1}\cdots s_{3}t_{k}s_{n}\cdots s_{i+1}s_{2}\cdots
s_{i^{\prime}}$. The first term is an element of
Span$(\Lambda_{n-1}\Lambda_{n})$. We check that the second term also belongs
to Span$(\Lambda_{n-1}\Lambda_{n})$. Actually,

_If $i^{\prime}<i$_, the second term is equal to $s_{n-1}\cdots
s_{3}t_{k}s_{n}\cdots
s_{i+1}\underline{s_{2}}\cdots\underline{s_{i^{\prime}}}$.
The underlined letters commute with $s_{n}\cdots s_{i+1}$ and are shifted to
the left. We get $s_{n-1}\cdots s_{3}t_{k}s_{2}\cdots
s_{i^{\prime}}s_{n}\cdots s_{i+1}\in$ Span$(\Lambda_{n-1}\Lambda_{n})$.

_If $i^{\prime}\geq i$_, we write $s_{i-1}s_{i}s_{i+1}$ in $s_{2}\cdots
s_{i^{\prime}}$ and get $s_{n-1}\cdots s_{3}t_{k}s_{n}\cdots
s_{i+1}(s_{2}\cdots s_{i^{\prime}})=$
$\begin{array}[]{ll}s_{n-1}\cdots s_{3}t_{k}s_{n}\cdots
s_{i+1}(\underline{s_{2}}\cdots\underline{s_{i-1}}s_{i}s_{i+1}\cdots
s_{i^{\prime}})&\stackrel{{\scriptstyle(1)}}{{=}}\\\ s_{n-1}\cdots
s_{3}t_{k}s_{2}\cdots s_{i-1}s_{n}\cdots\underline{s_{i+1}(s_{i}s_{i+1}}\cdots
s_{i^{\prime}})&\stackrel{{\scriptstyle(2)}}{{=}}\\\ s_{n-1}\cdots
s_{3}t_{k}s_{2}\cdots
s_{i-1}s_{n}\cdots\underline{s_{i}}s_{i+1}s_{i}(s_{i+2}\cdots
s_{i^{\prime}})&\stackrel{{\scriptstyle(1)}}{{=}}\\\ s_{n-1}\cdots
s_{3}t_{k}s_{2}\cdots s_{i-1}s_{i}s_{n}\cdots
s_{i+1}s_{i}(\underline{s_{i+2}}\cdots
s_{i^{\prime}})&\stackrel{{\scriptstyle(1)}}{{=}}\\\ s_{n-1}\cdots
s_{3}t_{k}s_{2}\cdots
s_{i-1}s_{i}s_{n}\cdots\underline{s_{i+2}s_{i+1}s_{i+2}}s_{i}(s_{i+3}\cdots
s_{i^{\prime}})&\stackrel{{\scriptstyle(2)}}{{=}}\\\ s_{n-1}\cdots
s_{3}t_{k}s_{2}\cdots
s_{i-1}s_{i}s_{n}\cdots\underline{s_{i+1}}s_{i+2}s_{i+1}s_{i}(s_{i+3}\cdots
s_{i^{\prime}})&\stackrel{{\scriptstyle(1)}}{{=}}\end{array}$
$\begin{array}[]{l}s_{n-1}\cdots s_{3}t_{k}s_{2}\cdots s_{i}s_{i+1}s_{n}\cdots
s_{i+2}s_{i+1}s_{i}(\underline{s_{i+3}}\cdots\underline{s_{i^{\prime}}}).\end{array}$
We apply the same operations to the underlined letters $\underline{s_{i+3}}$,
$\cdots$, $\underline{s_{i^{\prime}}}$. We finally get $s_{n-1}\cdots
s_{3}t_{k}s_{2}\cdots s_{i^{\prime}-1}s_{n}\cdots s_{i}\in$
Span$(\Lambda_{n-1}\Lambda_{n})$.

∎

######  Lemma 5.11.

If $a_{n-1}=s_{n-1}\cdots s_{3}t_{k}$ with $0\leq k\leq e-1$ and
$a_{n}=s_{n}\cdots s_{i}$ with $3\leq i\leq n$, then $s_{n}(a_{n-1}a_{n})$
belongs to Span$(\Lambda_{n-1}\Lambda_{n})$.

###### Proof.

We have $s_{n}(a_{n-1}a_{n})$ is equal to
$\begin{array}[]{ll}s_{n}s_{n-1}\cdots s_{3}t_{k}\underline{s_{n}}\cdots
s_{i}&\stackrel{{\scriptstyle(1)}}{{=}}\\\ \underline{s_{n}s_{n-1}s_{n}}\cdots
s_{3}t_{k}s_{n-1}\cdots s_{i}&\stackrel{{\scriptstyle(2)}}{{=}}\\\
s_{n-1}s_{n}s_{n-1}\cdots s_{3}t_{k}\underline{s_{n-1}}\cdots
s_{i}&\stackrel{{\scriptstyle(1)}}{{=}}\\\
s_{n-1}s_{n}\underline{s_{n-1}s_{n-2}s_{n-1}}\cdots s_{3}t_{k}s_{n-2}\cdots
s_{i}&\stackrel{{\scriptstyle(2)}}{{=}}\\\
s_{n-1}s_{n}\underline{s_{n-2}}s_{n-1}s_{n-2}\cdots s_{3}t_{k}s_{n-2}\cdots
s_{i}&\stackrel{{\scriptstyle(1)}}{{=}}\\\ \end{array}$
$\begin{array}[]{l}s_{n-1}s_{n-2}s_{n}s_{n-1}\cdots
s_{3}t_{k}\underline{s_{n-2}}\cdots\underline{s_{i}}.\end{array}$
Now we apply the same operations for $\underline{s_{n-2}}$, $\cdots$,
$\underline{s_{i}}$.

_If $i=3$_, we get $s_{n-1}\cdots
s_{3}s_{n}s_{n-1}\cdots\underline{s_{3}t_{k}s_{3}}$. Next, we apply a braid
relation to get $s_{n-1}\cdots
s_{3}s_{n}s_{n-1}\cdots\underline{t_{k}}s_{3}t_{k}$, then we shift
$\underline{t_{k}}$ to the left and we finally get $s_{n-1}\cdots
s_{3}t_{k}s_{n}s_{n-1}\cdots s_{3}t_{k}$ which belongs to
Span$(\Lambda_{n-1}\Lambda_{n})$.

_If $i>3$_, we directly get $s_{n-1}\cdots s_{i}s_{i-1}s_{n}\cdots s_{3}t_{k}$
that also belongs to Span$(\Lambda_{n-1}\Lambda_{n})$.

∎

######  Lemma 5.12.

If $a_{n-1}=s_{n-1}\cdots s_{3}t_{k}$ with $0\leq k\leq e-1$ and
$a_{n}=s_{n}\cdots s_{3}t_{l}$ with $0\leq l\leq e-1$, then
$s_{n}(a_{n-1}a_{n})$ belongs to Span$(\Lambda_{n-1}\Lambda_{n})$.

###### Proof.

By Lemma 5.11, one can write $s_{n}(a_{n-1}a_{n})=s_{n-1}\cdots
s_{3}t_{k}s_{n}s_{n-1}\cdots s_{3}t_{k}t_{l}$. By Lemma 5.2 where we compute
$t_{k}t_{l}$, we directly deduce that $s_{n}(a_{n-1}a_{n})$ belongs to
Span$(\Lambda_{n-1}\Lambda_{n})$.

∎

######  Lemma 5.13.

If $a_{n-1}=s_{n-1}\cdots s_{3}t_{k}$ with $0\leq k\leq e-1$ and
$a_{n}=s_{n}\cdots s_{3}t_{l}s_{2}\cdots s_{i}$ with $2\leq i\leq n$ and
$1\leq l\leq e-1$, then $s_{n}(a_{n-1}a_{n})$ belongs to
Span$(S_{n-1}^{*}\Lambda_{n})$.

###### Proof.

By the previous lemma, we have $s_{n}(a_{n-1}a_{n})=s_{n-1}\cdots
s_{3}t_{k}s_{n}\cdots s_{3}t_{k}t_{l}(s_{2}\cdots s_{i})$. By Lemma 5.2, the
case $i=2$ is obvious. Suppose $i\geq 3$. After replacing $t_{k}t_{l}$ by its
value given in Lemma 5.2, we have two different terms in $s_{n}(a_{n-1}a_{n})$
of the form $s_{n-1}\cdots s_{3}t_{k}s_{n}\cdots s_{3}t_{x}(s_{2}\cdots
s_{i})$ with $0\leq x\leq e-1$ and of the form
$s_{n-1}\cdots s_{3}t_{k}s_{n}\cdots s_{3}t_{x}(s_{3}\cdots s_{i})$ with
$0\leq x\leq e-1$.

For terms of the form $s_{n-1}\cdots s_{3}t_{k}s_{n}\cdots
s_{3}t_{x}(s_{3}\cdots s_{i})$ with $0\leq x\leq e-1$, we have
$\begin{array}[]{ll}s_{n-1}\cdots
s_{3}t_{k}s_{n}\cdots\underline{s_{3}t_{x}(s_{3}}\cdots
s_{i})&\stackrel{{\scriptstyle(2)}}{{=}}\\\ s_{n-1}\cdots
s_{3}t_{k}s_{n}\cdots\underline{t_{x}}s_{3}t_{x}(s_{4}\cdots
s_{i})&\stackrel{{\scriptstyle(1)}}{{=}}\\\ s_{n-1}\cdots
s_{3}t_{k}t_{x}s_{n}\cdots s_{3}t_{x}(\underline{s_{4}}\cdots
s_{i})&\stackrel{{\scriptstyle(1)}}{{=}}\\\ s_{n-1}\cdots
s_{3}t_{k}t_{x}s_{n}\cdots\underline{s_{4}s_{3}s_{4}}t_{x}(s_{5}\cdots
s_{i})&\stackrel{{\scriptstyle(2)}}{{=}}\\\ s_{n-1}\cdots
s_{3}t_{k}t_{x}s_{n}\cdots\underline{s_{3}}s_{4}s_{3}t_{x}(s_{5}\cdots
s_{i})&\stackrel{{\scriptstyle(1)}}{{=}}\\\ \end{array}$
$\begin{array}[]{l}s_{n-1}\cdots s_{3}t_{k}t_{x}s_{3}s_{n}\cdots
s_{3}t_{x}(\underline{s_{5}}\cdots\underline{s_{i}}).\end{array}$
We apply the same operations for the underlined letters to get
$s_{n-1}\cdots s_{3}t_{k}t_{x}s_{3}\cdots s_{i-1}\underline{s_{n}\cdots
s_{3}t_{x}}$ which belongs to Span$(S_{n-1}^{*}\Lambda_{n})$.

Consider the terms of the form $s_{n-1}\cdots s_{3}t_{k}s_{n}\cdots
s_{3}t_{x}(s_{2}\cdots s_{i})$ with $0\leq x\leq e-1$.
If $x\neq 0$, they belong to Span$(\Lambda_{n-1}\Lambda_{n})$.
If $x=0$, we have $s_{n-1}\cdots s_{3}t_{k}s_{n}\cdots
s_{3}t_{0}(s_{2}s_{3}\cdots s_{i})\in R_{0}s_{n-1}\cdots s_{3}t_{k}s_{n}\cdots
s_{3}t_{0}s_{3}\cdots s_{i}+R_{0}s_{n-1}\cdots s_{3}t_{k}s_{n}\cdots
s_{4}s_{3}^{2}s_{4}\cdots s_{i}$. The first term correspond to the previous
case (with $x=0$) and then belongs to Span$(S_{n-1}^{*}\Lambda_{n})$. By Lemma
5.7, the second term also belongs to Span$(S_{n-1}^{*}\Lambda_{n})$.

∎

######  Lemma 5.14.

If $a_{n-1}=s_{n-1}\cdots s_{3}t_{k}s_{2}\cdots s_{i}$ with $2\leq i\leq n-1$,
$1\leq k\leq e-1$ and $a_{n}=s_{n}\cdots s_{i^{\prime}}$ with $3\leq
i^{\prime}\leq n$, then $s_{n}(a_{n-1}a_{n})$ belongs to
Span$(\Lambda_{n-1}\Lambda_{n})$.

###### Proof.

_Suppose $i<i^{\prime}$_. We have $s_{n}(a_{n-1}a_{n})$ is equal to
$\begin{array}[]{ll}s_{n}\cdots s_{3}t_{k}s_{2}\cdots
s_{i}\underline{s_{n}}\cdots
s_{i^{\prime}}&\stackrel{{\scriptstyle(1)}}{{=}}\\\
\underline{s_{n}s_{n-1}s_{n}}\cdots s_{3}t_{k}s_{2}\cdots s_{i}s_{n-1}\cdots
s_{i^{\prime}}&\stackrel{{\scriptstyle(2)}}{{=}}\\\ s_{n-1}s_{n}s_{n-1}\cdots
s_{3}t_{k}s_{2}\cdots s_{i}\underline{s_{n-1}}\cdots
s_{i^{\prime}}&\stackrel{{\scriptstyle(1)}}{{=}}\\\
s_{n-1}s_{n}\underline{s_{n-1}s_{n-2}s_{n-1}}\cdots s_{3}t_{k}s_{2}\cdots
s_{i}s_{n-2}\cdots s_{i^{\prime}}&\stackrel{{\scriptstyle(2)}}{{=}}\\\
s_{n-1}s_{n}\underline{s_{n-2}}s_{n-1}s_{n-2}\cdots s_{3}t_{k}s_{2}\cdots
s_{i}s_{n-2}\cdots s_{i^{\prime}}&\stackrel{{\scriptstyle(1)}}{{=}}\\\
\end{array}$
$\begin{array}[]{l}s_{n-1}s_{n-2}s_{n}s_{n-1}s_{n-2}\cdots
s_{3}t_{k}s_{2}\cdots
s_{i}\underline{s_{n-2}}\cdots\underline{s_{i^{\prime}+1}}s_{i^{\prime}}.\end{array}$
We apply the same operations to the underlined letters and
we get $s_{n-1}\cdots s_{i^{\prime}}s_{n}\cdots s_{3}t_{k}s_{2}\cdots
s_{i}s_{i^{\prime}}$.
_If $i^{\prime}=i+1$_, we directly have $s_{n}(a_{n-1}a_{n})\in$
Span$(\Lambda_{n-1}\Lambda_{n})$.
_If $i^{\prime}>i+1$_, then we write
$s_{i^{\prime}+1}s_{i^{\prime}}s_{i^{\prime}-1}$ in the underlined word of
$s_{n-1}\cdots s_{i^{\prime}}\underline{s_{n}\cdots s_{3}}t_{k}s_{2}\cdots
s_{i}s_{i^{\prime}}$ and get
$\begin{array}[]{ll}s_{n-1}\cdots s_{i^{\prime}}s_{n}\cdots
s_{i^{\prime}+1}s_{i^{\prime}}s_{i^{\prime}-1}\cdots s_{3}t_{k}s_{2}\cdots
s_{i}\underline{s_{i^{\prime}}}&\stackrel{{\scriptstyle(1)}}{{=}}\\\
s_{n-1}\cdots s_{i^{\prime}}s_{n}\cdots
s_{i^{\prime}+1}\underline{s_{i^{\prime}}s_{i^{\prime}-1}s_{i^{\prime}}}\cdots
s_{3}t_{k}s_{2}\cdots s_{i}&\stackrel{{\scriptstyle(2)}}{{=}}\\\ s_{n-1}\cdots
s_{i^{\prime}}s_{n}\cdots
s_{i^{\prime}+1}\underline{s_{i^{\prime}-1}}s_{i^{\prime}}s_{i^{\prime}-1}\cdots
s_{3}t_{k}s_{2}\cdots s_{i}&\stackrel{{\scriptstyle(1)}}{{=}}\\\ \end{array}$
$\begin{array}[]{l}s_{n-1}\cdots s_{i^{\prime}-1}s_{n}\cdots
s_{3}t_{k}s_{2}\cdots s_{i}\end{array}$ which belongs to
Span$(\Lambda_{n-1}\Lambda_{n})$.

_Suppose $i\geq i^{\prime}$_. We have $s_{n}(a_{n-1}a_{n})$ is equal to
$s_{n}\cdots s_{3}t_{k}s_{2}\cdots s_{i}\underline{s_{n}}\cdots
s_{i^{\prime}}$. We shift $\underline{s_{n}}$ to the left and apply a braid
relation to get $s_{n-1}s_{n}s_{n-1}\cdots s_{3}t_{k}s_{2}\cdots
s_{i}\underline{s_{n-1}\cdots s_{i^{\prime}}}$. Write $s_{i+2}s_{i+1}$ in the
underlined word to get $s_{n-1}s_{n}s_{n-1}\cdots s_{3}t_{k}s_{2}\cdots
s_{i}\underline{s_{n-1}}\cdots\underline{s_{i+2}}s_{i+1}\cdots
s_{i^{\prime}}$. We apply the same operations to the underlined letters to get
$\begin{array}[]{ll}s_{n-1}\cdots s_{i+1}s_{n}\cdots
s_{3}t_{k}s_{2}\cdots\underline{s_{i}s_{i+1}s_{i}}s_{i-1}\cdots
s_{i^{\prime}}&\stackrel{{\scriptstyle(2)}}{{=}}\\\ s_{n-1}\cdots
s_{i+1}s_{n}\cdots
s_{3}t_{k}s_{2}\cdots\underline{s_{i+1}}s_{i}s_{i+1}s_{i-1}\cdots
s_{i^{\prime}}&\stackrel{{\scriptstyle(1)}}{{=}}\\\ \end{array}$
$\begin{array}[]{l}s_{n-1}\cdots s_{i}s_{n}\cdots s_{3}t_{k}s_{2}\cdots
s_{i-1}s_{i}s_{i+1}s_{i-1}\cdots s_{i^{\prime}}\end{array}$ (The details of
the computation is left to the reader). Then we have
$\begin{array}[]{ll}s_{n-1}\cdots s_{i}s_{n}\cdots s_{3}t_{k}s_{2}\cdots
s_{i-1}s_{i}s_{i+1}\underline{s_{i-1}}\cdots
s_{i^{\prime}}&\stackrel{{\scriptstyle(1)}}{{=}}\\\ s_{n-1}\cdots
s_{i}s_{n}\cdots
s_{3}t_{k}s_{2}\cdots\underline{s_{i-1}s_{i}s_{i-1}}s_{i+1}s_{i-2}\cdots
s_{i^{\prime}}&\stackrel{{\scriptstyle(2)}}{{=}}\\\ s_{n-1}\cdots
s_{i}s_{n}\cdots
s_{3}t_{k}s_{2}\cdots\underline{s_{i}}s_{i-1}s_{i}s_{i+1}s_{i-2}\cdots
s_{i^{\prime}}&\stackrel{{\scriptstyle(1)}}{{=}}\\\ \end{array}$
$\begin{array}[]{l}s_{n-1}\cdots s_{i-1}s_{n}\cdots s_{3}t_{k}s_{2}\cdots
s_{i-2}s_{i-1}s_{i}s_{i+1}\underline{s_{i-2}}\cdots\underline{s_{i^{\prime}+1}}s_{i^{\prime}}.\end{array}$
We apply the same operations to the underlined letters and we finally get
$s_{n-1}\cdots s_{i^{\prime}+1}s_{n}\cdots
s_{3}t_{k}\underline{s_{2}s_{3}\cdots s_{i}s_{i+1}}s_{i^{\prime}}$. We write
$s_{i^{\prime}-1}s_{i^{\prime}}s_{i^{\prime}+1}$ in the underlined word and
get $s_{n-1}\cdots s_{i^{\prime}+1}s_{n}\cdots s_{3}t_{k}s_{2}s_{3}\cdots
s_{i^{\prime}-1}s_{i^{\prime}}s_{i^{\prime}+1}\cdots
s_{i}s_{i+1}\underline{s_{i^{\prime}}}$. We shift $\underline{s_{i^{\prime}}}$
to the left. We get $s_{n-1}\cdots s_{i^{\prime}+1}s_{n}\cdots
s_{3}t_{k}s_{2}s_{3}\cdots
s_{i^{\prime}-1}\underline{s_{i^{\prime}}s_{i^{\prime}+1}s_{i^{\prime}}}\cdots
s_{i}s_{i+1}$. We apply a braid relation and get $s_{n-1}\cdots
s_{i^{\prime}+1}s_{n}\cdots s_{3}t_{k}s_{2}s_{3}\cdots
s_{i^{\prime}-1}\underline{s_{i^{\prime}+1}}s_{i^{\prime}}s_{i^{\prime}+1}\cdots
s_{i}s_{i+1}$. Now we shift $\underline{s_{i^{\prime}+1}}$ to the left and get
$\begin{array}[]{ll}s_{n-1}\cdots
s_{i^{\prime}+1}s_{n}\cdots\underline{s_{i^{\prime}+1}s_{i^{\prime}}s_{i^{\prime}+1}}s_{i^{\prime}-1}\cdots
s_{3}t_{k}s_{2}\cdots s_{i+1}&\stackrel{{\scriptstyle(2)}}{{=}}\\\
s_{n-1}\cdots
s_{i^{\prime}+1}s_{n}\cdots\underline{s_{i^{\prime}}}s_{i^{\prime}+1}s_{i^{\prime}}s_{i^{\prime}-1}\cdots
s_{3}t_{k}s_{2}\cdots s_{i+1}&\stackrel{{\scriptstyle(1)}}{{=}}\\\
s_{n-1}\cdots s_{i^{\prime}+1}s_{i^{\prime}}s_{n}\cdots
s_{i^{\prime}+1}s_{i^{\prime}}s_{i^{\prime}-1}\cdots s_{3}t_{k}s_{2}\cdots
s_{i+1}&=\\\ \end{array}$
$\begin{array}[]{l}s_{n-1}\cdots s_{i^{\prime}}s_{n}\cdots
s_{3}t_{k}s_{2}\cdots s_{i+1},\end{array}$ which belongs to
Span$(\Lambda_{n-1}\Lambda_{n})$.

∎

######  Lemma 5.15.

If $a_{n-1}=s_{n-1}\cdots s_{3}t_{k}s_{2}\cdots s_{i}$ with $2\leq i\leq n-1$,
$1\leq k\leq e-1$ and $a_{n}=s_{n}s_{n-1}\cdots s_{3}t_{l}$ with $0\leq l\leq
e-1$, then $s_{n}(a_{n-1}a_{n})$ belongs to Span$(S_{n-1}^{*}\Lambda_{n})$.

###### Proof.

By the final result of the computations in Lemma 5.14, we have
$s_{n}(a_{n-1}a_{n})$ is equal to $s_{n-1}\cdots s_{3}s_{n}\cdots
s_{3}t_{k}s_{2}s_{3}\cdots s_{i+1}\underline{t_{l}}$. We shift
$\underline{t_{l}}$ to the left and get
$s_{n-1}\cdots s_{3}s_{n}\cdots s_{3}t_{k}s_{2}s_{3}t_{l}\cdots s_{i+1}$. By
Case 5 of Proposition 5.6, we have to deal with the following two terms:

  * •

$s_{n-1}\cdots s_{3}s_{n}\cdots s_{3}t_{x}s_{3}t_{l}s_{4}\cdots s_{i+1}$ and

  * •

$s_{n-1}\cdots s_{3}s_{n}\cdots s_{3}t_{x}s_{3}t_{l}s_{3}s_{4}\cdots s_{i+1}$
with $1\leq x,l\leq e-1$.

The first term is of the form
$\begin{array}[]{ll}s_{n-1}\cdots
s_{3}s_{n}\cdots\underline{s_{3}t_{x}s_{3}}t_{l}s_{4}\cdots
s_{i+1}&\stackrel{{\scriptstyle(2)}}{{=}}\\\ s_{n-1}\cdots s_{3}s_{n}\cdots
s_{4}\underline{t_{x}}s_{3}t_{x}t_{l}s_{4}\cdots
s_{i+1}&\stackrel{{\scriptstyle(1)}}{{=}}\\\ s_{n-1}\cdots
s_{3}t_{x}s_{n}\cdots s_{3}t_{x}t_{l}\underline{s_{4}}\cdots
s_{i+1}&\stackrel{{\scriptstyle(1)}}{{=}}\\\ s_{n-1}\cdots
s_{3}t_{x}s_{n}\cdots\underline{s_{4}s_{3}s_{4}}t_{x}t_{l}s_{5}\cdots
s_{i+1}&\stackrel{{\scriptstyle(2)}}{{=}}\\\ s_{n-1}\cdots
s_{3}t_{x}s_{n}\cdots\underline{s_{3}}s_{4}s_{3}t_{x}t_{l}s_{5}\cdots
s_{i+1}&\stackrel{{\scriptstyle(1)}}{{=}}\\\ \end{array}$
$\begin{array}[]{l}s_{n-1}\cdots s_{3}t_{x}s_{3}s_{n}\cdots
s_{4}s_{3}t_{x}t_{l}\underline{s_{5}}\cdots\underline{s_{i+2}}s_{i+1}.\end{array}$
We apply the same operations to the underlined letters, we get $s_{n-1}\cdots
s_{3}t_{x}s_{3}\cdots s_{i-1}s_{n}\cdots
s_{4}s_{3}t_{x}t_{l}\underline{s_{i+1}}$. Finally, we shift
$\underline{s_{i+1}}$ to the left and get $s_{n-1}\cdots s_{3}t_{x}s_{3}\cdots
s_{i}s_{n}\cdots s_{4}s_{3}t_{x}t_{l}$. Since $2\leq i\leq n-1$ and by the
computation of $t_{x}t_{l}$ in Lemma 5.2, the lemma is satisfied for this
case.
The second term is equal to
$\begin{array}[]{ll}s_{n-1}\cdots
s_{3}s_{n}\cdots\underline{s_{3}t_{x}s_{3}}t_{l}s_{3}s_{4}\cdots
s_{i+1}&\stackrel{{\scriptstyle(2)}}{{=}}\\\ s_{n-1}\cdots
s_{3}s_{n}\cdots\underline{t_{x}}s_{3}t_{x}t_{l}s_{3}s_{4}\cdots
s_{i+1}&\stackrel{{\scriptstyle(1)}}{{=}}\\\ \end{array}$
$\begin{array}[]{l}s_{n-1}\cdots s_{3}t_{x}s_{n}\cdots
s_{3}t_{x}t_{l}s_{3}s_{4}\cdots s_{i+1}.\end{array}$ We replace $t_{x}t_{l}$
by its value given in Lemma 5.2, we get terms of the three following forms:

  * •

$s_{n-1}\cdots s_{3}t_{x}s_{n}\cdots s_{3}t_{m}t_{0}s_{3}s_{4}\cdots s_{i+1}$
with $1\leq m\leq e-1$,

  * •

$s_{n-1}\cdots s_{3}t_{x}s_{n}\cdots s_{3}t_{m}s_{3}s_{4}\cdots s_{i+1}$ with
$0\leq m\leq e-1$,

  * •

$s_{n-1}\cdots s_{3}t_{x}s_{n}\cdots s_{4}s_{3}^{2}s_{4}\cdots s_{i+1}$.

The first term belongs to Span$(S_{n-1}^{*}\Lambda_{n})$. The third term also
belongs to Span$(S_{n-1}^{*}\Lambda_{n})$. This is done by using the
computation in the proof of Lemma 5.7. For the second term, we have
$\begin{array}[]{ll}s_{n-1}\cdots s_{3}t_{x}s_{n}\cdots
s_{4}\underline{s_{3}t_{m}s_{3}}s_{4}\cdots
s_{i+1}&\stackrel{{\scriptstyle(2)}}{{=}}\\\ s_{n-1}\cdots
s_{3}t_{x}s_{n}\cdots\underline{s_{4}t_{m}}s_{3}t_{m}\underline{s_{4}}\cdots
s_{i+1}&\stackrel{{\scriptstyle(1)}}{{=}}\\\ s_{n-1}\cdots
s_{3}t_{x}t_{m}s_{n}\cdots\underline{s_{4}s_{3}s_{4}}t_{m}s_{5}\cdots
s_{i+1}&\stackrel{{\scriptstyle(2)}}{{=}}\\\ s_{n-1}\cdots
s_{3}t_{x}t_{m}s_{n}\cdots\underline{s_{3}}s_{4}s_{3}t_{m}s_{5}\cdots
s_{i+1}&\stackrel{{\scriptstyle(1)}}{{=}}\\\ \end{array}$
$\begin{array}[]{l}s_{n-1}\cdots s_{3}t_{x}t_{m}s_{3}s_{n}\cdots
s_{4}s_{3}t_{m}\underline{s_{5}}\cdots\underline{s_{i+2}}s_{i+1}.\end{array}$
We apply the same operations to the underlined letters and get $s_{n-1}\cdots
s_{3}t_{x}t_{m}s_{3}\cdots s_{i-1}s_{n}\cdots s_{3}t_{m}s_{i+1}$. Now we shift
$\underline{s_{i+1}}$ to the left and finally get $s_{n-1}\cdots
s_{3}t_{x}t_{m}s_{3}\cdots s_{i}\underline{s_{n}\cdots s_{3}t_{m}}$ with
$2\leq i\leq n-1$ which belongs to Span$(S_{n-1}^{*}\Lambda_{n})$.
Note that for $i=2$, we get terms that are equal to the itemized terms (given
at the beginning of this proof) after replacing $s_{4}\cdots s_{i+1}$ by $1$.

∎

######  Lemma 5.16.

If $a_{n-1}=s_{n-1}\cdots s_{3}t_{k}s_{2}\cdots s_{i}$ with $2\leq i\leq n-1$,
$1\leq k\leq e-1$ and $a_{n}=s_{n}\cdots s_{3}t_{l}s_{2}\cdots s_{i^{\prime}}$
with $1\leq l\leq e-1$ and $2\leq i^{\prime}\leq n$, then
$s_{n}(a_{n-1}a_{n})$ belongs to Span$(S_{n-1}^{*}\Lambda_{n})$.

###### Proof.

According to the computation in the proof of Lemma 5.15, we get the following
possible terms. They appear in the proof of Lemma 5.15 in the following order.

  1. 1.

$s_{n}\cdots s_{3}t_{x}t_{l}$ with $0\leq x,l\leq e-1$,

  2. 2.

$s_{n}\cdots s_{3}t_{m}t_{0}s_{3}\cdots s_{i+1}$ with $1\leq m\leq e-1$,

  3. 3.

$s_{n}\cdots s_{3}t_{m}$ with $0\leq m\leq e-1$,

  4. 4.

$s_{n}\cdots s_{4}s_{3}^{2}s_{4}\cdots s_{i+1}$

We show that the product on the right by $s_{2}\cdots s_{i^{\prime}}$ of each
of the previous terms belongs to Span$(S_{n-1}^{*}\Lambda_{n})$.

_Case 1_. Consider the first term $s_{n}\cdots s_{3}t_{x}t_{l}(s_{2}\cdots
s_{i^{\prime}})$ with $0\leq x,l\leq e-1$. We replace $t_{x}t_{l}$ by its
decomposition given in Lemma 5.2, we get these terms

  * •

$s_{n}\cdots s_{3}t_{m}t_{0}s_{3}\cdots s_{i^{\prime}}$ with $1\leq m\leq
e-1$,

  * •

$s_{n}\cdots s_{3}t_{m}s_{3}\cdots s_{i^{\prime}}$ with $0\leq m\leq e-1$,

  * •

$s_{n}\cdots s_{4}s_{3}^{2}s_{4}\cdots s_{i^{\prime}}$.

The first term belongs to Span$(S_{n-1}^{*}\Lambda_{n})$. The third one is
done in Lemma 5.7. For the second one, we have
$\begin{array}[]{ll}s_{n}\cdots\underline{s_{3}t_{m}s_{3}}\cdots
s_{i^{\prime}}&\stackrel{{\scriptstyle(2)}}{{=}}\\\
s_{n}\cdots\underline{t_{m}}s_{3}t_{m}\underline{s_{4}}\cdots
s_{i^{\prime}}&\stackrel{{\scriptstyle(1)}}{{=}}\\\
t_{m}s_{n}\cdots\underline{s_{4}s_{3}s_{4}}t_{m}s_{5}\cdots
s_{i^{\prime}}&\stackrel{{\scriptstyle(2)}}{{=}}\\\
t_{m}s_{n}\cdots\underline{s_{3}}s_{4}s_{3}t_{m}s_{5}\cdots
s_{i^{\prime}}&\stackrel{{\scriptstyle(1)}}{{=}}\\\ \end{array}$
$\begin{array}[]{l}t_{m}s_{3}s_{n}\cdots
s_{4}s_{3}t_{m}\underline{s_{5}}\cdots\underline{s_{i^{\prime}-1}}s_{i^{\prime}}.\end{array}$
We apply the same operations to $\underline{s_{5}}$, $\cdots$,
$\underline{s_{i^{\prime}-1}}$ and get $t_{m}s_{3}\cdots
s_{i^{\prime}-2}s_{n}\cdots s_{3}t_{m}\underline{s_{i^{\prime}}}$. We shift
$\underline{s_{i^{\prime}}}$ to the left and finally get
$t_{m}s_{3}\cdots s_{i^{\prime}-1}\underline{s_{n}\cdots s_{3}t_{m}}$ which
belongs to Span$(S_{n-1}^{*}\Lambda_{n})$.

We now consider _Case 3_ because we use the computation we made in Case 1. In
this case, the term is of the form $s_{n}\cdots s_{3}t_{m}(s_{2}\cdots
s_{i^{\prime}})$ with $0\leq m\leq e-1$. If $m\neq 0$, then it belongs to
Span$(S_{n-1}^{*}\Lambda_{n})$. If $m=0$, we get two terms $s_{n}\cdots
s_{3}t_{0}s_{3}\cdots s_{i^{\prime}}$ and $s_{n}\cdots
s_{4}s_{3}^{2}s_{4}\cdots s_{i^{\prime}}$. The first term is done in Case 1.
The second term is done in Lemma 5.7.

Consider _Case 4_. We replace $s_{n}\cdots s_{4}s_{3}^{2}s_{4}\cdots s_{i+1}$
by its decomposition given by the computation in the proof of Lemma 5.7. We
multiply each term of the decomposition by $s_{2}\cdots s_{i^{\prime}}$ on the
right and we prove that it belongs to Span$(S_{n-1}^{*}\Lambda_{n})$ in the
same way as the proof of Lemma 5.10.

Finally, it remains to show that the term corresponding to _Case 2_ belongs to
Span$(S_{n-1}^{*}\Lambda_{n})$. It is of the form

$s_{n}\cdots s_{3}t_{m}t_{0}s_{3}\cdots s_{i+1}(s_{2}\cdots s_{i^{\prime}})$
with $1\leq m\leq e-1$.

_Suppose $i^{\prime}\leq i$_. We have
$\begin{array}[]{ll}s_{n}\cdots s_{3}t_{m}s_{2}s_{3}\cdots
s_{i+1}\underline{s_{2}}\cdots
s_{i^{\prime}}&\stackrel{{\scriptstyle(1)}}{{=}}\\\ s_{n}\cdots
s_{3}t_{m}\underline{s_{2}s_{3}s_{2}}s_{4}\cdots s_{i+1}s_{3}\cdots
s_{i^{\prime}}&\stackrel{{\scriptstyle(2)}}{{=}}\end{array}$

$\begin{array}[]{ll}s_{n}\cdots\underline{s_{3}t_{m}s_{3}}s_{2}s_{3}s_{4}\cdots
s_{i+1}s_{3}\cdots s_{i^{\prime}}&\stackrel{{\scriptstyle(2)}}{{=}}\\\
s_{n}\cdots\underline{t_{m}}s_{3}t_{m}s_{2}s_{3}s_{4}\cdots s_{i+1}s_{3}\cdots
s_{i^{\prime}}&\stackrel{{\scriptstyle(1)}}{{=}}\\\ t_{m}s_{n}\cdots
s_{3}t_{m}s_{2}s_{3}s_{4}\cdots s_{i+1}\underline{s_{3}}\cdots
s_{i^{\prime}}&\stackrel{{\scriptstyle(1)}}{{=}}\\\ t_{m}s_{n}\cdots
s_{3}t_{m}s_{2}\underline{s_{3}s_{4}s_{3}}s_{5}\cdots s_{i+1}s_{4}\cdots
s_{i^{\prime}}&\stackrel{{\scriptstyle(2)}}{{=}}\\\ t_{m}s_{n}\cdots
s_{3}t_{m}s_{2}\underline{s_{4}}s_{3}s_{4}s_{5}\cdots s_{i+1}s_{4}\cdots
s_{i^{\prime}}&\stackrel{{\scriptstyle(1)}}{{=}}\\\
t_{m}s_{n}\cdots\underline{s_{4}s_{3}s_{4}}t_{m}s_{2}s_{3}s_{4}s_{5}\cdots
s_{i+1}s_{4}\cdots s_{i^{\prime}}&\stackrel{{\scriptstyle(2)}}{{=}}\\\
t_{m}s_{n}\cdots\underline{s_{3}}s_{4}s_{3}t_{m}s_{2}s_{3}s_{4}s_{5}\cdots
s_{i+1}s_{4}\cdots s_{i^{\prime}}&\stackrel{{\scriptstyle(1)}}{{=}}\\\
t_{m}s_{3}s_{n}\cdots s_{4}s_{3}t_{m}s_{2}s_{3}s_{4}s_{5}\cdots
s_{i+1}\underline{s_{4}}\cdots\underline{s_{i^{\prime}-1}}s_{i^{\prime}}.\end{array}$
We apply the same operations to $\underline{s_{4}}$, $\cdots$,
$\underline{s_{i^{\prime}-1}}$ to get
$t_{m}s_{3}\cdots s_{i^{\prime}-1}s_{n}\cdots s_{3}t_{m}s_{2}s_{3}\cdots
s_{i}s_{i+1}\underline{s_{i^{\prime}}}$. We shift $\underline{s_{i^{\prime}}}$
to the left and finally get
$t_{m}s_{3}\cdots s_{i^{\prime}}s_{n}\cdots s_{3}t_{m}s_{2}s_{3}\cdots
s_{i}s_{i+1}$. Since $i^{\prime}\leq i\leq n-1$, this term satisfies the
property of the lemma.

_Suppose $i^{\prime}>i$_. As previously, we have
$\begin{array}[]{ll}s_{n}\cdots s_{3}t_{m}s_{2}s_{3}\cdots
s_{i+1}\underline{s_{2}}\cdots
s_{i^{\prime}}&\stackrel{{\scriptstyle(1)}}{{=}}\\\ t_{m}s_{n}\cdots
s_{3}t_{m}s_{2}s_{3}\cdots s_{i+1}\underline{s_{3}}\cdots
s_{i^{\prime}}&\stackrel{{\scriptstyle(1)}}{{=}}\\\ t_{m}s_{3}s_{n}\cdots
s_{3}t_{m}s_{2}s_{3}\cdots s_{i+1}s_{4}\cdots s_{i^{\prime}}.&\\\ \end{array}$
Now we write $s_{i}s_{i+1}$ in $s_{4}\cdots s_{i^{\prime}}$ and get
$t_{m}s_{3}s_{n}\cdots s_{3}t_{m}s_{2}s_{3}\cdots
s_{i+1}\underline{s_{4}}\cdots\underline{s_{i}}s_{i+1}\cdots s_{i^{\prime}}$.
We apply the same operations to $\underline{s_{4}}$, $\cdots$,
$\underline{s_{i}}$ to get
$t_{m}s_{3}\cdots s_{i}s_{n}\cdots s_{3}t_{m}s_{2}s_{3}\cdots
s_{i}s_{i+1}^{2}s_{i+2}\cdots s_{i^{\prime}}$. Applying a quadratic relation,
we finally get $at_{m}s_{3}\cdots s_{i}s_{n}\cdots s_{3}t_{m}s_{2}s_{3}\cdots
s_{i^{\prime}}+t_{m}s_{3}\cdots s_{i}s_{n}\cdots s_{3}t_{m}s_{2}s_{3}\cdots
s_{i}s_{i+2}\cdots s_{i^{\prime}}$.
The first term satisfies the property of the lemma.
For the second term, we write $s_{i+2}s_{i+1}$ in $\underline{s_{n}\cdots
s_{3}}$ of
$t_{m}s_{3}\cdots s_{i}\underline{s_{n}\cdots s_{3}}t_{m}s_{2}s_{3}\cdots
s_{i}s_{i+2}\cdots s_{i^{\prime}}$ and get
$\begin{array}[]{ll}t_{m}s_{3}\cdots s_{i}s_{n}\cdots s_{i+2}s_{i+1}\cdots
s_{3}t_{m}s_{2}s_{3}\cdots s_{i}\underline{s_{i+2}}\cdots
s_{i^{\prime}}&\stackrel{{\scriptstyle(1)}}{{=}}\\\ t_{m}s_{3}\cdots
s_{i}s_{n}\cdots\underline{s_{i+2}s_{i+1}s_{i+2}}\cdots
s_{3}t_{m}s_{2}s_{3}\cdots s_{i}s_{i+3}\cdots
s_{i^{\prime}}&\stackrel{{\scriptstyle(2)}}{{=}}\\\ t_{m}s_{3}\cdots
s_{i}s_{n}\cdots\underline{s_{i+1}}s_{i+2}s_{i+1}\cdots
s_{3}t_{m}s_{2}s_{3}\cdots s_{i}s_{i+3}\cdots
s_{i^{\prime}}&\stackrel{{\scriptstyle(1)}}{{=}}\\\ \end{array}$
$\begin{array}[]{l}t_{m}s_{3}\cdots s_{i+1}s_{n}\cdots
s_{3}t_{m}s_{2}s_{3}\cdots
s_{i}\underline{s_{i+3}}\cdots\underline{s_{i^{\prime}}}.\end{array}$
We apply the same operations to $\underline{s_{i+3}}$, $\cdots$,
$\underline{s_{i^{\prime}}}$ and finally get
$t_{m}s_{3}\cdots s_{i^{\prime}-1}s_{n}\cdots s_{3}t_{m}s_{2}s_{3}\cdots
s_{i}$. Since $i^{\prime}-1\leq n-1$, this term belongs to
Span$(S_{n-1}^{*}\Lambda_{n})$.

∎

As a consequence of Theorem 5.1, by the second item of Proposition 2.3 of
[14], we get another proof of the BMR freeness conjecture (see Theorem 2.3)
for the complex reflection groups $G(e,e,n)$.

######  Remark 5.17.

Our basis never coincides with the Ariki basis [1] for the Hecke algebra
associated with $G(e,e,n)$. For example, consider the element
$t_{1}t_{0}.t_{0}$ which belongs to Ariki’s basis. In our basis, it is equal
to the linear combination $at_{1}t_{0}+t_{1}$, where $t_{1}t_{0}$ and $t_{1}$
are two distinct elements of our basis.

The general hope would be to construct natural bases for $H(de,e,n)$ that can
be defined from geodesic normal forms in the associated complex reflection
groups $G(de,e,n)$, which was established in Theorem 5.1 for the case of
$H(e,e,n)$. This arises the question whether the geodesic normal forms
established in Section 3 by using the presentation of Corran-Lee-Lee of
$G(de,e,n)$ for $d>1$ also provide natural bases for the corresponding Hecke
algebras. Unfortunately, some intricate arguments in our proof for the case of
$H(e,e,n)$ does not work in the general case of $H(de,e,n)$. Actually, on the
one hand, the Hecke algebra is defined, in the general case, as a quotient of
the complex braid group algebra defined by the presentation of Corran-Lee-Lee,
where the generators $t_{i}$’s are defined over $\mathbb{Z}$, but on the other
hand our geodesic normal forms are attached to the presentation of Corran-Lee-
Lee of the complex reflection group $G(de,e,n)$, where the generators
$\mathbf{t}_{i}$’s are defined this time over $\mathbb{Z}/de\mathbb{Z}$. This
phenomenon does not occur in the case of the presentations of Corran-Picantin
of $G(e,e,n)$ and $B(e,e,n)$ used to construct a basis for $H(e,e,n)$.
Nonetheless, for $e=1$, the Hecke algebra $H(d,1,n)$ is defined by using the
classical presentation of the complex braid group $B(d,1,n)$. Using the
geodesic normal forms constructed in Subsection 3.3, we are also able to
provide a natural basis for $H(d,1,n)$. This will be established in the next
section.

##  6 The case of $H(d,1,n)$

Let $d>1$ and $n\geq 2$. Let $R_{0}=\mathbb{Z}[a,b_{1},b_{2},\cdots,b_{d-1}]$.
Recall that the Hecke algebra $H(d,1,n)$ is defined as the unitary associative
$R_{0}$-algebra generated by the elements $z,s_{2},s_{3},\cdots,s_{n}$ with
the following relations:

  1. 1.

$zs_{2}zs_{2}=s_{2}zs_{2}z$,

  2. 2.

$zs_{j}=s_{j}z$ for $2\leq j\leq n$,

  3. 3.

$s_{i}s_{i+1}s_{i}=s_{i+1}s_{i}s_{i+1}$ for $2\leq i\leq n-1$,

  4. 4.

$s_{i}s_{j}=s_{j}s_{i}$ for $|i-j|>1$,

  5. 5.

$z^{d}-b_{1}z^{d-1}-b_{2}z^{d-2}-\cdots-b_{d-1}z-1=0$ and
$s_{j}^{2}-as_{j}-1=0$ for $2\leq j\leq n$.

Using the geodesic normal forms introduced in subsection 3.3 for all the
elements of $G(d,1,n)$, we construct a basis for $H(d,1,n)$ that is different
from the one defined by Ariki-Koike in [2].

Let us introduce the following subsets of $H(d,1,n)$.

$\Lambda_{1}$ | $=$ |  $\\{z^{k}$ for $0\leq k\leq d-1\\}$,
---|---|---

and for $2\leq i\leq n$,

$\Lambda_{i}$ | $=$ |  $\\{1$, |
---|---|---|---
|  | $\ \ s_{i}\cdots s_{i^{\prime}}$ | for $2\leq i^{\prime}\leq i$,
|  | $\ \ s_{i}\cdots s_{2}z^{k}$ | for $1\leq k\leq d-1$,
|  | $\ \ s_{i}\cdots s_{2}z^{k}s_{2}\cdots s_{i^{\prime}}$ | for $1\leq k\leq d-1$ and $2\leq i^{\prime}\leq i\\}$.

Define $\Lambda=\Lambda_{1}\Lambda_{2}\cdots\Lambda_{n}$ to be the set of the
products $a_{1}a_{2}\cdots a_{n}$, where $a_{1}\in\Lambda_{1},\cdots,\\\
a_{n}\in\Lambda_{n}$. Remark that this set corresponds to all the reduced
words $R\\!E(w)$ of the form $R\\!E_{1}(w)R\\!E_{2}(w)R\\!E_{3}(w)\cdots
R\\!E_{n}(w)$ introduced in subsection 3.3 (see Definition 3.19). In this
section, we establish the following theorem.

######  Theorem 6.1.

The set $\Lambda$ provides an $R_{0}$-basis of the Hecke algebra $H(d,1,n)$.

We have $|\Lambda_{1}|=d$ and $|\Lambda_{i}|=id$ for $2\leq i\leq n$. Then
$|\Lambda|$ is equal to $d^{n}n!$ that is the order of $G(d,1,n)$. Hence by
Proposition 2.3$(i)$ of [14], it is sufficient to show that $\Lambda$ is an
$R_{0}$-generating set of $H(d,1,n)$. This is proved by induction on $n$ in
much the same way as Theorem 5.1. We provide the following preliminary lemmas
that are useful in the proof of the theorem.

######  Lemma 6.2.

For $1\leq k\leq d-1$, the element $(s_{2}zs_{2})^{k}$ belongs to
$\sum\limits_{\begin{subarray}{c}\lambda_{1}\in\Lambda_{1},\\\
\lambda_{2}\in\Lambda^{\prime}_{2}\end{subarray}}R_{0}\lambda_{1}\lambda_{2}$,
where
$\Lambda^{\prime}_{2}=\\{1,s_{2},s_{2}z,s_{2}z^{2},\cdots,s_{2}z^{k-1},s_{2}zs_{2},s_{2}z^{2}s_{2},\cdots,s_{2}z^{k}s_{2}\\}$.

###### Proof.

The property is clear for $k=1$. Let $k=2$. We have
$(s_{2}zs_{2})^{2}=s_{2}zs_{2}^{2}zs_{2}$. We apply a quadratic relation and
get $as_{2}zs_{2}zs_{2}+s_{2}z^{2}s_{2}$. Applying a braid relation, one gets
$azs_{2}zs_{2}^{2}+s_{2}z^{2}s_{2}$. Using a quadratic relation, this is equal
to $a^{2}zs_{2}zs_{2}+azs_{2}z+s_{2}z^{2}s_{2}$, where each term is of the
form $\lambda_{1}\lambda_{2}$ with $\lambda_{1}\in\Lambda_{1}$ and
$\lambda_{2}\in\\{1,s_{2},s_{2}z,s_{2}zs_{2},s_{2}z^{2}s_{2}\\}$.

Let $k\geq 3$. Suppose the property is satisfied for $(s_{2}zs_{2})^{3}$,
$\cdots$, and $(s_{2}zs_{2})^{k-1}$. We have
$(s_{2}zs_{2})^{k}=(s_{2}zs_{2})^{k-1}(s_{2}zs_{2})$. By the induction
hypothesis, the terms that appear in the decomposition of
$(s_{2}zs_{2})^{k-1}$ are of the following forms.

  * •

$z^{c}$ with $0\leq c\leq d-1$,

  * •

$z^{c}s_{2}z^{c^{\prime}}$ with $0\leq c\leq d-1$ and $0\leq c^{\prime}\leq
k-2$,

  * •

$z^{c}s_{2}z^{c^{\prime}}s_{2}$ with $0\leq c\leq d-1$ and $1\leq
c^{\prime}\leq k-1$.

Multiplying these terms by $s_{2}zs_{2}$ on the right, we get the following
$3$ cases.

_Case 1_ : A term of the form $z^{c}s_{2}zs_{2}$ with $0\leq c\leq d-1$. It is
of the form $\lambda_{1}\lambda_{2}$ with $\lambda_{1}\in\Lambda_{1}$ and
$\lambda_{2}\in\Lambda^{\prime}_{2}$.

_Case 2_ : A term of the form $z^{c}s_{2}z^{c^{\prime}}s_{2}zs_{2}$ with
$0\leq c\leq d-1$ and $0\leq c^{\prime}\leq k-2$. We shift $z^{c^{\prime}}$ to
the right by applying braid relations and get
$z^{c}s_{2}^{2}zs_{2}z^{c^{\prime}}$. Applying a quadratic relation, this is
equal to
$az^{c}s_{2}zs_{2}\underline{z^{c^{\prime}}}+z^{c+1}s_{2}z^{c^{\prime}}$. Now
we shift $\underline{z^{c^{\prime}}}$ to the left by applying braid relations
and get $az^{c+c^{\prime}}s_{2}zs_{2}+z^{c+1}s_{2}z^{c^{\prime}}$. Each term
is of the form $\lambda_{1}\lambda_{2}$ with $\lambda_{1}\in\Lambda_{1}$ and
$\lambda_{2}\in\Lambda^{\prime}_{2}$.

_Case 3_ : A term of the form $z^{c}s_{2}z^{c^{\prime}}s_{2}^{2}zs_{2}$ with
$0\leq c\leq d-1$ and $1\leq c^{\prime}\leq k-1$. By applying a quadratic
relation, we have
$z^{c}s_{2}z^{c^{\prime}}s_{2}^{2}zs_{2}=az^{c}s_{2}z^{c^{\prime}}s_{2}zs_{2}+z^{c}s_{2}z^{c^{\prime}+1}s_{2}$.
The first term is the same as in the previous case. Then both terms are of the
form $\lambda_{1}\lambda_{2}$ with $\lambda_{1}\in\Lambda_{1}$ and
$\lambda_{2}\in\Lambda^{\prime}_{2}$.

∎

######  Lemma 6.3.

For $1\leq k\leq d-1$, the element $(s_{2}zs_{2})^{k}s_{2}$ belongs to
$R_{0}(s_{2}zs_{2})^{k}+R_{0}z(s_{2}zs_{2})^{k-1}+\cdots+R_{0}z^{k-1}(s_{2}zs_{2})+R_{0}s_{2}z^{k}$.

###### Proof.

For $k=1$, we have $(s_{2}zs_{2})s_{2}=s_{2}zs_{2}^{2}=as_{2}zs_{2}+s_{2}z$.
Then the property is satisfied for $k=1$. Let $k\geq 2$. Suppose that the
property is satisfied for $(s_{2}zs_{2})^{k-1}$. We have
$(s_{2}zs_{2})^{k}s_{2}=(s_{2}zs_{2})(s_{2}zs_{2})^{k-1}s_{2}$. By the
induction hypothesis, it belongs to
$R_{0}(s_{2}zs_{2})(s_{2}zs_{2})^{k-1}+R_{0}(s_{2}zs_{2})z(s_{2}zs_{2})^{k-2}+\cdots+R_{0}(s_{2}zs_{2})z^{k-2}(s_{2}zs_{2})+R_{0}(s_{2}zs_{2})s_{2}z^{k-1}$.
Then it belongs to
$R_{0}(s_{2}zs_{2})^{k}+R_{0}z(s_{2}zs_{2})^{k-1}+\cdots+R_{0}z^{k-2}(s_{2}zs_{2})^{2}\\\
+R_{0}z^{k-1}(s_{2}zs_{2})+R_{0}s_{2}z^{k}$. It follows that for all $1\leq
k\leq d-1$, the element $(s_{2}zs_{2})^{k}s_{2}$ belongs to
$R_{0}(s_{2}zs_{2})^{k}+R_{0}z(s_{2}zs_{2})^{k-1}+\cdots+R_{0}z^{k-1}(s_{2}zs_{2})+R_{0}s_{2}z^{k}$.

∎

######  Lemma 6.4.

For $1\leq k\leq d-1$, the element $s_{2}z^{k}s_{2}$ belongs to
$\sum\limits_{\begin{subarray}{c}\lambda_{1}\in\Lambda_{1},\\\
\lambda_{2}\in\Lambda^{\prime\prime}_{2}\end{subarray}}R_{0}\lambda_{1}\lambda_{2}$,
where
$\Lambda^{\prime\prime}_{2}=\\{1,s_{2},s_{2}z,s_{2}z^{2},\cdots,s_{2}z^{k-1},s_{2}zs_{2},(s_{2}zs_{2})^{2},\cdots,(s_{2}zs_{2})^{k}\\}$.

###### Proof.

The lemma is satisfied for $k=1$. For $k=2$, we have
$s_{2}z^{2}s_{2}=s_{2}zs_{2}^{-1}s_{2}zs_{2}$. Using that
$s_{2}^{-1}=s_{2}-a$, we get
$s_{2}zs_{2}^{2}zs_{2}-a\underline{s_{2}zs_{2}z}s_{2}$. Now we apply a braid
relation then a quadratic relation and get
$(s_{2}zs_{2})^{2}-azs_{2}zs_{2}^{2}=(s_{2}zs_{2})^{2}-a^{2}zs_{2}zs_{2}-azs_{2}z$
which satisfies the property we are proving.

Suppose the property is satisfied for $s_{2}z^{k-1}s_{2}$. We have
$s_{2}z^{k}s_{2}=s_{2}z^{k-1}s_{2}^{-1}s_{2}zs_{2}=s_{2}z^{k-1}s_{2}s_{2}zs_{2}-as_{2}z^{k-1}s_{2}zs_{2}$
by replacing $s_{2}^{-1}$ by $s_{2}-a$. For the second term, we shift
$z^{k-1}$ to the right and get $s_{2}^{2}zs_{2}z^{k-1}$. We apply a quadratic
relation to get $as_{2}zs_{2}\underline{z^{k-1}}+zs_{2}z^{k-1}$ then we shift
$\underline{z^{k-1}}$ to the left and finally get
$az^{k-1}s_{2}zs_{2}+zs_{2}z^{k-1}$, where each term is of the form
$\lambda_{1}\lambda_{2}$ with $\lambda_{1}\in\Lambda_{1}$ and
$\lambda_{2}\in\Lambda^{\prime\prime}_{2}$.
For the first term $s_{2}z^{k-1}s_{2}s_{2}zs_{2}$, by the induction
hypothesis, the terms that appear in the decomposition of $s_{2}z^{k-1}s_{2}$
are of the following forms.

  * •

$z^{c}$ and $z^{c}s_{2}$ with $0\leq c\leq d-1$,

  * •

$z^{c}(s_{2}zs_{2})^{c^{\prime}}$ with $0\leq c\leq d-1$ and $1\leq
c^{\prime}\leq k-1$,

  * •

$z^{c}s_{2}z^{c^{\prime}}$ with $0\leq c\leq d-1$ and $1\leq c^{\prime}\leq
k-2$.

Multiplying these terms by $s_{2}zs_{2}$ on the right, we get the following
$3$ cases.

_Case 1_. We have $z^{c}s_{2}zs_{2}$ and
$z^{c}\underline{s_{2}s_{2}}zs_{2}=az^{c}s_{2}zs_{2}+z^{c+1}s_{2}$, where each
term in both expressions is of the form $\lambda_{1}\lambda_{2}$ with
$\lambda_{1}\in\Lambda_{1}$ and $\lambda_{2}\in\Lambda^{\prime\prime}_{2}$.

_Case 2_. The term
$z^{c}(s_{2}zs_{2})^{c^{\prime}}s_{2}zs_{2}=z^{c}(s_{2}zs_{2})^{c^{\prime}+1}$
is of the form $\lambda_{1}\lambda_{2}$ with $\lambda_{1}\in\Lambda_{1}$ and
$\lambda_{2}\in\Lambda^{\prime\prime}_{2}$ since $1\leq c^{\prime}\leq k-1$.

_Case 3_. We have
$z^{c}s_{2}z^{c^{\prime}}s_{2}zs_{2}=z^{c}s_{2}^{2}zs_{2}z^{c^{\prime}}=az^{c}s_{2}zs_{2}z^{c^{\prime}}+z^{c+1}s_{2}z^{c^{\prime}}$.
The first term is equal to $z^{c+c^{\prime}}s_{2}zs_{2}$ and the second term
is equal to $z^{c+1}s_{2}z^{c^{\prime}}$ with $1\leq c^{\prime}\leq k-2$. Both
are of the form $\lambda_{1}\lambda_{2}$ with $\lambda_{1}\in\Lambda_{1}$ and
$\lambda_{2}\in\Lambda^{\prime\prime}_{2}$.

∎

The following proposition ensures that the case $n=2$ of Theorem 6.1 works
properly.

######  Proposition 6.5.

For all $a_{1}\in\Lambda_{1}$ and $a_{2}\in\Lambda_{2}$, the elements
$za_{1}a_{2}$ and $s_{2}a_{1}a_{2}$ belong to _Span_
$(\Lambda_{1}\Lambda_{2})$.

###### Proof.

It is readily checked that $za_{1}a_{2}$ belongs to
Span$(\Lambda_{1}\Lambda_{2})$. Note that when the power of $z$ exceeds $d-1$,
we use Relation 1 of Definition 4.5.

It is easily checked that if $a_{1}\in\Lambda_{1}$ and $a_{2}=1$, the element
$s_{2}a_{1}a_{2}$ belongs to Span$(\Lambda_{1}\Lambda_{2})$. Also, when
$a_{1}=1$ and $a_{2}\in\Lambda_{2}$, we have that $s_{2}a_{1}a_{2}$ belongs to
Span$(\Lambda_{1}\Lambda_{2})$.

Suppose $a_{1}=z^{k}$ with $1\leq k\leq d-1$ and $a_{2}=s_{2}$. We have
$s_{2}a_{1}a_{2}$ is equal to $s_{2}z^{k}s_{2}$. Hence it belongs to
Span$(\Lambda_{1}\Lambda_{2})$.

Suppose $a_{1}=z^{k}$ with $1\leq k\leq d-1$ and $a_{2}=s_{2}z^{k^{\prime}}$
with $1\leq k^{\prime}\leq d-1$. We have
$s_{2}a_{1}a_{2}=s_{2}z^{k}s_{2}z^{k^{\prime}}$. We replace $s_{2}z^{k}s_{2}$
by its decomposition given in Lemma 6.4, then we use the result of Lemma 6.2
to directly deduce that $s_{2}z^{k}s_{2}z^{k^{\prime}}$ belongs to
Span$(\Lambda_{1}\Lambda_{2})$.

Finally, suppose $a_{1}=z^{k}$ with $1\leq k\leq d-1$ and
$a_{2}=s_{2}z^{k^{\prime}}s_{2}$ with $1\leq k^{\prime}\leq d-1$.
We have $s_{2}a_{1}a_{2}$ is equal to $s_{2}z^{k}s_{2}z^{k^{\prime}}s_{2}$. We
replace $s_{2}z^{k}s_{2}$ by its decomposition given in Lemma 6.4. Then by the
results of Lemmas 6.3 and 6.2, we deduce that
$s_{2}z^{k}s_{2}z^{k^{\prime}}s_{2}$ belongs to
Span$(\Lambda_{1}\Lambda_{2})$.

∎

In order to prove Theorem 6.1, we introduce Lemmas 6.6 to 6.15 below that are
similar to Lemmas 5.7 to 5.16. Along with Proposition 6.5, they provide an
inductive proof of Theorem 6.1 that is similar to the proof of Theorem 5.1.
Therefore, by Proposition 2.3$(ii)$ of [14], we get a new proof of Theorem 2.3
for the case of the complex reflection groups $G(d,1,n)$. The remaining part
of this section is devoted to the proof of Lemmas 6.6 to 6.15. Let $n\geq 3$.
Denote by $S_{n-1}^{*}$ the set of the words over
$\\{z,s_{2},s_{3},\cdots,s_{n-1}\\}$.

######  Lemma 6.6.

Let $2\leq i\leq n$. We have $s_{n}\cdots s_{3}s_{2}^{2}s_{3}\cdots s_{i}$
belongs to _Span_ $(S_{n-1}^{*}\Lambda_{n})$.

###### Proof.

The proof is the same as the proof of Lemma 5.7. If $i=2$, we have that
$s_{n}\cdots s_{3}s_{2}^{2}$ belongs to $R_{0}s_{n}\cdots
s_{3}s_{2}+R_{0}s_{n}\cdots s_{3}$. We continue as in the proof of Lemma 5.7,
we get two terms of the form (see line 7 of the proof of Lemma 5.7):
$s_{n}\cdots s_{k+1}s_{k}s_{k+1}\cdots s_{i}$ with $k+1\leq i$ and
$s_{n}\cdots s_{i+1}s_{i}s_{i-1}^{2}s_{i}$.

We also get that the first term $s_{n}\cdots s_{i+1}s_{i}s_{i-1}^{2}s_{i}$
belongs to $R_{0}s_{i-1}s_{n}\cdots s_{i-1}+R_{0}s_{n}\cdots
s_{i+1}s_{i}+R_{0}s_{n}\cdots s_{i+1}$ (the last term is equal to $1$ if
$i=n$). Hence the element $s_{n}\cdots s_{i+1}s_{i}s_{i-1}^{2}s_{i}$ belongs
to Span$(S_{n-1}^{*}\Lambda_{n})$.

As in the proof of Lemma 5.7, the element $s_{n}\cdots
s_{k+1}s_{k}s_{k+1}\cdots s_{i}$ is equal to $s_{k}s_{k+1}\cdots
s_{i-1}s_{n}s_{n-1}\cdots s_{k}$. Hence it belongs to
Span$(S_{n-1}^{*}\Lambda_{n})$.

∎

######  Lemma 6.7.

If $a_{n-1}=s_{n-1}s_{n-2}\cdots s_{i}$ with $2\leq i\leq n-1$ and
$a_{n}=s_{n}\cdots s_{i^{\prime}}$ with $2\leq i^{\prime}\leq n$, then
$s_{n}(a_{n-1}a_{n})$ belongs to _Span_ $(\Lambda_{n-1}\Lambda_{n})$.

###### Proof.

The proof is the same as for Lemma 5.8.

If $i<i^{\prime}$, then we get $s_{n}(a_{n-1}a_{n})=s_{n-1}s_{n-2}\cdots
s_{i^{\prime}-1}s_{n}\cdots s_{i}$ which belongs to
Span$(\Lambda_{n-1}\Lambda_{n})$.

If $i\geq i^{\prime}$, then we get $s_{n}(a_{n-1}a_{n})=as_{n-1}\cdots
s_{i}s_{n}\cdots s_{i^{\prime}}+s_{n}\cdots s_{i^{\prime}}s_{n}\cdots s_{i+1}$
which also belongs to Span$(\Lambda_{n-1}\Lambda_{n})$.

∎

######  Lemma 6.8.

If $a_{n-1}=s_{n-1}\cdots s_{i}$ with $2\leq i\leq n-1$ and $a_{n}=s_{n}\cdots
s_{2}z^{k}$ with $0\leq k\leq d-1$, then $s_{n}(a_{n-1}a_{n})$ belongs to
_Span_ $(\Lambda_{n-1}\Lambda_{n})$.

###### Proof.

This case correspond to the case $i^{\prime}=2$ in the proof of Lemma 6.7 with
a right multiplication by $z^{k}$ for $0\leq k\leq d-1$. Since $i\geq 2$, by
the case $i\geq i^{\prime}$ in the proof of Lemma 6.7, we get, using the same
technique as in the proof of Lemma 5.9, that $s_{n}(a_{n-1}a_{n})$ is equal to
$as_{n-1}\cdots s_{i}s_{n}\cdots s_{2}z^{k}+s_{n-1}\cdots
s_{2}z^{k}s_{n}\cdots s_{i+1}$ which belongs to
Span$(\Lambda_{n-1}\Lambda_{n})$.

∎

######  Lemma 6.9.

If $a_{n-1}=s_{n-1}\cdots s_{i}$ with $2\leq i\leq n-1$ and $a_{n}=s_{n}\cdots
s_{2}z^{k}s_{2}\cdots s_{i^{\prime}}$ with $1\leq k\leq d-1$ and $2\leq
i^{\prime}\leq n$, then $s_{n}(a_{n-1}a_{n})$ belongs to _Span_
$(\Lambda_{n-1}\Lambda_{n})$.

###### Proof.

The proof is exactly the same as the proof of Lemma 5.10. According to the
computation in the proof of Lemma 6.8, we have
$s_{n}(a_{n-1}a_{n})=as_{n-1}\cdots s_{i}s_{n}\cdots s_{2}z^{k}(s_{2}\cdots
s_{i^{\prime}})+s_{n-1}\cdots s_{2}z^{k}s_{n}\cdots s_{i+1}(s_{2}\cdots
s_{i^{\prime}})$.
The first term is an element of Span$(\Lambda_{n-1}\Lambda_{n})$. For the
second term, we follow exactly the proof (starting from line 3) of Lemma 5.10
:
If $i^{\prime}<i$, we get $s_{n-1}\cdots s_{2}z^{k}s_{2}\cdots
s_{i^{\prime}}s_{n}\cdots s_{i+1}$ which belongs to
Span$(\Lambda_{n-1}\Lambda_{n})$.
If $i^{\prime}\geq i$, we get $s_{n-1}\cdots s_{2}z^{k}s_{2}\cdots
s_{i^{\prime}-1}s_{n}\cdots s_{i}$ which also belongs to
Span$(\Lambda_{n-1}\Lambda_{n})$.

∎

######  Lemma 6.10.

If $a_{n-1}=s_{n-1}\cdots s_{2}z^{k}$ with $1\leq k\leq d-1$ and
$a_{n}=s_{n}\cdots s_{i}$ with $2\leq i\leq n$, then $s_{n}(a_{n-1}a_{n})$
belongs to _Span_ $(\Lambda_{n-1}\Lambda_{n})$.

###### Proof.

We follow exactly the proof of Lemma 5.11 and we get the following terms.

If $i=2$, we get $s_{n-1}\cdots s_{2}s_{n}\cdots s_{2}z^{k}s_{2}$ (see line 9
of the proof of Lemma 5.11) which belongs to Span$(\Lambda_{n-1}\Lambda_{n})$.

If $i>2$, we get $s_{n-1}\cdots s_{i-1}s_{n}\cdots s_{2}z^{k}$ (see the last
line of the proof of Lemma 5.11) which also belongs to
Span$(\Lambda_{n-1}\Lambda_{n})$.

∎

######  Lemma 6.11.

If $a_{n-1}=s_{n-1}\cdots s_{2}z^{k}$ with $1\leq k\leq d-1$ and
$a_{n}=s_{n}\cdots s_{2}z^{l}$ with $1\leq l\leq d-1$, then
$s_{n}(a_{n-1}a_{n})$ belongs to _Span_ $(\Lambda_{n-1}\Lambda_{n})$.

###### Proof.

By the case $i=2$ in the proof of Lemma 6.10, we get
$s_{n}(a_{n-1}a_{n})=s_{n-1}\cdots s_{2}s_{n}\cdots
s_{3}s_{2}z^{k}s_{2}z^{l}$. If we replace $s_{2}z^{k}s_{2}z^{l}$ by its
decomposition over $\Lambda_{1}\Lambda_{2}$ (this is the case $n=2$ of Theorem
6.1, see Proposition 6.5), we get the three following terms:

  * •

$s_{n-1}\cdots s_{2}s_{n}\cdots s_{3}z^{c}$ with $0\leq c\leq d-1$,

  * •

$s_{n-1}\cdots s_{2}s_{n}\cdots s_{3}z^{c}s_{2}z^{c^{\prime}}$ with $0\leq
c\leq d-1$ and $0\leq c^{\prime}\leq d-1$,

  * •

$s_{n-1}\cdots s_{2}s_{n}\cdots s_{3}z^{c}s_{2}z^{c^{\prime}}s_{2}$ with
$0\leq c\leq d-1$ and $1\leq c^{\prime}\leq d-1$.

The first term is equal to $s_{n-1}\cdots s_{2}z^{c}s_{n}\cdots s_{3}$ which
belongs to Span$(\Lambda_{n-1}\Lambda_{n})$.
The second term is equal to $s_{n-1}\cdots s_{2}z^{c}s_{n}\cdots
s_{3}s_{2}z^{c^{\prime}}$ which belongs to Span$(\Lambda_{n-1}\Lambda_{n})$.
Finally, the third term is equal to $s_{n-1}\cdots s_{2}z^{c}s_{n}\cdots
s_{2}z^{c^{\prime}}s_{2}$ which also belongs to
Span$(\Lambda_{n-1}\Lambda_{n})$.

∎

######  Lemma 6.12.

If $a_{n-1}=s_{n-1}\cdots s_{2}z^{k}$ with $1\leq k\leq d-1$ and
$a_{n}=s_{n}\cdots s_{2}z^{l}s_{2}\cdots s_{i}$ with $2\leq i\leq n$ and
$1\leq l\leq d-1$, then $s_{n}(a_{n-1}a_{n})$ belongs to _Span_
$(S_{n-1}^{*}\Lambda_{n})$.

###### Proof.

According to the proof of the previous lemma, we have to deal with the
following three terms:

  * •

$s_{n-1}\cdots s_{2}z^{c}s_{n}\cdots s_{3}(s_{2}\cdots s_{i})$ for $0\leq
c\leq d-1$,

  * •

$s_{n-1}\cdots s_{2}z^{c}s_{n}\cdots s_{3}s_{2}z^{c^{\prime}}(s_{2}\cdots
s_{i})$ for $0\leq c\leq d-1$ and $0\leq c^{\prime}\leq d-1$,

  * •

$s_{n-1}\cdots s_{2}z^{c}s_{n}\cdots s_{2}z^{c^{\prime}}s_{2}(s_{2}\cdots
s_{i})$ for $0\leq c\leq d-1$ and $1\leq c^{\prime}\leq d-1$.

For the first case, we have $s_{n}\cdots\underline{s_{3}s_{2}s_{3}}s_{4}\cdots
s_{i}=s_{n}\cdots\underline{s_{2}}s_{3}s_{2}\underline{s_{4}}\cdots s_{i}$. We
shift $\underline{s_{2}}$ and $\underline{s_{4}}$ to the left in the previous
expression and get
$s_{2}s_{n}\cdots\underline{s_{4}s_{3}s_{4}}s_{2}s_{5}\cdots
s_{i}=s_{2}s_{n}\cdots\underline{s_{3}}s_{4}s_{3}s_{2}s_{5}\cdots s_{i}$. We
shift $\underline{s_{3}}$ to the left in the previous expression and get
$s_{2}s_{3}s_{n}\cdots s_{2}\underline{s_{5}}\cdots\underline{s_{i}}$. We
apply the same operations to $\underline{s_{5}}$, $\cdots$,
$\underline{s_{i}}$ and get
$s_{2}s_{3}\cdots s_{i-1}s_{n}\cdots s_{2}$. Hence the term of the first case
can be written as follows $s_{n-1}\cdots s_{2}z^{c}s_{2}\cdots
s_{i-1}s_{n}\cdots s_{2}$. Since $i-1\leq n-1$, it belongs to
Span$(S_{n-1}^{*}\Lambda_{n})$.

For the second case, we have a term of the form $s_{n-1}\cdots
s_{2}z^{c}s_{n}\cdots s_{3}s_{2}z^{c^{\prime}}(s_{2}\cdots s_{i})$ for $0\leq
c\leq d-1$ and $0\leq c^{\prime}\leq d-1$. If $c^{\prime}\neq 0$, this term
belongs to Span$(S_{n-1}^{*}\Lambda_{n})$ and if $c^{\prime}=0$, by the
computation in the proof of Lemma 6.6, it also belongs to
Span$(S_{n-1}^{*}\Lambda_{n})$.

For the third case, we have $s_{n-1}\cdots s_{2}z^{c}s_{n}\cdots
s_{2}z^{c^{\prime}}s_{2}^{2}s_{3}\cdots s_{i}=$
$as_{n-1}\cdots s_{2}z^{c}s_{n}\cdots s_{2}z^{c^{\prime}}s_{2}\cdots
s_{i}+s_{n-1}\cdots s_{2}z^{c}s_{n}\cdots s_{2}z^{c^{\prime}}s_{3}\cdots
s_{i}$. The first term is an element of Span$(S_{n-1}^{*}\Lambda_{n})$. For
the second term, we have $s_{n-1}\cdots s_{2}z^{c}s_{n}\cdots
s_{2}\underline{z^{c^{\prime}}}s_{3}\cdots s_{i}\\\ =s_{n-1}\cdots
s_{2}z^{c}s_{n}\cdots s_{2}s_{3}\cdots s_{i}z^{c^{\prime}}$, where
$s_{n}\cdots s_{2}s_{3}\cdots s_{i}$ is already computed in the first case. It
is equal to $s_{2}\cdots s_{i-1}s_{n}\cdots s_{2}$. Hence the term is of the
form
$s_{n-1}\cdots s_{2}z^{c}s_{2}\cdots s_{i-1}s_{n}\cdots s_{2}z^{c^{\prime}}$
which belongs to Span$(S_{n-1}^{*}\Lambda_{n})$.

∎

######  Lemma 6.13.

If $a_{n-1}=s_{n-1}\cdots s_{2}z^{k}s_{2}\cdots s_{i}$ with $2\leq i\leq n-1$,
$1\leq k\leq d-1$ and $a_{n}=s_{n}\cdots s_{i^{\prime}}$ with $2\leq
i^{\prime}\leq n$, then $s_{n}(a_{n-1}a_{n})$ belongs to _Span_
$(\Lambda_{n-1}\Lambda_{n})$.

###### Proof.

We follow exactly the proof of Lemma 5.14.

Suppose $i<i^{\prime}$. If $i^{\prime}=i+1$, we get
$s_{n}(a_{n-1}a_{n})=s_{n-1}\cdots s_{i+1}s_{n}\cdots s_{2}z^{k}s_{2}\cdots
s_{i+1}$ which belongs to Span$(\Lambda_{n-1}\Lambda_{n})$, see lines 9 and 10
of the proof of Lemma 5.14. If $i^{\prime}>i+1$, we get $s_{n-1}\cdots
s_{i^{\prime}-1}s_{n}\cdots s_{2}z^{k}s_{2}\cdots s_{i}$ which belongs to
Span$(\Lambda_{n-1}\Lambda_{n})$, see line 16 of the proof of Lemma 5.14.

Suppose $i\geq i^{\prime}$. We get $s_{n}(a_{n-1}a_{n})=s_{n-1}\cdots
s_{i^{\prime}}s_{n}\cdots s_{2}z^{k}s_{2}\cdots s_{i+1}$, see the last line of
the proof of Lemma 5.14. Hence $s_{n}(a_{n-1}a_{n})$ belongs to
Span$(\Lambda_{n-1}\Lambda_{n})$.

∎

######  Lemma 6.14.

If $a_{n-1}=s_{n-1}\cdots s_{2}z^{k}s_{2}\cdots s_{i}$ with $2\leq i\leq n-1$,
$1\leq k\leq d-1$ and $a_{n}=s_{n}\cdots s_{2}z^{l}$ with $0\leq l\leq d-1$,
then $s_{n}(a_{n-1}a_{n})$ belongs to _Span_ $(S_{n-1}^{*}\Lambda_{n})$.

###### Proof.

According to the computations in the proof of the previous lemma, we have
$s_{n}(a_{n-1}a_{n})=s_{n-1}\cdots s_{2}s_{n}\cdots s_{2}z^{k}s_{2}\cdots
s_{i+1}z^{l}$. We shift $z^{l}$ to the left and get
$s_{n}(a_{n-1}a_{n})=s_{n-1}\cdots s_{2}s_{n}\cdots
s_{3}(s_{2}z^{k}s_{2})z^{l}s_{3}\cdots s_{i+1}$. If we replace
$(s_{2}z^{k}s_{2})z^{l}$ by its decomposition over $\Lambda_{1}\Lambda_{2}$
(this is the case $n=2$ of Theorem 6.1, see Proposition 6.5), we get terms of
the three following forms:

  * •

$s_{n-1}\cdots s_{2}s_{n}\cdots s_{3}z^{c}s_{3}\cdots s_{i+1}$ with $0\leq
c\leq d-1$,

  * •

$s_{n-1}\cdots s_{2}s_{n}\cdots s_{3}z^{c}s_{2}z^{c^{\prime}}s_{3}\cdots
s_{i+1}$ with $0\leq c\leq d-1$ and $0\leq c^{\prime}\leq d-1$,

  * •

$s_{n-1}\cdots s_{2}s_{n}\cdots s_{3}z^{c}s_{2}z^{c^{\prime}}s_{2}s_{3}\cdots
s_{i+1}$ with $0\leq c\leq d-1$ and $1\leq c^{\prime}\leq d-1$.

The first term is equal to $s_{n-1}\cdots s_{2}z^{c}s_{n}\cdots
s_{4}s_{3}^{2}s_{4}\cdots s_{i+1}$ with $2\leq i\leq n-1$. Thus, by the proof
of Lemma 6.6, it belongs to Span$(S_{n-1}^{*}\Lambda_{n})$.

The second term is equal to $s_{n-1}\cdots s_{2}z^{c}s_{n}\cdots
s_{3}s_{2}s_{3}\cdots s_{i+1}z^{c^{\prime}}$. We have
$s_{n}\cdots s_{3}s_{2}s_{3}\cdots s_{i+1}$ is equal to $s_{2}\cdots
s_{i}s_{n}\cdots s_{2}$. This is done in the first case of the proof of Lemma
6.12. Hence we get $s_{n-1}\cdots s_{2}z^{c}s_{2}\cdots s_{i}s_{n}\cdots
s_{2}z^{c^{\prime}}$ which belongs to Span$(S_{n-1}^{*}\Lambda_{n})$.

The third term is equal to $s_{n-1}\cdots s_{2}z^{c}s_{n}\cdots
s_{2}z^{c^{\prime}}s_{2}\cdots s_{i+1}$. Hence it belongs to
Span$(S_{n-1}^{*}\Lambda_{n})$.

∎

######  Lemma 6.15.

If $a_{n-1}=s_{n-1}\cdots s_{2}z^{k}s_{2}\cdots s_{i}$ with $1\leq k\leq d-1$,
$2\leq i\leq n-1$ and $a_{n}=s_{n}\cdots s_{2}z^{l}s_{2}\cdots s_{i^{\prime}}$
with $1\leq l\leq d-1$, $2\leq i^{\prime}\leq n$, then $s_{n}(a_{n-1}a_{n})$
belongs to _Span_ $(S_{n-1}^{*}\Lambda_{n})$.

###### Proof.

According to the proof of the previous lemma, we have to prove that the
following three terms belong to Span$(S_{n-1}^{*}\Lambda_{n})$:

  * •

$s_{n-1}\cdots s_{2}z^{c}s_{n}\cdots s_{4}s_{3}^{2}s_{4}\cdots
s_{i+1}(s_{2}\cdots s_{i^{\prime}})$ for $0\leq c\leq d-1$,

  * •

$s_{n-1}\cdots s_{2}z^{c}s_{2}\cdots s_{i}s_{n}\cdots
s_{2}z^{c^{\prime}}(s_{2}\cdots s_{i^{\prime}})$ for $0\leq c\leq d-1$ and
$0\leq c^{\prime}\leq d-1$,

  * •

$s_{n-1}\cdots s_{2}z^{c}s_{n}\cdots s_{2}z^{c^{\prime}}s_{2}\cdots
s_{i+1}(s_{2}\cdots s_{i^{\prime}})$ for $0\leq c\leq d-1$ and $1\leq
c^{\prime}\leq d-1$.

The first case is similar to Case 4 in the proof of Lemma 5.16.

For the second term, if $c^{\prime}\neq 0$, it belongs to
Span$(S_{n-1}^{*}\Lambda_{n})$ and if $c^{\prime}=0$, by the computation in
the proof of Lemma 6.6, it also belongs to Span$(S_{n-1}^{*}\Lambda_{n})$.

For the third term, we apply the same technique as in Case 2 of the proof of
Lemma 5.16. We get that $s_{n}\cdots s_{2}z^{c^{\prime}}s_{2}\cdots
s_{i+1}(s_{2}\cdots s_{i^{\prime}})$ is equal to:
If $i^{\prime}\leq i$, it is equal to $s_{2}s_{3}\cdots
s_{i^{\prime}}s_{n}\cdots s_{2}z^{c^{\prime}}s_{2}\cdots s_{i+1}$.
If $i^{\prime}>i$, it is equal to $s_{2}s_{3}\cdots
s_{i^{\prime}-1}s_{n}\cdots s_{2}z^{c^{\prime}}s_{2}\cdots s_{i}$.
It follows that $s_{n-1}\cdots s_{2}z^{c}s_{n}\cdots
s_{2}z^{c^{\prime}}s_{2}\cdots s_{i+1}(s_{2}\cdots s_{i^{\prime}})$ for $0\leq
c\leq d-1$ and $1\leq c^{\prime}\leq d-1$ belongs to
Span$(S_{n-1}^{*}\Lambda_{n})$.

∎

######  Remark 6.16.

We remark that for every $d$ and $n$ at least equal to $2$, our basis never
coincides with the Ariki-Koike basis [2] as illustrated by the following
example. Consider the element $s_{2}zs_{2}^{2}=s_{2}zs_{2}.s_{2}$ which
belongs to the Ariki-Koike basis. In our basis, it is equal to the linear
combination $as_{2}zs_{2}+s_{2}z$, where $s_{2}zs_{2}$ and $s_{2}z$ are two
distinct elements of our basis.

## Acknowledgements

Most of the results of this paper have been discovered during my PhD at
Université de Caen Normandie. I would like to thank my PhD supervisors Eddy
Godelle and Ivan Marin for the numerous stimulating discussions. I am also
grateful to Barbara Baumeister for her helpful comments and for giving me the
time to write this paper at the beginning of my postdoc (DFG project: BA
2200/5-1) at Universität Bielefeld.

## References

  * [1] S. Ariki.  Representation theory of a Hecke algebra of $G(r,p,n)$.  J. Algebra, 177(1):164–185, 1995.
  * [2] S. Ariki and K. Koike.  A Hecke algebra of $(\mathbb{Z}/r\mathbb{Z})\wr S_{n}$ and construction of its irreducible representations.  Adv. Math., 106(2):216–243, 1994.
  * [3] N. Bourbaki.  Groupes et algèbres de Lie, chap. 4, 5 et 6.  Hermann, Paris, 1968.
  * [4] K. Bremke and G. Malle.  Reduced words and a length function for $G(e,1,n)$.  Indag. Mathem., 8:453–469, 1997.
  * [5] M. Broué and G. Malle.  Zyklotomische Heckealgebren, in Représentations unipotentes génériques et blocs des groupes réductifs finis.  Astérisque, 212:119–189, 1993.
  * [6] M. Broué, G. Malle, and R. Rouquier.  Complex reflection groups, braid groups, Hecke algebras.  J. Reine Angew. Math., 500:127–190, 1998.
  * [7] E. Chavli.  The BMR freeness conjecture for exceptional groups of rank 2.  PhD thesis, Univ. Paris Diderot (Paris 7), 2016.
  * [8] E. Chavli.  The BMR freeness conjecture for the tetrahedral and octahedral family.  Communications in Algebra, 46(1):386–464, 2018.
  * [9] R. Corran, E.K. Lee, and S.J. Lee.  Braid groups of imprimitive complex reflection groups.  J. Algebra, 427:387–425, 2015.
  * [10] R. Corran and M. Picantin.  A new Garside structure for braid groups of type $(e,e,r)$.  J. London Math. Soc., 84(3):689–711, 2011.
  * [11] M. Geck and G. Pfeiffer.  Characters of finite Coxeter groups and Iwahori-Hecke algebras, volume 21.  Oxford University Press, 2000.
  * [12] I. Marin.  The cubic Hecke algebra on at most 5 strands.  J. of Pure and Applied Algebra, 216(12):2754–2782, 2012\.
  * [13] I. Marin.  The freeness conjecture for Hecke algebras of complex reflection groups and the case of the Hessian group $G_{26}$.  J. of Pure and Applied Algebra, 218(4):704–720, 2014.
  * [14] I. Marin.  Proof of the BMR conjecture for $G_{20}$ and $G_{21}$.  arXiv:1701.09017, 2017.  To appear in J. Symbolic Computations.
  * [15] I. Marin and G. Pfeiffer.  The BMR freeness conjecture for the 2-reflection groups.  Mathematics of Computation, 86:2005–2023, 2017.
  * [16] H. Matsumoto.  Générateurs et relations des groupes de Weyl généralisés.  C. R. Acad. Sci. Paris, 258:3419–3422, 1964.
  * [17] G. Neaime.  Interval Garside structures for the complex braid groups $B(e,e,n)$.  arXiv: 1707.06864v2, 2017.
  * [18] S. Rostam.  Cyclotomic quiver Hecke algebras and Hecke algebra of $G(r,p,n)$.  arXiv:1609.08908, 2016.  To appear in Trans. Amer. Math. Soc.
  * [19] G.C. Shephard and J.A. Todd.  Finite unitary reflection groups.  Canad. J. Math., 6(2):274–304, 1954.
  * [20] S. Tsuchioka.  BMR freeness for icosahedral family.  arXiv:1710.03868, 2017.