Search

International audience; The present volume consists of a collection of essays dedicated to Vladimir Turaev. The essays cover the large spectrum of topics in which Turaev has been interested, including knot and link invariants, quantum representations, TQFTs, state sum constructions, geometric structures on knot complements, Kleinian groups, geometric group theory and its relationship with 3-manifolds, mapping class groups, operads, mathematical physics, Grothendieck’s program, the philosophy of mathematics, and several other topics. At the same time, this volume will give an overview of topics that are at the forefront of current research in topology and geometry. Some of the essays are research articles and contain new results, sometimes answering questions that were raised by Turaev. The rest of the essays are surveys that will introduce the reader to some key ideas in the field. The authors of the essays are: Athanase Papadopoulos, Jean-Claude Hausmann, Charles Livingston, Norbert A’Campo, Julia Viro and Oleg Viro, Louis H. Kauffman, Julien Marché, Rinat Kashaev, Jun Murakami, Anna Beliakova and Kazuhiro Hikami, Christian Blanchet and Marco De Renzi, Louis-Hadrien Robert and Emmanuel Wagner, Sergey M. Natanzon, Stavros Garoufalidis and Rinat Kashaev, Louis Funar, Toshitake Kohno, Nariya Kawazumi, Yusuke Kuno, Gwénaël Massuyeau and Shunsuke Tsuji, Valentin Poénaru, Nikolay Abrosimov and Alexander Mednykh, Charalampos Charitos, Ken’ichi Ohshika, Gourab Bhattacharya and Maxim Kontsevich, Noémie C. Combe, Yuri I. Manin and Matilde Marcolli, A. Muhammed Uludag, Sumio Yamada, Vassiliki Farmaki and Stelios Negrepontis, Arkady Plotnitsky.

Residual finiteness is known to be an important property of groups appearing in combinatorial group theory and low dimensional topology. In a recent work [2] residual finiteness of quandles was introduced, and it was proved that free quandles and knot quandles are residually finite. In this paper, we extend these results and prove that free products of residually finite quandles are residually finite provided their associated groups are residually finite. As associated groups of link quandles are link groups, which are known to be residually finite, it follows that link quandles are residually finite., Comment: 11 pages, final version, to appear in Monatshefte f\"ur Mathematik

WOS:000451335800010 In Panaite [Iterated crossed products, J. Algebra Appl. 13(7), 14580036 (2014)], Panaite studied iterated crossed product construction from the point of algebraic structures. In this paper, we study iterated crossed product from the point of Combinatorial Group Theory and define a new version of the crossed product of groups. First, we give some conditions for this new product to be a group, then we obtain a presentation for iterated crossed product of cyclic groups. Additionally, using this presentation, we find a complete rewriting system and thus we obtain normal form structure of elements of this new group construction. This gives us the solvability of the word problem for this product. Scientific Research Fund of Karamanoglu Mehmetbey UniversityKaramanoglu Mehmetbey University [17-M-16] The authors would like to thank Professor A. S. Cevik for his enthusiastic encouragement in writing up this paper. This work is supported by the Scientific Research Fund of Karamanoglu Mehmetbey University Project No: 17-M-16.

We use combinatorial group theory methods to extend the definition of a classical James-Hopf invariant to a simplicial group setting. This allow us to realize certain coalgebra idempotents at sSet -level and obtain a functorial decomposition of the spectral sequence, associated with the lower p-central series filtration on the free simplicial group., Comment: 25 pages

In 1986 Umed Karimov constructed a space as a one-point compactification of a CW-complex, where each homotopy class of loops can be represented as an infinite product of commutators. We prove Karimov's conjecture that the first singular homology group of this space is uncountable. The proof uses methods of combinatorial group theory for one-relator groups and methods of geometric topology for smoothing singularities in van-Kampen diagrams corresponding to infinite words.

In Chapter 1 we give basics on combinatorial group theory, starting from free groups and proceeding with the fundamental constructions: free products, amalgamated free products and HNN extensions. We outline a synthesis of Bass-Serre theory, preceded by a survey on Cayley graphs and graphs of groups. After proving the main theorem of Bass-Serre theory, we present its application to the proof of Kurosh subgroup theorem. Subsequently we recall main definitions and properties of hyperbolic spaces. In Section 1.4 we define algebraic and definable closures and recall a few other notions of model theory related to saturation and homogeneity. The last section of Chapter 1 is devoted to asymptotic cones. In Chapter 2 we prove a theorem similar to Bestvina-Paulin theorem on the limit of a sequence of actions on hyperbolic graphs. Our setting is more general: we consider Bowditch-acylindrical actions on arbitrary hyperbolic graphs. We prove that edge stabilizers are (finite bounded)-by-abelian, that tripod stabilizers are finite bounded and that unstable edge stabilizers are finite bounded. In Chapter 3 we introduce the essential notions on limit groups, shortening argument and JSJ decompositions. In Chapter 4 we present the results on constructibility of a torsion-free hyperbolic group from the algebraic closure of a subgroup. Also we discuss constructibility of a free group from the existential algebraic closure of a subgroup. We obtain a bound to the rank of the algebraic and definable closures of subgroups in torsion-free hyperbolic groups. In Section 4.2 we prove some results about the position of algebraic closures in JSJ decompositions of torsion-free hyperbolic groups and other results for free groups. Finally, in Chapter 5 we answer the question about equality between algebraic and definable closure in a free group. A positive answer has been given for a free group F of rank smaller than 3. Instead, for free groups of rank strictly greater than 3 we found some counterexample. For the free group of rank 3 we found a necessary condition on the form of a possible counterexample.

In this paper, we consider an equivalence relation within the class of finitely presented discrete groups attending to their asymptotic topology rather than their asymptotic geometry. More precisely, we say that two finitely presented groups $G$ and $H$ are "proper $2$-equivalent" if there exist (equivalently, for all) finite $2$-dimensional CW-complexes $X$ and $Y$, with $\pi_1(X) \cong G$ and $\pi_1(Y) \cong H$, so that their universal covers $\widetilde{X}$ and $\widetilde{Y}$ are proper $2$-equivalent. It follows that this relation is coarser than the quasi-isometry relation. We point out that finitely presented groups which are $1$-ended and semistable at infinity are classified, up to proper $2$-equivalence, by their fundamental pro-group, and we study the behaviour of this relation with respect to some of the main constructions in combinatorial group theory. A (finer) similar equivalence relation may also be considered for groups of type $F_n, n \geq 3$, which captures more of the large-scale topology of the group. Finally, we pay special attention to the class of those groups $G$ which admit a finite $2$-dimensional CW-complex $X$ with $\pi_1(X) \cong G$ and whose universal cover $\widetilde{X}$ has the proper homotopy type of a $3$-manifold. We show that if such a group $G$ is $1$-ended and semistable at infinity then it is proper $2$-equivalent to either ${\mathbb Z} \times {\mathbb Z} \times {\mathbb Z}$, ${\mathbb Z} \times {\mathbb Z}$ or ${\mathbb F}_2 \times {\mathbb Z}$ (here, ${\mathbb F}_2$ is the free group on two generators). As it turns out, this applies in particular to any group $G$ fitting as the middle term of a short exact sequence of infinite finitely presented groups, thus classifying such group extensions up to proper $2$-equivalence.

The subject matter of the paper encompasses Abelian group theory, module theory, and topology. Hopfian groups appeared in combinatorial group theory, which appreciably determined characteristic features of the initial characterization of Hopfian groups. Methods and problems in combinatorial group theory served as tools for describing Hopfian groups and their connections with other classes of groups. In 1921 J. Nielsen published a paper [1] which improves on the research techniques for finitely generated subgroups of free groups developed in his previous works. Nielsen’s results imply an important consequence which says that a finitely generated free group cannot be isomorphic to its proper factor group; i.e., a homomorphic mapping of such a group onto itself always has a trivial kernel. Now this property, named after Heinz Hopf, is referred to as Hopficity. The reason for this is the following. In [2, 3], Hopf explored mappings of one two-dimensional variety into another. These mappings induce homomorphisms of the fundamental group of the first variety onto the fundamental group of its image. Using topological methods, Hopf showed that the groups mentioned cannot be isomorphic to any of their proper factor groups. The simplest case is one in which the fundamental group in question is free and has finite rank. Surprisingly, over a span of thirty years, nobody noticed that Nielsen had already given a purely algebraically proof of the fact that free groups of finite rank are Hopfian—in fact, ten years before Hopf posed his question. Hopfian groups (including Abelian ones) have been extensively studied by many algebraists (for a bibliography, see [4]). To some extent, the present paper can be regarded as a continuation of [4]. For the reader’s convenience, here we lay out some information concerning the notation and ∗Supported by the Russian Ministry of Education and Science, gov. contract No. 14.B37.21.0354.

We prove that a one-relator group $G$ is K��hler if and only if either $G$ is finite cyclic or $G$ is isomorphic to the fundamental group of a compact orbifold Riemann surface of genus $g > 0$ with at most one cone point of order $n$: $$< a_1\, b_1\, \,...\, a_g\, b_g\, \mid\, (\prod_{i=1}^g [a_i\, b_i])^n>\, .$$, v2: 9pgs. no figs. Final version, to appear in "Geometry and Topology"

First we introduce the history of group theory. Group theory has three main historical sources: number theory, the theory of algebraic equations, and geometry. Secondly, we give the main classes of groups: permutation groups, matrix groups, transformation groups, abstract groups and topological and algebraic groups. Finally, we give two different presentations of a group: combinatorial group theory and geometric group theory.

In a 1959–1975 cycle of papers, P.S. Novikov and S.I. Adian created a new method for studying periodic groups based on the classification of periodic words by means of a complicated simultaneous induction. The method was developed for solving the well-known Burnside problem on periodic groups, but it also enabled the authors to solve a number of other difficult problems of group theory. An extended survey of results contained in the cycle of papers mentioned above and of other significant results obtained after 1975 by Adian and other authors on the basis of the developed theory and its modifications is presented.

Artin presentations are certain group presentations intimately related to pure braids and manifolds of dimensions two, three, and four. This paper studies combinatorial group theoretic properties of Artin presentations as interesting objects in their own right with subtle and pertinent problems.

This is a survey on the automorphism groups in various classes of affine algebraic surfaces and the algebraic group actions on such surfaces. Being infinite-dimensional, these automorphism groups share some important features of algebraic groups. At the same time, they can be studied from the viewpoint of the combinatorial group theory, so we put a special accent on group-theoretical aspects (ind-groups, amalgams, etc.). We provide different approaches to classification, prove certain new results, and attract attention to several open problems., Proposition 2.10 from the previous version (published in Algebraic Varieties and Automorphism Groups, ASPM 75) deleted. There is a mistake in the proof kindly indicated by J.-P. Furter; the validity of the result remains open. This does not affect the rest of the paper

In this paper, we develop a geometric procedure for producing a reverse to Quillen's plus construction, a construction called a 1-sided h-cobordism or semi-h-cobordism. We then use this reverse to the plus construction to produce uncountably many distinct ends of manifolds called pseudo-collars, which are stackings of 1-sided h-cobordisms. Each of our pseudo-collars has the same boundary and pro-homology systems at infinity and similar group-theoretic properties for their pro-fundamental group systems at infinity. In particular, the kernel group of each group extension for each 1-sided h-cobordism in the pseudo-collars is the same group. Nevertheless, the pro-fundamental group systems at infinity are all distinct. A good deal of combinatorial group theory is needed to verify this fact, including an application of Thompson's group V. The notion of pseudo-collars originated in Hilbert cube manfold theory, where it was part of a necessary and suffcient condition for placing a Z-set as the boundary of an open Hilbert cube manifold. We are interested in pseudo-collars on finite-dimensional manifolds for the same reason, attempting to put a Z-set as the boundary of an open high-dimensional manifold., This paper is a submission for publication of my doctoral dissertation arXiv:1502.04338

We discuss a map θ from the semisimple conjugacy classes of a finite group GF of Lie type to the F-conjugacy classes of its Weyl group. We obtain two expressions for the number of semisimple classes mapped by θ into a given F-conjugacy class of W. The first involves distinguished coset representatives in the affine Weyl group and the second is the number of elements in the coroot lattice satisfying certain conditions. The Brauer complex plays a key role in the proof. The map θ has recently proved of interest in connection with probabilistic and combinatorial group theory.

We study one-relator free products in which the relator has free-product length $4$. We find conditions for such presentations to have a Freiheitssatz and classify all non-aspherical presentations under certain conditions.AMS 2000 Mathematics subject classification: Primary 20F05; 20F06; 20F10

We construct for each n > 2 infinitely many n-component oriented links that are neither amphicheiral nor invertible; among these examples, infinitely many are Brunnian links. Amphicheirality and invertibility questions concerning knots and links in the 3sphere S3 are among the earliest problems in classical knot theory. These questions are of interest since they add to our knowledge of knot and link groups. The Jones polynomial and its various generalizations detect nonamphicheirality of a wide range of knots and links, but they fail to distinguish a single knot or link from its inverse. In this paper, we construct for each n > 2 infinitely many n-component oriented links that are neither amphicheiral nor invertible; among these examples, infinitely many are Brunnian links. Our starting observation is that if an oriented link L in S3 is amphicheiral or invertible, then the corresponding covering links in the universal abelian cover of the complement of one component of L admit a certain symmetry. The examples are provided by applying the band-summing construction introduced by Cochran [1] to certain based Brunnian links and based homotopy Brunnian links. It should be noticed that the existence of noninvertible knots was first established by Trotter [7]. Noninvertible links with an arbitrary number of components and invertible proper sublinks were first constructed by Whitten [8], [9]. However, Whitten's examples are not Brunnian links and the noninvertibility was established by difficult arguments from combinatorial group theory. Milnor's ft-invariants [4], [5] of weight m have the ability to detect nonamphicheirality or noninvertibility of oriented links for m even or odd respectively. These invariants can be used to show that the n-component Brunnian link in Figure 7 of [4] is nonamphicheiral or noninvertible for n even or odd respectively. By using the algorithm provided by Cochran [1], further nonamphicheiral or noninvertible Brunnian links could be constructed. However, Milnor's ft-invariants fail to detect noninvertibility of 2component oriented links by Traldi [6] and it is not clear whether they detect noninvertibility of n-component oriented links for other even n. Definitions. An n-component oriented link in an oriented 3-manifold X is an ordered collection of n disjoint oriented circles tamely embedded in X. Two ncomponent oriented links L1 and L2 are equivalent or have the same link type if there exists an orientation preserving homeomorphism h of X onto itself such that Received by the editors April 29, 1996 and, in revised form, October 15, 1996. 1991 Mathematics Subject Classification. Primary 57M25.

We will study the presentations of fundamental groups of the complement of complexified real affine line arrangements that do not contain two parallel lines. By Yoshinaga's minimal presentation, we can give positive homogeneous presentations of the fundamental groups. We consider the associated monoids defined by the presentations. It turns out that, in some cases, left (resp. right) \emph{least common multiple} does not always exist. Hence, the monoids are neither \emph{Garside} nor \emph{Artin}. Nevertheless, we will show that they carry certain particular elements similar to the \emph{fundamental elements} in Artin monoids, and that, by improving the classical method in combinatorial group theory, they are \emph{cancellative monoids}. As a result, we will show that the word problem can be solved and the center of them are determined., arXiv admin note: text overlap with arXiv:1302.5736

A permutation group is cofinitary if any non-identity element fixes only finitely many points. This paper presents a survey of such groups. The paper has four parts. Sections 1-6 develop some basic theory, concerning groups with finite orbits, topology, maximality, and normal subgroups. Sections 7-12 give a variety of constructions, both direct and from geometry, combinatorial group theory, trees, and homogeneous relational structures. Sections 13-15 present some generalisations of sharply fc-transitive groups, including an orbit-counting result with a character-theoretic flavour. The final section treats some miscellaneous topics. Several open problems are mentioned.

It is well-known that the canonical commutation relation $[x,p]=i$ can be realized only on an infinite-dimensional Hilbert space. While any finite set of experimental data can also be explained in terms of a finite-dimensional Hilbert space by approximating the commutation relation, Occam's razor prefers the infinite-dimensional model in which $[x,p]=i$ holds on the nose. This reasoning one will necessarily have to make in any approach which tries to detect the infinite-dimensionality. One drawback of using the canonical commutation relation for this purpose is that it has unclear operational meaning. Here, we identify an operationally well-defined context from which an analogous conclusion can be drawn: if two unitary transformations $U,V$ on a quantum system satisfy the relation $V^{-1}U^2V=U^3$, then finite-dimensionality entails the relation $UV^{-1}UV=V^{-1}UVU$; this implication strongly fails in some infinite-dimensional realizations. This is a result from combinatorial group theory for which we give a new proof. This proof adapts to the consideration of cases where the assumed relation $V^{-1}U^2V=U^3$ holds only up to $\eps$ and then yields a lower bound on the dimension., Comment: 5+4 pages, minor revision, to appear in J. Math. Phys

The structure of certain quasiperiodic systems is analysed and interpreted by algebraic means. All systems considered have a free monoid and semigroup structure with n generators, as treated in the field of combinatorics on words. An extension from free monoids to free groups and their automorphisms, as treated by combinatorial group theory, applies to a class of iterative systems. The group structures yield algebraic relations and conserved quantities. Examples encompass the Fibonacci system and its generalizations. Motivated by the applications to the physics of these systems, homomorphisms from the free groups into linear operators of SU(2) and SU(1,1) are studied. The systems are also viewed in a geometry due to Fricke and Klein. The homomorphism to the group SU(1,1) is the basis for the determination of 1D electronic spectra. The class types, their multiplication, and the commutator properties are given. The physics of these systems corresponds to the continuous Schrodinger equation. The quasiperiodic structure gives rise to exact relations between continuous and discrete systems.

We study monoids generated by Zariski-van Kampen generators in the 17 fundamental groups of the complement of logarithmic free divisors in C^3 listed by Sekiguchi (Theorem 1). Five of them are Artin monoids and eight of them are free abelian monoids. The remaining four monoids are not Gaussian and, hence, are neither Garside nor Artin (Theorem 2). However, we introduce, similarly to Artin monoids, fundamental elements and show their existence (Theorem 3). One of the four non-Gaussian monoids satisfies the cancellation condition (Theorem 4)., Comment: 28 pages, 4 figures

Exact bounds for the positions of the branch points for cyclic coverings of the $p$-adic projective line by Mumford curves are calculated in two ways. Firstly, by using Fumiharu Kato's *-trees, and secondly by giving explicit matrix representations of the Schottky groups corresponding to the Mumford curves above the projective line through combinatorial group theory., 17 pages, 3 eps-figures. To appear in manuscripta mathematica

We propose a way of associating to each finitely generated monoid or semigroup a formal language, called its loop problem. In the case of a group, the loop problem is essentially the same as the word problem in the sense of combinatorial group theory. Like the word problem for groups, the loop problem is regular if and only if the monoid is finite. We study also the case in which the loop problem is context-free, showing that a celebrated group-theoretic result of Muller and Schupp extends to describe completely simple semigroups with context-free loop problems. We consider also right cancellative monoids, establishing connections between the loop problem and the structural theory of these semigroups by showing that the syntactic monoid of the loop problem is the inverse hull of the monoid., 21 pages

We describe a pair of invariants for actions of finite groups on shifts of finite type, the left-reduced and right-reduced shifts. The left-reduced shift was first constructed by U. Fiebig, who showed that its zeta function is an invariant, and in fact equal to the zeta function of the quotient dynamical system. We also give conditions for expansivity of the quotient, and applications to combinatorial group theory, knot theory and topological quantum field theory., 14 pages, no figures. To appear in Ergodic Theory and Dynamical Systems

Let G be a finite group and let M be a G-manifold. We introduce the concept of generalized orbifold invariants of M/G associated to an arbitrary group Gamma, an arbitrary Gamma-set, and an arbitrary covering space of a connected manifold Sigma whose fundamental group is Gamma. Our orbifold invariants have a natural and simple geometric origin in the context of locally constant G-equivariant maps from G-principal bundles over covering spaces of Sigma to the G-manifold M. We calculate generating functions of orbifold Euler characteristic of symmetric products of orbifolds associated to arbitrary surface groups (orientable or non-orientable, compact or non-compact), in both an exponential form and in an infinite product form. Geometrically, each factor of this infinite product corresponds to an isomorphism class of a connected covering space of a manifold Sigma. The essential ingredient for the calculation is a structure theorem of the centralizer of homomorphisms into wreath products described in terms of automorphism groups of Gamma-equivariant G-principal bundles over finite Gamma-sets. As corollaries, we obtain many identities in combinatorial group theory. As a byproduct, we prove a simple formula which calculates the number of conjugacy classes of subgroups of given index in any group. Our investigation is motivated by orbifold conformal field theory., Comment: Published by Algebraic and Geometric Topology at http://www.maths.warwick.ac.uk/agt/AGTVol3/agt-3-27.abs.html

We demonstrate how some problems arising in simplicial quantum gravity can be successfully addressed within the framework of combinatorial group theory. In particular, we argue that the number of simplicial 3-manifolds having a fixed homology type grows exponentially with the number of tetrahedra they are made of. We propose a model of 3D gravity interacting with scalar fermions, some restriction of which gives the 2-dimensional self-avoiding-loop-gas matrix model. We propose a qualitative picture of the phase structure of 3D simplicial gravity compatible with the numerical experiments and available analytical results., 24 pages

When one wishes to classify 2-complexes, the first classification scheme one must consider is homotopy type. In Section 1, we will define an obstruction to homotopy equivalence, called bias, but show that it is actually an obstruction to homology equivalence. In Section 2, we will refine the bias to the Browning obstruction and use it to get a complete classification of 2-complexes with finite abelian fundamental groups. In Section 3, we will give the currently known facts on the homotopy classification for other fundamental groups. Subsections 3.2 and 3.3, as well as the list of problems are co-authored with Cynthia Hog-Angeloni. Bias Invariant & Homology Classification The concept of bias is based on Whitehead's Theorem (Chapter II, Theorem 2.12). We will define bias using equivariant chain maps on the equivariant chain complexes of the universal covers of 2-complexes, as discussed in Chapter II, §3.2. Theorem 3.6 of Chapter II identifies maps of 2-complexes with chain maps for the universal coverings. The bias-invariant was first used in [Me76] and then in [Dy76], [Dy79], [Si77], [SiDy79] to show that certain 2-complexes were not homotopy equivalent. Dyer showed in [Dy86] that the bias invariant, in fact, detected integral homology equivalence. In §1.1, we will motivate and define bias as an obstruction to homotopy equivalence. In §1.2, we will show that bias is the complete obstruction to homology equivalence (with induced isomorphism on fundamental groups). In §1.3, we will make specific calculations of the bias to distinguish the homotopy types of important examples.

Surfaces appear in different fields of mathematics: in differential geometry, in complex analysis as Riemann surfaces, in algebraic geometry and topology. Most topological problems on surfaces can be treated within combinatorial group theory thanks to some basic results on surfaces. In the theory of Riemann surfaces discontinuous groups appear; again they have a rich combinatorial structure which we describe here.

The free group F n with n generators and its automorphism group Φ n , studied in combinatorial group theory, provide an algebraic non-commutative scheme for quasiperiodic systems. Homomorphisms from F 2 to the groups SU(2) and SU(1,1) are considered. A particular geometry, inspired by Fricke and Klein, is developed for these groups. The elements of Φ2 in this geometry are generated by elementary transformations of triangles on orbit spaces. The Fibonacci system is examined as an example. Matrix invariants and their geometric interpretation are studied beyond the usual trace map. The groups yield symmetry principles for spin and electron dynamics in quasiperiodic structures.

Actions of groups on ℝ-trees are natural generalizations of actions of groups on ℤ-trees (simplicial trees). The latter, known as Bass-Serre Theory, has become a standard tool in combinatorial group theory. This theory says that a group action on a ℤ-tree is equivalent to a combinatorial presentation of the group. On the other hand, actions of groups on ℝ-trees arise from groups of isometries of hyperbolic spaces, and have significant applications in the study of hyperbolic manifolds. Morgan, Shalen, Culler and others define and analyze compactification of representation space R(G) of a group G in SL(2, ℂ) and SO (n,1). For a valuation of the function field of a subvariety of R(G), they define an ℝ-tree on which G acts. This is applied notably when G = π 1(M), M a hyperbolic manifold. The tree and action then give a codimension-1 measured lamination on M. Applications include the theory of incompressible surfaces in 3-manifolds and the description of a natural boundary for Teichmuller space. The points at infinity correspond to πl (M)-actions on ℝ-trees.

Although the category of pro-finite groups forms a natural extension of the category of finite groups, it carries a richer structure in that it has categorical objects and notions which do not exist in the finite case; e.g. projective groups and free product. The existence of such notions in the extended category leads to the definition of the usual notions of combinatorial group theory, such as free groups and defining a group by generators and relations. Topics in various fields lead to a special consideration of pro-p groups: the tower problem (cf. [21]), Galois theory over p-adic fields and Demuskin groups (cf. [20]), the interpretation of generators and relations by means of cohomology (cf.

For finitely additively generated torsion free modules and rings, we show existence of module monomorphisms is decidable but of epimorphisms is undecidable. What structural problems in algebra are decidable? Grunewald and Segal [21 have recently shown a wide variety of isomorphism problems are decidable by a method of finding fundamental domains. (See [5, 6].) Matijasevic's negative solution to Hilbert's tenth problem has many undecidability consequences for algebra. Many problems in combinatorial group theory are undecidable. A particularly simple class of problems in algebra because of their linearity, are module problems. Here we show the monomorphism problem is decidable for finitely additively generated torsion free modules, and the epimorphism problem is undecidable. Remeslennikov proved for nilpotent groups the epimorphism problem is undecidable. Here our rings and modules are finitely additively generated unless otherwise specified. They are specified by giving a basis and products of basis elements. Additively they are torsion free. We consider (1) the monomorphism problem: given a ring 9i, modules 93,9I can we find a monomorphism h: 9) -+ 91?, and (2) the epimorphism problem: can we find an epimorphism h: 93 --+ 91? By finding we mean algorithmic solvability as with Hilbert's problem. Solvability of the isomorphism problem is contained in [2]. THEOREM 1. The monomorphism problem is decidable. PROOF. Tensor 9X,9I with the real numbers R. Then a monomorphism is an algebraic problem over the real numbers which can be decided because the first order theory of the real numbers is decidable. We may take the determinant of a suitable minor of a matrix to be 1. Approximate this linear mapping by a (linear) module homomorphism 9M01:1 IN0i 0. A sufficiently close approximation has the minor with nonzero determinant. Now multiply it by a number to make it integral. O THEOREM 2. The problem of, given a linear space (by additive generators) ? of matrices of nonnegative determinant over Z, of deciding whether M E ? with det M = 1 is undecidable. We may assume ? is a summand of Mn (Z) additively. Received by the editors August 20, 1986 and, in revised form, September 15, 1987. 1980 Mathematics Subject Classification (1985 Revision). Primary 16A64.

After a brief survey of the known results about group languages, we prove that many of the familiar classes of groups have word problems whose complexity is linear time. We also consider the complexity of extensions and HNN extensions. Finally, in an attempt to find languages that have complexity which is greater than linear time, we discuss the language of palutators, where a palutator is defined as a generalization of a palindrome and a commutator.

The purpose of this work is to demonstrate how a subgroup theorem, including Karrass’ and Solitar’s results [3, 4] for tree products and HNN constructions, may be deduced from the theory of groupoids (here called “groupnets”). It is well-known that many topological proofs of group theoretic results, such as the Nielsen theorem on subgroups of free groups, the Reidemeister-Schreier Theorem, Kurosh’ and Grushko’s Theorems, may be formalized in purely algebraic terms using groupoids (see for example Ordman [7], Stallings [8], Higgins [2], Crowell and Smythe [1]), however it seems to have been the general feeling, until Higgin’s work appeared, that the benefits of such a formalization were negligible, particularly in view of the large amount of preliminary machinery which must be assembled in order to make the theory work. We feel that this effort is in fact justified, in that the theory provides a “theorem-proving” machine for combinatorial group theory. Thus, once the basic machinery has been set up, it is completely obvious that a theorem of the Karrass and Solitar type “A subgroup of an HNN group is again an HNN group” must exist, and it merely remains to find the exact statement of the theorem. Proofs in the theory are usually (not always) entirely straightforward, often amounting to checking that some obvious construction actually satisfies all the requirements made upon it. Of course the details and notation in this present work become complex, because of the nature of the result to be proved, but we trust that the reader will find the basic idea of the argument (which is summarized in Section 8) acceptably simple.

Part exposition and part presentation of new results, this monograph deals with that area of mathematics which has both combinatorial group theory and mathematical logic in common. Its main topics are the word problem for groups, the conjugacy problem for groups, and the isomorphism problem for groups. The presentation depends on previous results of J. L. Britton, which, with other factual background, are treated in detail.

Combinatorial group theory has roots in Poincaré's work on the topology of manifolds, which in turn was based on problems in differential equations and analytic number theory. Thus the Fuchsian groups, which are the fundamental (first homotopy) groups of oriented negatively curved compact surfaces, served as important models in their day. In the last few years there have been advances in the understanding of the structure of fundamental groups of negatively curved manifolds, some of them based on examples from analytic number theory. Here I describe one of these developments and pose a few difficult combinatorial questions.