Which is the smallest number $n$ such that $S_n$ has non-isomorphic subgroups of the same order with the same number of cyclic subgroups of the same order?

Example: $S_4$ has subgroups of order $4$ isomorphic to $Z_4$ and $Z_2\times Z_2$. Here $Z_4$ has only one cyclic subgroup of order $2$ while $Z_2\times Z_2$ has three cyclic subgroups of order 2, so the test with cyclic subgroups shows that $Z_4$ and $Z_2\times Z_2$ is not isomorphic.

The idea with the cyclic subgroup test is to make a first (fast) try to falsify that two finite groups of the same order are isomorphic - in a set based system for computational algebra.

Unfortunately, set based group implementations are slow, so I can't make a systematic test, but have tested a lot of groups with same order so far without finding examples of non-isomorphic groups which fails in the test.

  • $\begingroup$ Can you clarify what "a lot of groups" constitutes? $\endgroup$ – zibadawa timmy Mar 12 '16 at 9:46
  • $\begingroup$ $\Bbb Z_2\times \Bbb Z_2\;$ has three, not only two, subgroups of order two. $\endgroup$ – DonAntonio Mar 12 '16 at 9:56
  • $\begingroup$ I believe I just wrote some GAP code which finds several examples of groups of order 16 which are non-isomorphic but have the same number of cyclic subgroups of every order. For example, small group IDs [16,2], [16,4], and [16,12] all have the same number of cyclic subgroups of the same order. These groups have structure description $C_4\times C_4, C_4\rtimes C_4,$ and $C_2\times Q_8$. $\endgroup$ – zibadawa timmy Mar 12 '16 at 10:18
  • $\begingroup$ @Joanpemo, yes you are right. $\endgroup$ – Lehs Mar 12 '16 at 12:45
  • $\begingroup$ @zibadawatimmy: thank you! So I know that $n\leq 16$ then. Well, my system has a poor implementation of groups so far. I guess I have to learn GAP for reference requests... $\endgroup$ – Lehs Mar 12 '16 at 12:49

The following GAP code will go through all groups of order 16 (which is easily changed to other orders in the small group package) and will find the number of every cyclic group of every order in each such group. The values stored in vallist are a list of lists, where each entry gives the SmallGroup ID number for the relevant cyclic group in the first entry and the total number of copies of that cyclic subgroup as the second number. It then adds the completed vallist as an element of cyclist. So the vallist for SmallGroup(16,4), for example, is the 4th entry of cyclist: cyclist[4];

cyclist := []; 

for G in AllSmallGroups(16) 
    vallist := []; 
    subs := Filtered(ConjugacyClassesSubgroups(G),X->IsCyclic(Representative(X)));  
    subclasses := Set(List(subs,H->IdGroup(Representative(H)))); 
    for H in subclasses 
        subnumber := Sum(List(Filtered(subs,X->IdGroup(Representative(X))=H),Size)); 


The final line just prints the entire contents of cyclist, and can be omitted.

Two groups will have the same number of cyclic subgroups of every order if and only if they yield the same vallist. So you can perform various searches or logical tests to find all such groups. For example


will spit out the positions in cyclist of every entry that is identical to cyclist[4]. In this case the output should be


Meaning that SmallGroup(16,2), SmallGroup(16,4), and SmallGroup(16,12) all have the same number of cyclic subgroups of every order. Applying the StructureDescription function to all of these yields, respectively

\begin{align*} C_4\times C_4\\ C_4\rtimes C_4\\ C_2\times Q_8 \end{align*}

I'll note at this stage that this is not the only set of groups of order 16 which share this property. The desired relation is clearly an equivalence relation, and the (non-singleton) classes can be computed via


yielding the output

[ [ 2, 4, 12 ], [ 3, 10, 13 ], [ 5, 6 ] ]

The first and last classes have two subgroups that can be embedded into $S_{10}$ (which can be proven by a few known facts, or using gap code such as what I'm about to use). The second class, however, is much more interesting. We can compute permutation representations of small degree for them and notice the highest number that appears to find the upper bound for the $S_n$ they each embed into.



[ Group([ (1,2,4,6)(3,5,7,8), (2,5)(6,8), (1,3)(2,5)(4,7)(6,8), (1,4)(2,6)(3,7)(5,8) ]), 
Group([ (1,2), (3,4), (5,6,7,8) ]), 
Group([ (2,6)(5,8), (1,2)(3,5)(4,6)(7,8), (1,3,4,7)(2,5,6,8), (1,4)(2,6)(3,7)(5,8) ]) ]

Therefore, all three of these groups embed into $S_8$. So we have an upper bound of $n\leq 8$. Note that GAP does not guarantee that the degrees of the representations above are the actual minimum.

So what's a lower bound?

The following code is one way to check smaller symmetric groups for such subgroups.

    for n in [3..7]
        G := SymmetricGroup(n);
        subgroups := Filtered(ConjugacyClassesSubgroups(G),X->Order(Representative(X))<Factorial(n)/2;
        subgroups := Set(List(subgroups,X->IdGroup(Representative(X))));

        testlist := [];

        for Hh in subgroups 
            H := SmallGroup(Hh);
            vallist := [];

            cycsubs := Filtered(ConjugacyClassesSubgroups(H),X->IsCyclic(Representative(X)));

            cyctypes := Set(List(cycsubs,X->IdGroup(Representative(X))));

            for K in cyctypes
                subnumber := Sum(List(Filtered(cycsubs,X->IdGroup(Representative(X))=K),Size));


    truthvals := List(testlist, L->Size(Filtered(testlist,M->M=L))>1);

    if ForAny(truthvals,X->X) then Print(n, "\n") ; break; fi;

It'll simply print out the value $n$ if $S_n$ has non-isomorphic subgroups which have the same number of cyclic groups of every order. In this case, it prints out nothing. So we have a lower bound $n\geq 8$, and thus $n=8$ is the answer.

Note the first definition of subgroups excludes $S_n$ and $A_n$--these subgroups are the unique subgroups of their order in $S_n$, so we may safely exclude them. This has the added advantage of making sure that all calls to IdGroup will be valid: $A_7$ and $S_7$ are not covered by the SmallGroups package, and therefore using IdGroup on them would result in errors. With them safely excluded, all groups that occur work with IdGroup, which is all we need to determine isomorphism types.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.