Opened 5 years ago

Closed 5 years ago

#17573 closed enhancement (fixed)

Wrap Gap Structure Description

Reported by: kcrisman Owned by:
Priority: minor Milestone: sage-6.5
Component: group theory Keywords:
Cc: Merged in:
Authors: Sergey Bykov Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: 294041b (Commits) Commit: 294041b72adf4b10f44f913d7439c33c96524eee
Dependencies: Stopgaps:

Description

Change History (41)

comment:1 Changed 5 years ago by ncohen

Something like that ?

sage: graphs.PetersenGraph().automorphism_group().structure_description()
'S5'

It is in sage.groups.perm_gps.permgroup.PermutationGroup (relevant ticket#15128)

Nathann

Last edited 5 years ago by ncohen (previous) (diff)

comment:2 Changed 5 years ago by ncohen

To make it work on the example given on math.sx, you have to first build the associated permutation group.

sage: F.<x, y> = FreeGroup()
sage: G=F / [x^2*y^-1, x^3*y^2, x*y*x^-1*y^-1]
sage: G.as_permutation_group().structure_description()
'C7'

It should probably be exposed in F directly. As an alias to .as_permutation_group().structure_description() if we have to, but it seems that gap does not actually need to build the permutation group in order to compute that.

Nathann

Last edited 5 years ago by ncohen (previous) (diff)

comment:3 Changed 5 years ago by captaintrunky

  • Branch set to u/captaintrunky/wrap_gap_structure_description

comment:4 Changed 5 years ago by captaintrunky

  • Authors set to Sergey Bykov
  • Commit set to b88e7a5c17a8e564852bef7d1a80580c04d0f114
  • Status changed from new to needs_review

New commits:

b88e7a5Added shortcut for structure_description() procedure

comment:5 Changed 5 years ago by vdelecroix

Hello,

The method does not look reasonable: if you ask the structure description of the free group, it will not answer. I am pretty sure that there are things to analyze structure of finitely generated groups in GAP. Moreover why 4096000 for finite groups? it is quite huge!

Vincent

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

Hello again,

It seems that it is not necessary to turn the group into a permutation group in order to get this information from gap

sage: F.<x, y> = FreeGroup()
sage: G=F / [x^2*y^-1, x^3*y^2, x*y*x^-1*y^-1]
sage: G._gap_().StructureDescription()
"C7"

Thus there should be no problem with a limit argument or anything.

There remains some work to do in this ticket, however, for the code of structure_description defined in PermutationGroup does not only return GAP's answer: there is some string rewriting going on (as well as a latex output available), and it would be better to not copy/paste it here.

Nathann

comment:7 Changed 5 years ago by ncohen

  • Status changed from needs_review to needs_work

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

Hi, Nathan. Thanks for the feedback. I've ended up today with exactly the same solution like yours. I'll add Latex output and proper string formatting in a couple of days.

Replying to ncohen:

Hello again,

It seems that it is not necessary to turn the group into a permutation group in order to get this information from gap

sage: F.<x, y> = FreeGroup()
sage: G=F / [x^2*y^-1, x^3*y^2, x*y*x^-1*y^-1]
sage: G._gap_().StructureDescription()
"C7"

Thus there should be no problem with a limit argument or anything.

There remains some work to do in this ticket, however, for the code of structure_description defined in PermutationGroup does not only return GAP's answer: there is some string rewriting going on (as well as a latex output available), and it would be better to not copy/paste it here.

Nathann

comment:9 in reply to: ↑ 8 Changed 5 years ago by ncohen

Yoooooooo !

I've ended up today with exactly the same solution like yours. I'll add Latex output and proper string formatting in a couple of days.

Great! Thanks for working on that.

Nathann

comment:10 Changed 5 years ago by git

  • Commit changed from b88e7a5c17a8e564852bef7d1a80580c04d0f114 to 3afe347685ec8ccf777c633f9c91bd6f334b1c83

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

3afe347Added direct call to the _gap_.StructureDescription and Latex formatting

comment:11 Changed 5 years ago by captaintrunky

  • Status changed from needs_work to needs_review

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

Hello again,

I thought for a while about how we could avoid some copy/pate meant to handle the GAP output, then ended up using a trick. I wrote a couple of commits which do the following:

1) Move structure_description from permgroup.py to generic.py without doing any modification to it

2) Update it a bit (change 'self' into 'G', add a couple of examples) then bind this function to the permutation_group and finitely_presented_group classes. And also to Matrix_group while I was at it.

I had to find a workaround for this .sage()/.str() problem you must have met yourself while you were working on this patch. This code works but there is definitely something fishy there.

Tell me what you think,

Nathann

P.S.: Those two commits can be found at: public/17573

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

Hi, Nathann! StructureDescription routine seems to be very general, so I agree that it should be moved from a special object like permutation_group somewhere else. I found your solution in these 2 commits reasonable for the whole problem. Yes, I have already struggled with sage()/str(). Maybe we should open a ticket for this? I was very surprised that such basic stuff works in different (and not obvious) ways under the same cover due to several APIs to GAP. In conclusion, I think that this ticket may be closed -- the goal is achieved.

Replying to ncohen:

Hello again,

I thought for a while about how we could avoid some copy/pate meant to handle the GAP output, then ended up using a trick. I wrote a couple of commits which do the following:

1) Move structure_description from permgroup.py to generic.py without doing any modification to it

2) Update it a bit (change 'self' into 'G', add a couple of examples) then bind this function to the permutation_group and finitely_presented_group classes. And also to Matrix_group while I was at it.

I had to find a workaround for this .sage()/.str() problem you must have met yourself while you were working on this patch. This code works but there is definitely something fishy there.

Tell me what you think,

Nathann

P.S.: Those two commits can be found at: public/17573

comment:14 in reply to: ↑ 13 Changed 5 years ago by ncohen

  • Branch changed from u/captaintrunky/wrap_gap_structure_description to public/17573
  • Commit changed from 3afe347685ec8ccf777c633f9c91bd6f334b1c83 to 294041b72adf4b10f44f913d7439c33c96524eee
  • Reviewers set to Nathann Cohen

Hello!

StructureDescription routine seems to be very general, so I agree that it should be moved from a special object like permutation_group somewhere else.

Indeed.

I found your solution in these 2 commits reasonable for the whole problem.

Thanks.

Yes, I have already struggled with sage()/str(). Maybe we should open a ticket for this? I was very surprised that such basic stuff works in different (and not obvious) ways under the same cover due to several APIs to GAP.

To be honest I would be glad to see it fixed, but I really did not understand where the problem came from. For some reason that I do not get, calling str(x) is not equivalent to x.__str__() on some objects O_o

In conclusion, I think that this ticket may be closed -- the goal is achieved.

Well, then you can switch the ticket's status to positive_review and it will make it in the next release :-)

Nathann


New commits:

a2d8adetrac #17573: Move structure_description from permgroup.py to generic.py
294041btrac #17573: update structure_descriptions and bind it to the classes

comment:15 Changed 5 years ago by captaintrunky

  • Status changed from needs_review to positive_review

I'll try to investigate the troubles with str()/sage().

comment:16 follow-up: Changed 5 years ago by vbraun

Argh, monkey patching classes to inherit your methods? Really? Am I the only one who finds this hideously ugly?

The plan is to

  1. get rid of Group_old, ie. switch permutation group to libgap
  2. get rid of all users of the old gap pexpect interface

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

Argh, monkey patching classes to inherit your methods? Really? Am I the only one who finds this hideously ugly?

Where do you think that this method should be implemented in order to be only inherited by classes on which it will actually work?

Nathann

comment:18 follow-up: Changed 5 years ago by vbraun

  • Status changed from positive_review to needs_work

At the very least don't impose your idea of the degree of the dihedral group on others. Especially if your docs say that you use GAP's definititon.

comment:19 in reply to: ↑ 17 Changed 5 years ago by vbraun

Replying to ncohen:

Where do you think that this method should be implemented in order to be only inherited by classes on which it will actually work?

The standard lore is to give a generic implementation as high up as possible (e.g. in Group) and then override it with specialized implementations where appropriate.

comment:20 in reply to: ↑ 18 Changed 5 years ago by ncohen

At the very least don't impose your idea of the degree of the dihedral group on others. Especially if your docs say that you use GAP's definititon.

None of the code that this branch contains does that. As you will find from the commits, it merely moves a function from one place to another, and the function's body has not been changed.

The standard lore is to give a generic implementation as high up as possible (e.g. in Group) and then override it with specialized implementations where appropriate.

If you do that, the function will be broken on many groups. It will not give wrong or slow results, but will just break. This is why I only added it to the classes that I found able to handle it.

I set this patch back to its original status.

Nathann

comment:21 Changed 5 years ago by ncohen

  • Status changed from needs_work to positive_review

comment:22 follow-up: Changed 5 years ago by vbraun

Fine, take a dump in our codebase.

comment:23 in reply to: ↑ 22 Changed 5 years ago by ncohen

Fine, take a dump in our codebase.

I'll be glad to improve this implementation if you eventually want to contribute some more constructive criticism.

Nathann

comment:24 follow-up: Changed 5 years ago by kcrisman

Could raising a NotImplementedError at the highest level solve this standoff? I believe that is the usual way to deal with this.

comment:25 in reply to: ↑ 24 Changed 5 years ago by ncohen

Could raising a NotImplementedError at the highest level solve this standoff? I believe that is the usual way to deal with this.

This would make the function available on all groups, but then how should we make the 'real code' available in the groups that actually support it (if not by the trick used here)?

Nathann

comment:26 follow-up: Changed 5 years ago by vbraun

Really the SX question boils down to : why is structure_description not consistently available for every group, after all it makes sense for every group. Just monkey-patching it to yet another group addresses one particular symptom, but does nothing against the disease. I agree with Karl-Dieter, just raise NotImplementedError where appropriate (e.g. there is no gap method).

comment:27 Changed 5 years ago by kcrisman

I haven't looked at the details, just trying a suggestion; perhaps in this case it isn't appropriate. There is no subclass of groups that it is available on?

Or is the problem that the code for wrapping this only should be written once, but the various subclasses it works on aren't inherited from each other, so that then one has to rewrite this code for each such class?

To Volker's point, I believe that not every group actually has this description available in gap itself, or so I read the comments and tests to imply. It isn't sufficient to have a gap method, it looks like.

Last edited 5 years ago by kcrisman (previous) (diff)

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

Yo!

Really the SX question boils down to : why is structure_description not consistently available for every group, after all it makes sense for every group.

True. There are oddities in the code, however, like this MatrixGroup_gap class whose description reads:

Matrix group over a ring that GAP understands

I took it as a hint that there will never be a working .gap() function on all groups.

Just monkey-patching it to yet another group addresses one particular symptom, but does nothing against the disease.

Indeed. It only makes the method available on some classes where it was not.

I agree with Karl-Dieter, just raise NotImplementedError where appropriate (e.g. there is no gap method).

Thus this patch should only move that function from one place to another. In which class do you think it should go?

Nathann

comment:29 in reply to: ↑ 28 ; follow-ups: Changed 5 years ago by vbraun

Replying to ncohen:

I took it as a hint that there will never be a working .gap() function on all groups.

Yes. Another possible generic implementation is to call .as_permutation_group().structure_description(), if that is available. But in some cases you'll have to raise NotImplementedError. It is then up to author of that particular group to override structure_description.

Thus this patch should only move that function from one place to another. In which class do you think it should go?

Evidently it should be in sage.groups.group.Group

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

Yes. Another possible generic implementation is to call .as_permutation_group().structure_description(), if that is available.

Only applies to finite groups. And will be meaningless for very large finitely presented groups.

But in some cases you'll have to raise NotImplementedError. It is then up to author of that particular group to override structure_description.

I personally consider this bad design, and this is why I prefer to monkey-patch functions that work rather than inherit broken ones.

Evidently it should be in sage.groups.group.Group

Will you review it if I make the change?

Nathann

comment:31 in reply to: ↑ 30 ; follow-up: Changed 5 years ago by vbraun

Replying to ncohen:

And will be meaningless for very large finitely presented groups.

Everything is impossible to compute once you increase the problem size too far. FP groups are perhaps particularly tricky in that regard since there is no algorithm that necessarily terminates. But you should be allowed to ask the question.

I personally consider this bad design

this = consistent interfaces and specialized implementations in subclasses?

Will you review it if I make the change?

Sure

comment:32 in reply to: ↑ 31 Changed 5 years ago by ncohen

Everything is impossible to compute once you increase the problem size too far.

You are oversimplifying. Some finitely presented groups can be described very easily in either Sage or Gap, and this function can be called quickly too. Turning them into a permutation group is a very bad move.

I personally consider this bad design

this = consistent interfaces and specialized implementations in subclasses?

Calling non implemented or broken functions, and saying that "it is somebody else's problem"

It is then up to author of that particular group to override structure_description.

Nathann

comment:33 in reply to: ↑ 29 Changed 5 years ago by ncohen

Evidently it should be in sage.groups.group.Group

This change does not work: a CyclicPermutationGroup does not inherit from Group. If you wonder how that happens, just look at that and roll your eyes, just like me:

def is_Group(x):
    from sage.groups.old import Group as OldGroup
    return isinstance(x, (Group, OldGroup))

Nathann

comment:34 follow-up: Changed 5 years ago by vbraun

I know. This is why I said that permutation groups need to be switched away from OldGroup.

comment:35 in reply to: ↑ 34 Changed 5 years ago by ncohen

I know. This is why I said that permutation groups need to be switched away from OldGroup.

I see. What do you propose that we do with this ticket, then? I want this feature to make it into Sage, but I cannot rewrite code that I do not understand.

Nathann

comment:36 follow-up: Changed 5 years ago by vbraun

I would just add a method to OldGroup? that calls Group.structure_description (or whatever is appropriate) with a note that it should be removed later.

comment:37 in reply to: ↑ 36 Changed 5 years ago by ncohen

I would just add a method to OldGroup? that calls Group.structure_description (or whatever is appropriate) with a note that it should be removed later.

I am sorry to block this here, but I do not agree with this way of doing things. I can rebase this patch on another ticket if this OldGroup/Group problem is solved soon, but otherwise I prefer this code as it is, as it does not introduce broken methods.

Nathann

comment:38 follow-up: Changed 5 years ago by vbraun

So we'll have a consistent interface as soon as we have monkey-patched every group in Sage, excellent.

comment:39 in reply to: ↑ 38 Changed 5 years ago by ncohen

So we'll have a consistent interface as soon as we have monkey-patched every group in Sage, excellent.

Stop being difficult and let us do something useful: I am telling you that I am willing to help you or whoever will try to rewrite this code. The only thing I cannot do is rewrite it all by myself if you start taking this ticket as a hostage.

My problem is that I do not know nor understand how the group code works. I only want to add a feature, and this is the only way I found to do it without introducing broken functions (I do not want users to call a function and end up with an exception -- to them that is nothing but a bug).

If you are willing to solve the root of the problem, let us do so in another ticket. I will be glad to help.

Nathann

comment:40 Changed 5 years ago by kcrisman

In general I agree with ncohen here. Though:

this is the only way I found to do it without introducing broken functions (I do not want users to call a function and end up with an exception -- to them that is nothing but a bug).

Well, NotImplementedError is a special case, though. Maybe you can make the error message really really obvious that it is GAP which doesn't have this available, not that Sage has some error? Then it takes the sting away - nobody can calculate it, it's not a Sage bug at all, just the user wishing something got calculated that isn't, like an elementary integral to sin(x)/x.

comment:41 Changed 5 years ago by vbraun

  • Branch changed from public/17573 to 294041b72adf4b10f44f913d7439c33c96524eee
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.