# Are semigroups with finite-to-one right multiplication “moving”?

A semigroup $S$ is moving if $S$ is infinite, and for all finite $F\subseteq S$ and infinite $A\subseteq S$, there are $a_{1},\dots,a_{k}\in A$ such that, for all but finitely many $s\in S$, $$\{a_{1}s,\dots,a_{k}s\} \nsubseteq F.$$ A function $f\colon X\to Y$ is finite to one if for each $y\in Y$, the set $\{x\in X : f(x)=y\}$ of preimages of $y$ is finite.

The following implications hold among the properties listed below: $$(1)\Rightarrow(2)\Rightarrow(4)\Rightarrow(5); (1)\Rightarrow(3)\Rightarrow(5).$$ (1) $S$ is a group.

(2) $S$ is left cancellative: for all $a,b,c\in S$, if $ca=cb$ then $a=b$.

(3) $S$ is right cancellative: for all $a,b,c\in S$, if $ac=bc$ then $a=b$.

(4) Left multiplication in $S$ is finite-to-one: for all $a\in S$, the function $x\mapsto ax$ is finite-to-one.

(5) $S$ is moving.

Question. Let $S$ be a smigroup such that right multiplication in $S$ is finite-to-one (that is, for all $a\in S$, the function $x\mapsto xa$ is finite-to-one). Is $S$ necessarily moving?

Remarks: Moving semigroups are interesting since a genrealization of Hindman's Finite Sums coloring theorem applies to them. This is so because a semigroup $S$ is moving if and only if the Stone-Cech remainder $\beta S\setminus S$ is a subsemigroup of $\beta S$.

Theorem. Let $S$ be a moving semigroup. For each coloring of the elements of $S$ in finitely many colors, there are distinct elements $a_{1},a_{2},\dots\in S$ such that all products $a_{i_1}a_{i_2}\cdots a_{i_n}$ with $i_1<i_2<\cdots<i_n$ ($n$ arbitrary) have the same color.

Update: Shevrin's classification of semigroups (On the theory of periodic semigroups, Izvestija Vys\v{s}ih U\v{c}ebnyh Zavedeni\u{\i} Matematika, 1974) implies that, if right multiplication in $S$ is finite-to-one, then $S$ has a moving subsemigroup. It follows that the above coloring theorem holds true for semigroups with finite-to-one right multiplication.

• I suppose right cancellative can be replaced by a uniform bound on the degree of finite-to-oneness. – Benjamin Steinberg Apr 23 '14 at 10:34
• Just checking that I follow the intent of the question: if we remove "distinct" from the statement of the Finite Products theorem then (I believe) it remains true in an arbitrary semigroup. Is the point that you can get "distinct" by cutting $S$ out of $\beta S$, ensuring that your idempotent is non-principal? – Ben Barber Apr 23 '14 at 15:30
• @BenjaminSteinberg: Of course. – Boaz Tsaban Apr 23 '14 at 20:21
• @BenBarber: Exactly. And otherwise the theorem becomes nonsense: If there is an idempotent $e$ in $S$, then taking all $a_i$ to be $e$, all products are equal to $e$ (!), so it is not interesting to know that they all have the same color (being the same element)... – Boaz Tsaban Apr 23 '14 at 20:25

The answer is no. Here is a monoid where right multiplication is finite-to-one but is not moving.

Let $M$ be the monoid with presentation

$\langle t,x_0,x_1,\ldots,\mid x_0t=x_0,x_it=x_{i-1}, i>0\rangle$.

Then each element of $M$ can be written uniquely in the form $t^nw$ with $n\geq 0$ and $w$ a word over the $x_i$ possibly empty. It is easy to check multiplication on the right is finite-to-one. Each $x_i$ acts injectively on the right. The element $t$ is at most two-to-one: $t^nw$ has 2 preimages under right multiplication by $t$ iff $w$ ends in $x_0$. Compositions of finite-to-one maps are finite-to-one giving the general case.

Take $F=\{x_0\}$ and $A=\{x_0,x_1,\ldots\}$. Then infinitely many powers of $t$ right multiply any finite subset of $A$ into $F$. So $M$ is not moving.

Added May 2, 2014. A finitely generated counterexample is the monoid $N$ with presentation

$\langle a,b,t\mid at=a,ab^nt=ab^{n-1}, n>1\rangle$

If you set $x_i=ab^i$, then the $x_i$ and $t$ generate a submonoid isomorphic to $M$ above and hence $N$ is not moving. Since this presentation is Church-Rosser it is easy to check that right multiplication by $a,b$ is injective and right multiplication by $t$ is at most 2-to-1. The normal forms are words of the form $u$ and $uw$ where $u$ is a word in $b,t$ and $w$ is a word in $a,b$ with at least one $a$.

• Excellent, thanks! So we are in a good situation: We known that the answer is negative, and we know how to still get the Ramsey theoretic theorem. Much apprecited. The bounty is yours. :) – Boaz Tsaban Apr 28 '14 at 11:51