GSoC 2019 - Week 8 - Phase-II Completion

Phase-II has been completed and now it’s time to present all the work done during this phase. This week’s blog is little early in comparison to my previous blogs because I’ll not be active for next 2 upcoming days. In the whole phase we worked on Computations with Polycyclic Groups though the tasks mentioned in proposal for this phase were quite different. But let me tell you it worth that much time, Computation with Polycyclic groups(solvable groups) shows the actual development in computational group theory.

Below are the functioalities that were added to the polycyclic group in this phase, Here is the PR sympy/sympy#16991.

Testing Collector

As discussed in week-5 blog at the time of Collector implementation we did not have the implementation of polycyclic presentation so some hand made tests were used. Here is an example of S(4).

>>> from sympy.combinatorics import *
>>> from sympy.combinatorics.free_groups import free_group
>>> F, x0, x1, x2, x3 = free_group("x0, x1, x2, x3")
>>> pc_relators = { x0**2: (), x1**3: (), x2**2: (), x3**2: (),
...                 x0**-1*x1*x0: x1**2, x0**-1*x2*x0: x2*x3,
...                 x0**-1*x3*x0: x3, x1**-1*x2*x1: x3,
...                 x1**-1*x3*x1: x2*x3, x2**-1*x3*x2: x3
...               }
>>> word = x3*x2*x1*x0
>>> relative_order = [2, 3, 2, 2]
>>> group = word.group
>>> collector = Collector(pc_relators, relative_order, group)
>>> collector.collected_word(word)
x0*x1**2*x2*x3

The final word x0*x1**2*x2*x3 is said to be collected. For more information about collected word please look into the docstrings of the method Collector.collected_word().

Computation of Polycyclic Sequence and Series

Polycyclic sequence and series are the building blocks of polycyclic presentation (have a look at week-6 blog) . One thing to note is that, the derived series of a group may change on different course of execution so we may have different pc sequence and series for the same group.

>>> from sympy.combinatorics import *
>>> G = SymmetricGroup(4)
>>> PcGroup = G.polycyclic_group()
>>> PcGroup.pcgs
[Permutation(0, 1, 2, 3), Permutation(3)(0, 2, 1), Permutation(0, 3)(1, 2), Permutation(0, 1)(2, 3)]
>>> 
>>> PcGroup.pc_series[0] == G
True
>>> PcGroup.pc_series[1] == AlternatingGroup(4)
True
>>> PcGroup.relative_order()
[2, 3, 2, 2]

Computation of Polycyclic Presentation

Few approaches were used to compute polycyclic presentation, the current implementation is discussed in week-7 blog. Below is a small example to show the functionality.

>>> from sympy.combinatorics import *
>>> G = SymmetricGroup(4)
>>> PcGroup = G.polycyclic_group()
>>> from sympy.combinatorics.free_groups import free_group
>>> len(PcGroup.pcgs)
4
>>> free_group, x0, x1, x2, x3 = free_group("x0, x1, x2, x3")
>>> PcGroup.pc_presentation(free_group)
{x3**2: (), x2**2: (), x2**-1*x3*x2: x3, x1**3: (), x1**-1*x3*x1: x2*x3, x1**-1*x2*x1: x3, x0**2: x2*x3, x0**-1*x3*x0: x2, x0**-1*x2*x0: x3, x0**-1*x1*x0: x1**2*x3}

As I mentioned above pc_sequence and pc_series may change on different course of execution and hence the pc_presentation changes accordingly.

Testing Presentation

Due to the changing pc_presentation initially, it was difficult to test presentation but later on a method has been developed and a good amount of code is introduced to test the presentation. The details can be found in the module test_pc_groups.py in the above PR.

Additional methods for Polycyclic groups

There were few additional methods added to the polycyclic group.

• exponent_vector() :- It represents the given generator of a polycyclic group with the help of product of pcgs.
• depth() :- Depth of the first non-zero element in exponent_vector.
• leading_exponent() :- It represents the power of polycyclic generator at the above depth.

>>> from sympy.combinatorics import *
>>> from sympy.combinatorics.free_groups import free_group
>>> G = SymmetricGroup(4)
>>> PcGroup = G.polycyclic_group()
>>> pcgs = PcGroup.pcgs
>>> len(pcgs)
4
>>> free_group, x0, x1, x2, x3 = free_group("x0, x1, x2, x3")
>>> PcGroup.exponent_vector(G[1], F)
[1, 1, 1, 1]
>>> G[1] == pcgs[0]*pcgs[1]*pcgs[2]*pcgs[3]
True
>>> PcGroup.depth(G[1], free_group) == 1
>>> PcGroup.leading_exponent(G[1], free_group) == 1

Currently, we are discussing about organizing above methods of polycyclic group. As Kalevi feels that the suitable place for pc_presentation(currently, it’s a method of PolycyclicGroup class) is the Collector class, Perhaps the structure of both the classes should be changed and the same will be reflected in the examples mentioned above.