5
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Derek Holt
    Commented May 7, 2011 at 17:01

3 Answers 3

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Edgar A. Bering IV
    Commented May 8, 2011 at 2:23
  • $\begingroup$ 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$. $\endgroup$
    – Daniel Litt
    Commented May 8, 2011 at 5:59
  • $\begingroup$ 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. $\endgroup$
    – Derek Holt
    Commented May 8, 2011 at 10:41
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .