text:
\begin{document}

\title{Gr\"obner-Shirshov basis for the braid semigroup  }

\author[Bokut]{L. A. Bokut$^*$}
\address{Sobolev Institute of Mathematics, Novosibirsk 630090, Russia; =
and
Chang Jung Christian University, Kway Jen, Tainan 711, Taiwan}
\email{bokut@math.nsc.ru}
\thanks{$^*$Supported in part by the Russia's Fund of
    Fundamental Research.}

\author[Fong]{Y. Fong}
\address{Department of Mathematics, National Cheng-Kung University,
Tainan , Taiwan} \email{yfong@mail.ncku.edu.tw}

\author[Ke]{W.-F. Ke}
\address{Department of Mathematics, National Cheng-Kung University,
Tainan , Taiwan} \email{wfke@mail.ncku.edu.tw}

\author[Shiao]{L.-S. Shiao}
\address{Chang Jung Christian University, Kway Jen, Tainan 711,
Taiwan} \email{lsshiao@mail.cju.edu.tw}

 \begin{abstract}
 We found Gr\"obner-Shirshov basis for the braid semigroup $B^+_{n+1}$.
 It gives a new algorithm for the solution of the word problem for the braid
 semigroup and so for the braid group.
  \end{abstract}

\maketitle

\section{Introduction}

In this paper, we are continuing to use a language of the \GS\
bases for some semigroups presented by defining relations (in
papers \cite{BoS01}, \cite{BoSh01} some groups have been treated
as semigroups). Traditionally in this situation, one use some other
languages like  elementary transformations language
(\cite{Ad66},\cite{AD00}), Newman's Diamond lemma language
(\cite{Ne42}), the rewriting systems language (\cite{BoOt93} ), or
some else (\cite{KhS95}). For example, P.M. Cohn used Diamond
lemma for semigroups as early as in 1956 (\cite{Co56a},
\cite{Co56b}). After him first author used the same language to
prove some embedding theorems for semigroups
\cite{Bo63a},\cite{Bo63b}. Also first author used a language of
rewriting systems in order to prove that multiplicative semigroups
of some rings is  embeddable into groups \cite{Bo69a},
\cite{Bo69b} (see also  \cite{Bo80}, \cite{Bo96}).
 But here we formulate our main results in terms of \GS\ bases.

During the last few years the \GS\ bases method has been used to
study some important examples of associative algebras (quantum
enveloping algebras of the type $A_n$, Hecke algebras of type
$A_n$), Lie algebras (simple Lie algebras of the types $A_n, B_n,
C_n, D_n,$ $ G_2, F_4, E_6, E_7, E_8$, Kac-Moody algebras of the
types $A_n^{(1)},B_n^{(1)},C_n^{(1)},D_n^{(1)}$), Lie superalgebras
(simple Lie superalgebras of
the types $A_n, B_n, C_n, D_n$), modules (irreducible modules over
simple Lie algebras of the type $A_n$, Specht modules over Hecke
algebras of the type $A_n$), and groups (\GS\ bases for Coxeter
groups of types $A_n, B_n, D_n$) \cite{BoK96} -- \cite{BoS01},
\cite{KaLe00}--\cite{KangPreprint}, \cite{Po99a} -- \cite{Po99d}. Also this method
was invented for associative conformal algebras \cite{BoFK1},
\cite{BoFK2}.

In recent paper \cite{BoSh01},  two of us  applied the \GS\ bases method
to study some groups by P.S. Novikov \cite{No55} and W.W. Boone
\cite{Boone59} with the algorithmically unsolvable word problem.
They revised some papers \cite{Bo66}, \cite{Bo67a}, \cite{Bo84},
\cite{Bo85} (see also \cite{Bo86}, \cite{BoK94}) that used a
rewriting systems language (between lines  of HNN-extension
theory) using the very language of \GS\ bases. It means that they
eliminated any group theory in proving Novikov's and Boone's
theorems on unsolvability.

Some other activities on \GS\ (non-commutative Gr\"obner,
standard) bases  may be found in papers by T. Mora \cite{Mo94},
V.N. Latyshev \cite{La00}, V. Ufnarovski \cite{Uf98}, A.A.
Mikhalev and A.A. Zolotyh \cite{MiZ98}, A.A. Mikhalev and E.
Vasilieva \cite{MiV00}, V.P. Gerdt and V.V. Kornyak
\cite{GerdtK96}.

A great  interest has been done to the word and conjugacy problems
for  braid groups $B_{n+1}$. Let us mention a pioneering paper by
E. Artin \cite{Ar26}, \cite{Ar47}, papers by A.A. Markov
\cite{Ma45}, A.F. Garside \cite{Ga69}, P. Deligne \cite{Del72}, W. Thurston \cite{Th88},
K. Tatsuoka \cite{Ta93},
E.A. Elrifai and H.R. Morton
\cite{EM94}, P. Dehornoy \cite{De97}, J. Birman, K.H. Ko, and S.J.
Lee \cite{BKL98}. In those papers , a fundamental role of a semigroup of positive words
of $B_{n+1}$ is proved to be crucial. Actually this semigroup
depends of generators of $B_{n+1}$. Let us denote this semigroup
in Artin generators $a_i,1\leq i\leq n$ by $B_{n+1}^+$ and call
the braid semigroup. It has the following
defining relations as a semigroup:
\begin{align*}
&a_{i+1}a_ia_{i+1}=a_ia_{i+1}a_i,\\
&a_ia_j=a_ja_i, i-j\geq 2.
\end{align*}

In this paper, we found \GS\ basis of $B_{n+1}^+$. It gives
a new solution of the word problem for the braid semigroup and as the
result for the braid group. We also
 study a more general concept of braid semigroups. The braid
semigroup $B_{n+1}^+$ is  a braid semigroup of type
$A_n$.
 We formulate a hypothesis on \GS\ bases
of any braid semigroup. It is a modification of a hypothesis on
\GS\ bases of Coxeter groups \cite{BoS01}. The previous example
support our hypothesis.

Let us mentioned that in Birman-Ko-Lee generators $a_{ts}, 1\leq
t<s\leq n+1$ a semigroup of positive braids of $B_{n+1}$
have the following defining relations \cite{BKL98}:
\begin{align*}
&a_{ts}a_{rq}=a_{rq}a_{ts}, (t-r)(t-q)(s-r)(s-q)>0,\\
&a_{ts}a_{sr}=a_{tr}a_{ts}=a_{sr}a_{tr} .
\end{align*}

It would be interesting to fined a \GS\ basis of this semigroup
too. It may have some connections with a new Public-Key
Cryptosystem \cite{Ko00}.

\section{\GS\ bases }

Let $\mathbf{X}$ be a linearly ordered set,  $k$ be a field,
$k\langle \mathbf{X}\rangle$ be the free associative algebra over
$\mathbf{X}$ and $k$. On the set $\mathbf{X}^*$ of words we impose
a monomial well order $>$ (i.e. a well order that  agrees with the
concatenation of words). Any polynomial $f\in k\langle
\mathbf{X}\rangle$ has the leading word $\bar f$. We say that $f$
is monic if $\bar f$ occurs in $f$ with coefficient $1$. By a
composition of intersection $(f,g)_w$ of two monic polynomials
relative to some word $w$, such that $w = \bar fb= a\bar g$,
$\deg( \bar f) + \deg(\bar g) > \deg (w)$, one means the following
polynomial
$$
                            (f,g)_w = fb - ag.
$$
By composition of including $(f,g)_w$  two monic polynomials,
where $w = \bar f = a\bar gb$, one means the following polynomial
$$
                           (f,g)_w = f - agb.
$$
In the last case the transformation
$$
                     f\mapsto (f,g)_w = f -agb
$$
is called the elimination of the leading word (ELW) of g in f.

In both cases the word $w$ is called an $ambiguity$ of polynomials
(relations) $f,g.$

A composition $(f,g)_w$ is called trivial relative to some
$\mathbf{S} \subset k\langle \mathbf{X}\rangle$ ($(f, g)_w\equiv
0 $ $ mod (\mathbf{S}, w))$, if
$$
            (f,g)_w = \sum \alpha_i a_it_i b_i,
$$
where   $t_i \in \mathbf{S}$, $a_i, b_i \in  \mathbf{X}  ^*$, and
$\bar {a_it_ib_i} < w$. In particular, if $(f,g)_w$ goes to zero
by the ELW's of $\mathbf{S}$ then $(f,g)_w$ is trivial relative to
$\mathbf{S}$.

We assume for some polynomials $f_1$ and $f_2$ that
$$
               f_1 \equiv f_2 mod (\mathbf{S}, w),
$$
if
$$
f_1-f_2 \equiv 0 mod (\mathbf{S},w).
$$

A subset $\mathbf{S}$ of $k\langle \mathbf{X}\rangle$ is called a
\GS\ basis if any composition of polynomials from $\mathbf{S}$ is
trivial relative to $\mathbf{S}$.

By $\langle \mathbf{X}\vb \mathbf{S}\rangle$, the algebra with
generators $\mathbf{X}$ and defining relations $\mathbf{S}$, we
will mean the factor-algebra of $k\langle \mathbf{X}\rangle$ by
the ideal generated by $\mathbf{S}$.

The following lemma goes back to the Poincare - Birkhoff-Witt
(PBW) theorem, the Diamond Lemma of M.H.A. Newman \cite{Ne42}, the
Composition Lemma of A.I. Shirshov (\cite{Sh62}) (see also
\cite{Bo72}, \cite{Bo76}, where this Composition Lemma was
formulated explicitly and in a current form for Lie algebras and
associative algebras respectively), the Buchberger's Theorem
(\cite{Bu65}) (published in \cite{Bu70}), the Diamond Lemma of G.
Bergman \cite{Be78} (this lemma was also known to P.M. Cohn, see,
for example, \cite{Co66}, \cite{Co81} and some historical comments
to Chapter ``Gr\"obner bases" in \cite{Ei95}):

\begin{lemma}(Composition-Diamond Lemma)

   $\mathbf{S}$ is a \GS\ basis if and
only if the set
$$
       \{u \in \mathbf{X}^* \mid u \neq a\bar fb, \mbox{ for any }f\in
\mathbf{S}\}
$$
of $\mathbf{S}$-reduced words consists of  a linear basis of the
algebra $\langle \mathbf{X}\vb \mathbf{S}\rangle$.
\end{lemma}

While $\mathbf{S}$ is fixed, we will call $\mathbf{S}$-reduced
words just reduced words. Actually we would like to introduce a
new term for this basis - the $ PBW-basis$ for the algebra relative
to the \GS\ basis of relations of this algebra. It would reflect to
the fact that as we have mentioned the Composition-Diamond lemma
goes back to the Poincare-Birkhoff-Witt (PBW) theorem as well.
In fact the PBW theorem is a particular and the most important up
to now case of \CD\ lemma when $\mathbf{S}= \{x_ix_j-x_jx_i-\sum
x_{ij}^k, i>j\}$ and $[x_ix_j]=\sum x_{ij}^k, i>j$ is the
multiplicative table of some Lie algebra. In this case
$PBW(\mathbf{S})=\{x_{i_1}x_{i_2}\dots x_{i_k}, i_1\leq i_2\dots
\leq i_k \}.$

If a subset $\mathbf{S}$ of $k\langle \mathbf{X}\rangle$ is not a
\GS\ basis then one can add to $\mathbf{S}$ all nontrivial
compositions of polynomials of
 $\mathbf{S}$, and continue this process (infinitely) many times  in
order to have a
\GS\  basis $\mathbf{S}^{\rm comp}$ that contains $S$. This
procedure is called the Buchberger - Shirshov algorithm
\cite{Sh62}, \cite{Bu65}, \cite{Bu70}.

A \GS\ basis $\mathbf{S}$ is called $minimal$  if any
$s\in \mathbf{S}$ is a linear combination of
$\mathbf{S}\setminus\{s\}$ - reduced words. Any ideal of $k\langle
\mathbf{X} \rangle$ with a fix monomial order has the unique minimal \GS\ basis.

If $\mathbf{S}$ is a set of ``semigroup relations" (that is,
polynomials of the form $u - v$, where $u,v \in \mathbf{X}^*$),
then any nontrivial composition will have the same form. As a
result the set $\mathbf{S}^{\rm comp}$ also consists of semigroup
relations.

Let $A = smg\langle \mathbf{X}\vb \mathbf{S}\rangle$  be a
semigroup presentation. Then $\mathbf{S}$ is a subset of $k\langle
\mathbf{S}\rangle$ and one can find a \GS\ basis $ \mathbf{S}^{\rm
comp}$. The last set does not depend on $k$, and consists of
semigroup relations. We will call $\mathbf{S}^{\rm comp}$ a \GS\
basis of $A$. It is the same as a \GS\ basis of the semigroup
algebra $kA = \langle \mathbf{X}\vb\mathbf{S}\rangle$.

 Let $\{u_i\}$ be a set of words in an alphabet. By $V(u_i)$ we
understand any
word in $\{u_i\}$. Let $\{w_i\}$ be some other set of words with a
surjection $u_i \mapsto w_i$. Then by $V(w_i)$ we understand the
same word  $V$, but in the set $\{w_i\}$.

\section{A hypothesis}

Here we will formulate a general hypothesis  on \GS\ bases for any
braid semigroup.

We will present Coxeter group $W$  relative to Coxeter matrix $M$
in the following way. Let $S$ be a linear ordered $l$-elements
set, $M = (m_{ss'})$  be $l \times l$ Coxeter matrix. Then
$$
   W = smg\langle S \mid s^2 = 1, (ss' )^{m_{ss'}} = 1, s \neq s',
\forall s, s' \in S \mbox{ and finite }m_{ss'}\rangle.
$$
Let us define  for finite $m_{ss'}$,
\begin{align*}
m(s, s')  &= ss' \dots &&\mbox{(there are $m_{ss'}$ alternative
    letters $s$, $s'$)},\\
(m-1) (s, s') &= ss' \dots &&\mbox{(there are $m_{ss'}-1$
    alternative letters $s$, $s'$)},
\end{align*}
and so on.  For example, if $m_{ss'} = 2$, then $m(s, s') = ss'$,
$(m-1)(s, s') = s$. If $m_{ss'} = 3$, then $m(s, s') = ss's$,
$(m-1)(s, s') = ss'$.

In this notations defining relations of W can be presented in the
form
\begin{equation}\label{E1}
                 s^2 = 1,\,  m(s, s') = m(s', s),\,  s > s',
\end{equation}
for all $s, s' \in S$ and finite $m_{ss'}$.

\begin{defn}
The following semigroup will be called the braid semigroup $W^+$
relative to the Coxeter matrix $M$:
\begin{equation}\label{E2}
W^+= smg\langle s_1, \dots, s_l\vb  m(s, s') = m(s', s),\,  s >
s', s,s'\in S, m_{ss'}<\infty \rangle.
\end{equation}

\end{defn}

Also we will use the following notation:
$$
(m,i)(s,s')
$$
is a result of removing first $i$ letters in $m(s,s')$, where
$1\leq i\leq m.$

Let us call two words in $S$ equivalent if they are equal module
commutativity relations from (\ref{E1}).  To be more prices, it
means that they are equal in the so called free partially
commutative semigroup (algebra) generated by $S$ and with
commutativity relations from (\ref{E1}) \cite{BoS01}.  Two
relations $a = b$ and $c = d$ of $W$ are called equivalent if $a$,
$b$ are equivalent to $c$, $d$ respectively.

\begin{hyp}
 A \GS\ basis $\mathbf{T}$ of $W^+$ include of initial relations
(\ref{E2}) and relations that are equivalent to  the following
ones:
\begin{equation}\label{E3}
\begin{split}
 &(m-i_0)(s, s')(m-i_1)(s_1, s_2) \dots (m-i_k)(s_{2k-1},
s_{2k})m(s_{2k+1},
  s_{2k+2})\\
 &\quad = m(s', s)(m,i_0)(s_2, s_1) \dots (m,i_{k-1})(s_{2k},
s_{2k-1})(m,i_k)
(s_{2k+2}, s_{2k+1}),
\end{split}
\end{equation}
where $s > s'$, $s_1 < s_2$, \dots, $s_{2k-1} <  s_{2k}$,
$s_{2k+1} < s_{2k+2}$,  and
\begin{align*}
&(m-i_k)(s_{2k-1}, s_{2k})m(s_{2k+2},s_{2k+1})\doteq
m(s_{2k-1}, s_{2k})(m,i_k)(s_{2k+2},s_{2k+1}),\\
 &(m-i_{k-1})(s_{2k-3},
s_{2k-2})m(s_{2k},s_{2k-1})\doteq m(s_{2k-3},
s_{2k-2})(m,i_{k-1})(s_{2k},s_{2k-1}),\\
 &.\\
 &. \\
 &. \\
&(m-i_1)(s_1, s_2)m(s_4,s_3)\doteq
m(s_1, s_2)(m,i_1)(s_4,s_3),\\
 &(m-i_0)(s,
s')m(s_2,s_1)\doteq m(s, s')(m,i_0)(s_2,s_1).
\end{align*}

Above $\doteq$ means the equality in the free semigroup.

Let us fix left hand and rite hand sides of (\ref{E3}). If $A=B$
has a form (\ref{E3}) then a transformation
$$
A\rightarrow B
$$
will be  called a positive chain, while $B\rightarrow A$ will be
called negative.

Any other relation of $\mathbf{T}$ is equivalent to the following
one:
\begin{equation}\label{E4}
X=Y,
\end{equation}
where $X$ goes to some $X'$ by a series of negative chains,
$$
X\rightarrow X_1\rightarrow \dots \rightarrow X_k=X',
$$
(in the free  partially commutative semigroup), $X'=AY_1$, and
$Y=BY_1$, where $A\rightarrow B$ is a positive chain.
\end{hyp}

\begin{rem}
Let us compere this hypothesis with our hypothesis on \GS\ bases
of Coxeter groups \cite{BoS01}. Relations (6.2) in \cite{BoS01} is
just relations (\ref{E3}) with $i_0=i_1= \dots =i_k=1$ and with an
extra condition that all neighbor pairs $(s,s'), (s_1,s_2), \dots
,(s_{2k+1},s_{2k+2})$ are different. In particular we don't expect
negative chains for Coxeter groups at all.
\end{rem}

\section{Braid semigroup of the type $A_n$}

Let $B_3^+$ is the braid semigroup with 2 generators
$a_1,a_2, a_2a_1a_2=a_1a_2a_1.$ We will assume that $a_1<a_2$, and
$u<v$ for words $u,v$ will mean the $deg-lex$ order (first we
compere words by the degree (length) and then lexicographically).

\begin{lemma}\label{L1}
The minimal \GS\ basis of $B_3^+$ consists of the initial
relation and relations
\begin{equation}\label{E5}
a_2a_1^la_2a_1=a_1a_2a_1^2a_2^{l-1}, l\geq 2
\end{equation}
of a form (\ref{E3}).
\end{lemma}

\begin{proof}
First of all (\ref{E5}) is follows from Garside's formulas
\cite{Ga69}, Lemma 2:
$$
a_1\Delta_2=\Delta_2a_2, a_2\Delta_2=\Delta_2a_1,
$$
where $\Delta_2=a_1a_2a_1.$

Secondly (\ref{E5}) has a form (\ref{E3}):
$$
(m-1)(a_2,a_1)(m-2)(a_1,a_2)(m-2)(a_1,a_2) \dots
(m-2)(a_1,a_2)m(a_1,a_2)=
$$
$$
m(a_1,a_2)(m,1)(a_2,a_1)(m,2)(a_2,a_1)\dots
(m,2)(a_2,a_1)(m,2)(a_2,a_1).
$$

Now we need to proof that any composition of relations from the
lemma is trivial. There are some compositions of intersections
relative to the following   ambiguities $w$:
\begin{align*}
&a_2a_1a_2a_1a_2, a_2a_1^la_2a_1a_2, l\geq
2, a_2a_1a_2a_1^la_2a_1, l\geq 2,\\
&a_2a_1^la_2a_1^ka_2a_1, l,k\geq 2.
\end{align*}

Let us check the last composition for an example:
\begin{align*}
&(f,g)_w=(a_2a_1^la_2a_1-a_1a_2a_1^2a_2^{l-1})a_1^{k-1}a_2a_1-\\
&a_2a_1^l(a_2a_1^ka_2a_1-a_1a_2a_1^2a_2^{k-1})=\\
&a_2a_1^{l+1}a_2a_1^2a_2^{k-1}-a_1a_2a_1^2a_2^{l-1}a_1^{k-1}a_2a_1\equiv\\
&a_1a_2a_1^2a_2^la_1a_2^{k-1}-a_1a_2a_1^2a_2^{l-1}a_1^{k-1}a_2a_1\equiv
0.
\end{align*}

All other compositions can be figure out in the same way.

\end{proof}

Let us introduce the following notations that are  analogous to
that of \cite{BoS01}:
\begin{align*}
&a_{ij}=a_ia_{i-1} \dots a_j,i\geq j, a_{ii}=a_i,a_{ii+1}=1,\\
& a_{ij}(\mathbf{p})=a_i^{p_0}a_{i-1}^{p_1} \dots
a_j^{p_{i-j}},i\geq j,a_{ii}( \mathbf{p})=a_i^{p_0},a_{ii+1}(
\mathbf{p})=1.
\end{align*}
 where
$\mathbf{p}=(p_0,\dots, p_{i-j})$, all $p'$s are $\geq 1$. We will
write $\mathbf{p}> \mathbf{1}$, if at least one of $p$'s is
greater that 1. Otherwise we will write $\mathbf{p}= \mathbf{1}.$

 It is easy to see the
following equality in $B_n^+$:
\begin{equation}\label{E6}
\begin{split}
&a_{ij-1}a_{i+1j-1}=a_{i+1j-1}a_{i+1j},j\leq i+1.\\
&a_{ij-1}( \mathbf{p})a_{i+1j-1}=a_{i+1j-1}a_{i+1j}( \mathbf{p}),
j\leq i+1.
\end{split}
\end{equation}
In fact the first of this equalities has a form:
\begin{equation}\label{E7}
\begin{split}
&(m-1)(a_i,a_{i+1})(m-1)(a_{i-1},a_i) \dots
(m-1)(a_j,a_{j+1})m(a_{j-1},a_j)=\\
&m(a_{i+1},a_i)(m,1)(a_{i-1},a_i)\dots
(m,1)(a_{j+1},a_j)(m,1)(a_j,a_{j-1}).
\end{split}
\end{equation}

The second of equalities (\ref{E6}) has an analogous  form:
\begin{equation}\label{E8}
\begin{split}
&(m-2)(a_i,a_{i+1})^{p_0-1}(m-1)(a_i,a_{i+1})\dots
(m-2)(a_{j-1},a_j)^{p_{i-j+1}-1}\cdot \\
&m(a_{j-1},a_j)= m(a_{i+1},a_i)(m,2)(a_{i+1},a_i)^{p_0-1}\dots
(m,1)(a_j,a_{j-1})\cdot \\
&(m,2)(a_j,a_{j-1})^{p_{i-j+1}-1}.
\end{split}
\end{equation}

Also we will use the following Garside's formula:
\begin{equation}\label{E9}
a_sa_{i+1j}=a_{i+1j}a_{s+1}, j\leq i,j\leq s\leq i.
\end{equation}
This formula looks like
\begin{align*}
&m(a_s,a_{i+1})\dots(m-1)(a_s,a_{s+1})\dots(m-1)(a_{s+1},a_j)=\\
&(m,1)(a_{i+1},a_s)\dots(m,1)(a_{s+1},a_s)\dots m(a_j,a_{s+1}).
\end{align*}

By $W(a_j,\dots,a_i)=W(j,i)$ we will mean any word in alphabet
${a_j,a_{j+1},\dots,a_i}$ if $j\leq i$, and empty word if $j>i$.

\begin{thm}\label{T1}
A \GS\ bases of $B_{n+1}^+$ consists of the following
relations :
\begin{align}
&a_{i+1}a_iV(1,i-1)W(j,i)a_{i+1j}=a_ia_{i+1}a_iV(1,i-1)a_{ij}W'(j+1,i+1),\label{E10}\\
 &a_sa_k=a_ka_s, s-k\geq 2,\label{E11}
\end{align}
where $1\leq i\leq n-1,$ $1\leq j\leq i+1, ,$ $
W'=W(a_{j+1},\dots, a_{i+1})$, and $W$ begins with $a_i$ if it is
not empty.
\end{thm}

\begin{rem}
In    particular the following relations are in the previous list:
\begin{align*}
&a_{i+1}a_ia_{i+1}=a_ia_{i+1}a_i\mbox{  } (V=1,j=i+1),\\
 &a_{i+1}a_i^la_{i+1}a_i=a_ia_{i+1}a_i^2a_{i+1}^{l-1},l\geq 2\mbox{   }
(V=1,W=a_i^{l-1},j=i),\\
&a_{i+1}a_i^la_{i-1j}(\mathbf{p})a_{i+1j}=a_ia_{i+1}a_i^2a_{i-1j}a_{i+1}^{l-1}a_{ij+1}(
\mathbf{p}),l\geq 2,i-1\geq j \\
&(V=1,W=a_i^{l-1}a_{i-1j}(\mathbf{p})).\\
\end{align*}

This relations have a form (\ref{E3}) because of Lemma \ref{L1}
and (\ref{E8}). In general (if $W$ is not empty) relation
(\ref{E10}) has a form (\ref{E4}). It follows from above and
(\ref{E9}).

Also the rite hand sides of (\ref{E6}) go to the left hand sides
using the eliminations of leading words of relations (\ref{E10}).
\end{rem}
\begin{proof}

Let $\mathbf{S}$ is the set of relations (polynomials) from the
theorem. We need to proof that any composition of polynomials from
$\mathbf{S}$ is trivial $mod \mathbf{S}.$

First of all let us deal with compositions of including. It is
easy to see that any composition of including of (\ref{E11}) in
(\ref{E10}) is trivial for the only possible composition of
this including should correspond of some including of
$a_sa_k,s-k\geq 2$ in $VW$, or else of $a_ia_k,i-k\geq 2$ in
$a_iV$. So we need to figure out any composition of including
relations of the type (\ref{E10}). Let $f$ be a relation
(polynomial) (\ref{E10}) and $g$ be the following relation:
$$
a_{i_1+1}a_{i_1}V_1(1,i_1-1)W_1(j_1.i_1)a_{i_1+1j_1}=
a_{i_1}a_{i_1+1}a_{i_1}V_1(1,i_1-1)a_{i_1j_1}W_1'(j_1+1.i_1+1),
$$
where $j_1\leq i_1+1$ and $W_1$ begins with $a_{i_1}$ if not
empty. Let $u,u_1$ be the leading monomials of $f,g$ respectively.
Suppose that $u_1$ is a subword of $u$. Following possibilities
may occur:

1)$i=i_1$. Then $V=V_1,W=W_1$, $j_1\geq j.$

Then
\begin{align*}
&(f,g)_u=a_ia_{i+1}a_iVa_{ij_1}W'a_{j_1-1j}-a_ia_{i+1}a_iVa_{ij}W'\equiv0,\\
\end{align*}
for $W'=W_1'=W(a_{j_1+1},\dots,a_{i+1})$, hence
$W'a_{j_1-1j}\equiv a_{j_1-1j}W'$.

2)$i=i_1+1.$ Then
$$
u_1=a_ia_{i-1}V_1(1,i-2)W_1(j_1,i-1)a_{ij_1}.
$$
It means that
$$
V(1,i-1)=a_{i-1}V_1(1,i-2)W_1(j_1,i-1),W(j,i)=a_{ij_1}W_2(j,i).
$$
We have
\begin{align*}
&(f,g)_u=a_{i+1}a_{i-1}a_ia_{i-1}V_1(1,i-2)a_{i-1j_1}W_1'(j_1+1,i)W_2(j,i)a_{i+1j}-\\
&a_ia_{i+1}[a_ia_{i-1}V_1(1,i-2)W_1(j_1,i-1)a_{ij_1}]a_{j_1-1j}a_{i+1j_1+1}
W_2'(j+1,i+1)\equiv\\
&a_{i-1}[a_{i+1}a_ia_{i-1}V_1(1,i-2)a_{i-1j_1}W_1'(j_1+1,i)W_2(j,i)a_{i+1
j}]-\\
&a_ia_{i+1}a_{i-1}a_ia_{i-1}V_1(1,i-2)a_{i-1j_1}W_1'(j_1+1,i)a_{j_1-1j}a_
{i+1j_1+1}
W_2'(j+1,i+1)\equiv\\
&a_{i-1}a_ia_{i+1}[a_ia_{i-1}V_1(1,i-2)a_{i-1j_1}a_{ij_1}]a_{j_1-1j}W_1''
(j_1+2,i+1)
W_2'(j+1,i+1)-\\
&a_ia_{i-1}[a_{i+1}a_ia_{i-1}V_1(1,i-2)a_{i-1j_1}a_{j_1-1j}W_1'(j_1+1,i)a
_{i+1j_1+1}]
W_2'(j+1,i+1)\equiv\\
&a_{i-1}a_ia_{i+1}a_{i-1}a_ia_{i-1}V_1(1,i-2)a_{i-1j_1}a_{ij_1+1}a_{j_1-1
j}W_1''(j_1+2,i+1)
W_2'(j+1,i+1)-\\
&a_ia_{i-1}a_ia_{i+1}a_ia_{i-1}V_1(1,i-2)a_{i-1j}a_{ij_1+1}W_1''(j_1+2,i+
1)
W_2'(j+1,i+1)\equiv 0,
\end{align*}
for $a_{ij_1+1}a_{j_1-1j}\equiv a_{j_1-1j}a_{j_1-1j}$.

3) $i-i_1\geq 2.$ The $u_1$ is a subword of
$V(1,i-1)W(j,i)a_{i+1j}$. Than it should be a subword either $V$
or $W$. First case is clear. Let us figure out second case:
\begin{align*}
&W=W_2(j,i)a_{i_1+1}a_{i_1}V_1(1,i_1-1)W_1(j_1,i_1)a_{i_1+1j_1}W_3(j,i)
,\\
&w=a_{i+1}a_iV(1,i-1)W_2(j,i)a_{i_1+1}a_{i_1}V_1(1,i_1-1)W_1(j_1,i_1)
a_{i_1+1j_1}W_3(j,i)a_{i+1j},\\
&(f,g)_w=a_ia_{i+1}a_iV(1,i-1)a_{ij}W_2'(j+1,i+1)a_{i_1+2}a_{i_1+1}V_1'
(2,i_1)
W_1'(j_1+1,i_1+1)\cdot\\
&a_{i_1+2j_1+1}W_3'(j+1,i+1)-[a_{i+1}a_iV(1,i-1)W_2(j,i)a_{i_1}a_{i_1+1}a
_{i_1}
V_1(1,i_1-1)a_{i_1+1j_1}\cdot\\
&W_1'(j_1+1,i_1+1)W_3(j,i)a_{i+1j}]\equiv
a_ia_{i+1}a_iV(1,i-1)a_{ij}W_2'(j+1,i+1)[a_{i_1+2}a_{i_1+1}\cdot\\
&V_1'(2,i_1)W_1'(j_1+1,i_1+1)a_{i_1+2j_1+1}]W_3'(j+1,i+1)-a_ia_{i+1}a_iV(
1,i-1)
a_{ij}\cdot\\
&W_2'(j+1,i+1)a_{i_1+1}a_{i_1+2}a_{i_1+1}V_1'(2,i_1)a_{i_1+1j_1+1}
W_1''(j_1+2,i_1+2)W_3'(j+1,i+1) \\
&\equiv0.
\end{align*}

Now we need to check compositions of intersection.

 It is easy to see that all compositions of
intersection with (\ref{E11}) are trivial. Therefore we only need
to consider compositions of intersection of (\ref{E10}) relative
to the following ambiguities $w$:

1)It is a case of one letter intersection,
\begin{align*}
&
w=a_{i+1}a_iV(1,i-1)W(j,i)a_{i+1j}a_{j-1}V_1(1,j-2)W_1(j_1,j-1)a_{jj_1}
,\\
&(f,g)_w=a_ia_{i+1}a_iV(1,i-1)a_{ij}W'(j+1,i+1)a_{j-1}V_1(1,j-2)
W_1(j_1,j-1)a_{jj_1}-\\
&a_{i+1}a_iV(1,i-1)W(j,i)a_{i+1j+1}a_{j-1}a_ja_{j-1}V_1(1,j-2)a_{j-1j_1}
W_1'(j_1+1,j)\equiv \\
&a_ia_{i+1}a_iV(1,i-1)a_{ij-1}W'(j+1,i+1)V_1(1,j-2)
W_1(j_1,j-1)a_{jj_1}-\\
&[a_{i+1}a_iV(1,i-1)(W(j,i)a_{j-1})a_{i+1j-1}]V_1(1,j-2)a_{j-1j_1}
W_1'(j_1+1,j)\equiv \\
&a_ia_{i+1}a_iV(1,i-1)a_{ij-1}W'(j+1,i+1)V_1(1,j-2)
W_1(j_1,j-1)a_{jj_1}-\\
&a_ia_{i+1}a_iV(1,i-1)a_{ij-1}(W'(j+1,i+1)a_j)V_1(1,j-2)a_{j-1j_1}
W_1'(j_1+1,j)\equiv0,
\end{align*}
for $a_jV_1(1,j-2)\equiv a_jV_1(1,j-2)$ and
$W_1(j_1,j-1)a_{jj_1}\equiv a_{jj_1}W_1'(j_1+1,j)$;

 2) It is a case of two letters intersection,
\begin{align*}
&
w=a_{i+1}a_iV(1,i-1)W(j,i)a_{i+1j+2}a_{j+1}a_jV_1(1,j-1)W_1(j_1,j)a_{j+
1j_1},\\
&(f,g)_w=a_ia_{i+1}a_iV(1,i-1)a_{ij}W'(j+1,i+1)V_1(1,j-1)
W_1(j_1,j)a_{j+1j_1}-\\
&a_{i+1}a_iV(1,i-1)W(j,i)a_{i+1j+2}a_ja_{j+1}a_jV_1(1,j-2)a_{jj_1}
W_1'(j_1+1,j+1)\equiv \\
&a_ia_{i+1}a_iV(1,i-1)a_{ij}W'(j+1,i+1)V_1(1,j-1)
W_1(j_1,j)a_{j+1j_1}-\\
&[a_{i+1}a_iV(1,i-1)(W(j,i)a_j)a_{i+1j}]V_1(1,j-2)a_{jj_1}
W_1'(j_1+1,j+1)\equiv \\
&a_ia_{i+1}a_iV(1,i-1)a_{ij}W'(j+1,i+1)V_1(1,j-1)
W_1(j_1,j)a_{j+1j_1}-\\
&a_ia_{i+1}a_iV(1,i-1)a_{ij}(W'(j+1,i+1)a_{j+1})V_1(1,j-2)a_{jj_1}
W_1'(j_1+1,j+1)\equiv 0,\\
\end{align*}
for $a_{j+1}V_1(1,j-2)\equiv V_1(1,j-2)a_{j+1}$ and
$W_1(j_1,j)a_{j+1j_1}\equiv a_{j+1j_1}W_1'(j_1+1,j+1).$

3) It is a case of more than two letters intersection:

\begin{align*}
& w=a_{i+1}a_iV(1,i-1)W(j,i)a_{i+1}a_i\dots a_{i_1+1}a_{i_1}\dots
a_jV_2(1,i_1-1)W_1(j_1,i_1)a_{i_1+1j_1},\\
&(f,g)_w=a_ia_{i+1}a_iV(1,i-1)a_{ij}W'(j+1,i+1)V_2(1,i_1-1)W_1(j_1,i_1)=
a_{i_1+1j_1}-\\
&a_{i+1}a_iV(1,i-1)W(j,i)a_{i+1i_1+2}a_{i_1}a_{i_1+1}a_{i_1}a_{i_1-1j}
V_2(1,i_1-1)a_{i_1j_1}
W_1'(j_1+1,i_1+1)\equiv \\
&a_ia_{i+1}a_iV(1,i-1)a_{ij}W'(j+1,i+1)V_2(1,i_1-1)W_1(j_1,i_1)a_{i_1+1j_=
1}-\\
&[a_{i+1}a_iV(1,i-1)(W(j,i)a_{i_1})a_{i+1j}]V_2(1,i_1-1)a_{i_1j_1}
W_1'(j_1+1,i_1+1)\equiv \\
&a_ia_{i+1}a_iV(1,i-1)a_{ij}W'(j+1,i+1)V_2(1,i_1-1)W_1(j_1,i_1)a_{i_1+1j_=
1}-\\
&a_ia_{i+1}a_iV(1,i-1)a_{ij}(W'(j+1,i+1)a_{i_1+1})V_2(1,i_1-1)a_{i_1j_1}
W_1'(j_1+1,i_1+1)\equiv 0,
\end{align*}
for $a_{i_1+1}V_2(1,i_1-1)\equiv V_2(1,i_1-1)a_{i_1+1}$ and
$W_1(j_1,i_1)a_{i_1+1j_1}\equiv a_{i_1+1j_1}W_1'(j_1+1,i_1+1).$

We have checked all compositions and the theorem is proved.

\end{proof}

\begin{rem}
In  view of \cite{Ga69}, it is important to have an efficient
algorithm to know whether a word $v$ of $B_{n+1}$ begin with the
fundamental word $ \Delta$ in some presentation, where
$$
\Delta = \Lambda_1 \Lambda_2 \dots \Lambda_n, \Lambda_i=a_i\dots
a_1, i\geq 1.
$$

Let us formulate the following statement that easily follows from
the previous theorem.

\begin{prop}\label{T2}
Let $v\in PBW(B_{n+1}^+)$. Then $v$ begins with $\Delta$ in
some presentation if and only if
$$
v\doteq \Lambda_1 V_1(1) \Lambda_2 V_2(1,2)\dots
\Lambda_{n-1}V_{n-1}(1,n-1)\Lambda_nu,
$$
where $V_i(1,i)$ begins with $a_1 $ or empty. In this case we have
$$
v=\Delta V_1^{(n-1)}(n)V_2^{(n-2)}(n-1,n)\dots V_{n-1}'(2,n).
$$
\end{prop}
\begin{proof}The result follows imediatly from the following formula:
$$
PBW(a_{i+1}a_i\dots a_1w)\doteq V(1,i)a_{i+1}a_i\dots a_1w', w,w'\in B_{n+1}^+.
$$
\end{proof}
\end{rem}
\begin{rem}
In  view of \cite{Ga69}, Theorem \ref{T1} gives rise to a new algorithm of the solution
of the word problem for the braid group $B_{n+1}$. Indeed, any group word $w\in B_{n+1} $
can be presented in a form $ \Delta ^kv  $, where $k\in \mathbb{Z}$,  $ v\in  B_{n+1}^+$.
Using Proposition
\ref{T2}, we may present $v$ in a form
$$
v=\Delta^su,
$$
where $s\in \mathbb{N} $, $u$ does not begin with $\Delta$ in any presentation
(it means that $u\neq \Delta u_1$ in the braid semigroup). Also we may assume
that $u$ is a reduced word, $u\in PBW(  B_{n+1}^+)$.
Now $u$ is nothing else as $ \overline{v} $ in the sense
of \cite{Ga69}, Theorem 5. As a result, the presentation
$$
w=\Delta^{k+s}u
$$
is unique due to the same Theorem 5 \cite{Ga69}. Let us call the last
presentation the Garsaid normal form of an element of the braid group.
Garside normal form is effective due to Theorem \ref{T1}. Now the new
algorithm for the solution of the word problem for the braid group
can be written down using the ELW's of the \GS\ basis of this group.
\end{rem}


TITLE: When is $2^{2n+2}+2^{m+2}+1$ a perfect square?
QUESTION [5 upvotes]: Let $m,n$ be natural numbers satisfying $m\leq 2n$. Is it true that $$2^{2n+2}+2^{m+2}+1$$ is a perfect square if and only if $m=n$?
What I have tried: Under the assumption $m<n$, I've tried to 'squeeze' the above number between two consecutive squares, implying it cannot be a perfect square. This works fine because (writing $P(m,n)=2^{2n+2}+2^{m+2}+1$), we have $(2\cdot2^n)^2<P(m,n)<(2\cdot2^n+1)^2$. But this method doesn't work when $\frac{m}{2}\leq n<m$, and I wonder if there is any pair $(m,n)$ with $m\ne n$ making $P(m,n)$ a perfect square.
Any advice is welcome.

REPLY [3 votes]: Let $$2^{2n+2}+2^{m+2}+1=(2k+1)^2\text{where}\; k\ge 2\\
\implies 2^{2n}+2^m=k^2+k$$
For $m=2n$,  $2^{m+1}=k(k+1)$. All factors of $2^{m+1}$ are even but one of $k$ and $k+1$ is odd.  Hence $m\neq 2n$
For $m\lt 2n$, $2^m(2^{2n-m}+1)=k(k+1)$ The factors on both sides are co-prime.  So $k=2^m$ and $k+1=2^{2n-m}+1\implies m=n$
Or $k=2^{2n-m}+1$ and $k+1=2^m$ which means $k$ is one more and one less than powers of $2$ which is only possible if $k=3\implies n=\frac32$ which is impossible.
Hence, $2^{2n+2}+2^{m+2}+1$ is perfect square if and only if $m=n$


TITLE: What is the convergence order of a series
QUESTION [0 upvotes]: What is the convergence order of the following iterative series:
$x_{n+1}=e^{x_n*x_{n-1}}-1 $ when we're given that it converges to c=0.
With the definition of $\epsilon_n=x_n-c$, it was a little complicated ..

REPLY [1 votes]: When the sequence converges, it converges to a fixed point of $g(x)= e^{x^2}-1$, so it will either diverge, converge to $z_1=0$ or converge to $z_2\approx 0.746882$. The second fixed point is unstable and only by shear luck (for instance starting right on the fixed point) will you obtain convergence. So, in your case you should just use $c=0$ in the definition of $e_n$, as it is proposed.


TITLE: Reflexivity of the relation between strings over language $L$ defined by $xc \equiv L$ and $yc \equiv L $
QUESTION [0 upvotes]: Given any two strings, call them $x$ and $y$, over any language $L$ and given property such that  if $xc \equiv L$ and  $yc \equiv L $ (where $c$ is some string), then $x \equiv y$.

I would like to prove that $\equiv$ is reflexive. I tried $x \equiv x \rightarrow x-x \equiv0$ and $y(0) \rightarrow x(0)\equiv0$ Therefore, $\equiv$ is reflexive.
But somehow I don't feel this is right.  Can someone point out what I am doing wrong here?

REPLY [2 votes]: The relation $\equiv_L$ is defined by: $x\equiv_L y$ iff $xz\in L\iff yz\in L$ for all strings $z$.
Clearly, $x\equiv_L x$ since $xz\in L\iff xz\in L$ for all strings $z$.


TITLE: Explicit formula for recurrence relation by generating function
QUESTION [1 upvotes]: My question concerns the following recurrence relation:
$u_n= \frac{u_{n-1}}{2}+\frac{1}{u_{n-1}} $
and how to find an explicit formula for this expression using generating functions (GF). I so far have only had experience with linear recurrence relations and GFs and can't see how to start on this problem. Any help would be appreciated!

REPLY [0 votes]: I write as an answer as my comment was too long:
Well you can do the same trick with an arbitrary number $a$ and write $\frac{u_n-a}{u_{n}+a}$ and you will find that to complete the squares $a$ must be $\sqrt{2}$. On the other hand, the stationary solution of the recurrence can be found by considering the fixed points of the system
$$u_n=\frac{u_n}{2}+\frac{1}{u_n}$$ and solve for $u_n$, finding $u_n=\pm\sqrt{2}$. In general, for nonlinear recurrence relations the explicit closed form solution is very difficult to find, often impossible. In this case you expose, for example, changing the $+$ sign to $-$ gives chaotic solutions with no explicit closed form formula. As far as I know you have to do the trick with a clever transformation to turn the equation in a simplified form.


TITLE: Prove or disprove uniform convergence
QUESTION [2 upvotes]: $g_n(y)=\sum_{k=1}^{n} \frac{\sin ky}{k},x \in [0,\pi]$. So i try to find the pointwise limit function first, following this approach in this post Proving that the sequence $F_{n}(x)=\sum\limits_{k=1}^{n} \frac{\sin{kx}}{k}$ is boundedly convergent on $\mathbb{R}$. I find it to be $\lim\limits_{n\to\infty}\ \sum\limits_{k=1}^{n}\frac{\sin kx}{k}=\frac{\pi-x}{2}=g(x) ,\, x\in(0,2\pi).$
I tried to prove it by Dirichlet test:
take $h_n(x)=\frac{1}{n}\quad \text{and} \quad u_n(x)=\sin(nx) ,
\text{then}  |\sum_{k=1}^n\sin(kx)| \leq \frac{1}{\sin(\frac{x}{2})} \leq \frac{1}{\sin(\frac{\delta}{2})}$.
I want to prove or disprove that $(g_n)$ converge uniformly on $[0,\pi]$.

REPLY [1 votes]: You have shown correctly with the Dirichlet test that $(g_n)$ converges uniformly on the interval $[\delta, \pi]$ for any $\delta > 0$.  This relies on the fact that $\left|\sum_{k=1}^n \sin kx \right| \leqslant 1 / \sin (\delta/2)$ is   uniformly bounded for all $n \in \mathbb{N}$ and $x \in [\delta,\pi]$.
However, if $\delta = 0$ the partial sums are not bounded and the Dirichlet test is not applicable. This is a clue that convergence is not uniform on $[0,\pi]$.
If the convergence were uniform, then by the Cauchy criterion for any $\epsilon > 0$ there exists $N \in \mathbb{N}$ such that for all $m > n \geqslant N$ and all $x \in [0,\pi]$ we would have
$$\tag{1}\left|\sum_{k=n+1}^{m}\frac{\sin kx }{k} \right| < \epsilon$$
We can show that this criterion is violated and the convergence is not uniform. Take $\epsilon = 1/(4\sqrt{2})$ and, for any integer $N$, no matter how large, choose $n = N$, $m = 2n$ and $x_n = \pi/(4n) \in [0,\pi]$. For any $k > n$, we have $kx_n > \pi/4$ and $\sin kx_n > \sin (\pi/4) = 1/\sqrt{2}$.
Hence,
$$\tag{2}\left|\sum_{k=n+1}^{2n}\frac{\sin kx_n }{k} \right| > \frac{1}{\sqrt{2}}\sum_{k=n+1}^{2n}\frac{1 }{k} > \frac{1}{\sqrt{2}}\cdot n \cdot \frac{1}{2n} = \frac{1}{2\sqrt{2}} > \epsilon,$$
and we have a contradiction to condition (1).


TITLE: Does the following sum converge?
QUESTION [0 upvotes]: Does the sum
$$
\lim_{n\to\infty}\sum_{k=0}^{\lfloor\alpha n \rfloor}C_n^k(-1)^k\left(1-\frac{k}{\alpha n}\right)
$$
converge, where $C_n^k$ is the  binomial coefficient  and $0 <\alpha <1$?

The above question has been solved by Iosif Pinelis. A variation is
$$
\lim_{n\to \infty}\sum_{k=0}^{\lfloor\alpha n \rfloor}C_n^k(-1)^k\left(1-\frac{k}{\alpha n}\right)^n.
$$
How can we handle this sum?

REPLY [4 votes]: $\newcommand\an{\lfloor a n \rfloor}$
Let $a:=\alpha\in(0,1)$. By induction on $m=0,1,\dots$,
$$\sum_{k=0}^m \binom nk(-1)^k\Big(1-\frac k{a n}\Big) \\
=(-1)^{m+1} (a+m-a n)\frac{m+1}{an (n-1)}\,\binom n{m+1}.$$
So, letting $S_n$ denote the sum in question, we have
$$S_n\sim(-1)^{\lfloor a n \rfloor+1}(a-\{a n\}) \,M_n,$$
where $\{a n\}$ is the fractional part of $a n$ and
$$M_n:=\frac1n\,\binom n{\an+1}.$$
Let now $n\to\infty$. Depending on the arithmetical properties of $a$, the factor $(-1)^{\lfloor a n \rfloor+1}$ will alternate between $1$ and $-1$ and the factor $a-\{na\}$ will oscillate between $a-1<0$ and $a>0$, whereas  $M_n\to\infty$, since eventually, for all large enough $n$, we have $\binom n{\an+1}\ge\min[\binom n2,\binom n{n-2}]=n(n-1)/2$. So, the sum $S_n$ will not converge to any limit.

For an illustration, here are the connected graphs $\{(n,c_a^n n^{3/2}\,S_n)\colon n=1,\dots,100\}$ for $a=1/3$ (left) and $a=\sqrt2-1$ (right), where $c_a:=a^a (1 - a)^{1 - a}\in(0,1)$:


TITLE: How to finish the proof of: If $N\unlhd G=H\times K$, then $N$ is abelian or $N$ intersects $H \times \{e\}$ or $\{e\} \times K$ non trivially
QUESTION [1 upvotes]: Question:  Let $N$ is normal to $G=H\times K$, Prove that $N$ is abelian or $N$ intersects one of $H \times \{e\}$ or $\{e\} \times K$ non trivially.
Solution:  Since $G=H\times K$, then $G$ can be written as an internal direct product of $H$ and $K$, then $H\cap K=\{e\}$ Suppose $h\in H$ and $k\in K$ and $hkh^{-1}k^{-1}\in H\cap K$, then $hk=kh$, where $e$ denotes the identity of both $H$ and $K$.  Hence $Nhkh^{-1}k^{-1}=N$, $Nhk=Nkh$. Also, $Nhk=NhNk=Nkh=NkNh$. So $NhNk=NkNh$.  Hence $N$ is a normal abelian group.   If we interpret $G=H\times K$ as the external direct product, then $H\times K=(H\times \{e\})\cdot(\{e\}\times K)$.  Also, since $N\leq (H\times K)$, then $H\cong (H\times \{e\})$, $K\cong (\{e\}\times K)$, $N\cong (N\times \{e\})$ and $N\cong (\{e\}\times N)$, so
$$\begin{align} N\times N&\cong (N\times \{e\})\cdot (\{e\}\times N)\\
&\cong N\cdot N \in N.
\end{align}$$
Can I conclude at this point that both $N\cap H$ and $N\cap K$ are non empty?
Thank you in advance

REPLY [2 votes]: Suppose $N$ is normal, and nonabelian. Since it is nonabelian, there exists an element $(h,k)\in N$ such that either $h$ is not central in $H$, or $k$ is not central in $K$ (if both $h\in Z(H)$ and $k\in Z(K)$, then $(h,k)\in Z(G)$, hence it commutes with everything in $G$, and thus in $N$).
If $h\notin Z(H)$, then there exists $h'\in H$ such that $h'h(h')^{-1}\neq h$. Since $N$ is normal in $G$, then
$(h',e)(h,k)(h',e)^{-1} = (h'h(h')^{-1},k)\in N$. Therefore,
$$(h',e)(h,k)(h',e)(h,k)^{-1} = (h'h(h')^{-1}h^{-1},e)\in N.$$
Since $h'$ and $h$ do not commute, this is a nontrivial element of $H\times \{e\}$. Thus, $N$ intersects $H\times\{e\}$ nontrivially.
If $k\notin Z(K)$, then a symmetric argument shows that $N$ intersects $\{e\}\times K$ nontrivially.
Thus, if $N$ is normal, then either $N$ is abelian, or else $N$ intersects either $H\times\{e\}$ or $\{e\}\times K$ nontrivially.
Note that in fact we established more: the argument holds if $N$ contains an element that is not in $Z(H)\times Z(K) = Z(G)$; so if $N\triangleleft H\times K$, either $N$ is central, or else it intersects $H\times\{e\}$ or $\{e\}\times K$ nontrivially.

If you don't know what the center is, you don't need it. If $N$ is nonabelian find two elements $(h_1,k_1)$ and $(h_2,k_2)$ of $N$ that do not commute. We must have either the $h_i$ nontrivial do not commute, or the $k_i$ nontrivial do not commute. In the first case, conjugate $(h_1,k_1)$ by $(h_2,e)$ and proceed as before. In the latter, conjugate by $(e,k_2)$.


TITLE: Prove this simple graph is not planar.
QUESTION [2 upvotes]: Graph
I need to show this graph is not planar. I've attempted to find $K_5$ and $K_{3,3}$ as a subgraphs but haven't been successful yet. It's possible but unlikely this graph is planar but I haven't been able to draw it as a plane graph.

REPLY [1 votes]: Draw this graph without vertex 10 or 15. Then think of constricting the path 4-20-5-30 down to a single vertex.
Remember, you don't need to have $K_{5}$ or $K_{3,3}$ as subgraphs, only a subgraph that is a subdivision of $K_{5}$ or $K_{3,3}$.


TITLE: Deriving and applying the cosine law
QUESTION [1 upvotes]: A brake lever for a crane is 0.9 meters long and hinged at its base. To fully activate brake, the top end of the lever must move 0.4m horizontally. Through what angle must the lever rotate?

REPLY [0 votes]: Hint:  Have you drawn a picture?  You have a right triangle, with hypotenuse $0.9$ and one leg $0.4$.


TITLE: How to find the orthogonal of a vector
QUESTION [1 upvotes]: Suppose that we have a vector
$w = \begin{bmatrix}
3\\
4.654\\
3.34\\
4.234\\
-1.23\\
\end{bmatrix}$
and we want to find an orthogonal to $w$. I have read about Gram-Schmidt process for me the most simple is the following one. Since the dot product should be $0$, i randomly fix 4 random elements and i compute their inner product $p$ with the first 4 dimensions of vector $w$. Then in order to find the last coefficient of the orthogonal vector i divide $p$ with -1.23 (the last coefficient). Is this a wrong method? And why Gram Schmidt is being preferred?

REPLY [1 votes]: The Gram-Schmidt process is a systematic way of finding a whole set of orthogonal vectors that form a basis for a space spanned by given vectors.  In your case, you're given only one vector, and are tasked with finding another, and the procedure you mention would find two orthogonal vectors in a 5 dimensional space.  How would you find a third orthogonal vector?  Extending your logic, you would have a new vector with three fixed coordinates and two unknowns, then require it to be orthogonal to the first two, giving two equations for the two unknowns.  You would solve the 2x2 system to find a third orthogonal vector.  Then for a fourth, you would fix two coordinates and have three unknowns, and now solve a 3x3 system.  Similar logic shows that the fifth orthogonal vector would require solving a 4x4 system of equations.  What's worse, it's not trivial to pick coordinates to fix and randomly set their values to begin with; if its random, you might accidentally pick something already spanned by the basis you've built so far, in which case the procedure would break down.
The Gram-Schmidt process is simply a consistent way of doing the same thing, that is guaranteed to find an orthonormal basis.  It is certainly simpler to think through and apply consistently when you are solving for an orthogonal basis.  The only operations involved are dot products, vector sums, and scalar multiplication; you never have to solve a system of equations when you use it.  These are the reasons that Gram-Schmidt is preferred.


text:
section \<open>Implementation\<close>

theory HMM_Implementation
  imports
    Hidden_Markov_Model
    "Monad_Memo_DP.State_Main"
begin

subsection \<open>The Forward Algorithm\<close>

locale HMM4 = HMM3 _ _ _ \<O>\<^sub>s \<K> for \<O>\<^sub>s :: "'t set" and \<K> :: "'s \<Rightarrow> 's pmf" +
  assumes states_distinct: "distinct state_list"

context HMM3_defs
begin

context
  fixes os :: "'t iarray"
begin

text \<open>
  Alternative definition using indices into the list of states.
  The list of states is implemented as an immutable array for better performance.
\<close>

function forward_ix_rec where
  "forward_ix_rec s t_end n = (if n \<ge> IArray.length os then indicator {t_end} s else
    (\<Sum>t \<leftarrow> state_list.
      ennreal (pmf (\<O> t) (os !! n)) * ennreal (pmf (\<K> s) t) * forward_ix_rec t t_end (n + 1)))
  "
  by auto
termination
  by (relation "Wellfounded.measure (\<lambda>(_,_,n). IArray.length os - n)") auto

text \<open>Memoization\<close>

memoize_fun forward_ix\<^sub>m: forward_ix_rec
  with_memory dp_consistency_mapping
  monadifies (state) forward_ix_rec.simps[unfolded Let_def]
  term forward_ix\<^sub>m'
memoize_correct
  by memoize_prover

text \<open>The main theorems generated by memoization.\<close>
context
  includes state_monad_syntax
begin
thm forward_ix\<^sub>m'.simps forward_ix\<^sub>m_def
thm forward_ix\<^sub>m.memoized_correct
end

end (* Fixed IArray *)

definition
  "forward_ix os = forward_ix_rec (IArray os)"

definition
  "likelihood_compute s os \<equiv>
    if s \<in> set state_list then Some (\<Sum>t \<leftarrow> state_list. forward s t os) else None"

end (* HMM3 Defs *)

text \<open>Correctness of the alternative definition.\<close>

lemma (in HMM3) forward_ix_drop_one:
  "forward_ix (o # os) s t (n + 1) = forward_ix os s t n"
  by (induction "length os - n" arbitrary: s n; simp add: forward_ix_def)

lemma (in HMM4) forward_ix_forward:
  "forward_ix os s t 0 = forward s t os"
  unfolding forward_ix_def
proof (induction os arbitrary: s)
  case Nil
  then show ?case
    by simp
next
  case (Cons o os)
  show ?case
    using forward_ix_drop_one[unfolded forward_ix_def] states_distinct
    by (subst forward.simps, subst forward_ix_rec.simps)
       (simp add: Cons.IH state_list_\<S> sum_list_distinct_conv_sum_set
             del: forward_ix_rec.simps forward.simps
       )
qed

text \<open>
  Instructs the code generator to use this equation instead to execute \<open>forward\<close>.
  Uses the memoized version of \<open>forward_ix\<close>.
\<close>
lemma (in HMM4) forward_code [code]:
  "forward s t os = fst (run_state (forward_ix\<^sub>m' (IArray os) s t 0) Mapping.empty)"
  by (simp only:
      forward_ix_def forward_ix\<^sub>m.memoized_correct forward_ix_forward[symmetric]
      states_distinct
     )

theorem (in HMM4) likelihood_compute:
  "likelihood_compute s os = Some x \<longleftrightarrow> s \<in> \<S> \<and> x = likelihood s os"
  unfolding likelihood_compute_def
  by (auto simp: states_distinct state_list_\<S> sum_list_distinct_conv_sum_set likelihood_forward)

subsection \<open>The Viterbi Algorithm\<close>

context HMM3_defs
begin

context
  fixes os :: "'t iarray"
begin

text \<open>
  Alternative definition using indices into the list of states.
  The list of states is implemented as an immutable array for better performance.
\<close>

function viterbi_ix_rec where
  "viterbi_ix_rec s t_end n = (if n \<ge> IArray.length os then ([], indicator {t_end} s) else
  fst (
    argmax snd (map
      (\<lambda>t. let (xs, v) = viterbi_ix_rec t t_end (n + 1) in
        (t # xs, ennreal (pmf (\<O> t) (os !! n) * pmf (\<K> s) t) * v))
    state_list)))
  "
  by pat_completeness auto
termination
  by (relation "Wellfounded.measure (\<lambda>(_,_,n). IArray.length os - n)") auto

text \<open>Memoization\<close>

memoize_fun viterbi_ix\<^sub>m: viterbi_ix_rec
  with_memory dp_consistency_mapping
  monadifies (state) viterbi_ix_rec.simps[unfolded Let_def]

memoize_correct
  by memoize_prover

text \<open>The main theorems generated by memoization.\<close>
context
  includes state_monad_syntax
begin
thm viterbi_ix\<^sub>m'.simps viterbi_ix\<^sub>m_def
thm viterbi_ix\<^sub>m.memoized_correct
end

end (* Fixed IArray *)

definition
  "viterbi_ix os = viterbi_ix_rec (IArray os)"

end (* HMM3 Defs *)

context HMM3
begin

lemma viterbi_ix_drop_one:
  "viterbi_ix (o # os) s t (n + 1) = viterbi_ix os s t n"
  by (induction "length os - n" arbitrary: s n; simp add: viterbi_ix_def)

lemma viterbi_ix_viterbi:
  "viterbi_ix os s t 0 = viterbi s t os"
  unfolding viterbi_ix_def
proof (induction os arbitrary: s)
  case Nil
  then show ?case
    by simp
next
  case (Cons o os)
  show ?case
    using viterbi_ix_drop_one[unfolded viterbi_ix_def]
    by (subst viterbi.simps, subst viterbi_ix_rec.simps)
       (simp add: Cons.IH del: viterbi_ix_rec.simps viterbi.simps)
qed

lemma viterbi_code [code]:
  "viterbi s t os = fst (run_state (viterbi_ix\<^sub>m' (IArray os) s t 0) Mapping.empty)"
  by (simp only: viterbi_ix_def viterbi_ix\<^sub>m.memoized_correct viterbi_ix_viterbi[symmetric])

end (* Hidden Markov Model 3 *)

subsection \<open>Misc\<close>

lemma pmf_of_alist_support_aux_1:
  assumes "\<forall> (_, p) \<in> set \<mu>. p \<ge> 0"
  shows "(0 :: real) \<le> (case map_of \<mu> x of None \<Rightarrow> 0 | Some p \<Rightarrow> p)"
  using assms by (auto split: option.split dest: map_of_SomeD)

lemma pmf_of_alist_support_aux_2:
  assumes "\<forall> (_, p) \<in> set \<mu>. p \<ge> 0"
    and "sum_list (map snd \<mu>) = 1"
    and "distinct (map fst \<mu>)"
  shows "\<integral>\<^sup>+ x. ennreal (case map_of \<mu> x of None \<Rightarrow> 0 | Some p \<Rightarrow> p) \<partial>count_space UNIV = 1"
  using assms
  apply (subst nn_integral_count_space)
  subgoal
    by (rule finite_subset[where B = "fst ` set \<mu>"];
        force split: option.split_asm simp: image_iff dest: map_of_SomeD)
  apply (subst sum.mono_neutral_left[where T = "fst ` set \<mu>"])
     apply blast
  subgoal
    by (smt ennreal_less_zero_iff map_of_eq_None_iff mem_Collect_eq option.case(1) subsetI)
  subgoal
    by auto
  subgoal premises prems
  proof -
    have "(\<Sum>x = 0..<length \<mu>. snd (\<mu> ! x))
      = sum (\<lambda> x. case map_of \<mu> x of None \<Rightarrow> 0 | Some v \<Rightarrow> v) (fst ` set \<mu>)"
      apply (rule sym)
      apply (rule sum.reindex_cong[where l = "\<lambda> i. fst (\<mu> ! i)"])
        apply (auto split: option.split)
      subgoal
        using prems(3) by (intro inj_onI, auto simp: distinct_conv_nth)
      subgoal
        by (auto simp: in_set_conv_nth rev_image_eqI)
      subgoal
        by (simp add: map_of_eq_None_iff)
      subgoal
        using map_of_eq_Some_iff[OF prems(3)]
        by (metis fst_conv nth_mem option.inject prod_eqI snd_conv)
      done
    with prems(2) show ?thesis
      by (smt pmf_of_alist_support_aux_1[OF assms(1)] atLeastLessThan_iff ennreal_1
          length_map nth_map sum.cong sum_ennreal sum_list_sum_nth
          )
  qed
  done

lemma pmf_of_alist_support:
  assumes "\<forall> (_, p) \<in> set \<mu>. p \<ge> 0"
    and "sum_list (map snd \<mu>) = 1"
    and "distinct (map fst \<mu>)"
  shows "set_pmf (pmf_of_alist \<mu>) \<subseteq> fst ` set \<mu>"
  unfolding pmf_of_alist_def
  apply (subst set_embed_pmf)
  subgoal for x
    using assms(1) by (auto split: option.split dest: map_of_SomeD)
  subgoal
    using pmf_of_alist_support_aux_2[OF assms] .
  apply (force split: option.split_asm simp: image_iff dest: map_of_SomeD)+
  done

text \<open>Defining a Markov kernel from an association list.\<close>
locale Closed_Kernel_From =
  fixes K :: "('s \<times> ('t \<times> real) list) list"
    and S :: "'t list"
  assumes wellformed: "S \<noteq> []"
      and closed: "\<forall> (s, \<mu>) \<in> set K. \<forall> (t, _) \<in> set \<mu>. t \<in> set S"
      and is_pmf:
        "\<forall> (_, \<mu>) \<in> set K. \<forall> (_, p) \<in> set \<mu>. p \<ge> 0"
        "\<forall> (_, \<mu>) \<in> set K. distinct (map fst \<mu>)"
        "\<forall> (s, \<mu>) \<in> set K. sum_list (map snd \<mu>) = 1"
      and is_unique:
        "distinct (map fst K)"
begin

definition
  "K' s \<equiv> case map_of (map (\<lambda> (s, \<mu>). (s, PMF_Impl.pmf_of_alist \<mu>)) K) s of
  None \<Rightarrow> return_pmf (hd S) |
  Some s \<Rightarrow> s"

sublocale Closed_Kernel K' "set S"
  using wellformed closed is_pmf pmf_of_alist_support
  unfolding K'_def by - (standard; fastforce split: option.split_asm dest: map_of_SomeD)

definition [code]:
  "K1 = map_of (map (\<lambda> (s, \<mu>). (s, map_of \<mu>)) K)"

lemma pmf_of_alist_aux:
  assumes "(s, \<mu>) \<in> set K"
  shows
    "pmf (pmf_of_alist \<mu>) t = (case map_of \<mu> t of
      None \<Rightarrow> 0
    | Some p \<Rightarrow> p)"
  using assms is_pmf unfolding pmf_of_alist_def
  by (intro pmf_embed_pmf pmf_of_alist_support_aux_2)
     (auto 4 3 split: option.split dest: map_of_SomeD)

lemma unique: "\<mu> = \<mu>'" if "(s, \<mu>) \<in> set K" "(s, \<mu>') \<in> set K"
  using that is_unique
  by (smt Pair_inject distinct_conv_nth fst_conv in_set_conv_nth length_map nth_map)

lemma (in -) map_of_NoneD:
  "x \<notin> fst ` set M" if "map_of M x = None"
  using that by (auto dest: weak_map_of_SomeI)

lemma K'_code [code_post]:
  "pmf (K' s) t = (case K1 s of
      None \<Rightarrow> (if t = hd S then 1 else 0)
    | Some \<mu> \<Rightarrow> case \<mu> t of
        None \<Rightarrow> 0
      | Some p \<Rightarrow> p
  )"
  unfolding K'_def K1_def
  apply (clarsimp split: option.split, safe)
                 apply (drule map_of_SomeD, drule map_of_NoneD, force)+
         apply (fastforce dest: unique map_of_SomeD simp: pmf_of_alist_aux)+
  done

end

subsection \<open>Executing Concrete HMMs\<close>

locale Concrete_HMM_defs =
  fixes \<K> :: "('s \<times> ('s \<times> real) list) list"
    and \<O> :: "('s \<times> ('t \<times> real) list) list"
    and \<O>\<^sub>s :: "'t list"
    and \<K>\<^sub>s :: "'s list"
begin

definition
  "\<K>' s \<equiv> case map_of (map (\<lambda> (s, \<mu>). (s, PMF_Impl.pmf_of_alist \<mu>)) \<K>) s of
    None \<Rightarrow> return_pmf (hd \<K>\<^sub>s) |
    Some s \<Rightarrow> s"

definition
  "\<O>' s \<equiv> case map_of (map (\<lambda> (s, \<mu>). (s, PMF_Impl.pmf_of_alist \<mu>)) \<O>) s of
    None \<Rightarrow> return_pmf (hd \<O>\<^sub>s) |
    Some s \<Rightarrow> s"

end

locale Concrete_HMM = Concrete_HMM_defs +
  assumes observations_wellformed': "\<O>\<^sub>s \<noteq> []"
      and observations_closed': "\<forall> (s, \<mu>) \<in> set \<O>. \<forall> (t, _) \<in> set \<mu>. t \<in> set \<O>\<^sub>s"
      and observations_form_pmf':
        "\<forall> (_, \<mu>) \<in> set \<O>. \<forall> (_, p) \<in> set \<mu>. p \<ge> 0"
        "\<forall> (_, \<mu>) \<in> set \<O>. distinct (map fst \<mu>)"
        "\<forall> (s, \<mu>) \<in> set \<O>. sum_list (map snd \<mu>) = 1"
      and observations_unique:
        "distinct (map fst \<O>)"
  assumes states_wellformed: "\<K>\<^sub>s \<noteq> []"
      and states_closed: "\<forall> (s, \<mu>) \<in> set \<K>. \<forall> (t, _) \<in> set \<mu>. t \<in> set \<K>\<^sub>s"
      and states_form_pmf:
        "\<forall> (_, \<mu>) \<in> set \<K>. \<forall> (_, p) \<in> set \<mu>. p \<ge> 0"
        "\<forall> (_, \<mu>) \<in> set \<K>. distinct (map fst \<mu>)"
        "\<forall> (s, \<mu>) \<in> set \<K>. sum_list (map snd \<mu>) = 1"
      and states_unique:
        "distinct (map fst \<K>)" "distinct \<K>\<^sub>s"
begin

interpretation O: Closed_Kernel_From \<O> \<O>\<^sub>s
  rewrites "O.K' = \<O>'"
proof -
  show \<open>Closed_Kernel_From \<O> \<O>\<^sub>s\<close>
    using observations_wellformed' observations_closed' observations_form_pmf' observations_unique
    by unfold_locales auto
  show \<open>Closed_Kernel_From.K' \<O> \<O>\<^sub>s = \<O>'\<close>
    unfolding Closed_Kernel_From.K'_def[OF \<open>Closed_Kernel_From \<O> \<O>\<^sub>s\<close>] \<O>'_def
    by auto
qed

interpretation K: Closed_Kernel_From \<K> \<K>\<^sub>s
  rewrites "K.K' = \<K>'"
proof -
  show \<open>Closed_Kernel_From \<K> \<K>\<^sub>s\<close>
    using states_wellformed states_closed states_form_pmf states_unique by unfold_locales auto
  show \<open>Closed_Kernel_From.K' \<K> \<K>\<^sub>s = \<K>'\<close>
    unfolding Closed_Kernel_From.K'_def[OF \<open>Closed_Kernel_From \<K> \<K>\<^sub>s\<close>] \<K>'_def
    by auto
qed

lemmas O_code = O.K'_code O.K1_def
lemmas K_code = K.K'_code K.K1_def

sublocale HMM_interp: HMM4 \<O>' "set \<K>\<^sub>s" \<K>\<^sub>s "set \<O>\<^sub>s" \<K>'
  using O.Closed_Kernel_axioms K.Closed_Kernel_axioms states_unique(2)
  by (intro_locales; intro HMM4_axioms.intro HMM3_axioms.intro HOL.refl)

end (* Concrete HMM *)

end

subset_name: curated


TITLE: Gaussian like non exponential distributions
QUESTION [0 upvotes]: Lets say I have a probability distribution $f(x) \propto a^{-\lambda x^2}$, where $a$ is any real number not necesarily equal to $e$. What do we call such a distribution? Have such distributions discussed in any detail in literature ? If $a<e$, can we call such a distribution as heavy-tailed ?

REPLY [3 votes]: Assuming $a > 1$, we call it Gaussian.  $a^{-\lambda x^2} = e^{-\beta x^2}$ where $\beta = \lambda \ln(a)$.  If $ a \le 1$, it's not a probability distribution.