Merge pull request sympy#24384 from skieffer/is-dihedral

Add a `PermutationGroup.is_dihedral` property
smichr · Dec 15, 2022 · 4801871 · 4801871
2 parents c7fe006 + 28caebe
commit 4801871
Show file tree

Hide file tree

Showing 3 changed files with 147 additions and 0 deletions.
diff --git a/sympy/combinatorics/named_groups.py b/sympy/combinatorics/named_groups.py
@@ -124,6 +124,7 @@ def AlternatingGroup(n):
     G._degree = n
     G._is_transitive = True
     G._is_alt = True
+    G._is_dihedral = False
     return G
 
 
@@ -168,6 +169,7 @@ def CyclicGroup(n):
     G._degree = n
     G._is_transitive = True
     G._order = n
+    G._is_dihedral = (n == 2)
     return G
 
 
@@ -230,6 +232,7 @@ def DihedralGroup(n):
         G._is_nilpotent = True
     else:
         G._is_nilpotent = False
+    G._is_dihedral = True
     G._is_abelian = False
     G._is_solvable = True
     G._degree = n
@@ -302,6 +305,7 @@ def SymmetricGroup(n):
     G._degree = n
     G._is_transitive = True
     G._is_sym = True
+    G._is_dihedral = (n in [2, 3])  # cf Landau's func and Stirling's approx
     return G
 
 

diff --git a/sympy/combinatorics/perm_groups.py b/sympy/combinatorics/perm_groups.py
@@ -162,6 +162,7 @@ def __init__(self, *args, **kwargs):
         self._max_div = None
         self._is_perfect = None
         self._is_cyclic = None
+        self._is_dihedral = None
         self._r = len(self._generators)
         self._degree = self._generators[0].size
 
@@ -3230,6 +3231,103 @@ def is_cyclic(self):
         self._is_abelian = True
         return True
 
+    @property
+    def is_dihedral(self):
+        r"""
+        Return ``True`` if the group is dihedral.
+
+        Examples
+        ========
+
+        >>> from sympy.combinatorics.perm_groups import PermutationGroup
+        >>> from sympy.combinatorics.permutations import Permutation
+        >>> from sympy.combinatorics.named_groups import SymmetricGroup, CyclicGroup
+        >>> G = PermutationGroup(Permutation(1, 6)(2, 5)(3, 4), Permutation(0, 1, 2, 3, 4, 5, 6))
+        >>> G.is_dihedral
+        True
+        >>> G = SymmetricGroup(3)
+        >>> G.is_dihedral
+        True
+        >>> G = CyclicGroup(6)
+        >>> G.is_dihedral
+        False
+
+        References
+        ==========
+
+        .. [Di1] https://math.stackexchange.com/a/827273
+        .. [Di2] https://kconrad.math.uconn.edu/blurbs/grouptheory/dihedral.pdf
+        .. [Di3] https://kconrad.math.uconn.edu/blurbs/grouptheory/dihedral2.pdf
+        .. [Di4] https://en.wikipedia.org/wiki/Dihedral_group
+        """
+        if self._is_dihedral is not None:
+            return self._is_dihedral
+
+        order = self.order()
+
+        if order % 2 == 1:
+            self._is_dihedral = False
+            return False
+        if order == 2:
+            self._is_dihedral = True
+            return True
+        if order == 4:
+            # The dihedral group of order 4 is the Klein 4-group.
+            self._is_dihedral = not self.is_cyclic
+            return self._is_dihedral
+        if self.is_abelian:
+            # The only abelian dihedral groups are the ones of orders 2 and 4.
+            self._is_dihedral = False
+            return False
+
+        # Now we know the group is of even order >= 6, and nonabelian.
+        n = order // 2
+
+        # Handle special cases where there are exactly two generators.
+        gens = self.generators
+        if len(gens) == 2:
+            x, y = gens
+            a, b = x.order(), y.order()
+            # Make a >= b
+            if a < b:
+                x, y, a, b = y, x, b, a
+            # Using Theorem 2.1 of [Di3]:
+            if a == 2 == b:
+                self._is_dihedral = True
+                return True
+            # Using Theorem 1.1 of [Di3]:
+            if a == n and b == 2 and y*x*y == ~x:
+                self._is_dihedral = True
+                return True
+
+        # Procede with algorithm of [Di1]
+        # Find elements of orders 2 and n
+        order_2, order_n = [], []
+        for p in self.elements:
+            k = p.order()
+            if k == 2:
+                order_2.append(p)
+            elif k == n:
+                order_n.append(p)
+
+        if len(order_2) != n + 1 - (n % 2):
+            self._is_dihedral = False
+            return False
+
+        if not order_n:
+            self._is_dihedral = False
+            return False
+
+        x = order_n[0]
+        # Want an element y of order 2 that is not a power of x
+        # (i.e. that is not the 180-deg rotation, when n is even).
+        y = order_2[0]
+        if n % 2 == 0 and y == x**(n//2):
+            y = order_2[1]
+
+        self._is_dihedral = (y*x*y == ~x)
+        return self._is_dihedral
+
     def pointwise_stabilizer(self, points, incremental=True):
         r"""Return the pointwise stabilizer for a set of points.
 

diff --git a/sympy/combinatorics/tests/test_perm_groups.py b/sympy/combinatorics/tests/test_perm_groups.py
@@ -1047,6 +1047,51 @@ def test_cyclic():
     assert G._is_abelian
 
 
+def test_dihedral():
+    G = SymmetricGroup(2)
+    assert G.is_dihedral
+    G = SymmetricGroup(3)
+    assert G.is_dihedral
+
+    G = AbelianGroup(2, 2)
+    assert G.is_dihedral
+    G = CyclicGroup(4)
+    assert not G.is_dihedral
+
+    G = AbelianGroup(3, 5)
+    assert not G.is_dihedral
+    G = AbelianGroup(2)
+    assert G.is_dihedral
+    G = AbelianGroup(6)
+    assert not G.is_dihedral
+
+    # D6, generated by two adjacent flips
+    G = PermutationGroup(
+        Permutation(1, 5)(2, 4),
+        Permutation(0, 1)(3, 4)(2, 5))
+    assert G.is_dihedral
+
+    # D7, generated by a flip and a rotation
+    G = PermutationGroup(
+        Permutation(1, 6)(2, 5)(3, 4),
+        Permutation(0, 1, 2, 3, 4, 5, 6))
+    assert G.is_dihedral
+
+    # S4, presented by three generators, fails due to having exactly 9
+    # elements of order 2:
+    G = PermutationGroup(
+        Permutation(0, 1), Permutation(0, 2),
+        Permutation(0, 3))
+    assert not G.is_dihedral
+
+    # D7, given by three generators
+    G = PermutationGroup(
+        Permutation(1, 6)(2, 5)(3, 4),
+        Permutation(2, 0)(3, 6)(4, 5),
+        Permutation(0, 1, 2, 3, 4, 5, 6))
+    assert G.is_dihedral
+
+
 def test_abelian_invariants():
     G = AbelianGroup(2, 3, 4)
     assert G.abelian_invariants() == [2, 3, 4]