Opened 4 years ago

# Creating and passing permutation groups and their elements in libgap

Reported by: Owned by: SimonKing major interfaces libgap permutation group dimpase N/A

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

### comment:1 follow-up: ↓ 2 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

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: ↓ 4 ↓ 6 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):

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: ↓ 5 Changed 4 years ago by SimonKing

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

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: ↓ 7 Changed 4 years ago by dimpase

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: ↓ 9 Changed 4 years ago by nbruin

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

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

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: ↓ 11 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: ↓ 12 Changed 4 years ago by dimpase

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

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.