1import itertools
2from sympy.combinatorics.fp_groups import FpGroup, FpSubgroup, simplify_presentation
3from sympy.combinatorics.free_groups import FreeGroup
4from sympy.combinatorics.perm_groups import PermutationGroup
5from sympy.core.numbers import igcd
6from sympy.ntheory.factor_ import totient
7from sympy import S
8
9class GroupHomomorphism:
10    '''
11    A class representing group homomorphisms. Instantiate using `homomorphism()`.
12
13    References
14    ==========
15
16    .. [1] Holt, D., Eick, B. and O'Brien, E. (2005). Handbook of computational group theory.
17
18    '''
19
20    def __init__(self, domain, codomain, images):
21        self.domain = domain
22        self.codomain = codomain
23        self.images = images
24        self._inverses = None
25        self._kernel = None
26        self._image = None
27
28    def _invs(self):
29        '''
30        Return a dictionary with `{gen: inverse}` where `gen` is a rewriting
31        generator of `codomain` (e.g. strong generator for permutation groups)
32        and `inverse` is an element of its preimage
33
34        '''
35        image = self.image()
36        inverses = {}
37        for k in list(self.images.keys()):
38            v = self.images[k]
39            if not (v in inverses
40                    or v.is_identity):
41                inverses[v] = k
42        if isinstance(self.codomain, PermutationGroup):
43            gens = image.strong_gens
44        else:
45            gens = image.generators
46        for g in gens:
47            if g in inverses or g.is_identity:
48                continue
49            w = self.domain.identity
50            if isinstance(self.codomain, PermutationGroup):
51                parts = image._strong_gens_slp[g][::-1]
52            else:
53                parts = g
54            for s in parts:
55                if s in inverses:
56                    w = w*inverses[s]
57                else:
58                    w = w*inverses[s**-1]**-1
59            inverses[g] = w
60
61        return inverses
62
63    def invert(self, g):
64        '''
65        Return an element of the preimage of ``g`` or of each element
66        of ``g`` if ``g`` is a list.
67
68        Explanation
69        ===========
70
71        If the codomain is an FpGroup, the inverse for equal
72        elements might not always be the same unless the FpGroup's
73        rewriting system is confluent. However, making a system
74        confluent can be time-consuming. If it's important, try
75        `self.codomain.make_confluent()` first.
76
77        '''
78        from sympy.combinatorics import Permutation
79        from sympy.combinatorics.free_groups import FreeGroupElement
80        if isinstance(g, (Permutation, FreeGroupElement)):
81            if isinstance(self.codomain, FpGroup):
82                g = self.codomain.reduce(g)
83            if self._inverses is None:
84                self._inverses = self._invs()
85            image = self.image()
86            w = self.domain.identity
87            if isinstance(self.codomain, PermutationGroup):
88                gens = image.generator_product(g)[::-1]
89            else:
90                gens = g
91            # the following can't be "for s in gens:"
92            # because that would be equivalent to
93            # "for s in gens.array_form:" when g is
94            # a FreeGroupElement. On the other hand,
95            # when you call gens by index, the generator
96            # (or inverse) at position i is returned.
97            for i in range(len(gens)):
98                s = gens[i]
99                if s.is_identity:
100                    continue
101                if s in self._inverses:
102                    w = w*self._inverses[s]
103                else:
104                    w = w*self._inverses[s**-1]**-1
105            return w
106        elif isinstance(g, list):
107            return [self.invert(e) for e in g]
108
109    def kernel(self):
110        '''
111        Compute the kernel of `self`.
112
113        '''
114        if self._kernel is None:
115            self._kernel = self._compute_kernel()
116        return self._kernel
117
118    def _compute_kernel(self):
119        from sympy import S
120        G = self.domain
121        G_order = G.order()
122        if G_order is S.Infinity:
123            raise NotImplementedError(
124                "Kernel computation is not implemented for infinite groups")
125        gens = []
126        if isinstance(G, PermutationGroup):
127            K = PermutationGroup(G.identity)
128        else:
129            K = FpSubgroup(G, gens, normal=True)
130        i = self.image().order()
131        while K.order()*i != G_order:
132            r = G.random()
133            k = r*self.invert(self(r))**-1
134            if not k in K:
135                gens.append(k)
136                if isinstance(G, PermutationGroup):
137                    K = PermutationGroup(gens)
138                else:
139                    K = FpSubgroup(G, gens, normal=True)
140        return K
141
142    def image(self):
143        '''
144        Compute the image of `self`.
145
146        '''
147        if self._image is None:
148            values = list(set(self.images.values()))
149            if isinstance(self.codomain, PermutationGroup):
150                self._image = self.codomain.subgroup(values)
151            else:
152                self._image = FpSubgroup(self.codomain, values)
153        return self._image
154
155    def _apply(self, elem):
156        '''
157        Apply `self` to `elem`.
158
159        '''
160        if not elem in self.domain:
161            if isinstance(elem, (list, tuple)):
162                return [self._apply(e) for e in elem]
163            raise ValueError("The supplied element doesn't belong to the domain")
164        if elem.is_identity:
165            return self.codomain.identity
166        else:
167            images = self.images
168            value = self.codomain.identity
169            if isinstance(self.domain, PermutationGroup):
170                gens = self.domain.generator_product(elem, original=True)
171                for g in gens:
172                    if g in self.images:
173                        value = images[g]*value
174                    else:
175                        value = images[g**-1]**-1*value
176            else:
177                i = 0
178                for _, p in elem.array_form:
179                    if p < 0:
180                        g = elem[i]**-1
181                    else:
182                        g = elem[i]
183                    value = value*images[g]**p
184                    i += abs(p)
185        return value
186
187    def __call__(self, elem):
188        return self._apply(elem)
189
190    def is_injective(self):
191        '''
192        Check if the homomorphism is injective
193
194        '''
195        return self.kernel().order() == 1
196
197    def is_surjective(self):
198        '''
199        Check if the homomorphism is surjective
200
201        '''
202        from sympy import S
203        im = self.image().order()
204        oth = self.codomain.order()
205        if im is S.Infinity and oth is S.Infinity:
206            return None
207        else:
208            return im == oth
209
210    def is_isomorphism(self):
211        '''
212        Check if `self` is an isomorphism.
213
214        '''
215        return self.is_injective() and self.is_surjective()
216
217    def is_trivial(self):
218        '''
219        Check is `self` is a trivial homomorphism, i.e. all elements
220        are mapped to the identity.
221
222        '''
223        return self.image().order() == 1
224
225    def compose(self, other):
226        '''
227        Return the composition of `self` and `other`, i.e.
228        the homomorphism phi such that for all g in the domain
229        of `other`, phi(g) = self(other(g))
230
231        '''
232        if not other.image().is_subgroup(self.domain):
233            raise ValueError("The image of `other` must be a subgroup of "
234                    "the domain of `self`")
235        images = {g: self(other(g)) for g in other.images}
236        return GroupHomomorphism(other.domain, self.codomain, images)
237
238    def restrict_to(self, H):
239        '''
240        Return the restriction of the homomorphism to the subgroup `H`
241        of the domain.
242
243        '''
244        if not isinstance(H, PermutationGroup) or not H.is_subgroup(self.domain):
245            raise ValueError("Given H is not a subgroup of the domain")
246        domain = H
247        images = {g: self(g) for g in H.generators}
248        return GroupHomomorphism(domain, self.codomain, images)
249
250    def invert_subgroup(self, H):
251        '''
252        Return the subgroup of the domain that is the inverse image
253        of the subgroup ``H`` of the homomorphism image
254
255        '''
256        if not H.is_subgroup(self.image()):
257            raise ValueError("Given H is not a subgroup of the image")
258        gens = []
259        P = PermutationGroup(self.image().identity)
260        for h in H.generators:
261            h_i = self.invert(h)
262            if h_i not in P:
263                gens.append(h_i)
264                P = PermutationGroup(gens)
265            for k in self.kernel().generators:
266                if k*h_i not in P:
267                    gens.append(k*h_i)
268                    P = PermutationGroup(gens)
269        return P
270
271def homomorphism(domain, codomain, gens, images=[], check=True):
272    '''
273    Create (if possible) a group homomorphism from the group ``domain``
274    to the group ``codomain`` defined by the images of the domain's
275    generators ``gens``. ``gens`` and ``images`` can be either lists or tuples
276    of equal sizes. If ``gens`` is a proper subset of the group's generators,
277    the unspecified generators will be mapped to the identity. If the
278    images are not specified, a trivial homomorphism will be created.
279
280    If the given images of the generators do not define a homomorphism,
281    an exception is raised.
282
283    If ``check`` is ``False``, don't check whether the given images actually
284    define a homomorphism.
285
286    '''
287    if not isinstance(domain, (PermutationGroup, FpGroup, FreeGroup)):
288        raise TypeError("The domain must be a group")
289    if not isinstance(codomain, (PermutationGroup, FpGroup, FreeGroup)):
290        raise TypeError("The codomain must be a group")
291
292    generators = domain.generators
293    if any([g not in generators for g in gens]):
294        raise ValueError("The supplied generators must be a subset of the domain's generators")
295    if any([g not in codomain for g in images]):
296        raise ValueError("The images must be elements of the codomain")
297
298    if images and len(images) != len(gens):
299        raise ValueError("The number of images must be equal to the number of generators")
300
301    gens = list(gens)
302    images = list(images)
303
304    images.extend([codomain.identity]*(len(generators)-len(images)))
305    gens.extend([g for g in generators if g not in gens])
306    images = dict(zip(gens,images))
307
308    if check and not _check_homomorphism(domain, codomain, images):
309        raise ValueError("The given images do not define a homomorphism")
310    return GroupHomomorphism(domain, codomain, images)
311
312def _check_homomorphism(domain, codomain, images):
313    if hasattr(domain, 'relators'):
314        rels = domain.relators
315    else:
316        gens = domain.presentation().generators
317        rels = domain.presentation().relators
318    identity = codomain.identity
319
320    def _image(r):
321        if r.is_identity:
322            return identity
323        else:
324            w = identity
325            r_arr = r.array_form
326            i = 0
327            j = 0
328            # i is the index for r and j is for
329            # r_arr. r_arr[j] is the tuple (sym, p)
330            # where sym is the generator symbol
331            # and p is the power to which it is
332            # raised while r[i] is a generator
333            # (not just its symbol) or the inverse of
334            # a generator - hence the need for
335            # both indices
336            while i < len(r):
337                power = r_arr[j][1]
338                if isinstance(domain, PermutationGroup) and r[i] in gens:
339                    s = domain.generators[gens.index(r[i])]
340                else:
341                    s = r[i]
342                if s in images:
343                    w = w*images[s]**power
344                elif s**-1 in images:
345                    w = w*images[s**-1]**power
346                i += abs(power)
347                j += 1
348            return w
349
350    for r in rels:
351        if isinstance(codomain, FpGroup):
352            s = codomain.equals(_image(r), identity)
353            if s is None:
354                # only try to make the rewriting system
355                # confluent when it can't determine the
356                # truth of equality otherwise
357                success = codomain.make_confluent()
358                s = codomain.equals(_image(r), identity)
359                if s is None and not success:
360                    raise RuntimeError("Can't determine if the images "
361                        "define a homomorphism. Try increasing "
362                        "the maximum number of rewriting rules "
363                        "(group._rewriting_system.set_max(new_value); "
364                        "the current value is stored in group._rewriting"
365                        "_system.maxeqns)")
366        else:
367            s = _image(r).is_identity
368        if not s:
369            return False
370    return True
371
372def orbit_homomorphism(group, omega):
373    '''
374    Return the homomorphism induced by the action of the permutation
375    group ``group`` on the set ``omega`` that is closed under the action.
376
377    '''
378    from sympy.combinatorics import Permutation
379    from sympy.combinatorics.named_groups import SymmetricGroup
380    codomain = SymmetricGroup(len(omega))
381    identity = codomain.identity
382    omega = list(omega)
383    images = {g: identity*Permutation([omega.index(o^g) for o in omega]) for g in group.generators}
384    group._schreier_sims(base=omega)
385    H = GroupHomomorphism(group, codomain, images)
386    if len(group.basic_stabilizers) > len(omega):
387        H._kernel = group.basic_stabilizers[len(omega)]
388    else:
389        H._kernel = PermutationGroup([group.identity])
390    return H
391
392def block_homomorphism(group, blocks):
393    '''
394    Return the homomorphism induced by the action of the permutation
395    group ``group`` on the block system ``blocks``. The latter should be
396    of the same form as returned by the ``minimal_block`` method for
397    permutation groups, namely a list of length ``group.degree`` where
398    the i-th entry is a representative of the block i belongs to.
399
400    '''
401    from sympy.combinatorics import Permutation
402    from sympy.combinatorics.named_groups import SymmetricGroup
403
404    n = len(blocks)
405
406    # number the blocks; m is the total number,
407    # b is such that b[i] is the number of the block i belongs to,
408    # p is the list of length m such that p[i] is the representative
409    # of the i-th block
410    m = 0
411    p = []
412    b = [None]*n
413    for i in range(n):
414        if blocks[i] == i:
415            p.append(i)
416            b[i] = m
417            m += 1
418    for i in range(n):
419        b[i] = b[blocks[i]]
420
421    codomain = SymmetricGroup(m)
422    # the list corresponding to the identity permutation in codomain
423    identity = range(m)
424    images = {g: Permutation([b[p[i]^g] for i in identity]) for g in group.generators}
425    H = GroupHomomorphism(group, codomain, images)
426    return H
427
428def group_isomorphism(G, H, isomorphism=True):
429    '''
430    Compute an isomorphism between 2 given groups.
431
432    Parameters
433    ==========
434
435    G : A finite ``FpGroup`` or a ``PermutationGroup``.
436        First group.
437
438    H : A finite ``FpGroup`` or a ``PermutationGroup``
439        Second group.
440
441    isomorphism : bool
442        This is used to avoid the computation of homomorphism
443        when the user only wants to check if there exists
444        an isomorphism between the groups.
445
446    Returns
447    =======
448
449    If isomorphism = False -- Returns a boolean.
450    If isomorphism = True  -- Returns a boolean and an isomorphism between `G` and `H`.
451
452    Examples
453    ========
454
455    >>> from sympy.combinatorics import Permutation
456    >>> from sympy.combinatorics.perm_groups import PermutationGroup
457    >>> from sympy.combinatorics.free_groups import free_group
458    >>> from sympy.combinatorics.fp_groups import FpGroup
459    >>> from sympy.combinatorics.homomorphisms import group_isomorphism
460    >>> from sympy.combinatorics.named_groups import DihedralGroup, AlternatingGroup
461
462    >>> D = DihedralGroup(8)
463    >>> p = Permutation(0, 1, 2, 3, 4, 5, 6, 7)
464    >>> P = PermutationGroup(p)
465    >>> group_isomorphism(D, P)
466    (False, None)
467
468    >>> F, a, b = free_group("a, b")
469    >>> G = FpGroup(F, [a**3, b**3, (a*b)**2])
470    >>> H = AlternatingGroup(4)
471    >>> (check, T) = group_isomorphism(G, H)
472    >>> check
473    True
474    >>> T(b*a*b**-1*a**-1*b**-1)
475    (0 2 3)
476
477    Notes
478    =====
479
480    Uses the approach suggested by Robert Tarjan to compute the isomorphism between two groups.
481    First, the generators of ``G`` are mapped to the elements of ``H`` and
482    we check if the mapping induces an isomorphism.
483
484    '''
485    if not isinstance(G, (PermutationGroup, FpGroup)):
486        raise TypeError("The group must be a PermutationGroup or an FpGroup")
487    if not isinstance(H, (PermutationGroup, FpGroup)):
488        raise TypeError("The group must be a PermutationGroup or an FpGroup")
489
490    if isinstance(G, FpGroup) and isinstance(H, FpGroup):
491        G = simplify_presentation(G)
492        H = simplify_presentation(H)
493        # Two infinite FpGroups with the same generators are isomorphic
494        # when the relators are same but are ordered differently.
495        if G.generators == H.generators and (G.relators).sort() == (H.relators).sort():
496            if not isomorphism:
497                return True
498            return (True, homomorphism(G, H, G.generators, H.generators))
499
500    #  `_H` is the permutation group isomorphic to `H`.
501    _H = H
502    g_order = G.order()
503    h_order = H.order()
504
505    if g_order is S.Infinity:
506        raise NotImplementedError("Isomorphism methods are not implemented for infinite groups.")
507
508    if isinstance(H, FpGroup):
509        if h_order is S.Infinity:
510            raise NotImplementedError("Isomorphism methods are not implemented for infinite groups.")
511        _H, h_isomorphism = H._to_perm_group()
512
513    if (g_order != h_order) or (G.is_abelian != H.is_abelian):
514        if not isomorphism:
515            return False
516        return (False, None)
517
518    if not isomorphism:
519        # Two groups of the same cyclic numbered order
520        # are isomorphic to each other.
521        n = g_order
522        if (igcd(n, totient(n))) == 1:
523            return True
524
525    # Match the generators of `G` with subsets of `_H`
526    gens = list(G.generators)
527    for subset in itertools.permutations(_H, len(gens)):
528        images = list(subset)
529        images.extend([_H.identity]*(len(G.generators)-len(images)))
530        _images = dict(zip(gens,images))
531        if _check_homomorphism(G, _H, _images):
532            if isinstance(H, FpGroup):
533                images = h_isomorphism.invert(images)
534            T =  homomorphism(G, H, G.generators, images, check=False)
535            if T.is_isomorphism():
536                # It is a valid isomorphism
537                if not isomorphism:
538                    return True
539                return (True, T)
540
541    if not isomorphism:
542        return False
543    return (False, None)
544
545def is_isomorphic(G, H):
546    '''
547    Check if the groups are isomorphic to each other
548
549    Parameters
550    ==========
551
552    G : A finite ``FpGroup`` or a ``PermutationGroup``
553        First group.
554
555    H : A finite ``FpGroup`` or a ``PermutationGroup``
556        Second group.
557
558    Returns
559    =======
560
561    boolean
562    '''
563    return group_isomorphism(G, H, isomorphism=False)
564