%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-36/document.tex.
%%%%
%% Standard package list
\documentclass[letterpaper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage[top=3cm, bottom=3cm, left=3.5cm, right=3.5cm]{geometry}
\usepackage[onehalfspacing]{setspace}
\usepackage{amsmath,amssymb,amsthm,wasysym}
\usepackage{nicefrac,booktabs}
\usepackage{mathptmx}
\usepackage{cite}
\usepackage[colorlinks=true]{hyperref}

%% Various helpers for Tom's papers
\newcommand{\gs}{\textnormal{gs}}
\newcommand{\ord}{\textnormal{ord}}
\newcommand{\Exp}{\textnormal{Exp}}
\newcommand{\Log}{\textnormal{Log}}
\newcommand{\lcm}{\textnormal{lcm}}
\newcommand{\range}{\textnormal{range}}
\newcommand{\NR}{\textnormal{NR}}
\newcommand{\Mod}[1]{\left(\textnormal{mod}~#1\right)}

\newcommand{\ap}[2]{\left\langle #1;#2 \right\rangle}
\newcommand{\summ}[1]{\sum_{k=1}^m{#1}}
\newcommand{\bt}[1]{{{#1}\mathbb{N}}}
\newcommand{\fp}[1]{{\left\lbrace{#1}\right\rbrace}}
\newcommand{\intv}[1]{{\left[1,{#1}\right]}}


%% Lifted from http://stackoverflow.com/questions/2767389/referencing-a-theorem-like-environment-by-its-name
%% This lets me do things like "Theorem A" and have the references work properly.
\makeatletter
\let\@old@begintheorem=\@begintheorem
\def\@begintheorem#1#2[#3]{%
  \gdef\@thm@name{#3}%
  \@old@begintheorem{#1}{#2}[#3]%
}
\def\namedthmlabel#1{\begingroup
   \edef\@currentlabel{\@thm@name}%
   \label{#1}\endgroup
}
\makeatother
% end lift

\newtheoremstyle{namedthrm}
  {}{}{}{}{}{}{ }  % This last space needs to be there
  {\bf\thmname{#1} \thmnote{#3}.}
%% End reference hack


%% Document start
\date{}
\begin{document}

%% Content start


\newtheorem*{cor}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{thm}{Theorem}
\newtheorem*{prop}{Proposition}
\newtheorem{q}{Problem}
\theoremstyle{definition}
\newtheorem*{defn}{Definition}
\newtheorem*{notation}{Notation}
\newtheorem{remark}{Remark}

\title{Cancellation in Semigroups in Which $x^2 = x^3$}
\author{Tom C. Brown \\ Communicated by G. Lallement}
\date{}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown}, \emph{Cancellation in semigroups in which $x^2 = x^3$}, Semigroup
  Forum \textbf{41} (1990), 49--53.}\bigskip\end{center}

\section{Introduction} \label{sec 1}
Let $B(k,m,n)$ denote the semigroup generated by $k$ elements and satisfying the identity $x^m = x^n$, where $0 \leq m < n$. That is, $B(k,m,n)$ is the free semigroup on $k$ generators in the variety of semigroups defined by the law $x^m = x^n$ (we are following the notation of Lallement~\cite{lallement1979}).

Green and Rees~\cite{green+rees1952} showed that for each $n \geq 1$, the semigroups $B(k,1,n)$ are finite for all $k \geq 1$ if and only if the groups $B(k,0,n-1)$ are finite for all $k \geq 1$. Thus in particular all semigroups in which $x = x^2$ are locally finite, and so are all semigroups in which $x = x^3$. The word problem for semigroups in which $x = x^3$ was solved by Gerhard~\cite{gerhard1978}.

The existence of an infinite sequence on $3$ symbols in which there are no two consecutive indentical blocks shows that $B(3,2,3)$ is infinite, since the left factors of such a sequence will all be distinct modulo the law $x^2 = x^3$. This was first observed by Morse and Hedlund~\cite{morse+hedlund1944}, who constructed such a sequence. An earlier construction of such a sequence was given by Thue~\cite{thue1912}, and other constructions appear in Dean~\cite{dean1965}, Dejean~\cite{dejean1972}, and Leech~\cite{leech1957}.

It is much more difficult to show that $B(2,2,3)$ is infinite. This was done by Brzozowski, Culik II, and Gabrielian~\cite{brzozowski+culik+gabrielian1971}, and is also described in Lallement~\cite{lallement1979}. It follows that $B(k,m,n)$ is infinite for all $k \geq 2$, $n>m \geq 2$, since $B(k,2,3)$ is a quotient of $B(k,m,n)$. 

It was shown in~\cite{brown1967} that $S = B(k,2,3)$ is the disjoint union of locally finite subsemigroups. Specifically, for each idempotent $e = e^2$ in $S$, let $S_e = \{x \in S: x^2 = e\}$. Then $S$ is the union of the locally finite subsemigroups $S_e$.

It has been asserted~\cite{shevrin1967} that each $S_e$ is in fact a \emph{finite} subsemigroup of $S$. As far as the author knows, no proof of this assertion has been published. One possible approach of such a proof would be to show that if $x$ is any element of $S$ and $g$ is any generator of $S$, no too much 'cancellation' can occur in the product $gx$.

To make this precise, for each $x$ in $S$ let $|x|$ denote the \emph{length} of $x$, that is, the smallest integer $p$ such that $x$ can be written as the product of $p$ (not necessarily distinct) generators of $S$.

Then if there exists a constant $c>0$ such that $|gx| \geq c|x|$ for every generator $g$ of $S$ and every element $x$ of $S$, it would follow that $S_e$ is finite, for if $|e| = t$ and $x \in S_e$, then $e = ex$, so $t = |ex| \geq c^t|x|$, which bounds the length of $x$.

What could be the largest possible numerical value of such a constant $c$? This is the subject of the present note.

\section{An Upper Bound for the Constant $c$} \label{sec 2}

Since the value of $c$ depends on $k$, the number of generators of $S$, we make the following definition.

\begin{defn} Let $g_1,g_2, \dots, g_k, \dots,$ be a sequence so that for each $k \geq 1$, $g_1,g_2,\dots,g_k$ is a set of generators for the semigroup $B_k = B(k,2,3)$, and let $B_\omega = B_1 \cup B_2 \cup \cdots$. For each $k \geq 1$, let $c_k$ be the largest real number such that for all $x \in B_k$ and all $i$, $ 1 \leq i \leq k$, $|g_ix| \geq c_k|x|$. Similarly, let $c_\omega$ be the largest real number such that for all $x \in B_\omega$ and all $i \geq 1$, $|g_ix| \geq c_\omega|x|$.
\end{defn}

Note that if $C_k$ is the set of all real numbers $c$ such that $|g_ix| \geq c|x|$ for $ 1 \leq i \leq k$ and $x \in B_k$, then $c_k = \sup C_k = \max C_k$.

Since $2 = |g_1(g_1)^2| \geq c_1|(g_1)^2| = 2c_1$, we have $1 = c_1$, and since $B_\omega \supseteq B_{k + 1} \supseteq B_k$, we have $c_k \geq c_{k + 1} \geq c_{\omega}$, so that 
\[ 1 = c_1 \geq c_2 \geq \cdots \geq c_k \geq c_{k + 1} \geq \cdots \geq c_\omega \geq 0. \]

It is easy to see that $2/3 \geq c_\omega$. For let $A = g_2g_3\cdots g_p$ nd $x = Ag_1Ag_1A$. Then $|x| = 3p - 1$ and $|g_1x| = |g_1Ag_1A| = 2p$, so that for all $p \geq 2$, 
\[ \left( \frac{2}{3} + \frac{2}{9p - 3} \right)|x| = |g_1x| \geq c_\omega |x|. \]

We will improve the bound of $2/3$ to $(\sqrt{5} - 1)/2 \approx .618$ by finding, for each $\varepsilon > 0$, elements $x,y$ in $B_\omega$ so that 
\[ |g_1xy^2| \leq \left( \frac{\sqrt{5} - 1}{2} + \varepsilon \right)|xy^2|. \]
For this we need the following two lemmas.

\begin{lemma} \label{lemma 1}
Let $a,b,c \in B_\omega$, where the generator $g_1$ does not occur in any of $a,b,c$. Then $|ag_1bg_1| = |a| + |b| + 2$, and (unless $a = b = c$) $|ag_1bg_1cg_1| = |a| + |b| + |c| + 3$.
\end{lemma}

\begin{proof}
For \emph{words} $X,Y$ in the \emph{alphabet} $\{g_1,g_2,g_3, \dots\}$, let us say that $X$ is \emph{equivalent} to $Y$, and write $X \approx Y$, in case $X$ can be transformed into $Y$ by means of a finite sequence of 'expansions' $UW^2V \to UW^3V$ and 'contractions' $UW^3V \to UW^2V$, where $U,W,V$ are any words, possibly empty.

To prove the first equality of the lemma, suppose that $Ag_1Bg_1C = X \approx Y = Eg_1Fg_1G$, where the letter $g_1$ does not occur in any of the words $A,B,E,F$. (At this point we need not assume that $g_1$ does not occur in $C$ or $G$; reading $X$ from left to right, the word $A$ is the segment of $X$ which precedes the first occurrence of $g_1$, and the words $B,E,F$ are similarly characterized.) We will show that $A \approx E$ and $B \approx F$. It suffices to consider the case where $X = Ag_1Bg_1C = UW^2V, UW^3V = Eg_1Fg_1G = Y$. By considering the several possible locations of $W^2$ in $X$ (and noting that $W^2$ contains at least two $g_1$s if it contains one), one sees easily that $A \approx E$ and $B \approx F$. The fact that $|ag_1bg_1| = |a| + |b| + 2$ now follows easily.

For the second equality of the lemma, we need to use also that 'right-handed' version of the preceding, namely that if $Ag_1Bg_1C \approx Eg_1Fg_1G$, where the letter $g_1$ does not occur in any of the words $B,C,F,G$, then $B \approx F$ and $C \approx G$. Then, if the shortest product of generators which equals $ag_1bg_1cg_1$ contains at least three $g_1$s, it contains only three $g_1$s, and $|ag_1bg_1cg_1| = |a| + |b| + |c| + 3$. If the shortest such product contains only two $g_1$s, then it is not hard to see that $a = b = c$.
\end{proof}

\begin{lemma} \label{lemma 2}
Define elements $x_n,y_n$ in $B_\omega$ for all $n \geq 2$ inductively as follows. Let $x_2 = g_2$, $y_2 = g_1g_2$. For $n \geq 2$, let $x_{n + 1} = x_ny_ng_{n + 1}$, $y_{n + 1} = x_ny_n^2g_{n + 1}$. Then for $n \geq 2$, $|g_1x_{n + 1}y_{n + 1}| = |g_1x_ny_n| + |x_ny_n^2| + 2$ and $|x_{n + 1}y_{n + 1}^2| = |x_ny_n| + 2|x_ny_n^2| + 3$.
\end{lemma}

\begin{proof}
This follows from Lemma~\ref{lemma 1}, with the $g_{n + 1}$ in Lemma~\ref{lemma 2} playing the role of $g_1$ in Lemma~\ref{lemma 1}. One needs to know that $x_{n + 1} \ne y_{n + 1}$. But if $x_{n + 1} = y_{n + 1}$, then $x_ny_n = x_ny_n^2$, and this implies (by Lemma~\ref{lemma 1}) that $x_{n - 1}y_{n - 1} = x_{n - 1}y_{n - 1}^2$.
\end{proof}

\begin{prop} \label{prop 1}
Let $\tau$ denote the golden mean, $\tau = (1 + \sqrt{5})/2 \approx 1.618$. Then $\tau - 1 \geq c_\omega$.
\end{prop}

\begin{proof}
In our calculation, we will make use of the Fibonacci numbers $F_n$, where $F_0 = F_1 = 1$ and $F_{n + 2} = F_{n + 1} + F_n$, and the fact that $F_n/F_{n + 1}$ converges to $1/\tau$.

For $n \geq 2$, let $x_n,y_n$ be defined as in Lemma~\ref{lemma 2}. Then by induction it follows that for all $n \geq 2$, $g_1x_ny_n^2 = g_1x_ny_n$. By Lemma~\ref{lemma 2} and induction it follows that for all $n \geq 2$, $|g_1x_ny_n| = F_{2n - 3} + F_{2n - 1}$, $|x_ny_n^2| = F_{2n - 2} + F_{2n} - 2$.

Then for all $n \geq 2$,
\[ c_\omega \leq \frac{|g_1x_ny_n^2|}{|x_ny_n^2|} = \frac{|g_1x_ny_n|}{|x_ny_n^2|} = \frac{ F_{2n - 3} + F_{2n - 1}}{F_{2n - 2} + F_{2n} - 2} \to 1/\tau = \tau - 1, \]
and it follows that $c_\omega \leq \tau - 1$.
\end{proof}

\section{An Open Question} \label{sec 3}

It would be interesting to know the exact values of $c_2$ and $c_\omega$, and inparticular whether $c_2 >0$, and whether $c_\omega > 0$.



\bibliographystyle{amsplain}
\bibliography{tom-all}
\end{document}