8
$\begingroup$

Does the 6-element group $S_3$ have a finite (balanced) semigroup presentation of the form $$\langle a_1,...,a_n\mid a_1=u_1, a_2=u_2,...,a_n=u_n\rangle$$ where $u_1,u_2,...,u_n$ are semigroup words? Let us call such a semigroup presentation {\it tree-like}.

Edit: By a semigroup word, I mean a word without inverses of letters. By a semigroup presentation, I mean a presentation in the class of semigroups (not groups). For example, $\langle a,b\mid a^3=a, b=ab^2a\rangle$ defines $S_3$ in the class of groups but a "bigger" semigroup in the class of semigroups. In that semigroup, $b$ does not divide $a$, so it is not a group.

Motivation 1. The cyclic group of order $n$ has a tree-like semigroup presentation $\langle a\mid a=a^{n+1}\rangle$. Matt Brin noted that the 8-element quaternion group has the tree-like presentation $\langle a,b,c \mid a=bc, b=ca, c=ab\rangle$. The groups $S_m, m>3$ do not have tree-like presentations because they do not even have balanced (same number of relations and generators) presentations at all since their Schur multipliers are non-trivial. The group $S_3$ has a balanced presentation.

Motivation 2. Every tree-like semigroup presentation corresponds to a (closed) subgroup of the R. Thompson group $F$. For example as shown by Guba the Brin tree-like presentation of the quaternion group corresponds to a copy of the Thompson group $F_9$ (the group of piecewise linear homeomorphisms of $[0,1]$ with slopes of the form $9^k$ and break points of the derivative from $\mathbb{Z}[1/9]$).

| cite | improve this question | |
$\endgroup$
  • 3
    $\begingroup$ By a “semigroup word”, do you mean a nontrivial word involving only positive powers of the generators? If so, can’t you just adapt the balanced presentation that you link to slightly? $\langle a,b\mid a=a^3, b=ab^2a\rangle$? $\endgroup$ – Jeremy Rickard Jul 21 '18 at 8:19
  • $\begingroup$ Note that $Z[1/9]=Z[1/3]$. So the only difference between $F_3$ and $F_9$ lies in the slopes, not the breakpoints. $\endgroup$ – YCor Jul 21 '18 at 8:22
  • $\begingroup$ Do you mean that $u_i$ is a semigroup word in the generators except $a_i$? Otherwise such a presentation exists for any group. $\endgroup$ – Dan Petersen Jul 21 '18 at 9:49
  • $\begingroup$ @DanPetersen That cannot be right because, as is explained in the post, any finite group with a presentation of that type must have trivial Schur Multiplier. $\endgroup$ – Derek Holt Jul 21 '18 at 9:59
  • $\begingroup$ @DanPetersen existence of a balanced presentation (number of relators = number of generators) is a strong restriction. More generally, see the notion of deficiency en.wikipedia.org/wiki/Presentation_of_a_group#Deficiency $\endgroup$ – YCor Jul 21 '18 at 10:10
6
$\begingroup$

I see that Jeremy has beaten me to it - but here is a solution found by computer by choosing random entries from the group multiplication table.

This one also generates $S_3$ as a semigroup. The Magma command $\mathtt{RWSMonoid}$ applies the Knuth-Bendix algorithm to the presentation, and regards it as a monoid presentation. It has order $7$ as a monoid with identity equal to the empty word, and so it has order $6$ as a semigroup presentation.

$$\langle a,b,c,d,e,f\mid a=f^2,b=ab,c=df,d=ec,e=db,f=ce\rangle.$$

  > G := Group< a,b,c,d,e,f | a = f^2, b = a*b, c = d*f, d=e*c, e=d*b, f=c*e >;
  > Order(G);
  6
  > Homomorphisms(G,Sym(3))[1];
   Homomorphism of GrpFP: G into GrpPerm: X, Degree 3, Order 2 * 3 induced by
      G.1 |--> Id(X)
      G.2 |--> (1, 2, 3)
      G.3 |--> (1, 3, 2)
      G.4 |--> (1, 2)
      G.5 |--> (1, 3)
      G.6 |--> (2, 3)

> M := Monoid< a,b,c,d,e,f | a = f^2, b = a*b, c = d*f, d=e*c, e=d*b, f=c*e >; 
> R := RWSMonoid(M);
> Order(R);
7
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ An interesting thing is that the Knuth-Bendix completion of your presentation is the whole multiplication table of $S_3$. $\endgroup$ – user6976 Jul 21 '18 at 13:36
  • $\begingroup$ I think that would also happen if you used all elements of the group/monoid/semigroup as generators, with a word ordering based on word length. $\endgroup$ – Derek Holt Jul 21 '18 at 14:08
  • $\begingroup$ You mean: if I take randomly one relation from every row of the multiplication table, then the completion of that presentation will be the whole multiplication table? It can't be true because some groups just do not have a balanced presentation. What may be true is that one gets the universal central extension of the finite group this way. $\endgroup$ – user6976 Jul 21 '18 at 14:17
  • $\begingroup$ No, I just meant that any complete rewriting system using all (semi)group elements as generators would consist of the relations given by the multiplication table. One could conjecture that for any group of order $n$ with a balanced presentation there would be one consisting of $n$ relations from the multiplication table, but i don't see how you might go about proving that. $\endgroup$ – Derek Holt Jul 21 '18 at 15:17
  • $\begingroup$ Yes, that is the conjecture. If the group does not have a balanced presentation, then a part of the multiplication table (one relation per row and column?) should define the universal central extension of the group. I think that for the Klein 4-group $K_4$ it is true. $\endgroup$ – user6976 Jul 21 '18 at 15:32
7
$\begingroup$

Campbell, C. M.; Mitchell, J. D.; Ruškuc, N. On defining groups efficiently without using inverses. Math. Proc. Cambridge Philos. Soc. 133 (2002), no. 1, 31–36 shows among other things that a group with a balanced group presentation has a balanced semigroup presentation. The proof gives a tree like presentation. Look at the proof of Prop 2.4 and 2.5 and note R' and R'' are empty when the group presentation was balanced. See https://www.cambridge.org/core/journals/mathematical-proceedings-of-the-cambridge-philosophical-society/article/on-defining-groups-efficiently-without-using-inverses/ED8A580F336B47B2162DB5E3A5FA8459

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The tree-like presentation they produce defines the group in the class of all group (not in the class of all semigroups)? $\endgroup$ – user6976 Jul 21 '18 at 16:01
  • $\begingroup$ No it is in the class of semigroups. $\endgroup$ – Benjamin Steinberg Jul 21 '18 at 16:33
  • $\begingroup$ Look at Proposition 2.1. $\endgroup$ – Benjamin Steinberg Jul 21 '18 at 16:34
  • $\begingroup$ Yes, it is true. Very nice! $\endgroup$ – user6976 Jul 21 '18 at 17:54
  • $\begingroup$ I remember the authors giving a talk on this over 15 years ago. I just needed to check the proof gives treelike. $\endgroup$ – Benjamin Steinberg Jul 21 '18 at 17:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy