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.

  • $\begingroup$ I guess you want polynomial time with respect of the logarithm of $\sharp(H)$? (The answer is trivially yes otherwise.) $\endgroup$ May 31 '10 at 16:20
  • $\begingroup$ Sorry, the answer is yes for finitely presented groups. $\endgroup$ May 31 '10 at 16:21
  • $\begingroup$ edited to clarify. $\endgroup$ May 31 '10 at 16:44
  • 1
    $\begingroup$ 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? $\endgroup$ Jun 2 '10 at 6:59
  • $\begingroup$ 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. $\endgroup$ 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.

  • $\begingroup$ 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... $\endgroup$ Jun 1 '10 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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