New approaches to plactic monoid via Gröbner-Shirshov bases
We present the plactic algebra on an arbitrary alphabet set $A$ by row generators and column generators respectively. We give Gröbner-Shirshov bases for such presentations. In the case of column generators, a finite Gröbner-Shirshov basis is given if $A$ is finite. From the Composition-Diamond lemma for associative algebras, it follows that the set of Young tableaux is a linear basis of plactic algebra. As the result, it gives a new proof that Young tableaux are normal forms of elements of plactic monoid. This result was proved by D.E. Knuth \cite{Knuth} in 1970, see also Chapter 5 in \cite{M.L}.
\section{Introduction}\label{Intro}

Let $A=\{1,2,\dots,n\}$ with $1<2<\dots<n$. Then we call
$$
Pl(A):=sgp\langle A|\Omega\rangle=A^*/\equiv
$$
a plactic monoid on the alphabet set $A$, see \cite{M.L}, where
$A^*$ is the free monoid generated by $A$, $\equiv$ is the
congruence of $A^*$ generated by the Knuth relations $\Omega$ and
$\Omega$ consists of
\begin{eqnarray*}
&&\sigma_i\sigma_k\sigma_j= \sigma_k\sigma_i\sigma_j \ (i\leq j<k),\\
&&\sigma_j\sigma_i\sigma_k= \sigma_j\sigma_k\sigma_i \ (i< j\leq k).
\end{eqnarray*}

Let $F$ be a field. Then $F\langle A|\Omega\rangle$ is called the
plactic monoid algebra over $F$ of  $Pl(A)$.

The basic theory of plactic monoid was systematically developed in
Lascoux and Sch$\ddot{u}$tzenberger \cite{M.L.M.-P} in 1981.

D.E. Knuth \cite{Knuth} in 1970, see also Chapter 5 in \cite{M.L},
shows that Young tableaux are normal forms of elements of plactic
monoid.

In a recent paper \cite{Okninskii}, with the deg-lex ordering on
$A^*$, a finite Gr\"{o}bner-Shirshov basis for plactic algebra is
given when $n=3$. They prove that for $n>3$, a corresponding
Gr\"{o}bner-Shirshov basis must be infinite. In fact, it is an open
problem to give a corresponding Gr\"{o}bner-Shirshov basis by using
such a presentation and the deg-lex ordering on $A^*$.

In this paper, we present the plactic algebra on an arbitrary
alphabet set $A$ by row generators. We give a Gr\"{o}bner-Shirshov
basis for such the presentation. From the Composition-Diamond lemma
for associative algebras, it follows that the set of Young tableaux
is a linear basis of plactic algebra. As the result, it gives a new
proof that Young tableaux are normal forms of elements of plactic
monoid.

\section{Preliminaries}\label{pre1}
We first cite some concepts and results from the literatures
\cite{Bo72, Bo76, Sh62,Shir3} which are related to
Gr\"{o}bner-Shirshov bases for associative algebras.

Let $X$ be a set and $F$ a field.  Throughout this paper, we denote
$F\langle X\rangle$ the free associative algebra over $F$ generated
by $X$,  $X^*$ the free monoid generated by $X$ and
 $N$ the set of non-negative integers.

A well ordering $<$ on $X^*$ is called monomial if for $u, v\in
X^*$, we have
$$
u < v \Rightarrow w|_u < w|_v\  \ for \  all \
 w\in  X^*,
$$
where $w|_u=w|_{x_i\mapsto u}, \ w|_v=w|_{x_i\mapsto v}$ and
$x_{i}$'s are the same individuality of the letter $x_{i}\in X$ in
$w$.

A standard example of monomial ordering on $X^*$ is the deg-lex
ordering which first compare two words by degree and then by
comparing them lexicographically, where $X$ is a well-ordered set.

Let $X^*$ be a set with a monomial ordering $<$. Then, for any
non-zero polynomial $f\in F\langle X\rangle$, $f$ has the leading
word $\overline{f}$. We call $f$  monic if the coefficient of
$\overline{f}$ is 1. By $|\overline{f}|$ we denote the degree
(length) of $\overline{f}$.

Let $f,\ g\in F\langle X\rangle$ be two monic polynomials and $w\in
X^*$. If  $w=\overline{f}b=a\overline{g}$  for some $a,b\in X^*$
such that $|\overline{f}|+|\overline{g}|>|w|$, then $(f,g)_w=fb-ag$
is called the intersection composition of $f,g$ relative to $w$. If
$w=\overline{f}=a\overline{g}b$  for some $a, b\in X^*$, then
$(f,g)_w=f-agb$ is called the inclusion composition of $f,g$
relative to $w$.

Let $S\subset F\langle X\rangle$ be a monic set. A composition
$(f,g)_w$ is called trivial modulo $(S,w)$, denoted by
$$
(f,g)_w\equiv0 \ \ \ mod(S,w)
$$
if $(f,g)_w=\sum\alpha_ia_is_ib_i,$ where every $\alpha_i\in k, \
s_i\in S,\ a_i,b_i\in X^*$, and $a_i\overline{s_i}b_i<w$.

Recall that $S$ is a Gr\"{o}bner-Shirshov basis in $F\langle
X\rangle$ if any composition of polynomials from $S$ is trivial
modulo $S$ and corresponding $w$.

The following lemma was first proved by Shirshov \cite{Sh62,Shir3}
for free Lie algebras (with deg-lex ordering) (see also Bokut
\cite{Bo72}). Bokut \cite{Bo76} specialized the approach of Shirshov
to associative algebras (see also Bergman \cite{Be}). For
commutative polynomials, this lemma is known as Buchberger's Theorem
(see \cite{Bu65, Bu70}).

\begin{lemma}\label{l1}
(Composition-Diamond lemma for associative algebras) \ Let $F$ be a
field,  $<$ a monomial ordering on $X^*$ and $Id(S)$ the ideal of $F
\langle X\rangle$ generated by $S$. Then the following statements
are equivalent:

\begin{enumerate}
\item[1)] $S$ is a Gr\"{o}bner-Shirshov basis in $F\langle
X\rangle$.
\item[2)] $f\in Id(S)\Rightarrow \bar{f}=a\bar{s}b$
for some $s\in S$ and $a,b\in  X^*$.
\item[3)] $Irr(S) = \{ u \in X^* |  u \neq a\bar{s}b,s\in S,a ,b \in X^*\}$
is an $F$-basis of the algebra $A=F\langle X | S \rangle=F\langle
X\rangle/Id(S)$.
\end{enumerate}
\end{lemma}

If a subset $S$ of $F\langle X \rangle$ is not a
Gr\"{o}bner-Shirshov basis then one can add all nontrivial
compositions of polynomials of $S$ to $S$. Continuing this process
repeatedly, we finally obtain a Gr\"{o}bner-Shirshov basis
$S^{comp}$ that contains $S$. Such a process is called Shirshov
algorithm.

Let $A=sgp\langle X|S\rangle$ be a semigroup representation. Then $S$
is also a subset of $F\langle X \rangle$ and we can find
Gr\"{o}bner-Shirshov basis
 $S^{comp}$. We also call $S^{comp}$ a
Gr\"{o}bner-Shirshov basis of $A$. $Irr(S^{comp})=\{u\in X^*|u\neq
a\overline{f}b,\ a ,b \in X^*,\ f\in S^{comp}\}$ is an $F$-basis of
$F\langle X|S\rangle$ which is also a normal form of the semigroup
$A$.
\section{Main theorem}
Let $A=\{\sigma_i|i\in I\}$ be a well-ordered alphabet set. Then we
call
$$
Pl(A):=sgp\langle A|\Omega\rangle=A^*/\equiv
$$
a plactic monoid on the alphabet set $A$, see \cite{M.L}, where
$\equiv$ is the congruence of $A^*$ generated by the Knuth relations
$\Omega$ and $\Omega$ consists of
\begin{eqnarray*}
&&\sigma_i\sigma_k\sigma_j= \sigma_k\sigma_i\sigma_j \ (\sigma_i\leq \sigma_j<\sigma_k),\\
&&\sigma_j\sigma_i\sigma_k= \sigma_j\sigma_k\sigma_i \ (\sigma_i<
\sigma_j\leq \sigma_k).
\end{eqnarray*}

\ \

Now, suppose that  $A=\{1,2,\dots,n\}$ with $1<2<\dots<n$.

Let $N$ be the set of non-negative integers. A word $R\in A^*$ is
called a row if it is nondecreasing, for example, $R=111225$ is a
row. For convenience, denote  $R=(r_1,r_2,\dots, r_n)$, where $r_i$
is the number of letter $i\ (i=1,2,\dots,n)$, for example,
$R=111225=(3,2,0,0,1,0,\dots,0)$.


Let $U=\{R\in A^*\ |\ R \mbox{ is a row} \}$.



We order the set $U^*$ as follows.

Let $R=(r_1,r_2,\dots, r_n)\in U$. Then $|R|=r_1+\dots+r_n$ is the
length of $R$ in $A^*$.

We first order $U$: for any $R, S\in U$, $ R<S $ if and  only if
$|R|<|S|$ or $|R|=|S|$ and there exists a $t \ (0\leq t< n)$ such
that $r_i=s_i, \ i=1,\dots, t$ and $r_{t+1}>s_{t+1}.$ Clearly, this
is a well ordering on $U$.

Then, we order $U^*$ by the deg-lex ordering. We will use this
ordering throughout this paper.

Let $R,S\in U$. Then $R$ dominates $ S$ if $|R|\leq|S|$ and each
letter of $R$ is larger than the corresponding letter of $S$.



A (semistandard) Young tableau on $A$ (see \cite{M.L}) is a word
$w=R_1R_2 \cdots R_t\in U^*$ such that
 $R_{i}$ dominates $R_{i+1},\ i=1,\dots,t-1$. For example,
 $4556\cdot223357\cdot1112444$ is a Young tableau.

The following algorithm was introduced by Schensted \cite{Schensted}
in 1961.

\begin{definition}\label{def3}
(Schensted's algorithm \cite{Schensted})\\
Let $R\in U$, $x\in$ A.
$$
R\cdot x= \left\{
\begin{array}{cc}
    Rx,& if~Rx~is~a~row, \\
    y\cdot R',& otherwise
\end{array}
\right.
$$
where $y$ is the leftmost letter in $R$ and is strictly larger than
$x$, and $R'=R\mid _{y\mapsto x}$, i.e., $R'$ is obtained from $R$
by replacing $y$ by $x$.
\end{definition}

Then, for any $R,S\in U$, by induction,  it is clear that there
exist uniquely $R',S'\in U$ such that $R\cdot S=R'\cdot S'$ and
$R'\cdot S'$ is a Young tableau, where $R'$ is empty if $R\cdot
S=S'$ is a row.

It is clear that
$$
sgp\langle U\mid \Lambda\rangle=sgp\langle A\mid
\Omega\rangle
$$
and so $F\langle U\mid \Lambda\rangle=F\langle A\mid \Omega\rangle$,
where $\Lambda=\{R\cdot S=R'\cdot S',\ R,S\in U\}$.






The following is the main theorem of the paper.

\begin{theorem}\label{mainTH}
Let the notation be as before. Then with the deg-lex ordering on
$U^*$, $\Lambda$ is a Gr\"{o}bner-Shirshov basis for the plactic
algebra $F\langle U\mid \Lambda\rangle$.
\end{theorem}

By using Composition-Diamond lemma for associative algebras (Lemma
\ref{l1}) and Theorem \ref{mainTH}, we have the following corollary.

\begin{corollary}\label{co1}(\cite{M.L}, Chapter 5)
The set of Young tableaux on $A$ is a normal form of the plactic
monoid $sgp\langle A\mid \Omega\rangle$.
\end{corollary}


We will prove Theorem \ref{mainTH} by assuming that
$A=\{1,2,\dots,n\}$ with $1<2<\dots<n$.

\ \

\noindent{\bf Remark}: For an arbitrary well-ordered set $A$, we
define similarly  a row on $A^*$, Schensted's algorithm, Young
tableau on $A$ and the set  $\Lambda$. Then for an arbitrary
well-ordered set $A$, similar to the proof of $A$ to be finite, we
also have Theorem \ref{mainTH} and Corollary \ref{co1}.
\section{A proof of Theorem \ref{mainTH}}
\subsection{Technique formulas}
Let $(\phi_1,\dots,\phi_n)\in U$. Denote
$\Phi_p=\sum_{i=1}^{p}\phi_i\ (1 \leq p \leq n)$, where $\phi$
represents any lowercase symbol and $\Phi$ the corresponding
uppercase symbol.
\begin{definition}\label{def2}
Let $W=(w_1,w_2,\dots,w_n),Z=(z_1,z_2,\dots,z_n)\in U$. Define an
algorithm
\begin{eqnarray*}
W\cdot Z&=&(w_1,w_2,\dots,w_n)(z_1,z_2,\dots,z_n)\\
  &=&(x_1,x_2,\dots,x_n)(y_1,y_2,\dots,y_n)\\
  &=&X\cdot Y
\end{eqnarray*}
where $X=(x_1,x_2,\dots,x_n),Y=(y_1,y_2,\dots,y_n)$, $x_1=0$
and\begin{eqnarray*}
x_p&=&min(Z_{p-1}-X_{p-1},w_p),\\
X_p&=&min(Z_{p-1},X_{p-1}+w_p),\\
y_q&=&w_q+z_q-x_q, \\
Y_q&=&W_q+Z_q-X_q,
\end{eqnarray*}
where $n\geq p\ge 2,\ n\geq q\ge 1$. Clearly, either $X,Y\in U$ or
$Y\in U$ and $X= (0,0,\dots,0)$.
\end{definition}

The formulas in Definition \ref{def2} are very useful in the proof
of Theorem \ref{mainTH}.


\begin{lemma}
The algorithms in Definition \ref{def2} and Definition \ref{def3}
are equivalent.
\end{lemma}
\begin{proof}\ Definition \ref{def2} $\Rightarrow$ Definition \ref{def3}.

Suppose that $W=(w_1,w_2,\dots,w_n)\in U$ and $Z$ is a letter. Then
we can express $Z=(0,\dots,0,z_p,0,\dots,0)$, where $z_p=1  \ (1\leq
p\leq n).$

Clearly $Z_1=Z_2=\dots=Z_{p-1}=0$ and $Z_p=Z_{p+1}=\dots=Z_n=1$.
Since $x_1=X_1=0$ and Definition \ref{def2}, $x_2=min(Z_1-X_1,
w_2)=0$. Similarly, $x_3=x_4=\dots=x_p=0$.

Let $w_j\ (1\leq j\leq n)$ satisfy $w_j\neq0$ and
$w_{j+1}=\dots=w_n=0$. There are two cases to consider.

Case 1. $p\geq j$.

By Definition \ref{def2}, $x_{p+1}=min(Z_{p}-X_{p},
w_{p+1})=min(1-0, 0)=0$. Similarly, $x_{j+1}=\dots=x_n=0$, i.e.,
$X=(0,\dots,0)$. Then $Y=(w_1,\dots,w_{p-1},
w_p+1,w_{p+1},\dots,w_n)$. This means $WZ=Y$ is a row which
corresponds to the first part of Definition \ref{def3}.

Case 2. $p< j$.

There must exist a $w_t, p<t\leq j$ such that $w_t\neq0$ and
$w_k=0,\ p<k<t$. If $p+1=t$, then $x_t=min(Z_{t-1}-X_{t-1},
w_t)=min(1-0, w_t)=1$, and $x_{i}=min(Z_{i-1}-X_{i-1},
w_{i})=min(1-1, w_{i})=0, t+1\leq i \leq n$. If $p+1<t$, then by
Definition \ref{def2}, $x_{p+1}=min(Z_p-X_p, w_{p+1})=min(1-0,
0)=0$. Similarly, $x_{p+2}=\dots=x_{t-1}=0$. Moreover
$x_t=min(Z_{t-1}-X_{t-1}, w_t)=min(1-0, w_t)=1$,
 $x_{t+1}=min(Z_t-X_t, w_{t+1})=0$.
Similarly, $x_{t+2}=\dots=x_n=0$. This shows that
$X=(0,\dots,0,x_t,0,\dots,0)$, where $x_t=1$. Now,
$y_p=w_p+z_p-x_p=w_p+1$, $y_t=w_t+z_t-x_t=w_t-1$ and
$y_i=w_i+z_i-x_i=w_i, 1\leq i\leq n, i\neq p, i\neq t$, i.e.,
$Y=(w_1,\dots,w_p+1,\dots,w_t-1,\dots,w_n)$,  which corresponds to
the second part of Definition \ref{def3}.

Definition \ref{def3} $\Rightarrow$ Definition \ref{def2}.

Clearly, $x_1=0$ and $x_2=min(z_1,w_2)=min(Z_1-X_1,w_2)$.

Assume that for all $t\le m-1\ (t\geq1,\ m\ge 3)$,
$x_t=min(Z_{t-1}-X_{t-1},w_t)$. Then
\begin{eqnarray*}
x_m&=&min(Z_{m-2}-X_{m-2}-x_{m-1}+z_{m-1},w_m)\\
   &=&min(Z_{m-1}-X_{m-1},w_m)
\end{eqnarray*}
which shows that $x_p=min(Z_{p-1}-X_{p-1},w_p)$ for any $p$.


It is obvious that $ X_p=x_p+X_{p-1}=min(Z_{p-1},X_{p-1}+w_p),\
y_q=w_q+z_q-x_q$ and $ Y_q=W_q+Z_q-X_q$.
\end{proof}

\begin{corollary}
In Definition \ref{def2}, $X\cdot Y$ is a Young tableau.
\end{corollary}
\subsection{ Expressions of reductions}\label{mulexp}
In order to prove the Theorem \ref{mainTH}, we have to check that
all possible compositions in $\Lambda$, which are only
intersections, are trivial.

Let $R=(r_1,r_2,\dots,r_n),\ S=(s_1,s_2,\dots,s_n),\
T=(t_1,t_2,\dots,t_n)\in U$.

For reductions, we will use the following notation.
\begin{eqnarray*}
RST&=&\left( \begin{array}{ccccc}
               r_1 & r_2 & r_3 & \dots & r_n \\
               s_1 & s_2 & s_3 & \dots & s_n \\
               t_1 & t_2 & t_3 & \dots & t_n
               \end{array} \right)
        \overset{\text{$S\cdot T=A\cdot B$}}{\Longrightarrow}\left( \begin{array}{ccccc}
                r_1 & r_2 & r_3 & \dots & r_n \\
                a_1 & a_2 & a_3 & \dots & a_n \\
                b_1 & b_2 & b_3 & \dots & b_n
                \end{array} \right)\\
    &\ \overset{\text{$R\cdot A=C\cdot D$}}{\Longrightarrow}&\left( \begin{array}{ccccc}
        c_1 & c_2 & c_3 & \dots & c_n \\
        d_1 & d_2 & d_3 & \dots & d_n \\
        b_1 & b_2 & b_3 & \dots & b_n
        \end{array} \right)
    \overset{\text{$D\cdot B=E\cdot F$}}{\Longrightarrow}\left( \begin{array}{ccccc}
    c_1 & c_2  & c_3 & \dots & c_n \\
    e_1 & e_2 & e_3 & \dots & e_n \\
    f_1 & f_2 & f_3 & \dots & f_n
    \end{array} \right),
\end{eqnarray*}
\begin{eqnarray*}
RST&=&\left( \begin{array}{ccccc}
               r_1 & r_2 & r_3 & \dots & r_n \\
               s_1 & s_2 & s_3 & \dots & s_n \\
               t_1 & t_2 & t_3 & \dots & t_n
               \end{array} \right)
         \overset{\text{$R\cdot S=G\cdot H$}}{\Longrightarrow}\left( \begin{array}{ccccc}
                g_1 & g_2 & g_3 & \dots & g_n \\
                h_1 & h_2 & h_3 & \dots & h_n \\
                t_1 & t_2 & t_3 & \dots & t_n
                \end{array} \right)\\
    &\overset{\text{$H\cdot T=I\cdot J$}}{\Longrightarrow}&\left( \begin{array}{ccccc}
        g_1 & g_2 & g_3 & \dots & g_n \\
        i_1 & i_2 & i_3 & \dots & i_n \\
        j_1 & j_2 & j_3 & \dots & j_n
        \end{array} \right)
    \overset{\text{$G\cdot I=K\cdot L$}}{\Longrightarrow}\left( \begin{array}{ccccc}
    k_1 & k_2 & k_3 & \dots & k_n \\
    l_1 & l_2 & l_3 & \dots & l_n \\
    j_1 & j_2 & j_3 & \dots & j_n
    \end{array} \right),
\end{eqnarray*}\\
where
\begin{eqnarray*}
&&A=(a_1,a_2,\dots,a_n),\ \ B=(b_1,b_2,\dots,b_n),\ \
C=(c_1,c_2,\dots,c_n),\\
&&D=(d_1,d_2,\dots,d_n),\ \ E=(e_1,e_2,\dots,e_n),\ \
F=(f_1,f_2,\dots,f_n),\\
&&G=(g_1,g_2,\dots,g_n),\ \ H=(h_1,h_2,\dots,h_n),\ \
I=(i_1,i_2,\dots,i_n),\\
&&J=(j_1,j_2,\dots,j_n),\ \ K=(k_1,k_2,\dots,k_n),\ \
L=(l_1,l_2,\dots,l_n),
\end{eqnarray*}
and $S\cdot T=A\cdot B,R\cdot A=C\cdot D,D\cdot B=E\cdot F, R\cdot
S=G\cdot H,H\cdot T=I\cdot J,G\cdot I=K\cdot L\in \Lambda$.

We will prove that
\begin{equation*}\label{e1}
\left( \begin{array}{ccccc}
c_1 & c_2  & c_3 & \dots & c_n \\
    e_1 & e_2 & e_3 & \dots & e_n \\
    f_1 & f_2 & f_3 & \dots & f_n
    \end{array} \right)
=\left( \begin{array}{ccccc}
    k_1 & k_2 & k_3 & \dots & k_n \\
    l_1 & l_2 & l_3 & \dots & l_n \\
    j_1 & j_2 & j_3 & \dots & j_n
    \end{array} \right),
\end{equation*}
which implies that the intersection composition $(RS,ST)_{RST}\equiv
0, mod(\Lambda,RST)$. Therefore,
 $\Lambda$ is a
Gr\"{o}bner-Shirshov basis of the algebra $F\langle U\mid
\Lambda\rangle$.

\ \

By the definition of the algorithm in Definition \ref{def2},
$a_1=c_1=c_2=e_1=g_1=i_1=k_1=k_2=l_1=0$.
Therefore, one needs only to show that $c_p=k_p$ and $e_q=l_q$ for all $3\le p\le
n,2\le q\le n$.
\subsection{$c_p=k_p\ (p\ge 3)$} \label{cpkp}
We need the following lemmas to prove $c_p=k_p\ (p\ge 3)$.

\begin{lemma}\label{AleI}
For all $p\ (1\leq p\le n)$, $A_p\le I_p$.
\end{lemma}

\begin{proof} By the algorithm in Definition \ref{def2},
$A_1=a_1=i_1=I_1=0$. Assume that for all $p\le m-1\ (m\ge 2)$,
$A_p\le I_p$. Since
\begin{eqnarray*}
A_m&=&min(T_{m-1},A_{m-1}+s_m),\\
I_m&=&min(T_{m-1},I_{m-1}+h_m),\\
h_m&=&r_m+s_m-g_m\\
   &=&r_m+s_m-min(S_{m-1}-G_{m-1},r_m)\ge s_m,
\end{eqnarray*}
we have $A_m\le I_m$. Now by induction, the result follows.
\end{proof}


\begin{lemma}\label{KeqI}
Assume that $p\geq3, \ K_{p-1}=C_{p-1},\
K_p=C_p=A_{p-1}<C_{p-1}+r_p$ and $S_{p-1}-G_{p-1}\ge r_p$. Then
$K_p=I_{p-1}$.
\end{lemma}

\begin{proof} Note that $ C_p=min(A_{p-1},C_{p-1}+r_p)$ and $
K_p=min(I_{p-1},K_{p-1}+g_p)$.

If $S_{p-1}-G_{p-1}\ge r_p,$ then
$g_p=min(S_{p-1}-G_{p-1},r_p)=r_p.$

Therefore $K_p=C_p=A_{p-1}<C_{p-1}+r_p=K_{p-1}+g_p$, which concludes
$K_p=I_{p-1}$.
\end{proof}

\begin{lemma}\label{CCr2SGr}
Assume that  $p\geq2,\ C_p=K_p,\ C_{p+1}=K_{p+1}$ and
$C_{p+1}=C_p+r_{p+1}$. Then $S_p-G_p\ge r_{p+1}$.
\end{lemma}

\begin{proof} Note that $C_{p+1}=min(A_p,C_p+r_{p+1})$ and
$K_{p+1}=min(I_p,K_p+g_{p})
      =min(I_p,K_p+S_p-G_p,K_p+r_{p+1})$.

If $C_p=K_p,  C_{p+1}=K_{p+1}$ and $C_{p+1}=C_p+r_{p+1}$,
 then
$ K_{p+1}=C_{p+1}
        =C_p+r_{p+1}
        =K_p+r_{p+1}.
$
Therefore, $I_p\ge K_p+r_{p+1}$, $K_p+S_p-G_p\ge K_p+r_{p+1}$, which
concludes $S_p-G_p\ge r_{p+1}$.
\end{proof}


\subsubsection{$C_3=K_3$} \label{c3k3}
\begin{proof}
Since $c_1=c_2=k_1=k_2=0$, we have  $C_3=c_3$ and $K_3=k_3$.
According to the algorithm in Definition \ref{def2},
\begin{eqnarray*}
c_3&=&min(a_2,r_3)\\
   &=&min[min(t_1,s_2),r_3]\\
   &=&min(t_1,s_2,r_3),\\
k_3&=&min(i_2,g_3)\\
   &=&min[min(t_1,h_2),min(s_1+s_2-g_2,r_3)]\\
   &=&min[t_1,r_2+s_2-min(s_1,r_2),s_1+s_2-min(s_1,r_2),r_3]\\
   &=&min[t_1,s_2+min(r_2,s_1)-min(s_1,r_2),r_3]\\
   &=&min(t_1,s_2,r_3).
\end{eqnarray*}
Therefore, $C_3=K_3=min(t_1,s_2,r_3)$.
\end{proof}
\subsubsection{$C_p=K_p$ $(p\ge 4)$}
\begin{proof}
Assume that for all $p\le m-1\ (m\ge 4)$, $C_p=K_p$. Note that
\begin{eqnarray*}
&&C_m=min(T_{m-2},A_{m-2}+s_{m-1},C_{m-1}+r_m), \\
&&K_m=min(T_{m-2},I_{m-2}+h_{m-1},K_{m-1}+M,K_{m-1}+r_m),
\end{eqnarray*}
where $M=s_{m-1}+S_{m-2}-G_{m-2}-g_{m-1}$.


There are three cases to consider.


Case 1. $C_{m-1}=A_{m-2}$.


If $A_{m-2}<C_{m-2}+r_{m-1}$,
$S_{m-2}-G_{m-2}<r_{m-1}$, then
\begin{eqnarray*}
&&C_{m-1}=A_{m-2},\\
&&g_{m-1}=S_{m-2}-G_{m-2}, \\
&&h_{m-1}=r_{m-1}+s_{m-1}-S_{m-2}+G_{m-2}>s_{m-1},\\
&&M=s_{m-1}, \\
&&I_{m-2}+h_{m-1}\ge K_{m-1}+h_{m-1}>K_{m-1}+s_{m-1}.
\end{eqnarray*}
Therefore, $K_m=C_m=min(T_{m-2},C_{m-1}+s_{m-1},C_{m-1}+r_m)$.


If $A_{m-2}<C_{m-2}+r_{m-1}$, $S_{m-2}-G_{m-2}\ge r_{m-1}$, then $
C_{m-1}=A_{m-2},\ g_{m-1}=r_{m-1},\ h_{m-1}=s_{m-1}$ and $M\ge
s_{m-1}$. By Lemma \ref{KeqI}, we have $ K_{m-1}=I_{m-2}$ and $
I_{m-2}+h_{m-1}=K_{m-1}+s_{m-1}$.  Therefore,
$K_m=C_m=min(T_{m-2},C_{m-1}+s_{m-1},C_{m-1}+r_m)$.


Case 2. $C_{m-1}=A_{m-q-2}+\sum_{i=1}^{q+1}r_{m-i}$, where $q\le m-4$.


The condition $C_{m-1}=A_{m-q-2}+\sum_{i=1}^{q+1}r_{m-i}$ implies
that for all $k\le q \ (q\le m-4)$, $C_{m-k-1}+r_{m-k}\le
A_{m-k-1}$. Then
$
C_{m-k}=C_{m-k-1}+r_{m-k}
$
and by Lemma \ref{CCr2SGr}, we have
\begin{eqnarray*}
&&S_{m-k-1}-G_{m-k-1}\ge r_{m-k}, \\
&&g_{m-k}=r_{m-k}, \\
&&h_{m-k}=s_{m-k},
\end{eqnarray*}
\begin{eqnarray*}
&&C_m=min(T_{m-2},T_{m-3}+s_{m-1},\dots,T_{m-q-2}+\sum_{i=1}^{q}s_{m-i},
A_{m-q-2}+\sum_{i=1}^{q+1}s_{m-i},C_{m-1}+r_m),\\
&&K_m=min(T_{m-2},T_{m-3}+s_{m-1},\dots,T_{m-q-2}+\sum_{i=1}^{q}s_{m-i},\\
&&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
I_{m-q-2}+h_{m-q-1}+\sum_{i=1}^{q}s_{m-i},
K_{m-q-1}+\sum_{i=1}^{q}r_{m-i}+M,K_{m-1}+r_m),
\end{eqnarray*}
 where
$M=\sum_{i=1}^{q+1}s_{m-i}+S_{m-q-2}-G_{m-q-2}-g_{m-q-1}-\sum_{i=1}^{q}r_{m-i}$.


If $A_{m-q-2}<C_{m-q-2}+r_{m-q-1}$ and
$S_{m-q-2}-G_{m-q-2}<r_{m-q-1}$, then
\begin{eqnarray*}
&&C_{m-q-1}=A_{m-q-2},\\
&&g_{m-q-1}=S_{m-q-2}-G_{m-q-2},\\
&&h_{m-q-1}=r_{m-q-1}+s_{m-q-1}-S_{m-q-2}+G_{m-q-2}>s_{m-q-1},\\
&&M=\sum_{i=1}^{q+1}s_{m-i}-\sum_{i=1}^{q}r_{m-i},\\
&&K_{m-q-1}+\sum_{i=1}^{q}r_{m-i}+M=K_{m-q-1}+\sum_{i=1}^{q+1}s_{m-i},\\
&&I_{m-q-2}+h_{m-q-1}+\sum_{i=1}^{q}s_{m-i}>K_{m-q-1}+\sum_{i=1}^{q+1}s_{m-i}.
\end{eqnarray*}
Therefore,
\begin{eqnarray*}
K_m&=&min(T_{m-2},T_{m-3}+s_{m-1},\dots,T_{m-q-2}+\sum_{i=1}^{q}s_{m-i},
C_{m-q-1}+\sum_{i=1}^{q+1}s_{m-i},C_{m-1}+r_m)\\
   &=&C_m.
\end{eqnarray*}


If $A_{m-q-2}<C_{m-q-2}+r_{m-q-1}$ and
$S_{m-q-2}-G_{m-q-2}\ge r_{m-q-1}$, then $C_{m-q-1}=A_{m-q-2},$
$g_{m-q-1}=r_{m-q-1}$ and $h_{m-q-1}=s_{m-q-1}$. By Lemma
\ref{KeqI},
\begin{eqnarray*}
&&K_{m-q-1}=I_{m-q-2},\\
&&M\ge \sum_{i=1}^{q+1}s_{m-i}-\sum_{i=1}^{q}r_{m-i},\\
&&K_{m-q-1}+\sum_{i=1}^{q}r_{m-i}+M\ge
K_{m-q-1}+\sum_{i=1}^{q+1}s_{m-i},\\
&&I_{m-q-2}+h_{m-q-1}+\sum_{i=1}^{q}s_{m-i}=K_{m-q-1}+\sum_{i=1}^{q+1}s_{m-i}.
\end{eqnarray*}
Therefore,
\begin{eqnarray*}
K_m=min(T_{m-2},T_{m-3}+s_{m-1},\dots,
T_{m-q-2}+\sum_{i=1}^{q}s_{m-i},C_{m-q-1}+\sum_{i=1}^{q+1}s_{m-i},C_{m-1}+r_m)=C_m.
\end{eqnarray*}


Case 3. $C_{m-1}=C_2+\sum_{i=1}^{m-3}r_{m-i}$.

The condition $C_{m-1}=C_2+\sum_{i=1}^{m-3}r_{m-i}$ implies that for
all $k\le q=m-3$, $C_{m-k-1}+r_{m-k}\le A_{m-k-1}$ and so
$C_{m-k}=C_{m-k-1}+r_{m-k}$. Now, by Lemma \ref{CCr2SGr},
\begin{eqnarray*}
&&S_{m-k-1}-G_{m-k-1}\ge r_{m-k},\\
&&g_{m-k}=r_{m-k},\\
&&h_{m-k}=s_{m-k},\\
M&=&\sum_{i=1}^{m-2}s_{m-i}+S_1-G_1-g_2-\sum_{i=1}^{m-3}r_{m-i}\\
 &=&\sum_{i=1}^{m-2}s_{m-i}+s_1-g_2-\sum_{i=1}^{m-3}r_{m-i}.
\end{eqnarray*}
Thus,
\begin{eqnarray*}
C_m&=&min(T_{m-2},T_{m-3}+s_{m-1},\dots,T_1+\sum_{i=1}^{m-3}s_{m-i},A_1+\sum_{i=1}^{m-2}s_{m-i},C_{m-1}+r_m)\\
   &=&min(T_{m-2},T_{m-3}+s_{m-1},\dots,T_1+\sum_{i=1}^{m-3}s_{m-i},\sum_{i=1}^{m-2}s_{m-i},C_{m-1}+r_m),
\end{eqnarray*}
and
\begin{eqnarray*}
K_m&=&min(T_{m-2},T_{m-3}+s_{m-1},\dots,T_1+\sum_{i=1}^{m-3}s_{m-i},I_1+h_2+\sum_{i=1}^{m-3}s_{m-i},\\
   & &\ \ \ \ \ \ \ K_2+\sum_{i=1}^{m-3}r_{m-i}+M,K_{m-1}+r_m)\\
   &=&min(T_{m-2},T_{m-3}+s_{m-1},\dots,T_1+\sum_{i=1}^{m-3}s_{m-i},\\
        & & \ \ \ \ \ \ \
        \sum_{i=1}^{m-2}s_{m-i}+min(h_2-s_2,s_1-g_2),K_{m-1}+r_m).
\end{eqnarray*}
Since
\begin{eqnarray*}
min(h_2-s_2,s_1-g_2)&=&min[r_2-min(s_1,r_2),s_1-min(s_1,r_2)] \\
                    &=&min(r_2,s_1)-min(s_1,r_2)\\
                    &=&0,
\end{eqnarray*}
one gets
\begin{eqnarray*}
K_m=min(T_{m-2},T_{m-3}+s_{m-1},\dots,T_1+\sum_{i=1}^{m-3}s_{m-i},\sum_{i=1}^{m-2}s_{m-i},K_{m-1}+r_m)=C_m.
\end{eqnarray*}
Therefore, the proof of $K_m=C_m$ is complete.
\end{proof}

\ \

Therefore, we have shown that $C_p=K_p\ (1\leq p\leq n)$ which, by
using the formulas in Definition \ref{def2}, is clearly equivalent
to $c_p=k_p\ (1\leq p\leq n)$.
\subsection{$e_p=l_p$ $(p\ge 2)$}
We need the following lemmas to prove $e_p=l_p\ (p\ge 2)$.

\begin{lemma}\label{SCGAgezero}
For any $p\ (p\le n)$, $S_p+C_p-G_p-A_p\ge 0$.
\end{lemma}

\begin{proof} For $p=1$, we have
$S_{1}+C_{1}-G_{1}-A_{1}=s_1\ge 0$.

Assume that for all $p\le m-1\ (m\ge 2)$, $S_p+C_p-G_p-A_p\ge 0$.

If $A_{m-1}<C_{m-1}+r_m$, then $C_m=A_{m-1}$ and
$$
S_m+C_m-G_m-A_m \ge S_m+A_{m-1}-S_{m-1}-A_{m-1}-s_m=0.
$$
If $C_{m-1}+r_m\le A_{m-1}$, then $C_m=C_{m-1}+r_m$. By section 4.3,
we have $K_m=C_m$ and $K_{m-1}=C_{m-1}$. Then by Lemma
\ref{CCr2SGr},
$$S_{m-1}-G_{m-1}\ge r_m,$$
$$G_m=G_{m-1}+r_m.$$
So,
\begin{eqnarray*}
S_m+C_m-G_m-A_m&=&S_m+C_{m-1}+r_m-G_{m-1}-r_m-A_m\\
               &=&S_m+C_{m-1}-G_{m-1}-A_m\\
               &=&S_{m-1}+C_{m-1}-G_{m-1}-A_{m-1}+s_m-a_m\\
               &\ge & s_m-a_m\\
               &=&s_m-min(T_{m-1}-A_{m-1},s_m)\\
               &\ge & 0.
\end{eqnarray*}


The proof is complete.
\end{proof}


\begin{lemma}\label{AeqI}
If $S_p+C_p-G_p-A_p>0$, then  $A_p=I_p$.
\end{lemma}

\begin{proof}
For $p=1$, we have $A_1=I_1=0$.

Assume that for all $p\le m-1\ (m\ge 2)$, $A_p=I_p$ if
$S_p+C_p-G_p-A_p>0$. By using Lemma \ref{SCGAgezero},
$S_m+C_m-G_m-A_m\ge 0$. Suppose that $S_m+C_m-G_m-A_m>0$. Then by
the proof of Lemma \ref{SCGAgezero}, one of the following four
conditions should be satisfied.


(\ref{AeqI}.1) $A_{m-1}<C_{m-1}+r_m$,
$A_m=T_{m-1}<A_{m-1}+s_m$;


(\ref{AeqI}.2) $A_{m-1}<C_{m-1}+r_m$,
$G_m=G_{m-1}+r_m<S_{m-1}$;


(\ref{AeqI}.3) $C_{m-1}+r_m\le A_{m-1}$,
$S_{m-1}+C_{m-1}-G_{m-1}-A_{m-1}>0$;


(\ref{AeqI}.4)
$C_{m-1}+r_m\le A_{m-1}$, $S_{m-1}+C_{m-1}-G_{m-1}-A_{m-1}=0$,
$s_m>a_m$.


Assume (\ref{AeqI}.1). Then $ C_m=A_{m-1}$, and by Lemma \ref{AleI},
                       $A_m=T_{m-1}<A_{m-1}+s_m\le I_{m-1}+h_m$. So,
                       $ A_m=I_m=T_{m-1}$.

Assume (\ref{AeqI}.2). Then $C_m=A_{m-1},\ g_m=r_m,\ h_m=s_m$, and by
                      Lemma \ref{KeqI}, $K_m=I_{m-1}$. Thus,
                      $A_m=I_m=min(T_{m-1},C_m+s_m)$.

Assume (\ref{AeqI}.3). Then $C_m=C_{m-1}+r_m$. Since $K_m=C_m$ and
$K_{m-1}=C_{m-1}$, by Lemma \ref{CCr2SGr}, we have
                       $S_{m-1}-G_{m-1}\ge r_m$, $g_m=r_m$, $h_m=s_m$ and
                       $A_{m-1}=I_{m-1}$. So,
                       $A_m=I_m=min(T_{m-1},A_{m-1}+s_m)$.

Assume (\ref{AeqI}.4). Then $C_m=C_{m-1}+r_m$ and
$a_m=T_{m-1}-A_{m-1}$. By Lemma \ref{AleI},
$A_m=T_{m-1}<A_{m-1}+s_m\le I_{m-1}+h_m$. So,
                       $A_m=I_m=T_{m-1}$.
\end{proof}


\subsubsection{$e_2=l_2$} \label{e2l2}
\begin{proof}
\begin{eqnarray*}
e_2&=&min(b_1,d_2)\\
   &=&min(s_1+t_1,r_2+a_2)\\
   &=&min[s_1+t_1,r_2+min(t_1,s_2)]\\
   &=&min(s_1+t_1,t_1+r_2,r_2+s_2),\\
l_2&=&g_2+i_2\\
   &=&min(s_1,r_2)+min(t_1,h_2)\\
   &=&min(s_1,r_2)+min[t_1,r_2+s_2-min(s_1,r_2)]\\
   &=&min(s_1+t_1,t_1+r_2,r_2+s_2)\\
   &=&e_2.
\end{eqnarray*}
\end{proof}
\subsubsection{$e_p=l_p$ $(p\ge 3)$} \label{enln}
\begin{proof}
Assume that for any $p\le m-1\ (m\ge 3)$, $e_p=l_p$.


Since $E_{m-1}=L_{m-1}=G_{m-1}+I_{m-1}-K_{m-1}$ and
$K_{m-1}=C_{m-1}=C_m-c_m$, we have
\begin{eqnarray*}
e_m&=&min(B_{m-1}-E_{m-1},d_m)\\
    &=&min(S_{m-1}+T_{m-1}-A_{m-1}-E_{m-1},r_m+a_m-c_m)\\
    &=&min[S_{m-1}+T_{m-1}-A_{m-1}-E_{m-1},r_m+min(T_{m-1}-A_{m-1},s_m)-c_m]\\
    &=&min(S_{m-1}+T_{m-1}+C_m-A_{m-1}-G_{m-1}-I_{m-1},r_m+T_{m-1}-A_{m-1},\\
    & &r_m+s_m)-c_m,\\
l_m&=&g_m+i_m-k_m\\
    &=&min(S_{m-1}-G_{m-1},r_m)+min(T_{m-1}-I_{m-1},h_m)-k_m\\
    &=&min(S_{m-1}+T_{m-1}-G_{m-1}-I_{m-1},S_{m-1}-G_{m-1}+h_m,\\
    & &r_m+T_{m-1}-I_{m-1},r_m+h_m)-k_m.
\end{eqnarray*}


There are two cases to consider.


Case 1. $A_{m-1}<C_{m-1}+r_m$.

Then $C_m=A_{m-1}$.

If $S_{m-1}-G_{m-1}<r_m$, then
\begin{eqnarray*}
&&g_m=S_{m-1}-G_{m-1},\\
&&h_m=r_m+s_m-S_{m-1}+G_{m-1}>s_m,\\
&&S_{m-1}-G_{m-1}+h_m=r_m+s_m<r_m+h_m
\end{eqnarray*}
and by Lemma \ref{AleI},
\begin{eqnarray*}
S_{m-1}+T_{m-1}-G_{m-1}-I_{m-1}&<&r_m+T_{m-1}-I_{m-1}\\
                               &\le& r_m+T_{m-1}-A_{m-1}.
\end{eqnarray*}
Therefore,
$l_m=e_m=min(S_{m-1}+T_{m-1}-G_{m-1}-I_{m-1},r_m+s_m)-c_m$.


If $S_{m-1}-G_{m-1}\ge r_m$, then $g_m=r_m,\ h_m=s_m$, and by
Lemma \ref{KeqI},
\begin{eqnarray*}
&&K_m=I_{m-1},\\
&&S_{m-1}+T_{m-1}-G_{m-1}-I_{m-1}\ge
r_m+T_{m-1}-I_{m-1}=r_m+T_{m-1}-K_m,\\
&&S_{m-1}-G_{m-1}+h_m=S_{m-1}-G_{m-1}+s_m\ge r_m+s_m.
\end{eqnarray*}
Therefore, $l_m=e_m=min(T_{m-1}-C_m,s_m)+r_m-c_m$.


Case 2. $C_{m-1}+r_m\le A_{m-1}$.

Then $C_m=C_{m-1}+r_m$, and by Lemma \ref{CCr2SGr},
\begin{eqnarray*}
&&S_{m-1}-G_{m-1}\ge r_m,\\
&& g_m=r_m,\\
&& h_m=s_m,\\
&&S_{m-1}+T_{m-1}-G_{m-1}-I_{m-1}\ge r_m+T_{m-1}-I_{m-1},\\
&&S_{m-1}-G_{m-1}+h_m\ge r_m+h_m=r_m+s_m,\\
&&e_m=min(S_{m-1}+T_{m-1}+C_{m-1}-A_{m-1}-G_{m-1}-I_{m-1},T_{m-1}-A_{m-1},s_m)+r_m-c_m,\\
&&l_m=min(T_{m-1}-I_{m-1},s_m)+r_m-k_m.
\end{eqnarray*}

By Lemma \ref{SCGAgezero}, $S_{m-1}+C_{m-1}-G_{m-1}-A_{m-1}\ge 0$.


If $S_{m-1}+C_{m-1}-G_{m-1}-A_{m-1}=0$, by Lemma \ref{AleI},
\begin{eqnarray*}
e_m&=&min(T_{m-1}-I_{m-1},T_{m-1}-A_{m-1},s_m)+r_m-c_m\\
   &=&min(T_{m-1}-I_{m-1}, s_m)+r_m-k_m\\
   &=&l_m.
\end{eqnarray*}

If $S_{m-1}+C_{m-1}-G_{m-1}-A_{m-1}>0$, by Lemma \ref{AeqI},
\begin{eqnarray*}
&&A_{m-1}=I_{m-1}, \\
&&S_{m-1}+T_{m-1}+C_{m-1}-A_{m-1}-G_{m-1}-I_{m-1}>T_{m-1}-A_{m-1}.
\end{eqnarray*}
Therefore,
\begin{eqnarray*}
e_m&=&min(T_{m-1}-A_{m-1},s_m)+r_m-c_m\\
   &=&min(T_{m-1}-I_{m-1},s_m)+r_m-k_m\\
   &=&l_m.
\end{eqnarray*}
\end{proof}


\ \

\noindent{\bf Acknowledgement}: The authors would like to thank
Professor L.A. Bokut for his guidance, useful discussions and
enthusiastic encouragement in writing up this paper.




2011-06-24T02:03:37.000
1106
1106.4753
en
https://arxiv.org/abs/1106.4753
We present the plactic algebra on an arbitrary alphabet set $A$ by row generators and column generators respectively. We give Gröbner-Shirshov bases for such presentations. In the case of column generators, a finite Gröbner-Shirshov basis is given if $A$ is finite. From the Composition-Diamond lemma for associative algebras, it follows that the set of Young tableaux is a linear basis of plactic algebra. As the result, it gives a new proof that Young tableaux are normal forms of elements of plactic monoid. This result was proved by D.E. Knuth \cite{Knuth} in 1970, see also Chapter 5 in \cite{M.L}.
Rings and Algebras (math.RA)
New approaches to plactic monoid via Gröbner-Shirshov bases
Qwen/Qwen-72B
1. YES
2. YES