%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-59/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}

\newcommand{\id}[1]{\langle #1 \rangle}

\title{An Interesting Combinatorial Method in the Theory of Locally Finite Semigroups}
\author{T. C. Brown}
\date{}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown}, \emph{An interesting combinatorial method in the theory of locally
  finite semigroups}, Pacific J. Math. \textbf{36} (1971), 285--289.}\bigskip\end{center}

\begin{abstract}
Let $X$ be a finite set, $X^*$ the free semigroup (without identity) on $X$, let $M$ be a finite semigroup, and let $\varphi$ be an epimorphism of $X^*$ upon $M$. We give a simple proof of a combinatorial property of the triple $(X, \varphi, M)$, and exploit this property to get very simple proofs for these two theorems: 1. If $\varphi$ is an epimorphism of the semigroup $S$ upon the locally finite semigroup $T$ such that $\varphi^{-1}(e)$ is a locally finite subsemigroup of $S$ for each idempotent element $e$ of $T$, then $S$ is locally finite. 2. Throughout 1, replace ``locally finite'' by ``locally nilpotent''. 

The method is simple enough, and yet powerful enough, to suggest its applicability in other contexts.
\end{abstract}

\section{Introduction} \label{sec 1}

Theorem~\ref{theorem 1} below was first proved by the author in~\cite{brown1968} by a circuitous and laborious method. In the present paper it drops out easily from Lemma~\ref{lemma 2} below, as does Theorem~\ref{theorem 2}, which is new. Lemma~\ref{lemma 2} was first discovered by J. Justin~\cite{justin1972-2} as a generalization of Lemma~\ref{lemma 1}, which is the author's~\cite{brown1969}. The proof given here, however, is new, and is conceptually quite transparent, though apparently non-trivial. Justin has used Lemma~\ref{lemma 2} in an alternative proof of his generalization of Van der Waerden's theorem (on arithmetic progressions), using Van der Waerden's theorem in the course of the proof. The author is inclined to believe that a refined or more powerful version of Lemma~\ref{lemma 2} would yield a proof of Van der Waerden's theorem itself. 

The construction of a sequence ``in the regular way'', given below, has been formalized by R. Rado in~\cite{rado1949}.

\section{Notation and Definitions} \label{sec 2}

The symbol $X$ will always denote a finite set, and $X^*$ denotes the free semigroup without identity on $X$. Thus $X^*$ is the semigroup of nonempty ``words'' in the ``letters'' of the ``alphabet'' $X$, with juxtaposition as multiplication. If $w = x_1x_2 \cdots x_k \in X^*$, where the $x_i \in X$, then the \emph{length} of $w$, denoted by $|w|$, is $k$. The symbol $X^\omega$ denotes the set of sequences on $X$, regarded as ``infinitely long words'' in the alphabet $X$. If $x,y,z \in X^*$ and $s \in X^\omega$, then $x,y,$ and $z$ are each \emph{factors} ($x$ is a \emph{left factor}) of the word $xyz$ and of the sequence $xyzs$. 

Let $H$ be an infinite subset of $X^*$. We indicate now how to construct a sequence $S = a_1a_2 \cdots \in X^\omega$ such that each left factor of $s$ is a left factor of infinitely many of the words of $H$. Such a sequence is used several times in the proofs that follow, and is said to constructed \emph{in the regular way} from $H$. 

We choose the $a_i$'s inductively. In view of the fact that $H$ is infinite and $X$ is finite, we choose $a_1$ to be an element of $X$ which occurs infinitely often as the first letter in the words of $H$, and we denote by $H_1$ the (infinite) set of those words of $H$ which have $a_1$ as the first letter. Thus $a_1$ is a left factor of infinitely many of the words of $H$. Now suppose that $a_1,\dots,a_n \in X$ have been chosen so that $a_1a_2 \cdots a_n$ is a left factor of each word in an infinite subset $H_n$ of $H$. We choose $a_{n + 1}$ to be an element of $X$ which occurs infinitely often as the $(n + 1)$st letter in the words of $H_n$, and denote by $H_{n + 1}$ the (infinite) set of those words of $H_n$ which have $a_{n + 1}$ as the $(n + 1)$st letter. Thus $a_1a_2 \cdots a_{n + 1}$ is a left factor of infinitely many of the words of $H$.

\section{Two Lemmas} \label{sec 3}

\begin{lemma} \label{lemma 1}
Let $s = a_1a_2 \cdots \in X^\omega$. Then there exist an element $x \in X$ and a fixed integer $\bar{k}$ such that for any $n$ there are integers $i_1 < i_2 < \cdots < i_n$ \emph{(these depend on $n$)} with $x = a_{i_1} = a_{i_2} = \cdots = a_{i_n}$ and $i_{j + 1} - i_j \leq \bar{k}$, $1 \leq j \leq n - 1$.
\end{lemma}

\begin{proof} We proceed by induction on $|X|$, the cardinal of $X$. If $|X| = 1$, we are through. Assume the result for $|X| = k$, and suppose now that $|X| = k + 1$, $X = \{x_1, \dots, x_{k + 1} \}$. Let $s = a_1a_2\cdots \in X^\omega$. If $x_{k + 1}$ is not missing from arbitrarily long factors of $s$ we are done, hence we may assume that there is an infinite set $H$ of factors of $s$ from which $x_{k + 1}$ is missing. Thus $H \subset \{x_1,\dots,x_k\}^*$, and we construct a sequence $t = b_1b_2 \cdots \in \{x_1,\dots,x_k\}^\omega$ from $H$ in the regular way. By the induction hypothesis, there exist an element $x \in \{x_1,\dots,x_k\}$ and an integer $\bar{k}$ such that for any $n$ there are integers $i_1 < i_2 < \cdots < i_n$ with $x = b_{i_1} = b_{i_2} = \cdots = b_{i_n}$ and $i_{j + 1} - i_j \leq \bar{k}$, $1 \leq j \leq n - 1$. But every left factor of $t$ is a left factor of words in $H$, and each word in $H$ is a factor of $s$, therefore every left factor of $t$ is a factor of $s$, and hence every factor of $t$ is a factor of $s$, in particular the factor $b_{i_1} \cdots b_{i_2} \cdots \cdots b_{i_n}$. By a translation of indices (perhaps a different translation for each $n$) we are done.
\end{proof}

\begin{lemma} \label{lemma 2}
Let $\varphi$ be an epimorphism of $X^*$ upon a finite semigroup $M$, and let $s \in X^\omega$. Then there exist an idempotent $e \in M$ and a fixed integer $\bar{k}$ such that for any $n$ there are $n$ consecutive factors $g_1,\dots,g_n$ \emph{(these depend on $n$)} of $s$ \emph{(i.e., $s = ag_1g_2\cdots g_ns'$, where $a, g_1,\dots, g_n \in X^*, s' \in X^\omega$)} with $e = \varphi(g_1) = \varphi(g_2) = \cdots = \varphi(g_n)$ and $|g_j| \leq \bar{k}$, $1 \leq j \leq n$.
\end{lemma}

\begin{proof}
We proceed by induction on $|M|$. If $|M| = 1$, we are done, so now let be $M$ fixed with $M \geq 2$, and assume the result for all semigroups with cardinal smaller than that of $M$. Now with this $M$ we proceed by induction on $|X|$. If $|X| = 1$ we are through, so we may assume the result for $|X| = k$ and now let $|X| = k + 1$.

Let $s = a_1a_2 \cdots \in X^\omega$, and let $x$ be a fixed element of $X$. If $x$ is missing from arbitrarily long factors of $s$, then constructing in the regular way a new sequence from the set of these factors, and arguing as in the proof of Lemma~\ref{lemma 1}, we are done by the induction hypothesis on $|X|$. Thus we may assume that there is an integer $\bar{m}$ and integers $i_1,i_2,\dots$ such that $x = a_{i_1} = a_{i_2} = \cdots$ and $0 < i_{j + 1} - i_j \leq \bar{m}$ for $j = 1,2,\dots$. To simplify the notation, let us assume without loss of generality that $i_1 = 1$.

Next, we take a new (finite) alphabet $B = \{a_{i_j}a_{i_{j} + 1} \cdots a_{i_{j + 1} - 1} : j = 1,2,\dots\}$ and write $s$ as a sequence in $B^\omega$. Let $\varphi(x) = p$. Then $\varphi(a_{i_j}) = p$ for $j = 1,2,\dots,$ so the restriction of $\varphi$ to $B^*$ is an epimorphism of $B^*$ upon the semigroup $pM$. If $|pM| < |M|$, then we are done by the induction hypothesis on $|M|$, since we can easily find our way back to $s$ regarded as a sequence in $X^\omega$. (Indeed, if the length of a factor $g$ of $s$ in the alphabet $B$ is $\leq \bar{k}$, then the length of $g$ in the alphabet $X$ is $\leq \bar{m}\bar{k}$.)

Thus we may assume that $|pM| = |M|$, and similarly that $|Mp| = |M|$ for \emph{all} $p \in M$ (since the fixed element $x$ chosen above was an arbitrary element of $X$). Since $M$ is finite, this amounts to saying that $M$ is a (finite) group.

All we have to do now is to regard $M$ temporarily as a set only, and apply Lemma~\ref{lemma 1} to the sequence $p_1p_2 \cdots \in M^\omega$, where $p_i = \varphi(a_1a_2 \cdots a_i)$, $i = 1,2,\cdots$. Thus there exist an element $p \in M$ and a fixed integer $\bar{k}$ such that for any $n$ there are integers $i_1 < i_2 < \cdots < i_n$ with $p = p_{i_1} = p_{i_2} = \cdots = p_{i_n}$ and $i_{j + 1} - i_j \leq \bar{k}$, $1 \leq j \leq n - 1$. Setting $g_1 = a_1\cdots a_{i_1}$, $g_2 = a_{{i_1} + 1} \cdots a_{i_2}, \cdots, g_n = a_{{i_{n - 1}} + 1} \cdots a_{i_n}$, this says $\varphi(g_1) = \varphi(g_1g_2) = \cdots = \varphi(g_1g_2\cdots g_n)$, and so $e = \varphi(g_2) = \varphi(g_3) = \cdots = \varphi(g_n)$ (where $e$ is the identity of the group $M$), which is the conclusion we seek.
\end{proof}

\section{Two Theorems} \label{sec 4}

\begin{thm} \label{theorem 1}
Let $\varphi$ be an epimorphism of the semigroup $S$ upon the locally finite semigroup $T$ such that $\varphi^{-1}(e)$ is a locally finite subsemigroup of $S$ for each idempotent element $e$ of $T$. Then $S$ is locally finite.
\end{thm}

\begin{proof} 
First we note that it suffices to consider the case where $T$ is finite. For suppose the theorem is true in this case, and let $\varphi$ be an epimorphism (with the required properties) of $S$ onto an arbitrary, that is, possibly infinite, locally finite semigroup $T'$. Let $X$ be a finite subset of $S$, and let $\id{X}$ denote the subsemigroup of $S$ generated by $X$. It is required to show that $\id{X}$ is finite. Now $\id{\varphi(X)} = T$ is a finite subsemigroup of $T'$ since $T'$ is locally finite, hence restricting $\varphi$ to $\varphi^{-1}(T)$ we get an epimorphism (with the required properties) of $\varphi^{-1}(T)$ onto the finite semigroup $T$. By our assumption, $\varphi^{-1}(T)$ is locally finite, hence, since $X \subset \varphi^{-1}(T)$, $\id{X}$ is finite, as required.

Therefore, we assume that $T$ is finite, and we let $X$ denote a finite subset of $S$, $\id{X}$ the subsemigroup of $S$ generated by $X$.

To show that $\id{X}$ is finite, it is convenient to introduce some additional notation. Let $X = \{x_1,\dots,x_m\}$, and let $\bar{X} = \{\bar{x_1}, \dots, \bar{x_m} \}$ be a set. If $\bar{w} = \bar{x_{i_1}}\cdots \bar{x_{i_k}} \in \bar{X}^*$, let $w$ denote the element $x_{i_1} \cdots x_{i_k}$ of $\id{X}$. Thus ``removal of bars'' is a homomorphism of $\bar{X}^*$ upon $\id{X}$. We shall call a word $\bar{w} \in \bar{X}^*$ \emph{contractible} if there is another word $\bar{u} \in \bar{X}^*$ such that $|\bar{u}| < |\bar{w}|$ and $u = w$. A sequence $\bar{s} \in \bar{X}^\omega$ is \emph{contractible} if $\bar{s}$ has a contractible factor. Now $\id{X}$ will be finite provided every sufficiently long word of $\bar{X}^*$ is contractible, and this will be the case provided that every \emph{sequence} in $\bar{X}^\omega$ is contractible; for otherwise we could take an infinite set of noncontractible words of $\bar{X}^*$ and, by then constructing a sequence in the regular way from this set, obtain a non-contractible sequence.

Thus it remains to show that every sequence in $\bar{X}^\omega$ is contractible.

Let $\bar{s} \in \bar{X}^\omega$, and define the homomorphism $\bar{\varphi}$ from $\bar{X}^*$ into $T$ by setting $\bar{\varphi}(\bar{w}) = \varphi(w)$ for $\bar{w} \in \bar{X}^*$. Applying Lemma~\ref{lemma 2}, we obtain an idempotent $e \in T$ and a fixed integer $\bar{k}$ such that for \emph{any $n$} there are $n$ consecutive factors $\bar{g_1},\dots,\bar{g_n}$ of $\bar{s}$ with $e = \bar{\varphi}(\bar{g_1}) = \bar{\varphi}(\bar{g_2}) = \cdots = \bar{\varphi}(\bar{g_n})$ and $|\bar{g_j}| \leq \bar{k}$, $1 \leq j \leq n$. By the definition of $\bar{\varphi}$, we have $g_1,\dots,g_n$ all in $\varphi^{-1}(e)$, which is locally finite by assumption. Since $|\bar{g_j}| \leq \bar{k}$ there are only finitely many possibilities for the elements $g_1,\dots,g_n$, hence the element $g_1\cdots g_n$ always belongs to a certain fixed finite subsemigroup of $\varphi^{-1}(e)$, no matter how large $n$ is. Thus if $n$ is taken sufficiently large, the factor $\bar{g_1}\cdots \bar{g_n}$ of $\bar{s}$ will be contractible. Thus the sequence $\bar{s}$ is contractible. This completes the proof.
\end{proof}

\begin{thm} \label{theorem 2}
Let $\varphi$ be an epimorphism of the semigroup $S$ upon the locally nilpotent semigroup $T$ such that $\varphi^{-1}(e)$ is a locally nilpotent subsemigroup of $S$ for each idempotent element $e$ of $T$. Then $S$ is locally nilpotent.
\end{thm}

\begin{proof}
The proof of Theorem~\ref{theorem 2} is practically the same as the proof of Theorem~\ref{theorem 1}. Here instead of showing that every sequence $\bar{s}$ in $\bar{X}^\omega$ (same notation as in the proof of Theorem~\ref{theorem 1}) has a contractible factor, one shows that every sequence $\bar{s}$ has a factor $\bar{w}$ with $w = 0$.
\end{proof}


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