# Does the hypergraph structure of the set of subgroups of a finite group characterize isomorphism type?

Question

Suppose there is a bijection between the underlying sets of two finite groups $$G, H$$, such that every subgroup of $$G$$ corresponds to a subgroup of $$H$$, and that every subgroup of $$H$$ corresponds to a subgroup of $$G$$. Does this imply that $$G, H$$ are isomorphic? Note that we do not require the bijection to actually be the isomorphism.

Motivation

The question is interesting to me because I am considering maps of groups which aren't homomorphisms but preserve the subgroup structure in some sense - given a group, we can forget the multiplication operation and look only at the closure operator that maps a subset of $$G$$ to the subgroup generated by it. If the question is resolved in the affirmative, then the forgetful functor from the usual category $$Grp$$ to this category won't create any new isomorphisms. (Note that I didn't precisely specify the morphisms this new category -- you could just use the usual definition of a homomorphism, and say that if the mapping commutes with the closure operator, then its a morphism. The definition I actually care about is, a morphism of this category is a mapping such that every closed set in the source object is the preimage of a closed set of the target object. It doesn't make much difference as far as this question is concerned, the isomorphisms of both categories are the same.)

I asked a friend at Mathcamp about this a few weeks ago, he said a bunch of people started thinking about it but got stumped after a while. The consensus seems to have been that it is probably false, but the only counter examples may be very large. I don't really have any good ideas / tools for how to prove it might be true, I mostly wanted to just ask if anyone knew offhand / had good intuition for how to find a finite counterexample.

Edit (YCor): (a) the question has reappeared in the following formulation: does the hypergraph structure of the set of subgroups of a (finite) group determine its isomorphism type? A hypergraph is a set endowed with a set of subsets. The hypergraph of subgroups is the data of the set of subgroups, and therefore to say that groups $$G,H$$ have isomorphic hypergraphs of subgroups means that there's a bijection $$f:G\to H$$ such that for every subset $$A\subset G$$, $$f(A)$$ is a subgroup of $$H$$ if and only $$A$$ is a subgroup of $$G$$. Several answers, complementing the one given here, have been provided in this question.

(b) There a weaker well-studied notion for groups, namely to have isomorphic subgroup lattices. Having isomorphic hypergraphs of subgroups requires such an isomorphism to be implemented by a bijection (this is not always the case: take two groups of distinct prime order).

• For finite abelian groups, I think the answer is "yes, they are isomorphic". – Steve D Aug 13 '10 at 9:44
• I removed my answer since the definition of the second group operation was buggy causing that the proof was wrong that all subgroups with respect to the second operation are subgroups with respect of the first operation. – j.p. Aug 13 '10 at 21:29
• An easy example giving a negative answer. Let $p>2$, $G$ be abelian of type $(p^2,p)$ and $H$ is nonabelian metacyclic of order $p^3$. – yakov Sep 16 '16 at 9:05

The answer is no in general. I.e, there are finite non-isomorphic groups G and H such that there exists a bijection between their elements which also induces a bijection between their subgroups.

For this, I used two non-isomorphic groups which not only have the same subgroup lattice (which certainly is necessary), but also have the same conjugacy classes. There are two such groups of size 605, both a semidirect product $$(C_{11}\times C_{11}) \rtimes C_5$$ (see this site for details on the construction). In the small group library of GAP, these are the groups with id [ 605, 5 ] and. [ 605, 6 ]. These are provably non-isomorphic (you can construct the groups as described in the reference I gave, and then use GAPs IdSmallGroup command to verify that the groups described there are the same as the ones I am working with here). With a short computer program, one can now construct a suitable bijection.

First, let us take the two groups:

gap> G:=SmallGroup(605, 5);
<pc group of size 605 with 3 generators>
gap> H:=SmallGroup(605, 6);
<pc group of size 605 with 3 generators>


The elements of these groups are of order 1, 5 or 11, and there are 1, 484 and 120 of each. We will sort them in a "nice" way (that is, we try to match each subgroup of order 5 to another one, element by element) and obtain a bijection from this. First, a helper function to give us all elements in "nice" order:

ElementsInNiceOrder := function (K)
local elts, cc;
elts := [ One(K) ];
cc := ConjugacyClassSubgroups(K, Group(K.1));
Append(elts, Concatenation(List(cc, g -> Filtered(g,h->Order(h)=5))));
Append(elts, Filtered(Group(K.2, K.3), g -> Order(g)=11));
return elts;
end;;


Now we can take the elements in the nice order and define the bijection $$f$$:

gap> Gelts := ElementsInNiceOrder(G);;
gap> Helts := ElementsInNiceOrder(H);;
gap> f := g -> Helts[Position(Gelts, g)];;


Finally, we compute the sets of all subgroups of $$G$$ resp. $$H$$, and verify that $$f$$ induces a bijection between them:

gap> Gsubs := Union(ConjugacyClassesSubgroups(G));;
gap> Hsubs := Union(ConjugacyClassesSubgroups(H));;
gap> Set(Gsubs, g -> Group(List(g, f))) = Hsubs;
true


Thus we have established the claim with help of a computer algebra system. From this, one could now obtain a pen & paper proof for the claim, if one desires so. I have not done this in full detail, but here are some hints.

Say $$G$$ is generated by three generators $$g_1,g_2,g_3$$, where $$g_1$$ generates the $$C_5$$ factor and $$g_2,g_3$$ generate the characteristic subgroup $$C_{11}\times C_{11}$$. We choose a similar generating set $$h_1,h_2,h_3$$ for $$H$$. We now define $$f$$ in two steps: First, for $$0\leq n,m <11$$ it shall map $$g_2^n g_3^m$$ to $$h_2^n h_3^m$$.

This covers all elements of order 1 or 11, so in step two we specify how to map the remaining elements, which all have order 5. These are split into four conjugacy classes: $$g_1^G$$, $$(g_1^2)^G$$, $$(g_1^3)^G$$ and $$(g_1^4)^G$$. We fix any bijection between $$g_1^G$$ and $$h_1^H$$ and extend that to a bijection on all elements of order 5 by the rule $$f((g_1^g)^n)=f(g_1^g)^n$$. With some effort, one can now verify that this is a well-defined bijection between $$G$$ and $$H$$ with the desired properties. You will need to determine the subgroup lattice in each case; linear algebra helps a bit, as well as the fact that all subgroups have order 1, 5, 11, 55, 121 (unique) or 605. I'll leave the details to the reader, as I myself am happy enough with the computer result.

UPDATE: as pointed out in another answer below by @dvitek (explained by @Ian Agol in comments), there is actually a much simpler example, which I somehow overlooked when I did my computer search. Credit to them, but just in case people want to reproduce their example with GAP, here is an input session doing just that:

gap> G:=SmallGroup(16,5);; StructureDescription(G);
"C8 x C2"
gap> H:=SmallGroup(16,6);; StructureDescription(H);
"C8 : C2"
gap> Gelts := ListX([1..8],[1,2],{i,j}->G.1^i*G.2^j);;
gap> Helts := ListX([1..8],[1,2],{i,j}->H.1^i*H.2^j);;
gap> f := g -> Helts[Position(Gelts, g)];;
gap> Gsubs := Union(ConjugacyClassesSubgroups(G));;
gap> Hsubs := Union(ConjugacyClassesSubgroups(H));;
gap> Set(Gsubs, g -> Group(List(g, f))) = Hsubs;
true

• Very nice answer! – Cam McLeman Aug 17 '10 at 18:00
• Wow, I can't believe that ordering works! It is completely arbitrary dependent on how GAP chooses to order the elements, right? Out of curiosity, do you have reason to believe that a random bijection that respects the orders of elements should work, for most large enough groups, if not all groups, or something along these lines? I intend to accept the answer, I'd just like to work out the pencil and paper proof myself first :) – Chris Beck Aug 18 '10 at 8:54
• The construction for the groups is general, so you can construct infinitely many. All these are (super)solvable. So, what about simple groups? My hunch: They won't work (there are few pairs of simple groups of equal order); using the existing knowledge of the maximal subgroups of simple groups one should be able to resolve this. My example seems to be pretty "rare", the "equal conjugacy classes" property is strong. The order chosen by GAP is deterministically "random". It works so well because all the subgroups of order 5 intersect each other trivially, and also the subgroup of order $11^2$. – Max Horn Aug 18 '10 at 9:57
• I just modified ElementsInNiceOrder to randomly permute the subgroups of order 5 (equivalently, the conjugacy class $g_1^G$), and run the program a couple hundred times. That empirically confirms my claim. To prove it in general, you have to show that any permutation of the order 5 groups extends to an automorphism of the subgroup lattice. Every subgroup of order 5 is in exactly 2 groups of order 55. There are 22 subgroups of these in total, split into 2 conjugacy classes of size 11. Pick any pair, their intersection defines a unique group of order 5 -- so we get all $11^2=121$ of them! – Max Horn Aug 18 '10 at 10:13
• I found a better answer!: math.stackexchange.com/questions/14588/… – Ángel Valencia Jul 10 '16 at 19:40

The modular group of order 16 and the group C8 x C2 have the same subgroup lattice. Does this provide a counterexample to what you are trying to prove?

• No it doesn't, one can (either manually, or by using a computer algebra system such as GAP) verify that no bijection of the desired nature exists for these two groups. Same for the similar example of two groups of order 32 with the same subgroup lattice. – Max Horn Aug 16 '10 at 11:18
• @ Max: actually, there seems to be a bijection preserving subgroups. The modular group $G$ has subgroups $C_8 =\langle s\rangle$ and $C_2=\langle t\rangle$, and $G=C_8 \times C_2$ (a product of cosets if you like) according to the link given by drvitek. Then the obvious bijection preserves the subgroup lattice. If you look at the list of subgroups, since $\langle s^2\rangle$ is central in $G$, the subgroup $\langle s^2\rangle \times C_2 \cong C_4\times C_2$, and so every subgroup of $G$ not involving an element with an odd power of $s$ will be equivalent to a subgroup of $C_8\times C_2$. – Ian Agol Aug 18 '10 at 4:30
• @ Max (cont.): The only two groups with an odd power of $s$ are $\langle s\rangle \cong C_8$ and $\langle st\rangle \cong C_8$ correspond to the two subgroups of $C_8\times C_2$ of order 8, depending on whether the $C_2$ coordinate of a generator is 0 or 1 respectively. (in my previous comment, I should have used the notation $G=C_8\cdot C_2$, to indicate a product of cosets). – Ian Agol Aug 18 '10 at 4:36
• This answer is suitable here as a comment: mathoverflow.net/questions/34914/… – Unknown Sep 4 '10 at 17:43
• Errr, I guess I don't know what "the modular group of order 16" means... I'll read up on that and then reply – Max Horn May 27 at 7:53

To expand on Steve D's comment, the answer is indeed yes for finite abelian groups. The following is a simplified version of an earlier proof (rendering some of the below comments obsolete).

Proof. We proceed by (strong) induction on $$|G|$$. Let $$G$$ and $$H$$ be finite abelian groups for which there exists a bijection $$f:G \to H$$ that preserves subgroups.

Suppose $$G=A \oplus B$$, where $$A$$ and $$B$$ are both proper subgroups of $$G$$. By induction, $$A \cong f(A)$$ and $$B \cong f(B)$$. Since $$A \cap B=\{0\}$$, we conclude that $$f(A) \cap f(B)=\{f(0)\}$$. Since $$f$$ preserves subgroups, $$f(A)$$ and $$f(B)$$ are both subgroups of $$H$$, whose interection is the zero element of $$H$$. Moreover, since $$|f(A)||f(B)|= |H|$$, it follows that $$H = f(A) \oplus f(B) \cong A \oplus B \cong G$$. Therefore, we are done unless $$G=\mathbb Z / p^k \mathbb Z$$. However, by interchanging the roles of $$G$$ and $$H$$ we conclude that $$H$$ is also equal to $$\mathbb Z / p^k \mathbb Z$$.

• It takes a bit of work to conclude that $f(A)$ is a cyclic subgroup of $B$ of the largest order, because for an abelian group, the property of being cyclic cannot be detected from the subgroup lattice. But note that a finite abelian group is a direct product of its $p$-components, and so the question can be reduced to abelian $p$-groups from the outset. A finite abelian group of prime power order is cyclic if and only if it is uniserial (i.e. its subgroups are linearly ordered). Thus if $A$ is a maximal cyclic subgroup of order $p^m$ for some $p$ then the same holds for $f(A).$ – Victor Protsak Aug 14 '10 at 4:32
• I think the fact that $f(A)$ is a cyclic subgroup of $B$ of the largest order follows from the way the induction is set up. If $B' \neq H$ is a larger order cyclic subgroup of $H$, then $f^{-1}(B') \cong B'$ by induction, which contradicts the fact that $A$ is a largest order cyclic subgroup of $G$. – Tony Huynh Aug 14 '10 at 17:57
• My objection was not about the order, but about the assertion that $f(A)$ is cyclic, but I see now that it's true by the inductive assumption. – Victor Protsak Aug 15 '10 at 8:14
• Sorry to arrive late with this comment. The claim that one cannot recognize a cyclic subgroup by looking at its subgroup lattice, while inconsequential for the matter at hand, is false. A theorem of Ore says that a finite group is cyclic if and only if its subgroup lattice is distributive. See Structures and Group Theory, II, Duke Math. J. 4, 1938. – John Shareshian Sep 4 '10 at 19:58
• @JohnShareshian: Is there any known generalization of Ore's Theorem to infinite cyclic groups? – user 170039 Sep 1 '18 at 4:06