Opened 5 years ago
Last modified 2 years ago
#19594 needs_work enhancement
Implement the cactus group
Reported by:  tscrim  Owned by:  tscrim 

Priority:  major  Milestone:  sage7.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_group19594 (Commits)  Commit:  b354f580ec5437e70b4d92502f09aa6206cb2fc1 
Dependencies:  Stopgaps: 
Description
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.
Change History (40)
comment:1 Changed 5 years ago by
 Branch set to public/groups/cactus_group19594
 Commit set to 83a2cc64551145946032112169f011ef897716c3
 Status changed from new to needs_review
comment:2 followup: ↓ 3 Changed 5 years ago by
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 5 years ago by
 Cc ptingley added
 Milestone changed from sage6.10 to sage7.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 5 years ago by
 Commit changed from 83a2cc64551145946032112169f011ef897716c3 to 832d7f0de192e519ed8fd251eb8039722fad48b6
Branch pushed to git repo; I updated commit sha1. New commits:
55d0e28  Merge branch 'public/groups/cactus_group19594' of trac.sagemath.org:sage into public/groups/cactus_group19594

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.

comment:6 Changed 5 years ago by
 Commit changed from 832d7f0de192e519ed8fd251eb8039722fad48b6 to 7eb2a1278ea0ca08375f87e0f82081218a2ea1ec
comment:7 followup: ↓ 8 Changed 5 years ago by
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 unequal are actually distinct?
comment:8 in reply to: ↑ 7 Changed 5 years ago by
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 unequal 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 followup: ↓ 10 Changed 5 years ago by
Is any cactus group automatic? GAP has means to try to check whether an f.p. group is automatic.
comment:10 in reply to: ↑ 9 Changed 5 years ago by
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 5 years ago by
for n=3,4 KnuthBendix 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 followup: ↓ 14 Changed 5 years ago by
I wonder why the code does not compute a presentation for the pure cactus group. This is more or less standard thing, ReidemeisterSchreier algorithm, implemented in GAP (see e.g. PresentationSubgroup
).
comment:13 followup: ↓ 15 Changed 5 years ago by
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 ; followup: ↓ 18 Changed 5 years ago by
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, ReidemeisterSchreier algorithm, implemented in GAP (see e.g.
PresentationSubgroup
).
Is this a comment on my code or GAP's? I don't know the ReidemeisterSchreier algorithm, but I am not opposed to trying to extend the implementation.
comment:15 in reply to: ↑ 13 Changed 5 years ago by
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 followup: ↓ 17 Changed 5 years ago by
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 5 years ago by
Replying to darij:
Sorry, Travis, you are right with your worries:
sage: s45*s13 == s13*s45 True sage: s26*s45*s13 == s26*s13*s45 FalseThis cactus is thornier than I thought.
this is also what KnuthBendix computation was predicting, that for n>4 things get hard.
comment:18 in reply to: ↑ 14 Changed 5 years ago by
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, ReidemeisterSchreier algorithm, implemented in GAP (see e.g.
PresentationSubgroup
).Is this a comment on my code or GAP's? I don't know the ReidemeisterSchreier 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 5 years ago by
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 5 years ago by
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 followup: ↓ 23 Changed 5 years ago by
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 5 years ago by
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 ; followup: ↓ 24 Changed 5 years ago by
Replying to tscrim:
s14 > (1,4) (2,3)
is the correct image ass14
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'stype 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 ; followup: ↓ 27 Changed 5 years ago by
Replying to dimpase:
Replying to tscrim:
s14 > (1,4) (2,3)
is the correct image ass14
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'stype 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 Garsidetype 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.
comment:25 followup: ↓ 26 Changed 5 years ago by
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 finitedimensional representation). I should try to understand the representation they construct and implement that as well...
comment:26 in reply to: ↑ 25 ; followup: ↓ 28 Changed 5 years ago by
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 finitedimensional 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 5 years ago by
Replying to tscrim:
I am guessing it would be too much to ask for a Garsidetype structure coming from the projection onto S_{n}, where every element can be written as
xy^k
wherex
is the natural section of S_{n} andy
is some special element in J_{n} (similar to a normal form for the braid group elements, wherey
corresponds to the section of the long element).
A Garsidetype 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 5 years ago by
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 finitedimensional 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 Rightangled 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 5 years ago by
 Commit changed from 7eb2a1278ea0ca08375f87e0f82081218a2ea1ec to a3ab2d2076464e3451720832ef384186abcc1552
Branch pushed to git repo; I updated commit sha1. New commits:
a3ab2d2  Added DJS representation for the cactus group.

comment:30 Changed 5 years ago by
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 rightangled 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 asis with a warning stating that elements may be equal even if ==
does not necessarily return True
?
comment:31 Changed 5 years ago by
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 welldefined, you know.
comment:32 Changed 5 years ago by
 Commit changed from a3ab2d2076464e3451720832ef384186abcc1552 to 3e99cfe0c0f0054ce44fa8e1ad9f2ea6c929ea2a
Branch pushed to git repo; I updated commit sha1. New commits:
3e99cfe  Merge branch 'public/groups/cactus_group19594' into 7.3.b1

comment:33 Changed 4 years ago by
 Commit changed from 3e99cfe0c0f0054ce44fa8e1ad9f2ea6c929ea2a to d883593277148ad5301c7f428efe5edf6d1585a7
Branch pushed to git repo; I updated commit sha1. New commits:
d883593  Merge branch 'public/groups/cactus_group19594' in 7.5.b2

comment:34 Changed 4 years ago by
 Commit changed from d883593277148ad5301c7f428efe5edf6d1585a7 to 002edc4c3ba10274b93dbf960ed5a4d6d8e7f270
comment:35 Changed 3 years ago by
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 3 years ago by
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 HenriquesKamnitzer definition).
comment:37 Changed 3 years ago by
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 3 years ago by
 Commit changed from 002edc4c3ba10274b93dbf960ed5a4d6d8e7f270 to 14ec15b7c35aecd879bc4bab020dddd19580d85c
Branch pushed to git repo; I updated commit sha1. New commits:
14ec15b  Merge branch 'public/groups/cactus_group19594' in 8.1.rc4

comment:39 Changed 3 years ago by
 Commit changed from 14ec15b7c35aecd879bc4bab020dddd19580d85c to b354f580ec5437e70b4d92502f09aa6206cb2fc1
Branch pushed to git repo; I updated commit sha1. New commits:
b354f58  fix import

comment:40 Changed 2 years ago by
 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.
New commits:
Implementation of the (type A) cactus group.