Computing orbits of different actions (through gap)

[Jernej]

Hello!

I have a few questions concerning GAP interface in Sage 7.x.

I have a permutation group G acting on a set S and I would like to compute the representatives of the orbits of G acting on k-sets of S. 

I recall that a while ago I could do the following (as seen on this example http://ask.sagemath.org/question/9652/orbits-on-group-actions-acting-on-sets/?answer=14470#post-id-14470)

====

sage: g=SymmetricGroup(7)  

sage: gap("Orbits("+str(g._gap_())+","+str(tuples([1..7],2))+",OnTuples)")

====

and yes, it works in Sage 6.x. However, in Sage 7.x one gets the following error 

====

TypeError: Gap terminated unexpectedly while reading in a large line:

Gap produced error output

Error, Permutation: cycles must be disjoint and duplicate-free

====

Given this, I have the following questions

- What is the proper way to call gap in Sage 7x t obtain the orbits of a group G acting on k-sets of a set S?

  - (GAP question) I recall there is a way to return only the representatives of the orbits? Anyone happens to recall the right GAP command for that?

- Does it make sense to add an option for various group actions to Sage directly (as is already done for specific orbits ) ?

Best,

Jernej

[Dima Pasechnik]

use libgap:

sage: g=libgap.SymmetricGroup(7)

sage: g.Orbits(tuples([1..7],2),libgap.OnTuples)

[ [ [ 1, 1 ], [ 2, 2 ], [ 3, 3 ], [ 4, 4 ], [ 5, 5 ], [ 6, 6 ], [ 7, 7 ] ], [ [ 1, 2 ], [ 2, 3 ], [ 2, 1 ], [ 3, 4 ], [ 1, 3 ], [ 3, 2 ], [ 4, 5 ], [ 2, 4 ], [ 4, 3 ], [ 3, 1 ], [ 5, 6 ], [ 3, 5 ], [ 1, 4 ], [ 5, 4 ], [ 4, 2 ], [ 6, 7 ], [ 4, 6 ], [ 2, 5 ], [ 6, 5 ], [ 5, 3 ], [ 4, 1 ], [ 7, 1 ], [ 5, 7 ], [ 3, 6 ], [ 1, 5 ], [ 7, 6 ], [ 6, 4 ], [ 5, 2 ], [ 7, 2 ], [ 6, 1 ], [ 4, 7 ], [ 2, 6 ], [ 1, 7 ], [ 7, 5 ], [ 6, 3 ], [ 5, 1 ], [ 6, 2 ], [ 3, 7 ], [ 1, 6 ], [ 2, 7 ], [ 7, 4 ], [ 7, 3 ] ] ]

[Dima Pasechnik]

On Tuesday, March 22, 2016 at 1:09:07 PM UTC, Dima Pasechnik wrote:

use libgap:

sage: g=libgap.SymmetricGroup(7)

sage: g.Orbits(tuples([1..7],2),libgap.OnTuples)

[ [ [ 1, 1 ], [ 2, 2 ], [ 3, 3 ], [ 4, 4 ], [ 5, 5 ], [ 6, 6 ], [ 7, 7 ] ], [ [ 1, 2 ], [ 2, 3 ], [ 2, 1 ], [ 3, 4 ], [ 1, 3 ], [ 3, 2 ], [ 4, 5 ], [ 2, 4 ], [ 4, 3 ], [ 3, 1 ], [ 5, 6 ], [ 3, 5 ], [ 1, 4 ], [ 5, 4 ], [ 4, 2 ], [ 6, 7 ], [ 4, 6 ], [ 2, 5 ], [ 6, 5 ], [ 5, 3 ], [ 4, 1 ], [ 7, 1 ], [ 5, 7 ], [ 3, 6 ], [ 1, 5 ], [ 7, 6 ], [ 6, 4 ], [ 5, 2 ], [ 7, 2 ], [ 6, 1 ], [ 4, 7 ], [ 2, 6 ], [ 1, 7 ], [ 7, 5 ], [ 6, 3 ], [ 5, 1 ], [ 6, 2 ], [ 3, 7 ], [ 1, 6 ], [ 2, 7 ], [ 7, 4 ], [ 7, 3 ] ] ]

if you only need representatives, you can just use map:

map(lambda x: x[0], g.OrbitsDomain(tuples([1..7],2),libgap.OnTuples))

(Here I used OrbitsDomain, which you should use for efficiency if you know that your set is invariant under your

group) 

[Jernej]

Hello!

Thanks! I wasn't aware of libgap! One more followup question. Say I want to compute the orbits of the CubeGraph of order 10. The description of  respective automorphism group seems to be to heave for libgap

====

sage: G = graphs.CubeGraph(10)

sage: G.relabel()

sage: A = G.automorphism_group()

sage: libgap(A)

python: libgap.c:186: libgap_get_input: Assertion `strlen(libGAP_stdin_buffer) < length' failed.

===

Is there a way to overcome this limitation?

Best,

Jernej

[Dima Pasechnik]

On Wednesday, March 23, 2016 at 11:10:42 PM UTC, Jernej wrote:

Hello!

Thanks! I wasn't aware of libgap! One more followup question. Say I want to compute the orbits of the CubeGraph of order 10. The description of  respective automorphism group seems to be to heave for libgap

====

sage: G = graphs.CubeGraph(10)

sage: G.relabel()

sage: A = G.automorphism_group()

sage: libgap(A)

python: libgap.c:186: libgap_get_input: Assertion `strlen(libGAP_stdin_buffer) < length' failed.

===

Is there a way to overcome this limitation?

sage: G = graphs.CubeGraph(10)

sage: A = G.automorphism_group()

sage: T=libgap.Group(map(libgap,A.gens()))

sage: T.Order()

3715891200

works.

There is probably a fixed side buffer somewhere that is not big enough for passing the whole of A

directly.

[Dima Pasechnik]

On Thursday, March 24, 2016 at 6:36:55 AM UTC, Dima Pasechnik wrote:

On Wednesday, March 23, 2016 at 11:10:42 PM UTC, Jernej wrote:

Hello!

Thanks! I wasn't aware of libgap! One more followup question. Say I want to compute the orbits of the CubeGraph of order 10. The description of  respective automorphism group seems to be to heave for libgap

====

sage: G = graphs.CubeGraph(10)

sage: G.relabel()

sage: A = G.automorphism_group()

sage: libgap(A)

python: libgap.c:186: libgap_get_input: Assertion `strlen(libGAP_stdin_buffer) < length' failed.

===

Is there a way to overcome this limitation?

sage: G = graphs.CubeGraph(10)

sage: A = G.automorphism_group()

sage: T=libgap.Group(map(libgap,A.gens()))

sage: T.Order()

3715891200

works.

There is probably a fixed side buffer somewhere that is not big enough for passing the whole of A

directly.

 

I suppose it is the assertion here:

 

https://bitbucket.org/vbraun/libgap/src/0273a81b021a35ff6ce18d8a2c41be5144c872c3/src/libgap.c?at=master&fileviewer=file-view-default#libgap.c-184 

perhaps Volker knows the problem behind this error.

[Jernej]

Thanks. I wasn't aware that passing the group to libgap will actually try to pass all of its elements to gap! Continuing on the topic though I have two new questions about this libgap magic.

When doing g.Orbits(tuples([1..7],2),libgap.OnTuples) are the tuples actually computed in Sage and passed to gap? The reason I am trying to call directly is to make sure this is computed in gap, where I am (blindly) assuming it's faster.

Finally, if I want to repeat the example using combinations it seems that the obvious conversion fails

g.Orbits(combinations([1..7],2),libgap.OnSets)

gives the (expected) NameError: name 'combinations' is not defined, 

capitalizing combinations gives

ValueError: libGAP: Syntax error: ; expected

Combinations of [1, 2, 3, 4, 5, 6, 7] of length 2;

Best,

Jernej

[Dima Pasechnik]

On Thursday, March 24, 2016 at 2:20:56 PM UTC, Jernej wrote:

Thanks. I wasn't aware that passing the group to libgap will actually try to pass all of its elements to gap!

It does not pass all of its elements, certainly. 

It passes the generators, as a string, and this string is too long in your example. The workaround I suggested passes each generator separately.

So this would also break on groups with about 10 higher degree...

 

Continuing on the topic though I have two new questions about this libgap magic.

When doing g.Orbits(tuples([1..7],2),libgap.OnTuples) are the tuples actually computed in Sage and passed to gap? The reason I am trying to call directly is to make sure this is computed in gap, where I am (blindly) assuming it's faster.

here, naturally, tuples() is a Python function.

 

Finally, if I want to repeat the example using combinations it seems that the obvious conversion fails

g.Orbits(combinations([1..7],2),libgap.OnSets)

gives the (expected) NameError: name 'combinations' is not defined, 

capitalizing combinations gives

ValueError: libGAP: Syntax error: ; expected

Combinations of [1, 2, 3, 4, 5, 6, 7] of length 2;

GAP functions need a prefix

sage: g.Orbits(libgap.Combinations([1..7],2),libgap.OnTuples)

[ [ [ 1, 2 ], [ 2, 3 ], [ 2, 1 ], [ 3, 4 ], [ 1, 3 ], [ 3, 2 ], [ 4, 5 ], [ 2, 4 ], [ 4, 3 ], [ 3, 1 ], [ 5, 6 ], [ 3, 5 ], [ 1, 4 ], [ 5, 4 ], [ 4, 2 ], [ 6, 7 ], [ 4, 6 ], [ 2, 5 ], [ 6, 5 ], [ 5, 3 ], [ 4, 1 ], [ 7, 1 ], [ 5, 7 ], [ 3, 6 ], [ 1, 5 ], [ 7, 6 ], [ 6, 4 ], [ 5, 2 ], [ 7, 2 ], [ 6, 1 ], [ 4, 7 ], [ 2, 6 ], [ 1, 7 ], [ 7, 5 ], [ 6, 3 ], [ 5, 1 ], [ 6, 2 ], [ 3, 7 ], [ 1, 6 ], [ 2, 7 ], [ 7, 4 ], [ 7, 3 ] ] ]

alternatively, you could do (almost) the same as follows:

sage: g.Orbits(libgap([1..7]).Combinations(2),libgap.OnTuples)

By the way, we have a recent trac ticket allowing to get rid of libgap. prefix, but it's not

merged (yet).