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

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$.