Mathematics – Algebraic Topology
Scientific paper
2008-06-28
Journal of Pure and Applied Algebra, 215, 2011, p. 1702-1710
Mathematics
Algebraic Topology
Totally reworked: bogus section removed, much new material added
Scientific paper
10.1016/j.jpaa.2010.10.005
We give two results for computing doubly-twisted conjugacy relations in free groups with respect to homomorphisms $\phi$ and $\psi$ such that certain remnant words from $\phi$ are longer than the images of generators under $\psi$. Our first result is a remnant inequality condition which implies that two words $u$ and $v$ are not doubly-twisted conjugate. Further we show that if $\psi$ is given and $\phi$, $u$, and $v$ are chosen at random, then the probability that $u$ and $v$ are not doubly-twisted conjugate is 1. In the particular case of singly-twisted conjugacy, this means that if $\phi$, $u$, and $v$ are chosen at random, then $u$ and $v$ are not in the same singly-twisted conjugacy class with probability 1. Our second result generalizes Kim's "bounded solution length". We give an algorithm for deciding doubly-twisted conjugacy relations in the case where $\phi$ and $\psi$ satisfy a similar remnant inequality. In the particular case of singly-twisted conjugacy, our algorithm suffices to decide any twisted conjugacy relation if $\phi$ has remnant words of length at least 2. As a consequence of our generic properties we give an elementary proof of a recent result of Martino, Turner, and Ventura, that computes the densities of injective and surjective homomorphisms from one free group to another. We further compute the expected value of the density of the image of a homomorphism.
No associations
LandOfFree
Remnant inequalities and doubly-twisted conjugacy in free groups does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Remnant inequalities and doubly-twisted conjugacy in free groups, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Remnant inequalities and doubly-twisted conjugacy in free groups will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-624861