Opened 13 months ago

Closed 12 months ago

Last modified 10 months ago

#26750 closed enhancement (fixed)

Use GroupHomset_libgap for permutation groups, as well

Reported by: soehms Owned by:
Priority: major Milestone: sage-8.6
Component: group theory Keywords: permutation group, homomorphism, libgap
Cc: tscrim, sbrandhorst Merged in:
Authors: Sebastian Oehms Reviewers: Simon Brandhorst
Report Upstream: N/A Work issues:
Branch: 66ceb94 (Commits) Commit:
Dependencies: #26420 Stopgaps:

Description

At the moment the construction of group homomorphisms between groups implemented under the classes ParentLibGAP and PermutationGroup_generic (and vice versa) is not possible in sage using the method hom. For example, it isn't possible to construct the natural projection from symplectic groups onto the corresponding projective group although this is possible using GAP:

sage: Sp43 = Sp(4,3)
sage: PSp43 = PSp(4,3)
sage: natProj = Sp43.hom(PSp43.gens())
Traceback (most recent call last):
...
TypeError: unable to convert [(3,4)(6,7)(9,10)(12,13)(17,20)(18,21)(19,22)(23,32)(24,33)(25,34)(26,38)(27,39)(28,40)(29,35)(30,36)(31,37), (1,5,14,17,27,22,19,36,3)(2,6,32)(4,7,23,20,37,13,16,26,40)(8,24,29,30,39,10,33,11,34)(9,15,35)(12,25,38)(21,28,31)] to an element of Set of Morphisms from Symplectic Group of degree 4 over Finite Field of size 3 to The projective symplectic linear group of degree 4 over Finite Field of size 3 in Category of finite groups

The reason for this is that the constructor of the class GroupHomset_libgap explicitly checks both groups to be instances of ParentLibGAP. So an easy way to have hom work in such cases, as well, would be to allow PermutationGroup_generic additionally.

An alternative option is to shift PermutationGroup_generic into the ParentLibGAP framework. But this would cause a lot of work to have all doctests pass through. The main problem here is that the element class of PermutationGroup_generic still has parent as second (optional) argument (in opposite to ParentLibGAP).

Therefore, this ticket will follow the first option!

Change History (37)

comment:1 Changed 13 months ago by soehms

  • Branch set to u/soehms/libgap_morphism_permgroup-26750

comment:2 Changed 13 months ago by soehms

  • Commit set to 28f39df7a269aad93c918b7039a7da68b1869ded
  • Dependencies set to #26420
  • Status changed from new to needs_review

I do the following:

1) I add the method gap to the classes PermutationGroup_generic and PermutationGroupElement to achieve compatibility with class GroupHomset_libgap and its elements class. For the same reason I add the method _subgroup_constructor to PermutationGroup_generic (needed in the methods pushforward, kernel and preimage in GroupMorphism_libgap)

2) I implement the method _Hom_ in PermutationGroup_generic to have hom use class GroupHomset_libgap.

3) In the module libgap_morphism I add PermutationGroup_generic to the list of allowed parent-instances at all relevant pieces of code. Furthermore, I changed the _element_constructor_ in order to avoid buffer size overflow by transferring long lists of large permutation generators to GAP. This is done in a new local method _obtain_gap_hom.

4) I take the occasion to implement two methods from framework: section of class Map and natural_map of class HomsetWithBase improving their default implementation using the possibilities of GroupHomset_libgap and its element class.


New commits:

841a405group morphism constructor from a libgap morphism
08a0735a doctest
b2d9622docs
21cb664correct docstring for argument `gap_hom`
2a432d0Merge commit '21cb66449cd424f94d15bd695fa986a0ce40c30c' of git://trac.sagemath.org/sage into libgap_morphism_permgroup-26750
28f39dfinitial version

comment:3 Changed 13 months ago by sbrandhorst

I am not convinced the function _obtain_gap_hom is useful/necessary. It seems to be used only for the natural_map method. But then the code just belongs there. But indeed one could replace

gens = [g.gap() for g in dom.gens()]

by

gens = dom.gap().GeneratorsOfGroup()

in the _element_constructor_ and likewise for the images in natural map. Would that fix the overflow?

comment:4 Changed 13 months ago by git

  • Commit changed from 28f39df7a269aad93c918b7039a7da68b1869ded to deaa64722319dc847871b77b15cab2efbb972850

Branch pushed to git repo; I updated commit sha1. New commits:

deaa647remove unnecessary method _obtain_gap_hom

comment:5 Changed 13 months ago by soehms

Thanks for looking at this, Simon! Of course you are right: This method has been a stupid idea! I corrected as you suggested.

comment:6 Changed 13 months ago by git

  • Commit changed from deaa64722319dc847871b77b15cab2efbb972850 to 2b74ce465c362921430ba0b58b7c5e207ad3241d

Branch pushed to git repo; I updated commit sha1. New commits:

0133335implement subgroup / ambient methods for MatrixGroup_base
747bc16removed unused keyword
c3a92a4Merge branch 'develop' into matrix_groups_subgroups-25894
901441bMerge branch 'develop' into matrix_groups_subgroups-25894
b02eb31Merge branch 'libgap_morphism_permgroup-26750' into cubic_braid_group
be4674binitial implementation
6a07854Merge branch 'develop' into adapt_unitary_burau-26657
806d0c6Merge branch 'adapt_unitary_burau-26657' into cubic_braid_group
464b784Merge branch 'libgap_morphism_permgroup-26750' into cubic_braid_group
2b74ce4restore deleted doctest

comment:7 Changed 13 months ago by soehms

New commits:

0133335implement subgroup / ambient methods for MatrixGroup_base
747bc16removed unused keyword
c3a92a4Merge branch 'develop' into matrix_groups_subgroups-25894
901441bMerge branch 'develop' into matrix_groups_subgroups-25894
b02eb31Merge branch 'libgap_morphism_permgroup-26750' into cubic_braid_group
be4674binitial implementation
6a07854Merge branch 'develop' into adapt_unitary_burau-26657
806d0c6Merge branch 'adapt_unitary_burau-26657' into cubic_braid_group
464b784Merge branch 'libgap_morphism_permgroup-26750' into cubic_braid_group
2b74ce4restore deleted doctest

comment:8 Changed 13 months ago by soehms

New commits:

0133335implement subgroup / ambient methods for MatrixGroup_base
747bc16removed unused keyword
c3a92a4Merge branch 'develop' into matrix_groups_subgroups-25894
901441bMerge branch 'develop' into matrix_groups_subgroups-25894
b02eb31Merge branch 'libgap_morphism_permgroup-26750' into cubic_braid_group
be4674binitial implementation
6a07854Merge branch 'develop' into adapt_unitary_burau-26657
806d0c6Merge branch 'adapt_unitary_burau-26657' into cubic_braid_group
464b784Merge branch 'libgap_morphism_permgroup-26750' into cubic_braid_group
2b74ce4restore deleted doctest

comment:9 Changed 13 months ago by soehms

I think I need some help. I wanted to restore the doctest of _obtain_gap_hom in _element_constructor_ but pushed from the wrong branch.

How can I go back to commit deaa64722319dc847871b77b15cab2efbb972850?

comment:10 Changed 13 months ago by git

  • Commit changed from 2b74ce465c362921430ba0b58b7c5e207ad3241d to 68582de9123703c95fcc065e56599da12e87ec9d

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

68582derestore deleted doctest

comment:11 Changed 13 months ago by soehms

I think I got it!

comment:12 Changed 13 months ago by sbrandhorst

in the _element_constructor method:

if list(x) == codom.gens():
    # avoid buffer size overflow in the interface
    imgs = codom.gap().GeneratorsOfGroup()

this seems to fit better with the natural_map method? Put it there.

comment:13 Changed 13 months ago by git

  • Commit changed from 68582de9123703c95fcc065e56599da12e87ec9d to a119816b247bfcfe18330326067e2f908b342b04

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

a119816revert changes in _element_constructor_ and improve method gap of permutation groups

comment:14 Changed 13 months ago by soehms

Thanks for your useful hints, Simon! There where two problems:

1) I provided the wrong example, so that you did not have a chance to see what these lines of code should be good for. The correct example needs to have an instance of PermutationGroup_subgroup as codomain and be large enough to produce:

python2: libgap.c:184: libgap_get_input: Assertion `strlen(libGAP_stdin_buffer) < length' failed

2) The origin for this error, has not been in the _element_constructor_ method. So any changes here where useless, as you pointed out. Actually, the problem was that GAP didn't know about the subgroup construction.

So I revert all changes of code with respect to the _element_constructor_ and provide the example which caused the trouble in its docstring. I inserted a line of code in the constructor of the PermutationGroup_subgroup class to have the gap method of such a subgroup work well. This line I explain by a doctest in gap.

In addition I change the implementation of gap, since I realized that the former one can cause pickling errors.

comment:15 Changed 13 months ago by soehms

  • Branch u/soehms/libgap_morphism_permgroup-26750 deleted
  • Commit a119816b247bfcfe18330326067e2f908b342b04 deleted

comment:16 Changed 13 months ago by soehms

  • Branch set to u/soehms/libgap_morphism_permgroup_26750

comment:17 follow-up: Changed 13 months ago by sbrandhorst

  • Commit set to e1e4da03582f9674e1628a02e6b502d9dfdcee85

It seems you are caching twice here. Once with the decorator once inside the method.

@cached_method
def gap(self):

New commits:

e1e4da0resetting to a new branch because of merge error

comment:18 in reply to: ↑ 17 ; follow-up: Changed 13 months ago by soehms

Replying to sbrandhorst:

It seems you are caching twice here. Once with the decorator once inside the method.

@cached_method
def gap(self):

New commits:

e1e4da0resetting to a new branch because of merge error

I inserted the decorator since I removed the explixit caching via the _libgap attribute (since this caused pickling problems). I am not aware that there is an implicite caching mechanism via the element construction of class Gap. Can you explain how this is working?

comment:19 Changed 12 months ago by dimpase

I've linked this ticket to #26902, which aims at planning and tracking conversion of Sage library code from pexpect gap to libgap.

comment:20 Changed 12 months ago by dimpase

Could you take care of pyflakes' advice (see patchbot output) and remove unneeded imports:

========== pyflakes ==========
git checkout patchbot/ticket_merged
src/sage/categories/homset.py:73: 'sage.misc.constant_function.ConstantFunction' imported but unused
src/sage/categories/homset.py:75: 'types' imported but unused
found 2 pyflakes errors in the modified files

comment:21 in reply to: ↑ 18 ; follow-up: Changed 12 months ago by sbrandhorst

Replying to soehms:

I inserted the decorator since I removed the explixit caching via the _libgap attribute (since this caused pickling problems). I am not aware that there is an implicite caching mechanism via the element construction of class Gap. Can you explain how this is working?

It still seems to be there:

+    @cached_method
+    def gap(self):
+        if self._libgap is not None:
+            return self._libgap
+        from sage.libs.gap.libgap import libgap
+        return libgap(self)

To me it looks like there are 2 caches once via the _libgap attribute and once in the @cached method Say if one first calls .gap() and then the _libgap attribute is set somewhere

comment:22 in reply to: ↑ 21 Changed 12 months ago by soehms

Replying to sbrandhorst:

Replying to soehms: To me it looks like there are 2 caches once via the _libgap attribute and once in the @cached method Say if one first calls .gap() and then the _libgap attribute is set somewhere

In general it isn't cached via that attribute (I've removed that in my last change):

sage: S = SymmetricGroup(6)
sage: print S._libgap
None
sage: S.gap()
Sym( [ 1 .. 6 ] )
sage: print S._libgap
None

comment:23 Changed 12 months ago by git

  • Commit changed from e1e4da03582f9674e1628a02e6b502d9dfdcee85 to 5b2c3816259709db4e033bef1c3ca0ff14abfd21

Branch pushed to git repo; I updated commit sha1. New commits:

70a87bfMerge branch 'develop' into libgap_morphism_permgroup_26750
4f4ec99Merge branch 'develop' into libgap_morphism_permgroup_26750
5b2c381removed import statements according to pyflakes hints

comment:24 Changed 12 months ago by sbrandhorst

+        from sage.libs.gap.element import GapElement_Permutation
+        if isinstance(img_gap, GapElement_Permutation):
+            return self.codomain()(img_gap.sage())

What happens here is a conversion of a gap element to an element of a permutation group. It would be more useful to let this be handled by the permuation group code i.e. in the element constructor of permutation groups and not in the _call_ method of the morphism. Also there are a few little python style remarks for the doctests, like

+            sage: GS=G.subgroup([G.gen(0)])

should be

+            sage: GS = G.subgroup([G.gen(0)])

comment:25 Changed 12 months ago by sbrandhorst

  • Branch changed from u/soehms/libgap_morphism_permgroup_26750 to u/sbrandhorst/libgap_morphism_permgroup_26750

comment:26 Changed 12 months ago by soehms

  • Branch changed from u/sbrandhorst/libgap_morphism_permgroup_26750 to u/soehms/libgap_morphism_permgroup_26750

comment:27 Changed 12 months ago by soehms

  • Commit changed from 5b2c3816259709db4e033bef1c3ca0ff14abfd21 to 09b469601aa8cad0fa1f51baf225a8fb807eaa0a

I follow your suggestion concerning the _call_ method and I revert one of your style changes because of a failing doctest (see patchbot).


New commits:

54a7f1bMerge branch 'develop' into t/26750/libgap_morphism_permgroup_26750
8bd5effcosmetic changes to the docs
09b4696move conversion to element construction of permutation

comment:28 Changed 12 months ago by sbrandhorst

  • Branch changed from u/soehms/libgap_morphism_permgroup_26750 to u/sbrandhorst/libgap_morphism_permgroup_26750

comment:29 follow-up: Changed 12 months ago by sbrandhorst

  • Commit changed from 09b469601aa8cad0fa1f51baf225a8fb807eaa0a to e0feb001f33e1f78efd180d38a6ddbbe6741ebeb

Positive review if you are happy with my changes & we have a green bot


New commits:

e0feb00changes to docs and the permutation group and subgroup constructor

comment:30 follow-up: Changed 12 months ago by sbrandhorst

btw. if you split up your tickets into smaller ones, they are easier to review

comment:31 Changed 12 months ago by soehms

  • Branch changed from u/sbrandhorst/libgap_morphism_permgroup_26750 to u/soehms/libgap_morphism_permgroup_26750

comment:32 in reply to: ↑ 29 Changed 12 months ago by soehms

  • Commit changed from e0feb001f33e1f78efd180d38a6ddbbe6741ebeb to 66ceb94036041b2bf05e1f4abf91ea8bdeac862a
  • Reviewers set to Simon Brandhorst

Replying to sbrandhorst:

Positive review if you are happy with my changes & we have a green bot


New commits:

e0feb00changes to docs and the permutation group and subgroup constructor

This is a good improvement in order to get the permutation groups closer to libgap! I just do two doc-string adaptions and rename your GapElement since that name is already used globally with respect to sage.interfaces.gap

Thanks for the review, Simon. I wish you a merry Christmas!


New commits:

66ceb94adapt doc-strings to former change and ticket #26889

comment:33 in reply to: ↑ 30 Changed 12 months ago by soehms

Replying to sbrandhorst:

btw. if you split up your tickets into smaller ones, they are easier to review

Sure! I will try to take care of that the next time!

comment:34 Changed 12 months ago by soehms

  • Status changed from needs_review to positive_review

comment:35 Changed 12 months ago by vbraun

  • Branch changed from u/soehms/libgap_morphism_permgroup_26750 to 66ceb94036041b2bf05e1f4abf91ea8bdeac862a
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:36 Changed 12 months ago by embray

  • Commit 66ceb94036041b2bf05e1f4abf91ea8bdeac862a deleted
  • Milestone changed from sage-8.5 to sage-8.6

comment:37 Changed 10 months ago by soehms

I've created a follow up ticket #27234 since by the improvements in connection with GAP 4.10 upgrade, the implementation of the gap method of class PermutationGroupElement can be done properly, right now.

Note: See TracTickets for help on using tickets.