## Where communities thrive

• Join over 1.5M+ people
• Join over 100K+ communities
• Free without limits
##### Activity
Mohit Gupta
@mohitacecode
okay I will first look for adding small functionalities maybe I will get familiar with the code much faster this way and will be able to estimate the right and sufficient amount of work for one summer.

I think there is an existing method in SymPy to check the normality of permutation groups.

Yes It is there as is_normal.

Mohit Gupta
@mohitacecode

Hello Kalevi,
Good morning I was thinking about adding a functions to check whether a group is a hall subgroups or not (https://en.wikipedia.org/wiki/Hall_subgroup.

Since we have all the required method that we need to implement a test for hall subgroups it will not take much time.
this is the possible algorithm I am thinking:

is_hall_subgroups(H,G):
#We want to check if H is a hall subgroups and H is the subgroup of G where G should be a finite group.
1.)check if G is a finite groups
2.)find the order of H.(Ord)
3.)find the index for H.(ind)
4.)If gcd(Ord,Ind) is 1 then H is a hall_subgroup.(gcd = Greatest Common Divisor)
Kalevi Suominen
@jksuom
Have you some idea of where it would be useful to know that a subgroup is Hall subgroup?
Mohit Gupta
@mohitacecode

I suggest this because there was a Computation of Hall Subgroup idea proposed in last year gsoc proposal but due to time constraint it was not implemented So I was looking to implement that but while looking I found this hall subgroup property so i was thinking it may be helpfull to add it but after a thorough research I didnt find it helpfull.

do we also need Computation of Hall Subgroup ?

Kalevi Suominen
@jksuom
Hall subgroups are subgroups that have a certain property (which is easy to check). There is no specific Hall subgroup that could be computed.
Mohit Gupta
@mohitacecode
I looked at GAP maybe the title Computation of Hall Subgroup (given in previous year proposal) disguiding I mean that HallSubgroup( G, P ): computes a P-Hall subgroup for a set P of primes. This is a subgroup the order of which is only divisible by primes in P and whose index is coprime to all primes in P.
Mohit Gupta
@mohitacecode
Kalevi Suominen
@jksuom
That is what sylow_subgroup does if there is exactly one prime in P. So that looks like a generalization.
Mohit Gupta
@mohitacecode
just clarifying my doubt sylow_subgroup genrates a subgroup for any particular prime I think ?
Mohit Gupta
@mohitacecode

HallSubgroup( G, P ) will generate a subgroup for a list of primes. maybe we can use sylow_subgroup and take intersection(not there now in sympy) for them.

will HallSubgroup( G, P ) usefull for sympy?

Kalevi Suominen
@jksuom
One often speaks of Sylow p-subgroups for a particular prime.
will HallSubgroup( G, P ) usefull for sympy?
I don't know..
Mohit Gupta
@mohitacecode

One often speaks of Sylow p-subgroups for a particular prime.

Okay..

Should I leave it for now?
Kalevi Suominen
@jksuom
You could take a look at how Sylow subgroups are found in SymPy and then try to find an algorithm for Hall subgroups.
Mohit Gupta
@mohitacecode
Sure I will do it now.
Mohit Gupta
@mohitacecode
Please see it's not a fully detailed we can break this down but it need discussion
Hall_Subgroup(G,P):
1.) Check if every p in P is prime if not:
valueerror
2.) Check if order of G is divisible by every prime in P if not:
return trivial subgroup (only Identity Element)
3.) Compute sylow p subgroup for every prime in P.
4.) Find the common of sylow p subgroups computed in above step.(since every sylow subgroup of a group is hallsubgroup)
Kalevi Suominen
@jksuom
Check if order of G is divisible by every prime in P
This is not necessary. The order of a Hall subgroup does not have to be divisible be p if the order of the group is not.
Find the common of sylow p subgroups
A Hall subgroup must contain a Sylow p-group for each p in P.
Kalevi Suominen
@jksuom
Finding a Hall subgroup for several primes is probably harder than finding a Sylow subgroup.
Mohit Gupta
@mohitacecode

This is not necessary. The order of a Hall subgroup does not have to be divisible be p if the order of the group is not.

can you explain please? beacuse to contain a subgroup for any prime the order of the group should be divisible by it sylow p subgroup also uses it.

suppose P = [2,3] should'nt be hall subgroup be intersection of sylow 2 subgroup and sylow 3 subgroup for any group G.just clarifying .
Kalevi Suominen
@jksuom
The intersection of a Sylow 2-group and 3-group is a subgroup of both of them. The order of a subgroup of a 2-group is a power of 2 and that of a 3-group is a power of 3. The only subgroup whose order is both a power of 2 and a power of 3 is the trivial group of order 1.
Mohit Gupta
@mohitacecode
okay now I understood
I just noticed Probably If H is already a Hall subgroup for a set of primes P then we can say that it is join of sylow p subgroup for p in P but it is not true vice versa. I have to think more for devising a algo.

suppose P = [2,3] should'nt be hall subgroup be intersection of sylow 2 subgroup and sylow 3 subgroup for any group G.just clarifying .

I was completely wrong

Mohit Gupta
@mohitacecode
any subgroup of index 2 is normal is the condition which we can used in is_normal method in perm_groups.py which will reduce further unnecessary steps. please see If I am saying anything wrong
Kalevi Suominen
@jksuom
Computation of the index will also take time. Besides, index 2 is probably rather uncommon.
Mohit Gupta
@mohitacecode
computatation of index requires to compute degree maybe it is much efficient than going for computing further steps.
Mohit Gupta
@mohitacecode
Besides, index 2 is probably rather uncommon.
So should I leave it ?
Kalevi Suominen
@jksuom
Perhaps you could check how adding that test would affect the average time spent in in_normal.
Mohit Gupta
@mohitacecode
I am elobarating few of the ideas that I mentioned previously:
• Extend functionalities of polycyclic groups
There are various things that can be implemented such as:
1.)canonical polycyclic sequence for subgroup.
The pseudocode or Implementation of this algorithm is given in handbook and this is usefull in checking whether two subgroups of polycyclic presented group G are equal since every subgroup has unique canonical polycyclic sequence.This will be use as a helper method for the below method.
2.)check if two subgroups of a polycyclic presented groups are equal or not.
3.)polycyclic orbit-stabilizer algorithm:
This algorithm is also given in the handbook with detailed implementation.
4.)numerator pcgs
5.)denominator pcgs
both numerator and denominator pcgs I have taken reference from the gap(https://www.biu.ac.il/os_site/documentation/gap4r1/ref/CHAP040.htm#SECT011) 40.9
Mohit Gupta
@mohitacecode
• Quotient groups
As you have asked for what kind of groups I think for Finitely presented group (Fp group) In the chapter 9 of the handbook various algorithms are described which can be usefull.
some algorithms such as epimorphism can also be used for computing automorphism group.
I am still working for more descriptive description (As I am still reading the book) And btw I am thinking to start working on canonical polycyclic sequence.
Mohit Gupta
@mohitacecode
Addition of method to compute homomorphism from one polycyclic group G to another polycyclic group H would be usefull?
for a reference gap has a method for it where gens is the list of generators of G and imgs are the list of images of elements of H.
GroupHomomorphismByImages(G, H, gens, imgs)
Kalevi Suominen
@jksuom
I think that something like that has already been implemented.
Mohit Gupta
@mohitacecode
just asking will that work for polycyclic group? beacuse the method we have now is checking whether the group G and H are PermutationGroup, FpGroup, FreeGroup
    if not isinstance(domain, (PermutationGroup, FpGroup, FreeGroup)):
raise TypeError("The domain must be a group")
if not isinstance(codomain, (PermutationGroup, FpGroup, FreeGroup)):
raise TypeError("The codomain must be a group")
Kalevi Suominen
@jksuom
Polycyclic groups are actually special fp-groups. They are formed from a free group by relators that are called pc_presentation.
Mohit Gupta
@mohitacecode
Okay understood will try to use it with polycyclic group
Mohit Gupta
@mohitacecode
Can you please tell how should I use this method with polycyclic group?
Mohit Gupta
@mohitacecode
should I consider looking for monoids and semigroups as a one of usefull idea as it was also mentioned by gaurav(@gxyd ) in gsoc 2016 but was'nt completed due to time constarint.
Kalevi Suominen
@jksuom
Monoids are more difficult to handle than groups. I don't know of any algorithms for them.
Mohit Gupta
@mohitacecode
Okay thanks for you response I will consider these things if i add it in proposal.