11
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ I guess you want polynomial time with respect of the logarithm of $\sharp(H)$? (The answer is trivially yes otherwise.) $\endgroup$
    – Roland Bacher
    Commented May 31, 2010 at 16:20
  • $\begingroup$ Sorry, the answer is yes for finitely presented groups. $\endgroup$
    – Roland Bacher
    Commented May 31, 2010 at 16:21
  • $\begingroup$ edited to clarify. $\endgroup$
    – Eric Rowell
    Commented May 31, 2010 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$
    – Bruce Westbury
    Commented Jun 2, 2010 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$
    – Eric Rowell
    Commented Jun 2, 2010 at 12:55

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\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$
    – Eric Rowell
    Commented Jun 1, 2010 at 18:09

You must log in to answer this question.

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