# Is there an unique “minimal enclosing group” for any two groups?

I'm not sure I'm using the correct terms, therefore let me define what I mean:

Given a set of groups $G_i$, $i\in I$, I call an enclosing group of those groups any group $G$ so that for all $i\in I$ there exists a subgroup $H_i$ of $G$ which is isomorphic to $G_i$. As an example, the direct product of groups is an enclosing group of those groups. Also each group trivially encloses all its subgroups.

I call an enclosing group minimal if there's no subgroup of $G$ which also encloses the given set of groups. For example, unless I'm mistaken, the group $U(2)$ is a minimal enclosing group of $SU(2)$ and $U(1)$.

My question now is: Is there, up to isomorphism, an unique minimal enclosing group for any set of groups?

There are a few simple cases where this is obviously the case:

• If the set is empty, obviously the trivial group $\{e\}$ is the only minimal enclosing group.
• If the set has only one element, that element is the only minimal enclosing group.
• If all members of the set are subgroups of some specific member of that set, that member is the only minimal enclosing group.
-
I don't think this is true. Taking as your groups $\mathbb{Z}_2$ and $\mathbb{Z}_3$, both $\mathbb{Z}_2\times\mathbb{Z}_3$ and $S_3$ seem to be minimal enclosing groups. – Miha Habič Jul 19 '12 at 9:29
Your second bullet point is false. If $G$ has proper subgroups isomorphic to itself (like $(\mathbb{R},+)$, say) then $G$ is not a minimal enclosing group for $\{ G \}$, and in fact $\{ G \}$ has no minimal enclosing group. – Chris Eagle Jul 19 '12 at 9:40
You might consider a similar but different notion of "minimalness" since, as seen in Chris' answer, looking at subgroups might not be useful. Instead, you might want to look at whether there exists a universal object in the category of groups with monomorphisms from each of the given groups. – Tobias Kildetoft Jul 19 '12 at 10:02
@ChrisEagle: Good point, I didn't think about that possibility. – celtschk Jul 19 '12 at 10:07
@Tobias: Maybe you are right, but unfortunately I don't understand what you say :-) My knowledge about category theory is, well, minimal. – celtschk Jul 19 '12 at 10:09

As stated in the comments, this is false. Considering the two cyclic groups $\mathbb{Z}_2$ and $\mathbb{Z}_3$, both $\mathbb{Z}_2\times\mathbb{Z}_3$ and $S_3$ are enclosing groups and both are minimal, due to cardinality constraints.

-
My group theory is kinda weak, but why are they not isomorphic? $\mathbb{Z}_2\times\mathbb{Z}_3$ is abelian and $S_3$ is not? – akkkk Jul 19 '12 at 10:04
Thanks, that's indeed a quite simple counterexample. – celtschk Jul 19 '12 at 10:12
@Auke: Yes, the direct product of two abelian groups is always abelian ($(g_1,h_1)(g_2,h_2)=(g_1g_2,h_1h_2)=(g_2g_1,h_2h_1)=(g_2,h_2)(g_1,h_1)$) while $S_3$ isn't ($(12)(123)=(23)$ but $(123)(12)=(13)$). – celtschk Jul 19 '12 at 10:17

In this answer, I change the definition of "minimal enclosing group" a bit to match some standard ideas in group theory that I suspect the OP will like.

## Free products: the universal minimal enclosing group

Suppose $G_1 = \langle (1,2,3) \rangle$ and $G_2 = \left\langle \left(\begin{smallmatrix}0&1\\-1&-1\end{smallmatrix}\right)\right\rangle$. We want a group $G$ that contains both $G_1$ and $G_2$. We want $G$ to be "minimal" in the sense that $G$ does not have any elements it didn't need to have beyond containing $G_1$ and $G_2$.

My schooling has so far been incomplete, and I don't know how to multiply permutations and matrices, but I know $G$ is going to have to contain such products. In fact if $G$ is going to be minimal, then that is all it should contain: products of permutations and matrices.

For instance, $G$ is going to have to include $(1,2,3) \cdot \left(\begin{smallmatrix}0&1\\-1&-1\end{smallmatrix}\right) \cdot (1,2,3)$. In general $G$ as a set will consist of all $h_1 \cdot h_2 \cdots h_n$ where each $h_i$ either comes from $G_1$ or $G_2$.

What sort of rules should the product $\cdot$ obey? Well one obvious thing is that $(1,2,3) \cdot (1,2,3)$ better still be $(1,3,2)$. So if we ever have $h_1$ and $h_2$ from the same $G_i$, we probably ought to replace $h_1 \cdot h_2 \cdots h_n$ with the shorter $h_1' \cdot h_2' \cdots h_{n-1}'$ where $h_1' = (h_1 h_2) \in G_i$ and then $h_2' = h_3$, etc. In other words, we just shorten the formal product when we can by actually multiplying elements from the same $G_i$ together.

One other rule is needed: How do $(1,2,3)\cdot(3,2,1)$ and $\left(\begin{smallmatrix}0&1\\-1&-1\end{smallmatrix}\right) \cdot \left(\begin{smallmatrix}-1&-1\\1&0\end{smallmatrix}\right)$ compare? They are both the identity in $G_i$, so they both need to be the identity in $G$. In this case we want to remove irrelevant multiplications by identities. So if $h_1$ is the identity, we want to define $h_1' = h_2$, $h_2' = h_3$, etc. so that our new formal product is just shorter.

It is not too hard to check that using these two rules is sufficient to define a group $G$! We let $\tilde G$ be the set of all finite sequences $(h_1,h_2,\cdots,h_n)$ with each $h_j$ from some $G_i$ (with $i$ and $j$ not necessarily related). To define $G$ itself we need to get rid of the superfluous sequences that can be simplified. We can do this with a subset or a quotient set. The subset way: say that $(h_1,h_2,\cdots,h_n)$ is simplified if (1) no $h_i$ is the identity and (2) there is no $j$ with both $h_j, h_{j+1} \leq H_i$. Let $G$ be the set of simplified sequences. The quotient way: we say that $(h_1,h_2,\cdots,h_n)$ can be simplified to $(h_1',h_2',\cdots,h_{n-1}')$ if either (1) there is some $j$ such that $h_j$ and $h_{j+1}$ are both in $H_i$ and $$h_k' = \begin{cases} h_k & \text{if } k < j \\ h_{j} h_{j+1} & \text{if } k = j \\ h_{k+1} & \text{if } k > j \end{cases}$$ or (2) there is some $j$ such that $h_j$ is the identity and $$h_k' = \begin{cases} h_k & \text{if } k < j \\ h_{k+1} & \text{if } k \geq j \end{cases}$$ Then $G$ is the equivalence classes of $\tilde G$ under the reflexive, symmetric, transitive closure of the relation "can be simplified to". Notice that each equivalence class contains only one simplified word. Multiplication in the group is very easy: since $(h_1, h_2, \cdots,h_n)$ is supposed to represent $h_1 \cdot h_2 \cdots h_n$, multiplication is defined as $(h_1, h_2, \cdots,h_n) \cdot (h_{n+1}, h_{n+2}, \cdots,h_{n+m}) = (h_1, h_2, \cdots, h_n, h_{n+1}, h_{n+2}, \cdots, h_{n+m})$.

The identity is a little strange, since the identities of both $G_i$ get simplified away. The result is just the empty sequence with $n=0$, which I denote as $()$.

In particular, elements of our $G$ will look like $(1,2,3) \cdot \left(\begin{smallmatrix}0&1\\-1&-1\end{smallmatrix}\right) \cdot (1,2,3)$ and we can square this element to get $${\left((1,2,3) \cdot \left(\begin{smallmatrix}0&1\\-1&-1\end{smallmatrix}\right) \cdot (1,2,3)\right)}^2 = (1,2,3) \cdot \left(\begin{smallmatrix}0&1\\-1&-1\end{smallmatrix}\right) \cdot (1,3,2) \cdot \left(\begin{smallmatrix}0&1\\-1&-1\end{smallmatrix}\right) \cdot (1,2,3)$$

In some sense we are just treating the elements of the groups like variables. We don't need to know what x or y is in order to multiply them: we just get the polynomial xy. Of course $xx=x^2$ and $xy/y = x$ allow us to simplify some things, but in principle we just have strings of variables as the things we add up in polynomials.

Summary: The universal way to contain some subgroups is called the free product and consists of formal products simplified according to two obvious rules.

## Quotients of free products: smaller minimal enclosing groups

The last bit about variables and formal products suggests a neat idea: we can evaluate polynomials to get "real" numbers, like if $x=2$ and $y=3$ then $xy=6$, so why can't we do the same for our universal minimal enclosing group?

Suppose we noticed that there was an isomorphism $f_2: G_2 \to \operatorname{Sym}(6)$ that took $\left(\begin{smallmatrix}0&1\\-1&-1\end{smallmatrix}\right)$ to $(4,5,6)$. Then instead of treating $\left(\begin{smallmatrix}0&1\\-1&-1\end{smallmatrix}\right)$ like a variable (since how are we supposed to multiply it by a permutation?) let's just treat it like the permutation $(4,5,6)$. We know how to multiply permutations, and so now everything is great!

In this case we get $G_6 =\langle (1,2,3), (4,5,6) \rangle \cong G_1 \times G_2$ which is the elementary abelian group of order 9. Since our two groups did not really overlap, but were both normal, we got a very nice minimal enclosing group, the direct product. Of course substituting this value for $\left(\begin{smallmatrix}0&1\\-1&-1\end{smallmatrix}\right)$ defines a homomorphism from the universal minimal enclosing group to this smaller minimal enclosing group: the formal product $h_1 \cdot h_2 \cdots h_n$ just maps to the "real" product in $\operatorname{Sym}(6)$.

Can we get smaller? Well, duh, $G_2$ is also isomorphic to a subgroup of $\operatorname{Sym}(5)$ by mapping $\left(\begin{smallmatrix}0&1\\-1&-1\end{smallmatrix}\right)$ to $(3,4,5)$. Since $5<6$ surely $G_5 < G_6$. So $G_5 = \langle (1,2,3), (3,4,5) \rangle$ contains copies of both $G_1$ and $G_2$ and is generated by those copies, but something wonderful happens! $G_5 = \operatorname{Alt}(5)$ is actually the alternating group of degree 5, a simple group of order 60. In particular, it is not smaller, and neither of $G_5$ nor $G_6$ is a quotient of the other. We have two completely different minimal enclosing groups!

The relationship between them is that they are both quotients of the universal minimal enclosing group.

Of course in this case there is an exceptional small minimal enclosing group: $G_3 = \langle (1,2,3), (1,2,3) \rangle$. In this case $G_1 = G_2 = G$.

Summary: Every minimal enclosing group is a quotient of the universal minimal enclosing group, called the free product.

## Amalgamation: when the $G_i$ are related

In our previous example, we didn't assume the $G_i$ were related or not. In some of our minimal enclosing groups they were equal, but in most they intersected trivially. When we start to care about how the $G_i$ intersect, we come across some ideas like amalgams of groups.

If every pair of $G_i$ all intersect in exactly the same subgroup $G_0$, then we can still form a universal minimal enclosing group $G$ in which the isomorphic images of the $G_i$ all intersect (pairwise) in the image of $G_0$ (which will be the same image, no matter which $G_i$ we imagine it is a subgroup of).

All we need to do to our previous construction is add one more rule about what it means to be simplified and we get the free product with amalgamation. This rule basically requires the $h_k$ to be chosen from a transversal of $G_0$ in $G_i$, except that the first element can be any non-identity element of $G_0$.

Again every minimal enclosing group such that the $G_i$ intersect in at least $G_0$ will be a quotient of this universal $G$, and if $G_0$ is a normal subgroup of the $G_i$ we can form a "direct product with amalgamation" as well.

One feature that I find particularly nice is that if the $G_i$ are finite (and there are finitely many of them), then there are minimal enclosing groups that are still finite. This is an old result of Schreier and produces (in my opinion) beautiful pictures, as shown in the very silly examples from my question: When does a biregular graph for the free product 2∗(2×2) have a 4 cycle?

Summary: If all the $G_i$ intersect in the same subgroup, then we can form the universal minimal enclosing group that respects the intersection, called the free product with amalgamation. Its finite quotients produce pretty graphs.

## Directed sets: when the minimal enclosing group is unique

In order for the universal minimal enclosing group to be the only minimal enclosing group we need the groups to be very tightly related. If there are only finitely many of the groups $G_i$, then condition becomes very, very simple: we need to require that one of the $G_i$, say $G_n$, contains all the others, and that in any enclosing group we want this containment respected. In this case, the universal minimal enclosing group is just $G_n$ itself.

In the infinite case it turns out we can use the idea of limits (more or less from calculus, but these days considered category theory) to have a similar result. I'll describe a more general situation first, so that we can see which ones have a unique answer.

We need to be precise about how $G_i$ and $G_j$ are related. Before we used the $\leq$ subgroup relation. This is pretty good, but it puts a little bit too much emphasis on the sets themselves. Our whole problem was that $G_1$ and $G_2$ had sets that were sort of incompatible: permutations and matrices multiplying together. We want to be able to express relationships even when the underlying sets are uncooperative. A really important idea is that a relationship between $G_i$ and $G_j$ is exactly a homomorphism $f_{i,j}$ from $G_i$ to $G_j$. We want our minimal enclosing group to respect those relations, and this is in turn a relationship between the $G_i$ and $G$. Let $I$ be the index set for the $i$ in the $G_i$, and let $J$ be all the pairs of indices that are related.

Then the thing we want to enclose is the groups $\{ G_i : i \in I \}$ and their relationships $\{ f_{i,j} : G_i \to G_j | (i,j) \in J \}$. A minimal enclosing group is the defined to be a group $G$ that is related to the groups $G_i$ by $f_i : G_i \to G$ and the relations $f_{i,j}$ this time by a simpler equality: $G_i \xrightarrow{f_i} G = G_i \xrightarrow{f_{i,j}} G_j \xrightarrow{f_j} G$. In other words, if $G_i$ and $G_j$ are related by $f_{i,j}$, then their images under $f_i$ and $f_j$ are also related.

In this case we get a very simple description of when the minimal enclosing group is unique. It has nothing to do with the $G_i$ or the $f_{i,j}$ themselves, just the relation $J$ on the set $I$ matters. This was surprising to me, but I guess it should be no surprise: the same was true earlier. It did not matter what the $G_i$ were, only that there were all contained in $G_n$. In other words, we just needed $J=\{ (i,n) : i \in I \}$. The $J$ that work in general are called directed sets. For example, if $J = \{ (i,\infty) : i \in I \}$ for $I = \{1,2,3,\cdots,\infty\}$ then we again get that $G_\infty$ is the universal minimal enclosing group. It is the limit as $i$ goes to infinity of $G_i$. Limits are sort of silly, if $G_\infty$ is already there. A more exciting $J$ that works is $J = \{ (i,i+1) : i \in I \}$ where $I=\{1,2,3,\cdots\}$ without the $\infty$. In this case, the universal minimal enclosing group is still unique (and more excitingly it exists!) and is called the direct limit.

At one point, I thought direct limits were kind of stupid. $G_\infty$ is basically just the union of the $G_i$. All you have to do is write them consistently, and take the union. Then one day I realized that the Sylow 2-subgroup of GL(2,R) is a direct limit I can't seem to write down consistently.

Summary: Directed sets are like your third point: every group is contained in a largest group which is either explicitly one of the $G_i$ or is "directly" implied by them as a $G_\infty$.

## Bad relationships don't end well, but at least it is the end of the answer

Actually, to use the word "enclose" we normally want the homomorphisms to be 1-1, otherwise its more like "squish" than "contain". So let's agree that all the $f_{i,j}$ and $f_i$ must be injective. It turns out that with this restriction, minimal enclosing groups no longer need to exist.

Now a first problem is kind of dumb: if $f_{1,2} :G_1 \to G_2$ and $f_{2,3} : G_2 \to G_3$, then we basically force a relationship $f_{1,3} : G _1 \to G_3$ by $G_1 \xrightarrow{f_{1,3}} G_3 = G_1 \xrightarrow{f_{1,2}} G_2 \xrightarrow{f_{2,3}} G_3$. If we also require a different $f_{1,3}$, then of course no $G$ is going to be able to preserve both relationships. In particular, we need the $f_{i,j}$ to be compatible. If $(i,j)$ and $(j,k)$ are both in $J$, then we might as well require $(i,k)$ to be in $J$ and that $G_i \xrightarrow{f_{i,k}} G_k = G_i \xrightarrow{f_{i,j}} G_j \xrightarrow{f_{j,k}} G_k$.

I think category theory type people call things like this "a functor from a diagram category $J$ over the set $I$ into the category of groups". A bunch of relationships that don't automatically contradict each other.

Now, if we didn't require "enclose but not squish", it is some general category theory nonsense (or just a way more complicated definition of "simplified formal product") that a universal minimal enclosing-but-possibly-squishing group exists. However, there may not exist any (universal or not) minimal enclosing-but-not-squishing group.

Summary: I think I've covered the major existence theorems (except for a parabolic system result I don't have at hand). They were if $J$ is empty, then we get the free product. If $J=\{(i,n) : i \in I \}$ then we get $G_n$. If $J=\{(0,i) : i \in I \}$ then we get the free group with amalgamation. Otherwise (being neither directed, nor the reversed $J$ being directed), I think there are choices of $G_i$ and $f_{i,j}$ that are compatible but such that there is no minimal enclosing-but-not-squishing group.

-
Thank you very much for this detailed answer. It's definitely a +1; I'm currently considering whether I also should move the accepted check to it. On one hand, it's immensely more useful than the other answer (I'll need some time to fully understand it; however from first reading I think the free product with amalgamation matches closest what I had in mind), on the other hand, the other answer answers exactly the question I've asked, so I feel it would be a bit unfair to remove the acceptance. – celtschk Jul 19 '12 at 21:28
@celtschk: leave the check is fine with the first answer. Direct answers should have the check, and short answers should probably be above essays. – Jack Schmidt Jul 19 '12 at 21:36
@celtschk Let me just say that I would have no problem with ceding the accepted answer to this wonderfully informative piece. – Miha Habič Jul 20 '12 at 7:10