Opened 5 years ago

Closed 5 years ago

#16725 closed enhancement (fixed)

Implement a general monoid_generators for groups

Reported by: tscrim Owned by: tscrim
Priority: major Milestone: sage-6.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 5 years ago by tscrim

  • Cc nthiery added

comment:2 Changed 5 years ago by ncohen

Aaaaaaand would it make sense to use monoid_generators when there is no group_generators too ? :-PPPPPP

comment:3 Changed 5 years ago by tscrim

  • Branch set to public/groups/monoid_generators-16725
  • 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:

0791169Added monoid generators for general groups.
e5cd7ccAdded try-except block for group_generators to fallback to monoid_generators.
c64a5fbAdded message for NotImplementedError for infinitely generated groups.

comment:4 follow-up: Changed 5 years ago by ncohen

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 ; follow-up: Changed 5 years ago by tscrim

Replying to ncohen:

Hmmmm... group_generators calls monoid_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 not-implemented generic infinite loops (there's another example with descents in Weyl groups #15456).

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 :-/

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 ; follow-up: Changed 5 years ago by ncohen

Helloooooooooooo !!!

Unfortunately we don't currently have a way to break out of such not-implemented 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 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 :-/

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.

Ahhahahah. Right, sorry.

Nathann

comment:7 in reply to: ↑ 6 ; follow-up: Changed 5 years ago by tscrim

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 semi-abstract methods like this).

comment:8 in reply to: ↑ 7 ; follow-up: Changed 5 years ago by ncohen

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 call monoid_generators. I think the infinite loop is the lesser of two evils (at least until we have the framework for semi-abstract 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 5 years ago by git

  • Commit changed from c64a5fb9487a0d54da40acd2003b0a2930f06207 to 796262d2ecb0d4aebc168e5107d5cd5ebb0d9d2d

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

796262dChanged behavior of general group_generators method.

comment:10 in reply to: ↑ 8 ; follow-up: Changed 5 years ago by tscrim

Replying to ncohen:

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

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 calling group_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 ; follow-up: Changed 5 years ago by 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 ?

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 re-defining gens().

Nathann

comment:12 in reply to: ↑ 11 ; follow-up: Changed 5 years ago by tscrim

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 re-defining gens().

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 ; follow-up: Changed 5 years ago by ncohen

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 5 years ago by ncohen

  • 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 follow-up: Changed 5 years ago by tscrim

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 5 years ago by ncohen

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 on-the-fly class inheritance, written in a non-compiled and non-typed 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 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:18 Changed 5 years ago by vbraun

  • Branch changed from public/groups/monoid_generators-16725 to 796262d2ecb0d4aebc168e5107d5cd5ebb0d9d2d
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.