# Computability and complexity of computing $|Hom(G,H)|$ for finitely presented groups G, H.

In the general case, I want to say that determining $|Hom(G,H)|$ is incomputable, arguing that you could use the number to test for simplicity of a presentation, but I am new to this area and I keep finding flaws with my argument.

While I believe the general case is incomputable, there are computable special cases. One in particular that interests me is: compute $|Hom(\pi(S),G)|$ for the fundamental group of a surface $S$, given by a triangulation, and $G$ finite. This arises in Mednykh’s Formula for a 2D TLFT invariant ( $|G|^{\chi(S)-1}|Hom(\pi(S),G)|$), which one can approximate (details in a paper to appear by Gorjan Alagic and myself) efficiently on a quantum computer. However, I have been unable to find any information on the classical complexity of finding $|Hom(\pi(S),G)|$ (with $\pi(S),G$ given in any way) to contrast with the quantum case, or even a discussion of when $|Hom(G,H)|$ is computable and what the complexity of computing it should be.

So, that leaves me with the possibly too broad:

When is $|Hom(G,H)|$ computable for finitely presented $G,H$ and in these special cases what is the classical complexity of computing it?

• It is probably not helpful to be given $H$ as a finitely presented group. Even if $H$ is known to be finite, to make any computations in $H$ you would first need to run something like Todd-Coxeter coset enumeration, which has unknown complexity. To even start attempting any meaningful complexity analysis, you would do better to assume for example that $H$ is given as a finite group of permutations. Another situation where you could compute $|{\rm Hom}(G,H)|$ would be $H$ abelian, but again you should assume that $H$ is given as a direct product of cyclic groups. May 7, 2011 at 17:01

Take $G=\mathbb{Z}$. Then computing $|\operatorname{Hom}(G, H)|=|H|$ is the same as computing the size of a finitely presented group, and is thus wildly undecidable. This eliminates both the general case you seem to ask about, and the case of fundamental groups of surfaces (replacing $\mathbb{Z}$ with, say $\mathbb{Z}\oplus \mathbb{Z}$ and letting your surface $S$ be a torus).

In other words, this problem seems essentially intractable as you've asked it. On the other hand, if you restrict $H$ to lie in the class of finite groups, then the complexity is bounded above by $$|H|^{|\text{\# of generators of } G|}\cdot \sum_r t_H(|r|)$$ where the sum is taken over the relations of the given presentation of $G$, and where $t_H(|r|)$ is the time complexity of deciding the word problem in $H$ for a word of length $|r|$. To see this, consider the algorithm which considers all maps $$\{\text{generators of G}\to H\}$$ of which there are $$|H|^{|\text{\# of generators of } G|},$$ and for each map, checks whether the relations of $G$ are satisfied in $H$. This algorithm has the time complexity described.

So essentially your question is identical to finding the time complexity of solving the word problem in whatever class of groups $H$ belongs to, about which there is tons of literature.

• Thank you for the pointers. In the case where H is finite this is exponential in the number of generators of $G$, so in the particular case I mentioned above, the genus of the surface $S$ (if one uses the standard presentation for $pi(S)$). Is this the best that can be done classically? In the case where H is solvable the Matei algorithm Eric mentions gives another approach using group cohomology but the complexity isn't clear. May 8, 2011 at 2:23
• I see no reason why this (extremely naive) algorithm should be optimal, nor a reason to believe it isn't; I'm by no means an expert on this stuff. On the other hand the fundamental groups of surfaces are of a particularly simple form, so it's reasonable to guess there might be a better algorithm. But counting in general is quite computationally difficult--I suspect this problem is not even in $\#P$. May 8, 2011 at 5:59
• I don't believe there is any known algorithm that is not exponential in the number of generators of $H$, but there are ways of making it run faster in practice. The most obvious one is that the image in $H$ of the first generator of $G$ can be restricted to a set of conjugacy class representatives in $H$. You can also make use of the structure of the relators of $G$ to prune the search tree. If some of them only involve a subset of the generators (for example some of them might be powers of single generators), then you can make use of that. Implementations are available in GAP and Magma. May 8, 2011 at 10:41

This answer is really just intended to add some keywords to the discussion.

If $G=\langle x_1,\ldots,x_m\mid r_1,\ldots,r_n\rangle$ then the set $\mathrm{Hom}(G,H)$ is naturally in bijection with the set of solutions to the system of equations

$r_1(x_1,\ldots,x_m)=1$

$\ldots$

$r_n(x_1,\ldots,x_m)=1$

in $H$.

For this reason, the study of $\mathrm{Hom}(G,H)$ is sometimes called 'algebraic (or Diophantine) geometry over $H$'. See the masses of recent literature on the Tarski Problem and related matters, with the key works by Sela and Kharlampovich--Miasnikov, for the case in which $H$ is free. In this case, $\mathrm{Hom}(G,H)$ is infinite if and only if it's non-trivial, which one can determine using Makanin's Algorithm.

I asked a similar question a while back. In case H is solvable there is an algorithm (see http://arxiv.org/abs/math/0405122) but the complexity is not clear. If H is nipotent and S is a knot complement then M. Eisermann has shown that the $|Hom(\pi(S),H)|$ is constant (see http://www-fourier.ujf-grenoble.fr/~eiserm/Publications/twistseq.pdf). Agol has pointed out that is should be polynomial if H is dihedral in his answer to my question linked above.