%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-64/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{q}{Problem}
\theoremstyle{definition}
\newtheorem*{defn}{Definition}
\newtheorem*{notation}{Notation}
\newtheorem{remark}{Remark}

\title{On the Finiteness of Semigroups in Which $x^r = x$}
\author{Thomas C. Brown \\ Communicated by P. Hall}
\date{}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown}, \emph{On the finiteness of semigroups in which $x^r = r$}, Proc.
  Cambridge Philos. Soc. \textbf{60} (1964), 1028--1029.}\bigskip\end{center}

In this note we present a new proof of the following theorem (see~\cite{green+rees1952}).

\begin{thm} \label{theorem 1}
For each $r$, $r \geq 2$, every finitely generated semigroup in which $x^r = x$ holds identically is finite if and only if every finitely generated group of exponent $r - 1$ is finite.
\end{thm}

\begin{notation} 
Throughout, $r$ is fixed and $S_k$ denotes a semigroup on $k$ generators in which $x^r = x$. The elements of $S_k$ are regarded as equivalence classes of words in $k$ symbols $X_1, \dots, X_k$. Upper case letters will denote words, and lower case letters the elements of the semigroup $S_k$; thus if the word $W$ represents the element $w$ of $S_k$, we write $W \in w \in S_k$, and also say that $W$ is a word of $S_k$. $W = W'$ signifies that $W$ and $W'$ are identical, while $W \sim W'$ signifies that $W$ and $W'$ are equivalent, i.e., represent the same element of $S_k$. If $W$ is a word of $S_k$, we write $|W|$ for the \emph{length} of $W$ in the symbols $X_i$; e.g., $|X_1X_2X_3| = 3$. If each $X_i$ appears in $W$, $1 \leq i \leq k$, we say that $W$ is a \emph{complete} word of $S_k$; any word $W$ is \emph{minimal} if $W \sim W'$ implies $|W| \leq |W'|$.
\end{notation}

\begin{remark} \label{remark 1}
Clearly $S_k$ is finite if and only if the lengths of minimal words of $S_k$ are bounded from above.
\end{remark}

\begin{lemma} \label{lemma 1}
$W \sim AXB$ implies $W \sim W(XW)^{r -1}.$
\end{lemma}

\begin{proof}
\[ W(XW)^{r - 1} \sim AXB(XAXB)^{r - 1} \sim (AX)^{r - 2} A[XAXB(XAXB)^{r - 1}] \sim AXB \sim W. \qedhere \]
\end{proof}

\begin{lemma} \label{lemma 2}
Let $T$ be a complete word of $S_k$. Then for any word $X$ of $S_k$, $T \sim T(XT)^{r - 1}$.
\end{lemma}

\begin{proof}
By Lemma~\ref{lemma 1} we need only show that $T \sim AXB$ for some $A,B$. We show by induction on $|X|$ that $T \sim TXB$ for a suitable $B$. If $|X| = 0$, i.e., $X$ is the empty word, we may take $B = X$. Now let $X = X_0X_i$, where $|X_0| = n$, and suppose $T \sim TX_0B_0$. Since $T$ is complete we have $T = T'X_iT''$, and hence
\begin{align*} 
T \sim T'(X_iT''X_0)B_0 &\sim (T'X_iT''X_0X_i)T''X_0(X_iT''X_0)^{r - 2}B_0 \\
&=TX[T''X_0(X_iT''X_0)^{r - 2}B_0]. \qedhere
\end{align*}
\end{proof}

\begin{lemma} \label{lemma 3}
Let $T \in t \in S_k$, where $T$ is complete. Then the set $tS_kt$ is a group.
\end{lemma}

\begin{proof}
$tS_kt$ is a semigroup with identity $t^{r - 1}$, and the inverse of $txt$ is $(txt)^{r - 2}$. (For by Lemma~\ref{lemma 2} we have $t(xt)^{r - 1} = t$; hence $(txt)^{r - 1} = t(xtt)^{r - 2}xt = t(xtt)^{r - 1}t^{r - 2} = t^{r - 1}$.)
\end{proof}

\begin{proof}[Proof of Theorem]
One direction is trivial. For the other, we use induction on $k$; $S_1$ is obviously finite, and we suppose that $S_{k - 1}$ is finite. By Remark~\ref{remark 1}, there is a number $m$ such that if $|X| = m$, where $X$ is a minimal word of $S_k$, then $X$ is complete in the $k$ symbols $X_1,\dots,X_k$.

Let $W$ be any minimal word of $S_k$; then $W$ can be written in the form 
\begin{equation}
W = W_1W_2 \cdots W_NW', \label{eq 1} 
\end{equation}
where
\[ |W_j| = m \quad (1 \leq i \leq N), \: |W'| < m. \]
Since $W$ is minimal, each $W_j$ is minimal and hence complete. Let $T \in t \in S_k$, where $T$ is complete. Then for each $j$, $W_j \sim W_j(T^2W_j)^{r - 1}$; and making this substitution into (1) for each $j$, we obtain
\begin{equation} 
W \sim W_1[T(TW_1T)^{r - 2}(TW_1W_2T)(TW_2T)^{r - 2} \cdots (TW_NT)^{r - 2}T] W_N W'. 
\end{equation}
Now let $G$ be the subgroup of $tS_kt$ generated by all those elements with representatives of the form $TXT$, where $|X| \leq 2m$. Since $G$ is finitely generated and of exponent $r - 1$, $G$ is finite by assumption; hence every element of $G$ has a representative word whose length does not exceed some number $M$. Thus by (2), $W \sim W_1YW_NW'$, where $|Y| \leq M$, and by the minimality of $W$, $|W| \leq M + 3m$. Finally, since $M$ did not depend on the particular choice of $W$, $S_k$ is finite, and the proof is complete.
\end{proof}


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