Creating and passing permutation groups and their elements in libgap

[simon-king-jena]

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

CC: @dimpase

Component: interfaces

Keywords: libgap permutation group

Issue created by migration from https://trac.sagemath.org/ticket/26960

[dimpase]

comment:1

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.

[simon-king-jena]

comment:2

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.

[nbruin]

comment:3

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.

[simon-king-jena]

comment:4

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?

[nbruin]

comment:5

Replying to @simon-king-jena:

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.

[dimpase]

comment:6

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.

[nbruin]

comment:7

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?

[dimpase]

comment:8

how about such a tagline?

[dimpase]

comment:9

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.

[nbruin]

comment:10

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?

[dimpase]

comment:11

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

[nbruin]

comment:12

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

[embray]

comment:13

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.

[embray]

comment:14

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

[embray]

comment:15

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