text:
\begin{document}

\author{Artem N. Shevlyakov}
\title{Finite subsemigroups of free left regular bands}

\maketitle

\abstract{We describe all finite subsemigroups of free left regular bands. Moreover, we show applications of this result in algebraic geometry and model theory.}

\section{Introduction}

A semigroup is a left regular band if it satisfies the identities $x^2=x$, $xyx=xy$. Left regular bands have important applications in hyperplane arrangements, random walks and matroid theory, see e.g.~\cite{brown,margolis1,margolis2,steinberg,saliola1,saliola2,saliola3,saliola4}. In the current paper we describe all finite subsemigroups of free left regular bands (Theorems~~\ref{th:main_irred} and~\ref{th:main_for_finite_bands}).

Actually, our proof is not short and easy. For example, we had to introduce about six partial orders over left regular bands (remark that all our orders are not compatible with the multiplication over left regular bands).

Let us give the plan of our paper. The first tree sections contain all necessary definitions and simple statements devoted to left regular bands and semilattices. In particular, we give here the important definitions of local linear order and right hereditary property. In Section~\ref{sec:finite_subbands_of_F} we prove (Theorem~\ref{th:S_has_local_linear_order}) that any finite subband of a free left regular band has a local linear order. Thus, the local linear order is the necessary condition of the embeddability into free left regular bands.

In Section~\ref{sec:main_result} we prove that any right hereditary left regular band $S$ with a local linear order is embeddable into a free left regular band of an appropriate rank. Firstly, we define a map $h\colon S\to\F$, where $\F$ is a free left regular band of infinite rank, and prove (Lemma~\ref{l:h_is_homomorphism}) that $h$ is a homomorphism. However, $h$ may be not injective. Therefore, in Subsection~\ref{sec:improving_the_homomorphism} we define a procedure which takes $h$ and obtains an embedding $h^\pr$ after a finite number of iterations. Thus, the embedding $h^\pr$ proves the main result of our paper (Theorem~\ref{th:main_irred}).

In the last section of our paper we talk about open problems and possible applications of Theorem~\ref{th:main_irred}. Moreover, we discuss how to simplify the proof of Theorem~\ref{th:main_irred} and why we do not do it.

\section{Semilattices}

Below we shall consider join semilattices, and denote multiplication by $\cup$. Elements of semilattices are denoted below by bold letters $\xbf,\ybf,\zbf,\ldots$

One can define a partial order over any join semilattice by
\begin{equation}
\xbf\subseteq \ybf \Leftrightarrow \ybf\cup\xbf=\ybf.
\label{eq:definition_of_partial_order}
\end{equation}

Let $M$ be a set, and $\Fbf_M$ be the family of all finite subsets (including $\emptyset$) of $M$. Let us define over $\Fbf_M$ a multiplication as a set union. Obviously, $\Fbf_M$ is isomorphic to the join free semilattice of rank $|M|$ with the adjoined identity. We denote the free basis of $\Fbf_M$ by $\{\a_m|m\in M\}$. Sometimes elements of $\Fbf_M$ (free generators $\a_m$) will be called \textit{words} (respectively, \textit{letters}). By $\a_m\in \cbf$ we shall denote that a letter $\a_m$ belongs to a word $\cbf\in\Fbf_M$.

For any $\b,\c\in\Fbf_M$ one can define $\c\setminus\b\in\Fbf_M$ as the set difference.  The {\it length} $|\a|$ of $\a\in\Fbf_M$ is the length of a word representing $\a$. Let $\Fbf$ denote the free semilattice generated by an infinite set of generators $\{\a_i|i\in\I\}$.

Take a finite join semilattice $L$. According to semilattice theory, $L$ is embeddable into a free semilattice of an appropriate rank. The following embedding will play a crucial role in our study.

Let us define a map $\nu\colon L\to \Fbf_L$ by
\[
\nu(\xbf)=\bigcup_{\xbf\nsubseteq \tbf}\a_\tbf.
\]

\begin{lemma}
$\nu$ is an embedding of $L$ into $\Fbf_L$.
\label{l:nu_is_embedding}
\end{lemma}
\begin{proof}

First, we prove that $\nu$ is a homomorphism of $L$. Let us take $\xbf,\ybf$ and $\zbf=\xbf\cup\ybf$. We have
\[
\nu(\xbf)=\bigcup_{\xbf\nsubseteq \tbf}\a_\tbf,\; \nu(\ybf)=\bigcup_{\ybf\nsubseteq \rbf}\a_\rbf,
\]
\[
\nu(\zbf)=\bigcup_{\zbf\nsubseteq \pbf}\a_\pbf.
\]
It is sufficient to prove
\[
\{\tbf|\xbf\nsubseteq \tbf\}\cup\{\rbf|\ybf\nsubseteq \rbf\}=\{\pbf|\zbf\nsubseteq \pbf\}.
\]

The relation $\xbf\nsubseteq \tbf$ ($\ybf\nsubseteq \rbf$) implies $\zbf\nsubseteq \tbf$ (respectively, $\zbf\nsubseteq \rbf$). Hence,
\[
\{\tbf|\xbf\nsubseteq \tbf\}\cup\{\rbf|\ybf\nsubseteq \rbf\}\subseteq\{\pbf|\zbf\nsubseteq \pbf\}.
\]

Let $\zbf\nsubseteq \pbf$. If $\xbf\subseteq \pbf$ and $\ybf\subseteq \pbf$ then $\zbf=\xbf\cup \ybf\subseteq \pbf$, a contradiction. Therefore, either $\xbf\nsubseteq \pbf$ or $\ybf\nsubseteq \pbf$. Thus, we obtained
\[
\{\tbf|\xbf\nsubseteq \tbf\}\cup\{\rbf|\ybf\nsubseteq \rbf\}\supseteq\{\pbf|\zbf\nsubseteq \pbf\}.
\]

\bigskip

Second, we prove that $\nu$ is an embedding.

Suppose that $F_\xbf=F_\ybf$ for some distinct $\xbf,\ybf$, where
\[
F_\xbf=\{\tbf|\xbf\nsubseteq \tbf\},\; F_\ybf=\{\rbf|\ybf\nsubseteq \rbf\}.
\]
Since $\xbf\notin F_\xbf$, $\ybf\notin F_\ybf$, we have $\xbf\notin F_\ybf$, $\ybf\notin F_\xbf$. It follows that $\xbf\subseteq \ybf$ and $\ybf\subseteq \xbf$, hence $\xbf=\ybf$.

\end{proof}

By the definition of $\nu$, we have the next statement.

\begin{lemma}
If $\nu(\xbf)$ does not contain a letter $\a_\ybf$, then $\xbf\subseteq \ybf$ in $L$.
\label{l:property_of_nu}
\end{lemma}

\begin{lemma}
Let $\xbf,\xbf^\pr,\ybf,\ybf^\pr\in L$, $\xbf\subset\xbf^\pr$, $\ybf\subset\ybf^\pr$ and
\[
d(\xbf^\pr)=\nu(\xbf^\pr)\setminus\nu(\xbf)\subseteq\nu(\ybf^\pr)\setminus\nu(\ybf)=d(\ybf^\pr).
\]
Then $\ybf\subseteq\xbf$.

Moreover, the equality $d(\xbf^\pr)=d(\ybf^\pr)$ implies $\xbf=\ybf$ and $\xbf^\pr=\ybf^\pr$.
\label{l:property_of_nu_new}
\end{lemma}
\begin{proof}
By the definition of $\nu$, $\nu(\xbf)$ does not contain $\a_{\xbf}$.
However $\xbf\subset\xbf^\pr$ implies $\a_\xbf\in\nu(\xbf^\pr)$. Hence,
\[
\a_{\xbf}\in d(\xbf^\pr)\Rightarrow\a_{\xbf}\in d(\ybf^\pr)\Rightarrow\a_{\xbf}\notin \nu(\ybf).
\]
By Lemma~\ref{l:property_of_nu}, the last expression gives $\ybf\subseteq \xbf$.

Suppose $d(\xbf^\pr)=d(\ybf^\pr)$. By above, it follows $\xbf=\ybf$ and therefore $\xbf^\pr=\ybf^\pr$.
\end{proof}

\section{Left regular bands}
\label{sec:left_regular_bands}
A semigroup $S$ is a {\it left regular band} if the next identities
\[
x^2=x,\; xyx=xy
\]
hold in $S$.

{\it Remark that we always consider left regular bands with the identity $\eps$ adjoined.}

By $\F$ we denote the free left regular of infinite rank. The elements of $\F$ are all words $w$ in an infinite alphabet $\{a_i|i\in \I\}$ such that any letter $a_i$ occurs at most one time in $w$. The product of two elements $w_1,w_2\in\F$ is defined as follows:
\[
w_1w_2=w_1\circ (w_2)^{\exists},
\]
where $\circ$ is the word concatenation and the operator $\exists$ is the deletion of all letters which occur earlier. For example, $(a_1a_2a_3)(a_2a_3a_4)=a_1a_2a_3a_4$.

Below elements of $\F$ (free generators $a_i$) are called {\it words} (respectively, {\it letters}), and we shall use the denotation $a_i\in w$ if a letter $a_i$ belongs to a word $w\in\F$.

Remark that in our denotations free generators of the semilattice $\Fbf$ and the left regular band $\F$ are indexed by the common set $\I$.

For elements $x,y$ of a left regular band $S$ one can define a relation
\[
x\leq y \Leftrightarrow xy=y.
\]
It is easy to check that $\leq$ is a partial order over $S$. Remark that in some papers (e.g. see~\cite{steinberg}) $\leq$ defines the contrary relation: $yx=x$.

For elements $x,y\in\F$ the relation $x\leq y$ means that the word $x$ is a prefix of $y$.

The next lemma contains simple statements about the structure of free left regular bands $\F$.

\begin{lemma}
\begin{enumerate}
\item The Hasse diagram of the order $\leq$ is a tree for $\F$. The root of this tree is the identity $\eps$. For example, the Hasse diagram for the free left regular band generated by three elements $a_1,a_2,a_2$ is

\begin{center}
\begin{picture}(400,150)
\put(100,0){\line(3,1){120}}
\put(100,0){\line(-1,1){50}}
\put(100,0){\line(1,2){20}}
\put(85,0){$\eps$}

\put(120,40){\line(1,2){20}}
\put(120,40){\line(-1,2){20}}
\put(125,40){$a_2$}

\put(220,40){\line(1,2){20}}
\put(220,40){\line(-1,2){20}}
\put(225,40){$a_3$}

\put(50,50){\line(1,2){20}}
\put(50,50){\line(-1,2){20}}
\put(55,50){$a_1$}

\put(30,90){\line(0,1){40}}
\put(35,90){$a_1a_2$}
\put(70,90){\line(0,1){40}}
\put(70,90){$a_1a_3$}

\put(200,80){\line(0,1){40}}
\put(205,80){$a_3a_1$}
\put(240,80){\line(0,1){40}}
\put(245,80){$a_3a_2$}

 \put(100,80){\line(0,1){40}}
\put(105,80){$a_2a_1$}
\put(140,80){\line(0,1){40}}
\put(145,80){$a_2a_3$}

\put(20,130){$a_1a_2a_3$}
\put(60,130){$a_1a_3a_2$}
\put(90,120){$a_2a_1a_3$}
\put(130,120){$a_2a_3a_1$}
\put(190,120){$a_3a_1a_2$}
\put(230,120){$a_3a_2a_1$}
\end{picture}

Fig. 1
\end{center}

\item Let $x_1,x_2,y_1,y_2\in \F$, $x_i\leq y_i$ and $x_1,x_2$ are not $\leq$-comparable. Then $y_1,y_2$ are not $\leq$-comparable.

\end{enumerate}
\label{l:simple_properties_of_F}
\end{lemma}

Define the another relation on elements of a left regular band $S$ by
\[
x\preceq y\Leftrightarrow yx=y.
\]
This relation is reflexive and transitive, but not necessarily antisymmetric.

For a free left regular band $\F$ the relation $x\preceq y$ means that the word $y$ contains all letters of a word $x$. For example, $a_1a_2\preceq a_2a_1$, $a_2\preceq a_1a_2a_3$. Obviously, the relation $x\leq y$ implies $x\preceq y$ in any left regular band.

We shall write $x\approx y$ iff $x\preceq y$ and $y\preceq x$. One can get a join semilattice $L$ by identifying $x$ and $y$ if $x\approx y$.
Let $\s\colon S\to L$ denote the quotient map. $L$ is called the {\it support
semilattice} of $S$ and for all $x,y\in S$ we have
\[
\s(xy)=\s(x)\cup\s(y).
\]

It is easy to see that for any $s\in \F$ the map $\s(s)$ gets the set of all letters occurring in $s$.
Thus, we obtain
\[
\s(\F)=\Fbf,
\]
where $\s(a_i)=\a_i$ ($i\in \I$).

Let us define a linear order $<^\F$ over the semilattice $\F$ as follows. We have $\F=\bigcup_{n=0}^\infty L_n$, where $L_n=\{a\in \F\mid\;  |\s(a)|=n\}$ and each set $L_n$ has a linear order $<_{L_n}$. Thus, we put
\[
a<^\F b\Leftrightarrow |\s(a)|<|\s(b)|\mbox{ or } a<_{L_n}b \mbox{ for }a,b\in L_n.
\]
Notice that $x\prec y$ implies $x<^\F y$ for all $x,y\in\F$.

Let us define a map $\overrightarrow{()}\colon\Fbf\to\F$ as follows. Let $\{\a_{i_1},\a_{i_2},\ldots,\a_{i_n}\}$ be the set of all letters of a word $\a\in\Fbf$. The letters of $\a$ correspond to free generators $\{a_{i_1},a_{i_2},\ldots,a_{i_n}\}\subseteq \F$ and the order $<^\F$ is given by
\[
a_{i_1}<^\F a_{i_2}<^\F\ldots<^\F a_{i_n}.
\]
Then the word $\overrightarrow{(\a)}\in\F$ is the product
\[
a_{i_1}a_{i_2}\ldots a_{i_n}.
\]

Roughly speaking, $\overrightarrow{(\a)}$ replaces the letters of $\a$ to the corresponding generators of $\F$ and sorts them in the given order $<^{\F}$.

Following~\cite{steinberg}, a left regular band $S$ is called \textit{right hereditary} if the Hasse diagram of $\leq$ is a tree with the root element $\eps$. By Lemma~\ref{l:simple_properties_of_F}, any free left regular band is right hereditary.

Let $x,y,z$ be elements of a left regular band $S$, and the equivalence relation $\sim_z$ be as follows:
\[
x\sim_z y\Leftrightarrow xz=yz.
\]

Clearly, the relation $x\leq y$ is equivalent to $x\sim_y y$.

\begin{lemma}
Let $S,T$ be left regular bands. Suppose a map $h\colon S\to T$ preserves the relations $\preceq$, $\sim_c$ for each $c\in S$, i.e. for any $a,b,c\in S$ we have:
\[
a\preceq b\Rightarrow h(a)\preceq h(b),
\]
\[
a\sim_c b\Rightarrow h(a)\sim_{h(c)} h(b).
\]
Then $h$ is a homomorphism.
\label{l:condition_of_hom}
\end{lemma}
\begin{proof}
Let us prove $h(xy)=h(x)h(y)$ for all $x,y\in S$. Denote $z=xy$, hence $zy=xy$ and $z\sim_y x$. By the condition, $h(z)h(y)=h(x)h(y)$. Since $y\preceq z$, we have $h(y)\preceq h(z)$ and obtain $h(z)=h(x)h(y)$.
\end{proof}

\begin{example}
Let us define a right hereditary band $\B=\{x_1,x_2,x_3,y_0,y_1,y_2\}$
defined by the following multiplication table (the identity $\eps$ is omitted):

\begin{tabular}{|c||c|c|c|c|c|c|}
\hline
&$x_1$&$x_2$&$x_3$&$y_0$&$y_1$&$y_2$\\
\hline
\hline
$x_1$&$x_1$&$y_0$&$y_1$&$y_0$&$y_1$&$y_1$\\
\hline
$x_2$&$x_2$&$x_2$&$y_2$&$x_2$&$y_2$&$y_2$\\
\hline
$x_3$&$x_3$&$x_3$&$x_3$&$x_3$&$x_3$&$x_3$\\
\hline
$y_0$&$y_0$&$y_0$&$y_1$&$y_0$&$y_1$&$y_1$\\
\hline
$y_1$&$y_1$&$y_1$&$y_1$&$y_1$&$y_1$&$y_1$\\
\hline
$y_2$&$y_2$&$y_2$&$y_2$&$y_2$&$y_2$&$y_2$\\
\hline
\end{tabular}

The order $\leq$ over $\B$ is defined by the following Hasse diagram:

\begin{center}
\begin{picture}(200,100)
\put(100,0){\line(3,2){60}}
\put(100,0){\line(-1,1){30}}
\put(100,0){\line(1,2){20}}
\put(85,0){$\eps$}

\put(120,40){\line(0,1){40}}
\put(125,40){$x_2$}

\put(165,40){$x_3$}

\put(70,30){\line(0,1){40}}
\put(75,30){$x_1$}
\put(75,50){$y_0$}
\put(75,70){$y_1$}

\put(110,80){$y_2$}

\end{picture}

{\it Fig. 2}
\end{center}

The support semilattice of $\B$ is a linear ordered semilattice $1<2<3<4$, where
\[
\s(\eps)=1,\; \s(x_1)=2,\;\s(x_2)=\s(y_0)=3,\;\s(x_3)=\s(y_1)=\s(y_2)=4.
\]

The embedding $\nu$ gives:
\[
\nu(\s(x_1))=\a_1,\;\nu(\s(x_2))=\nu(\s(y_0))=\a_1\a_2,\;\nu(\s(x_3))=\nu(\s(y_1))=\nu(\s(y_2))=\a_1\a_2\a_3.
\]

Thus, $\nu$ embeds $\s(\B)$ into $\Fbf$.

The multiplication over $\B$ generates the following equivalence classes:
\begin{tabular}{|c|c|}
\hline
$x$& Equivalence classes of $\sim_x$\\
\hline
\hline
$x_1$&$\{\eps,x_1\},\{x_2\},\{y_2\},\{y_0\},\{y_1\},\{x_3\}$\\
\hline
$x_2$&$\{\eps,x_2\},\{x_1,y_0\},\{x_3\},\{y_1\},\{y_2\}$\\
\hline
$x_3$&$\{\eps,x_3\},\{x_2,y_2\},\{x_1,y_0,y_1\}$\\
\hline
$y_0$&$\{\eps,x_1,y_0\},\{x_2\},\{x_3\},\{y_2\},\{y_1\}$\\
\hline
$y_1$&$\{\eps,x_1,y_0,y_1\},\{x_2,y_2\},\{x_3\}$\\
\hline
$y_2$&$\{\eps,x_2,y_2\},\{x_3\},\{x_1,y_0,y_1\}$\\
\hline
\end{tabular}

\end{example}

\section{Properties of right hereditary bands}

Below $S$ is a right hereditary band and $L=\s(S)$. The following lemma describes the main property of left regular bands.

\begin{lemma}
The equality $x_1x_2=x_3x_4$ ($x_i\in S$) implies $x_1\leq x_3$ or $x_3\leq x_1$.
\end{lemma}
\begin{proof}
Let $x=x_1x_2=x_3x_4$ and we have $x_1\leq x$, $x_3\leq x$. Since the Hasse diagram of the order $\leq$ is a tree, the elements $x_1,x_3$ should be $\leq$-comparable.
\end{proof}

\begin{lemma}
Let $S$ be a right hereditary band and $x,y,z\in S$. Then $x\leq y\leq xz$ or $y\leq x\leq yz$ iff $x\sim_z y$.
\label{l:sim_from_interval}
\end{lemma}
\begin{proof}
Let us prove the ``only if'' part of the lemma. Let $x\leq y\leq xz$. By the definition of the order $\leq$ we have:
\[
xy=y,\; yxz=xz.
\]
Therefore,
\[
(xy)xz=xz\Leftrightarrow (xy)z=xz\Leftrightarrow yz=xz\Leftrightarrow x\sim_z y.
\]

Let us prove the ``if'' part of the lemma. Since $S$ is right hereditary, the relation $xz=yz$ implies either $x\leq y$ or $y\leq x$. So
\[
x\leq y\leq yz=xz\;\mbox{ or } y\leq x\leq xz=yz.
\]
\end{proof}

Since the Hasse diagram of the order $\leq$ is a tree with the root $\eps$, it allows us to define {\it the ancestor} $\al(s)\in S$ for any $s\neq\eps$ as follows:
\[
\al(s)=\max\{x\in S|x<s\}.
\]
An element $s^\pr$ with $\al(s^\pr)=s$ is called {\it a descendant} of $s$.

For any $c\neq\eps$ let us define a set $S_c\subseteq S$ by
\begin{equation}
S_c=\{s\in S\setminus\{\eps\}|s\sim_c\al(s),s\nsim_{c^\pr}\al(s)\mbox{ for any }c^\pr<c\}
\label{eq:S_c}
\end{equation}

Notice that $S_c\neq\emptyset$, since $c\in S_c$.

\begin{example}
For the left regular band $\B$ we have:
$S_{x_1}=\{x_1\}$, $S_{x_2}=\{x_2,y_0\}$, $S_{x_3}=\{x_3,y_0,y_1,y_2\}$, $S_{y_0}=\{y_0\}$, $S_{y_1}=\{y_1,y_2\}$, $S_{y_2}=\{y_1,y_2\}$.
\end{example}

\begin{lemma}
For any $x\in S_b$, $a<b$ we have $a\preceq\al(x)$.
\label{l:properties_of_S_c}
\end{lemma}
\begin{proof}
By the condition, $a\leq \al(b)<b$.

By Lemma~\ref{l:sim_from_interval} we have
\[
\al(x)\leq x\leq\al(x)b.
\]
Also we have
\[
\al(x)\leq \al(x)a\leq\al(x)ab=\al(x)b.
\]

Since the Hasse diagram of $\leq$ is a tree, the first chain above should contain $\al(x)a$.

If $\al(x)\leq x\leq \al(x)a$ Lemma~\ref{l:sim_from_interval} gives $\al(x)\sim_a x$ that contradicts the definition of the set $S_b$.
Thus,
\[
\al(x)\leq\al(x)a< x.
\]
By the definition of the ancestor, it holds $\al(x)=\al(x)a$, hence $a\preceq\al(x)$.

\end{proof}

\begin{lemma}
For all $x,y\in S_c$ the elements $\al(x)\al(y)x$, $\al(x)\al(y)y$ are $\leq$-comparable.
\label{l:comparable_composition_inS_c}
\end{lemma}
\begin{proof}
By the definition of $S_c$, we have $\al(x)c=xc$, $\al(y)c=yc$. Let us multiply both equalities by $\al(x)\al(y)$ and obtain
\[
\al(x)\al(y)c=\al(x)\al(y)xc,\; \al(x)\al(y)c=\al(x)\al(y)yc.
\]
Therefore,
\[
\al(x)\al(y)xc=\al(x)\al(y)yc.
\]
Since $S$ is right hereditary, the prefixes $\al(x)\al(y)x$, $\al(x)\al(y)y$ are $\leq$-comparable.
\end{proof}

\medskip

Let $s\in S\setminus\{\eps\}$ and denote
\begin{equation}
\delta_\nu(s)=\nu(\s(s))\setminus\nu(\s(\al(s)))\in\Fbf_{L}.
\label{eq:delta_nu(s)}
\end{equation}

A band $S$ has a \textit{local linear order} if for each $b$ the set $S_b$ admits a linear order $\sqsubset_b$ such that for all $x,y\in S_b$ it holds:

\begin{enumerate}
\item
\begin{equation}
\delta_\nu(x)\subset \delta_\nu(y)\Rightarrow x\sqsubset_b y;
\label{eq:sq_cond1}
\end{equation}

\item
\begin{equation}
\s(x)\subseteq \s(\al(y))\Rightarrow x\sqsubset_b y.
\label{eq:sq_cond2}
\end{equation}

\item for arbitrary $S_c\supseteq S_b$ we have:
\begin{equation}
x\sqsubset_b y \Rightarrow x\sqsubset_c y.
\label{eq:sq_cond5}
\end{equation}

\end{enumerate}

\section{Finite subbands of $\F$}
\label{sec:finite_subbands_of_F}

Below in this section we assume $S\subseteq\F$, $|S|<\infty$, $L=\s(S)\subseteq\Fbf$ and $\nu$ embeds $L$ into $\Fbf_L$. Let $\{w\}$ denote the set of all letters of a word $w\in\F$. By the properties of $\F$, for each $x\in S\setminus\{\eps\}\subseteq\F$ there exists a unique $\Delta(x)\in\F$ such that $x=\al(x)\Delta(x)$ and $\{\al(x)\}\cap\{\Delta(x)\}=\emptyset$.

\begin{lemma}
The following correspondences between $\delta_\nu$ and $\Delta$ hold:
\begin{enumerate}
\item
\begin{equation}
\delta_\nu(x)\subseteq\delta_\nu(y)\Rightarrow \Delta(x)\preceq\Delta(y)
\label{eq:delta_subseteq->Delta_subseteq}
\end{equation}
\item
\begin{equation}
\delta_\nu(x)\subset\delta_\nu(y)\mbox{ and }\Delta(x)\approx\Delta(y)\Rightarrow y\prec x.
\label{eq:delta_subset->Delta_subset}
\end{equation}
\end{enumerate}
\end{lemma}
\begin{proof}
\begin{enumerate}
\item By Lemma~\ref{l:property_of_nu_new}, we have $\al(y)\preceq\al(x)$. Let
\[
s_1=\al(x)\al(y)x=\al(x)x=\al(x)\Delta(x),
\]
\[
s_2=\al(x)\al(y)y=\al(x)y=\al(x)\al(y)\Delta(y)=\al(x)\Delta(y).
\]
The images of the support mapping are:
\[
\nu(\s(s_1))=\nu(\s(\al(x)))\cup\nu(\s(\al(y))\cup\nu(\s(x))=\nu(\s(\al(x)))\cup\nu(\s(\al(y))\cup\delta_\nu(x)
\]
\[
\nu(\s(s_2))=\nu(\s(\al(x)))\cup\nu(\s(\al(y))\cup\nu(\s(y))=\nu(\s(\al(x)))\cup\nu(\s(\al(y))\cup\delta_\nu(y)
\]

Since $\delta_\nu(x)\subseteq\delta_\nu(y)$, we have $\nu(\s(s_1))\subseteq\nu(\s(s_2))$, and therefore $s_1\preceq s_2$. By Lemma~\ref{l:comparable_composition_inS_c} $s_1,s_2$ are $\leq$-comparable, hence $s_1\leq s_2$ and
\[
\al(x)\Delta(x)\leq\al(x)\Delta(y).
\]

Let $a$ be a letter form $\Delta(x)$. Since $a\notin\al(x)$, we have $a\in\Delta(y)$. Thus, $\Delta(x)\preceq\Delta(y)$.

\item According to Lemma~\ref{l:property_of_nu_new}, we have
\begin{equation}
\al(y)\preceq\al(x).
\label{eq:gggg1}
\end{equation}

By $\Delta(x)\approx\Delta(y)$ we obtain $y=\al(y)\Delta(y)\preceq \al(x)\Delta(x)=x$. Thus, $y\preceq x$.

Assume
\begin{equation}
x\approx y,
\label{eq:gggg2}
\end{equation}
then
\begin{multline*}
yx=y\Rightarrow \al(y)\Delta(y)\al(x)\Delta(x)=\al(y)\Delta(y) \Rightarrow \\
\al(y)\Delta(y)\al(x)=\al(y)\Delta(y)\Rightarrow \al(x)\preceq\al(y)\Delta(y).
\end{multline*}

By $\Delta(x)\approx\Delta(y)$, the words $\al(x)$ and $\Delta(y)$ have no common letters, therefore, $\al(x)\preceq\al(y)$.

By~(\ref{eq:gggg1}), it follows $\al(x)\approx\al(y)$. Using~(\ref{eq:gggg2}), we obtain $\delta_\nu(x)=\delta_\nu(y)$ that contradicts the condition.
\end{enumerate}
\end{proof}

Let us define relations $\sqsubset^=$, $\sqsubset_b^{\neq}$ over a set $S_b$ as follows:
\[
x\sqsubset^= y \Leftrightarrow \Delta(x)\approx\Delta(y),\;\mbox{ and } y<^\F x,
\]
where the linear order $<^\F$ over $\F$ was defined above.

Define $x\sqsubset_b^{\neq} y$ iff $b$ contains a letter $a\in\{\Delta(y)\}\setminus\{\Delta(x)\}$ and there is not any letter $a^\pr\in\{\Delta(x)\}\setminus\{\Delta(y)\}$ occurring after $a$ in the word $b$. The letter $a$ with such property is called the {\it $(x,y)$-separator} if $b$ does not contain any letter with the same property after $a$.

\begin{example}
If $\Delta(x)=a_1a_2a_3a_5$, $\Delta(y)=a_2a_4a_5$ for some $x,y\in S_b$, $b=a_1a_2a_3a_4a_5$ then $x\sqsubset_b^{\neq} y$ and $a_4$ is the $(x,y)$-separator.
\end{example}

\medskip

Obviously, $\sqsubset_b^{\neq}$ is defined for all $x,y\in S_b$ with distinct sets $\{\Delta(x)\},\{\Delta(y)\}$.

The relation $x\sqsubset_b y$ holds iff
\begin{enumerate}
\item $x\sqsubset_b^{\neq} y$ or
\item $x\sqsubset^= y$ for undefined $x\sqsubset_b^{\neq} y$.
\end{enumerate}

Clearly, $\sqsubset_b$ is defined for any pair $(x,y)\in S_b^2$.

\begin{lemma}
If $x\in S_b$ then $\Delta(x)\preceq\Delta(b)$.
\label{l:inclusion_of_Delta}
\end{lemma}
\begin{proof}
We have $\al(x)b=xb$ and Lemma~\ref{l:properties_of_S_c} gives $\al(b)\preceq \al(x)$. Therefore,
\[
\al(x)b=xb\Leftrightarrow \al(x)\Delta(b)=\al(x)\Delta(x)\Delta(b).
\]
Let $a$ be a letter from the word $\Delta(x)$. Hence, $a$ should occur in the left part of the last equality. Since $\al(x),\Delta(x)$ have no common letters, we obtain $a\in\Delta(b)$. Thus, $\Delta(x)\preceq \Delta(b)$.
\end{proof}

\begin{theorem}
Any finite subband $S\subseteq\F$ has a local linear order.
\label{th:S_has_local_linear_order}
\end{theorem}
\begin{proof}
By the definition of the local linear order, one should prove the following.

Let us prove that $\sqsubset_b$ satisfies all conditions of a local linear order.
\begin{enumerate}

\item {\it $\sqsubset_b$ is a linear order.} By the definition, $\sqsubset_b$ is irreflexive and asymmetric and it is defined for any pair $(x,y)\in S_b^2$. Let us prove the transitivity and take $x\sqsubset_b y$, $y\sqsubset_b z$. We have the following cases.

\begin{enumerate}
\item $x\sqsubset_b^{\neq} y$, $y\sqsubset_b^{\neq} z$. Let us prove $x\sqsubset^{\neq}_b z$.

It follows there exist the $(x,y)$-separator $a$ and the $(y,z)$-separator $a^\pr$. By the definition of a separator, we have $a\in\{\Delta(y)\}\setminus\{\Delta(x)\}$, $a^\pr\in\{\Delta(z)\}\setminus\{\Delta(y)\}$.

Suppose $a$ is before $a^\pr$ in the word $b$ (or $a=a^\pr$). It follows that $a^\pr\notin \Delta(x)$. Let us prove that $a^\pr$ is the $(x,z)$-separator. Take an arbitrary $a^{\pr\pr}\in\{\Delta(x)\}$ after $a^\pr$ in the word $b$. By $x\sqsubset_b^{\neq} y$, $a^{\pr\pr}\in\{\Delta(y)\}$. Since $y\sqsubset_b^{\neq} z$, $a^{\pr\pr}$ should belong to $\{\Delta(z)\}$. Thus, $a^\pr$ is the $(x,z)$-separator and $x\sqsubset_b^{\neq} z$.

Suppose $a$ is after $a^\pr$ in the word $b$. Since $y\sqsubset_b^{\neq} z$, then $a\in\{\Delta(z)\}$. Let us prove that $a$ is the $(x,z)$-separator. Take an arbitrary $a^{\pr\pr}\in\{\Delta(x)\}$ after $a$ in the word $b$. By $x\sqsubset_b^{\neq} y$, we have $a^{\pr\pr}\in\Delta(y)$. Since $y\sqsubset_b^{\neq} z$ and $a^{\pr\pr}$ occurs in $b$ after $a$, $a^{\pr\pr}$ should belong to $\{\Delta(z)\}$. Thus, $a$ is the $(x,z)$-separator, and therefore $x\sqsubset_b^{\neq} z$.

\item $x\sqsubset^= y$, $y\sqsubset^= z$. It easily follows $\Delta(x)\approx\Delta(z)$, $z<^\F y<^\F  x$. Thus, $x\sqsubset^= z$.

\item $x\sqsubset_b^{\neq} y$, $y\sqsubset^= z$. We have $\Delta(y)\approx\Delta(z)$. Let $a$ be the $(x,y)$-separator. Hence, there is not any  $a^\pr\in \{\Delta(x)\}\setminus\{\Delta(y)\}=\{\Delta(x)\}\setminus\{\Delta(z)\}$ after $a$ in the word $b$. Thus, $a$ is the $(x,z)$-separator, and $x\sqsubset_b^{\neq} z$.

\item $x\sqsubset^{=} y$, $y\sqsubset_b^{\neq} z$. This case is similar to the previous one.
\end{enumerate}

\item {\it Prove~(\ref{eq:sq_cond1})}. Take $x,y$ with $\delta_\nu(x)\subset \delta_\nu(y)$. By~(\ref{eq:delta_subseteq->Delta_subseteq}), we have $\Delta(x)\preceq\Delta(y)$.

Assume $\Delta(x)\prec\Delta(y)$. By Lemma~\ref{l:inclusion_of_Delta}, all letters of $\Delta(y)$ belong to the word $b$. Thus, the last letter $a\in\{\Delta(y)\}\setminus\{\Delta(x)\}$ in the word $b$ is the $(x,y)$-separator, and $x\sqsubset_b^{\neq} y$.

If $\Delta(x)\approx\Delta(y)$ then~(\ref{eq:delta_subset->Delta_subset}) gives
\[
y\prec x\Rightarrow y<^\F x\Rightarrow x\sqsubset^= y.
\]

\item {\it Prove~(\ref{eq:sq_cond2})}. By Lemma~\ref{l:inclusion_of_Delta}, all letters of $\Delta(x),\Delta(y)$ belong to the word $b$. Since $x\preceq \al(y)$, the sets of letters $\{x\}$, $\{\Delta(y)\}$ do not intersect. Let $a$ ($a^\pr$) be the last letter from $\{\Delta(x)\}$ (respectively, $\{\Delta(y)\}$) in the word $b$. If $a$ is before $a^\pr$ in $b$ we immediately obtain $x\sqsubset_b y$. Let us assume the converse: $\Delta(b)=d_1a^\pr d_2a d_3$ for some $d_i\in\F$. Using Lemma~\ref{l:properties_of_S_c}, we have $\al(b)\preceq \al(x)$ and
\[
\al(x)b=xb\Rightarrow \al(x)\Delta(b)=x\Delta(b)\Rightarrow \al(x)d_1a^\pr d_2a d_3=x d_1a^\pr d_2a d_3.
\]
The word $\al(x)d_1a^\pr$ does not contain $a$, and $x$ does not contain $a^\pr$. Therefore, the words $\al(x)d_1a^\pr$, $x$ are not $\leq$-comparable, and the last equality does not hold.

\item {\it Prove~(\ref{eq:sq_cond5}).}   Suppose $x\sqsubset^= y$. Since the relation $\sqsubset^=$ does not depend on $b$, we immediately obtain $x\sqsubset_c y$. Let us put $x\sqsubset_b^{\neq} y$, and  $a$ is the $(x,y)$-separator. By Lemma~\ref{l:properties_of_S_c}, $\al(b)\preceq\al(x)$, $\al(b)\preceq\al(y)$, and $\al(c)\preceq\al(b)$ (since $b\in S_b\subseteq S_c$).  Hence, $\{\Delta(x)\}\cap\{\al(b)\}=\{\Delta(y)\}\cap\{\al(b)\}=\emptyset$ and $a\notin\{\al(b)\}$. The equality $\al(b)c=bc$ gives
\[
\al(b)\Delta(c)=\al(b)\Delta(b)\Delta(c).
\]
By Lemma~\ref{l:inclusion_of_Delta}, $\Delta(y)\preceq\Delta(y)$ and therefore $a\in\Delta(b)$. Therefore, the left part of the last equality should contain $a$, hence, $a\in\{\Delta(c)\}$. The relation $x\sqsubset_c^{\neq} y$ fails if there exists a letter $a^\pr\in\{\Delta(x)\}\setminus\{\Delta(y)\}$ and $a^\pr$ occurs after $a$ in $\Delta(c)$. By Lemma~\ref{l:inclusion_of_Delta}, $a^\pr\in\{\Delta(x)\}\subseteq\{\Delta(b)\}$. Since $x\sqsubset_b^{\neq} y$, $a^\pr$ occurs before $a$ in the word $b$.

Thus, $\Delta(c)=c_1ac_2a^\pr c_3$ and $\Delta(b)=b_1a^\pr b_2a b_3$ for some $c_i,b_i\in\F$ and we have
\[
\al(b)\sim_c b\Leftrightarrow \al(b)c_1ac_2a^\pr c_3=\al(b)b_1a^\pr b_2a b_3c_1c_2c_3.
\]
The prefixes $s_1=\al(b)c_1a$, $s_2=\al(b)b_1a^\pr$ are not $\leq$-comparable ($s_1$ does not contain $a^\pr$, $s_2$ does not contain $a$), a contradiction.

Thus, we proved $x\sqsubset_c y$.

\end{enumerate}
\end{proof}

\section{Main result}
\label{sec:main_result}

Recall that $\F=\{a_i|i\in\I\}$ is the free left regular band of infinite rank with the identity adjoined. The aim of this paper is to prove the next theorem.

\begin{theorem}
\label{th:main_irred}
For any finite left regular band $S$ the following conditions are equivalent:
\begin{enumerate}
\item $S$ is embeddable into $\F$;
\item $S$ is right hereditary and has a local linear order.
\end{enumerate}
\end{theorem}

Obviously, Theorem~\ref{th:main_irred} immediately gives the following result for free left regular bands of finite ranks.

\begin{theorem}
\label{th:main_for_finite_bands}
For any finite left regular band $S$ the following conditions are equivalent:
\begin{enumerate}
\item $S$ is embeddable into a free left regular band $\F_n$ of an appropriate rank $n$;
\item $S$ is right hereditary and has a local linear order.
\end{enumerate}
\end{theorem}

Let us come back to the proof of Theorem~\ref{th:main_irred}. The implication \noindent ${(1)\Rightarrow(2)}$ follows from Theorem~\ref{th:S_has_local_linear_order}.
The implication $(2)\Rightarrow(1)$ is quite complicated, so its proof is divided into two parts. Below $S$ is a finite right hereditary band with a local linear order.

\subsection{Orderings and homomorphisms}

Let $L=\s(S)$. {\it One can initially assume that $L$ is a subsemilattice of $\Fbf$. Thus, below we consider elements of $L$ as words of $\Fbf$}. Let $s\in S\setminus\{\eps\}$ and
\[
\delta(s)=\s(s)\setminus\s(\al(s))\in\Fbf
\]
(obviously, $\delta(s)$ coincides with $\delta_\nu(s)$ defined in~(\ref{eq:delta_nu(s)}) if we embed $L$ into $\Fbf$ via the embedding $\nu$).

For any $c\in S$ we define a vector
\begin{equation}
\label{eq:char}
\chi(c)=(\chi(\al(c)),y_1,y_2,\ldots,y_{n_c})
\end{equation}
such that
\begin{enumerate}
\item $\chi(c)$ is a recursive structure, since it contains a subvector $\chi(\al(c))$;
\item $S_c=\{y_1,y_2,\ldots,y_{n_c}\}$;
\item $y_i\sqsubset_c y_{i+1}$;
\item $\chi(\eps)$ is the empty vector.
\end{enumerate}

\begin{example}
Let us show that the left regular band $\B$ from the previous examples has a local linear order and compute the vectors $\chi(c)$ for each $c\in S_c$.

For elements of $\B$ we have $\delta(x_1)=\a_1$, $\delta(x_2)=\a_1\a_2$, $\delta(x_3)=\a_1\a_2\a_3$, $\delta(y_0)=\a_2$, $\delta(y_1)=\a_3$, $\delta(y_2)=\a_3$ (since $\nu$ embeds $\s(\B)$ into $\Fbf$ we have $\delta(s)=\delta_\nu(s)$ for each $s\in \B$).

One of the possible definitions of $\sqsubset_b$ is in the following table (if a set $S_b$ consists of a unique element the definition of $\sqsubset_b$ is omitted). Using the definition of $\sqsubset_b$, one can define vectors $\chi(b)$.

\begin{tabular}{|c|c|c|}
\hline
$x$& $\sqsubset_x$ over $S_x$& $\chi(x)$\\
\hline
\hline
$x_1$&---&$(x_1)$\\
\hline
$x_2$&$y_0\sqsubset x_2$&$(y_0,x_2)$\\
\hline
$x_3$&$y_0\sqsubset y_1\sqsubset y_2\sqsubset x_3$&$(y_0,y_1,y_2,x_3)$\\
\hline
$y_0$& ---&$(\chi(x_1),y_0)$\\
\hline
$y_1$& $y_1\sqsubset y_2$&$(\chi(y_0),y_1,y_2)$\\
\hline
$y_2$& $y_1\sqsubset y_2$&$(\chi(x_2),y_1,y_2)$\\
\hline
\end{tabular}

\end{example}

One can recursively apply~(\ref{eq:char}) to $\al(c)$ and obtain a new vector
\[
\chi(c)=(\chi(\al(\al(c))),x_1,x_2,\ldots,x_{n_{\al(c)}},y_1,y_2,\ldots,y_{n_c}).
\]

It allows us to descend to any element $a\leq c$ obtaining the vector:
\begin{equation}
\chi(c)=(\chi(a),\ldots,y_1,y_2,\ldots,y_{n_c}).
\label{eq:char_iterate}
\end{equation}

We shall say $y\in\chi(c)$ if  $y\in S_c$ or $y\in\chi(\al(c))$.

\begin{lemma}
Let $\chi(c)$ be the vector~(\ref{eq:char}). Then any element $y$ with $y\sim_c \al(y)$ belongs to $\chi(c)$.
\label{l:sim_c_in_char}
\end{lemma}
\begin{proof}
Let $c^\pr\leq c$ be the maximal element such that $\al(y)\nsim_{\al(c^\pr)} y$ and $\al(y)\sim_{c^\pr} y$ (such element always exists in the set $\{s\in S|\eps<s\leq c\}$). Therefore, $y\in S_{c^\pr}$ and $y\in \chi(c^\pr)\subseteq\chi(c)$.
\end{proof}

Now we are able to define a map $h\colon S\to \F$ of a right hereditary band $S$.
\begin{equation}
h(c)=\begin{cases}
\eps, \mbox{ if }c=\eps,\\
h(\al(c))c_1c_2\ldots c_n, \mbox{ otherwise}
\end{cases},
\label{eq:h(c)}
\end{equation}
where $\chi(c)=(\chi(\al(c)),y_1,y_2,\ldots,y_n)$ and $c_i=\overrightarrow{\delta(y_i)}$ (the operator $\overrightarrow{()}$ was defined in Section~\ref{sec:left_regular_bands}).

\begin{example}
Let us compute the images of $h$ for elements of the left regular band $\B$ defined in examples above. Let us fix an order over the free generators $a_1<^{\F}a_2<^{\F} a_3$ and obtain

\begin{tabular}{|c|c|c|}
\hline
$x$& $\overrightarrow{\delta(x)}$& $h(x)$\\
\hline
\hline
$x_1$&$a_1$&$a_1$\\
\hline
$x_2$&$a_1a_2$&$(a_2)\cdot(a_1a_2)=a_2a_1$\\
\hline
$x_3$&$a_1a_2a_3$&$(a_2)\cdot(a_3)\cdot(a_3)(a_1a_2a_3)=a_2a_3a_1$\\
\hline
$y_0$&$a_2$&$h(x_1)\cdot(a_2)=a_1a_2$\\
\hline
$y_1$&$a_3$&$h(y_0)\cdot(a_3)\cdot(a_3)=a_1a_2a_3$\\
\hline
$y_2$&$a_3$&$h(x_2)\cdot(a_3)\cdot(a_3)=a_2a_1a_3$\\
\hline
\end{tabular}

One can directly check that $h$ embeds $\B$ into $\F$.
\end{example}

\bigskip

Since $h(c)$ is recursively defined by the image $h(\al(c))$ and $h(\al(c))\leq h(c)$, we obtain the next simple statement.

\begin{lemma}
The map $h$ preserves the order $\leq$: if $a\leq b$ then $h(a)\leq h(b)$.
\label{l:h_preserves_leq_order}
\end{lemma}

\medskip

\begin{lemma}
For any $c\in S$ it holds $\s(h(c))=\s(c)$ (recall that both elements $\s(s),\s(h(s))$ belong to $\Fbf$).
\label{l:h_preserves_preq}
\end{lemma}
\begin{proof}
If $c=\eps$ the equality obviously holds. Assume the equality holds for the ancestor $\al(c)$:
\begin{equation*}
\s(h(\al(c)))=\s(\al(c))

\end{equation*}

Let $\chi(c)$ be the vector~(\ref{eq:char}), and the image $h(c)$ is defined by~(\ref{eq:h(c)}).
Since $c\in S_c$, there exists an index $i$ such that $y_i=c$, hence
\begin{equation*}
\s(h(c))\supseteq\s(h(\al(c)))\cup\delta(c)=\s(\al(c))\cup\delta(c)=\s(c).

\end{equation*}

Let us prove the contrary inclusion.
By the choice of the elements $y_i$, we have $y_ic=\al(y_i)c$, hence $\s(y_i)\cup\s(c)=\s(\al(y_i))\cup\s(c)$ and it follows
\begin{equation*}
\delta(y_i)\subseteq\s(c).
\end{equation*}

Thus,
\[
\s(h(c))=\s(h(\al(c)))\bigcup_i\delta(y_i)\subseteq\s(\al(c))\cup\s(c)=\s(c).
\]
\end{proof}

We need the next auxiliary lemma.

\begin{lemma}
Let $y,z,c\in S\setminus\{\eps\}$, $z\sim_c\al(z)$, $s=\al(z)yz$, $s\neq\al(z)y$ and in the chain
\[
s=s_0>s_1>\ldots>s_{k-1}>s_k=\al(z)y
\]
each $s_i$ is the ancestor of $s_{i-1}$ ($1\leq i\leq k$). Then
\begin{enumerate}
\item $s_i\sim_c s_{i-1}$;
\item $\s(s)\setminus\s(\al(z)y)\subseteq \delta(z)$;
\item $\delta(s_i)\subseteq \s(s)\setminus\s(\al(z)y)$;
\item $\delta(s_i)\subseteq\delta(z)$;
\item
\begin{equation}
\bigcup_{i=0}^k\delta(s_i)=\s(s)\setminus\s(\al(z)\al(b));
\label{eq:sum_of_delta_s_i}
\end{equation}
\item the equality $\delta(s_i)=\delta(z)$ implies $k=1$;
\item suppose $z\in S_{c^\pr}$ (it follows $c^\pr\leq c$). Then $s_i\in S_{c_i}$ for some $c_i\leq c^\pr$;
\item if $\delta_\nu(s_i)\subset \delta_\nu(z)$ then $s_i$ occurs before $z$ in the vector $\chi(c)$.
\end{enumerate}
\label{l:aux}
\end{lemma}
\begin{proof}
\begin{enumerate}
\item We have the chain
\[
\al(z)y=s_k<s_{k-1}<\ldots< s_0=\al(z)yz\leq\al(z)yzc=\al(z)y\al(z)c=\al(z)yc.
\]
By Lemma~\ref{l:sim_from_interval}, $s_i\sim_c\al(z)y$ and therefore $s_i\sim_c s_{i-1}$.

\item Suppose a letter $\abf$ belongs to $\s(\al(z)yz)\setminus\s(\al(z)y)\in \Fbf$. Then $\abf\in\s(z)$ but $\abf\notin\s(\al(z))$. Thus, $\abf\in\delta(z)$.

\item Consider a letter $\abf\in\delta(s_i)$. Hence, $\abf\in \s(s_i)\subseteq\s(s)$, $\abf\notin\s(s_{i+1})$. Since $s_{i+1}\geq\al(z)y$, we have $\abf\notin \s(\al(z)y)$. Thus, $\abf\in \s(s)\setminus\s(\al(z)y)$.

\item The statement immediately follows from the previous ones.

\item
We have $\s(s_{i-1})=\delta(s_{i-1})\sqcup\s(s_i)$  ($\xbf \sqcup\ybf$ is the join of words $\xbf,\ybf\in\Fbf$ which do not have common letters). Thus,
\[
\s(s_0)=\delta(s_0)\sqcup\s(s_1)=\delta(s_0)\sqcup\delta(s_1)\sqcup\s(s_2)=\ldots=
\bigcup_{i=0}^k\delta(s_i)\sqcup \s(\al(z)y)
\]
and we obtain~(\ref{eq:sum_of_delta_s_i}).

\item Immediately follows from~(\ref{eq:sum_of_delta_s_i}) and previous statements of the lemma.

\item We have $z\sim_{c^\pr}\al(z)$. One can repeat the proof of the first statement of the lemma for $c^\pr$ instead of $c$ and obtain $s_i\sim_{c^\pr} s_{i-1}$. Therefore, $s_i\in S_{c_i}$ for some $c_i\leq c^\pr\leq c$

\item By the previous statement of the lemma, each $s_i$ belongs to $S_{c_i}$ for some $c_i\leq c^\pr$. Therefore, the element $s_i$ ($z$) belongs to the vector $\chi(c_i)$ (respectively, $\chi(c^\pr)$). If $c_i<c^\pr$, then the contents of $\chi(c_i)$ occur before the contents of $\chi(c^\pr)$ in the vector $\chi(c)$, and therefore $s_i$ occur before $z$ in the vector $\chi(c)$. If $c_i=c^\pr$ then, according to~(\ref{eq:sq_cond1}), the condition $\delta_\nu(s_i)\subset \delta_\nu(z)$ implies $s_i\sqsubset_{c^\pr} z$. Therefore, $s_i$ occurs before $z$ in the vector $\chi(c^\pr)$. Since the vector $\chi(c^\pr)$ is included in $\chi(c)$, $s_i$ occurs before $z$ in $\chi(c)$.

\end{enumerate}
\end{proof}

{\it Recall that Lemma~\ref{l:aux} holds for any embedding of $\s(S)$ into $\Fbf$. If we replace all occurrences of $\delta$ to $\delta_\nu$ we obtain true statements about the embedding $\nu$.}

\begin{lemma}
The map $h\colon S\to \F$ is a homomorphism of a right hereditary band $S$.
\label{l:h_is_homomorphism}
\end{lemma}
\begin{proof}
Using Lemmas~\ref{l:condition_of_hom},~\ref{l:h_preserves_preq}, it is sufficient to prove the implication
\begin{equation}
a\sim_c b\Rightarrow h(a)\sim_{h(c)} h(b).
\label{eq:h(a)_sim_h(c)_h(b)}
\end{equation}

First, we prove
\begin{equation}
\al(b)\sim_c b\Rightarrow h(\al(b))\sim_{h(c)} h(b).
\label{eq:h(al_b)_sim_h(c)_h(b)}
\end{equation}

By the definition of $h$, one can write
\begin{equation*}
h(b)=h(\al(b))b_1b_2\ldots b_n,
\end{equation*}
\begin{equation*}
h(c)=c_1c_2\ldots c_m

\end{equation*}
(in the last expression we iterate the definition of $h(c)$ to the identity $\eps$), and there exist vectors
\[
\chi(b)=(\chi(\al(b)),y_1,y_2,\ldots,y_n),
\]
\[
\chi(c)=(z_1,z_2,\ldots,z_m),
\]
such that $b_i=\overrightarrow{\delta(y_i)}$, $c_j=\overrightarrow{\delta(z_j)}$.

Lemma~\ref{l:sim_c_in_char} states $z_j\sim_c\al(z_j)$ ($1\leq j\leq m$), $y_i\sim_b\al(y_i)$ ($1\leq i\leq n$). Using Lemmas~\ref{l:sim_from_interval},~\ref{l:properties_of_S_c}, we have the following chain
\[
\al(y_i)\leq y_i\leq \al(y_i)b\leq\al(y_i)bc =(\al(y_i)\al(b))c=\al(y_i)c.
\]

By Lemma~\ref{l:sim_from_interval}, it follows $\al(y_i)\sim_c y_i$. Thus, the vector $\chi(c)$ contains all $y_i$. In other words, there exists a function $f\colon\{1,2,\ldots,n\}\to\{1,2,\ldots,m\}$ which embeds $\{y_1,y_2,\ldots,y_n\}$ into $\chi(c)$ ($y_i=z_{f(i)}$).
By~(\ref{eq:sq_cond5}), the function $f$ is monotone:
$i_1<i_2\to f(i_1)<f(i_2)$.

\medskip

Let $z\in \chi(c)$ and below we prove that one of the following holds:
\begin{enumerate}
\item
\begin{equation}
\delta(z)\subseteq\bigcup_j\delta(z_j)\cup\s(\al(b)),
\label{eq:z_depends_on_previous}
\end{equation}
where elements $z_j$ occur in $\chi(c)$ before $z$;
\item $z$ is after $b$ in $\chi(c)$;
\item $z$ belongs to $\chi(b)$, i.e. $z=y_i$ or $z\in\chi(\al(b))$.
\end{enumerate}

Assume for some $z\in\chi(c)$ all conditions above fail. Let $s=\al(z)\al(b)z$. If $s=\al(z)\al(b)$ then $\delta(z)\subseteq \s(\al(b))$, and~(\ref{eq:z_depends_on_previous}) holds. Therefore, we assume below $s>\al(z)\al(b)$, and we have a nontrivial chain
\[
s=s_0>s_1>\ldots>s_k>\al(z)\al(b),
\]
where each $s_i$ is the ancestor of the previous one. By Lemma~\ref{l:aux} we have $s_i\sim_c\al(s_i)$, and all $s_i$ belong to the vector $\chi(c)$ (Lemma~\ref{l:sim_c_in_char}).

We have the following cases.

\begin{enumerate}
\item Let $s=z$ and denote $s^\pr=\al(z)b$ (we use $z\sim_c \al(z)$ below):
\begin{multline*}
\al(z)\al(b)z=z\Rightarrow \al(z)\al(b)zc=zc\Rightarrow \al(z)\al(b)\al(z)c=zc\Rightarrow \al(z)(\al(b)c)=zc
\\
\Rightarrow \al(z)bc=zc\Rightarrow s^\pr c=zc.
\end{multline*}
Since $S$ is right hereditary, the elements $z,s^\pr$ are $\leq$-comparable. Thus, we have the following cases.
\begin{enumerate}
\item If $z\leq s^\pr$ then
\[
\al(z)\leq z\leq\al(z)b
\]
and Lemma~\ref{l:sim_from_interval} gives $\al(z)\sim_b z$. Thus, $z$ should occur in the $\chi(b)$, a contradiction.

\item Let $s^\pr=\al(z)b< z$. By the definition of the ancestor  (there are not elements between $\al(z)$ and $z$), we obtain $s^\pr=\al(z)$. Thus, $b\preceq\al(z)$. By~(\ref{eq:sq_cond2}), we have $b\sqsubset_c z$, therefore $z$ occurs after $b$ in $\chi(c)$, a contradiction with the choice of $z$.

\end{enumerate}

\item Let $s\neq z$ and Lemma~\ref{l:aux} gives $\delta_\nu(s)\subseteq \delta_\nu(z)$. If we assume $\delta_\nu(s)=\delta_\nu(z)$ then $\al(z)\approx\al(s)\succeq \al(z)\al(b)$ (Lemma~\ref{l:property_of_nu_new}) and we have $\al(b)\preceq \al(z)$. Therefore
\[
s=(\al(z)\al(b))z=\al(z)z=z,
\]
a contradiction.

Thus, $\delta_\nu(s)\subset\delta_\nu(z)$, and Lemma~\ref{l:aux} provides $\delta_\nu(s_i)\subset\delta_\nu(z)$. By the last statement of Lemma~\ref{l:aux}, all $s_i$ occur before $z$ in $\chi(c)$. Let
\[
\cbf=\s(\al(b))\cup\bigcup_{i=0}^k\delta(s_i).
\]
By~(\ref{eq:sum_of_delta_s_i}), $\cbf=\s(\al(b))\cup (\s(s)\setminus\s(\al(z)\al(b)))$.

Let us prove $\cbf\supseteq\delta(z)$. Suppose a letter $\abf$ belongs to the word $\delta(z)$. Therefore, $\abf\in\s(z)$, $\abf\notin \s(\al(z))$. If $\abf\in \s(\al(b))$ we immediately obtain $\abf\in\cbf$. Otherwise ($\abf\notin\s(\al(b))$), we have
\[
\abf\in \s(z)\setminus\s(\al(z)\al(b))\Rightarrow \abf\in\cbf.
\]

Thus, we have proved~(\ref{eq:z_depends_on_previous}) that contradicts the choice of $z$.

\end{enumerate}

\bigskip

Let us come back to the equality~(\ref{eq:h(al_b)_sim_h(c)_h(b)}). One should prove
\begin{equation}
h(\al(b))c_1c_2\ldots c_m=h(\al(b))b_1b_2\ldots b_nc_1c_2\ldots c_m.
\label{eq:cdsfsdfdfs}
\end{equation}

Since $b\in\chi(b)$ and $b\in \chi(c)$, there exists an index $i$ such that $\overrightarrow{\delta(y_i)}=\overrightarrow{\delta(z_{f(i)})}=\overrightarrow{\delta(b)}$. For each $z_k$, $k<f(i)$ we have one of the following
\begin{enumerate}
\item $z_k\in \chi(b)$ (probably, $z_k\in\chi(\al(b))$);
\item $z_k$ satisfies~(\ref{eq:z_depends_on_previous}).
\end{enumerate}

In the second case all letters of $c_k$ are eliminated by letters of previous elements and one can remove such $c_k$ from~(\ref{eq:cdsfsdfdfs}). If $z_k\in\chi(\al(b))$ then all letters of $c_k$ occur in $h(\al(b))$ (Lemma~\ref{l:h_preserves_preq}) and $c_k$ can be removed from~(\ref{eq:cdsfsdfdfs}).

Thus one can reduce~(\ref{eq:cdsfsdfdfs}) to
\begin{multline}
h(\al(b))b_1b_2\ldots b_{i-1}\overrightarrow{\delta(b)} c_{f(i)+1}c_{f(i)+2}\ldots c_m=\\
h(\al(b))b_1b_2\ldots b_{i-1}\overrightarrow{\delta(b)}b_{i+1}\ldots b_n b_1b_2\ldots b_{i-1}\overrightarrow{\delta(b)} c_{f(i)+1}c_{f(i)+2}\ldots c_m\Leftrightarrow\\
h(\al(b))b_1b_2\ldots b_{i-1}\overrightarrow{\delta(b)} c_{f(i)+1}c_{f(i)+2}\ldots c_m=
h(\al(b))b_1b_2\ldots b_{i-1}\overrightarrow{\delta(b)}b_{i+1}\ldots b_n c_{f(i)+1}c_{f(i)+2}\ldots c_m.
\label{eq:hgrghth}
\end{multline}

Relations $\al(y_i)\sim_b y_i$ implies
\[
\s(y_i)\cup\s(b)=\s(\al(y_i))\cup \s(b)\Rightarrow \delta(y_j)\subseteq \s(b)=\s(\al(b))\cup\delta(b)=\s(h(\al(b)))\cup\delta(b).
\]

Therefore, the elements $b_{i+1},b_{i+2},\ldots,b_n$ in~(\ref{eq:hgrghth}) are eliminated by letters of $h(\al(b)),\overrightarrow{\delta(b)}$, and~(\ref{eq:hgrghth}) becomes a true equality:
\[
h(\al(b))b_1b_2\ldots b_{i-1}\overrightarrow{\delta(b)} c_{f(i)+1}c_{f(i)+2}\ldots c_m=
h(\al(b))b_1b_2\ldots b_{i-1}\overrightarrow{\delta(b)}c_{f(i)+1}c_{f(i)+2}\ldots c_m.
\]

Thus, we have proved~(\ref{eq:h(al_b)_sim_h(c)_h(b)}).

Let us prove~(\ref{eq:h(a)_sim_h(c)_h(b)}) using~(\ref{eq:h(al_b)_sim_h(c)_h(b)}). Since $S$ is right hereditary, $a<b$ (similarly, one can assume $b<a$). Therefore, there exists a chain
\[
b=b_0>b_1>\ldots>b_r=a,
\]
where $b_i=\al(b_{i-1})$. Since $a\leq b_i\leq b\leq ac$, Lemma~\ref{l:sim_from_interval} gives
$a\sim_c b_i$. The transitivity of $\sim_c$ provides $b_{i+1}\sim_c b_i$. Above we proved $h(b_{i+1})\sim_{h(c)} h(b_i)$, and the transitivity of $\sim_{h(c)}$ gives $h(a)\sim_{h(c)} h(b)$.

\end{proof}

\subsection{Improving the homomorphism}
\label{sec:improving_the_homomorphism}

The homomorphism $h\colon S\to\F$ defined above is not necessarily an embedding of $S$ into $\F$. In other words, it is possible
\[
\ker(h)=\{(s_1,s_2)|s_1\neq s_2,\;h(s_1)=h(s_2)\}\neq \emptyset.
\]

\begin{example}
Let us define a right hereditary band $\B^\pr=\{x_1,x_2,x_3,y_1,y_2,y_3\}$
by the following multiplication table (the identity $\eps$ is omitted):

\begin{tabular}{|c||c|c|c|c|c|c|}
\hline
&$x_1$&$x_2$&$x_3$&$y_1$&$y_2$&$y_3$\\
\hline
\hline
$x_1$&$x_1$&$x_1$&$y_1$&$y_1$&$y_2$&$y_3$\\
\hline
$x_2$&$x_2$&$x_2$&$y_3$&$y_3$&$y_3$&$y_3$\\
\hline
$x_3$&$x_3$&$x_3$&$x_3$&$x_3$&$x_3$&$x_3$\\
\hline
$y_1$&$y_1$&$y_1$&$y_1$&$y_1$&$y_1$&$y_1$\\
\hline
$y_2$&$y_2$&$y_2$&$y_2$&$y_2$&$y_2$&$y_2$\\
\hline
$y_3$&$y_3$&$y_3$&$y_3$&$y_3$&$y_3$&$y_3$\\
\hline
\end{tabular}

The order $\leq$ over $\B^\pr$ is defined by:

\begin{center}
\begin{picture}(200,100)
\put(100,0){\line(3,2){60}}
\put(100,0){\line(-1,1){30}}
\put(100,0){\line(1,2){20}}
\put(85,0){$\eps$}

\put(120,40){\line(0,1){40}}
\put(125,40){$x_2$}

\put(165,40){$x_3$}

\put(70,30){\line(0,1){40}}
\put(75,30){$x_1$}
\put(75,70){$y_1$}

\put(70,30){\line(1,1){30}}
\put(105,60){$y_2$}

\put(110,80){$y_3$}

\end{picture}

{\it Fig. 3}
\end{center}

The support semilattice of $\B^\pr$ is a linear ordered semilattice $1<2<3$, where
\[
\s(\eps)=1,\; \s(x_1)=\s(x_2)=2,\; \s(x_3)=\s(y_1)=\s(y_2)=\s(y_3)=3.
\]

The embedding $\nu$ gives:
\[
\s(x_1)=\s(x_2)=\a_1,\; \s(x_3)=\s(y_1)=\s(y_2)=\s(y_3)=\a_1\a_2.
\]

Thus, the embedding $\nu$ embeds $\s(\B^\pr)$ into $\Fbf$. We have (computing $\overrightarrow{\delta(x)}$, we use $a_1<^{\F} a_2$):

\begin{tabular}{|c|c|c|c|c|c|}
\hline
$x$& $S_x$ & $\sqsubset_x$ &$\overrightarrow{\delta(x)}$& $\chi(x)$& $h(x)$\\
\hline
\hline
$x_1$&$\{x_1\}$&---&$a_1$&$(x_1)$&$a_1$\\
\hline
$x_2$&$\{x_2\}$&---&$a_1$&$(x_2)$&$a_1$\\
\hline
$x_3$&$\{x_3,y_1,y_3\}$&$y_1\sqsubset y_2\sqsubset x_3$&$a_1a_2$&$(y_1,y_2,x_3)$&$a_2a_1$\\
\hline
$y_1$&$\{y_1,y_3\}$&$y_1\sqsubset y_3$&$a_2$&$(\chi(x_1),y_1,y_3)$&$a_1a_2$\\
\hline
$y_2$&$\{y_2,y_3\}$&$y_2\sqsubset y_3$&$a_2$&$(\chi(x_1),y_2,y_3)$&$a_1a_2$\\
\hline
$y_3$&$\{y_2,y_3\}$&$y_2\sqsubset y_3$&$a_2$&$(\chi(x_2),y_2,y_3)$&$a_1a_2$\\
\hline
\end{tabular}

Thus, we have a nonempty kernel
\[
\ker(h)=\{(x_1,x_2),(y_1,y_2),(y_1,y_3),(y_2,y_3)\}.
\]
\end{example}

Below we define a series of homomorphisms $h_1,h_2,\ldots,h_m$ such that
\[
\ker(h)\supset \ker(h_{1})\supset \ker(h_{2})\supset\ldots\supset \ker(h_{m})=\emptyset.
\]
using the next algorithm.

\begin{center}
{\bf Embedding algorithm}
\end{center}

\begin{enumerate}
\item[INPUT:] a homomorphism $h\colon S\to \F$.
\item[OUTPUT:] an embedding $h^\pr\colon S\to \F$.

\item Put $h^\pr=h$, and $F^\pr$ is the free left regular band generated by letters $\{a_i\mid\exists s\in S, \; a_i\in h(s)\}$.
\item Take $c\in S$ such that $b_1,b_2,\ldots,b_k$ are all descendants of $c$ ($\al(b_i)=c$), and $h^\pr(b_i)\leq h^\pr(b_j)$ for some distinct $i,j$;

Apply Modification$(h^\pr,F^\pr,c,b_1,b_2,\ldots,b_k)$ (see below) and obtain a new homomorphism $h^\pr$ and a new free left regular band $F^\pr$.
\item If there is not any $c\in S$ from the previous step, we terminate the algorithm.
\end{enumerate}

\bigskip

\begin{center}
{\bf Modification($h,F,c,b_1,b_2,\ldots,b_k$)}
\end{center}
\begin{enumerate}
\item[INPUT:] a homomorphism $h\colon S\to F$, free left regular band $F$, $c\in S$, and all descendants $b_1,b_2,\ldots,b_k$ of $c$.
\item[OUTPUT:] a homomorphism $h^\pr\colon S\to F^\pr$, where $F^\pr\supseteq F$ is a free left regular band, and $h^\pr$ is defined as follows.
\end{enumerate}

Let $C\subseteq F$ be the set of all letters $a\notin h(c)$.
Let $F^\pr$ be the free left regular band generated by $F$ and new free generators
\[
\{t_c^{\emptyset},t_c^{b_1},t_c^{b_2},\ldots,t_c^{b_k}\}.
\]
Let
\[
t_c^\pr=t_c^{\emptyset}t_c^{b_1}t_c^{b_2}\ldots t_c^{b_k},
\]

$H_c=\{s\in S\mid h(s)\mbox{ contains a letter from }  C\}$,
\[
S_{c b_i}=\{s\mid \exists y\geq b_i\; cs=ys\},
\]
\[
S_{c\emptyset}=H_c\setminus \left(\bigcup_{i}S_{\cbf b_i}\right).
\]

First, one should prove the following statement.

\begin{lemma}
\label{l:S_cbf_b_i_do_not_intersect}
For all $i\neq j$ $S_{c b_i}\cap S_{c b_j}=\emptyset$ and $S_{cb_i}\subseteq H_c$.
\end{lemma}
\begin{proof}
Assume $s\in S_{c b_i}\cap S_{c b_j}$. It follows that there exist $y_i,y_j$ such that $b_i\leq y_i$, $b_j\leq y_j$, $cs=y_is$, $cs=y_is$. Therefore, $y_is=y_js$ and $y_i,y_j$ should be $\leq$-comparable. However it is impossible, since $S$ is right hereditary.

Let us prove $S_{cb_i}\subseteq H_c$. Any $s\in S_{cb_i}$ satisfies $h(c)h(s)=h(y)h(s)$ for some $y\geq b_i>c$. If assume $s\notin H_c$ then $h(s)\preceq h(c)\leq h(y)$ and the last equality becomes $h(c)=h(y)$, a contradiction.
\end{proof}

Now we are ready to define a new mapping $h^\pr$ by the following substitutions in images of $h$:
\[
h^\pr(s)=\begin{cases}
h(s),\mbox{ if }s\notin H_c,\\
h(s)|_{a:=at_c^{x}t_c^\pr},\mbox{ for all $a\in C$ if }s\in S_{c x} \; (x\in\{b_1,b_2,\ldots,b_k,\emptyset\})
\end{cases}
\]
After the definition of $h^\pr$ Modification algorithm stops.

\begin{example}
Let us explain the work of Embedding and Modification algorithms at the semigroup $\B^\pr$.

First, we take $c=\eps$. Then $C=\{a_1,a_2\}$, $b_1=x_1$, $b_2=x_2$, $b_3=x_3$, $S_{\eps x_1}=\{x_1,y_1,y_2\}$, $S_{\eps x_2}=\{x_2,y_3\}$, $S_{\eps x_3}=\{x_3\}$, $S_{\eps\emptyset}=\emptyset$.

By the Modification algorithm, we obtain $t_\eps^\pr=t_{\eps}^\emptyset t_{\eps}^{x_1}t_{\eps}^{x_2}t_{\eps}^{x_3}$. Thus, $h^\pr(x_1)=a_1t_{\eps}^{x_1}t_{\eps}^\emptyset t_{\eps}^{x_2}t_{\eps}^{x_3}$,  $h^\pr(x_2)=a_1t_{\eps}^{x_2}t_{\eps}^\emptyset t_{\eps}^{x_1}t_{\eps}^{x_3}$,
\[
h^\pr(x_3)=a_2t_{\eps}^{x_3}t_{\eps}^\emptyset t_{\eps}^{x_1}t_{\eps}^{x_2} a_1t_{\eps}^{x_3}t_{\eps}^\emptyset t_{\eps}^{x_1}t_{\eps}^{x_2}=a_2t_{\eps}^{x_3}t_{\eps}^\emptyset t_{\eps}^{x_1}t_{\eps}^{x_2} a_1,
\]
\[
h^\pr(y_1)=h^\pr(y_2)=a_1t_{\eps}^{x_1}t_{\eps}^\emptyset t_{\eps}^{x_2}t_{\eps}^{x_3}a_2t_{\eps}^{x_1}t_{\eps}^\emptyset t_{\eps}^{x_2}t_{\eps}^{x_3}=
a_1t_{\eps}^{x_1}t_{\eps}^\emptyset t_{\eps}^{x_2}t_{\eps}^{x_3}a_2,
\]
\[
h^\pr(y_3)=a_1t_{\eps}^{x_2}t_{\eps}^\emptyset t_{\eps}^{x_1}t_{\eps}^{x_3}a_2t_{\eps}^{x_2}t_{\eps}^\emptyset t_{\eps}^{x_1}t_{\eps}^{x_3}=a_1t_{\eps}^{x_2}t_{\eps}^\emptyset t_{\eps}^{x_1}t_{\eps}^{x_3}a_2.
\]

We have $\ker(h^\pr)=\{(y_1,y_2)\}$, so one should repeat an iteration of Embedding algorithm. We take $c=x_1$ and obtain $C=a_2$ $b_1=y_1$, $b_2=y_2$, $S_{x_1 y_1}=\{y_1,x_3\}$ (since $x_1x_3=y_1x_3$), $S_{x_1 y_2}=\{y_2\}$, $S_{x_1 \emptyset}=\{y_3\}$.

Modification algorithm now gives: $t_{x_1}^\pr=t_{x_1}^\emptyset t_{x_1}^{y_1}t_{x_1}^{y_2}$, $h^{\pr\pr}(x_1)=h^{\pr}(x_1)$, $h^{\pr\pr}(x_2)=h^{\pr}(x_2)$, $h^{\pr\pr}(x_3)=a_2t_{x_1}^{y_1} t_{x_1}^\emptyset t_{x_1}^{y_2}t_{\eps}^{x_3}t_{\eps}^\emptyset t_{\eps}^{x_1}t_{\eps}^{x_2}a_1$,
$h^{\pr\pr}(y_1)=a_1 t_{\eps}^{x_1}t_{\eps}^\emptyset t_{\eps}^{x_2}t_{\eps}^{x_3} a_2t_{x_1}^{y_1} t_{x_1}^\emptyset t_{x_1}^{y_2}$, $h^{\pr\pr}(y_2)=a_1 t_{\eps}^{x_1}t_{\eps}^\emptyset t_{\eps}^{x_2}t_{\eps}^{x_3} a_2t_{x_1}^{y_2} t_{x_1}^\emptyset t_{x_1}^{y_1}$, $h^{\pr\pr}(y_3)=a_1t_{\eps}^{x_2}t_{\eps}^\emptyset t_{\eps}^{x_1}t_{\eps}^{x_3}a_2 t_{x_1}^\emptyset t_{x_1}^{y_1}t_{x_1}^{y_2}$.

Thus, we obtained an embedding $h^{\pr\pr}\colon S\to\F$ after two iterations of Embedding algorithm.
\end{example}

\begin{lemma}
\label{l:when_equalities_fail}
Let $B=\{b_1,b_2,\ldots,b_k,\emptyset\}$.
\begin{enumerate}
\item Let us consider $x,y\in S$ such that $x\in S_{cd}$ for some $d\in B$. Then
\begin{equation}
h^\pr(x)h^\pr(y)=h(x)|_{a:=at_c^{d}t_c^\pr}h(y),
\label{eq:h_pr_h_pr=hh}
\end{equation}
where $a$ is the first letter of $h(x)$ from the set $C$.

\item Suppose $x,y\in S$ satisfy $h(x)<h(y)$. The inequality $h^\pr(x)<h^\pr(y)$ fails only if
$x\in S_{c d}$, $y\in S_{c e}$ for distinct $e,d\in B$.

\item Suppose $x,y,z\in S$ satisfy $h(x)\sim_{h(z)}h(y)$, $h(x)\leq h(y)$ and $h^\pr(x)\leq h^\pr(y)$. The relation $h^\pr(x)\sim_{h^\pr(z)}h^\pr(y)$ fails only if
$y\in S_{c d}$, $z\in S_{c e}$ for distinct $e,d\in B$ and $x\notin H_c$.
\end{enumerate}
\end{lemma}
\begin{proof}
\begin{enumerate}
\item Let $a^\pr\in C$ be a letter of the word $h(x)h(y)$ which occurs after $a$. By the definition of the map $h^\pr$, the letter $a$ ($a^\pr$) will be replaced to the expression $a^\pr t_c^{d}t_c^\pr$ for some $d\in B$ (respectively, $a^\pr t_c^{e}t_c^\pr$ for some $e\in B$). However the subword $t_c^{e}t_c^\pr$ is eliminated by $t_c^{d}t_c^\pr$ which occurs earlier. Thus, $t$-letters will be occur only after $a$ in $h^\pr(x)h^\pr(y)$ and we immediately obtain~(\ref{eq:h_pr_h_pr=hh}).

\item If $y\notin H_c$ then $x\notin H_c$ (since $h(x)<h(y)$) and $h^\pr(x)=h(x)$, $h^\pr(y)=h(y)$. In this case the inequality $h^\pr(x)<h^\pr(y)$ holds.

Since the case $x\notin H_c$, $y\in H_c$ is impossible, it is sufficient to consider the case $x\in H_c$, i.e. $x\in S_{cd}$ for some $d\in B$. Since $h(x)<h(y)$, we have $y\in H_c$ and $x\in S_{ce}$ for some $e\in B$. If $d=e$ then the inequality $h^\pr(x)<h^\pr(y)$ remains true. Thus, $d\neq e$.

\item If $x\in H_c$ then $x\in S_{cf}$ for some $f\in B$. Since $h^\pr(x)\leq h^\pr(y)$, $y$ belongs to the same set $S_{cf}$. Let $a$ be the first letter from $h(x)$ with $a\in C$ (since $h(x)\leq h(y)$, $a$ is the first letter from $C$ in the word $h(y)=h(x)w$). By~(\ref{eq:h_pr_h_pr=hh}) we have
\[
h^\pr(x)h^\pr(z)=h(x)|_{a:=at_c^{f}t_c^\pr}h(z),
\]
\[
h^\pr(y)h^\pr(z)=h(y)|_{a:=at_c^{f}t_c^\pr}h(z)=h(x)|_{a:=at_c^{f}t_c^\pr}wh(z),
\]
and the equality
\[
h(x)|_{a:=at_c^{f}t_c^\pr}h(z)=h(x)|_{a:=at_c^{f}t_c^\pr}wh(z)
\]
obviously holds, since we have the condition $h(x)h(z)=h(x)wh(z)$.

Thus, below we assume $x\notin H_c$, i.e. $h(x)$ does not contain letters from $C$ and hence $h^\pr(x)=h(x)$. Suppose $y\in H_c$, i.e. $y\in S_{cd}$ for some $d\in B$. We have that the right part of the equality $h(x)h(z)=h(y)h(z)$ contains letters from $C$. Therefore, $h(z)$ should contain a letter from $C$, i.e. $z\in S_{ce}$ for some $e\in B$. Let $a\in C$ ($a^\pr\in C$) be the first letter in the word $h(y)$ (respectively, $h(z)$). By~(\ref{eq:h_pr_h_pr=hh}), we have
\[
h^\pr(y)h^\pr(z)=h(y)|_{a:=a t_c^{d}t_c^\pr}h(z),
\]
\[
h^\pr(x)h^\pr(z)=h(x)h(z)|_{a^\pr:=a^\pr t_c^{e}t_c^\pr}.
\]
It is easy to see that for $d=e$ the equality $h^\pr(x)h^\pr(z)=h^\pr(y)h^\pr(z)$ holds, and we came to the contradiction. Thus, $d\neq e$.

It is sufficient to consider the case $x,y\notin H_c$, i.e. $h^\pr(x)=h(x)$, $h^\pr(y)=h(y)$. If assume $z\notin H_c$ then $h^\pr(z)=h(z)$, and the equality $h^\pr(x)h^\pr(z)=h^\pr(y)h^\pr(z)$ holds. Thus, we put $z\in H_c$, i.e. $z\in S_{ce}$ for some $e\in B$. Therefore,
\[
h^\pr(x)h^\pr(z)=h(x)h(z)|_{a:=a t_c^{e}t_c^\pr},
\]
\[
h^\pr(y)h^\pr(z)=h(y)h(z)|_{a:=a t_c^{e}t_c^\pr}
\]
for some letter $a\in C$ of the word $h(z)$. Obviously, we obtain the equality $h^\pr(x)h^\pr(z)=h^\pr(y)h^\pr(z)$ (since $h(x)h(z)=h(y)h(z)$), a contradiction.
\end{enumerate}
\end{proof}

Let us prove that the map $h^\pr$ defined in Modification procedure is a homomorphism.

\begin{lemma}
If $x<y$ ($x,y\in S$) then
\begin{equation}
h^\pr(x)< h^\pr(y)
\label{eq:h_pr(x)_leq_h_pr(y)}
\end{equation}
\label{l:h_pr_preserves_leq}
\end{lemma}
\begin{proof}
Since $h$ is a homomorphism and $h$ satisfies Lemma~\ref{l:h_preserves_preq}, we have
\begin{equation}
h(x)< h(y)
\end{equation}

According to Lemma~\ref{l:when_equalities_fail}, the relation~(\ref{eq:h_pr(x)_leq_h_pr(y)}) fails only if $x\in S_{c d}$, $y\in S_{c e}$, where $e,d\in\{b_1,b_2,\ldots,b_k,\emptyset\}$ and $e\neq d$.

\begin{enumerate}
\item Let $x\in S_{c b_i}$, i.e. there exists $x^\pr\geq b_i$ such that
\[
cx=x^\pr x.
\]
Let us multiply the last equality by $y$ and obtain $cy=x^\pr y$. Thus, $y\in S_{c b_i}$.

\item Suppose $y\in S_{c b_i}$. There exists $y^\pr\geq b_i$ such that $cy=y^\pr y$. Since $x\leq y$, we have $cxy=y^\pr x y$ and the elements $cx,y^\pr x$ are $\leq$-comparable.

For the inequality $cx\geq y^\pr x$ we have
\[
y^\pr xcx=cx\Leftrightarrow y^\pr x=cx \; (\mbox{we use }y^\pr\geq c)\Rightarrow x\in S_{c b_i}.
\]

The relation $cx\leq y^\pr x$ implies (we use $\al(b_i)=c$ and $y^\pr x\geq b_i$) either $cx=c$ or $cx\geq b_i$. We have:

\begin{enumerate}
\item $cx\geq b_i$, therefore $b_ix=cx$ and $x\in S_{c b_i}$;
\item $cx=c$ ($x\preceq c$), then the word $h(x)$ does not contain any letter from $C$. Hence, $x\notin H_c$ that gives a contradiction with $x\in S_{c d}$ (Lemma~\ref{l:S_cbf_b_i_do_not_intersect} provides $x\in H_c$).
\end{enumerate}
\end{enumerate}
\end{proof}

\begin{lemma}
$h^\pr$ is a homomorphism.
\label{l:h_pr_is_homomorphism}
\end{lemma}
\begin{proof}
Following Lemma~\ref{l:condition_of_hom}, it is sufficient to check that $h^\pr$ preserves the relations $\preceq,\sim_x$.

Actually $h^\pr$ is a substitution of letters in images of $h$. Hence, it obviously preserves $\preceq$-relation. Let us prove
\begin{equation}
h^\pr(x)\sim_{h^\pr(z)} h^\pr(y)
\label{eq:h_prime_preserves_sim}
\end{equation}
if $x\sim_z y$. Below we assume $x\leq y$. Since $h$ is a homomorphism, we have
\begin{equation}
\label{eq:h_equality}
h(x)\sim_{h(z)} h(y),
\end{equation}
where $h(x)\leq h(y)$.

By Lemma~\ref{l:h_pr_preserves_leq}, we have
\begin{equation}
\label{eq:kkkk}
h^\pr(x)\leq h^\pr(y).
\end{equation}

According to Lemma~\ref{l:when_equalities_fail}, the relation~(\ref{eq:h_prime_preserves_sim}) fails only if the word $h(x)$ does not contain letters from $C$, but  $y\in S_{c d}$, $z\in S_{c e}$ for distinct $d,e\in\{\emptyset,b_1,b_2,\ldots,b_k\}$.

By the definition of $C$, we have
\[
x\preceq c.
\]

Suppose $y\in S_{c b_i}$. It follows there exist $y^\pr\geq b_i$ such that $cy=y^\pr y$. Multiplying the last equality by $z$, we obtain
\[
cyz=y^\pr yz.
\]
Applying $x\sim_y z$ and $x\preceq c\leq y^\pr$, we have
\[
cyz=y^\pr yz\Rightarrow cxz=y^\pr xz \Rightarrow cz=y^\pr z.
\]
The last equality states that $z\in S_{c b_i}$ and ~(\ref{eq:h_prime_preserves_sim}) holds.

Suppose now $z\in S_{c b_i}$. There exists $z^\pr\geq b_i$ such that $cz=z^\pr z$. Since $x\preceq c\leq z^\pr$, we have
\[
cz=z^\pr z\Rightarrow cxz=z^\pr xz\Rightarrow cyz=z^\pr yz.
\]
Since $S$ is right hereditary, the elements $cy,z^\pr y$ are $\leq$-comparable.

\begin{enumerate}
\item If $z^\pr y\leq cy$, then (below we use $c\preceq z^\pr$)
\[
z^\pr y\leq cy \Rightarrow z^\pr yc=cy\Rightarrow z^\pr y=cy.
\]
The last equality gives $y\in S_{c b_i}$, and~(\ref{eq:h_prime_preserves_sim}) holds.

\item If $z^\pr y\geq cy$, then (we use $z^\pr y\geq b_i$) either $cy=c$ or $cy\geq b_i$. The first alternative gives $y\preceq c$. It follows that $h(y)$ does not contain new letters $t_c^\emptyset,t_c^{b_1},t_c^{b_2},\ldots,t_c^{b_k}$, and~(\ref{eq:h_prime_preserves_sim}) holds.

Let us put $cy\geq b_i$ then
\[
cy\geq b_i\Leftrightarrow (b_ic)y=cy \Leftrightarrow b_iy=cy\Rightarrow y\in S_{c b_i}
\]
and~(\ref{eq:h_prime_preserves_sim}) holds.

\end{enumerate}

\end{proof}

\begin{lemma}
Let $b_i,b_j\in S$ ($i\neq j$) be elements from Modification procedure. Then the elements $h^\pr(b_i),h^\pr(b_j)$ are not $\leq$-comparable.
\label{l:modification_increasing_kernel}
\end{lemma}
\begin{proof}
Clearly, we have $b_i\in S_{c b_i}$, $b_j\in S_{c b_j}$, and the words $h(b_i),h(b_j)$ are $h(b_i)=h(c)aw_i$, $h(b_j)=h(c)a^\pr w_j$ for some $w_i,w_j\in F$ and some letters $a,a^\pr$ (probably, $a=a^\pr$). The images $h^\pr(b_i), h^\pr(b_j)$ are
\[
h^\pr(b_i)=h(c)at_c^{b_i}t_c^\pr h^\pr(w_i),\; h^\pr(b_j)=h(c)a^\pr t_c^{b_j}t_c^\pr h^\pr(w_j),
\]
and $h^\pr(b_i), h^\pr(b_j)$ have $\leq$-incomparable prefixes $h(c)at_c^{b_i}$, $h(c)at_c^{b_j}$. Thus, the words $h^\pr(b_i), h^\pr(b_j)$ are $\leq$-incomparable.

\end{proof}

By the definition of $h^\pr$ it immediately follows the next statement.

\begin{lemma}
If $h(x),h(y)$ are not $\leq$-comparable, so are $h^\pr(x),h^\pr(y)$.
\label{l:modification_saving_property}
\end{lemma}

By Lemmas~\ref{l:modification_increasing_kernel},~\ref{l:modification_saving_property}, it follows
\begin{equation}
\ker(h)\supset \ker(h^\pr).
\label{eq:ker(h)_supset_ker(h_pr)}
\end{equation}

\bigskip

Let us come back to the definition of Embedding Algorithm.

Let $h_i^\pr$ be the homomorphism defined by the Modification algorithm at $i$-th  iteration of Embedding algorithm. By~(\ref{eq:ker(h)_supset_ker(h_pr)}), we have
\begin{equation}
\ker(h)\supset \ker(h_1^\pr)\supset \ker(h_2^\pr)\supset\ldots
\label{eq:ker(h)_supset_chain}
\end{equation}

Since the left regular band $S$ is finite, the chain~(\ref{eq:ker(h)_supset_chain}) terminates after finite steps.  It means that Embedding algorithm terminates after finite number of iterations.

\begin{lemma}
Let $m$ be the last iteration of Embedding algorithm, then $\ker(h^\pr_m)=\emptyset$, i.e. $h^\pr_m$ is an embedding of $S$ into $F^\pr$.
\end{lemma}
\begin{proof}
Let us take distinct $s_1,s_2$ with $s_1<s_2$. Lemma~\ref{l:h_preserves_preq} gives $h(s_1)<h(s_2)$, and Lemma~\ref{l:h_pr_preserves_leq} provides  $h_m^\pr(s_1)<h^\pr_m(s_2)$ .

Let us take two $\leq$-incomparable elements $s_1,s_2$. Therefore, there exist the maximal element $c$ with $c<s_i$, and distinct $b_1,b_2$ such that $b_i\leq s_i$, $\al(b_i)=c$.

By the termination condition of Embedding algorithm, we have that the words $h^\pr_m(b_1),h^\pr_m(b_2)$ are not $\leq$-comparable. Thus, the words $h^\pr_m(s_1),h^\pr_m(s_2)$ have incomparable prefixes $h^\pr_m(b_1),h^\pr_m(b_2)$, therefore $h^\pr_m(s_1)\neq h^\pr_m(s_2)$.

\end{proof}

\section{Open problems and further research}

\subsection{Algebraic geometry: equations with no constants. How to simplify our proof}

Theorem~\ref{th:main_irred} has a natural application in the study of equations over $\F$. Let us remind main definitions of universal algebraic geometry (for more details see~\cite{uniTh_I,uniTh_II,uniTh_III}).

Let $X=\{x_1,x_2,\ldots,x_n\}$ be a finite set of variables, and $\F(X)$ be the free left regular band generated by the set $X$. The elements of $\F(X)$ are called {\it terms}.

An equality of two terms $t(X)=s(X)$ is called an {\it equation}. For example, the next expressions are equations $x_1x_2=x_2x_1$, $x_1x_2x_3=x_3x_4$.

A set $Y\subseteq \F^n$ is called \textit{algebraic} if there exists a system of equations in variables $X$ with the solution set $Y$. An algebraic set is \textit{irreducible} if it is not a proper finite union of algebraic sets.

For any algebraic set $Y$ one can define a left regular band $\Gamma(Y)$ which is called the \textit{coordinate band} of $Y$ (see~\cite{uniTh_I} for more details). Coordinate bands are analogues of coordinate rings in commutative algebra, so the description of all algebraic sets over $\F$ may be approximated by the description of their coordinate bands.  Notice that any coordinate band $\Gamma(Y)$ is always finitely generated, so all $\Gamma(Y)$ over $\F$ are finite (the variety of left regular bands is locally finite).

In~\cite{margolis2} submonoids of face monoids were studied. However, applying results of~\cite{uniTh_I} to~\cite{margolis2}, one can easily obtain the description of all coordinate bands over $\F$.

\begin{theorem}
\label{th:steinberg}
The following conditions are equivalent for a finite left regular band $S$:
\begin{enumerate}
\item $S$ is a coordinate band of an algebraic set over $\F$;
\item $S\in\qvar(\F)$;
\item $S$ satisfies the formulas $Q_n$ (see~\cite{steinberg});
\item $S$ is embedded into  a direct power of the semigroup $H=\{+,-,0\}$ defined by:
\begin{tabular}{|c||c|c|c|}
\hline
&$+$&$-$&$0$\\
\hline
\hline
$+$&$+$&$+$&$+$\\
\hline
$-$&$-$&$-$&$-$\\
\hline
$0$&$+$&$-$&$0$\\
\hline
\end{tabular}
\end{enumerate}
\label{th:all_for_alg_geom}
\end{theorem}

Actually Theorem~\ref{th:steinberg} was proved in~\cite{margolis2} with the second condition $S\in \qvar(H)$, but one can prove $\qvar(\F)=\qvar(H)$ and obtain the theorem above.

A coordinate band which corresponds to an irreducible algebraic set is called \textit{irreducible}. The study of irreducible coordinate bands is important, since any algebraic set over $\F$ is a finite union of algebraic ones (it follows from the Noetherian property of $\F$, see~\cite{uniTh_I} for details).

Theorem~\ref{th:all_for_alg_geom} describes {\it all} coordinate bands over $\F$, but the class of {\it irreducible} coordinate bands is described by the following theorem.

\begin{theorem}
\label{th:main_for_alg_geom}
The following conditions are equivalent for a finite left regular band $S$:
\begin{enumerate}
\item $S$ is a coordinate band of an irreducible algebraic set over $\F$;
\item $S$ is discriminated by $\F$;
\item $S\in\ucl(\F)$;
\item $S$ is right hereditary and has a local linear order;
\item $S$ is embedded into $\F$.
\end{enumerate}
\end{theorem}
\begin{proof}
The implications $(1)\Leftrightarrow(2)\Leftrightarrow(3)$ follows from the general results of~\cite{uniTh_I}. The implication $(4)\Leftrightarrow(5)$ is the statement of Theorem~\ref{th:main_irred}.

Let us prove $(2)\Rightarrow(5)$. By the definition, a band $S$ {\it is discriminated by} $\F$ if for any finite set $\{s_1,s_2,\ldots,s_n\}\subseteq S$ there exists a homomorphism $h\colon S\to \F$ such that $h(s_i)\neq h(s_j)$ for all $i\neq j$.

Since any finitely generated left regular band is finite,  we have $S=\{s_1,s_2,\ldots,s_n\}$. By the condition, there exists a homomorphism $h\colon S\to\F$ which is injective on $S$, i.e. $h$ is an embedding.

The implication $(5)\Rightarrow(2)$ clearly follows from the definition of the discrimination. Thus, the theorem is proved.
\end{proof}

Let us explain the class $\ucl(\F)$. Let $\varphi$ be a first-order sentence (formula) of the multiplicative language $\LL=\{\cdot\}$. A formula $\varphi$ is \textit{universal} if it is equivalent to
\[
\forall x_1\forall x_2\ldots\forall x_n \varphi^\pr(x_1,x_2,\ldots,x_n),
\]
where $\varphi^\pr$ is quantifier-free.
The {\it universal closure} of $\F$ consists of all left regular bands $S$ such that $S\models\varphi$ for any universal formula $\varphi$ with $\F\models\varphi$.

According to Theorem~\ref{th:main_for_alg_geom}, the embedability of a finite band into $\F$ can be defined by a set of universal formulas. Therefore, the right hereditary and local linear order properties can be written as universal formulas. A universal formula defining the right hereditary property is simple:
\[
\forall x_1,x_2,x_3 (x_1\leq x_3)\&(x_2\leq x_3)\to (x_1\leq x_2\vee x_2\leq x_1).
\]

\begin{problem}
Find a set $\Sigma$ of universal formulas in the language $\LL=\{\cdot\}$ such that the following holds: {\it a finite right hereditary band has a local linear order iff it satisfies $\Sigma$.}
\label{pr:find_Sigma}
\end{problem}

We guess the positive solution of Problem~\ref{pr:find_Sigma} allows to simplify the proof of Theorem~\ref{th:main_irred}. In particular, we will be able to prove it with no the properties of the embedding $\nu$.

\subsection{Algebraic geometry: equations with constants. Advantages of the complicated proof}

The current proof of Theorem~\ref{th:main_irred} is complicated but it has an advantage. In Lemma~\ref{l:h_is_homomorphism} we found a homomorphism $h\colon S\to \F$ with $\s(h(s))=\s(s)$, where $\s(s),\s(h(s))\in\Fbf$. Let us show that this homomorphism property is useful in the study of equations with constants.

Let $X=\{x_1,x_2,\ldots,x_n\}$ be a finite set of variables, and $\F[X]$ be the free left regular band generated by $\F$ and $X$. Elements of $\F[X]$ are called  {\it $\F$-terms}.

An equality of two $\F$-terms $t(X)=s(X)$ is called an {\it $\F$-equation}. For example, the next expressions are $\F$-equations $x_1a_1x_2a_2a_3=a_3x_2a_4a_1x_1a_2$, $x_1x_2a_1x_3a_2a_3=x_3a_4x_4$, $x_1x_2=a_1a_2a_3$.

One can naturally define algebraic sets and coordinate bands for systems of equations with constants. Following~\cite{uniTh_I}, any coordinate band of such algebraic set contains a subband isomorphic to $\F$ (subband of constants), and any homomorphism between coordinate bands $\Gamma_1,\Gamma_2$ should map $\F\subseteq\Gamma_1$ onto $\F\subseteq\Gamma_2$ (constants are mapped into constants).

Thus, we need homomorphisms which act trivially on $\F$. Fortunately, the  homomorphism $h$ has the required property, and we hope $h$ will play a crucial role in the solution of the next problem.

\begin{problem}
Describe coordinate bands of irreducible algebraic sets over $\F$ defined by equations with constants.
\end{problem}

\subsection{``Almost free'' left regular bands}

Following Theorem~\ref{th:main_for_alg_geom}, the universal closure $\ucl(\F)$ consists of right hereditary bands with a local linear order. According to model theory, $\ucl(\F)$ is the ``logical neighbourhood'' of $\F$, i.e. a structure  of each $S\in\ucl(\F)$ is highly close to $\F$. So we formulate

\begin{problem}
Prove theorems about the structure of bands from $\ucl(\F)$ (right hereditary bands with a local linear order) and solve uniformly algorithmic problems (e.g. the word problem) for each band from $\ucl(\F)$.
\end{problem}

\bigskip

We hope this problem should be solved, since we have a similar result in group theory. In~\cite{kh_myas_II} it was proved the analogue of Theorem~\ref{th:main_for_alg_geom} for a free non-abelian group $F$.

\begin{theorem}
The following conditions are equivalent for a finitely generated group $G$:
\begin{enumerate}
\item $G$ is a coordinate group of an irreducible algebraic set over $F$;
\item $G$ is fully residually free;
\item $G\in\ucl(F)$;
\item $G$ is embedded into Lyndon group $F^{\mathbb{Z}[t]}$.
\end{enumerate}
\end{theorem}

There are results about the structure and algorithms for fully residually groups (see~\cite{fully_res_free_I,fully_res_free_II}), and it follows that all groups from $\ucl(F)$ inherits many properties of the free group $F$. Thus, we hope  all semigroups from $\ucl(\F)$ have many nice properties.

\subsection{Approximation with left regular bands}

Many objects (e.g. hyperplane arrangements, matroids) are approximated by left regular bands (see~\cite{brown}). In other words, any hyperplane arrangement $H$ (matroid $M$) admits a multiplication such that $H$  (respectively, $M$) becomes a left regular band. Below we shall talk only about matroids, but one can easily reformulate the following problem for hyperplane arrangements and other objects.

Let $S(M)$ be the left regular band corresponding to a matroid $M$. Following~\cite{brown}, $S(M)$ of a free matroid of rank $n$ is the free left regular band of the same rank. Free matroids have a simple structure (the free matroid $M_n$ of rank $n$ is isomorphic to all subsets of $n$ linearly independent vectors). Thus, it is interesting to describe matroids which are ``almost free''.

\begin{problem}
What can we say about a matroid $M$ with $S(M)\in\ucl(\F)$ (i.e. $S(M)$ is right hereditary with a local linear order)?
\end{problem}

config: arxiv


TITLE: Tracing a non-concentric circle in cylindrical coordinate system
QUESTION [0 upvotes]: I am trying to trace the outline of the circle, at a distance d and with radius r, with the variables rho and phi_max as defined on the diagram.
I tried to convert both coordinate systems to Cartesian and tried to solve for rho and phi_max with the Cartesian equation for the circle with the same origin. $(x-d)^2 + y^2 = r^2 .$
I converted the coordinates as:
$$
\rho \cos(\phi_{max}(\rho)) = x \\
\rho \sin(\phi_{max}(\rho)) = \pm y
$$
ignoring signs because they'll be squared anyway.
I plug these into the circle equation to get:
$$
\rho^2 - 2d\rho\cos(\phi_{max}(\rho)) + (d^2 - r^2) =0 .
$$
I can't solve this equation, it appears that there are 2 variables but only 1 equation to solve for them. I could express $\cos(\phi_{max}(\rho))$ in terms of $\rho$, then use the fact that $\rho$ is bounded ( $[d-r,d+r]$) to solve for each value of $\rho$ and $\arccos(\cos(\phi_{max}(\rho)))$, giving me the sets of values.
However, I am not sure if this would be correct, and more importantly I am concerned that I am missing an easier and more rigorous method.
Note: I am not looking for a singular angle at which the line would be tangent to the circle. $\phi_{max}$ is a function of $\rho$, described at every line that connects to a point on the circle. $\phi_{max}$ is not a maximal angle, it is the name of the variable that I did not change in a different context. Please see the additional image.
Image for clarification

REPLY [1 votes]: I think the only thing you're missing is the distinction between the bounding $\varphi_{\text{max}}$ and the dynamical graphing variables $\rho,\varphi$. You presumably want to get an equation for a function $\rho(\varphi)$ (which really has to be a pair of functions) and you have a good starting point,$$
\rho^2-2\rho d\cos\varphi +d^2 -r^2 = 0
$$(you have an unnecessary extra square, and you are unnecessarily only looking for the maximums).
Instead, by completing the square, we get
$$
(\rho - d\cos\varphi)^2 - (d\cos \varphi)^2 +d^2 -r^2 = 0,\\
\rho(\varphi) = d\cos\varphi\pm \sqrt{r^2 - (d\sin\varphi)^2}
$$the two functions come from $\pm$ and the domain of applicability is clearly where the argument of the square root is nonnegative, $-r/d<\sin\varphi<r/d,$ so $\varphi_{\text{max}}=\sin^{-1}(r/d)$, except that there is no maximum angle if $r>d$.


TITLE: Generating Functions or Counting?
QUESTION [0 upvotes]: Alice has two bags. Each bag has $4$ slips of paper with the numbers $1$ through $4$ on them.
Betty also has two bags, each with $4$ slips of paper with positive integers on them. They decide to play a game whereby each girl pulls a slip from each of her own bags, records the sum of the numbers, then returns each slip to the bag it came from. The numbers in Betty's bags are not $1$ through $4$ in each bag, but the expected distribution of her sums is the same as Alice's. What are all eight numbers in Betty's bags?

Would a way to solve this problem be using generating functions? Counting?

REPLY [4 votes]: Neither. Start by computing the frequency distribution of sums for Alice:
$$\begin{array}{rccc}
\text{sum}:&2&3&4&5&6&7&8\\
\text{frequency}:&1&2&3&4&3&2&1
\end{array}$$
Betty has the same distribution, and the slips of paper in her bags have positive integers written on them.

Show that each of Betty’s bags must contain exactly one slip with the number $1$.
Show that if each of Betty’s bags contained a slip with the number $2$, then her bags would be a copy of Alice’s which is not allowed. Conclude that one of Betty’s bags contains two slips numbered $2$, and the other contains no slips numbered $2$.

At this point we know that one of Betty’s bags contains a $1$ and no $2$s, and the other contains a $1$ and two $2$s, so we have totals of $2,3$, and $3$, and the smallest remaining number in either bag is a $3$.

Show that in order to get the sum $4$ with frequency $3$, we must have two $3$s in one bag and one $3$ in the other. Which bag is which?
Now complete the assignment of numbers to Betty’s bags.

REPLY [2 votes]: Generating functions, I think.
The generating function for Alice’s outcomes is $g(x)=(x+x^2+x^3+x^4)^2$. Can you find polynomials (one for each of Betty’s bags, which have $N$ and $M$ slips in them, respectively) $b_1(x)=\sum\limits_{i=1}^{N}x^{n_i}$ and $b_2(x)=\sum\limits_{i=1}^{M}x^{m_i}$ where $g(x)=b_1(x)\cdot b_2(x)$ and the sets $\{n_i\}_{i=1}^N$ and $\{m_i\}_{i=1}^M$ are sets of positive integers that are different from $\{1,2,3,4\}$?


TITLE: PDE boundary condition question regarding limits
QUESTION [2 upvotes]: Just as a bit of background, I'm working with the Black-Scholes PDE and I'm testing some things out by taking an initial condition for it as $\sin(S/50)$, where $S$ is the spot price (but that's irrelevant to the question).
My issue comes with attempting to find the boundary condition as $S \rightarrow \infty$. Usually the limit of the initial condition is used to find the boundary condition as $S \rightarrow \infty$. In the case with $\sin(S/50)$, what would be an appropriate boundary condition to take? I've already tried taking boundary conditions such as $0$, $\sin(S_{T}/50)$ (where $S_{T}$ is the maximum spot price), and $\sin(S_{t}/50)$ (where $S_{t}$ is the current spot price), but none of these match with the Monte Carlo plot.
I'm fairly certain the Monte Carlo simulation is accurate since it is extremely easy to implement for this function, so I'm pretty sure the issue comes with the PDE simulation. If anyone can help me out with this I would greatly appreciate it, thanks in advance.
EDIT: Perhaps I should note that for the Monte Carlo simulation, I'm basically just taking $\sin(S_{t}/50) / (iterations)$ to find the expectation, where $iterations$ are the number of iterations performed and $S_{t} = \exp((r-0.5\sigma^{2})T + \sigma T N(0,1)$ where $\sigma$ is the volatility, $T$ is the maturity, $r$ is the interest rate, and $N(0,1)$ is the Normal distribution. Could it perhaps be an issue with the Monte Carlo code?

REPLY [0 votes]: Since $\sin$ is $2\pi$-periodic, the only sensible boundary is to take $S_T = 2\pi \cdot 50$. This artificially restricts your domain to a compact interval of spot prices, but we lose no generality since any higher spot price can be simulated by using the corresponding one in the range from $[0,S_T]$.