# Existence of a possible counterexample in automaton semigroups

In an attempt to resolve a question posed by Cain in his paper on Automaton Semigroups (open problem 6.12), I would like to know if there exists a finite semigroup $S$ satisfying the following properties:

1. $S$ is self-dual (anti-isomorphic to itself)
2. $S\neq S^2$
3. $S^2$ is a band
4. $S$ has a faithful left-regular representation (i.e.all rows in the Cayley Table of $S$ are distinct)

I'm having no luck constructing one (or proving that one doesn't exist) so any help/suggestions would be greatly appreciated!

-
Semigroups satisfying 3 form a self-dual locally finite variety. Have you tried computing the free object on 2 or 3 generators. It will satisfy 1-3. I am not sure about 4. – Benjamin Steinberg Jun 26 '13 at 0:09
Would you provide the link/reference of Cain's original paper? I can only find the PDF slides on Internet. – scaaahu Jun 26 '13 at 4:17
The reference for Cain's paper is: "Automaton Semigroups", Theoretical Computer Science 410 (2009) no. 47-49, 5022-5038. – Alex McLeman Jun 26 '13 at 9:59
The free object on 2 generators doesn't seem to work unless I made a dumb mistake. – Benjamin Steinberg Jun 26 '13 at 19:33
It should be noted that a band is a semigroup all of whose elements are idempotent. – Benjamin Steinberg Jun 29 '13 at 2:16

I believe I have an example but you should check the details of whether it works. Maybe GAP can be used.

Let $X=\{1,2,3,4,5\}$ and $X'=\{1',2',3',4',5'\}$. Let $a,b\colon X\to X$ be given by $$a=\begin{pmatrix} 1 & 2 & 3& 4 &5\\ 2& 3& 3 &4& 5 \end{pmatrix}\qquad b=\begin{pmatrix} 1 & 2 & 3& 4 &5\\ 4& 5& 4 &4& 5 \end{pmatrix}.$$ Let $T=\langle a,b\rangle$ where we view $a,b$ as functions acting on the right of $X$. Then one checks $a\neq a^2=a^3$, $b^2=b$, $ba=b$ and I suppose these are defining relations.Anyway $T=\{a,a^2,b,ab,a^2b\}$. In particular $T^2$ is a band and $T^2\neq T$. Crucial is that $ab\neq a^2b$.

Let $T'=\langle a',b'\rangle$ be the dual semigroup obtained by reversing the multiplication of $T$. So $a'b'=b'$ and still $a'\neq (a')^2=(a')^3$, $(b')^2=b'$. Also $b'a'\neq b'(a')^2$. We view $T'$ as functions acting on the left of $X'$ in the obvious way (replace $i$ by $i'$ for each $i$ in $X$ to get $a',b'$ from $a$ and $b$). Let $\overline {T}$ be the subsemigroup of $T'\times T$ generated by $(a',a)$ and $(b',b)$. It has $11$ elements and satisfies $\overline{T}^2$ is a band, $\overline{T}^2\neq \overline{T}$ and $\overline{T}$ is self-dual via the obvious involution. $\overline{T}$ almost acts faithfully on the left of itself except that elements of the form $(b'a',t)$ and $(b'(a')^2,t)$ act the same for any $t\in \{b,ab,a^2b\}$.

To remedy that let $R=X'\times X$ with the rectangular band multiplication $(i,j)(k,l)=(i,l)$. Then $S=\overline T\cup R$ is a semigroup using the products in $\overline{T}$ and $R$ already defined and by putting $(u,v)(i,j)=(u(i),j)$ and $(i,j)(u,v)=(i,jv)$ for $u\in T', v\in T$, $i\in X'$ and $j\in X$. So $R$ is the minimal ideal of $S$. Note $S^2$ is a band, $S^2\neq S$ and still $S$ is self-dual (using the obvious involution on $X'\times X$ and the involution on $\overline{T}$).

Because $T'$ acts faithfully on the left of $X'$ we can now distinguish $(b'a',t)$ and $(b'(a')^2,t)$ (with $t$ as above) by the action on the left of $R$. Clearly if $i\neq k$ then $(i,j)$ and $(k,l)$ do not act the same on the left of $R$. On the other hand if $\{j,k\}\neq \{2,3\}$, then $$(i,j)(a',a)=(i,ja)\neq (i,ka)=(i,k)(a',a).$$ On the other hand $$(i,2)(b',b)=(i,5)\neq (i,4)=(i,3)(b',b).$$ Thus the action of $S$ on the left of itself is faithful. Note that $S$ has $36$ elements.

I hope this is correct and helps.

-
Very nice. +1.. – Babak S. Jan 31 '14 at 12:54

Not an answer, but a question based on a previous attempt of finding a solution, for which Benjamin Steinberg pointed out a foolish mistake in the comments below. Is there an "enlarge-and-shrink recipe" to extend a semigroup $\mathbb A = (A, \cdot)$ for which Conditions 1, 3 and 4 hold true to a larger semigroup $(S, \cdot)$ for which Conditions 1, 3 and 4 continue to be true, but in addition $S^2 \ne S$? If the answer is yes, then the problem is solved in the positive: Start with your preferred self-dual band $\mathbb A$, unitize it by adjoining an identity only if $\mathbb A$ is not already unital (in such a way that the unitization is still a self-dual band, but we have a gain in the process, since now the outcome is a semigroup whose regular representations are both faithful, regardless as to whether or not this was already the case with $\mathbb A$), and finally use the enlarge-and-shrink recipe to conclude.

-
e is not a new identity in your table for 1 and e. I think your general construction inflates the adjoined identity and hence e and infinity have the same rows and columns. – Benjamin Steinberg Jun 25 '13 at 23:04
I made a mess with the table, but you are still right: The construction as it is doesn't work. Is there any hope to fix it? – Salvo Tringali Jun 25 '13 at 23:19
Inflation doesn't work. – Benjamin Steinberg Jun 26 '13 at 12:58
I am skeptical of such a recipe but I think I have an answer above, if correct. – Benjamin Steinberg Jun 28 '13 at 17:24