% -------------------------------------------------------------
% NOTE ON THE DETAILED AND SHORT VERSIONS:
% -------------------------------------------------------------
% This paper comes in two versions, a detailed and a short one.
% The short version should be more than sufficient for any
% reasonable use; the detailed one was written purely to
% convince the author of its correctness.
% To switch between the two versions, find the line containing
% "\newenvironment{noncompile}{}{}" in this LaTeX file.
% Look at the two lines right beneath this line.
% To compile the detailed version, they should be as follows:
%   \includecomment{verlong}
%   \excludecomment{vershort}
% To compile the short version, they should be as follows:
%   \excludecomment{verlong}
%   \includecomment{vershort}
% As a rule, the line
%   \excludecomment{noncompile}
% should stay as it is.
% -------------------------------------------------------------
% NOTES ON SOME HACKS USED IN THIS FILE:
% -------------------------------------------------------------
% One of my pet peeves with amsthm is its use of italics in the theorem and
% proposition environments; this makes math and text indistinguishable in said
% enviroments. To avoid this, I redefine the enviroments to use the standard
% font and to use a hanging indent, along with a bold vertical bar to its
% left, to distinguish these environments from surrounding text. (Along with
% the advantage of distinguishing math from text, this also allows nesting
% several such environments inside each other, like a definition inside a
% remark. I'm not sure how good of an idea this is, though. There are also
% downsides related to the hanging indentation, such as footnotes out of it
% being painful to do right.) This is done starting from the line
%   \theoremstyle{definition}
% and until the line
%   {\end{leftbar}\end{exmp}}

\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage[breaklinks=true]{hyperref}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{tikz}
\usepackage{needspace}
\usepackage{tabls}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{CSTFile=LaTeX article (bright).cst}
%TCIDATA{Created=Sat Mar 27 17:33:36 2004}
%TCIDATA{LastRevised=Monday, April 29, 2019 19:21:41}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%TCIDATA{Language=American English}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{quote}\phantomsection}
{\end{quote}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{quote}\phantomsection}
{\end{quote}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{quote}\phantomsection}
{\end{quote}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{quote}\phantomsection}
{\end{quote}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{quote}\phantomsection}
{\end{quote}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{quote}\phantomsection}
{\end{quote}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{convention}[1][]
{\begin{conv}[#1]\begin{quote}\phantomsection}
{\end{quote}\end{conv}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{warning}[1][]
{\begin{warn}[#1]\begin{quote}\phantomsection}
{\end{quote}\end{warn}}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{convention}[1][Convention]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{warning}[1][Warning]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\newcommand{\Ker}{\operatorname*{Ker}}
\newcommand{\id}{\operatorname*{id}}
\newcommand{\inc}{\operatorname*{inc}}
\newcommand{\gr}{\operatorname*{gr}}
\newcommand{\Hom}{\operatorname*{Hom}}
\newcommand{\Sym}{\operatorname{Sym}}
\newcommand{\calA}{\mathcal A}
\newcommand{\arinj}{\ar@{_{(}->}}
\newcommand{\arsurj}{\ar@{->>}}
\newcommand{\arelem}{\ar@{|->}}
\newcommand{\fraka}{\mathfrak{a}}
\newcommand{\frakb}{\mathfrak{b}}
\newcommand{\frakc}{\mathfrak{c}}
\newcommand{\xycs}{\xymatrixcolsep}
\newcommand{\xyrs}{\xymatrixrowsep}
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\bigoplusnonlimits\bigoplus
\let\bigcupnonlimits\bigcup
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigoplus}{\bigoplusnonlimits\limits}
\renewcommand{\bigcup}{\bigcupnonlimits\limits}
\begin{document}

\begin{center}
\textbf{Promotion and Rowmotion}

\textit{Jessica Striker, Nathan Williams}

\href{https://arxiv.org/abs/1108.1172v3}{version 17 Sep 2012
(arXiv:1108.1172v3)}

\textbf{Errata and comments, 2 July 2013}

\begin{verlong}
\textbf{[detailed version]}
\end{verlong}

\bigskip
\end{center}

\begin{itemize}
\item \textbf{Page 3, Theorem 2.8:} Replace ``$C_{n}$'' by ``$C_{nm}$''.

\item \textbf{Page 6, Lemma 4.1:} I personally would write ``$x\mapsto gx$''
instead of your ``$x\rightarrow gx$'', as I belong to the set of
mathematicians who make a distinction between the $\rightarrow$ and $\mapsto$ arrows.

\item \textbf{Page 8, after the proof of Corollary 4.9:} In ``$\varnothing
=I_{0}\subset I_{1}\cdots\subset I_{n}=\mathcal{P}$'', it would be better to
add a ``$\subset$'' sign after the ``$I_{1}$''. (This appears at least twice
in the text.)

\item \textbf{Page 8, after the proof of Corollary 4.9:} Replace ``in the
singleton set $I_{i+1}-I_{i}$'' by ``in the singleton set $I_{i}-I_{i-1}$''
(unless you have suddenly decided that linear extensions are bijections to
$\left\{  0,1,\ldots,n-1\right\}  $ rather than $\left\{  1,2,\ldots,n\right\}  $).

\item \textbf{Page 9, Definition 4.13:} Replace ``$R$'' by ``$\mathcal{R}$''.

\item \textbf{Page 10, proof of Lemma 5.1:} Replace ``$\prod_{j=1}^{n}g_{i}$''
by ``$\prod_{i=1}^{n}g_{i}$'' on the first line and also on the last line of
the proof.

\item I'm unhappy with your notation $\prod\limits_{i=\alpha}^{\beta}f\left(
i\right)  $, which (I believe) you define to be something like $\left\{
\begin{array}
[c]{c}%
f\left(  \alpha\right)  f\left(  \alpha+1\right)  \cdots f\left(  \beta\right)
,\ \ \ \ \ \ \ \ \ \ \text{if }\alpha\leq\beta;\\
f\left(  \alpha\right)  f\left(  \alpha-1\right)  \cdots f\left(  \beta\right)
,\ \ \ \ \ \ \ \ \ \ \text{if }\alpha\geq\beta
\end{array}
\right.  $. I understand that this notation is an answer to the
noncommutativity of the groups in which the products live, but I'd prefer
$\overrightarrow{\prod\limits_{i=\alpha}^{\beta}}$ and $\overleftarrow{\prod
\limits_{i=\alpha}^{\beta}}$ instead. The problem with your notation is that
it conflicts with the classical convention that an empty product like
$\prod\limits_{i=\alpha}^{\alpha-1}f\left(  i\right)  $ has to mean $1$ (this
is, for example, the meaning of the products in Definition 4.8 when $k=n=0$,
or the meaning of the product in Theorem 5.4 when $m=1$).

\item \textbf{Page 14:} On the first line of this page, I think both
\textquotedblleft$J$\textquotedblright's in \textquotedblleft$e_{i}+e_{n}\in
J$ if and only if $e_{i}-e_{n}\in J$\textquotedblright\ should be
\textquotedblleft$I$\textquotedblright's.

\item \textbf{Page 16:} You write: ``A word containing parentheses is called
\textit{balanced} if the number of left parentheses is always greater than or
equal to the number of right parentheses.'' I'd wish the word ``always'' be more
concretized (you probably mean ``in every initial subword'', not ``in every subword'').

\item \textbf{Page 20, Definition 8.7:} To be honest I don't find this very
readable. What exactly are the ``outward-pointing edges''; what does ``every
second'' mean (starting where?); are the paths directed (you say ``begin'' and
``end'' yet you don't draw arrows); and don't you want to say that the paths
should not cross?

\item \textbf{Page 21, \S 8.3:} In the first line of \S 8.3, the ``2n'' should
be in mathmode (i. e., inside dollar signs).
\end{itemize}

--------------------------------------------

\begin{vershort}
Here is something more substantial, but probably not an error on your side: I
don't understand your proof of Lemma 5.1. But I have an alternative one,
which seems easier to formalize. Let me sketch it:

\textit{Alternative proof of Lemma 5.1:} First, let me notice that the
conditions on the $g_{i}$ can be replaced by the following one:%
\begin{equation}
g_{i}g_{j}=g_{j}g_{i}\text{ for every two }i\in\left\{  1,2,\ldots,n\right\}
\text{ and }j\in\left\{  1,2,\ldots,n\right\}  \text{ satisfying }\left\vert
i-j\right\vert >1. \label{simple-condition}%
\end{equation}
Of course, (\ref{simple-condition}) is a consequence of the conditions you
give, but it is much more general and I wouldn't be surprised if Lemma 5.1 is
also useful in cases where your conditions are not satisfied (Hecke
algebras?). (That said, it is also not necessary to require the $g_{i}$ to be generators...)

We will show that%
\begin{equation}
\left(
\begin{array}
[c]{c}%
\text{for any }k\in\left\{  1,2,\ldots,n\right\}  \text{ and any }\omega
\in\mathfrak{S}_{k}\text{ and }\nu\in\mathfrak{S}_{k}\text{, there exists}\\
\text{an }\alpha\in\left\langle g_{1},g_{2},\ldots,g_{k-1}\right\rangle \text{
such that }\overrightarrow{\prod\limits_{i=1}^{k}}g_{\omega\left(  i\right)
}=\alpha\cdot\left(  \overrightarrow{\prod\limits_{i=1}^{k}}g_{\nu\left(
i\right)  }\right)  \cdot\alpha^{-1}%
\end{array}
\right)  \label{l5.1.pf.main-short}%
\end{equation}
(where my $\overrightarrow{\prod\limits_{i=1}^{k}}$ means what you would call
$\prod\limits_{i=1}^{k}$). Once this is shown, we will immediately obtain the
claim of Lemma 5.1 just by applying this to $k=n$. Notice how
(\ref{l5.1.pf.main-short}) says $\alpha\in\left\langle g_{1},g_{2}%
,\ldots,g_{k-1}\right\rangle $, not $\alpha\in\left\langle g_{1},g_{2}%
,\ldots,g_{k}\right\rangle $; this is what makes (\ref{l5.1.pf.main-short}) prone
to induction over $k$.

\textit{Proof of (\ref{l5.1.pf.main-short}):} Of course,
(\ref{l5.1.pf.main-short}) is clear for $k=1$, so we only need to do the
induction step.

Let $\omega\in\mathfrak{S}_{k}$ and $\nu\in\mathfrak{S}_{k}$. It is easy to
find an $\omega^{\prime}\in\mathfrak{S}_{k-1}$ and $\gamma\in\left\langle
g_{1},g_{2},\ldots,g_{k-1}\right\rangle $ such that
\begin{equation}
\overrightarrow{\prod\limits_{i=1}^{k}}g_{\omega\left(  i\right)  }=\gamma
g_{k}\cdot\left(  \overrightarrow{\prod\limits_{i=1}^{k-1}}g_{\omega^{\prime
}\left(  i\right)  }\right)  \cdot\gamma^{-1}. \label{l5.1e.pf.gamma-short}%
\end{equation}
\footnote{Indeed, let $a=\omega^{-1}\left(  k\right)  $, set $\gamma
=g_{\omega\left(  1\right)  }g_{\omega\left(  2\right)  } \cdots g_{\omega\left(
a-1\right)  }$, and let $\omega^{\prime}\in\mathfrak{S}_{k-1}$ be defined by%
\[
\left(  \omega^{\prime}\left(  1\right)  ,\omega^{\prime}\left(  2\right)
,\ldots,\omega^{\prime}\left(  k-1\right)  \right)  =\left(  \omega\left(
a+1\right)  ,\omega\left(  a+2\right)  ,\ldots,\omega\left(  k\right)
,\omega\left(  1\right)  ,\omega\left(  2\right)  ,\ldots,\omega\left(
a-1\right)  \right)  .
\]
} Similarly, we can find a $\nu^{\prime}\in\mathfrak{S}_{k-1}$ and $\delta
\in\left\langle g_{1},g_{2},\ldots,g_{k-1}\right\rangle $ such that%
\begin{equation}
\overrightarrow{\prod\limits_{i=1}^{k}}g_{\nu\left(  i\right)  }=\delta
g_{k}\cdot\left(  \overrightarrow{\prod\limits_{i=1}^{k-1}}g_{\nu^{\prime
}\left(  i\right)  }\right)  \cdot\delta^{-1}. \label{l5.1e.pf.delta-short}%
\end{equation}


But by the induction assumption, there exists a $\beta\in\left\langle
g_{1},g_{2},\ldots,g_{k-2}\right\rangle $ such that%
\begin{equation}
\overrightarrow{\prod\limits_{i=1}^{k-1}}g_{\omega^{\prime}\left(  i\right)
}=\beta\cdot\left(  \overrightarrow{\prod\limits_{i=1}^{k-1}}g_{\nu^{\prime
}\left(  i\right)  }\right)  \cdot\beta^{-1}. \label{l5.1e.pf.beta-short}%
\end{equation}


Now, since $\beta\in\left\langle g_{1},g_{2},\ldots,g_{k-2}\right\rangle $, we
have $g_{k}\beta=\beta g_{k}$ (as an easy consequence of
(\ref{simple-condition})). Thus, (\ref{l5.1e.pf.gamma-short}) becomes%
\begin{align*}
\overrightarrow{\prod\limits_{i=1}^{k}}g_{\omega\left(  i\right)  }  &
=\gamma g_{k}\cdot\underbrace{\left(  \overrightarrow{\prod\limits_{i=1}%
^{k-1}}g_{\omega^{\prime}\left(  i\right)  }\right)  }_{\substack{=\beta
\cdot\left(  \overrightarrow{\prod\limits_{i=1}^{k-1}}g_{\nu^{\prime}\left(
i\right)  }\right)  \cdot\beta^{-1}\\\text{(by (\ref{l5.1e.pf.beta-short}))}%
}}\cdot\gamma^{-1}\\
&  =\gamma\underbrace{g_{k}\beta}_{=\beta g_{k}}\cdot\left(
\overrightarrow{\prod\limits_{i=1}^{k-1}}g_{\nu^{\prime}\left(  i\right)
}\right)  \cdot\beta^{-1}\gamma^{-1}=\gamma\underbrace{\beta}_{=\beta
\delta^{-1}\delta}g_{k}\cdot\left(  \overrightarrow{\prod\limits_{i=1}^{k-1}%
}g_{\nu^{\prime}\left(  i\right)  }\right)  \cdot\underbrace{\beta^{-1}%
}_{=\delta^{-1}\delta\beta^{-1}}\gamma^{-1}\\
&  =\gamma\beta\delta^{-1}\underbrace{\delta g_{k}\cdot\left(
\overrightarrow{\prod\limits_{i=1}^{k-1}}g_{\nu^{\prime}\left(  i\right)
}\right)  \cdot\delta^{-1}}_{\substack{=\overrightarrow{\prod\limits_{i=1}%
^{k}}g_{\nu\left(  i\right)  }\\\text{(by (\ref{l5.1e.pf.delta-short}))}%
}}\delta\beta^{-1}\gamma^{-1}\\
&  =\gamma\beta\delta^{-1}\cdot\left(  \overrightarrow{\prod\limits_{i=1}^{k}%
}g_{\nu\left(  i\right)  }\right)  \cdot\underbrace{\delta\beta^{-1}%
\gamma^{-1}}_{=\left(  \delta^{-1}\right)  ^{-1}\beta^{-1}\gamma^{-1}=\left(
\gamma\beta\delta^{-1}\right)  ^{-1}}\\
&  =\gamma\beta\delta^{-1}\cdot\left(  \overrightarrow{\prod\limits_{i=1}^{k}%
}g_{\nu\left(  i\right)  }\right)  \cdot\left(  \gamma\beta\delta^{-1}\right)
^{-1}.
\end{align*}
Thus, there exists an $\alpha\in\left\langle g_{1},g_{2},\ldots,g_{k-1}%
\right\rangle $ such that $\overrightarrow{\prod\limits_{i=1}^{k}}%
g_{\omega\left(  i\right)  }=\alpha\cdot\left(  \overrightarrow{\prod
\limits_{i=1}^{k}}g_{\nu\left(  i\right)  }\right)  \cdot\alpha^{-1}$ (namely,
$\alpha=\gamma\beta\delta^{-1}$). This completes the induction step, and
proves Lemma 5.1.
\end{vershort}

\begin{verlong}
Here is something more substantial, but probably not an error on your side: I
don't understand your proof of Lemma 5.1. But I have an alternative one,
which seems easier to formalize. Let me show this proof in all its details.
Before I start with the actual proof, here is a very basic lemma:

\textbf{Lemma 5.1a.} Let $k$ be a positive integer. Let $\omega\in
\mathfrak{S}_{k}$. Let $i=\omega^{-1}\left(  k\right)  $. Then, there exists a
permutation $\sigma\in\mathfrak{S}_{k-1}$ such that
\[
\left(  \sigma\left(  1\right)  ,\sigma\left(  2\right)  ,\ldots,\sigma\left(
k-1\right)  \right)  =\left(  \omega\left(  i+1\right)  ,\omega\left(
i+2\right)  ,\ldots,\omega\left(  k\right)  ,\omega\left(  1\right)
,\omega\left(  2\right)  ,\ldots,\omega\left(  i-1\right)  \right)  .
\]


\textit{Proof of Lemma 5.1a.} Since $\omega\in\mathfrak{S}_{k}$, we know that
$\omega$ is a permutation. Hence, $\omega$ is invertible, and $\omega^{-1}$ is well-defined.

For every $j\in\left\{  1,2,\ldots,k-1\right\}  $, the element $\left\{
\begin{array}
[c]{c}%
\omega\left(  i+j\right)  ,\ \ \ \ \ \ \ \ \ \ \text{if }j\leq k-i;\\
\omega\left(  j-k+i\right)  ,\ \ \ \ \ \ \ \ \ \ \text{if }j>k-i
\end{array}
\right.  $ of $\left\{  1,2,\ldots,k-1\right\}  $ is
well-defined\footnote{\textit{Proof.} Let $j\in\left\{  1,2,\ldots,k-1\right\}
$. We need to prove that the element $\left\{
\begin{array}
[c]{c}%
\omega\left(  i+j\right)  ,\ \ \ \ \ \ \ \ \ \ \text{if }j\leq k-i;\\
\omega\left(  j-k+i\right)  ,\ \ \ \ \ \ \ \ \ \ \text{if }j>k-i
\end{array}
\right.  $ of $\left\{  1,2,\ldots,k-1\right\}  $ is well-defined. We distinguish
between two cases:
\par
\textit{Case 1:} We have $j\leq k-i$.
\par
\textit{Case 2:} We have $j>k-i$.
\par
Let us consider Case 1 first. In this case, $j\leq k-i$. Thus, $i+j\leq k$.
Hence, $i+j\in\left\{  1,2,\ldots,k\right\}  $ (since $i+j>0$ (because $i>0$ and
$j>0$)). Therefore, $\omega\left(  i+j\right)  $ is a well-defined element of
$\left\{  1,2,\ldots,k\right\}  $. Since $j\in\left\{  1,2,\ldots,k-1\right\}  $, we
have $j\neq0$, hence $i+j\neq i=\omega^{-1}\left(  k\right)  $ and thus
$\omega\left(  i+j\right)  \neq k$. Combining $\omega\left(  i+j\right)
\in\left\{  1,2,\ldots,k\right\}  $ with $\omega\left(  i+j\right)  \neq k$, we
obtain $\omega\left(  i+j\right)  \in\left\{  1,2,\ldots,k\right\}
\setminus\left\{  k\right\}  =\left\{  1,2,\ldots,k-1\right\}  $. Thus, the
element $\left\{
\begin{array}
[c]{c}%
\omega\left(  i+j\right)  ,\ \ \ \ \ \ \ \ \ \ \text{if }j\leq k-i;\\
\omega\left(  j-k+i\right)  ,\ \ \ \ \ \ \ \ \ \ \text{if }j>k-i
\end{array}
\right.  $ of $\left\{  1,2,\ldots,k-1\right\}  $ is well-defined (because we
have%
\begin{align*}
\left\{
\begin{array}
[c]{c}%
\omega\left(  i+j\right)  ,\ \ \ \ \ \ \ \ \ \ \text{if }j\leq k-i;\\
\omega\left(  j-k+i\right)  ,\ \ \ \ \ \ \ \ \ \ \text{if }j>k-i
\end{array}
\right.   &  =\omega\left(  i+j\right)  \ \ \ \ \ \ \ \ \ \ \left(
\text{since }j\leq k-i\right) \\
&  \in\left\{  1,2,\ldots,k-1\right\}
\end{align*}
). We have thus proven that the element $\left\{
\begin{array}
[c]{c}%
\omega\left(  i+j\right)  ,\ \ \ \ \ \ \ \ \ \ \text{if }j\leq k-i;\\
\omega\left(  j-k+i\right)  ,\ \ \ \ \ \ \ \ \ \ \text{if }j>k-i
\end{array}
\right.  $ of $\left\{  1,2,\ldots,k-1\right\}  $ is well-defined in Case 1.
\par
Now let us consider Case 2. In this case, $j>k-i$. Hence, $j+i>k$, so that
$j-k+i>0$. On the other hand, we have $i\in\left\{  1,2,\ldots,k\right\}  $, and
thus $i\leq k$. Moreover, $j\in\left\{  1,2,\ldots,k-1\right\}  $, so that $j<k$.
Thus, $\underbrace{j}_{<k}-k+\underbrace{i}_{\leq k}<k-k+k=k$. Hence,
$j-k+i\leq k$. Combined with $j-k+i>0$, this yields $j-k+i\in\left\{
1,2,\ldots,k\right\}  $. Hence, $\omega\left(  j-k+i\right)  $ is a well-defined
element of $\left\{  1,2,\ldots,k\right\}  $. Since $\underbrace{j}%
_{<k}-k+i<k-k+i=i$, we have $j-k+i\neq i=\omega^{-1}\left(  k\right)  $ and
thus $\omega\left(  j-k+i\right)  \neq k$. Combining $\omega\left(
j-k+i\right)  \in\left\{  1,2,\ldots,k\right\}  $ with $\omega\left(
j-k+i\right)  \neq k$, we obtain $\omega\left(  j-k+i\right)  \in\left\{
1,2,\ldots,k\right\}  \setminus\left\{  k\right\}  =\left\{  1,2,\ldots,k-1\right\}
$. Thus, the element $\left\{
\begin{array}
[c]{c}%
\omega\left(  i+j\right)  ,\ \ \ \ \ \ \ \ \ \ \text{if }j\leq k-i;\\
\omega\left(  j-k+i\right)  ,\ \ \ \ \ \ \ \ \ \ \text{if }j>k-i
\end{array}
\right.  $ of $\left\{  1,2,\ldots,k-1\right\}  $ is well-defined (because we
have%
\begin{align*}
\left\{
\begin{array}
[c]{c}%
\omega\left(  i+j\right)  ,\ \ \ \ \ \ \ \ \ \ \text{if }j\leq k-i;\\
\omega\left(  j-k+i\right)  ,\ \ \ \ \ \ \ \ \ \ \text{if }j>k-i
\end{array}
\right.   &  =\omega\left(  j-k+i\right)  \ \ \ \ \ \ \ \ \ \ \left(
\text{since }j>k-i\right) \\
&  \in\left\{  1,2,\ldots,k-1\right\}
\end{align*}
). We have thus proven that the element $\left\{
\begin{array}
[c]{c}%
\omega\left(  i+j\right)  ,\ \ \ \ \ \ \ \ \ \ \text{if }j\leq k-i;\\
\omega\left(  j-k+i\right)  ,\ \ \ \ \ \ \ \ \ \ \text{if }j>k-i
\end{array}
\right.  $ of $\left\{  1,2,\ldots,k-1\right\}  $ is well-defined in Case 2.
\par
Hence, in each of the Cases 1 and 2, we have shown that the element $\left\{
\begin{array}
[c]{c}%
\omega\left(  i+j\right)  ,\ \ \ \ \ \ \ \ \ \ \text{if }j\leq k-i;\\
\omega\left(  j-k+i\right)  ,\ \ \ \ \ \ \ \ \ \ \text{if }j>k-i
\end{array}
\right.  $ of $\left\{  1,2,\ldots,k-1\right\}  $ is well-defined. Since the
Cases 1 and 2 cover all possibilities, this yields that the element $\left\{
\begin{array}
[c]{c}%
\omega\left(  i+j\right)  ,\ \ \ \ \ \ \ \ \ \ \text{if }j\leq k-i;\\
\omega\left(  j-k+i\right)  ,\ \ \ \ \ \ \ \ \ \ \text{if }j>k-i
\end{array}
\right.  $ of $\left\{  1,2,\ldots,k-1\right\}  $ is always well-defined, qed.}.
Hence, we can define a map $\tau:\left\{  1,2,\ldots,k-1\right\}  \rightarrow
\left\{  1,2,\ldots,k-1\right\}  $ by%
\[
\left(  \tau\left(  j\right)  =\left\{
\begin{array}
[c]{c}%
\omega\left(  i+j\right)  ,\ \ \ \ \ \ \ \ \ \ \text{if }j\leq k-i;\\
\omega\left(  j-k+i\right)  ,\ \ \ \ \ \ \ \ \ \ \text{if }j>k-i
\end{array}
\right.  \ \ \ \ \ \ \ \ \ \ \text{for all }j\in\left\{  1,2,\ldots,k-1\right\}
\right)  .
\]
Consider this map $\tau$. It is easy to see that
\begin{equation}
\left(  \tau\left(  1\right)  ,\tau\left(  2\right)  ,\ldots,\tau\left(
k-1\right)  \right)  =\left(  \omega\left(  i+1\right)  ,\omega\left(
i+2\right)  ,\ldots,\omega\left(  k\right)  ,\omega\left(  1\right)
,\omega\left(  2\right)  ,\ldots,\omega\left(  i-1\right)  \right)
\label{l5.1a.pf.5}%
\end{equation}
\footnote{\textit{Proof of (\ref{l5.1a.pf.5}):} Every $j\in\left\{
1,2,\ldots,k-i\right\}  $ satisfies%
\begin{align*}
\tau\left(  j\right)   &  =\left\{
\begin{array}
[c]{c}%
\omega\left(  i+j\right)  ,\ \ \ \ \ \ \ \ \ \ \text{if }j\leq k-i;\\
\omega\left(  j-k+i\right)  ,\ \ \ \ \ \ \ \ \ \ \text{if }j>k-i
\end{array}
\right.  =\omega\left(  i+j\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }j\leq k-i\text{ (since }%
j\in\left\{  1,2,\ldots,k-1\right\}  \text{)}\right)  .
\end{align*}
Hence,
\[
\left(  \tau\left(  1\right)  ,\tau\left(  2\right)  ,\ldots,\tau\left(
k-i\right)  \right)  =\left(  \omega\left(  i+1\right)  ,\omega\left(
i+2\right)  ,\ldots,\omega\left(  i+k-i\right)  \right)  =\left(  \omega\left(
i+1\right)  ,\omega\left(  i+2\right)  ,\ldots,\omega\left(  k\right)  \right)
\]
(since $i+k-i=k$).
\par
Every $j\in\left\{  1,2,\ldots,i-1\right\}  $ satisfies%
\begin{align*}
\tau\left(  k-i+j\right)   &  =\left\{
\begin{array}
[c]{c}%
\omega\left(  i+\left(  k-i+j\right)  \right)  ,\ \ \ \ \ \ \ \ \ \ \text{if
}k-i+j\leq k-i;\\
\omega\left(  \left(  k-i+j\right)  -k+i\right)  ,\ \ \ \ \ \ \ \ \ \ \text{if
}k-i+j>k-i
\end{array}
\right.  \ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of }\tau\left(
k-i+j\right)  \right) \\
&  =\omega\left(  \underbrace{\left(  k-i+j\right)  -k+i}_{=j}\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }k-i+j>k-i\text{ (since }j>0\text{
(since }j\in\left\{  1,2,\ldots,i-1\right\}  \text{))}\right) \\
&  =\omega\left(  j\right)  .
\end{align*}
Hence,
\[
\left(  \tau\left(  k-i+1\right)  ,\tau\left(  k-i+2\right)  ,\ldots,\tau\left(
k-1\right)  \right)  =\left(  \omega\left(  1\right)  ,\omega\left(  2\right)
,\ldots,\omega\left(  i-1\right)  \right)  .
\]
\par
Now, whenever $\alpha$ and $\beta$ are two (finite) lists of objects, let us
denote by $\operatorname*{concat}\left(  \alpha,\beta\right)  $ the
concatenation of the lists $\alpha$ and $\beta$. (This concatenation
$\operatorname*{concat}\left(  \alpha,\beta\right)  $ is defined to be the
list $\left(  \alpha_{1},\alpha_{2},\ldots,\alpha_{u},\beta_{1},\beta
_{2},\ldots,\beta_{v}\right)  $, where the lists $\alpha$ and $\beta$ are written
in the forms $\alpha=\left(  \alpha_{1},\alpha_{2},\ldots,\alpha_{u}\right)  $
and $\beta=\left(  \beta_{1},\beta_{2},\ldots,\beta_{v}\right)  $). By the
definition of concatenation, we have%
\begin{align*}
&  \operatorname*{concat}\left(  \left(  \omega\left(  i+1\right)
,\omega\left(  i+2\right)  ,\ldots,\omega\left(  k\right)  \right)  ,\left(
\omega\left(  1\right)  ,\omega\left(  2\right)  ,\ldots,\omega\left(
i-1\right)  \right)  \right) \\
&  =\left(  \omega\left(  i+1\right)  ,\omega\left(  i+2\right)
,\ldots,\omega\left(  k\right)  ,\omega\left(  1\right)  ,\omega\left(  2\right)
,\ldots,\omega\left(  i-1\right)  \right)
\end{align*}
and%
\begin{align*}
&  \operatorname*{concat}\left(  \left(  \tau\left(  1\right)  ,\tau\left(
2\right)  ,\ldots,\tau\left(  k-i\right)  \right)  ,\left(  \tau\left(
k-i+1\right)  ,\tau\left(  k-i+2\right)  ,\ldots,\tau\left(  k-1\right)  \right)
\right) \\
&  =\left(  \tau\left(  1\right)  ,\tau\left(  2\right)  ,\ldots,\tau\left(
k-i\right)  ,\tau\left(  k-i+1\right)  ,\tau\left(  k-i+2\right)
,\ldots,\tau\left(  k-1\right)  \right)  =\left(  \tau\left(  1\right)
,\tau\left(  2\right)  ,\ldots,\tau\left(  k-1\right)  \right)  .
\end{align*}
Thus,%
\begin{align*}
&  \left(  \tau\left(  1\right)  ,\tau\left(  2\right)  ,\ldots,\tau\left(
k-1\right)  \right) \\
&  =\operatorname*{concat}\left(  \underbrace{\left(  \tau\left(  1\right)
,\tau\left(  2\right)  ,\ldots,\tau\left(  k-i\right)  \right)  }_{=\left(
\omega\left(  i+1\right)  ,\omega\left(  i+2\right)  ,\ldots,\omega\left(
k\right)  \right)  },\underbrace{\left(  \tau\left(  k-i+1\right)
,\tau\left(  k-i+2\right)  ,\ldots,\tau\left(  k-1\right)  \right)  }_{=\left(
\omega\left(  1\right)  ,\omega\left(  2\right)  ,\ldots,\omega\left(
i-1\right)  \right)  }\right) \\
&  =\operatorname*{concat}\left(  \left(  \omega\left(  i+1\right)
,\omega\left(  i+2\right)  ,\ldots,\omega\left(  k\right)  \right)  ,\left(
\omega\left(  1\right)  ,\omega\left(  2\right)  ,\ldots,\omega\left(
i-1\right)  \right)  \right) \\
&  =\left(  \omega\left(  i+1\right)  ,\omega\left(  i+2\right)
,\ldots,\omega\left(  k\right)  ,\omega\left(  1\right)  ,\omega\left(  2\right)
,\ldots,\omega\left(  i-1\right)  \right)  .
\end{align*}
This proves (\ref{l5.1a.pf.5}).}. Hence,%
\begin{align}
&  \left\{  \tau\left(  1\right)  ,\tau\left(  2\right)  ,\ldots,\tau\left(
k-1\right)  \right\} \nonumber\\
&  =\left\{  \omega\left(  i+1\right)  ,\omega\left(  i+2\right)
,\ldots,\omega\left(  k\right)  ,\omega\left(  1\right)  ,\omega\left(  2\right)
,\ldots,\omega\left(  i-1\right)  \right\} \nonumber\\
&  =\left\{  \omega\left(  i+1\right)  ,\omega\left(  i+2\right)
,\ldots,\omega\left(  k\right)  \right\}  \cup\left\{  \omega\left(  1\right)
,\omega\left(  2\right)  ,\ldots,\omega\left(  i-1\right)  \right\} \nonumber\\
&  =\left\{  \omega\left(  1\right)  ,\omega\left(  2\right)  ,\ldots,\omega
\left(  i-1\right)  \right\}  \cup\left\{  \omega\left(  i+1\right)
,\omega\left(  i+2\right)  ,\ldots,\omega\left(  k\right)  \right\}  .
\label{l5.1a.pf.6}%
\end{align}
On the other hand, any sets $A$ and $B$ satisfy%
\begin{equation}
A\cup B\setminus B\subseteq A. \label{l5.1a.pf.7}%
\end{equation}
Since $\omega\in\mathfrak{S}_{k}$, we know that $\omega$ is a bijective map
from $\left\{  1,2,\ldots,k\right\}  \rightarrow\left\{  1,2,\ldots,k\right\}  $.
Hence,%
\begin{align*}
\left\{  1,2,\ldots,k\right\}   &  =\omega\left(  \left\{  1,2,\ldots,k\right\}
\right)  =\left\{  \omega\left(  1\right)  ,\omega\left(  2\right)
,\ldots,\omega\left(  k\right)  \right\} \\
&  =\underbrace{\left\{  \omega\left(  1\right)  ,\omega\left(  2\right)
,\ldots,\omega\left(  i\right)  \right\}  }_{=\left\{  \omega\left(  1\right)
,\omega\left(  2\right)  ,\ldots,\omega\left(  i-1\right)  \right\}  \cup\left\{
\omega\left(  i\right)  \right\}  }\cup\left\{  \omega\left(  i+1\right)
,\omega\left(  i+2\right)  ,\ldots,\omega\left(  k\right)  \right\} \\
&  =\left\{  \omega\left(  1\right)  ,\omega\left(  2\right)  ,\ldots,\omega
\left(  i-1\right)  \right\}  \cup\left\{  \underbrace{\omega\left(  i\right)
}_{\substack{=k\\\text{(since }i=\omega^{-1}\left(  k\right)  \text{)}%
}}\right\}  \cup\left\{  \omega\left(  i+1\right)  ,\omega\left(  i+2\right)
,\ldots,\omega\left(  k\right)  \right\} \\
&  =\left\{  \omega\left(  1\right)  ,\omega\left(  2\right)  ,\ldots,\omega
\left(  i-1\right)  \right\}  \cup\left\{  k\right\}  \cup\left\{
\omega\left(  i+1\right)  ,\omega\left(  i+2\right)  ,\ldots,\omega\left(
k\right)  \right\} \\
&  =\left\{  \omega\left(  1\right)  ,\omega\left(  2\right)  ,\ldots,\omega
\left(  i-1\right)  \right\}  \cup\left\{  \omega\left(  i+1\right)
,\omega\left(  i+2\right)  ,\ldots,\omega\left(  k\right)  \right\}  \cup\left\{
k\right\}  .
\end{align*}
Thus,%
\begin{align*}
&  \left\{  1,2,\ldots,k\right\}  \setminus\left\{  k\right\} \\
&  =\left(  \left\{  \omega\left(  1\right)  ,\omega\left(  2\right)
,\ldots,\omega\left(  i-1\right)  \right\}  \cup\left\{  \omega\left(
i+1\right)  ,\omega\left(  i+2\right)  ,\ldots,\omega\left(  k\right)  \right\}
\cup\left\{  k\right\}  \right)  \setminus\left\{  k\right\} \\
&  \subseteq\left\{  \omega\left(  1\right)  ,\omega\left(  2\right)
,\ldots,\omega\left(  i-1\right)  \right\}  \cup\left\{  \omega\left(
i+1\right)  ,\omega\left(  i+2\right)  ,\ldots,\omega\left(  k\right)  \right\}
\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{by (\ref{l5.1a.pf.7}), applied to}\\
A=\left\{  \omega\left(  1\right)  ,\omega\left(  2\right)  ,\ldots,\omega\left(
i-1\right)  \right\}  \cup\left\{  \omega\left(  i+1\right)  ,\omega\left(
i+2\right)  ,\ldots,\omega\left(  k\right)  \right\}  \text{ and }B=\left\{
k\right\}
\end{array}
\right) \\
&  =\left\{  \tau\left(  1\right)  ,\tau\left(  2\right)  ,\ldots,\tau\left(
k-1\right)  \right\}  \ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{l5.1a.pf.6}%
)}\right) \\
&  =\tau\left(  \left\{  1,2,\ldots,k-1\right\}  \right)  .
\end{align*}
Hence, $\left\{  1,2,\ldots,k-1\right\}  =\left\{  1,2,\ldots,k\right\}
\setminus\left\{  k\right\}  \subseteq\tau\left(  \left\{
1,2,\ldots,k-1\right\}  \right)  $. The map $\tau$ is thus surjective.

But it is a known fact that any surjective map from a finite set to itself
must be bijective. Applying this to the map $\tau$ (which is a surjective map
from the finite set $\left\{  1,2,\ldots,k-1\right\}  $ to itself), we conclude
that the map $\tau$ is bijective. Thus we know that $\tau$ is a bijective map
from the set $\left\{  1,2,\ldots,k-1\right\}  $ to itself. In other words,
$\tau$ is a permutation of $\left\{  1,2,\ldots,k-1\right\}  $. That is, $\tau
\in\mathfrak{S}_{k-1}$. Hence, there exists a permutation $\sigma
\in\mathfrak{S}_{k-1}$ such that
\[
\left(  \sigma\left(  1\right)  ,\sigma\left(  2\right)  ,\ldots,\sigma\left(
k-1\right)  \right)  =\left(  \omega\left(  i+1\right)  ,\omega\left(
i+2\right)  ,\ldots,\omega\left(  k\right)  ,\omega\left(  1\right)
,\omega\left(  2\right)  ,\ldots,\omega\left(  i-1\right)  \right)
\]
(namely, $\sigma=\tau$). This proves Lemma 5.1a.

Here is another, even simpler, lemma for our proof:

\textbf{Lemma 5.1b.} Let $G$ be a group. Let $g\in G$. Let $S$ be a subset of
$G$. If $S\subseteq Z_{G}\left(  \left\{  g\right\}  \right)  $, then
$\left\langle S\right\rangle \subseteq Z_{G}\left(  \left\{  g\right\}
\right)  $. (Here, $Z_{G}\left(  \left\{  g\right\}  \right)  $ denotes the
centralizer of the subset $\left\{  g\right\}  $ of $G$, and $\left\langle
S\right\rangle $ denotes the subgroup of $G$ generated by the subset $S$).

\textit{Proof of Lemma 5.1b.} Let us recall that $\left\langle S\right\rangle
$ is the subgroup of $G$ generated by the subset $S$. Hence, every subgroup of
$G$ which contains $S$ as a subset must also contain $\left\langle
S\right\rangle $ as a subset. In other words,%
\begin{equation}
\text{every subgroup }H\text{ of }G\text{ which satisfies }S\subseteq H\text{
must also satisfy }\left\langle S\right\rangle \subseteq H. \label{l5.1b.pf.1}%
\end{equation}


Now, assume that $S\subseteq Z_{G}\left(  \left\{  g\right\}  \right)  $. It
is known that the centralizer of any subset of $G$ is a subgroup of $G$.
Applying this to the subset $\left\{  g\right\}  $ of $G$, we conclude that
the centralizer of the subset $\left\{  g\right\}  $ of $G$ is a subgroup of
$G$. In other words, $Z_{G}\left(  \left\{  g\right\}  \right)  $ is a
subgroup of $G$ (since $Z_{G}\left(  \left\{  g\right\}  \right)  $ is the
centralizer of the subset $\left\{  g\right\}  $ of $G$). Hence,
(\ref{l5.1b.pf.1}) (applied to $H=Z_{G}\left(  \left\{  g\right\}  \right)  $)
shows that $\left\langle S\right\rangle \subseteq Z_{G}\left(  \left\{
g\right\}  \right)  $. Lemma 5.1b is thus proven.

Finally, here is a definition and a third lemma:

\textbf{Definition.} The product sign $\overrightarrow{\prod\limits_{i=\alpha
}^{\beta}}$ is defined by
\[
\left(
\begin{array}
[c]{l}%
\overrightarrow{\prod\limits_{i=\alpha}^{\beta}}f\left(  i\right)  =f\left(
\alpha\right)  f\left(  \alpha+1\right)  \cdots f\left(  \beta\right) \\
\ \ \ \ \ \ \ \ \ \ \text{for any }\alpha\in\mathbb{N}\text{ and }\beta
\in\mathbb{N}\text{ satisfying }\alpha-1\leq\beta\text{,}\\
\ \ \ \ \ \ \ \ \ \ \text{every monoid }M\text{ and every map }f:\left\{
\alpha,\alpha+1,\ldots,\beta\right\}  \rightarrow M
\end{array}
\right)  .
\]


\textbf{Lemma 5.1c.} Let $\ell$ be a positive integer such that $\ell>1$. Let
$G$ be a group. Let $g_{1}$, $g_{2}$, $\ldots$, $g_{\ell}$ be $\ell$ elements of
$G$. Let $\omega\in\mathfrak{S}_{\ell}$. Then, there exists a $\sigma
\in\mathfrak{S}_{\ell-1}$ and an $\alpha\in\left\langle g_{1},g_{2}%
,\ldots,g_{\ell-1}\right\rangle $ such that%
\[
\overrightarrow{\prod\limits_{i=1}^{\ell}}g_{\omega\left(  i\right)  }=\alpha
g_{\ell}\cdot\left(  \overrightarrow{\prod\limits_{i=1}^{\ell-1}}%
g_{\sigma\left(  i\right)  }\right)  \cdot\alpha^{-1}.
\]


\textit{Proof of Lemma 5.1c.} Since $\omega\in\mathfrak{S}_{\ell}$, we know
that $\omega$ is a permutation. Hence, $\omega$ is invertible.

Let $a=\omega^{-1}\left(  \ell\right)  $. Then, $\omega\left(  a\right)
=\ell$. Applying Lemma 5.1a to $k=\ell$ and $a=i$, we conclude that there
exists a permutation $\sigma\in\mathfrak{S}_{\ell-1}$ such that
\[
\left(  \sigma\left(  1\right)  ,\sigma\left(  2\right)  ,\ldots,\sigma\left(
\ell-1\right)  \right)  =\left(  \omega\left(  a+1\right)  ,\omega\left(
a+2\right)  ,\ldots,\omega\left(  \ell\right)  ,\omega\left(  1\right)
,\omega\left(  2\right)  ,\ldots,\omega\left(  a-1\right)  \right)  .
\]
Denote this $\sigma$ by $\tau$. Thus, $\tau\in\mathfrak{S}_{\ell-1}$ is a
permutation such that
\begin{equation}
\left(  \tau\left(  1\right)  ,\tau\left(  2\right)  ,\ldots,\tau\left(
\ell-1\right)  \right)  =\left(  \omega\left(  a+1\right)  ,\omega\left(
a+2\right)  ,\ldots,\omega\left(  \ell\right)  ,\omega\left(  1\right)
,\omega\left(  2\right)  ,\ldots,\omega\left(  a-1\right)  \right)  .
\label{l5.1c.pf.3}%
\end{equation}


Let $\beta=g_{\omega\left(  1\right)  }g_{\omega\left(  2\right)
} \cdots g_{\omega\left(  a-1\right)  }\in G$. Notice that $\beta\in\left\langle
g_{1},g_{2},\ldots,g_{\ell-1}\right\rangle $\ \ \ \ \footnote{\textit{Proof.} Let
$i\in\left\{  1,2,\ldots,a-1\right\}  $. Then, $i<a$ (since $i\in\left\{
1,2,\ldots,a-1\right\}  $), so that $i\neq a=\omega^{-1}\left(  \ell\right)  $.
In other words, $\omega\left(  i\right)  \neq\ell$. Combined with
$\omega\left(  i\right)  \in\left\{  1,2,\ldots,\ell\right\}  $ (since $\omega
\in\mathfrak{S}_{\ell}$), this yields $\omega\left(  i\right)  \in\left\{
1,2,\ldots,\ell\right\}  \setminus\left\{  \ell\right\}  =\left\{  1,2,\ldots,\ell
-1\right\}  $. Thus, $g_{\omega\left(  i\right)  }\in\left\{  g_{1}%
,g_{2},\ldots,g_{\ell-1}\right\}  \subseteq\left\langle \left\{  g_{1}%
,g_{2},\ldots,g_{\ell-1}\right\}  \right\rangle =\left\langle g_{1}%
,g_{2},\ldots,g_{\ell-1}\right\rangle $.
\par
Now, forget that we fixed $i$. We thus have proven that every $i\in\left\{
1,2,\ldots,a-1\right\}  $ satisfies $g_{\omega\left(  i\right)  }\in\left\langle
g_{1},g_{2},\ldots,g_{\ell-1}\right\rangle $. Thus,
\begin{align*}
g_{\omega\left(  1\right)  }g_{\omega\left(  2\right)  } \cdots g_{\omega\left(
a-1\right)  }  &  \in\underbrace{\left\langle g_{1},g_{2},\ldots,g_{\ell
-1}\right\rangle \cdot\left\langle g_{1},g_{2},\ldots,g_{\ell-1}\right\rangle
\cdot \cdots \cdot\left\langle g_{1},g_{2},\ldots,g_{\ell-1}\right\rangle }_{a-1\text{
factors}}\\
&  \subseteq\left\langle g_{1},g_{2},\ldots,g_{\ell-1}\right\rangle
\ \ \ \ \ \ \ \ \ \ \left(  \text{since }\left\langle g_{1},g_{2}%
,\ldots,g_{\ell-1}\right\rangle \text{ is a subgroup of }G\right)  .
\end{align*}
Hence, $\beta=g_{\omega\left(  1\right)  }g_{\omega\left(  2\right)
} \cdots g_{\omega\left(  a-1\right)  }\in\left\langle g_{1},g_{2},\ldots,g_{\ell
-1}\right\rangle $, qed.}

Now,%
\begin{align*}
\overrightarrow{\prod\limits_{i=1}^{\ell-1}}g_{\tau\left(  i\right)  }  &
=g_{\tau\left(  1\right)  }g_{\tau\left(  2\right)  } \cdots g_{\tau\left(
\ell-1\right)  }=g_{\omega\left(  a+1\right)  }g_{\omega\left(  a+2\right)
} \cdots g_{\omega\left(  \ell\right)  }g_{\omega\left(  1\right)  }g_{\omega
\left(  2\right)  } \cdots g_{\omega\left(  a-1\right)  }\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{due to (\ref{l5.1c.pf.3})}\right) \\
&  =\left(  g_{\omega\left(  a+1\right)  }g_{\omega\left(  a+2\right)
} \cdots g_{\omega\left(  \ell\right)  }\right)  \left(  g_{\omega\left(  1\right)
}g_{\omega\left(  2\right)  }\cdots g_{\omega\left(  a-1\right)  }\right)  .
\end{align*}
Hence,%
\begin{align*}
&  \underbrace{\beta}_{=g_{\omega\left(  1\right)  }g_{\omega\left(  2\right)
}\cdots g_{\omega\left(  a-1\right)  }}\underbrace{g_{\ell}}_{\substack{=g_{\omega
\left(  a\right)  }\\\text{(since }\ell=\omega\left(  a\right)  \text{)}%
}}\cdot\underbrace{\left(  \overrightarrow{\prod\limits_{i=1}^{\ell-1}}%
g_{\tau\left(  i\right)  }\right)  }_{=\left(  g_{\omega\left(  a+1\right)
}g_{\omega\left(  a+2\right)  }\cdots g_{\omega\left(  \ell\right)  }\right)
\left(  g_{\omega\left(  1\right)  }g_{\omega\left(  2\right)  }%
\cdots g_{\omega\left(  a-1\right)  }\right)  }\cdot\underbrace{\beta^{-1}%
}_{\substack{=\left(  g_{\omega\left(  1\right)  }g_{\omega\left(  2\right)
}\cdots g_{\omega\left(  a-1\right)  }\right)  ^{-1}\\\text{(since }%
\beta=g_{\omega\left(  1\right)  }g_{\omega\left(  2\right)  }\cdots g_{\omega
\left(  a-1\right)  }\text{)}}}\\
&  =\left(  g_{\omega\left(  1\right)  }g_{\omega\left(  2\right)
}\cdots g_{\omega\left(  a-1\right)  }\right)  g_{\omega\left(  a\right)  }\left(
g_{\omega\left(  a+1\right)  }g_{\omega\left(  a+2\right)  }\cdots g_{\omega
\left(  \ell\right)  }\right)  \underbrace{\left(  g_{\omega\left(  1\right)
}g_{\omega\left(  2\right)  }\cdots g_{\omega\left(  a-1\right)  }\right)  \left(
g_{\omega\left(  1\right)  }g_{\omega\left(  2\right)  }\cdots g_{\omega\left(
a-1\right)  }\right)  ^{-1}}_{=1}\\
&  =\left(  g_{\omega\left(  1\right)  }g_{\omega\left(  2\right)
}\cdots g_{\omega\left(  a-1\right)  }\right)  g_{\omega\left(  a\right)  }\left(
g_{\omega\left(  a+1\right)  }g_{\omega\left(  a+2\right)  }\cdots g_{\omega
\left(  \ell\right)  }\right)  =g_{\omega\left(  1\right)  }g_{\omega\left(
2\right)  }\cdots g_{\omega\left(  \ell\right)  }=\overrightarrow{\prod
\limits_{i=1}^{\ell}}g_{\omega\left(  i\right)  }.
\end{align*}
Hence, $\overrightarrow{\prod\limits_{i=1}^{\ell}}g_{\omega\left(  i\right)
}=\beta g_{\ell}\cdot\left(  \overrightarrow{\prod\limits_{i=1}^{\ell-1}%
}g_{\tau\left(  i\right)  }\right)  \cdot\beta^{-1}$. Thus, there exists a
$\sigma\in\mathfrak{S}_{\ell-1}$ and an $\alpha\in\left\langle g_{1}%
,g_{2},\ldots,g_{\ell-1}\right\rangle $ such that $\overrightarrow{\prod
\limits_{i=1}^{\ell}}g_{\omega\left(  i\right)  }=\alpha g_{\ell}\cdot\left(
\overrightarrow{\prod\limits_{i=1}^{\ell-1}}g_{\sigma\left(  i\right)
}\right)  \cdot\alpha^{-1}$ (namely, $\sigma=\tau$ and $\alpha=\beta$). Lemma
5.1c is thus proven.

Now, here is a minor restatement of the Lemma 5.1 that we want to prove:

\textbf{Lemma 5.1d.} Let $G$ be a group. Let $n\in\mathbb{N}$. Let $g_{1}$,
$g_{2}$, $\ldots$, $g_{n}$ be $n$ elements of $G$. Assume that $g_{i}^{2}=1$ for
every $i\in\left\{  1,2,\ldots,n\right\}  $. Assume also that $\left(  g_{i}%
g_{j}\right)  ^{2}=1$ for every two $i\in\left\{  1,2,\ldots,n\right\}  $ and
$j\in\left\{  1,2,\ldots,n\right\}  $ satisfying $\left\vert i-j\right\vert >1$.
Then, for any $\omega\in\mathfrak{S}_{n}$ and $\nu\in\mathfrak{S}_{n}$, the
elements $\overrightarrow{\prod\limits_{i=1}^{n}}g_{\omega\left(  i\right)  }$
and $\overrightarrow{\prod\limits_{i=1}^{n}}g_{\nu\left(  i\right)  }$ of $G$
are conjugate.

This Lemma 5.1d is a bit more general than your Lemma 5.1, since $g_{1}$,
$g_{2}$, $\ldots$, $g_{n}$ are only required to be elements (not generators) of
$G$; but this generality is superficial, since one can derive Lemma 5.1d from
Lemma 5.1 very easily using an appropriate quotient of the free group. We will
prove Lemma 5.1d; this will immediately yield the validity of Lemma 5.1.

Indeed, we will prove a (non-superficial) generalization of Lemma 5.1d:

\textbf{Lemma 5.1e.} Let $G$ be a group. Let $n\in\mathbb{N}$. Let $g_{1}$,
$g_{2}$, $\ldots$, $g_{n}$ be $n$ elements of $G$. Assume also that $g_{i}%
g_{j}=g_{j}g_{i}$ for every two $i\in\left\{  1,2,\ldots,n\right\}  $ and
$j\in\left\{  1,2,\ldots,n\right\}  $ satisfying $\left\vert i-j\right\vert >1$.
Then, for any $\omega\in\mathfrak{S}_{n}$ and $\nu\in\mathfrak{S}_{n}$, the
elements $\overrightarrow{\prod\limits_{i=1}^{n}}g_{\omega\left(  i\right)  }$
and $\overrightarrow{\prod\limits_{i=1}^{n}}g_{\nu\left(  i\right)  }$ of $G$
are conjugate.

\textit{Proof of Lemma 5.1e.} If $n=0$, then the claim of Lemma 5.1e is
obviously true\footnote{\textit{Proof.} Assume that $n=0$. Let $\omega
\in\mathfrak{S}_{n}$ and $\nu\in\mathfrak{S}_{n}$. Then, $\omega
\in\mathfrak{S}_{n}=\mathfrak{S}_{0}$ (since $n=0$). Hence, $\omega
\in\mathfrak{S}_{0}=\left\{  \operatorname*{id}\right\}  $, so that
$\omega=\operatorname*{id}$. Similarly, $\nu=\operatorname*{id}$. Thus,
$\omega=\operatorname*{id}=\nu$. Hence, $\overrightarrow{\prod\limits_{i=1}%
^{n}}g_{\omega\left(  i\right)  }=\overrightarrow{\prod\limits_{i=1}^{n}%
}g_{\nu\left(  i\right)  }$. Thus, the elements $\overrightarrow{\prod
\limits_{i=1}^{n}}g_{\omega\left(  i\right)  }$ and $\overrightarrow{\prod
\limits_{i=1}^{n}}g_{\nu\left(  i\right)  }$ of $G$ are conjugate (because any
two equal elements of a group are conjugate). Thus, Lemma 5.1e is proven when
$n=0$.}. Hence, for the rest of this proof, we can WLOG assume that $n\neq0$.
Assume this. Thus, $n\neq0$, so that $n\geq1$.

We are going to prove that%
\begin{equation}
\left(
\begin{array}
[c]{c}%
\text{for any }k\in\left\{  1,2,\ldots,n\right\}  \text{ and any }\omega
\in\mathfrak{S}_{k}\text{ and }\nu\in\mathfrak{S}_{k}\text{, there exists}\\
\text{an }\alpha\in\left\langle g_{1},g_{2},\ldots,g_{k-1}\right\rangle \text{
such that }\overrightarrow{\prod\limits_{i=1}^{k}}g_{\omega\left(  i\right)
}=\alpha\cdot\left(  \overrightarrow{\prod\limits_{i=1}^{k}}g_{\nu\left(
i\right)  }\right)  \cdot\alpha^{-1}%
\end{array}
\right)  . \label{l5.1.pf.main}%
\end{equation}


\textit{Proof of (\ref{l5.1.pf.main}):} We will prove (\ref{l5.1.pf.main}) by
induction over $k$:

\textit{Induction base:} If $k=1$, then (\ref{l5.1.pf.main}) is obviously
true\footnote{\textit{Proof.} Assume that $k=1$. Let $\omega\in\mathfrak{S}%
_{k}$ and $\nu\in\mathfrak{S}_{k}$. Then, $\omega\in\mathfrak{S}%
_{k}=\mathfrak{S}_{1}$ (since $k=1$). Hence, $\omega\in\mathfrak{S}%
_{1}=\left\{  \operatorname*{id}\right\}  $, so that $\omega
=\operatorname*{id}$. Similarly, $\nu=\operatorname*{id}$. Thus,
$\omega=\operatorname*{id}=\nu$. Hence,%
\[
\overrightarrow{\prod\limits_{i=1}^{k}}g_{\omega\left(  i\right)
}=\overrightarrow{\prod\limits_{i=1}^{k}}g_{\nu\left(  i\right)
}=\operatorname*{id}\cdot\left(  \overrightarrow{\prod\limits_{i=1}^{k}}%
g_{\nu\left(  i\right)  }\right)  \cdot\operatorname*{id}\nolimits^{-1}.
\]
Hence, there exists an $\alpha\in\left\langle g_{1},g_{2},\ldots,g_{k-1}%
\right\rangle $ such that $\overrightarrow{\prod\limits_{i=1}^{k}}%
g_{\omega\left(  i\right)  }=\alpha\cdot\left(  \overrightarrow{\prod
\limits_{i=1}^{k}}g_{\nu\left(  i\right)  }\right)  \cdot\alpha^{-1}$ (namely,
$\alpha=\operatorname*{id}$). Thus, (\ref{l5.1.pf.main}) is proven when
$k=1$.}. This completes the induction base.

\textit{Induction step:} Let $\ell\in\left\{  1,2,\ldots,n\right\}  $ be such
that $\ell>1$. Assume that (\ref{l5.1.pf.main}) holds for $k=\ell-1$. We need
to prove that (\ref{l5.1.pf.main}) holds for $k=\ell$.

Let $\omega\in\mathfrak{S}_{\ell}$ and $\nu\in\mathfrak{S}_{\ell}$.

Due to Lemma 5.1c, there exists a $\sigma\in\mathfrak{S}_{\ell-1}$ and an
$\alpha\in\left\langle g_{1},g_{2},\ldots,g_{\ell-1}\right\rangle $ such that
$\overrightarrow{\prod\limits_{i=1}^{\ell}}g_{\omega\left(  i\right)  }=\alpha
g_{\ell}\cdot\left(  \overrightarrow{\prod\limits_{i=1}^{\ell-1}}%
g_{\sigma\left(  i\right)  }\right)  \cdot\alpha^{-1}$. Denote these $\sigma$
and $\alpha$ as $\omega^{\prime}$ and $\gamma$, respectively. Thus,
$\omega^{\prime}\in\mathfrak{S}_{\ell-1}$ and $\gamma\in\left\langle
g_{1},g_{2},\ldots,g_{\ell-1}\right\rangle $ satisfy
\begin{equation}
\overrightarrow{\prod\limits_{i=1}^{\ell}}g_{\omega\left(  i\right)  }=\gamma
g_{\ell}\cdot\left(  \overrightarrow{\prod\limits_{i=1}^{\ell-1}}%
g_{\omega^{\prime}\left(  i\right)  }\right)  \cdot\gamma^{-1}.
\label{l5.1e.pf.gamma}%
\end{equation}


Due to Lemma 5.1c (applied to $\nu$ instead of $\omega$), there exists a
$\sigma\in\mathfrak{S}_{\ell-1}$ and an $\alpha\in\left\langle g_{1}%
,g_{2},\ldots,g_{\ell-1}\right\rangle $ such that $\overrightarrow{\prod
\limits_{i=1}^{\ell}}g_{\nu\left(  i\right)  }=\alpha g_{\ell}\cdot\left(
\overrightarrow{\prod\limits_{i=1}^{\ell-1}}g_{\sigma\left(  i\right)
}\right)  \cdot\alpha^{-1}$. Denote these $\sigma$ and $\alpha$ as
$\nu^{\prime}$ and $\delta$, respectively. Thus, $\nu^{\prime}\in
\mathfrak{S}_{\ell-1}$ and $\delta\in\left\langle g_{1},g_{2},\ldots,g_{\ell
-1}\right\rangle $ satisfy
\begin{equation}
\overrightarrow{\prod\limits_{i=1}^{\ell}}g_{\nu\left(  i\right)  }=\delta
g_{\ell}\cdot\left(  \overrightarrow{\prod\limits_{i=1}^{\ell-1}}%
g_{\nu^{\prime}\left(  i\right)  }\right)  \cdot\delta^{-1}.
\label{l5.1e.pf.delta}%
\end{equation}


We have assumed that (\ref{l5.1.pf.main}) holds for $k=\ell-1$. Hence, we can
apply (\ref{l5.1.pf.main}) to $\ell-1$, $\omega^{\prime}$ and $\nu^{\prime}$
instead of $k$, $\omega$ and $\nu$. As a consequence, we conclude that there
exists an $\alpha\in\left\langle g_{1},g_{2},\ldots,g_{\left(  \ell-1\right)
-1}\right\rangle $ such that $\overrightarrow{\prod\limits_{i=1}^{\ell-1}%
}g_{\omega^{\prime}\left(  i\right)  }=\alpha\cdot\left(
\overrightarrow{\prod\limits_{i=1}^{\ell-1}}g_{\nu^{\prime}\left(  i\right)
}\right)  \cdot\alpha^{-1}$. Denote this $\alpha$ by $\beta$. Thus, $\beta
\in\left\langle g_{1},g_{2},\ldots,g_{\left(  \ell-1\right)  -1}\right\rangle $
satisfies%
\begin{equation}
\overrightarrow{\prod\limits_{i=1}^{\ell-1}}g_{\omega^{\prime}\left(
i\right)  }=\beta\cdot\left(  \overrightarrow{\prod\limits_{i=1}^{\ell-1}%
}g_{\nu^{\prime}\left(  i\right)  }\right)  \cdot\beta^{-1}.
\label{l5.1e.pf.beta}%
\end{equation}


Notice that
\begin{align*}
\beta &  \in\left\langle g_{1},g_{2},\ldots,g_{\left(  \ell-1\right)
-1}\right\rangle =\left\langle \underbrace{\left\{  g_{1},g_{2},\ldots,g_{\left(
\ell-1\right)  -1}\right\}  }_{\subseteq\left\{  g_{1},g_{2},\ldots,g_{\ell
-1}\right\}  }\right\rangle \subseteq\left\langle \left\{  g_{1}%
,g_{2},\ldots,g_{\ell-1}\right\}  \right\rangle \\
&  =\left\langle g_{1},g_{2},\ldots,g_{\ell-1}\right\rangle .
\end{align*}


Now, it is easy to see that $g_{\ell}\beta=\beta g_{\ell}$%
\ \ \ \ \footnote{\textit{Proof.} By the conditions of Lemma 5.1e, we have%
\begin{equation}
g_{i}g_{j}=g_{j}g_{i}\text{ for every two }i\in\left\{  1,2,\ldots,n\right\}
\text{ and }j\in\left\{  1,2,\ldots,n\right\}  \text{ satisfying }\left\vert
i-j\right\vert >1. \label{l5.1e.pf.4}%
\end{equation}
\par
But by the definition of the centralizer $N_{G}\left(  \left\{  g_{\ell
}\right\}  \right)  $ of the set $\left\{  g_{\ell}\right\}  $, we have%
\begin{align}
N_{G}\left(  \left\{  g_{\ell}\right\}  \right)   &  =\left\{  y\in
G\ \mid\ \underbrace{xy=yx\text{ for every }x\in\left\{  g_{\ell}\right\}
}_{\substack{\text{this assertion is equivalent to }\left(  g_{\ell}%
y=yg_{\ell}\right)  \\\text{(since the only }x\in\left\{  g_{\ell}\right\}
\text{ is }g_{\ell}\text{)}}}\right\} \nonumber\\
&  =\left\{  y\in G\ \mid\ g_{\ell}y=yg_{\ell}\right\}  . \label{l5.1e.pf.5}%
\end{align}
\par
Now, let $i\in\left\{  1,2,\ldots,\left(  \ell-1\right)  -1\right\}  $. Then,
$i\in\left\{  1,2,\ldots,n\right\}  $. Moreover, since $i\in\left\{
1,2,\ldots,\left(  \ell-1\right)  -1\right\}  $, we have $i\leq\left(
\ell-1\right)  -1=\ell-2$, so that $\ell-i\geq2$. Thus, $\ell-i$ is positive,
so that $\left\vert \ell-i\right\vert =\ell-i\geq2>1$. Hence,
(\ref{l5.1e.pf.4}) (applied to $\ell$ and $i$ instead of $i$ and $j$) yields
$g_{\ell}g_{i}=g_{i}g_{\ell}$.
\par
So $g_{i}\in G$ satisfies $g_{\ell}g_{i}=g_{i}g_{\ell}$. Thus, $g_{i}%
\in\left\{  y\in G\ \mid\ g_{\ell}y=yg_{\ell}\right\}  =N_{G}\left(  \left\{
g_{\ell}\right\}  \right)  $ (due to (\ref{l5.1e.pf.5})).
\par
Now, forget that we fixed $i$. We thus have proven that $g_{i}\in N_{G}\left(
\left\{  g_{\ell}\right\}  \right)  $ for every $i\in\left\{  1,2,\ldots,\left(
\ell-1\right)  -1\right\}  $. In other words, $\left\{  g_{1},g_{2}%
,\ldots,g_{\left(  \ell-1\right)  -1}\right\}  \subseteq N_{G}\left(  \left\{
g_{\ell}\right\}  \right)  $. According to Lemma 5.1b (applied to $\left\{
g_{1},g_{2},\ldots,g_{\left(  \ell-1\right)  -1}\right\}  $ and $g_{\ell}$
instead of $S$ and $g$), this yields $\left\langle \left\{  g_{1}%
,g_{2},\ldots,g_{\left(  \ell-1\right)  -1}\right\}  \right\rangle \subseteq
N_{G}\left(  \left\{  g_{\ell}\right\}  \right)  $. Now,%
\[
\beta\in\left\langle g_{1},g_{2},\ldots,g_{\left(  \ell-1\right)  -1}%
\right\rangle =\left\langle \left\{  g_{1},g_{2},\ldots,g_{\left(  \ell-1\right)
-1}\right\}  \right\rangle \subseteq N_{G}\left(  \left\{  g_{\ell}\right\}
\right)  =\left\{  y\in G\ \mid\ g_{\ell}y=yg_{\ell}\right\}
\]
(by (\ref{l5.1e.pf.5})). In other words, $g_{\ell}\beta=\beta g_{\ell}$,
qed.}. Now, (\ref{l5.1e.pf.gamma}) becomes%
\begin{align}
\overrightarrow{\prod\limits_{i=1}^{\ell}}g_{\omega\left(  i\right)  }  &
=\gamma g_{\ell}\cdot\underbrace{\left(  \overrightarrow{\prod\limits_{i=1}%
^{\ell-1}}g_{\omega^{\prime}\left(  i\right)  }\right)  }_{\substack{=\beta
\cdot\left(  \overrightarrow{\prod\limits_{i=1}^{\ell-1}}g_{\nu^{\prime
}\left(  i\right)  }\right)  \cdot\beta^{-1}\\\text{(by (\ref{l5.1e.pf.beta}%
))}}}\cdot\gamma^{-1}\nonumber\\
&  =\gamma\underbrace{g_{\ell}\beta}_{=\beta g_{\ell}}\cdot\left(
\overrightarrow{\prod\limits_{i=1}^{\ell-1}}g_{\nu^{\prime}\left(  i\right)
}\right)  \cdot\beta^{-1}\gamma^{-1}=\gamma\underbrace{\beta}_{=\beta
\delta^{-1}\delta}g_{\ell}\cdot\left(  \overrightarrow{\prod\limits_{i=1}%
^{\ell-1}}g_{\nu^{\prime}\left(  i\right)  }\right)  \cdot\underbrace{\beta
^{-1}}_{=\delta^{-1}\delta\beta^{-1}}\gamma^{-1}\nonumber\\
&  =\gamma\beta\delta^{-1}\underbrace{\delta g_{\ell}\cdot\left(
\overrightarrow{\prod\limits_{i=1}^{\ell-1}}g_{\nu^{\prime}\left(  i\right)
}\right)  \cdot\delta^{-1}}_{\substack{=\overrightarrow{\prod\limits_{i=1}%
^{\ell}}g_{\nu\left(  i\right)  }\\\text{(by (\ref{l5.1e.pf.delta}))}}%
}\delta\beta^{-1}\gamma^{-1}\nonumber\\
&  =\gamma\beta\delta^{-1}\cdot\left(  \overrightarrow{\prod\limits_{i=1}%
^{\ell}}g_{\nu\left(  i\right)  }\right)  \cdot\underbrace{\delta\beta
^{-1}\gamma^{-1}}_{=\left(  \delta^{-1}\right)  ^{-1}\beta^{-1}\gamma
^{-1}=\left(  \gamma\beta\delta^{-1}\right)  ^{-1}}\nonumber\\
&  =\gamma\beta\delta^{-1}\cdot\left(  \overrightarrow{\prod\limits_{i=1}%
^{\ell}}g_{\nu\left(  i\right)  }\right)  \cdot\left(  \gamma\beta\delta
^{-1}\right)  ^{-1}. \label{l5.1e.pf.gbd}%
\end{align}


Now, we know that $\gamma\in\left\langle g_{1},g_{2},\ldots,g_{\ell
-1}\right\rangle $, $\beta\in\left\langle g_{1},g_{2},\ldots,g_{\ell
-1}\right\rangle $ and $\delta\in\left\langle g_{1},g_{2},\ldots,g_{\ell
-1}\right\rangle $. Hence,%
\begin{align*}
\gamma\beta\delta^{-1}  &  \in\left\langle g_{1},g_{2},\ldots,g_{\ell
-1}\right\rangle \cdot\left\langle g_{1},g_{2},\ldots,g_{\ell-1}\right\rangle
\cdot\left\langle g_{1},g_{2},\ldots,g_{\ell-1}\right\rangle ^{-1}\\
&  \subseteq\left\langle g_{1},g_{2},\ldots,g_{\ell-1}\right\rangle
\ \ \ \ \ \ \ \ \ \ \left(  \text{since }\left\langle g_{1},g_{2}%
,\ldots,g_{\ell-1}\right\rangle \text{ is a subgroup of }G\right)  .
\end{align*}


So we know that $\gamma\beta\delta^{-1}$ is an element of $\left\langle
g_{1},g_{2},\ldots,g_{\ell-1}\right\rangle $ satisfying (\ref{l5.1e.pf.gbd}).
Thus, there exists an $\alpha\in\left\langle g_{1},g_{2},\ldots,g_{\ell
-1}\right\rangle $ such that $\overrightarrow{\prod\limits_{i=1}^{\ell}%
}g_{\omega\left(  i\right)  }=\alpha\cdot\left(  \overrightarrow{\prod
\limits_{i=1}^{\ell}}g_{\nu\left(  i\right)  }\right)  \cdot\alpha^{-1}$
(namely, $\alpha=\gamma\beta\delta^{-1}$).

Now, forget that we have fixed $\omega$ and $\nu$. We have thus shown that for
any $\omega\in\mathfrak{S}_{k}$ and $\nu\in\mathfrak{S}_{k}$, there exists an
$\alpha\in\left\langle g_{1},g_{2},\ldots,g_{k-1}\right\rangle $ such that
$\overrightarrow{\prod\limits_{i=1}^{k}}g_{\omega\left(  i\right)  }%
=\alpha\cdot\left(  \overrightarrow{\prod\limits_{i=1}^{k}}g_{\nu\left(
i\right)  }\right)  \cdot\alpha^{-1}$. In other words, (\ref{l5.1.pf.main})
holds for $k=\ell$. This completes the induction step. Thus, the induction
proof of (\ref{l5.1.pf.main}) is complete.

Now, applying (\ref{l5.1.pf.main}) to $k=n$, we conclude that for any
$\omega\in\mathfrak{S}_{n}$ and $\nu\in\mathfrak{S}_{n}$, there exists an
$\alpha\in\left\langle g_{1},g_{2},\ldots,g_{n-1}\right\rangle $ such that
$\overrightarrow{\prod\limits_{i=1}^{n}}g_{\omega\left(  i\right)  }%
=\alpha\cdot\left(  \overrightarrow{\prod\limits_{i=1}^{n}}g_{\nu\left(
i\right)  }\right)  \cdot\alpha^{-1}$. Hence, for any $\omega\in
\mathfrak{S}_{n}$ and $\nu\in\mathfrak{S}_{n}$, the elements
$\overrightarrow{\prod\limits_{i=1}^{n}}g_{\omega\left(  i\right)  }$ and
$\overrightarrow{\prod\limits_{i=1}^{n}}g_{\nu\left(  i\right)  }$ of $G$ are
conjugate. This proves Lemma 5.1e.

Now, very little has to be done to prove Lemma 5.1d (and thus Lemma 5.1):

\textit{Proof of Lemma 5.1d.} We have%
\begin{equation}
g_{i}^{2}=1\text{ for every }i\in\left\{  1,2,\ldots,n\right\}  .
\label{l5.1d.pf.1}%
\end{equation}
We also have%
\begin{equation}
\left(  g_{i}g_{j}\right)  ^{2}=1\text{ for every two }i\in\left\{
1,2,\ldots,n\right\}  \text{ and }j\in\left\{  1,2,\ldots,n\right\}  \text{
satisfying }\left\vert i-j\right\vert >1. \label{l5.1d.pf.2}%
\end{equation}


Now, we have $g_{i}g_{j}=g_{j}g_{i}$ for every two $i\in\left\{
1,2,\ldots,n\right\}  $ and $j\in\left\{  1,2,\ldots,n\right\}  $ satisfying
$\left\vert i-j\right\vert >1$\ \ \ \ \footnote{\textit{Proof.} Let
$i\in\left\{  1,2,\ldots,n\right\}  $ and $j\in\left\{  1,2,\ldots,n\right\}  $ be
two elements satisfying $\left\vert i-j\right\vert >1$. Then, $\left(
g_{i}g_{j}\right)  ^{2}=1$ (by (\ref{l5.1d.pf.2})). Also, $g_{i}^{2}=1$ (by
(\ref{l5.1d.pf.1})) and $g_{j}^{2}=1$ (by (\ref{l5.1d.pf.1}), applied to $j$
instead of $i$). From $\left(  g_{i}g_{j}\right)  ^{2}=1$, we obtain
$1=\left(  g_{i}g_{j}\right)  ^{2}=g_{i}g_{j}g_{i}g_{j}$. Multiplying this by
$g_{j}g_{i}$ from the right, we obtain $g_{j}g_{i}=g_{i}g_{j}g_{i}%
\underbrace{g_{j}g_{j}}_{=g_{j}^{2}=1}g_{i}=g_{i}g_{j}\underbrace{g_{i}g_{i}%
}_{=1}=g_{i}g_{j}$. Thus, $g_{i}g_{j}=g_{j}g_{i}$, qed.}. Hence, we can apply
Lemma 5.1e. As a consequence, we conclude that for any $\omega\in
\mathfrak{S}_{n}$ and $\nu\in\mathfrak{S}_{n}$, the elements
$\overrightarrow{\prod\limits_{i=1}^{n}}g_{\omega\left(  i\right)  }$ and
$\overrightarrow{\prod\limits_{i=1}^{n}}g_{\nu\left(  i\right)  }$ of $G$ are
conjugate. This proves Lemma 5.1e.
\end{verlong}


\end{document}