Repository: sympy/sympy
Pull request: Solves key error in creating polycyclic group, Improves _sift, induced_pcgs
<!-- Your title above should be a short description of what
was changed. Do not include the issue number in the title. -->

#### References to other Issues or PRs
<!-- If this pull request fixes an issue, write "Fixes #NNNN" in that exact
format, e.g. "Fixes #1234" (see
https://tinyurl.com/auto-closing for more information). Also, please
write a comment on that issue linking back to this pull request once it is
open. -->
Fixes #18804 
Fixes #18989 
#### Brief description of what is fixed or changed

- Improved `collected_word`, `_sift`, `induced_pcgs`.

#### Other comments


#### Release Notes

<!-- Write the release notes for this release below. See
https://github.com/sympy/sympy/wiki/Writing-Release-Notes for more information
on how to write release notes. The bot will check your release notes
automatically to see if they are formatted correctly. -->

<!-- BEGIN RELEASE NOTES -->
NO ENTRY
<!-- END RELEASE NOTES -->

Problem statement:
KeyError in creating a polycylic group from Dihedral Group
I am getting this error when `n>2`and `n` is `even` is there any reason we are getting this?if yes should we raise a `exception` instead?
```
>>> G = DihedralGroup(10)
>>> A = G.polycyclic_group()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/mohit/Documents/sympy-master/sympy/sympy/combinatorics/perm_groups.py", line 4862, in polycyclic_group
    return PolycyclicGroup(pc_sequence, pc_series, relative_order, collector=None)
  File "/home/mohit/Documents/sympy-master/sympy/sympy/combinatorics/pc_groups.py", line 33, in __init__
    self.collector = Collector(self.pcgs, pc_series, relative_order) if not collector else collector
  File "/home/mohit/Documents/sympy-master/sympy/sympy/combinatorics/pc_groups.py", line 80, in __init__
    self.pc_presentation = self.pc_relators()
  File "/home/mohit/Documents/sympy-master/sympy/sympy/combinatorics/pc_groups.py", line 477, in pc_relators
    word = self.collected_word(word)
  File "/home/mohit/Documents/sympy-master/sympy/sympy/combinatorics/pc_groups.py", line 318, in collected_word
    w = self.minimal_uncollected_subword(word)
  File "/home/mohit/Documents/sympy-master/sympy/sympy/combinatorics/pc_groups.py", line 123, in minimal_uncollected_subword
    if re[index[s1]] and (e1 < 0 or e1 > re[index[s1]]-1):
KeyError: x2**4
>>> G.is_solvable
True
```

creating an induced polycyclic sequence from Alt(4) group takes infinite time.
```
>>> a = AlternatingGroup(4)
>>> g = a.polycyclic_group()
>>> collector = g.collector
>>> gens = [a[0],a[1]]
>>> ipcgs = collector.induced_pcgs(gens)
```
It does not evaluate.

Hints from issue discussion:
Ping @jksuom @divyanshu132 
I think this should work, may be there is some problem with the collection of word.
The problem seems in the `pc_relators` function because on line `335` of `pc_groups.py` this (`self.pc_presentation[key]`) is returning a `x2**4` which is a exponential value. 
Mapped value can be exponential.
Replace that line with below lines.
```
presentation = self.pc_presentation[key].array_form
sym, exp = presentation[0]
word_ = ((w[0][0], r), (sym, q*exp))
```

Probably, this will fix the above issue.
@sylee957 Can I get your help in the above pr?

Commit message: changes example

Patch to review:
diff --git a/sympy/combinatorics/pc_groups.py b/sympy/combinatorics/pc_groups.py
index 3080f5970ef1..a68be2b382c3 100644
--- a/sympy/combinatorics/pc_groups.py
+++ b/sympy/combinatorics/pc_groups.py
@@ -332,7 +332,9 @@ def collected_word(self, word):
                 key = ((w[0][0], re), )
                 key = free_group.dtype(key)
                 if self.pc_presentation[key]:
-                    word_ = ((w[0][0], r), (self.pc_presentation[key], q))
+                    presentation = self.pc_presentation[key].array_form
+                    sym, exp = presentation[0]
+                    word_ = ((w[0][0], r), (sym, q*exp))
                     word_ = free_group.dtype(word_)
                 else:
                     if r != 0:
@@ -603,7 +605,7 @@ def _sift(self, z, g):
         d = self.depth(h)
         while d < len(self.pcgs) and z[d-1] != 1:
             k = z[d-1]
-            e = self.leading_exponent(h)*self.leading_exponent(k**-1)
+            e = self.leading_exponent(h)*(self.leading_exponent(k))**-1
             e = e % self.relative_order[d-1]
             h = k**-e*h
             d = self.depth(h)
diff --git a/sympy/combinatorics/tests/test_pc_groups.py b/sympy/combinatorics/tests/test_pc_groups.py
index ef4cdf3ee439..daaf07a50c76 100644
--- a/sympy/combinatorics/tests/test_pc_groups.py
+++ b/sympy/combinatorics/tests/test_pc_groups.py
@@ -1,10 +1,10 @@
 from sympy.combinatorics.permutations import Permutation
-from sympy.combinatorics.named_groups import SymmetricGroup
-
+from sympy.combinatorics.named_groups import SymmetricGroup, AlternatingGroup, DihedralGroup
+from sympy.matrices import Matrix
 
 def test_pc_presentation():
     Groups = [SymmetricGroup(3), SymmetricGroup(4), SymmetricGroup(9).sylow_subgroup(3),
-         SymmetricGroup(9).sylow_subgroup(2), SymmetricGroup(8).sylow_subgroup(2)]
+         SymmetricGroup(9).sylow_subgroup(2), SymmetricGroup(8).sylow_subgroup(2), DihedralGroup(10)]
 
     S = SymmetricGroup(125).sylow_subgroup(5)
     G = S.derived_series()[2]
@@ -73,18 +73,18 @@ def test_exponent_vector():
 
 
 def test_induced_pcgs():
-    G = SymmetricGroup(9).sylow_subgroup(3)
-    PcGroup = G.polycyclic_group()
-    collector = PcGroup.collector
-    gens = [G[0], G[1]]
-    ipcgs = collector.induced_pcgs(gens)
-    order = [gen.order() for gen in ipcgs]
-    assert order == [3, 3]
-
-    G = SymmetricGroup(20).sylow_subgroup(2)
-    PcGroup = G.polycyclic_group()
-    collector = PcGroup.collector
-    gens = [G[0], G[1], G[2], G[3]]
-    ipcgs = collector.induced_pcgs(gens)
-    order = [gen.order() for gen in ipcgs]
-    assert order ==[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
+    G = [SymmetricGroup(9).sylow_subgroup(3), SymmetricGroup(20).sylow_subgroup(2), AlternatingGroup(4),
+    DihedralGroup(4), SymmetricGroup(3), SymmetricGroup(4)]
+
+    for g in G:
+        PcGroup = g.polycyclic_group()
+        collector = PcGroup.collector
+        gens = []
+        genr = g.generators
+        for i in range(len(genr)):
+            gens.append(genr[i])
+        ipcgs = collector.induced_pcgs(gens)
+        m = []
+        for i in ipcgs:
+            m.append(collector.exponent_vector(i))
+        assert Matrix(m).is_upper


Code review comments:
diff_hunk: @@ -73,18 +73,18 @@ def test_exponent_vector():
 
 
 def test_induced_pcgs():
-    G = SymmetricGroup(9).sylow_subgroup(3)
-    PcGroup = G.polycyclic_group()
-    collector = PcGroup.collector
-    gens = [G[0], G[1]]
-    ipcgs = collector.induced_pcgs(gens)
-    order = [gen.order() for gen in ipcgs]
-    assert order == [3, 3]
-
-    G = SymmetricGroup(20).sylow_subgroup(2)
-    PcGroup = G.polycyclic_group()
-    collector = PcGroup.collector
-    gens = [G[0], G[1], G[2], G[3]]
-    ipcgs = collector.induced_pcgs(gens)
-    order = [gen.order() for gen in ipcgs]
-    assert order ==[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
+    G = [SymmetricGroup(9).sylow_subgroup(3), SymmetricGroup(20).sylow_subgroup(2), AlternatingGroup(4),
+    DihedralGroup(4), SymmetricGroup(3), SymmetricGroup(4)]
+
+    for g in G:
+        PcGroup = g.polycyclic_group()
+        collector = PcGroup.collector
+        gens = []
+        genr = g.generators
+        for i in range(len(genr)):
+            gens.append(genr[i])
path: sympy/combinatorics/tests/test_pc_groups.py
text: @user1:
`gens = [gen for gen in g.generators]`