# complexity of counting homomorphisms

This is a question I have thought about and asked a number of people, but have never got an answer beyond "It should be true that..."

Given a finitely generated group $G$ (eg. a link group $G_L:=\pi_1(S^3-L)$ for a link $L$) and a finite group $H$ we want to count homomorphisms from $G$ to $H$. For link groups as above, this is an invariant of $L$.

My question: (for which $H$) is there a polynomial-time algorithm (in the number of generators and relations for $G$) for computing $N(G,H):=|Hom(G,H)|$ (particularly for $G_L$)?

Some things I know: 1) If $L$ is a knot and $H$ is nilpotent then $N(G_L,H)$ is constant (M. Eisermann) 2) D. Matei; A. I. Suciu, have an algorithm for solvable $H$, but the complexity is not clear. 3) The abelianization of $G_L$ is just $Z^c$, $c$ the number of components, so for $H$ abelian it is easy.

A wild conjecture is that it should always be "FPRASable" i.e. there exists a fully polynomial randomized approximation scheme for the computation.

• I guess you want polynomial time with respect of the logarithm of $\sharp(H)$? (The answer is trivially yes otherwise.) May 31 '10 at 16:20
• Sorry, the answer is yes for finitely presented groups. May 31 '10 at 16:21
• edited to clarify. May 31 '10 at 16:44
• You can embellish this by using the peripheral structure. That is, a knot group comes with a pair of commuting elements (up to conjugacy). Then choose a pair of commuting elements in $G$ and count homomorphisms sending the first pair to the second pair. My naive guess is that your questions will have similar answers in this context? Jun 2 '10 at 6:59
• I like this idea Bruce. I have wondered how one might randomize the obvious (exponential) algorithm that tests all $n$-tuples from $H$ against the defining relations of $G_L$. Maybe something like this would work. Jun 2 '10 at 12:55

For $G$ a knot group, and for $H$ a dihedral group, there should be a simple algorithm for counting the number of homomorphisms. The meridians of $G$ normally generate, and are all conjugate, so they must be sent to conjugate elements in $H$. If they are sent to the cyclic subgroup of index 2, then the image is cyclic, and this is easy to count.
If a meridian is sent to an involution, then an index 2 subgroup of $G$ is sent to a cyclic group. This amounts to computing the homology of the 2-fold branched cover of the knot, together with the action of the involution on this homology. This is certainly polynomial-time computable, and I'm pretty sure one can determine its dihedral quotients easily. In any case, at least this reduces it to the problem of finding dihedral quotients of abelian-by-$\mathbb{Z}/2$ groups.
• Thanks Ian! This makes sense algebraically: the braid group image associated with the Drinfeld center of a (generalized) Dihedral group is an integer specialization of the Burau representation, reduced modulo some $m$. The link invariant associated with this (modular) Hopf algebra is some version of counting homomorphisms. So maybe the statement you make can be generalized to semidirect products of cyclic groups? I think I read somewhere that the Alexander polynomial can be used to compute the homology of Seifert surfaces... Jun 1 '10 at 18:09