Implement the cactus group #19594

tscrim · 2015-11-17T23:17:44Z

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

The text was updated successfully, but these errors were encountered:

tscrim · 2015-11-17T23:18:16Z

Branch: public/groups/cactus_group-19594

tscrim · 2015-11-17T23:18:16Z

New commits:

`83a2cc6`	`Implementation of the (type A) cactus group.`

tscrim · 2015-11-17T23:18:16Z

Commit: 83a2cc6

dimpase · 2015-12-23T20:35:21Z

comment:2

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

tscrim · 2015-12-24T23:10:15Z

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.

sagetrac-git · 2015-12-25T02:43:27Z

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

sagetrac-git · 2015-12-25T02:43:27Z

Changed commit from 83a2cc6 to 832d7f0

tscrim · 2015-12-25T02:44:09Z

comment:5

Done and done.

sagetrac-git · 2015-12-28T02:01:44Z

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`

sagetrac-git · 2015-12-28T02:01:44Z

Changed commit from 832d7f0 to 7eb2a12

darijgr · 2015-12-28T02:02:44Z

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 · 2015-12-28T04:56:08Z

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 · 2015-12-28T07:02:04Z

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 · 2015-12-28T08:11:26Z

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 · 2015-12-28T12:20:34Z

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 · 2015-12-28T14:59:50Z

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 · 2015-12-28T17:18:38Z

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 · 2015-12-28T18:00:44Z

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.

sagetrac-git · 2023-01-21T01:23:46Z

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

`d61d297`	`Fixing some doctests and details.`

sagetrac-git · 2023-01-21T01:23:46Z

Changed commit from 5439a9d to d61d297

tscrim · 2023-01-21T01:25:29Z

comment:53

Thank you. This should take care of those issues.

dimpase · 2023-01-21T11:39:05Z

comment:54

In finite group theory J_n (n=[1..4]) is a Janko group. Can you add a remark in the docs, to disambiguate ?

https://en.wikipedia.org/wiki/Janko_group

dimpase · 2023-01-21T11:39:38Z

comment:55

After this, it would be a positive review from me.

tscrim · 2023-01-21T12:18:31Z

comment:56

Replying to Dima Pasechnik:

In finite group theory J_n (n=[1..4]) is a Janko group. Can you add a remark in the docs, to disambiguate ?

https://en.wikipedia.org/wiki/Janko_group

I am not quite sure what you are looking for. Nearly everywhere in the docs, the notation J_n was clearly noted as the cactus group (the exception being in the method geometric_representation_generators()'s doc). Are you wanting a message saying something to the effect of "Despite having the same notation, this is not the Janko group."? I would be surprised if having the same notation would cause any confusion.

dimpase · 2023-01-21T21:47:48Z

comment:57

I'm talking about

$ git grep J_2
src/sage/graphs/generators/distance_regular.pyx:    Return the distance-transitive graph with automorphism group `J_2`.
src/sage/graphs/generators/distance_regular.pyx:    G.name("J_2 graph")
src/sage/graphs/generators/distance_regular.pyx:        Grassmann graph J_2(6, 3): Graph on 1395 vertices
src/sage/graphs/generators/smallgraphs.py:    permutation representation of the Janko group `J_2`, as described in version
src/sage/graphs/strongly_regular_db.pyx:    This graph is built from the action of `J_2` on the cosets of a `3.PGL(2,9)`-subgroup.
src/sage/graphs/strongly_regular_db.pyx:    g.name('J_2 on cosets of 3.PGL(2,9)')

here J_2 is a group - but a quite different one. How about

--- a/src/sage/groups/finitely_presented_named.py
+++ b/src/sage/groups/finitely_presented_named.py
@@ -12,7 +12,7 @@ Groups available as finite presentations:
 - Alternating group, `A_n` of order `n!/2` --
   :func:`groups.presentation.Alternating <sage.groups.finitely_presented_named.AlternatingPresentation>`
 
-- Cactus group, `J_n` --
+- Cactus group, `J_n` (not to be confused with Janko groups `J_n`) --
   :func:`groups.presentation.Cactus <sage.groups.finitely_presented_named.CactusPresentation>`
 
 - Cyclic group, `C_n` of order `n` --

tscrim · 2023-01-22T06:44:39Z

comment:58

Replying to Dima Pasechnik:

I'm talking about

I understand your issue that someone out there might confuse the notation with the standard notation for the Janko groups. (I would actually argue that those other places should make clear what group they are talking about since notation has a high chance of conflicting...)

How about sidestepping this by

--- a/src/sage/groups/finitely_presented_named.py
+++ b/src/sage/groups/finitely_presented_named.py
@@ -12,7 +12,7 @@ Groups available as finite presentations:
 - Alternating group, `A_n` of order `n!/2` --
   :func:`groups.presentation.Alternating <sage.groups.finitely_presented_named.AlternatingPresentation>`
 
-- Cactus group, `J_n` --
+- the `n`-fruit Cactus group --
   :func:`groups.presentation.Cactus <sage.groups.finitely_presented_named.CactusPresentation>`
 
 - Cyclic group, `C_n` of order `n` --

dimpase · 2023-01-22T12:35:21Z

comment:59

You do use J_n in several other docstring places in your patch - but now you propose to hide it in the index. No, this is making docs worse, not better.

I don't get what you don't like about my suggestion. Your patch introduces ambiguity w.r.t. to the meaning of "group J_n" - then please make sure that it does not confuse readers of the documentation.

tscrim · 2023-01-22T13:03:03Z

comment:60

There is no ambiguity. The notation clearly is referring to the cactus group every place in the documentation. I do not want to write anything saying “this notation is not the same as X, Y, and Z” anytime there is conflicting notation. This is distracting, a maintenance burden, and more likely to introduce confusion.

dimpase · 2023-01-22T18:39:46Z

comment:61

J_n is standard notation, as such should be mentioned in the catalog/index.

How about PJ_n, should it be in the catalog too?

tscrim · 2023-01-23T00:10:59Z

comment:62

Replying to Dima Pasechnik:

J_n is standard notation, as such should be mentioned in the catalog/index.

None of the groups have their notation (standard or otherwise) mentioned in any of the catalogs AFAICS. The only place notation is mentioned (other than in its own file) is in the finitely_presented_names.py module-level doc, where it is following the conventions there. However, I would be fine with a change like this:

--- a/src/sage/groups/finitely_presented_named.py
+++ b/src/sage/groups/finitely_presented_named.py
@@ -12,7 +12,7 @@ Groups available as finite presentations:
 - Alternating group, `A_n` of order `n!/2` --
   :func:`groups.presentation.Alternating <sage.groups.finitely_presented_named.AlternatingPresentation>`
 
-- Cactus group, `J_n` --
+- the `n`-fruit Cactus group, a standard notation for which is `J_n` --
   :func:`groups.presentation.Cactus <sage.groups.finitely_presented_named.CactusPresentation>`
 
 - Cyclic group, `C_n` of order `n` --

How about PJ_n, should it be in the catalog too?

It is in the main misc catalog. Are you referring to the finitely-presented one? There isn't a known presentation for the pure cactus group AFAIK. We can derive one since it is a finite-index subgroup of the cactus group, but it is algorithmic (which I didn't feel motivated to do; plus it should have a more general implementation, something the gens() code likely should be generalized to).

dimpase · 2023-01-23T00:33:19Z

comment:63

ok fine, just change as you proposed in the last comment

sagetrac-git · 2023-01-23T00:52:46Z

Changed commit from d61d297 to 3c4e316

sagetrac-git · 2023-01-23T00:52:46Z

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

`3c4e316`	`Some details about cactus group notation.`

sagetrac-git · 2023-01-23T00:58:42Z

Changed commit from 3c4e316 to 64608ff

sagetrac-git · 2023-01-23T00:58:42Z

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

`64608ff`	`Some last little details.`

tscrim · 2023-01-23T00:59:31Z

comment:66

Done. I also noticed a few other trivial things that I fixed in the last commit.

dimpase · 2023-01-23T09:15:23Z

comment:67

OK, thanks

tscrim · 2023-01-23T13:12:50Z

comment:68

Thank you for the review.

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. URL: https://trac.sagemath.org/19594 Reported by: tscrim Ticket author(s): Travis Scrimshaw Reviewer(s): Dima Pasechnik

mkoeppe · 2023-02-13T00:55:28Z

Merged in 10.0.beta0

tscrim added this to the sage-6.10 milestone Nov 17, 2015

tscrim added c: group theory labels Nov 17, 2015

tscrim self-assigned this Nov 17, 2015

tscrim added the s: needs review label Nov 17, 2015

tscrim added s: needs work and removed s: needs review labels Dec 24, 2015

tscrim modified the milestones: sage-6.10, sage-7.0 Dec 24, 2015

tscrim added s: needs review and removed s: needs work labels Dec 25, 2015

tscrim added s: needs review and removed s: needs work labels Jan 21, 2023

dimpase added s: positive review and removed s: needs review labels Jan 23, 2023

mkoeppe modified the milestones: sage-9.8, sage-9.9 Feb 11, 2023

mkoeppe closed this as completed Feb 13, 2023

mkoeppe removed the s: positive review label Feb 13, 2023

Implement the cactus group #19594

Implement the cactus group #19594

Comments

tscrim commented Nov 17, 2015

tscrim commented Nov 17, 2015

tscrim commented Nov 17, 2015

tscrim commented Nov 17, 2015

dimpase commented Dec 23, 2015

tscrim commented Dec 24, 2015

sagetrac-git mannequin commented Dec 25, 2015

sagetrac-git mannequin commented Dec 25, 2015

tscrim commented Dec 25, 2015

sagetrac-git mannequin commented Dec 28, 2015

sagetrac-git mannequin commented Dec 28, 2015

darijgr commented Dec 28, 2015

tscrim commented Dec 28, 2015

dimpase commented Dec 28, 2015

tscrim commented Dec 28, 2015

dimpase commented Dec 28, 2015

dimpase commented Dec 28, 2015

darijgr commented Dec 28, 2015

tscrim commented Dec 28, 2015

sagetrac-git mannequin commented Jan 21, 2023

sagetrac-git mannequin commented Jan 21, 2023

tscrim commented Jan 21, 2023

dimpase commented Jan 21, 2023

dimpase commented Jan 21, 2023

tscrim commented Jan 21, 2023

dimpase commented Jan 21, 2023

tscrim commented Jan 22, 2023

dimpase commented Jan 22, 2023

tscrim commented Jan 22, 2023

dimpase commented Jan 22, 2023

tscrim commented Jan 23, 2023

dimpase commented Jan 23, 2023

sagetrac-git mannequin commented Jan 23, 2023

sagetrac-git mannequin commented Jan 23, 2023

sagetrac-git mannequin commented Jan 23, 2023

sagetrac-git mannequin commented Jan 23, 2023

tscrim commented Jan 23, 2023

dimpase commented Jan 23, 2023

tscrim commented Jan 23, 2023

mkoeppe commented Feb 13, 2023