8
$\begingroup$

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.

$\endgroup$
1

1 Answer 1

7
$\begingroup$

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.)

ADDED:

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;
      if not found then
        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$.

ADDED (2):

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;
        if not found then
          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!

$\endgroup$
1
  • 3
    $\begingroup$ Sure. I've added more detail with the code I used. $\endgroup$
    – James
    Feb 7, 2013 at 4:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .