Coverage for /usr/lib/python3/dist-packages/sympy/combinatorics/pc_groups.py: 11%
220 statements
« prev ^ index » next coverage.py v7.9.1, created at 2025-06-14 15:55 +0200
1from sympy.ntheory.primetest import isprime
2from sympy.combinatorics.perm_groups import PermutationGroup
3from sympy.printing.defaults import DefaultPrinting
4from sympy.combinatorics.free_groups import free_group
7class PolycyclicGroup(DefaultPrinting):
9 is_group = True
10 is_solvable = True
12 def __init__(self, pc_sequence, pc_series, relative_order, collector=None):
13 """
15 Parameters
16 ==========
18 pc_sequence : list
19 A sequence of elements whose classes generate the cyclic factor
20 groups of pc_series.
21 pc_series : list
22 A subnormal sequence of subgroups where each factor group is cyclic.
23 relative_order : list
24 The orders of factor groups of pc_series.
25 collector : Collector
26 By default, it is None. Collector class provides the
27 polycyclic presentation with various other functionalities.
29 """
30 self.pcgs = pc_sequence
31 self.pc_series = pc_series
32 self.relative_order = relative_order
33 self.collector = Collector(self.pcgs, pc_series, relative_order) if not collector else collector
35 def is_prime_order(self):
36 return all(isprime(order) for order in self.relative_order)
38 def length(self):
39 return len(self.pcgs)
42class Collector(DefaultPrinting):
44 """
45 References
46 ==========
48 .. [1] Holt, D., Eick, B., O'Brien, E.
49 "Handbook of Computational Group Theory"
50 Section 8.1.3
51 """
53 def __init__(self, pcgs, pc_series, relative_order, free_group_=None, pc_presentation=None):
54 """
56 Most of the parameters for the Collector class are the same as for PolycyclicGroup.
57 Others are described below.
59 Parameters
60 ==========
62 free_group_ : tuple
63 free_group_ provides the mapping of polycyclic generating
64 sequence with the free group elements.
65 pc_presentation : dict
66 Provides the presentation of polycyclic groups with the
67 help of power and conjugate relators.
69 See Also
70 ========
72 PolycyclicGroup
74 """
75 self.pcgs = pcgs
76 self.pc_series = pc_series
77 self.relative_order = relative_order
78 self.free_group = free_group('x:{}'.format(len(pcgs)))[0] if not free_group_ else free_group_
79 self.index = {s: i for i, s in enumerate(self.free_group.symbols)}
80 self.pc_presentation = self.pc_relators()
82 def minimal_uncollected_subword(self, word):
83 r"""
84 Returns the minimal uncollected subwords.
86 Explanation
87 ===========
89 A word ``v`` defined on generators in ``X`` is a minimal
90 uncollected subword of the word ``w`` if ``v`` is a subword
91 of ``w`` and it has one of the following form
93 * `v = {x_{i+1}}^{a_j}x_i`
95 * `v = {x_{i+1}}^{a_j}{x_i}^{-1}`
97 * `v = {x_i}^{a_j}`
99 for `a_j` not in `\{1, \ldots, s-1\}`. Where, ``s`` is the power
100 exponent of the corresponding generator.
102 Examples
103 ========
105 >>> from sympy.combinatorics.named_groups import SymmetricGroup
106 >>> from sympy.combinatorics import free_group
107 >>> G = SymmetricGroup(4)
108 >>> PcGroup = G.polycyclic_group()
109 >>> collector = PcGroup.collector
110 >>> F, x1, x2 = free_group("x1, x2")
111 >>> word = x2**2*x1**7
112 >>> collector.minimal_uncollected_subword(word)
113 ((x2, 2),)
115 """
116 # To handle the case word = <identity>
117 if not word:
118 return None
120 array = word.array_form
121 re = self.relative_order
122 index = self.index
124 for i in range(len(array)):
125 s1, e1 = array[i]
127 if re[index[s1]] and (e1 < 0 or e1 > re[index[s1]]-1):
128 return ((s1, e1), )
130 for i in range(len(array)-1):
131 s1, e1 = array[i]
132 s2, e2 = array[i+1]
134 if index[s1] > index[s2]:
135 e = 1 if e2 > 0 else -1
136 return ((s1, e1), (s2, e))
138 return None
140 def relations(self):
141 """
142 Separates the given relators of pc presentation in power and
143 conjugate relations.
145 Returns
146 =======
148 (power_rel, conj_rel)
149 Separates pc presentation into power and conjugate relations.
151 Examples
152 ========
154 >>> from sympy.combinatorics.named_groups import SymmetricGroup
155 >>> G = SymmetricGroup(3)
156 >>> PcGroup = G.polycyclic_group()
157 >>> collector = PcGroup.collector
158 >>> power_rel, conj_rel = collector.relations()
159 >>> power_rel
160 {x0**2: (), x1**3: ()}
161 >>> conj_rel
162 {x0**-1*x1*x0: x1**2}
164 See Also
165 ========
167 pc_relators
169 """
170 power_relators = {}
171 conjugate_relators = {}
172 for key, value in self.pc_presentation.items():
173 if len(key.array_form) == 1:
174 power_relators[key] = value
175 else:
176 conjugate_relators[key] = value
177 return power_relators, conjugate_relators
179 def subword_index(self, word, w):
180 """
181 Returns the start and ending index of a given
182 subword in a word.
184 Parameters
185 ==========
187 word : FreeGroupElement
188 word defined on free group elements for a
189 polycyclic group.
190 w : FreeGroupElement
191 subword of a given word, whose starting and
192 ending index to be computed.
194 Returns
195 =======
197 (i, j)
198 A tuple containing starting and ending index of ``w``
199 in the given word.
201 Examples
202 ========
204 >>> from sympy.combinatorics.named_groups import SymmetricGroup
205 >>> from sympy.combinatorics import free_group
206 >>> G = SymmetricGroup(4)
207 >>> PcGroup = G.polycyclic_group()
208 >>> collector = PcGroup.collector
209 >>> F, x1, x2 = free_group("x1, x2")
210 >>> word = x2**2*x1**7
211 >>> w = x2**2*x1
212 >>> collector.subword_index(word, w)
213 (0, 3)
214 >>> w = x1**7
215 >>> collector.subword_index(word, w)
216 (2, 9)
218 """
219 low = -1
220 high = -1
221 for i in range(len(word)-len(w)+1):
222 if word.subword(i, i+len(w)) == w:
223 low = i
224 high = i+len(w)
225 break
226 if low == high == -1:
227 return -1, -1
228 return low, high
230 def map_relation(self, w):
231 """
232 Return a conjugate relation.
234 Explanation
235 ===========
237 Given a word formed by two free group elements, the
238 corresponding conjugate relation with those free
239 group elements is formed and mapped with the collected
240 word in the polycyclic presentation.
242 Examples
243 ========
245 >>> from sympy.combinatorics.named_groups import SymmetricGroup
246 >>> from sympy.combinatorics import free_group
247 >>> G = SymmetricGroup(3)
248 >>> PcGroup = G.polycyclic_group()
249 >>> collector = PcGroup.collector
250 >>> F, x0, x1 = free_group("x0, x1")
251 >>> w = x1*x0
252 >>> collector.map_relation(w)
253 x1**2
255 See Also
256 ========
258 pc_presentation
260 """
261 array = w.array_form
262 s1 = array[0][0]
263 s2 = array[1][0]
264 key = ((s2, -1), (s1, 1), (s2, 1))
265 key = self.free_group.dtype(key)
266 return self.pc_presentation[key]
269 def collected_word(self, word):
270 r"""
271 Return the collected form of a word.
273 Explanation
274 ===========
276 A word ``w`` is called collected, if `w = {x_{i_1}}^{a_1} * \ldots *
277 {x_{i_r}}^{a_r}` with `i_1 < i_2< \ldots < i_r` and `a_j` is in
278 `\{1, \ldots, {s_j}-1\}`.
280 Otherwise w is uncollected.
282 Parameters
283 ==========
285 word : FreeGroupElement
286 An uncollected word.
288 Returns
289 =======
291 word
292 A collected word of form `w = {x_{i_1}}^{a_1}, \ldots,
293 {x_{i_r}}^{a_r}` with `i_1, i_2, \ldots, i_r` and `a_j \in
294 \{1, \ldots, {s_j}-1\}`.
296 Examples
297 ========
299 >>> from sympy.combinatorics.named_groups import SymmetricGroup
300 >>> from sympy.combinatorics.perm_groups import PermutationGroup
301 >>> from sympy.combinatorics import free_group
302 >>> G = SymmetricGroup(4)
303 >>> PcGroup = G.polycyclic_group()
304 >>> collector = PcGroup.collector
305 >>> F, x0, x1, x2, x3 = free_group("x0, x1, x2, x3")
306 >>> word = x3*x2*x1*x0
307 >>> collected_word = collector.collected_word(word)
308 >>> free_to_perm = {}
309 >>> free_group = collector.free_group
310 >>> for sym, gen in zip(free_group.symbols, collector.pcgs):
311 ... free_to_perm[sym] = gen
312 >>> G1 = PermutationGroup()
313 >>> for w in word:
314 ... sym = w[0]
315 ... perm = free_to_perm[sym]
316 ... G1 = PermutationGroup([perm] + G1.generators)
317 >>> G2 = PermutationGroup()
318 >>> for w in collected_word:
319 ... sym = w[0]
320 ... perm = free_to_perm[sym]
321 ... G2 = PermutationGroup([perm] + G2.generators)
323 The two are not identical, but they are equivalent:
325 >>> G1.equals(G2), G1 == G2
326 (True, False)
328 See Also
329 ========
331 minimal_uncollected_subword
333 """
334 free_group = self.free_group
335 while True:
336 w = self.minimal_uncollected_subword(word)
337 if not w:
338 break
340 low, high = self.subword_index(word, free_group.dtype(w))
341 if low == -1:
342 continue
344 s1, e1 = w[0]
345 if len(w) == 1:
346 re = self.relative_order[self.index[s1]]
347 q = e1 // re
348 r = e1-q*re
350 key = ((w[0][0], re), )
351 key = free_group.dtype(key)
352 if self.pc_presentation[key]:
353 presentation = self.pc_presentation[key].array_form
354 sym, exp = presentation[0]
355 word_ = ((w[0][0], r), (sym, q*exp))
356 word_ = free_group.dtype(word_)
357 else:
358 if r != 0:
359 word_ = ((w[0][0], r), )
360 word_ = free_group.dtype(word_)
361 else:
362 word_ = None
363 word = word.eliminate_word(free_group.dtype(w), word_)
365 if len(w) == 2 and w[1][1] > 0:
366 s2, e2 = w[1]
367 s2 = ((s2, 1), )
368 s2 = free_group.dtype(s2)
369 word_ = self.map_relation(free_group.dtype(w))
370 word_ = s2*word_**e1
371 word_ = free_group.dtype(word_)
372 word = word.substituted_word(low, high, word_)
374 elif len(w) == 2 and w[1][1] < 0:
375 s2, e2 = w[1]
376 s2 = ((s2, 1), )
377 s2 = free_group.dtype(s2)
378 word_ = self.map_relation(free_group.dtype(w))
379 word_ = s2**-1*word_**e1
380 word_ = free_group.dtype(word_)
381 word = word.substituted_word(low, high, word_)
383 return word
386 def pc_relators(self):
387 r"""
388 Return the polycyclic presentation.
390 Explanation
391 ===========
393 There are two types of relations used in polycyclic
394 presentation.
396 * Power relations : Power relators are of the form `x_i^{re_i}`,
397 where `i \in \{0, \ldots, \mathrm{len(pcgs)}\}`, ``x`` represents polycyclic
398 generator and ``re`` is the corresponding relative order.
400 * Conjugate relations : Conjugate relators are of the form `x_j^-1x_ix_j`,
401 where `j < i \in \{0, \ldots, \mathrm{len(pcgs)}\}`.
403 Returns
404 =======
406 A dictionary with power and conjugate relations as key and
407 their collected form as corresponding values.
409 Notes
410 =====
412 Identity Permutation is mapped with empty ``()``.
414 Examples
415 ========
417 >>> from sympy.combinatorics.named_groups import SymmetricGroup
418 >>> from sympy.combinatorics.permutations import Permutation
419 >>> S = SymmetricGroup(49).sylow_subgroup(7)
420 >>> der = S.derived_series()
421 >>> G = der[len(der)-2]
422 >>> PcGroup = G.polycyclic_group()
423 >>> collector = PcGroup.collector
424 >>> pcgs = PcGroup.pcgs
425 >>> len(pcgs)
426 6
427 >>> free_group = collector.free_group
428 >>> pc_resentation = collector.pc_presentation
429 >>> free_to_perm = {}
430 >>> for s, g in zip(free_group.symbols, pcgs):
431 ... free_to_perm[s] = g
433 >>> for k, v in pc_resentation.items():
434 ... k_array = k.array_form
435 ... if v != ():
436 ... v_array = v.array_form
437 ... lhs = Permutation()
438 ... for gen in k_array:
439 ... s = gen[0]
440 ... e = gen[1]
441 ... lhs = lhs*free_to_perm[s]**e
442 ... if v == ():
443 ... assert lhs.is_identity
444 ... continue
445 ... rhs = Permutation()
446 ... for gen in v_array:
447 ... s = gen[0]
448 ... e = gen[1]
449 ... rhs = rhs*free_to_perm[s]**e
450 ... assert lhs == rhs
452 """
453 free_group = self.free_group
454 rel_order = self.relative_order
455 pc_relators = {}
456 perm_to_free = {}
457 pcgs = self.pcgs
459 for gen, s in zip(pcgs, free_group.generators):
460 perm_to_free[gen**-1] = s**-1
461 perm_to_free[gen] = s
463 pcgs = pcgs[::-1]
464 series = self.pc_series[::-1]
465 rel_order = rel_order[::-1]
466 collected_gens = []
468 for i, gen in enumerate(pcgs):
469 re = rel_order[i]
470 relation = perm_to_free[gen]**re
471 G = series[i]
473 l = G.generator_product(gen**re, original = True)
474 l.reverse()
476 word = free_group.identity
477 for g in l:
478 word = word*perm_to_free[g]
480 word = self.collected_word(word)
481 pc_relators[relation] = word if word else ()
482 self.pc_presentation = pc_relators
484 collected_gens.append(gen)
485 if len(collected_gens) > 1:
486 conj = collected_gens[len(collected_gens)-1]
487 conjugator = perm_to_free[conj]
489 for j in range(len(collected_gens)-1):
490 conjugated = perm_to_free[collected_gens[j]]
492 relation = conjugator**-1*conjugated*conjugator
493 gens = conj**-1*collected_gens[j]*conj
495 l = G.generator_product(gens, original = True)
496 l.reverse()
497 word = free_group.identity
498 for g in l:
499 word = word*perm_to_free[g]
501 word = self.collected_word(word)
502 pc_relators[relation] = word if word else ()
503 self.pc_presentation = pc_relators
505 return pc_relators
507 def exponent_vector(self, element):
508 r"""
509 Return the exponent vector of length equal to the
510 length of polycyclic generating sequence.
512 Explanation
513 ===========
515 For a given generator/element ``g`` of the polycyclic group,
516 it can be represented as `g = {x_1}^{e_1}, \ldots, {x_n}^{e_n}`,
517 where `x_i` represents polycyclic generators and ``n`` is
518 the number of generators in the free_group equal to the length
519 of pcgs.
521 Parameters
522 ==========
524 element : Permutation
525 Generator of a polycyclic group.
527 Examples
528 ========
530 >>> from sympy.combinatorics.named_groups import SymmetricGroup
531 >>> from sympy.combinatorics.permutations import Permutation
532 >>> G = SymmetricGroup(4)
533 >>> PcGroup = G.polycyclic_group()
534 >>> collector = PcGroup.collector
535 >>> pcgs = PcGroup.pcgs
536 >>> collector.exponent_vector(G[0])
537 [1, 0, 0, 0]
538 >>> exp = collector.exponent_vector(G[1])
539 >>> g = Permutation()
540 >>> for i in range(len(exp)):
541 ... g = g*pcgs[i]**exp[i] if exp[i] else g
542 >>> assert g == G[1]
544 References
545 ==========
547 .. [1] Holt, D., Eick, B., O'Brien, E.
548 "Handbook of Computational Group Theory"
549 Section 8.1.1, Definition 8.4
551 """
552 free_group = self.free_group
553 G = PermutationGroup()
554 for g in self.pcgs:
555 G = PermutationGroup([g] + G.generators)
556 gens = G.generator_product(element, original = True)
557 gens.reverse()
559 perm_to_free = {}
560 for sym, g in zip(free_group.generators, self.pcgs):
561 perm_to_free[g**-1] = sym**-1
562 perm_to_free[g] = sym
563 w = free_group.identity
564 for g in gens:
565 w = w*perm_to_free[g]
567 word = self.collected_word(w)
569 index = self.index
570 exp_vector = [0]*len(free_group)
571 word = word.array_form
572 for t in word:
573 exp_vector[index[t[0]]] = t[1]
574 return exp_vector
576 def depth(self, element):
577 r"""
578 Return the depth of a given element.
580 Explanation
581 ===========
583 The depth of a given element ``g`` is defined by
584 `\mathrm{dep}[g] = i` if `e_1 = e_2 = \ldots = e_{i-1} = 0`
585 and `e_i != 0`, where ``e`` represents the exponent-vector.
587 Examples
588 ========
590 >>> from sympy.combinatorics.named_groups import SymmetricGroup
591 >>> G = SymmetricGroup(3)
592 >>> PcGroup = G.polycyclic_group()
593 >>> collector = PcGroup.collector
594 >>> collector.depth(G[0])
595 2
596 >>> collector.depth(G[1])
597 1
599 References
600 ==========
602 .. [1] Holt, D., Eick, B., O'Brien, E.
603 "Handbook of Computational Group Theory"
604 Section 8.1.1, Definition 8.5
606 """
607 exp_vector = self.exponent_vector(element)
608 return next((i+1 for i, x in enumerate(exp_vector) if x), len(self.pcgs)+1)
610 def leading_exponent(self, element):
611 r"""
612 Return the leading non-zero exponent.
614 Explanation
615 ===========
617 The leading exponent for a given element `g` is defined
618 by `\mathrm{leading\_exponent}[g]` `= e_i`, if `\mathrm{depth}[g] = i`.
620 Examples
621 ========
623 >>> from sympy.combinatorics.named_groups import SymmetricGroup
624 >>> G = SymmetricGroup(3)
625 >>> PcGroup = G.polycyclic_group()
626 >>> collector = PcGroup.collector
627 >>> collector.leading_exponent(G[1])
628 1
630 """
631 exp_vector = self.exponent_vector(element)
632 depth = self.depth(element)
633 if depth != len(self.pcgs)+1:
634 return exp_vector[depth-1]
635 return None
637 def _sift(self, z, g):
638 h = g
639 d = self.depth(h)
640 while d < len(self.pcgs) and z[d-1] != 1:
641 k = z[d-1]
642 e = self.leading_exponent(h)*(self.leading_exponent(k))**-1
643 e = e % self.relative_order[d-1]
644 h = k**-e*h
645 d = self.depth(h)
646 return h
648 def induced_pcgs(self, gens):
649 """
651 Parameters
652 ==========
654 gens : list
655 A list of generators on which polycyclic subgroup
656 is to be defined.
658 Examples
659 ========
661 >>> from sympy.combinatorics.named_groups import SymmetricGroup
662 >>> S = SymmetricGroup(8)
663 >>> G = S.sylow_subgroup(2)
664 >>> PcGroup = G.polycyclic_group()
665 >>> collector = PcGroup.collector
666 >>> gens = [G[0], G[1]]
667 >>> ipcgs = collector.induced_pcgs(gens)
668 >>> [gen.order() for gen in ipcgs]
669 [2, 2, 2]
670 >>> G = S.sylow_subgroup(3)
671 >>> PcGroup = G.polycyclic_group()
672 >>> collector = PcGroup.collector
673 >>> gens = [G[0], G[1]]
674 >>> ipcgs = collector.induced_pcgs(gens)
675 >>> [gen.order() for gen in ipcgs]
676 [3]
678 """
679 z = [1]*len(self.pcgs)
680 G = gens
681 while G:
682 g = G.pop(0)
683 h = self._sift(z, g)
684 d = self.depth(h)
685 if d < len(self.pcgs):
686 for gen in z:
687 if gen != 1:
688 G.append(h**-1*gen**-1*h*gen)
689 z[d-1] = h;
690 z = [gen for gen in z if gen != 1]
691 return z
693 def constructive_membership_test(self, ipcgs, g):
694 """
695 Return the exponent vector for induced pcgs.
696 """
697 e = [0]*len(ipcgs)
698 h = g
699 d = self.depth(h)
700 for i, gen in enumerate(ipcgs):
701 while self.depth(gen) == d:
702 f = self.leading_exponent(h)*self.leading_exponent(gen)
703 f = f % self.relative_order[d-1]
704 h = gen**(-f)*h
705 e[i] = f
706 d = self.depth(h)
707 if h == 1:
708 return e
709 return False