# If $\lvert\operatorname{Hom}(H,G_1)\rvert = \lvert\operatorname{Hom}(H,G_2)\rvert$ for any $H$ then $G_1 \cong G_2$

Let $G_1$ and $G_2$ be two finite groups such that for any finite group $H$, $\lvert\operatorname{Hom}(H,G_1)\rvert = \lvert\operatorname{Hom}(H,G_2)\rvert$. How can I show that $G_1 \cong G_2$ ?

-
Prove the contrapositive, I suppose. If $G_1 \not\cong G_2$ then there exists a finite group $H$ (cleverly chosen by you) such that $|\operatorname{Hom}(H,G_1)| \not= |\operatorname{Hom}(H,G_2)|$. This looks like a fun version of the Yoneda lemma (we can't apply that here; for that we'd need $\operatorname{Hom}(H,G_1) \cong \operatorname{Hom}(H,G_2)$). –  Gunnar Þór Magnússon Dec 21 '13 at 2:18
@GunnarMagnusson Thanks. But Your idea is equivalent to my question. –  user41304 Dec 21 '13 at 2:21
Would it be much of a comment on your question if it wasn't? More to the point, since you didn't talk about the work you'd already done on the question I couldn't see if you'd already eliminated basic things like proving the contrapositive, or had compared the Yoneda lemma with your question and seen if its proof had a hint that could work for you. You get out of this site what you put into it. –  Gunnar Þór Magnússon Dec 21 '13 at 2:31
@GunnarMagnusson This really does not look like homework, so while I agree that the OP would get more interest had he mentioned where the question came from (OP: comments?) I don't think giving a report on partial results would be especially useful. –  Igor Rivin Dec 21 '13 at 3:09
Is this known to be true ? Because this result seems quite surprising to me. –  Jeremy Daniel Dec 21 '13 at 11:18

Hint: Using the in-and-out principle (aka "inclusion and exclusion"), you can compute the number of injective homomorphisms from a finite group $H$ to a finite group $G$ from the values of $\lvert\operatorname{Hom}(H/N,G)\rvert$ for every normal subgroup $N$ of $H$. Therefore, from your assumption that $\lvert\operatorname{Hom}(H,G_1)\rvert=\lvert\operatorname{Hom}(H,G_2)\rvert$ for every finite group $H$, it follows that every finite $H$ has the same number of injective homomorphisms to $G_1$ as to $G_2$, and in particular, that there is at least one injective homomorphism from $G_1$ to $G_2$ and vice versa, whence it easily follows that $G_1\cong G_2$. This argument applies to lots of other finite structures besides groups. I believe that it's due to László Lovász and that he discovered it as a high school student.

P.S. This has come up several times on Math Stack Exchange and Math Overflow, for example in this answer, which cites L. Lovász, Operations with structures, Acta Math. Acad. Sci. Hungar. 18 (1967) 321-328.

P.P.S. I will try to present the argument using the in-and-out principle. (I still think this argument must be due to Lovász, even it it's not the one he gives in the work cited above. Unless the argument is wrong, in which case it must be due to me.)

Let $H$ and $G$ be finite groups. Let $H\setminus\{1_H\}=\{h_1,\dots,h_n\}$.

For $i\in[n]=\{1,\dots,n\}$, let $S_i=\{\varphi\in\text{Hom}(H,G):\varphi(h_i)=1_G\}$.

For $I\subseteq[n]$, let $S_I=\bigcap_{i\in I}S_i=\{\varphi\in\text{Hom}(H,G):\forall i\in I\ \varphi(h_i)=1_G\}$ if $I\ne\emptyset$, and $S_\emptyset=\text{Hom}(H,G)$.

Then $|S_I|=|\text{Hom}(H/N_I,G)|$ where $N_I$ is the normal subgroup of $H$ generated by $\{h_i:i\in I\}$. By the in-and-out principle,$$|\text{Mono}(H,G)|=|\text{Hom}(H,G)\setminus\bigcup_{i\in[n]}S_i|=\sum_{I\subseteq[n]}(-1)^{|I|}|S_I|=\sum_{I\subseteq[n]}(-1)^{|I|}|\text{Hom}(H/N_I,G)|.$$Therefore, if $H,G_1,G_2$ are finite groups, and if $|\text{Hom}(H/N,G_1)|=|\text{Hom}(H/N,G_2)|$ for every normal subgroup $N$ of $H$, then $|\text{Mono}(H,G_1)|=|\text{Mono}(H,G_2)|$.

P.P.P.S. This is not true for infinite groups. If $G_1$ and $G_2$ are nonisomorphic groups such that each is isomorphic to a subgroup of the other, then $|\text{Hom}(H,G_1)|=|\text{Hom}(H,G_2)|$ for every (finite or infinite) group $H$, although $G_1\not\cong G_2$.

-

As mentioned in bof's answer this result is due to L. Lovász, Operations with structures. The argument is given on pages 326-327. But it doesn't use inclusion-exclusion, but rather what I could call a fibration argument. Let me present the proof in my own words.

Let us denote by $\mathrm{Hom}(-,-)$, $\mathrm{Epi}(-,-)$, $\mathrm{Mono}(-,-)$ the sets of homomorphisms, epimorphisms and monomorphisms. Up to isomorphism there is only a countable set of finite groups, say $\{G_1,G_2,G_3,\dotsc\}$ with $G_i \not\cong G_j$ for $i \neq j$.

Claim 1. If $G,H$ are finite groups, then $$|\mathrm{Hom}(H,G)| = \sum_i \frac{|\mathrm{Epi}(H,G_i)|}{|\mathrm{Aut}(G_i)|} \cdot |\mathrm{Mono}(G_i,G)|.$$ Notice that this sum is essentially finite.

Proof. Let $\mathrm{Hom}_i(H,G) \subseteq \mathrm{Hom}(H,G)$ be the set of all homomorphisms whose image is isomorphic to $G_i$. Then $\mathrm{Hom}(H,G) = \sqcup_i \mathrm{Hom}_i(H,G)$, so that it suffices to prove that $$|\mathrm{Hom}_i(H,G)| = \frac{|\mathrm{Epi}(H,G_i)|}{|\mathrm{Aut}(G_i)|} \cdot |\mathrm{Mono}(G_i,G)|.$$ Consider the composition map $\mathrm{Epi}(H,G_i) \times \mathrm{Mono}(G_i,G) \to \mathrm{Hom}_i(H,G)$. It is surjective, and in fact a torsor under the obvious action from $\mathrm{Aut}(G_i)$ (since image factorizations are essentially unique). The claim follows. $\square$

Let $G,G'$ be two finite groups such that $|\mathrm{Hom}(H,G)|=|\mathrm{Hom}(H,G')|$ for all finite groups $H$.

Claim 2. We have $|\mathrm{Mono}(H,G)| = |\mathrm{Mono}(H,G')|$ for all finite groups $H$.

From this it will follow immediately that there is a monomorphism $G \to G'$ and a monomorphism $G' \to G$. In particular $|G|=|G'|$ and therefore these monomorphisms are already isomorphisms $G \cong G'$.

Proof. By induction on $|H|$. We can decompose $\mathrm{Hom}(H,G)$ into the monomorphisms and the homomorphisms whose image is some $G_i$ with $|G_i| < |H|$. Hence, the first claim gives $$|\mathrm{Hom}(H,G)| = |\mathrm{Mono}(H,G)| + \sum\limits_{ i,~ |G_i|< |H|} \frac{|\mathrm{Epi}(H,G_i)|}{|\mathrm{Aut}(G_i)|} \cdot |\mathrm{Mono}(G_i,G)|$$ Since $|\mathrm{Hom}(H,G)|=|\mathrm{Hom}(H,G')|$ and $|\mathrm{Mono}(G_i,G)|=|\mathrm{Mono}(G_i,G')|$ by induction, it follows $|\mathrm{Mono}(H,G)| = |\mathrm{Mono}(H,G')|$.

Category-theoretic generalization. Instead of the category of finite groups $\mathsf{FinGrp}$, we can work with any category $\mathcal{C}$ with the following properties:

• For every $G,H \in \mathcal{C}$ the set $\mathrm{Hom}(G,H)$ is finite.
• Every $G \in \mathcal{C}$ has only finitely many subobjects.
• Every object $G \in \mathcal{C}$ has a size $|G| \in \mathbb{N}$ such that for every proper subobject $H < G$ we have $|H| < |G|$, likewise for proper quotients.
• Every morphism in $\mathcal{C}$ factors essentially unique as an epimorphism followed by a monomorphism.

Notice that any category of finite algebraic structures of a given type has these properties (this case was also considered by L. Lovász). The same proof as above shows: If $G,G' \in \mathcal{C}$ satisfy $|\mathrm{Hom}(H,G)|=|\mathrm{Hom}(H,G')|$ for all $H \in \mathcal{C}$, then $G \cong G'$.

-

This is not a complete answer, but it is too long for a comment and it may become a complete answer when we work together ...

I have the following ideas how to attack this problem.

• Two finite groups which are elementary equivalent are already isomorphic (this holds for arbitrary finite structures in the sense of model theory).
• In order to show that $G_1$ and $G_2$ are elementary equivalent, encode the fulfillment of a formula $\phi$ in a finite group $G$ in terms of the cardinality of $\hom(H,G)$ for a suitably chosen $H$.
• More generally, encode group-theoretic properties and invariants of a finite group $G$ in terms of these cardinalities $h(H) := |\hom(H,G)|$.

Here is what I've got so far:

1. A group presentation of $H$ gives a description of $h(H)$. For example, if $n \geq 1$, then $h(C_n)$ is the number of $x \in G$ with $x^n=1$, and $h(D_n)$ is the number of pairs $x,y \in G$ such that $x^n=y^2=(xy)^2=1$.
2. The order of $G$ is $|G|=\limsup_{n \to \infty} h(C_n)$.
3. The exponent of $G$ is the smallest $n \geq 1$ such that $h(C_n)=|G|$.
4. The "commutativity probability" of $G$ is $h(C_{|G|} \times C_{|G|}) = |\{(x,y) \in G : xy=yx\}|$ divided by $|G|^2$.
5. $G$ is abelian if and only if its commutativity probability is $=1$.
6. More generally, assume that $n=|G|$ and $\omega=\omega(x_1,\dotsc,x_m)$ is a group word such that $H:=\langle x_1,\dotsc,x_m : x_1^n=\dotsc=x_m^n=1, \omega(x_1,\dotsc,x_m)=1\rangle$ is finite (for example when the Burnside group $B(m,n)$ is finite). Then $\omega$ vanishes on all elements of $G^m$ if and only if $h(H)=|G|^m$.

Further remarks:

1. If there is a monomorphism $G_1 \to G_2$, then it must be an isomorphism $G_1 \cong G_2$. The reason is that the induced map $\hom(H,G_1) \to \hom(H,G_2)$ is an injective map between finite sets of the same cardinality, hence a bijection, so that we may apply Yoneda's Lemma.

2. If $G_1$ and hence $G_2$ is abelian, then $G_1 \cong G_2$: We may assume that $G_1$ and $G_2$ are finite abelian $p$-groups for a prime $p$, say isomorphic to $\oplus_i \mathbb{Z}/p^{a_i}$ resp. $\oplus_i \mathbb{Z}/p^{b_i}$ for increasing sequences $a_1 \leq \dotsc \leq a_n$ and $b_1 \leq \dotsc \leq b_m$. Applying 1. to $n=p^c$, we get $\prod_i \min(c,a_i) = \prod_i \min(c,b_i)$. We also know $\prod_i a_i = \prod_i b_i$ from 2. For $c=a_n$ we get $\prod_i b_i = \prod_i a_i = \prod_i \min(a_n,b_i) \leq \prod_i b_i$, hence $\min(a_n,b_i)=b_i$ for all $i$, in particular $b_m \leq a_n$. By symmetry, we also have $a_n \leq b_m$, hence $a_n=b_m$. But then we may cancel both and apply induction.

3. If $G_1,G_2$ are nontrivial, then there is a nontrivial homomorphism $G_1 \to G_2$ since $|\hom(G_1,G_2)| = |\hom(G_1,G_1)| \geq 2$. Similarly, there is a nontrivial homomorphism $G_2 \to G_1$. This is a quite useless observation, but it shows that one might also take $H$ to be some group constructed from $G_1$ or $G_2$.

-
PS: It is not clear to me if we can really prove $G_1 \cong G_2$. But I suspect that counterexamples will be rather ugly. –  Martin Brandenburg Dec 22 '13 at 2:29
The "opposite" of #2 also holds: If $G_1$ is simple, then so is $G_2$ and $G_1 \cong G_2$. This follows immediately from Further Remarks #1 since $h(G_1, G_2) = h(G_1, G_1) > 1$ (since conjugation must be nontrivial). –  RghtHndSd Dec 22 '13 at 4:26