MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
I guess you want polynomial time with respect of the logarithm of $\sharp(H)$? (The answer is trivially yes otherwise.) – Roland Bacher May 31 '10 at 16:20
Sorry, the answer is yes for finitely presented groups. – Roland Bacher May 31 '10 at 16:21
edited to clarify. – Eric Rowell 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? – Bruce Westbury 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. – Eric Rowell Jun 2 '10 at 12:55
up vote 3 down vote accepted

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.

share|cite|improve this answer
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... – Eric Rowell Jun 1 '10 at 18:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.