Narrow Results

We prove that the Brinkmann Problems (BrP & BrCP) and the Twisted-Conjugacy Problem (TCP) are decidable for any endomorphism of a free-abelian times free (FATF) group ${𝔽}_n\times {\mathbb{Z}}^m$. Furthermore, we prove the decidability of the two-sided Brinkmann Conjugacy Problem (2BrCP) for monomorphisms of FATF groups (and combine it with TCP) to derive the decidability of the conjugacy problem for ascending HNN extensions of FATF groups.

We describe an algorithm due to Eric Swenson for testing quasi-convex subgroups of hyperbolic groups for near malnormality. We go on to discuss some strategies for the practical implementation of this algorithm and consider an example. We then show that the methods of Swenson's algorithm extend to give practical solutions to the conjugacy problem for infinite order elements, and to the normalizer and centralizer problems for subgroups satisfying appropriate conditions. The results are presented here in outline — all the algorithms are described in more detail in the author's PhD thesis (University of Warwick, 2001).

We study, from a constructive computational point of view, the techniques used to solve the conjugacy problem in the "generic" lattice-ordered group Aut(ℝ). We use these techniques in order to show that for all f, g ∈ Aut(ℝ), the equation xfx = g is effectively solvable in Aut(ℝ).

We prove that every countable group with solvable power problem embeds into a finitely presented 2-generated group with solvable power and conjugacy problems.

The main result proved in this paper is that the conjugacy problem in word-hyperbolic groups is solvable in linear time. This is using a standard RAM model of computation, in which basic arithmetical operations on integers are assumed to take place in constant time. The constants involved in the linear time solution are all computable explicitly.

We also give a proof of the result of Mike Shapiro that in a word-hyperbolic group a word in the generators can be transformed into short-lex normal form in linear time. This is used in the proof of our main theorem, but is a significant theoretical result of independent interest, which deserves to be in the literature. Previously the best known result was a quadratic estimate.

We discuss the time complexity of the word and conjugacy search problems for free products G = A ⋆_C B of groups A and B with amalgamation over a subgroup C. We stratify the set of elements of G with respect to the complexity of the word and conjugacy problems and show that for the generic stratum the conjugacy search problem is decidable under some reasonable assumptions about groups A, B, C.

We investigate the use of random algorithms for the solution of the conjugacy problems for certain types of Artin groups of finite type including the braid groups.

The conjugacy problem and the inverse conjugacy problem of a finitely generated group are defined, from a language theoretic point of view, as sets of pairs of words. An automaton might be obliged to read the two input words synchronously, or could have the option to read asynchronously. Hence each class of languages gives rise to four classes of groups; groups whose (inverse) conjugacy problem is an (a)synchronous language in the given class. For regular languages all these classes are identical with the class of finite groups. We show that the finitely generated groups with asynchronously context-free inverse conjugacy problem are precisely the virtually free groups. Moreover, the other three classes arising from context-free languages are shown all to coincide with the class of virtually cyclic groups, which is precisely the class of groups with synchronously one-counter (inverse) conjugacy problem. It is also proved that, for a δ-hyperbolic group and any λ ≥ 1, ϵ ≥ 0, the intersection of the inverse conjugacy problem with the set of pairs of (λ, ϵ)-quasigeodesics is context-free. Finally we show that the conjugacy problem of a virtually free group is an asynchronously indexed language.

Let G be a word-hyperbolic group with given finite generating set, for which various standard structures and constants have been pre-computed. An (non-practical) algorithm is described that, given as input two lists A and B, each composed of m words in the generators and their inverses, determines whether or not the lists are conjugate in G, and returns a conjugating element, should one exist. The algorithm runs in time O(mμ), where μ is an upper bound on the length of elements in the two lists. Similarly, an algorithm is outlined that computes generators of the centralizer of A, with the same bound on running time.

In this paper, we study the conjugacy problem in polycyclic groups. Our main result is that we construct polycyclic groups G_n whose conjugacy problem is at least as hard as the subset sum problem with n indeterminates. As such, the uniform conjugacy problem over the groups G_n is NP-complete where the parameters of the problem are taken in terms of n and the length of the elements given on input.

If u and v are two conjugate elements of a hyperbolic group then the length of a shortest conjugating element for u and v can be bounded by a linear function of the sum of their lengths, as was proved by Lysenok in [Some algorithmic properties of hyperbolic groups, Izv. Akad. Nauk SSSR Ser. Mat.53(4) (1989) 814–832, 912]. Bridson and Haefliger showed in [Metrics Spaces of Non-Positive Curvature (Springer-Verlag, Berlin, 1999)] that in a hyperbolic group the conjugacy problem can be solved in polynomial time. We extend these results to relatively hyperbolic groups. In particular, we show that both the conjugacy problem and the conjugacy search problem can be solved in polynomial time in a relatively hyperbolic group, whenever the corresponding problem can be solved in polynomial time in each parabolic subgroup. We also prove that if u and v are two conjugate hyperbolic elements of a relatively hyperbolic group then the length of a shortest conjugating element for u and v is linear in terms of their lengths.

An introduction to the universal algebra approach to Higman–Thompson groups (including Thompson’s group $V$) is given, following a series of lectures by Graham Higman in 1973. In these talks, Higman outlined an algorithm for the conjugacy problem; which although essentially correct fails in certain cases, as we show here. A revised and complete version of the algorithm is written out explicitly. From this, we construct an algorithm for the power conjugacy problem in these groups. Python implementations of these algorithms can be found in [26].

Higman’s group $H=〈a,b,c,d|b^a=b^2,c^b=c^2,d^c=d^2,a^d=a^2〉$ is a remarkable group with large (non-elementary) Dehn function. Higman constructed the group in 1951 to produce the first examples of infinite simple groups. Using finite state automata, and studying fixed points of certain finite state transducers, we show the conjugacy problem in $H$ is decidable for all inputs. Diekert, Laun and Ushakov have recently shown the word problem in $H$ is solvable in polynomial time, using the power circuit technology of Myasnikov, Ushakov and Won. Building on this work, we also show in a strongly generic setting that the conjugacy problem for $H$ has a polynomial time solution.

We prove that the conjugacy problem in the first Grigorchuk group $\mathrm{\Gamma }$ can be solved in linear time. Furthermore, the problem to decide if a list of elements $w_1,\dots ,w_k\in \mathrm{\Gamma }$ contains a pair of conjugate elements can be solved in linear time. We also show that a conjugator for a pair of conjugate element $u,v\in \mathrm{\Gamma }$ can be found in polynomial time.

In 1971 C. F. Miller associated to every finitely presented group G a free-by-free group $M(G)$ known as the Miller Machine, whose conjugacy problem is closely related to the conjugacy and word problems of G. We quantify this relationship, and look to fully understand the conjugacy problem of $M(G)$; namely, we reduce the conjugacy problem in $M(G)$ to a strong form of list conjugacy in G, which we term iso-computational list conjugacy. As an application, we show that if G is finite, the conjugacy problem for $M(G)$ is in $PSPACE$.

In the symmetric group S_n, we introduced the notion of crossing and linking numbers to each permutation. Then a unique factorization of a permutation is given due to its crossing number of its factors and how the factors are linked. Consequently we introduced a matrix associated to each permutation, which we used it as a tool to prove that positive braids with different matrices are not conjugate braids. Up to n≤5 it is proved that two positive permutation braids are conjugate if and only if they have the same matrix, and a complete calculation of these matrices with the associated link type is given.

We show that the Wirtinger presentation of a prime alternating link group satisfies a generalized small cancellation condition. This new version of Weinbaum's solution to the word and conjugacy problems for these groups easily extends to finite sums of alternating links.

We show that there is a family of pseudo-Anosov braids independently parametrized by the braid index and the (canonical) length whose smallest conjugacy invariant sets grow exponentially in the braid index and linearly in the length.

The problem of finding the genus of a given link type of braid index 3 is solved by constructive methods. The results depend upon a new solution to the conjugacy problem in B₃. In this solution, conjugacy classes are represented by shortest words in terms of cyclically symmetric elementary braids which are used as generators in the new presentation of B₃. By related results of Bennequin [2] and of Birman and Menasco [4], the minimal spanning surfaces are described by these shortest words. An effective algorithm is given to find these shortest words starting with an arbitrary 3-braid representative of the link. It is proved that up to an easily described family of exceptional cases, a link of braid index 3 has a unique isotopy class of minimal spanning surfaces. The growth functions of B₃ and its conjugacy classes are also given here.

Let E and F be Banach spaces and f non-linear C¹ map from E into F. The main result is Theorem 2.2, in which a connection between local conjugacy problem of f at x₀∈ E and a local fine property of f′(x) at x₀ (see the Definition 1.1 in this paper) are obtained. This theorem includes as special cases the two known theorems: the finite rank theorem and Berger's Theorem for non-linear Fredholm operators. Moreover, the theorem gives rise the further results for some non-linear semi-Fredholm maps and for all non-linear semi-Fredholm maps when E and F are Hilbert spaces. Thus Theorem 2.2 not only just unifies the above known theorems but also really generalizes them.