Opened 4 years ago

Last modified 17 months ago

#19594 needs_work enhancement

Implement the cactus group

Reported by: tscrim Owned by: tscrim
Priority: major Milestone: sage-7.0
Component: group theory Keywords: cactus
Cc: ptingley, bsalisbury1 Merged in:
Authors: Travis Scrimshaw Reviewers:
Report Upstream: N/A Work issues:
Branch: public/groups/cactus_group-19594 (Commits) Commit: b354f580ec5437e70b4d92502f09aa6206cb2fc1
Dependencies: Stopgaps:

Description

We implement the cactus group Jn (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.

Change History (40)

comment:1 Changed 4 years ago by tscrim

  • Branch set to public/groups/cactus_group-19594
  • Commit set to 83a2cc64551145946032112169f011ef897716c3
  • Status changed from new to needs_review

New commits:

83a2cc6Implementation of the (type A) cactus group.

comment:2 follow-up: Changed 4 years ago by dimpase

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

comment:3 in reply to: ↑ 2 Changed 4 years ago by tscrim

  • Cc ptingley added
  • Milestone changed from sage-6.10 to sage-7.0
  • Status changed from needs_review to needs_work

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.

comment:4 Changed 4 years ago by git

  • Commit changed from 83a2cc64551145946032112169f011ef897716c3 to 832d7f0de192e519ed8fd251eb8039722fad48b6

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

55d0e28Merge branch 'public/groups/cactus_group-19594' of trac.sagemath.org:sage into public/groups/cactus_group-19594
83220d6Implement coercion/maps from the cactus group to the permutation group.
0b3b875Started implemention of kernel subgroups.
832d7f0Added kernel subgroup and pure cactus group.

comment:5 Changed 4 years ago by tscrim

  • Status changed from needs_work to needs_review

Done and done.

comment:6 Changed 4 years ago by git

  • Commit changed from 832d7f0de192e519ed8fd251eb8039722fad48b6 to 7eb2a1278ea0ca08375f87e0f82081218a2ea1ec

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

7c0fdf3Merge branch 'public/groups/cactus_group-19594' of git://trac.sagemath.org/sage into cactus
7eb2a12correct quadratic relations

comment:7 follow-up: Changed 4 years ago by darij

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?

comment:8 in reply to: ↑ 7 Changed 4 years ago by tscrim

Replying to darij:

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?

comment:9 follow-up: Changed 4 years ago by dimpase

Is any cactus group automatic? GAP has means to try to check whether an f.p. group is automatic.

Version 0, edited 4 years ago by dimpase (next)

comment:10 in reply to: ↑ 9 Changed 4 years ago by tscrim

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.

comment:11 Changed 4 years ago by dimpase

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.

comment:12 follow-up: Changed 4 years ago by 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).

comment:13 follow-up: Changed 4 years ago by darij

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?

comment:14 in reply to: ↑ 12 ; follow-up: Changed 4 years ago by 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.

comment:15 in reply to: ↑ 13 Changed 4 years ago by tscrim

Replying to darij:

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.

comment:16 follow-up: Changed 4 years ago by darij

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.

comment:17 in reply to: ↑ 16 Changed 4 years ago by dimpase

Replying to darij:

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.

comment:18 in reply to: ↑ 14 Changed 4 years ago by dimpase

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

comment:19 Changed 4 years ago by dimpase

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

comment:20 Changed 4 years ago by dimpase

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^-1*s34^-1 evaluates to (2,3,4) in Sym(4)...

comment:21 follow-up: Changed 4 years ago by tscrim

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?

comment:22 Changed 4 years ago by darij

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.

comment:23 in reply to: ↑ 21 ; follow-up: Changed 4 years ago by 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?

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

comment:24 in reply to: ↑ 23 ; follow-up: Changed 4 years ago by tscrim

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 Jn 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 Sn, where every element can be written as xy^k where x is the natural section of Sn and y is some special element in Jn (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.

comment:25 follow-up: Changed 4 years ago by 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...

comment:26 in reply to: ↑ 25 ; follow-up: Changed 4 years ago by 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 ?

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

comment:27 in reply to: ↑ 24 Changed 4 years ago by tscrim

Replying to tscrim:

I am guessing it would be too much to ask for a Garside-type structure coming from the projection onto Sn, where every element can be written as xy^k where x is the natural section of Sn and y is some special element in Jn (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.

comment:28 in reply to: ↑ 26 Changed 4 years ago by tscrim

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.

comment:29 Changed 4 years ago by git

  • Commit changed from 7eb2a1278ea0ca08375f87e0f82081218a2ea1ec to a3ab2d2076464e3451720832ef384186abcc1552

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

a3ab2d2Added DJS representation for the cactus group.

comment:30 Changed 4 years ago by tscrim

Okay, so the cactus group corresponds to type An 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?

comment:31 Changed 4 years ago by dimpase

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 Jn is not well-defined, you know.

comment:32 Changed 4 years ago by git

  • Commit changed from a3ab2d2076464e3451720832ef384186abcc1552 to 3e99cfe0c0f0054ce44fa8e1ad9f2ea6c929ea2a

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

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

comment:33 Changed 3 years ago by git

  • Commit changed from 3e99cfe0c0f0054ce44fa8e1ad9f2ea6c929ea2a to d883593277148ad5301c7f428efe5edf6d1585a7

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

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

comment:34 Changed 3 years ago by git

  • Commit changed from d883593277148ad5301c7f428efe5edf6d1585a7 to 002edc4c3ba10274b93dbf960ed5a4d6d8e7f270

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

854f529Merge branch 'public/groups/cactus_group-19594' in 7.5.rc1
002edc4trac 19594 pep8 cleanup, deprecation handled, py3-compatible code

comment:35 Changed 2 years ago by Bruce

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

comment:36 Changed 2 years ago by Bruce

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

comment:37 Changed 2 years ago by darij

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

comment:38 Changed 2 years ago by git

  • Commit changed from 002edc4c3ba10274b93dbf960ed5a4d6d8e7f270 to 14ec15b7c35aecd879bc4bab020dddd19580d85c

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

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

comment:39 Changed 2 years ago by git

  • Commit changed from 14ec15b7c35aecd879bc4bab020dddd19580d85c to b354f580ec5437e70b4d92502f09aa6206cb2fc1

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

b354f58fix import

comment:40 Changed 17 months ago by bsalisbury1

  • Cc bsalisbury1 added
  • Status changed from needs_review to needs_work

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

Note: See TracTickets for help on using tickets.