Repository: sympy/sympy

Issue:
PermutationGroup.is_normal gives incorrect result if PermutationGroup is the trivial group
Hey there,

I just encountered the following (independent of n):
```python
>>> from sympy.combinatorics import Permutation, PermutationGroup

>>> n = 2
>>> identity = Permutation(n-1)
>>> cycle = Permutation([(i+1)%n for i in range(n)])
>>> In = PermutationGroup(identity)
>>> Cn = PermutationGroup(cycle)
>>> In.is_normal(Cn)
False
```
I.e. I simply create two permutation groups, one containing the identity only, the other containing a cycle (thus being the cyclic group). ``is_normal`` should test if ``In`` is a normal subgroup of ``Cn`` (or of course for any other two groups). The result ``False`` is incorrect, as the trivial group on n elements is always a normal subgroup of any group on n elements.

If anybody could please double check this concern if I'm not terribly mistaken here?!

I assume the issue results from the implementation that uses ``coset_factor`` to check if the new permutation ``p = g*h*g^{-1}`` (``g \in G, H \in H``, H is tested to be a normal subgroup of G) is part of H.
In the above case, h is the identity permutation, therefore p is also the identity (because of ``g*h*g^{-1} = g*g^{-1}``). But there is no such factorization of the identity (and testing the above for the generators only, normally never gives the identity permutation, except for this case).

Discussion:
sympy-bot: :white_check_mark:

Hi, I am the [SymPy bot](https://github.com/sympy/sympy-bot) (v135). I'm here to help you write a release notes entry. Please read the [guide on how to write release notes](https://github.com/sympy/sympy/wiki/Writing-Release-Notes).



Your release notes are in good order.

Here is what the release notes will look like:
* combinatorics
  * `PermutationGroup.is_normal` did not perform a check if the group that is tested to be a normal subgroup is even a subgroup. ([#15800](https://github.com/sympy/sympy/pull/15800) by [@FabianBall](https://github.com/FabianBall))

  * When the identity group (a `PermutationGroup` that is generated by the identity permutation) was tested to be a normal subgroup of any other group, `PermutationGroup.is_normal` gave the incorrect result (`False` instead of `True`). ([#15800](https://github.com/sympy/sympy/pull/15800) by [@FabianBall](https://github.com/FabianBall))

This will be added to https://github.com/sympy/sympy/wiki/Release-Notes-for-1.4.

Note: This comment will be updated with the latest check if you edit the pull request. You need to reload the page to see it. <details><summary>Click here to see the pull request description that was parsed.</summary>

    #### References to other Issues or PRs
    This fixes #15636 
    <!-- If this pull request fixes an issue, write "Fixes #NNNN" in that exact
    format, e.g. "Fixes #1234". See
    https://github.com/blog/1506-closing-issues-via-pull-requests . Please also
    write a comment on that issue linking back to this pull request once it is
    open. -->


    #### Brief description of what is fixed or changed
    The implementation that uses PermutationGroup.coset_factor to check if a
    permutation p = g*h*g^{-1} (g \in G, H \in H, H is tested to be a normal
    subgroup of G) is again in H (that is the PermutationGroup instance on
    which the method is called) has the problem that if h is the identity
    permutation the check fails. As a consequence, the result of the
    is_normal check is incorrect. This contribution extends to check to
    recognize the identity permutation.
    Furthermore, the subgroup property was never checked which also led to
    incorrect results (i.e. a group of larger order was identified to be a
    normal subgroup of a group of lower order).
    Tests are extended and an incorrect test is removed.

    #### 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 -->
    * combinatorics
      * `PermutationGroup.is_normal` did not perform a check if the group that is tested to be a normal subgroup is even a subgroup.
      * When the identity group (a `PermutationGroup` that is generated by the identity permutation) was tested to be a normal subgroup of any other group, `PermutationGroup.is_normal` gave the incorrect result (`False` instead of `True`).

    <!-- END RELEASE NOTES -->


</details><p>

jksuom: I'm not sure if a non-trivial group might have the identity among its generators. In that case, it seems that `g1` would still have to be checked.
FabianBall: Ouch, I'm getting more and more into it and it's not getting easier... From what I have seen (and tested), the identity is removed from the list of permutations/generators when a new `PermutationGroup` is instantiated. The only possibility for the identity to be part of the generating set is if the group _is_ the trivial group. However, I would suggest not to rely on how this is implemented at the moment (though the behavior makes sense). This is also the reason why I chose the less efficient implementation at first.
What I found out just is that the behavior between `is_subgroup` and `is_normal` differs: the first performs type checking and only allows the (possible) subgroup to act on less elements (but not the other way round.
This is of course not directly related, but it is nonetheless related as in my opinion the behavior for both should be similar.
For now I suggest the following order of checks within `is_normal` (G is `self`, G' is the other group):
1. Check if G is a subgroup of G'. If not, G can't be a normal subgroup.
2. Check if G is the trivial group and if either the degrees of G and G' are the same or if we do not want to be strict. If yes, G is a normal subgroup and no further checks are needed.
3. Test strictness as before
4. Test the actual property of a normal subgroup as before.


oscarbenjamin: It looks as if the tests have failed because of an unrelated issue. If you merge in (or rebase) master they should pass.
jksuom: 100 commits doesn't look right. A merge issue?
FabianBall: I rebased sympy/master into my branch as @oscarbenjamin pointed out. Has it something to do with that?
I'm no git(hub) pro, therefore I'm not really sure. I hope I did not mess anything up?!
oscarbenjamin: Before trying to fix anything make sure you've saved the work that you've done somewhere outside of git.

Then you can fix this with something like:
```console
    $ git remote add upstream https://github.com/sympy/sympy.git
    $ git fetch upstream
    $ git log # Find a commit that is older than these 100 and that is definitely on upstream/master
    $ git log upstream/master
```

Assuming you've copied the hash for the commit as abcde then (careful with this - make sure your work is saved somewhere else before resetting):
```console
    $ git checkout 15636_perm_group_is_normal
    $ git reset --hard abcde
    $ git rebase upstream/master
```
Then this branch will be the same as upstream/master. If something goes wrong during the rebase you can cancel with `git rebase --abort` although that won't undo the reset.

Assuming you're now back in sync with master you can reapply the changes you made, commit then again and then push to this PR with
```
    $ git push --force
```

Patch:
diff --git a/sympy/combinatorics/perm_groups.py b/sympy/combinatorics/perm_groups.py
index d37a6b45e7..dd68d6c8a1 100644
--- a/sympy/combinatorics/perm_groups.py
+++ b/sympy/combinatorics/perm_groups.py
@@ -1817,8 +1817,12 @@ def is_normal(self, gr, strict=True):
         True
 
         """
+        if not self.is_subgroup(gr, strict=strict):
+            return False
         d_self = self.degree
         d_gr = gr.degree
+        if self.is_trivial and (d_self == d_gr or not strict):
+            return True
         new_self = self.copy()
         if not strict and d_self != d_gr:
             if d_self < d_gr:


Test patch:
diff --git a/sympy/combinatorics/tests/test_perm_groups.py b/sympy/combinatorics/tests/test_perm_groups.py
index 45cef8a4b2..ab6d579766 100644
--- a/sympy/combinatorics/tests/test_perm_groups.py
+++ b/sympy/combinatorics/tests/test_perm_groups.py
@@ -284,10 +284,26 @@ def test_is_normal():
     assert G1.is_subgroup(G6)
     assert not G1.is_subgroup(G4)
     assert G2.is_subgroup(G4)
-    s4 = PermutationGroup(Permutation(0, 1, 2, 3), Permutation(3)(0, 1))
-    s6 = PermutationGroup(Permutation(0, 1, 2, 3, 5), Permutation(5)(0, 1))
-    assert s6.is_normal(s4, strict=False)
-    assert not s4.is_normal(s6, strict=False)
+    I5 = PermutationGroup(Permutation(4))
+    assert I5.is_normal(G5)
+    assert I5.is_normal(G6, strict=False)
+    p1 = Permutation([1, 0, 2, 3, 4])
+    p2 = Permutation([0, 1, 2, 4, 3])
+    p3 = Permutation([3, 4, 2, 1, 0])
+    id_ = Permutation([0, 1, 2, 3, 4])
+    H = PermutationGroup([p1, p3])
+    H_n1 = PermutationGroup([p1, p2])
+    H_n2_1 = PermutationGroup(p1)
+    H_n2_2 = PermutationGroup(p2)
+    H_id = PermutationGroup(id_)
+    assert H_n1.is_normal(H)
+    assert H_n2_1.is_normal(H_n1)
+    assert H_n2_2.is_normal(H_n1)
+    assert H_id.is_normal(H_n2_1)
+    assert H_id.is_normal(H_n1)
+    assert H_id.is_normal(H)
+    assert not H_n2_1.is_normal(H)
+    assert not H_n2_2.is_normal(H)
 
 
 def test_eq():