| r""" |
| Construct transitive subgroups of symmetric groups, useful in Galois theory. |
| |
| Besides constructing instances of the :py:class:`~.PermutationGroup` class to |
| represent the transitive subgroups of $S_n$ for small $n$, this module provides |
| *names* for these groups. |
| |
| In some applications, it may be preferable to know the name of a group, |
| rather than receive an instance of the :py:class:`~.PermutationGroup` |
| class, and then have to do extra work to determine which group it is, by |
| checking various properties. |
| |
| Names are instances of ``Enum`` classes defined in this module. With a name in |
| hand, the name's ``get_perm_group`` method can then be used to retrieve a |
| :py:class:`~.PermutationGroup`. |
| |
| The names used for groups in this module are taken from [1]. |
| |
| References |
| ========== |
| |
| .. [1] Cohen, H. *A Course in Computational Algebraic Number Theory*. |
| |
| """ |
|
|
| from collections import defaultdict |
| from enum import Enum |
| import itertools |
|
|
| from sympy.combinatorics.named_groups import ( |
| SymmetricGroup, AlternatingGroup, CyclicGroup, DihedralGroup, |
| set_symmetric_group_properties, set_alternating_group_properties, |
| ) |
| from sympy.combinatorics.perm_groups import PermutationGroup |
| from sympy.combinatorics.permutations import Permutation |
|
|
|
|
| class S1TransitiveSubgroups(Enum): |
| """ |
| Names for the transitive subgroups of S1. |
| """ |
| S1 = "S1" |
|
|
| def get_perm_group(self): |
| return SymmetricGroup(1) |
|
|
|
|
| class S2TransitiveSubgroups(Enum): |
| """ |
| Names for the transitive subgroups of S2. |
| """ |
| S2 = "S2" |
|
|
| def get_perm_group(self): |
| return SymmetricGroup(2) |
|
|
|
|
| class S3TransitiveSubgroups(Enum): |
| """ |
| Names for the transitive subgroups of S3. |
| """ |
| A3 = "A3" |
| S3 = "S3" |
|
|
| def get_perm_group(self): |
| if self == S3TransitiveSubgroups.A3: |
| return AlternatingGroup(3) |
| elif self == S3TransitiveSubgroups.S3: |
| return SymmetricGroup(3) |
|
|
|
|
| class S4TransitiveSubgroups(Enum): |
| """ |
| Names for the transitive subgroups of S4. |
| """ |
| C4 = "C4" |
| V = "V" |
| D4 = "D4" |
| A4 = "A4" |
| S4 = "S4" |
|
|
| def get_perm_group(self): |
| if self == S4TransitiveSubgroups.C4: |
| return CyclicGroup(4) |
| elif self == S4TransitiveSubgroups.V: |
| return four_group() |
| elif self == S4TransitiveSubgroups.D4: |
| return DihedralGroup(4) |
| elif self == S4TransitiveSubgroups.A4: |
| return AlternatingGroup(4) |
| elif self == S4TransitiveSubgroups.S4: |
| return SymmetricGroup(4) |
|
|
|
|
| class S5TransitiveSubgroups(Enum): |
| """ |
| Names for the transitive subgroups of S5. |
| """ |
| C5 = "C5" |
| D5 = "D5" |
| M20 = "M20" |
| A5 = "A5" |
| S5 = "S5" |
|
|
| def get_perm_group(self): |
| if self == S5TransitiveSubgroups.C5: |
| return CyclicGroup(5) |
| elif self == S5TransitiveSubgroups.D5: |
| return DihedralGroup(5) |
| elif self == S5TransitiveSubgroups.M20: |
| return M20() |
| elif self == S5TransitiveSubgroups.A5: |
| return AlternatingGroup(5) |
| elif self == S5TransitiveSubgroups.S5: |
| return SymmetricGroup(5) |
|
|
|
|
| class S6TransitiveSubgroups(Enum): |
| """ |
| Names for the transitive subgroups of S6. |
| """ |
| C6 = "C6" |
| S3 = "S3" |
| D6 = "D6" |
| A4 = "A4" |
| G18 = "G18" |
| A4xC2 = "A4 x C2" |
| S4m = "S4-" |
| S4p = "S4+" |
| G36m = "G36-" |
| G36p = "G36+" |
| S4xC2 = "S4 x C2" |
| PSL2F5 = "PSL2(F5)" |
| G72 = "G72" |
| PGL2F5 = "PGL2(F5)" |
| A6 = "A6" |
| S6 = "S6" |
|
|
| def get_perm_group(self): |
| if self == S6TransitiveSubgroups.C6: |
| return CyclicGroup(6) |
| elif self == S6TransitiveSubgroups.S3: |
| return S3_in_S6() |
| elif self == S6TransitiveSubgroups.D6: |
| return DihedralGroup(6) |
| elif self == S6TransitiveSubgroups.A4: |
| return A4_in_S6() |
| elif self == S6TransitiveSubgroups.G18: |
| return G18() |
| elif self == S6TransitiveSubgroups.A4xC2: |
| return A4xC2() |
| elif self == S6TransitiveSubgroups.S4m: |
| return S4m() |
| elif self == S6TransitiveSubgroups.S4p: |
| return S4p() |
| elif self == S6TransitiveSubgroups.G36m: |
| return G36m() |
| elif self == S6TransitiveSubgroups.G36p: |
| return G36p() |
| elif self == S6TransitiveSubgroups.S4xC2: |
| return S4xC2() |
| elif self == S6TransitiveSubgroups.PSL2F5: |
| return PSL2F5() |
| elif self == S6TransitiveSubgroups.G72: |
| return G72() |
| elif self == S6TransitiveSubgroups.PGL2F5: |
| return PGL2F5() |
| elif self == S6TransitiveSubgroups.A6: |
| return AlternatingGroup(6) |
| elif self == S6TransitiveSubgroups.S6: |
| return SymmetricGroup(6) |
|
|
|
|
| def four_group(): |
| """ |
| Return a representation of the Klein four-group as a transitive subgroup |
| of S4. |
| """ |
| return PermutationGroup( |
| Permutation(0, 1)(2, 3), |
| Permutation(0, 2)(1, 3) |
| ) |
|
|
|
|
| def M20(): |
| """ |
| Return a representation of the metacyclic group M20, a transitive subgroup |
| of S5 that is one of the possible Galois groups for polys of degree 5. |
| |
| Notes |
| ===== |
| |
| See [1], Page 323. |
| |
| """ |
| G = PermutationGroup(Permutation(0, 1, 2, 3, 4), Permutation(1, 2, 4, 3)) |
| G._degree = 5 |
| G._order = 20 |
| G._is_transitive = True |
| G._is_sym = False |
| G._is_alt = False |
| G._is_cyclic = False |
| G._is_dihedral = False |
| return G |
|
|
|
|
| def S3_in_S6(): |
| """ |
| Return a representation of S3 as a transitive subgroup of S6. |
| |
| Notes |
| ===== |
| |
| The representation is found by viewing the group as the symmetries of a |
| triangular prism. |
| |
| """ |
| G = PermutationGroup(Permutation(0, 1, 2)(3, 4, 5), Permutation(0, 3)(2, 4)(1, 5)) |
| set_symmetric_group_properties(G, 3, 6) |
| return G |
|
|
|
|
| def A4_in_S6(): |
| """ |
| Return a representation of A4 as a transitive subgroup of S6. |
| |
| Notes |
| ===== |
| |
| This was computed using :py:func:`~.find_transitive_subgroups_of_S6`. |
| |
| """ |
| G = PermutationGroup(Permutation(0, 4, 5)(1, 3, 2), Permutation(0, 1, 2)(3, 5, 4)) |
| set_alternating_group_properties(G, 4, 6) |
| return G |
|
|
|
|
| def S4m(): |
| """ |
| Return a representation of the S4- transitive subgroup of S6. |
| |
| Notes |
| ===== |
| |
| This was computed using :py:func:`~.find_transitive_subgroups_of_S6`. |
| |
| """ |
| G = PermutationGroup(Permutation(1, 4, 5, 3), Permutation(0, 4)(1, 5)(2, 3)) |
| set_symmetric_group_properties(G, 4, 6) |
| return G |
|
|
|
|
| def S4p(): |
| """ |
| Return a representation of the S4+ transitive subgroup of S6. |
| |
| Notes |
| ===== |
| |
| This was computed using :py:func:`~.find_transitive_subgroups_of_S6`. |
| |
| """ |
| G = PermutationGroup(Permutation(0, 2, 4, 1)(3, 5), Permutation(0, 3)(4, 5)) |
| set_symmetric_group_properties(G, 4, 6) |
| return G |
|
|
|
|
| def A4xC2(): |
| """ |
| Return a representation of the (A4 x C2) transitive subgroup of S6. |
| |
| Notes |
| ===== |
| |
| This was computed using :py:func:`~.find_transitive_subgroups_of_S6`. |
| |
| """ |
| return PermutationGroup( |
| Permutation(0, 4, 5)(1, 3, 2), Permutation(0, 1, 2)(3, 5, 4), |
| Permutation(5)(2, 4)) |
|
|
|
|
| def S4xC2(): |
| """ |
| Return a representation of the (S4 x C2) transitive subgroup of S6. |
| |
| Notes |
| ===== |
| |
| This was computed using :py:func:`~.find_transitive_subgroups_of_S6`. |
| |
| """ |
| return PermutationGroup( |
| Permutation(1, 4, 5, 3), Permutation(0, 4)(1, 5)(2, 3), |
| Permutation(1, 4)(3, 5)) |
|
|
|
|
| def G18(): |
| """ |
| Return a representation of the group G18, a transitive subgroup of S6 |
| isomorphic to the semidirect product of C3^2 with C2. |
| |
| Notes |
| ===== |
| |
| This was computed using :py:func:`~.find_transitive_subgroups_of_S6`. |
| |
| """ |
| return PermutationGroup( |
| Permutation(5)(0, 1, 2), Permutation(3, 4, 5), |
| Permutation(0, 4)(1, 5)(2, 3)) |
|
|
|
|
| def G36m(): |
| """ |
| Return a representation of the group G36-, a transitive subgroup of S6 |
| isomorphic to the semidirect product of C3^2 with C2^2. |
| |
| Notes |
| ===== |
| |
| This was computed using :py:func:`~.find_transitive_subgroups_of_S6`. |
| |
| """ |
| return PermutationGroup( |
| Permutation(5)(0, 1, 2), Permutation(3, 4, 5), |
| Permutation(1, 2)(3, 5), Permutation(0, 4)(1, 5)(2, 3)) |
|
|
|
|
| def G36p(): |
| """ |
| Return a representation of the group G36+, a transitive subgroup of S6 |
| isomorphic to the semidirect product of C3^2 with C4. |
| |
| Notes |
| ===== |
| |
| This was computed using :py:func:`~.find_transitive_subgroups_of_S6`. |
| |
| """ |
| return PermutationGroup( |
| Permutation(5)(0, 1, 2), Permutation(3, 4, 5), |
| Permutation(0, 5, 2, 3)(1, 4)) |
|
|
|
|
| def G72(): |
| """ |
| Return a representation of the group G72, a transitive subgroup of S6 |
| isomorphic to the semidirect product of C3^2 with D4. |
| |
| Notes |
| ===== |
| |
| See [1], Page 325. |
| |
| """ |
| return PermutationGroup( |
| Permutation(5)(0, 1, 2), |
| Permutation(0, 4, 1, 3)(2, 5), Permutation(0, 3)(1, 4)(2, 5)) |
|
|
|
|
| def PSL2F5(): |
| r""" |
| Return a representation of the group $PSL_2(\mathbb{F}_5)$, as a transitive |
| subgroup of S6, isomorphic to $A_5$. |
| |
| Notes |
| ===== |
| |
| This was computed using :py:func:`~.find_transitive_subgroups_of_S6`. |
| |
| """ |
| G = PermutationGroup( |
| Permutation(0, 4, 5)(1, 3, 2), Permutation(0, 4, 3, 1, 5)) |
| set_alternating_group_properties(G, 5, 6) |
| return G |
|
|
|
|
| def PGL2F5(): |
| r""" |
| Return a representation of the group $PGL_2(\mathbb{F}_5)$, as a transitive |
| subgroup of S6, isomorphic to $S_5$. |
| |
| Notes |
| ===== |
| |
| See [1], Page 325. |
| |
| """ |
| G = PermutationGroup( |
| Permutation(0, 1, 2, 3, 4), Permutation(0, 5)(1, 2)(3, 4)) |
| set_symmetric_group_properties(G, 5, 6) |
| return G |
|
|
|
|
| def find_transitive_subgroups_of_S6(*targets, print_report=False): |
| r""" |
| Search for certain transitive subgroups of $S_6$. |
| |
| The symmetric group $S_6$ has 16 different transitive subgroups, up to |
| conjugacy. Some are more easily constructed than others. For example, the |
| dihedral group $D_6$ is immediately found, but it is not at all obvious how |
| to realize $S_4$ or $S_5$ *transitively* within $S_6$. |
| |
| In some cases there are well-known constructions that can be used. For |
| example, $S_5$ is isomorphic to $PGL_2(\mathbb{F}_5)$, which acts in a |
| natural way on the projective line $P^1(\mathbb{F}_5)$, a set of order 6. |
| |
| In absence of such special constructions however, we can simply search for |
| generators. For example, transitive instances of $A_4$ and $S_4$ can be |
| found within $S_6$ in this way. |
| |
| Once we are engaged in such searches, it may then be easier (if less |
| elegant) to find even those groups like $S_5$ that do have special |
| constructions, by mere search. |
| |
| This function locates generators for transitive instances in $S_6$ of the |
| following subgroups: |
| |
| * $A_4$ |
| * $S_4^-$ ($S_4$ not contained within $A_6$) |
| * $S_4^+$ ($S_4$ contained within $A_6$) |
| * $A_4 \times C_2$ |
| * $S_4 \times C_2$ |
| * $G_{18} = C_3^2 \rtimes C_2$ |
| * $G_{36}^- = C_3^2 \rtimes C_2^2$ |
| * $G_{36}^+ = C_3^2 \rtimes C_4$ |
| * $G_{72} = C_3^2 \rtimes D_4$ |
| * $A_5$ |
| * $S_5$ |
| |
| Note: Each of these groups also has a dedicated function in this module |
| that returns the group immediately, using generators that were found by |
| this search procedure. |
| |
| The search procedure serves as a record of how these generators were |
| found. Also, due to randomness in the generation of the elements of |
| permutation groups, it can be called again, in order to (probably) get |
| different generators for the same groups. |
| |
| Parameters |
| ========== |
| |
| targets : list of :py:class:`~.S6TransitiveSubgroups` values |
| The groups you want to find. |
| |
| print_report : bool (default False) |
| If True, print to stdout the generators found for each group. |
| |
| Returns |
| ======= |
| |
| dict |
| mapping each name in *targets* to the :py:class:`~.PermutationGroup` |
| that was found |
| |
| References |
| ========== |
| |
| .. [2] https://en.wikipedia.org/wiki/Projective_linear_group#Exceptional_isomorphisms |
| .. [3] https://en.wikipedia.org/wiki/Automorphisms_of_the_symmetric_and_alternating_groups#PGL%282,5%29 |
| |
| """ |
| def elts_by_order(G): |
| """Sort the elements of a group by their order. """ |
| elts = defaultdict(list) |
| for g in G.elements: |
| elts[g.order()].append(g) |
| return elts |
|
|
| def order_profile(G, name=None): |
| """Determine how many elements a group has, of each order. """ |
| elts = elts_by_order(G) |
| profile = {o:len(e) for o, e in elts.items()} |
| if name: |
| print(f'{name}: ' + ' '.join(f'{len(profile[r])}@{r}' for r in sorted(profile.keys()))) |
| return profile |
|
|
| S6 = SymmetricGroup(6) |
| A6 = AlternatingGroup(6) |
| S6_by_order = elts_by_order(S6) |
|
|
| def search(existing_gens, needed_gen_orders, order, alt=None, profile=None, anti_profile=None): |
| """ |
| Find a transitive subgroup of S6. |
| |
| Parameters |
| ========== |
| |
| existing_gens : list of Permutation |
| Optionally empty list of generators that must be in the group. |
| |
| needed_gen_orders : list of positive int |
| Nonempty list of the orders of the additional generators that are |
| to be found. |
| |
| order: int |
| The order of the group being sought. |
| |
| alt: bool, None |
| If True, require the group to be contained in A6. |
| If False, require the group not to be contained in A6. |
| |
| profile : dict |
| If given, the group's order profile must equal this. |
| |
| anti_profile : dict |
| If given, the group's order profile must *not* equal this. |
| |
| """ |
| for gens in itertools.product(*[S6_by_order[n] for n in needed_gen_orders]): |
| if len(set(gens)) < len(gens): |
| continue |
| G = PermutationGroup(existing_gens + list(gens)) |
| if G.order() == order and G.is_transitive(): |
| if alt is not None and G.is_subgroup(A6) != alt: |
| continue |
| if profile and order_profile(G) != profile: |
| continue |
| if anti_profile and order_profile(G) == anti_profile: |
| continue |
| return G |
|
|
| def match_known_group(G, alt=None): |
| needed = [g.order() for g in G.generators] |
| return search([], needed, G.order(), alt=alt, profile=order_profile(G)) |
|
|
| found = {} |
|
|
| def finish_up(name, G): |
| found[name] = G |
| if print_report: |
| print("=" * 40) |
| print(f"{name}:") |
| print(G.generators) |
|
|
| if S6TransitiveSubgroups.A4 in targets or S6TransitiveSubgroups.A4xC2 in targets: |
| A4_in_S6 = match_known_group(AlternatingGroup(4)) |
| finish_up(S6TransitiveSubgroups.A4, A4_in_S6) |
|
|
| if S6TransitiveSubgroups.S4m in targets or S6TransitiveSubgroups.S4xC2 in targets: |
| S4m_in_S6 = match_known_group(SymmetricGroup(4), alt=False) |
| finish_up(S6TransitiveSubgroups.S4m, S4m_in_S6) |
|
|
| if S6TransitiveSubgroups.S4p in targets: |
| S4p_in_S6 = match_known_group(SymmetricGroup(4), alt=True) |
| finish_up(S6TransitiveSubgroups.S4p, S4p_in_S6) |
|
|
| if S6TransitiveSubgroups.A4xC2 in targets: |
| A4xC2_in_S6 = search(A4_in_S6.generators, [2], 24, anti_profile=order_profile(SymmetricGroup(4))) |
| finish_up(S6TransitiveSubgroups.A4xC2, A4xC2_in_S6) |
|
|
| if S6TransitiveSubgroups.S4xC2 in targets: |
| S4xC2_in_S6 = search(S4m_in_S6.generators, [2], 48) |
| finish_up(S6TransitiveSubgroups.S4xC2, S4xC2_in_S6) |
|
|
| |
| |
| N_gens = [Permutation(5)(0, 1, 2), Permutation(5)(3, 4, 5)] |
|
|
| if S6TransitiveSubgroups.G18 in targets: |
| G18_in_S6 = search(N_gens, [2], 18) |
| finish_up(S6TransitiveSubgroups.G18, G18_in_S6) |
|
|
| if S6TransitiveSubgroups.G36m in targets: |
| G36m_in_S6 = search(N_gens, [2, 2], 36, alt=False) |
| finish_up(S6TransitiveSubgroups.G36m, G36m_in_S6) |
|
|
| if S6TransitiveSubgroups.G36p in targets: |
| G36p_in_S6 = search(N_gens, [4], 36, alt=True) |
| finish_up(S6TransitiveSubgroups.G36p, G36p_in_S6) |
|
|
| if S6TransitiveSubgroups.G72 in targets: |
| G72_in_S6 = search(N_gens, [4, 2], 72) |
| finish_up(S6TransitiveSubgroups.G72, G72_in_S6) |
|
|
| |
|
|
| if S6TransitiveSubgroups.PSL2F5 in targets: |
| PSL2F5_in_S6 = match_known_group(AlternatingGroup(5)) |
| finish_up(S6TransitiveSubgroups.PSL2F5, PSL2F5_in_S6) |
|
|
| if S6TransitiveSubgroups.PGL2F5 in targets: |
| PGL2F5_in_S6 = match_known_group(SymmetricGroup(5)) |
| finish_up(S6TransitiveSubgroups.PGL2F5, PGL2F5_in_S6) |
|
|
| |
| |
| |
|
|
| if S6TransitiveSubgroups.C6 in targets: |
| C6 = match_known_group(CyclicGroup(6)) |
| finish_up(S6TransitiveSubgroups.C6, C6) |
|
|
| if S6TransitiveSubgroups.S3 in targets: |
| S3 = match_known_group(SymmetricGroup(3)) |
| finish_up(S6TransitiveSubgroups.S3, S3) |
|
|
| if S6TransitiveSubgroups.D6 in targets: |
| D6 = match_known_group(DihedralGroup(6)) |
| finish_up(S6TransitiveSubgroups.D6, D6) |
|
|
| if S6TransitiveSubgroups.A6 in targets: |
| A6 = match_known_group(A6) |
| finish_up(S6TransitiveSubgroups.A6, A6) |
|
|
| if S6TransitiveSubgroups.S6 in targets: |
| S6 = match_known_group(S6) |
| finish_up(S6TransitiveSubgroups.S6, S6) |
|
|
| return found |
|
|
