Implement the cactus group

[tscrim]

We implement the cactus group J_n (of type A). The cactus group has important applications in category and representation theory.

This group is not available in GAP as far as I can tell.

CC: @sagetrac-ptingley @bsalisbury1

Component: group theory

Keywords: cactus

Author: Travis Scrimshaw

Branch/Commit: public/groups/cactus_group_v2-19594 @ 64608ff

Reviewer: Dima Pasechnik

Issue created by migration from https://trac.sagemath.org/ticket/19594

[tscrim]

Branch: public/groups/cactus_group-19594

[tscrim]

New commits:

83a2cc6

Implementation of the (type A) cactus group.

[tscrim]

Commit: 83a2cc6

[dimpase]

comment:2

Can you also construct the homomorphism to the symmetric group, and its kernel (i.e. pure cactus group) ?

[tscrim]

comment:3

Replying to @dimpase:

Can you also construct the homomorphism to the symmetric group, and its kernel (i.e. pure cactus group) ?

I can definitely add a default coercion to the symmetric group. I should be able to do a general subgroup defined by a particular condition (such as the kernel of a morphism). I will do this now.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

55d0e28	Merge branch 'public/groups/cactus_group-19594' of trac.sagemath.org:sage into public/groups/cactus_group-19594
83220d6	Implement coercion/maps from the cactus group to the permutation group.
0b3b875	Started implemention of kernel subgroups.
832d7f0	Added kernel subgroup and pure cactus group.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 83a2cc6 to 832d7f0

[tscrim]

comment:5

Done and done.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

7c0fdf3	Merge branch 'public/groups/cactus_group-19594' of git://trac.sagemath.org/sage into cactus
7eb2a12	correct quadratic relations

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 832d7f0 to 7eb2a12

[darijgr]

comment:7

Travis -- I like the fact that you are implementing this group, but are you sure that the switches you do in _product_on_gens are enough to bring every word in its generators to a normal form? I.e., that any two products of generators that compare as un-equal are actually distinct?

[tscrim]

comment:8

Replying to @darijgr:

Travis -- I like the fact that you are implementing this group, but are you sure that the switches you do in _product_on_gens are enough to bring every word in its generators to a normal form? I.e., that any two products of generators that compare as un-equal are actually distinct?

I haven't formally proved it (nor do I know if there is a formal proof that there is a normal form). I'm inclined to believe it works, but I'm not 100% sure (nor can I prove it right now). Perhaps we should add a warning about this?

[dimpase]

comment:9

Is any cactus group automatic? GAP has means to try to check whether an f.p. group is automatic. (this would give one a normal form, etc).

[tscrim]

comment:10

Replying to @dimpase:

Is any cactus group automatic? GAP has means to try to check whether an f.p. group is automatic. (this would give one a normal form, etc).

I don't know. The best I could find from some quick Googling is this MO question (which suggests that my approach does not give a normal form). We can try as I also included a f.p. version of the group which should be easy to feed to GAP. However, from me it would have to wait until tomorrow as I'm going to sleep now.

[dimpase]

comment:11

for n=3,4 Knuth-Bendix procedure (from the GAP package kbmag I mentioned in comment 9) quickly returns a rewriting system for J_n, but it gets stuck for n=5. I haven't tried to push this further yet.

[dimpase]

comment:12

I wonder why the code does not compute a presentation for the pure cactus group. This is more or less standard thing, Reidemeister-Schreier algorithm, implemented in GAP (see e.g. PresentationSubgroup).

[darijgr]

comment:13

After a few experiments (on paper), I have started suspecting that Travis's code does bring every word to a normal form. This could be a cool combinatorial result, if true.

If true, it should be provable using the diamond lemma... Does anyone volunteer to bash the cases?

[tscrim]

comment:14

Replying to @dimpase:

I wonder why the code does not compute a presentation for the pure cactus group. This is more or less standard thing, Reidemeister-Schreier algorithm, implemented in GAP (see e.g. PresentationSubgroup).

Is this a comment on my code or GAP's? I don't know the Reidemeister-Schreier algorithm, but I am not opposed to trying to extend the implementation.

[tscrim]

comment:15

Replying to @darijgr:

After a few experiments (on paper), I have started suspecting that Travis's code does bring every word to a normal form. This could be a cool combinatorial result, if true.

If true, it should be provable using the diamond lemma... Does anyone volunteer to bash the cases?

I am pretty sure that the terminating condition is possible, but I'm worried about a case of something like s[4, 5] * s[1, 7] * s[5, 8] and the shuffles. However, I agree it would be a nice little result if this was true, and as far as I can find, there is no such analogous result. At the very least, I think we can easily show an analog of Matsumoto's lemma, and so we build out a reduced word graph and find a lex min element in that.

[darijgr]

comment:16

Sorry, Travis, you are right with your worries:

sage: s45*s13 == s13*s45
True
sage: s26*s45*s13 == s26*s13*s45
False

This cactus is thornier than I thought.

[dimpase]

comment:17

Replying to @darijgr:

Sorry, Travis, you are right with your worries:

sage: s45*s13 == s13*s45
True
sage: s26*s45*s13 == s26*s13*s45
False

This cactus is thornier than I thought.

this is also what Knuth-Bendix computation was predicting, that for n>4 things get hard.

[dimpase]

comment:18

Replying to @tscrim:

Replying to @dimpase:

I wonder why the code does not compute a presentation for the pure cactus group. This is more or less standard thing, Reidemeister-Schreier algorithm, implemented in GAP (see e.g. PresentationSubgroup).

Is this a comment on my code or GAP's? I don't know the Reidemeister-Schreier algorithm, but I am not opposed to trying to extend the implementation.

it's a comment saying that this is doable (not sure how interesting).

[dimpase]

comment:19

There seems to be something wrong with the relations you provide.I am trying to check that you indeed have a homomorphism from J_4 to Sym(4), but GAP returns fail. Does your code check that your map is a group homomorphism?

gap> F:=FreeGroup(6);
<free group on the generators [ f1, f2, f3, f4, f5, f6 ]>
gap> s12:=F.1;; s13:=F.2;; s14:=F.3;; s23:=F.4;; s24:=F.5;; s34:=F.6;;
gap> rels:=[s12^2, s13^2, s14^2, s23^2, s24^2, s34^2, s13*s12*s13^-1*s23^-1, s13*s23*s13^-1*s12^-1, s14*s12*s14^-1*s34^-1, s14*s13*s14^-1*s24^-1, s14*s23*s14^-1*s23^-1, s14*s24*s14^-1*s13^-1, s14*s34*s14^-1*s12^-1, s24*s23*s24^-1*s34^-1, s24*s34*s24^-1*s23^-1, s34*s12*s34^-1*s12^-1 ];
[ f1^2, f2^2, f3^2, f4^2, f5^2, f6^2, f2*f1*f2^-1*f4^-1, f2*f4*f2^-1*f1^-1, f3*f1*f3^-1*f6^-1, 
  f3*f2*f3^-1*f5^-1, f3*f4*f3^-1*f4^-1, f3*f5*f3^-1*f2^-1, f3*f6*f3^-1*f1^-1, f5*f4*f5^-1*f6^-1, 
  f5*f6*f5^-1*f4^-1, f6*f1*f6^-1*f1^-1 ]
gap> G:=F/rels;
<fp group on the generators [ f1, f2, f3, f4, f5, f6 ]>
gap> s4:=Group([(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]);
Group([ (1,2), (1,3), (1,4), (2,3), (2,4), (3,4) ])
gap> GeneratorsOfGroup(s4);
[ (1,2), (1,3), (1,4), (2,3), (2,4), (3,4) ]
gap> f:=GroupHomomorphismByImages(G,s4);
fail

[dimpase]

comment:20

here is a direct check of the relations:

gap> s12:=(1,2); s13:=(1,3); s14:=(1,4); s23:=(2,3); s24:=(2,4); s34:=(3,4);
(1,2)
(1,3)
(1,4)
(2,3)
(2,4)
(3,4)
gap> [s12^2, s13^2, s14^2, s23^2, s24^2, s34^2, s13*s12*s13^-1*s23^-1, s13*s23*s13^-1*s12^-1, s14*s12*s14^-1*s34^-1, s14*s13*s14^-1*s24^-1, s14*s23*s14^-1*s23^-1, s14*s24*s14^-1*s13^-1, s14*s34*s14^-1*s12^-1, s24*s23*s24^-1*s34^-1, s24*s34*s24^-1*s23^-1, s34*s12*s34^-1*s12^-1 ];
[ (), (), (), (), (), (), (), (), (2,3,4), (2,4,3), (), (1,2,3), (1,3,2), (), (), () ]
gap> 

e.g. s14*s12*s14<sup>-1*s34</sup>-1 evaluates to (2,3,4) in Sym(4)...

[tscrim]

comment:21

s14 |-> (1,4) (2,3) is the correct image as s14 should correspond to flipping the entire interval [1, 4].

I asked Peter Tingley, who asked Joel Kamnitzer, and they do not know of a normal form.

What do both of you think about trying to prove an analog of Matsumoto's theorem for the cactus group, i.e., that all reduced words are related to each other by just applying the defining relations, as per comment:15?

[darijgr]

comment:22

It sounds like the next best thing, after we know that the obvious rewrite system does not work... But I don't see how to do it.

[dimpase]

comment:23

Replying to @tscrim:

s14 |-> (1,4) (2,3) is the correct image as s14 should correspond to flipping the entire interval [1, 4].

oops, OK then. Sorry for noise. By the way, what is proper Sage way to get words generating the kernel of the homomorphism to S_n?

I asked Peter Tingley, who asked Joel Kamnitzer, and they do not know of a normal form.

What do both of you think about trying to prove an analog of Matsumoto's theorem for the cactus group, i.e., that all reduced words are related to each other by just applying the defining relations, as per comment:15?

this looks a bit unlikely that a Matsumoto's-type argument would work here, with so many redundant generators (as opposed to the case of Coxeter groups). What might work is a kind of argument one sees for presentations of soluble groups, where one has commutator relations, allowing one to "sort" generators in words; but as we have S_n acting, unsolvable for n>4...

[tscrim]

comment:24

Replying to @dimpase:

Replying to @tscrim:

s14 |-> (1,4) (2,3) is the correct image as s14 should correspond to flipping the entire interval [1, 4].

oops, OK then. Sorry for noise. By the way, what is proper Sage way to get words generating the kernel of the homomorphism to S_n?

What I ended up doing on this ticket is just iterating over the ambient group J_n and returning the element in the kernel.

I asked Peter Tingley, who asked Joel Kamnitzer, and they do not know of a normal form.

What do both of you think about trying to prove an analog of Matsumoto's theorem for the cactus group, i.e., that all reduced words are related to each other by just applying the defining relations, as per comment:15?

this looks a bit unlikely that a Matsumoto's-type argument would work here, with so many redundant generators (as opposed to the case of Coxeter groups). What might work is a kind of argument one sees for presentations of soluble groups, where one has commutator relations, allowing one to "sort" generators in words; but as we have S_n acting, unsolvable for n>4...

I am guessing it would be too much to ask for a Garside-type structure coming from the projection onto S_n, where every element can be written as xy^k where x is the natural section of S_n and y is some special element in J_n (similar to a normal form for the braid group elements, where y corresponds to the section of the long element).

Are you thinking that there might be reduced expressions which require using the x^2 = 1 identity to add letters temporarily to get between them for n > 4?

I'm also emailing Joel and Peter about possible assistance we might get from geometric information.

[tscrim]

comment:25

Also Remark 6.2.4 of http://arxiv.org/abs/math/0203127 says that this should be a linear group (i.e., admits a faithful finite-dimensional representation). I should try to understand the representation they construct and implement that as well...

[dimpase]

comment:26

Replying to @tscrim:

Also Remark 6.2.4 of http://arxiv.org/abs/math/0203127 says that this should be a linear group (i.e., admits a faithful finite-dimensional representation). I should try to understand the representation they construct and implement that as well...

I don't see an immediate connection, as the presentation there seems to include more relations, of the form (xy)^m=1 ?

Anyhow, it might be quite hard to prove that an f.p. group is linear --- you probably heard the story of braid groups in this respect...

[tscrim]

comment:27

Replying to @tscrim:

I am guessing it would be too much to ask for a Garside-type structure coming from the projection onto S_n, where every element can be written as xy^k where x is the natural section of S_n and y is some special element in J_n (similar to a normal form for the braid group elements, where y corresponds to the section of the long element).

A Garside-type structure would not work here because that is used for passing from the braid monoid to the braid group. So I really don't think this will work for the cactus group.

[tscrim]

comment:28

Replying to @dimpase:

Replying to @tscrim:

Also Remark 6.2.4 of http://arxiv.org/abs/math/0203127 says that this should be a linear group (i.e., admits a faithful finite-dimensional representation). I should try to understand the representation they construct and implement that as well...

I don't see an immediate connection, as the presentation there seems to include more relations, of the form (xy)^m=1 ?

According to R. Scott's paper Right-angled Mock reflections and mock Artin groups, the cactus group is a special case of the presentation in that paper. I still need to verify it because I don't quite understand the first yet, but I believe Scott's comment.

Anyhow, it might be quite hard to prove that an f.p. group is linear --- you probably heard the story of braid groups in this respect...

Yea, but here I think we are closer to the Coxeter group than the braid group (and even have a representation to test). Yet, I do agree that this could be a hard thing to prove.

I forgot to mention it, but thank you Darij for testing it and the example showing my proposed normal form won't work.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 7eb2a12 to a3ab2d2

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

a3ab2d2

Added DJS representation for the cactus group.

[tscrim]

comment:30

Okay, so the cactus group corresponds to type A_n and when R is the full power set of the index set. I've added the representation described in the DJS paper here. One related question that comes to mind is what happens when t=1, do we get a (faithful) representation of the right-angled Coxeter group which has the t=1 bilinear form? We have a lot to think on for this...

The end result of our discussion as I see it is that we don't have a good way to construct normal forms of elements at present. So for the purposes of this ticket, should we include this as-is with a warning stating that elements may be equal even if == does not necessarily return True?

[dimpase]

comment:31

I am not sure that it is a good idea to have this group in the same catalog as the others (which do have a normal form for its elements). As it stands, the group operation for J_n is not well-defined, you know.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

3e99cfe

Merge branch 'public/groups/cactus_group-19594' into 7.3.b1

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from a3ab2d2 to 3e99cfe

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 3e99cfe to d883593

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

d883593

Merge branch 'public/groups/cactus_group-19594' in 7.5.b2

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

854f529	Merge branch 'public/groups/cactus_group-19594' in 7.5.rc1
002edc4	trac 19594 pep8 cleanup, deprecation handled, py3-compatible code

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from d883593 to 002edc4

[BruceWestbury]

comment:35

Daan Krammer has constructed an analogue of the Tits representation for the cactus groups. He proves this is faithful. The preprint version is:

https://arxiv.org/pdf/0708.1273.pdf

[You need to leave out the six term relations.]

[BruceWestbury]

comment:36

Is there a class for permutation representations of a finitely presented group?

I implemented the action on highest weight words in the tensor power of a crystal many years ago (using the Henriques-Kamnitzer definition).

[darijgr]

comment:37

Bruce: Interesting! Can you direct me to the specific point where the representation is constructed? How do I "leave out" the six term relations? (I mean, what do I tweak to make sure that the representation is still faithful?)

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 002edc4 to 14ec15b

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

14ec15b

Merge branch 'public/groups/cactus_group-19594' in 8.1.rc4

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 14ec15b to b354f58

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

b354f58

fix import

[bsalisbury1]

comment:40

According to a conversation with Travis today, the mathematics of this patch is incorrect at the moment.