Vehicle-cpp/hkpc/software/sympy/combinatorics/tests/test_fp_groups.py

from sympy.core.singleton import S
from sympy.combinatorics.fp_groups import (FpGroup, low_index_subgroups,
                                   reidemeister_presentation, FpSubgroup,
                                           simplify_presentation)
from sympy.combinatorics.free_groups import (free_group, FreeGroup)

from sympy.testing.pytest import slow

"""
References
==========

[1] Holt, D., Eick, B., O'Brien, E.
"Handbook of Computational Group Theory"

[2] John J. Cannon; Lucien A. Dimino; George Havas; Jane M. Watson
Mathematics of Computation, Vol. 27, No. 123. (Jul., 1973), pp. 463-490.
"Implementation and Analysis of the Todd-Coxeter Algorithm"

[3] PROC. SECOND  INTERNAT. CONF. THEORY OF GROUPS, CANBERRA 1973,
pp. 347-356. "A Reidemeister-Schreier program" by George Havas.
http://staff.itee.uq.edu.au/havas/1973cdhw.pdf

"""

def test_low_index_subgroups():
    F, x, y = free_group("x, y")

    # Example 5.10 from [1] Pg. 194
    f = FpGroup(F, [x**2, y**3, (x*y)**4])
    L = low_index_subgroups(f, 4)
    t1 = [[[0, 0, 0, 0]],
          [[0, 0, 1, 2], [1, 1, 2, 0], [3, 3, 0, 1], [2, 2, 3, 3]],
          [[0, 0, 1, 2], [2, 2, 2, 0], [1, 1, 0, 1]],
          [[1, 1, 0, 0], [0, 0, 1, 1]]]
    for i in range(len(t1)):
        assert L[i].table == t1[i]

    f = FpGroup(F, [x**2, y**3, (x*y)**7])
    L = low_index_subgroups(f, 15)
    t2 = [[[0, 0, 0, 0]],
           [[0, 0, 1, 2], [1, 1, 2, 0], [3, 3, 0, 1], [2, 2, 4, 5],
            [4, 4, 5, 3], [6, 6, 3, 4], [5, 5, 6, 6]],
           [[0, 0, 1, 2], [1, 1, 2, 0], [3, 3, 0, 1], [2, 2, 4, 5],
            [6, 6, 5, 3], [5, 5, 3, 4], [4, 4, 6, 6]],
           [[0, 0, 1, 2], [1, 1, 2, 0], [3, 3, 0, 1], [2, 2, 4, 5],
            [6, 6, 5, 3], [7, 7, 3, 4], [4, 4, 8, 9], [5, 5, 10, 11],
            [11, 11, 9, 6], [9, 9, 6, 8], [12, 12, 11, 7], [8, 8, 7, 10],
            [10, 10, 13, 14], [14, 14, 14, 12], [13, 13, 12, 13]],
           [[0, 0, 1, 2], [1, 1, 2, 0], [3, 3, 0, 1], [2, 2, 4, 5],
            [6, 6, 5, 3], [7, 7, 3, 4], [4, 4, 8, 9], [5, 5, 10, 11],
            [11, 11, 9, 6], [12, 12, 6, 8], [10, 10, 11, 7], [8, 8, 7, 10],
            [9, 9, 13, 14], [14, 14, 14, 12], [13, 13, 12, 13]],
           [[0, 0, 1, 2], [1, 1, 2, 0], [3, 3, 0, 1], [2, 2, 4, 5],
            [6, 6, 5, 3], [7, 7, 3, 4], [4, 4, 8, 9], [5, 5, 10, 11],
            [11, 11, 9, 6], [12, 12, 6, 8], [13, 13, 11, 7], [8, 8, 7, 10],
            [9, 9, 12, 12], [10, 10, 13, 13]],
           [[0, 0, 1, 2], [3, 3, 2, 0], [4, 4, 0, 1], [1, 1, 3, 3], [2, 2, 5, 6]
            , [7, 7, 6, 4], [8, 8, 4, 5], [5, 5, 8, 9], [6, 6, 9, 7],
            [10, 10, 7, 8], [9, 9, 11, 12], [11, 11, 12, 10], [13, 13, 10, 11],
            [12, 12, 13, 13]],
           [[0, 0, 1, 2], [3, 3, 2, 0], [4, 4, 0, 1], [1, 1, 3, 3], [2, 2, 5, 6]
            , [7, 7, 6, 4], [8, 8, 4, 5], [5, 5, 8, 9], [6, 6, 9, 7],
            [10, 10, 7, 8], [9, 9, 11, 12], [13, 13, 12, 10], [12, 12, 10, 11],
            [11, 11, 13, 13]],
           [[0, 0, 1, 2], [3, 3, 2, 0], [4, 4, 0, 1], [1, 1, 5, 6], [2, 2, 4, 4]
            , [7, 7, 6, 3], [8, 8, 3, 5], [5, 5, 8, 9], [6, 6, 9, 7],
            [10, 10, 7, 8], [9, 9, 11, 12], [13, 13, 12, 10], [12, 12, 10, 11],
            [11, 11, 13, 13]],
           [[0, 0, 1, 2], [3, 3, 2, 0], [4, 4, 0, 1], [1, 1, 5, 6], [2, 2, 7, 8]
            , [5, 5, 6, 3], [9, 9, 3, 5], [10, 10, 8, 4], [8, 8, 4, 7],
            [6, 6, 10, 11], [7, 7, 11, 9], [12, 12, 9, 10], [11, 11, 13, 14],
            [14, 14, 14, 12], [13, 13, 12, 13]],
           [[0, 0, 1, 2], [3, 3, 2, 0], [4, 4, 0, 1], [1, 1, 5, 6], [2, 2, 7, 8]
            , [6, 6, 6, 3], [5, 5, 3, 5], [8, 8, 8, 4], [7, 7, 4, 7]],
           [[0, 0, 1, 2], [3, 3, 2, 0], [4, 4, 0, 1], [1, 1, 5, 6], [2, 2, 7, 8]
            , [9, 9, 6, 3], [6, 6, 3, 5], [10, 10, 8, 4], [11, 11, 4, 7],
            [5, 5, 10, 12], [7, 7, 12, 9], [8, 8, 11, 11], [13, 13, 9, 10],
            [12, 12, 13, 13]],
           [[0, 0, 1, 2], [3, 3, 2, 0], [4, 4, 0, 1], [1, 1, 5, 6], [2, 2, 7, 8]
            , [9, 9, 6, 3], [6, 6, 3, 5], [10, 10, 8, 4], [11, 11, 4, 7],
            [5, 5, 12, 11], [7, 7, 10, 10], [8, 8, 9, 12], [13, 13, 11, 9],
            [12, 12, 13, 13]],
           [[0, 0, 1, 2], [3, 3, 2, 0], [4, 4, 0, 1], [1, 1, 5, 6], [2, 2, 7, 8]
            , [9, 9, 6, 3], [10, 10, 3, 5], [7, 7, 8, 4], [11, 11, 4, 7],
            [5, 5, 9, 9], [6, 6, 11, 12], [8, 8, 12, 10], [13, 13, 10, 11],
            [12, 12, 13, 13]],
           [[0, 0, 1, 2], [3, 3, 2, 0], [4, 4, 0, 1], [1, 1, 5, 6], [2, 2, 7, 8]
            , [9, 9, 6, 3], [10, 10, 3, 5], [7, 7, 8, 4], [11, 11, 4, 7],
            [5, 5, 12, 11], [6, 6, 10, 10], [8, 8, 9, 12], [13, 13, 11, 9],
            [12, 12, 13, 13]],
           [[0, 0, 1, 2], [3, 3, 2, 0], [4, 4, 0, 1], [1, 1, 5, 6], [2, 2, 7, 8]
            , [9, 9, 6, 3], [10, 10, 3, 5], [11, 11, 8, 4], [12, 12, 4, 7],
            [5, 5, 9, 9], [6, 6, 12, 13], [7, 7, 11, 11], [8, 8, 13, 10],
            [13, 13, 10, 12]],
           [[1, 1, 0, 0], [0, 0, 2, 3], [4, 4, 3, 1], [5, 5, 1, 2], [2, 2, 4, 4]
            , [3, 3, 6, 7], [7, 7, 7, 5], [6, 6, 5, 6]]]
    for i  in range(len(t2)):
        assert L[i].table == t2[i]

    f = FpGroup(F, [x**2, y**3, (x*y)**7])
    L = low_index_subgroups(f, 10, [x])
    t3 = [[[0, 0, 0, 0]],
          [[0, 0, 1, 2], [1, 1, 2, 0], [3, 3, 0, 1], [2, 2, 4, 5], [4, 4, 5, 3],
           [6, 6, 3, 4], [5, 5, 6, 6]],
          [[0, 0, 1, 2], [1, 1, 2, 0], [3, 3, 0, 1], [2, 2, 4, 5], [6, 6, 5, 3],
           [5, 5, 3, 4], [4, 4, 6, 6]],
          [[0, 0, 1, 2], [3, 3, 2, 0], [4, 4, 0, 1], [1, 1, 5, 6], [2, 2, 7, 8],
           [6, 6, 6, 3], [5, 5, 3, 5], [8, 8, 8, 4], [7, 7, 4, 7]]]
    for i in range(len(t3)):
        assert L[i].table == t3[i]


def test_subgroup_presentations():
    F, x, y = free_group("x, y")
    f = FpGroup(F, [x**3, y**5, (x*y)**2])
    H = [x*y, x**-1*y**-1*x*y*x]
    p1 = reidemeister_presentation(f, H)
    assert str(p1) == "((y_1, y_2), (y_1**2, y_2**3, y_2*y_1*y_2*y_1*y_2*y_1))"

    H = f.subgroup(H)
    assert (H.generators, H.relators) == p1

    f = FpGroup(F, [x**3, y**3, (x*y)**3])
    H = [x*y, x*y**-1]
    p2 = reidemeister_presentation(f, H)
    assert str(p2) == "((x_0, y_0), (x_0**3, y_0**3, x_0*y_0*x_0*y_0*x_0*y_0))"

    f = FpGroup(F, [x**2*y**2, y**-1*x*y*x**-3])
    H = [x]
    p3 = reidemeister_presentation(f, H)
    assert str(p3) == "((x_0,), (x_0**4,))"

    f = FpGroup(F, [x**3*y**-3, (x*y)**3, (x*y**-1)**2])
    H = [x]
    p4 = reidemeister_presentation(f, H)
    assert str(p4) == "((x_0,), (x_0**6,))"

    # this presentation can be improved, the most simplified form
    # of presentation is <a, b | a^11, b^2, (a*b)^3, (a^4*b*a^-5*b)^2>
    # See [2] Pg 474 group PSL_2(11)
    # This is the group PSL_2(11)
    F, a, b, c = free_group("a, b, c")
    f = FpGroup(F, [a**11, b**5, c**4, (b*c**2)**2, (a*b*c)**3, (a**4*c**2)**3, b**2*c**-1*b**-1*c, a**4*b**-1*a**-1*b])
    H = [a, b, c**2]
    gens, rels = reidemeister_presentation(f, H)
    assert str(gens) == "(b_1, c_3)"
    assert len(rels) == 18


@slow
def test_order():
    F, x, y = free_group("x, y")
    f = FpGroup(F, [x**4, y**2, x*y*x**-1*y])
    assert f.order() == 8

    f = FpGroup(F, [x*y*x**-1*y**-1, y**2])
    assert f.order() is S.Infinity

    F, a, b, c = free_group("a, b, c")
    f = FpGroup(F, [a**250, b**2, c*b*c**-1*b, c**4, c**-1*a**-1*c*a, a**-1*b**-1*a*b])
    assert f.order() == 2000

    F, x = free_group("x")
    f = FpGroup(F, [])
    assert f.order() is S.Infinity

    f = FpGroup(free_group('')[0], [])
    assert f.order() == 1

def test_fp_subgroup():
    def _test_subgroup(K, T, S):
        _gens = T(K.generators)
        assert all(elem in S for elem in _gens)
        assert T.is_injective()
        assert T.image().order() == S.order()
    F, x, y = free_group("x, y")
    f = FpGroup(F, [x**4, y**2, x*y*x**-1*y])
    S = FpSubgroup(f, [x*y])
    assert (x*y)**-3 in S
    K, T = f.subgroup([x*y], homomorphism=True)
    assert T(K.generators) == [y*x**-1]
    _test_subgroup(K, T, S)

    S = FpSubgroup(f, [x**-1*y*x])
    assert x**-1*y**4*x in S
    assert x**-1*y**4*x**2 not in S
    K, T = f.subgroup([x**-1*y*x], homomorphism=True)
    assert T(K.generators[0]**3) == y**3
    _test_subgroup(K, T, S)

    f = FpGroup(F, [x**3, y**5, (x*y)**2])
    H = [x*y, x**-1*y**-1*x*y*x]
    K, T = f.subgroup(H, homomorphism=True)
    S = FpSubgroup(f, H)
    _test_subgroup(K, T, S)

def test_permutation_methods():
    F, x, y = free_group("x, y")
    # DihedralGroup(8)
    G = FpGroup(F, [x**2, y**8, x*y*x**-1*y])
    T = G._to_perm_group()[1]
    assert T.is_isomorphism()
    assert G.center() == [y**4]

    # DiheadralGroup(4)
    G = FpGroup(F, [x**2, y**4, x*y*x**-1*y])
    S = FpSubgroup(G, G.normal_closure([x]))
    assert x in S
    assert y**-1*x*y in S

    # Z_5xZ_4
    G = FpGroup(F, [x*y*x**-1*y**-1, y**5, x**4])
    assert G.is_abelian
    assert G.is_solvable

    # AlternatingGroup(5)
    G = FpGroup(F, [x**3, y**2, (x*y)**5])
    assert not G.is_solvable

    # AlternatingGroup(4)
    G = FpGroup(F, [x**3, y**2, (x*y)**3])
    assert len(G.derived_series()) == 3
    S = FpSubgroup(G, G.derived_subgroup())
    assert S.order() == 4


def test_simplify_presentation():
    # ref #16083
    G = simplify_presentation(FpGroup(FreeGroup([]), []))
    assert not G.generators
    assert not G.relators


def test_cyclic():
    F, x, y = free_group("x, y")
    f = FpGroup(F, [x*y, x**-1*y**-1*x*y*x])
    assert f.is_cyclic
    f = FpGroup(F, [x*y, x*y**-1])
    assert f.is_cyclic
    f = FpGroup(F, [x**4, y**2, x*y*x**-1*y])
    assert not f.is_cyclic


def test_abelian_invariants():
    F, x, y = free_group("x, y")
    f = FpGroup(F, [x*y, x**-1*y**-1*x*y*x])
    assert f.abelian_invariants() == []
    f = FpGroup(F, [x*y, x*y**-1])
    assert f.abelian_invariants() == [2]
    f = FpGroup(F, [x**4, y**2, x*y*x**-1*y])
    assert f.abelian_invariants() == [2, 4]