Implementing minimum_generating_set() function

[Ruchit Jagodara]

I am implementing the minimum_generating_set function in Sage, but I am facing some issues, such as where I should implement that function as my implementation uses some gap methods. And I found one class ParentLibGAP which can be used for this but I am not sure because I found that PermutationGroup class is not derived from this class so if I implement this function here then function will not be available for this group (And I don't know if there are many more), plus I have to use some functions of GroupMixinLibGAP class, so can you please suggest me a location or any fix for this. 

[Ruchit Jagodara]

And to implement the function, I want a function that takes a list of generators and returns a group. Does anyone know of any function that can do this?

[Dima Pasechnik]

Functions such as Group(), PermutationGroup() take such lists as inputs.

[Ruchit Jagodara]

Actually, that won't work according to the implementation. Can you please take a look at the code I wrote (although I have not written it according to codestyle of sage, yet. But I will do that when the code starts working.), where minimum_generating_set is the main function?  

Link- https://github.com/RuchitJagodara/sage/blob/8b642329b6d579c536511d5f1d1511fb842c9c54/src/sage/groups/libgap_wrapper.pyx#L405C1-L513C1

I have implemented this code according to the research paper.
The algorithm can find the minimum generating set in polynomial time, which is very cool! So, I thought it would be good to implement this in Sage, especially since the paper has been recently published.

I've almost completed the code, but I'm unsure about how to find the Quotient group and its representative elements. I need help with this.

I've outlined my doubts in the code, which you can see in the following link:-

https://github.com/RuchitJagodara/sage/blob/8b642329b6d579c536511d5f1d1511fb842c9c54/src/sage/groups/libgap_wrapper.pyx#L478-L486 

GAP has a function named RightCosets that can be used to form a quotient group, but there is a problem: how can I find representative elements of that group? Additionally, how can I create a Quotient group using RightCosets in Sage, given that the algorithm uses a recursive call, and the quotient group must have the ParentLibGAP.minimum_generating_set function?

[Dima Pasechnik]

On Thu, Jan 18, 2024 at 11:39 AM 'Ruchit Jagodara' via sage-devel
<sage-...@googlegroups.com> wrote:
>
> Actually, that won't work according to the implementation.

sorry, I don't understand what won't work.
Did you mean to ask a different question?

> Can you please take a look at the code I wrote (although I have not written it according to codestyle of sage, yet. But I will do that when the code starts working.), where minimum_generating_set is the main function?
>
> Link- https://github.com/RuchitJagodara/sage/blob/8b642329b6d579c536511d5f1d1511fb842c9c54/src/sage/groups/libgap_wrapper.pyx#L405C1-L513C1
>
> I have implemented this code according to the research paper.

Sorry, what paper are you talking about?

> The algorithm can find the minimum generating set in polynomial time, which is very cool! So, I thought it would be good to implement this in Sage, especially since the paper has been recently published.
>
> I've almost completed the code, but I'm unsure about how to find the Quotient group and its representative elements. I need help with this.
>
> I've outlined my doubts in the code, which you can see in the following link:-
>
> https://github.com/RuchitJagodara/sage/blob/8b642329b6d579c536511d5f1d1511fb842c9c54/src/sage/groups/libgap_wrapper.pyx#L478-L486
>
> GAP has a function named RightCosets that can be used to form a quotient group, but there is a problem: how can I find representative elements of that group? Additionally, how can I create a Quotient group using RightCosets in Sage, given that the algorithm uses a recursive call, and the quotient group must have the ParentLibGAP.minimum_generating_set function?
> On Wednesday, January 17, 2024 at 2:35:55 PM UTC+5:30 Dima Pasechnik wrote:
>>
>> Functions such as Group(), PermutationGroup() take such lists as inputs.
>>
>>
>> On 17 January 2024 06:35:07 GMT, 'Ruchit Jagodara' via sage-devel <sage-...@googlegroups.com> wrote:
>>>
>>> And to implement the function, I want a function that takes a list of generators and returns a group. Does anyone know of any function that can do this?
>>> On Friday, January 12, 2024 at 8:38:18 PM UTC+5:30 Ruchit Jagodara wrote:
>>>>
>>>> I am implementing the minimum_generating_set function in Sage, but I am facing some issues, such as where I should implement that function as my implementation uses some gap methods. And I found one class ParentLibGAP which can be used for this but I am not sure because I found that PermutationGroup class is not derived from this class so if I implement this function here then function will not be available for this group (And I don't know if there are many more), plus I have to use some functions of GroupMixinLibGAP class, so can you please suggest me a location or any fix for this.
>

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/db166267-6491-42e3-bc58-01ea447a5c9bn%40googlegroups.com.

[Ruchit Jagodara]

In case my questions have caused any confusion, I am rephrasing them as below.

I have a group G and its minimal normal subgroup N.

I want to find G/N. Do you know how I can do that? (I also want G/N to be an object of the same class as G.)

My another question is: How can I find the group operation of a group G?

[Dima Pasechnik]

On 19 January 2024 15:18:45 GMT, 'Ruchit Jagodara' via sage-devel <sage-...@googlegroups.com> wrote:
>In case my questions have caused any confusion, I am rephrasing them as
>below.
>
>I have a group G and its minimal normal subgroup N.
>
>I want to find G/N. Do you know how I can do that? (I also want G/N to be
>an object of the same class as G.)

It's G.quotient(N), no?

[Ruchit Jagodara]

I think this is giving a group isomorphic to the actual quotient group but I need the actual quotient group. Therefor, I don't know how to find that exact group. Below is one example,

sage: p = PermutationGroup([(2,3,4,5,6,7)])
sage: N = p.minimal_normal_subgroups()[0]
sage: N
Subgroup generated by [(2,5)(3,6)(4,7)] of (Permutation Group with generators [(2,3,4,5,6,7)])
sage: N.list()
[(), (2,5)(3,6)(4,7)]
sage: p.quotient(N)
Permutation Group with generators [(1,2,3)]
sage: _.list()
[(), (1,2,3), (1,3,2)]

If this is the collection of representative elements(for cosets) then ``1`` should not be in any of the permutations.

I need a quotient group structure whose elements(the cosets) have the representative element (from the original group) and the normal subgroup (which was used to create the quotient group) as their properties or available in some other form.

[David Roe]

You can lift elements via the quotient map to get representatives of each coset.  I'm not sure that this is wrapped in Sage, but using gap directly you have:

sage: Pgap = p._libgap_()
sage: Ngap = N._libgap_()
sage: phi = Pgap.NaturalHomomorphismByNormalSubgroup(Ngap); phi

[ (2,3,4,5,6,7) ] -> [ f1^2 ]

sage: PN = phi.ImagesSource() # the quotient as an isomorphic group

sage: preimages_gens = [phi.PreImagesRepresentative(g) for g in PN.GeneratorsOfGroup()]
sage: preimages_gens
[(2,4,6)(3,5,7)]
sage: all_preimages = [phi.PreImagesRepresentative(g) for g in PN.List()]
sage: all_preimages
[(), (2,4,6)(3,5,7), (2,6,4)(3,7,5)]

David

To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/2119b5d7-b98d-4edb-acb7-3e7704cbaffen%40googlegroups.com.

[Ruchit Jagodara]

So, why is the quotient function implemented in Sage is giving RegularActionHomomorphism of G/N ? Is there any particular reason for it?  Should I change it (because I found a FIXME note also, saying that gap has a better way to find quotient)? I am implementing some functions related to group theory, and I can work on this as well.

[David Joyner]

On Sat, Feb 3, 2024 at 1:13 PM 'Ruchit Jagodara' via sage-devel <sage-...@googlegroups.com> wrote:

So, why is the quotient function implemented in Sage is giving RegularActionHomomorphism of G/N ? Is there any particular reason for it?  Should I change it (because I found a FIXME note also, saying that gap has a better way to find quotient)? I am implementing some functions related to group theory, and I can work on this as well.

The function quotient in the PermutationGroups class is returning another instance of that class. What you want is in a different Python class. Instead of "fixing" the quotient function, you can simply implement another quotient function, call it quotient_to_cosets or something like that. 

 

To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/41e28657-e22b-4cdc-846b-87cf6c4870d8n%40googlegroups.com.

[Ruchit Jagodara]

Okay , thank you for your help ! : )

[Dima Pasechnik]

GAP has a function, FactorCosetAction(), for action on cosets of a subgroup. I don't think there is a need to   implement anything of this sort directly,  and not use it via libgap.

https://docs.gap-system.org/doc/ref/chap41.html#X7FED50ED7ACA5FB2

[Ruchit Jagodara]

Okay, then I will leave it as it is. thanks : )