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.

  • $\begingroup$ I suppose right cancellative can be replaced by a uniform bound on the degree of finite-to-oneness. $\endgroup$ – Benjamin Steinberg Apr 23 '14 at 10:34
  • $\begingroup$ 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? $\endgroup$ – Ben Barber Apr 23 '14 at 15:30
  • $\begingroup$ @BenjaminSteinberg: Of course. $\endgroup$ – Boaz Tsaban Apr 23 '14 at 20:21
  • 1
    $\begingroup$ @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)... $\endgroup$ – 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$.

  • $\begingroup$ 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. :) $\endgroup$ – Boaz Tsaban Apr 28 '14 at 11:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.