%%%% 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}