Undecidability of module homomorphisms

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.