Opened 12 months ago

Closed 11 months ago

Last modified 11 months ago

#26903 closed defect (fixed)

Coercion map _permutation_group_morphism must depend on keyword arguments of as_permutation_group

Reported by: soehms Owned by:
Priority: major Milestone: sage-8.7
Component: group theory Keywords: as_permutation_group, coercion
Cc: tscrim Merged in:
Authors: Sebastian Oehms Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 050c9f2 (Commits) Commit:
Dependencies: Stopgaps:

Description

This ticket follows up #25706 which left a problem for the case where as_permutation_group is called with a keyword argument.

Example:

sage: G = Sp(4,3)
sage: P  = G.as_permutation_group(algorithm='smaller')
sage: P1 = G.as_permutation_group()
sage: P1 == P
False
sage: g1, g2 = G.gens()
sage: P(g1*g2)
(1,4,12,30,46,47,62,63,70,2,3,9,23,35,36,60,61,72)(5,6,17,39,65,44,45,71,78,7,8,22,50,57,42,43,69,77)(10,11,28,13,14,29)(15,16,37,67,51,52,54,55,56,20,21,48,68,40,41,59,64,53)(18,19)(24,25,49,31,32,38)(26,27,58,33,34,66)(73,74,80,75,76,79)
sage: P1(g1*g2)
Traceback (most recent call last):
...
TypeError: 'sage.groups.matrix_gps.group_element.MatrixGroupElement_gap' object is not iterable

Change History (17)

comment:1 Changed 12 months ago by soehms

  • Cc tscrim added

comment:2 Changed 11 months 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:3 Changed 11 months ago by soehms

  • Branch set to u/soehms/improve_as_permutation_morphism_26903

comment:4 Changed 11 months ago by soehms

  • Commit set to 050c9f2d8a6b3fbc36595207ffdfb386a2ca003f
  • Status changed from new to needs_review

The example of the description is not reproducible with version 8.6 (but still has been with 8.5). I guess this is caused by the upgrade to GAP 4.10. It seems that the result of as_permutation_group doesn't depend on wether the option is set or not, any more (I didn't find a counter example).

sage: G = Sp(4,3)
sage: P  = G.as_permutation_group(algorithm='smaller')
sage: P1 = G.as_permutation_group()
sage: P1 == P
True

But anyway, I think we should take into account that an option of that method, produces different results. Thus, there is no way out to have that fixed. Now, that we have GroupHomomorphim_libgap working for permutation groups, as well (by #26750), the best way to do that is to rewrite #25706 in the sense of #26750 by using the natural map of the homset.

This is what I pushed to this ticket!


New commits:

050c9f226903: initial version

comment:5 Changed 11 months ago by tscrim

Here is one that depends on the option in 8.6:

sage: P = SO(4,3,-1).as_permutation_group()
sage: Pp = SO(4,3,-1).as_permutation_group(algorithm='smaller')
sage: P
Permutation Group with generators [(1,2,3,6,14,20,15,18,7,16)(4,8,9,17,13,19,5,11,10,12), (1,3,5,12,17,20,18,8,13,10)(2,4,9,16,6,15,19,11,14,7), (2,5,13)(3,7,11)(4,10,16)(6,9,18)(8,12,15)(14,19,17)]
sage: Pp
Permutation Group with generators [(1,8)(2,3,4,6,5,7,9,10,12,11), (1,4,6,9,11,8,10,12,3,5)(2,7), (1,3,6)(2,5,4)(7,11,10)(8,9,12)]
sage: P == Pp
False
sage: P.is_isomorphic(Pp)
True
Last edited 11 months ago by tscrim (previous) (diff)

comment:6 Changed 11 months ago by soehms

That is curious: I can reproduce this ony, if I call the second twice:

sage: SO(4,3,-1).as_permutation_group(algorithm='smaller')
Permutation Group with generators [(1,2,3,6,14,20,15,18,7,16)(4,8,9,17,13,19,5,11,10,12), (1,3,5,12,17,20,18,8,13,10)(2,4,9,16,6,15,19,11,14,7), (2,5,13)(3,7,11)(4,10,16)(6,9,18)(8,12,15)(14,19,17)]
sage: SO(4,3,-1).as_permutation_group(algorithm='smaller')
Permutation Group with generators [(1,5,8,3,6,10,11,4,7,12)(2,9), (1,3,11,4,2,10,7,5,8,9)(6,12), (3,5,4)(7,11,8)]

and it gives another result as in your example (but permanentely the same). Did you use Python 2, as well? What is wrong, here?

comment:7 follow-ups: Changed 11 months ago by tscrim

  • Reviewers set to Travis Scrimshaw

Yes, I am using Python2. Actually, from the GAP documentation, SmallerDegreePermutationRepresentation is not guaranteed to give the same result on each call because it uses random elements. So I do not know of a reliable test to show different outputs. I would consider dropping that part of it and take the ticket as-is. If you agree, then set positive review (and put your name as author).

comment:8 in reply to: ↑ 7 Changed 11 months ago by soehms

  • Authors set to Sebastian Oehms
  • Status changed from needs_review to positive_review

Replying to tscrim:

Yes, I am using Python2. Actually, from the GAP documentation, SmallerDegreePermutationRepresentation is not guaranteed to give the same result on each call because it uses random elements. So I do not know of a reliable test to show different outputs. I would consider dropping that part of it and take the ticket as-is. If you agree, then set positive review (and put your name as author).

I was irritated by the reproducible behavior on my machine, so that I forgot about that. Thanks for the hint and the review!

comment:9 follow-up: Changed 11 months ago by embray

Yes there are many randomized algorithms in GAP, and I think even more since the upgrade to GAP 4.10, which caused many problems in testing as well.

If you want to get a "reproducible" result, one way is to call libgap.set_seed(N) to some specific RNG seed. It's unfortunate though since it's not immediately obvious, at least to users, when these interfaces are using GAP (though it's good to document that if it isn't).

It might be nice if interfaces like this did take additional keyword arguments for passing down to GAP, such as a seed= argument for algorithms that involve RNG.

comment:10 Changed 11 months ago by vbraun

  • Branch changed from u/soehms/improve_as_permutation_morphism_26903 to 050c9f2d8a6b3fbc36595207ffdfb386a2ca003f
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:11 in reply to: ↑ 9 Changed 11 months ago by soehms

  • Commit 050c9f2d8a6b3fbc36595207ffdfb386a2ca003f deleted

Replying to embray:

If you want to get a "reproducible" result, one way is to call libgap.set_seed(N) to some specific RNG seed. It's unfortunate though since it's not immediately obvious, at least to users, when these interfaces are using GAP (though it's good to document that if it isn't).

Thank you for this useful hint.

It might be nice if interfaces like this did take additional keyword arguments for passing down to GAP, such as a seed= argument for algorithms that involve RNG.

I've created ticket #27143 for your suggestion (and already startetd to work on it).

comment:12 in reply to: ↑ 7 ; follow-up: Changed 11 months ago by soehms

Replying to tscrim:

Actually, from the GAP documentation, SmallerDegreePermutationRepresentation is not guaranteed to give the same result on each call because it uses random elements.

Indeed, according to the GAP documentation the following is not a bug:

sage: G = SO(4,3,-1)
sage: libgap.set_seed(0)
0
sage: P = G.as_permutation_group()
sage: for i in range(10):
....:     Pp = G.as_permutation_group(algorithm='smaller')
....:     if P != Pp:
....:         break
....:
sage: i
6

But, is it reasonable to the user, that you have to repeat a statement 6 times to obtain a non trivial result? Maybe, this is o.k. for GAP users. But if we want to be comparable to Maple or Mathematica, I think we should consider this as a bug. But, 6 is not the worse case: In the above example the number of aditional invocations needed for the first 30 values for the initial seed are:

[6, 1, 1, 3, 4, 0, 2, 10, 4, 1, 5, 15, 11, 10, 0, 4, 1, 3, 19, 2, 11, 5, 13, 1, 4, 0, 13, 4, 3, 10]

The chance to get a non trivial result on the first try is just 1:10! So, Travis: you have been lucky to catch it! At least this could by improved if a loop as above would be intergated in as_permutation_group around the call of SmallerDegreePermutationRepresentation.

comment:13 in reply to: ↑ 12 ; follow-ups: Changed 11 months ago by tscrim

Replying to soehms:

At least this could by improved if a loop as above would be intergated in as_permutation_group around the call of SmallerDegreePermutationRepresentation.

That would not work because there might not be a better representation, so looping until a smaller one appears might loop forever. If we loop n times, then we do not get rid of any of the randomness. (In fact, the former might still be random because there could be multiple smaller reprs.) So I think we have to follow GAP here, but we might want to better document this.

comment:14 in reply to: ↑ 13 Changed 11 months ago by soehms

Replying to tscrim:

Replying to soehms:

At least this could by improved if a loop as above would be intergated in as_permutation_group around the call of SmallerDegreePermutationRepresentation.

That would not work because there might not be a better representation, so looping until a smaller one appears might loop forever.

You could limit the loop by an optional argument and explain the problem in its documentation.

If we loop n times, then we do not get rid of any of the randomness. (In fact, the former might still be random because there could be multiple smaller reprs.)

Sure, I did not mean to solve the randomness. But that would improve the chance to find a reduced degree representation. But, that was just a suggestion!

So I think we have to follow GAP here, but we might want to better document this.

I will try to do that in #27143 !

comment:15 in reply to: ↑ 13 ; follow-up: Changed 11 months ago by embray

Replying to tscrim:

Replying to soehms:

At least this could by improved if a loop as above would be intergated in as_permutation_group around the call of SmallerDegreePermutationRepresentation.

That would not work because there might not be a better representation, so looping until a smaller one appears might loop forever. If we loop n times, then we do not get rid of any of the randomness. (In fact, the former might still be random because there could be multiple smaller reprs.) So I think we have to follow GAP here, but we might want to better document this.

What's wrong with having a (largish? smallish?) default number of iterations, with an option to increase it/decrease it as needed (along with appropriate documentation).

comment:16 in reply to: ↑ 15 Changed 11 months ago by tscrim

Replying to embray:

What's wrong with having a (largish? smallish?) default number of iterations, with an option to increase it/decrease it as needed (along with appropriate documentation).

It doesn't remove any randomness; it is only more likely to return a smaller representation (which is not guaranteed to be unique). It also could just end up doing nothing special repeatedly because the representation given in the smallest possible; hence just wasting CPU cycles. I would be more inclined to give a smaller default number of iterations, but I feel it is better to do 1 and instruct the user on how to do more if that is what the user really wants.

comment:17 Changed 11 months ago by soehms

The longer I think about that, the less I understand why SmallerDegreePermutationRepresentation is integrated in as_permutation_group. Wouldn't it be better to wrap this separately by a method (named reduce_degree, for instance) of PermutationGroup_generic? That would have several advantages:

1) It could be used for other permutation groups, as well.

2) The documentation about that strange random behavior, could be better focused.

3) You could recurs as long as the the degree is reduced (not meaning that it will become unique, finally).

This method should return None if no reduction was possible and with two optional arguments seed=None, repeat=0 you could pass the optimization to the user.

Note: See TracTickets for help on using tickets.