#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:  sage8.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 8 months ago by
 Cc tscrim added
comment:2 Changed 7 months ago by
 Milestone changed from sage8.6 to sage8.7
comment:3 Changed 7 months ago by
 Branch set to u/soehms/improve_as_permutation_morphism_26903
comment:4 Changed 7 months ago by
 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:
050c9f2  26903: initial version

comment:5 Changed 7 months ago by
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
comment:6 Changed 7 months ago by
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 followups: ↓ 8 ↓ 12 Changed 7 months ago by
 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 asis. If you agree, then set positive review (and put your name as author).
comment:8 in reply to: ↑ 7 Changed 7 months ago by
 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 asis. 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 followup: ↓ 11 Changed 7 months ago by
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 7 months ago by
 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 7 months ago by
 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 ; followup: ↓ 13 Changed 7 months ago by
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 ; followups: ↓ 14 ↓ 15 Changed 7 months ago by
Replying to soehms:
At least this could by improved if a loop as above would be intergated in
as_permutation_group
around the call ofSmallerDegreePermutationRepresentation
.
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 7 months ago by
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 ofSmallerDegreePermutationRepresentation
.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 ; followup: ↓ 16 Changed 7 months ago by
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 ofSmallerDegreePermutationRepresentation
.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 7 months ago by
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 7 months ago by
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.
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 sagepending or sagewishlist.