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