# Quasicommutative semigroups.

A Semigroup is called quasicommutative if for all elements $a,b$ there is some $r≥1$ such that $$ab=b^ra$$

We know that every commutative semigroup is also quasicommutative, so we can make lots of examples for quasicommutative semigroups by regarding a commutative one. But I am looking for a non-commutative, finite quasicommutative semigroup. In fact, I am searching for a sample of such to see this structure work. Any help would be appreciated.

-
Nice question! + – amWhy Feb 7 '13 at 0:05

I have not yet found a non-group example, but the quaternion group $Q$ of order $8$ satisfies $b^{3}a = ab$, whenever $ba \neq ab$, for $a,b\in Q$. I checked this in Maple, but you could easily check it in GAP as well.

Furthermore (assuming that I haven't made a programming error), this is the smallest non-commutative example. Using the Magma package in Maple, I checked the semigroups of order less than $8$ and did not find any non-commutative examples. (I seem to recall there is a library of small semigroups in GAP, so you could double-check my calculations there too.)

For a finite group $G$, your conditions are equivalent to $G$ being Hamiltonian; that is, non-abelian but having all subgroups normal since, for $a$ and $b$ in $G$, we have $ab = b^{r}a$, for some $r\geq 1$ if, and only if, $aba^{-1}\in\langle b\rangle$. The quaternion group $Q$ of order $8$ is the smallest Hamiltonian group. (It follows that there are no smaller group examples.) Checking that $r\in \{1,3\}$ works is straight-forward in Maple:

with( group ):
Q := permgroup( 8, { [[1, 2, 3, 4], [5, 6, 8, 7]],  [[1, 5, 3, 8], [2, 7, 4, 6]] } ):
E := elements( Q ):
for a in E do
for b in E do
u := mulperms( a, b );
v := mulperms( b, a );
if u <> v then
v := mulperms( b, mulperms( b, v ) );
if u <> v then
print( a, b )
end if
end if
end do
end do:


To check the semigroups of order less than $8$, I used the Magma package in Maple, together with the following routine to check whether a semigroup given by its Cayley table is quasi-commutative.

QuasiComm? := proc( s::Array(order=C_order, datatype=integer[4]), n::posint )
description "check whether a semigroup given by its Cayley table is quasi-commutative";
option autocompile;
local i, j, u, found, r;
for i from 1 to n do
for j from 1 to n do
found := false;
u := j;
for r from 1 to n + 1 do
if s[ u, i ] = s[ i, j ] then
found := true;
#print(i,j,r);
break
end if;
u := s[ u, j ]; # u = j^(r+1)
end do;
return false
end if
end do
end do;
true
end proc:


This procedure takes a semigroup $s$ given by its Cayley table as first argument, along with the order $n$. It uses the fact that we need only check values of $r$ in $\{ 1, 2, \ldots, n\}$, for a semigroup of order $n$, because the sequence $b, b^{2}, b^{3},\ldots, b^{n}$ must eventually end up in a cycle. I supplied sufficient type information to enable the procedure to be compiled to machine code (option autocompile), since it will be called many, many times.

To run the test, I just used the Enumerate command in the Magma package, as follows:

N := 2: L := Enumerate( N, semigroup, output = list ): select( QuasiComm?, remove( IsCommutative, L ), N );
N := 3: L := Enumerate( N, semigroup, output = list ): select( QuasiComm?, remove( IsCommutative, L ), N );


and so on, up to $N = 7$. The output in each case was the empty list.

I'm trying a slight refinement of this approach to see if I can find any non-group examples of order $8$, but I'm not certain the computation is doable. (I'm going to run it overnight and see if it gets anywhere.) Order $9$ is probably not approachable this way; according to very recent (2013/01/25) work of Distler and Kelsey, the number of semigroups of order $9$ (up to isomorphism) is $105978177936292$.

It seems that the quaternion group of order $8$ is the only example of that order. To check this, I had to modify the predicate for use with the test option of the Enumerate command. Although I doubt Magma:-Enumerate could list all the semigroups of order $8$ (in principle, it can, but would likely take a very long time), the modified predicate can be used to prune the search tree. I wasn't sure even this would complete, but it did. The modified predicate is as follows. The main difference is the need to check whether "products" are defined (non-$0$).

IsQC := proc( s::Array(order=C_order, datatype=integer[4]), n::posint )
option autocompile;
local i, j, ij, u, r, found, undef;
for i from 1 to n do
for j from 1 to n do
ij := s[ i, j ];
if ij <> 0 then
found := false;
undef := false;
u := j;
for r from 1 to n + 1 do
if s[ u, i ] <> 0 then
if s[ u, i ] = ij then
found := true;
break
end if
else
undef := true;
break
end if;
u := s[ u, j ];
if u = 0 then
undef := true;
break
end if
end do;
if undef then
next
end if;
return false
end if
end if
end do
end do;
true
end proc:


To call this, use

with( Magma ):
L := Enumerate( 8, semigroup, test = IsQC, output = list ):


I found the resulting list had only one member, which I verified was $Q$.

Well, that was fun. Interesting question!

-
Sure. I've added more detail with the code I used. – James Feb 7 '13 at 4:31