MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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
up vote 3 down vote accepted

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.

share|cite|improve this answer
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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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