Where communities thrive


  • Join over 1.5M+ people
  • Join over 100K+ communities
  • Free without limits
  • Create your own community
People
Activity
    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

    Sorry for late reply
    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.
    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.
    Mohit Gupta
    @mohitacecode
    Till now socle of a primitive permutation group is not implemented which can be further extended in calculating a chief series for a permuation group.I am considering this for adding it in my proposal.
    After doing some research I have find some implementation of pseudo code for them.