Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
Nice question! + –  amWhy Feb 7 '13 at 0:05
2  

1 Answer 1

up vote 7 down vote accepted

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!

share|improve this answer
3  
Sure. I've added more detail with the code I used. –  James Feb 7 '13 at 4:31

Your Answer

 
discard

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.