Opened 4 years ago

Last modified 3 years ago

#26960 new enhancement

Creating and passing permutation groups and their elements in libgap

Reported by: SimonKing Owned by:
Priority: major Milestone:
Component: interfaces Keywords: libgap permutation group
Cc: dimpase Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

The GAP notation for permutations is a bit strange. A permutation group can, for example, be created like this:

sage: libgap.eval('Group( [ (1,2)(3,8)(4,6)(5,7), (1,3)(2,5)(4,7)(6,8) ] )')
Group([ (1,2)(3,8)(4,6)(5,7), (1,3)(2,5)(4,7)(6,8) ])

Rather than evaluating string, it would be more pythonic to be able to do the following (which currently fails):

sage: libgap.Group( [ ((1,2),(3,8),(4,6),(5,7)), ((1,3),(2,5),(4,7),(6,8)) ] )
Traceback (most recent call last):
...
ValueError: libGAP: Error, usage: Group(<gen>,...), Group(<gens>), Group(<gens>,<id>)

I am not aware of a different pythonic way to create a permutation group in libgap. If there is, please speak up and review this as "duplicate/won't fix".

Change History (15)

comment:1 follow-up: Changed 4 years ago by dimpase

copying from my sage-devel post: What are these permutations, type-wise? Are they Sage permutations, or just strings? The following works:

sage: G=PermutationGroup( [ ((1,2),(3,8),(4,6),(5,7)),
((1,3),(2,5),(4,7),(6,8)) ] )
sage: libgap(G)
Group([ (1,2)(3,8)(4,6)(5,7), (1,3)(2,5)(4,7)(6,8) ])

Unfortunately PermutationGroup(libgap(G)) does not currently work, one needs to dig deeper, to the level of generators. This ought to be fixed.

Also, currently this is done via strings, and there should be a much better way to exchange Sage's and GAP's permutations available, on C level. It's quite doable with libgap, but needs work.

comment:2 in reply to: ↑ 1 Changed 4 years ago by SimonKing

Replying to dimpase:

copying from my sage-devel post: What are these permutations, type-wise?

See ticket description.

Are they Sage permutations, or just strings? The following works:

sage: G=PermutationGroup( [ ((1,2),(3,8),(4,6),(5,7)),
((1,3),(2,5),(4,7),(6,8)) ] )

As you can see in the ticket description, it would be nice if libgap.Group would accept the same input that work for Sage's PermutationGroup.

comment:3 follow-ups: Changed 4 years ago by nbruin

One of the problems is that Gap has a fundamental datatype for "permutation" (with special syntax support!) that Sage does not have. One way to obtain what you request is by letting a python tuple of tuples translate into a permutation in libgap. I think that's a poor match-up. Currently both python tuples and lists get converted into gap lists. There's a bit of a loss there, but if Gap does not have a more suitable translation for a tuple (a permutation cycle certainly isn't), then that's probably the best choice.

The next best thing is a routine (in gap?) that takes a list of lists, interprets it as a cycle product, and returns the product as a permutation in Gap. There is such a routine in Gap 4.10, (but by the looks of it not in 4.8):

https://www.gap-system.org/Manuals/doc/ref/chap42.html#X7B3194EC869D936D

So if we can delay this ticket until libgap is upgraded to 4.10, then we can do simply something like

CycleFromList=libgap.function_factory("CycleFromList")
gens=[((1,2),(3,8),(4,6),(5,7)),((1,3),(2,5),(4,7),(6,8))]
[prod(CycleFromList(c) for c in L) for L in gens]

I would recommend to keep "libgap" as thin as possible: provide only a very faithful interface to and from gap, hopefully with as many useful basic datastructure mappings as possible. Then we can write convenient tools to translate back and forth higher level objects based on that. If we keep that basics of libgap largely independent of sage, I think you'll get the best cooperation from the Gap people in making it work well.

comment:4 in reply to: ↑ 3 ; follow-up: Changed 4 years ago by SimonKing

Replying to nbruin:

So if we can delay this ticket until libgap is upgraded to 4.10, ...

What do you mean by that? Isn't #22626 closed? Does that ticket not upgrade both gap and libgap?

comment:5 in reply to: ↑ 4 Changed 4 years ago by nbruin

Replying to SimonKing:

Replying to nbruin:

So if we can delay this ticket until libgap is upgraded to 4.10, ...

What do you mean by that? Isn't #22626 closed? Does that ticket not upgrade both gap and libgap?

I wasn't aware of that. Then I suggest you investigate using CycleFromList and see if you can build something convenient with that.

comment:6 in reply to: ↑ 3 ; follow-up: Changed 4 years ago by dimpase

Replying to nbruin:

One of the problems is that Gap has a fundamental datatype for "permutation" (with special syntax support!) that Sage does not have.

Sage does have fast permutations (in Cython) as a fundamental datatype, it merely lacks a convenient syntax. So the translation Sage<->GAP ought to be on that level, C arrays to C arrays.

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

Replying to dimpase:

Sage does have fast permutations (in Cython) as a fundamental datatype, it merely lacks a convenient syntax. So the translation Sage<->GAP ought to be on that level, C arrays to C arrays.

I see. Indeed, this works presently:

PermList=libgap.function_factory("PermList")
sage: L=[ ((1,2),(3,8),(4,6),(5,7)), ((1,3),(2,5),(4,7),(6,8)) ]
sage: G=libgap.Group([PermList(Permutation(s)) for s in L])

This looks like a more promising route than using CycleFromList.

It would not be unreasonable to be able to use libgap instead of PermList in the example above, especially if it would shortcut to an efficient conversion. Presently, the conversion of GapElement_Permutation goes via a ListPerm?, so it isn't very efficient either.

I'm also not so sure that currently the element returned by Permutation in Sage is actually a cythonized type. The MRO indicates not.

Should this ticket be the place to track more efficient permutation conversion between sage and libgap?

comment:8 Changed 4 years ago by dimpase

  • Summary changed from Creating a permutation group in libgap to Creating and passing permutations and permutation groups in libgap

how about such a tagline?

comment:9 in reply to: ↑ 7 Changed 4 years ago by dimpase

  • Summary changed from Creating and passing permutations and permutation groups in libgap to Creating and passing permutation groups and their elements in libgap

Replying to nbruin:

Replying to dimpase:

Sage does have fast permutations (in Cython) as a fundamental datatype, it merely lacks a convenient syntax. So the translation Sage<->GAP ought to be on that level, C arrays to C arrays.

I see. Indeed, this works presently:

PermList=libgap.function_factory("PermList")
sage: L=[ ((1,2),(3,8),(4,6),(5,7)), ((1,3),(2,5),(4,7),(6,8)) ]
sage: G=libgap.Group([PermList(Permutation(s)) for s in L])

This looks like a more promising route than using CycleFromList.

It would not be unreasonable to be able to use libgap instead of PermList in the example above, especially if it would shortcut to an efficient conversion. Presently, the conversion of GapElement_Permutation goes via a ListPerm?, so it isn't very efficient either.

I'm also not so sure that currently the element returned by Permutation in Sage is actually a cythonized type. The MRO indicates not.

I don't know what MRO is, but by reading src/sage/groups/perm_gps/permgroup_element.pyx one might see that the actual data for a permutation group element (not to be confused with Permutation) is kept in a C array. Likewise, in GAP permutation group elements are kept in C arrays, which can be accessed/created from libgap with their C API (what we already do for e.g. GAP long integers).

By the way, it seems that Permutation does not use that C array, so converting to/from Permutation won't be fast.

comment:10 follow-up: Changed 4 years ago by nbruin

OK, indeed. In one direction we're there already:

sage: from sage.groups.perm_gps.permgroup_element import SymmetricGroupElement as CyPerm
sage: L=[ ((1,2),(3,8),(4,6),(5,7)), ((1,3),(2,5),(4,7),(6,8)) ]
sage: G=libgap.Group([CyPerm(s) for s in L])

However, the round-trip is a bit off:

sage: a=CyPerm([(1,2,3)])
sage: type(a)
<type 'sage.groups.perm_gps.permgroup_element.SymmetricGroupElement'>
sage: r=libgap(a).sage()
sage: type(r)
<class 'sage.combinat.permutation.StandardPermutations_all_with_category.element_class'>

So it looks like either Permutation needs to be made to convert to libgap automatically as well, or sage.libs.gap.element.GapElement_Permutation.sage needs to be changed to return a SymmetricGroupElement instead.

In addition, perhaps it would be nice to merge the two notions of Permutation in sage? Or are the uses in combinatorics and group theory so different that it warrants different representing objects?

comment:11 in reply to: ↑ 10 ; follow-up: Changed 4 years ago by dimpase

Replying to nbruin:

OK, indeed. In one direction we're there already:

sage: from sage.groups.perm_gps.permgroup_element import SymmetricGroupElement as CyPerm
sage: L=[ ((1,2),(3,8),(4,6),(5,7)), ((1,3),(2,5),(4,7),(6,8)) ]
sage: G=libgap.Group([CyPerm(s) for s in L])

I am not at all sure that this goes directly from the C array in Sage.

However, the round-trip is a bit off:

sage: a=CyPerm([(1,2,3)])
sage: type(a)
<type 'sage.groups.perm_gps.permgroup_element.SymmetricGroupElement'>
sage: r=libgap(a).sage()
sage: type(r)
<class 'sage.combinat.permutation.StandardPermutations_all_with_category.element_class'>

So it looks like either Permutation needs to be made to convert to libgap automatically as well, or sage.libs.gap.element.GapElement_Permutation.sage needs to be changed to return a SymmetricGroupElement instead.

One might implement GapElement_PermutationGroupElement in src/sage/libs/gap/element.pyx, in addition to already present GapElement_Permutation However, it is then unclear what type(libgap.eval('(1,2);')) should be...

In addition, perhaps it would be nice to merge the two notions of Permutation in sage? Or are the uses in combinatorics and group theory so different that it warrants different representing objects?

well, yes and no. One reason for the divergence of the two we see in GAP is historical, the combinatorics of permutations comes from sage-combinat project. Merging would be some work...

comment:12 in reply to: ↑ 11 Changed 4 years ago by nbruin

Replying to dimpase:

One might implement GapElement_PermutationGroupElement in src/sage/libs/gap/element.pyx, in addition to already present GapElement_Permutation

And then prefer that to the present conversion performed by sage? I'd think that's reasonable, since permutations in gap are likely occurring in a group-theoretic context.

However, it is then unclear what type(libgap.eval('(1,2);')) should be...

No, why would that need to change? It gives whatever gap parses it to, wrapped by libgap in the appropriate element class. Are you worried that libgap(eval("(1,2)")) and libgap.eval("(1,2)") have different results?

In addition, perhaps it would be nice to merge the two notions of Permutation in sage? Or are the uses in combinatorics and group theory so different that it warrants different representing objects?

well, yes and no. One reason for the divergence of the two we see in GAP is historical, the combinatorics of permutations comes from sage-combinat project. Merging would be some work...

comment:13 Changed 3 years ago by embray

  • Milestone changed from sage-8.6 to sage-8.7

Retarging tickets optimistically to the next milestone. If you are responsible for this ticket (either its reporter or owner) and don't believe you are likely to complete this ticket before the next release (8.7) please retarget this ticket's milestone to sage-pending or sage-wishlist.

comment:14 Changed 3 years ago by embray

  • Milestone changed from sage-8.7 to sage-8.8

Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)

comment:15 Changed 3 years ago by embray

  • Milestone sage-8.8 deleted

As the Sage-8.8 release milestone is pending, we should delete the sage-8.8 milestone for tickets that are not actively being worked on or that still require significant work to move forward. If you feel that this ticket should be included in the next Sage release at the soonest please set its milestone to the next release milestone (sage-8.9).

Note: See TracTickets for help on using tickets.