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

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

2011-05-07T16:32:48Z

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?

Answer by Daniel Litt for Computability and complexity of computing $|Hom(G,H)|$ for finitely presented groups G, H.

2011-05-07T17:31:04Z

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.

Answer by Eric Rowell for Computability and complexity of computing $|Hom(G,H)|$ for finitely presented groups G, H.

2011-05-07T17:44:47Z

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.

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

2011-05-09T11:39:19Z

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.