Opened 6 years ago
Closed 6 years ago
#16725 closed enhancement (fixed)
Implement a general monoid_generators for groups
Reported by:  tscrim  Owned by:  tscrim 

Priority:  major  Milestone:  sage6.4 
Component:  group theory  Keywords:  
Cc:  ncohen, nthiery  Merged in:  
Authors:  Travis Scrimshaw  Reviewers:  Nathann Cohen 
Report Upstream:  N/A  Work issues:  
Branch:  796262d (Commits)  Commit:  796262d2ecb0d4aebc168e5107d5cd5ebb0d9d2d 
Dependencies:  Stopgaps: 
Description
As discussed on #16718, not all groups have a monoid_generators
method but we can define them by taking the generators as a group and their inverses.
Change History (18)
comment:1 Changed 6 years ago by
 Cc nthiery added
comment:2 Changed 6 years ago by
comment:3 Changed 6 years ago by
 Branch set to public/groups/monoid_generators16725
 Commit set to c64a5fb9487a0d54da40acd2003b0a2930f06207
 Status changed from new to needs_review
I set that as a fallback since most (all?) groups have a gens
method or a custom group_generators
.
New commits:
0791169  Added monoid generators for general groups.

e5cd7cc  Added tryexcept block for group_generators to fallback to monoid_generators.

c64a5fb  Added message for NotImplementedError for infinitely generated groups.

comment:4 followup: ↓ 5 Changed 6 years ago by
Hello Travis !
Hmmmm... group_generators
calls monoid_generators
and conversely. Isn't that an infinite loop, for some instance that I cannot create ? :P
Also, if a group has no group_generators
method nor monoid_generators
method then MyGroup.group_generators()
will result in an AttributeError
saying that monoid_generators
does not exist, which feels a bit weird :/
Nathann
comment:5 in reply to: ↑ 4 ; followup: ↓ 6 Changed 6 years ago by
Replying to ncohen:
Hmmmm...
group_generators
callsmonoid_generators
and conversely. Isn't that an infinite loop, for some instance that I cannot create ?:P
Unfortunately we don't currently have a way to break out of such notimplemented generic infinite loops (there's another example with descents in Weyl groups #15456).
Also, if a group has no
group_generators
method normonoid_generators
method thenMyGroup.group_generators()
will result in anAttributeError
saying thatmonoid_generators
does not exist, which feels a bit weird:/
With this, that situation will never occur since we've defined a generic group_generators
and monoid_generators
in the Groups
category, so every group gets it.
comment:6 in reply to: ↑ 5 ; followup: ↓ 7 Changed 6 years ago by
Helloooooooooooo !!!
Unfortunately we don't currently have a way to break out of such notimplemented generic infinite loops (there's another example with descents in Weyl groups #15456).
But don't you enter this infinite loop as soon as a group has no .gens()
?
sage: G=groups.presentation.Cyclic(10) sage: G=G.cartesian_product(G) sage: G.gens() AttributeError: 'CartesianProduct_with_category' object has no attribute 'gens' sage: G.group_generators() <loop>
Also, if a group has no
group_generators
method normonoid_generators
method thenMyGroup.group_generators()
will result in anAttributeError
saying thatmonoid_generators
does not exist, which feels a bit weird:/
With this, that situation will never occur since we've defined a generic
group_generators
andmonoid_generators
in theGroups
category, so every group gets it.
Ahhahahah. Right, sorry.
Nathann
comment:7 in reply to: ↑ 6 ; followup: ↓ 8 Changed 6 years ago by
Replying to ncohen:
But don't you enter this infinite loop as soon as a group has no
.gens()
?sage: G=groups.presentation.Cyclic(10) sage: G=G.cartesian_product(G) sage: G.gens() AttributeError: 'CartesianProduct_with_category' object has no attribute 'gens' sage: G.group_generators() <loop>
Right (unless the user implements a custom group_generators()
, which is the current recommendation). (Side note, this exact error shouldn't happen with #16718.) The other option would be to not have group_generators
call monoid_generators
. I think the infinite loop is the lesser of two evils (at least until we have the framework for semiabstract methods like this).
comment:8 in reply to: ↑ 7 ; followup: ↓ 10 Changed 6 years ago by
Yoooooo !
Right (unless the user implements a custom
group_generators()
, which is the current recommendation). (Side note, this exact error shouldn't happen with #16718.)
Right right. I just don't know much about groups in Sage, and it was the only way I knew to produce the bug :)
The other option would be to not have
group_generators
callmonoid_generators
. I think the infinite loop is the lesser of two evils (at least until we have the framework for semiabstract methods like this).
Hmmmm... And what would you think of not having group_generators
call monoid_generators
, and have group_generators
raise an exception if gens()
is not defined ? Something like that ?
AttributeError: No generators are available for this group. Please implement a .group_generators() method
It would tell the user what he needs to do in order to make everything work ?...
By the way I do not really understand what this .gens()
exactly is. The code seems to assume that .gens()
returns group generators, but in this case does the monoid code assume that .gens()
returns monoid generators too ?
gens()
should be the one calling group_generators
, not the other way around :/
Nathann
comment:9 Changed 6 years ago by
 Commit changed from c64a5fb9487a0d54da40acd2003b0a2930f06207 to 796262d2ecb0d4aebc168e5107d5cd5ebb0d9d2d
Branch pushed to git repo; I updated commit sha1. New commits:
796262d  Changed behavior of general group_generators method.

comment:10 in reply to: ↑ 8 ; followup: ↓ 11 Changed 6 years ago by
Replying to ncohen:
Hmmmm... And what would you think of not having
group_generators
callmonoid_generators
, and havegroup_generators
raise an exception ifgens()
is not defined ? Something like that ?
AttributeError: No generators are available for this group. Please implement a .group_generators() method
That's okay with me (although I've made it return a NotImplementedError
).
By the way I do not really understand what this
.gens()
exactly is. The code seems to assume that.gens()
returns group generators, but in this case does the monoid code assume that.gens()
returns monoid generators too ?
gens
is suppose to return a set of generators for this type of object. However this causes some problems if the generating set becomes smaller in a subcategory: #15381
gens()
should be the one callinggroup_generators
, not the other way around:/
I agree, but this comes from old code in Sage and I don't have the time and desire to go through and make the necessary changes.
comment:11 in reply to: ↑ 10 ; followup: ↓ 12 Changed 6 years ago by
Helloooooooooo !!
Thanks for your update !
That's okay with me (although I've made it return a
NotImplementedError
).
OKay ! Is there any technical reason why you prefered to not mention the name of the function ? Do you believe that this message is sufficient for group users to know what must be done ?
gens
is suppose to return a set of generators for this type of object. However this causes some problems if the generating set becomes smaller in a subcategory: #15381
I see. That's a rather unfortunate design choice.
I agree, but this comes from old code in Sage and I don't have the time and desire to go through and make the necessary changes.
Okay. It also helps me understand what you are fighting with when you write code like that.
Hey. Now that I think of it, it is another reason to raise an exception saying explicitly that group_generators
should be implemented. Not let them get away redefining gens()
.
Nathann
comment:12 in reply to: ↑ 11 ; followup: ↓ 13 Changed 6 years ago by
Replying to ncohen:
Helloooooooooo !!
Thanks for your update !
That's okay with me (although I've made it return a
NotImplementedError
).OKay ! Is there any technical reason why you prefered to not mention the name of the function ? Do you believe that this message is sufficient for group users to know what must be done ?
Since it is raised by group_generators
, I think it is sufficient.
Okay. It also helps me understand what you are fighting with when you write code like that.
Hey. Now that I think of it, it is another reason to raise an exception saying explicitly that
group_generators
should be implemented. Not let them get away redefininggens()
.
I don't hold a strong opinion on the error message; I just prefer them to be shorter and simple. If you want to expand on the error message, feel free to do so and you can set a positive review on my behalf.
comment:13 in reply to: ↑ 12 ; followup: ↓ 14 Changed 6 years ago by
Yo !
I don't hold a strong opinion on the error message; I just prefer them to be shorter and simple. If you want to expand on the error message, feel free to do so and you can set a positive review on my behalf.
Commit coming in a couple of minutes.
Nathann
comment:14 in reply to: ↑ 13 Changed 6 years ago by
 Reviewers set to Nathann Cohen
 Status changed from needs_review to positive_review
Commit coming in a couple of minutes.
HMmmm... I just looked at the code again, and you are right: it is better as it is.
Positive review ! Thanks for your patch !
Nathann
comment:15 followup: ↓ 16 Changed 6 years ago by
That's 2 tickets you've reviewed with categories, pretty soon you might actually be writing some. :P
Thanks for doing the review.
comment:16 in reply to: ↑ 15 Changed 6 years ago by
That's 2 tickets you've reviewed with categories, pretty soon you might actually be writing some.
:P
Already did in #16269 :P
My problem with categories is that I totally, deeply, wholeheartedly hate them. To me, categories are onthefly class inheritance, written in a noncompiled and nontyped language. It's like a disaster before the very first line is written. It can *ONLY* be slow, broken, and disappointing.
If the language were compiled and typed, well.. It may work. But that is not the case, and in the end most of the computations are spent on the category infrastructure rather than on what the user wants.
I had the problem recently because of very slow addition in the product of additive groups: it was solved by using the group product Sage object to obtain the addition law in the group, which is then translated to a matrix, then all the work is done with the matrix itself. Thank you categories !
Thanks for doing the review.
My pleasure. Add me in Cc when you have tickets like that, that are somehow local and understandable. But as I do not know much about categories in general, I do not feel secure touching anything that might have a global impact ^^;
Nathann
comment:17 Changed 6 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:18 Changed 6 years ago by
 Branch changed from public/groups/monoid_generators16725 to 796262d2ecb0d4aebc168e5107d5cd5ebb0d9d2d
 Resolution set to fixed
 Status changed from positive_review to closed
Aaaaaaand would it make sense to use
monoid_generators
when there is nogroup_generators
too ?:PPPPPP