* Your assessment is very important for improving the workof artificial intelligence, which forms the content of this project

# Download FROM COMMUTATIVE TO NONCOMMUTATIVE SETTINGS 1

Survey

Document related concepts

Capelli's identity wikipedia , lookup

Factorization wikipedia , lookup

Structure (mathematical logic) wikipedia , lookup

Group action wikipedia , lookup

Factorization of polynomials over finite fields wikipedia , lookup

Fundamental theorem of algebra wikipedia , lookup

Laws of Form wikipedia , lookup

Complexification (Lie group) wikipedia , lookup

Homological algebra wikipedia , lookup

Birkhoff's representation theorem wikipedia , lookup

Tensor product of modules wikipedia , lookup

Invariant convex cone wikipedia , lookup

Polynomial ring wikipedia , lookup

Transcript

FACTORIZATION THEORY: FROM COMMUTATIVE TO NONCOMMUTATIVE SETTINGS NICHOLAS R. BAETH AND DANIEL SMERTNIG Abstract. We study the non-uniqueness of factorizations of non zero-divisors into atoms (irreducibles) in noncommutative rings. To do so, we extend concepts from the commutative theory of non-unique factorizations to a noncommutative setting. Several notions of factorizations as well as distances between them are introduced. In addition, arithmetical invariants characterizing the non-uniqueness of factorizations such as the catenary degree, the ω-invariant, and the tame degree, are extended from commutative to noncommutative settings. We introduce the concept of a cancellative semigroup being permutably factorial, and characterize this property by means of corresponding catenary and tame degrees. Also, we give necessary and sufficient conditions for there to be a weak transfer homomorphism from a cancellative semigroup to its reduced abelianization. Applying the abstract machinery we develop, we determine various catenary degrees for classical maximal orders in central simple algebras over global fields by using a natural transfer homomorphism to a monoid of zero-sum sequences over a ray class group. We also determine catenary degrees and the permutable tame degree for the semigroup of non zero-divisors of the ring of n × n upper triangular matrices over a commutative domain using a weak transfer homomorphism to a commutative semigroup. 1. Introduction The study of factorizations in commutative rings and semigroups has a long and rich history. Beginning with attempts to understand the factorizations of elements in rings of algebraic integers into irreducibles, this field has grown to include the investigation of non-unique factorizations in Mori domains, Krull domains and Krull monoids, including the study of direct-sum decompositions of modules (see [BG14]). These investigations have used tools from multiplicative ideal theory, algebraic and analytic number theory, combinatorics, and additive group theory. A thorough overview of the various aspects of commutative factorization theory can be found in [And97, BW13, Cha05, FHL13, Ger09, GHK06]. On the other hand, the study of unique and non-unique factorization in noncommutative rings and semigroups has received limited attention. In fact, for many years the study of factorizations in noncommutative settings had been restricted to characterizing and studying noncommutative rings with properties analogous to that of commutative unique factorization domains or to studying factorizations of certain (symmetric) polynomials over noncommutative (e.g. matrix) rings (see [GRW01, HR95, LL04, LO04, GRSW05, GGRW05, LLO08, DL07, Ret10, Ler12]). From the beginning it was clear that each (noncommutative) PID intrinsically has certain unique factorization properties (see, for instance, [Jac43, Chapter 3.4], [Deu68, Chapter VI.9] and [Rei75, page 230]). More recently, such phenomena have been studied; for semifirs and in particular 2-firs by P. M. Cohn [Coh85, Coh06], for the ring of Hurwitz and Lipschitz quaternions by Conway and Smith [CS03] and by H. Cohn and Kumar [CK15], for quaternion orders by Estes and Nipp [EN89, Est91], and in a more general setting by Brungs [Bru69]. Somewhat different notions of unique factorization domains and unique factorization rings were introduced by Chatters and Jordan [Cha84, CJ86, Jor89], and have found applications in [JW01, LLR06, GY12]. Recently, techniques from the factorization theory of commutative rings and monoids have been used to investigate non-unique factorizations in a noncommutative setting. For example, in [BPA+ 11] factorizations within some natural subsemigroups of matrices with integer coefficients are considered, and in [BBG14] factorizations within the subsemigroup of non zero-divisors of the ring of n × n upper triangular matrices Tn (D)• over an arbitrary atomic commutative domain D are studied. In [Ger13], noncommutative Krull monoids are investigated. Through the study of the divisorial two-sided ideals of S that closely parallels the techniques that have been used fruitfully for commutative Krull monoids, it is shown that in the 2010 Mathematics Subject Classification. Primary 20M13; Secondary 16H10, 16U30, 20L05, 20M25. Key words and phrases. noncommutative rings, noncommutative semigroups, Krull monoids, maximal orders, distances, non-unique factorization. The first author was a Fulbright-NAWI Graz Visiting Professor in the Natural Sciences and supported by the AustrianAmerican Education Commission. The second author was supported by the Austrian Science Fund (FWF) projects P26036-N26 and W1230, Doctoral Program “Discrete Mathematics”. 1 2 N. BAETH AND D. SMERTNIG normalizing case (aS = Sa holds for all a in the Krull monoid S) many results from the commutative setting generalize. In [Sme13] this approach is, by means of divisorial one-sided ideal theory, extended to a class of semigroups that includes commutative and normalizing Krull monoids as special cases. In particular, this is applied to investigate factorizations in the semigroup of non zero-divisors of classical maximal orders in central simple algebras over global fields. In this way, results on some basic invariants of non-unique factorization theory, namely sets of lengths, are obtained. In [BPA+ 11], [BBG14], [Ger13], and [Sme13], the focus on noncommutative factorizations was solely on the sets of lengths of factorizations of a given element; that is, sets of the form L(a) = { n ∈ N0 : a = u1 · · · un with each ui an atom in S } and associated invariants. Much of this work was done through the use of various generalizations of transfer homomorphisms to the noncommutative settings, each of which preserves sets of lengths. While sets of lengths are amongst the most classical of arithmetical invariants describing the non-uniqueness of factorizations, their usefulness is limited by the fact that they can only measure how far a ring or semigroup is away from half-factoriality, that is, the property that all factorizations of a non-unit element into atoms have the same length. The purpose of this paper is to study more refined invariants that describe the non-uniqueness of factorizations in a noncommutative setting, with considerations not just of sets of lengths, but also of distinct factorizations of elements and divisibility properties. Our main objects of interest are certain classes of rings, but, as is done in the commutative case, we develop everything in the setting of cancellative semigroups (and often more generally in the setting of cancellative small categories), for essentially three reasons: First, we wish to emphasize that the theory of factorizations is a purely multiplicatively one; secondly, many of the auxiliary objects that appear in studying the factorization theory of rings (e.g. the monoid of zero sum sequences) are not themselves rings, yet we need to be able to apply the language of factorization theory to these objects; and thirdly, sometimes the object one is interested in studying itself is not a ring, but a semigroup. Moreover, throughout we will restrict to the cancellative case because even in the commutative setting the introduction of non-cancellative elements significantly increases the complexity of studying factorizations. For rings, this means that we will consider factorizations within the semigroup of non zero-divisors. While it is completely clear how sets of lengths should be defined in the noncommutative setting, any attempt to introduce more refined invariants such as the catenary degree or the tame degree in a noncommutative setting immediately leads one to the following question. When are two representations of a non-unit as products of atoms to be considered the same, and when are they distinct? In the commutative setting, one typically considers factorizations up to permutation and associativity, but this seems less fitting for many natural noncommutative objects. Further, in order to be able to describe how distinct different factorizations of an element are, one needs to define a reasonable distance between two factorizations. The choice of a notion of a distance and that of a factorization are closely linked, but there does not seem to be a canonical choice that is entirely satisfactory. For example, based on investigations by P. M. Cohn and Brungs in [Bru69, Coh85, Coh06], one can introduce two different notions of factorizations and corresponding distances, both coinciding with the usual one when considered in the commutative setting. A third notion, that of permutable factorizations, turns out to be particularly well suited to other examples, for instance the semigroup of non zero-divisors of the ring of n × n upper triangular matrices over a commutative atomic domain. For this reason, in Section 3, we first recall a rigorous notion of rigid factorizations. Based on this, we introduce an axiomatic notion of a distance d, and derive from it the notion of d-factorizations. Each such distance gives rise to a corresponding catenary degree and monotone catenary degree which we define and study in Section 4. As in the commutative setting, the (monotone) catenary degree associated to a distance d provides a measure of how far away a cancellative small category is from being d-factorial. In Propositions 4.6 and 4.8 we show that catenary degrees can be studied using (weak) transfer homomorphisms. In Section 5 we approach the study of factorization from the viewpoint of divisibility, introducing almost prime-like elements and prime-like elements that generalize prime elements from the commutative setting. We then introduce corresponding tame degrees and ω-invariants based on permutable factorizations that measure how far a given element is from being almost prime-like. With these notions we are able to give characterizations of permutable factoriality in Propositions 5.15, 5.19 and 5.21. In Section 6 we consider the notion of weak transfer homomorphisms as introduced in [BBG14] and give criteria for when there is such a weak transfer homomorphism from a cancellative semigroup to its reduced abelianization (if the abelianization is itself cancellative). Any weak transfer homomorphism preserves FACTORIZATION THEORY: FROM COMMUTATIVE TO NONCOMMUTATIVE SETTINGS 3 sets of lengths, and by constructing weak transfer homomorphisms from noncommutative cancellative semigroups to commutative cancellative semigroups, we illustrate that sometimes it is possible to reduce the study of sets of lengths in a noncommutative ring or semigroup to a corresponding commutative semigroup, where sets of lengths may have been investigated before. Of course, such noncommutative semigroups then necessarily have systems of sets of lengths which also occur as systems of sets of lengths in the commutative setting. At the end of the section we revisit some known examples of weak transfer homomorphisms: In particular, we study various distances for Tn (D)• , and determine the corresponding catenary degrees, tame degrees and ωp -invariants in Proposition 6.14. Also, in Proposition 6.16, we show that for a normalizing Krull monoid S (as studied in [Ger13]), ωp (S, a) is always finite as is the case in the commutative setting. Finally, in Section 7, we investigate catenary degrees in saturated subcategories of arithmetical groupoids and arithmetical maximal orders in quotient semigroups (as studied in [Sme13]). This treatment also includes normalizing Krull monoids considered in [Ger13]. Under suitable conditions, these subcategories, respectively maximal orders, possess a transfer homomorphism to a monoid of zero-sum sequences over a subset of an abelian group. The factorization theory of monoids of zero-sum sequences over finite abelian groups has been intensively studied (see [Ger09, Gry13]), due to its applications to commutative Krull monoids arising from rings of algebraic integers and holomorphy rings in function fields over finite fields. It is therefore desirable to show that catenary degrees in our setting can be studied by means of this transfer homomorphism, as the known results from the commutative setting then immediately carry over. Indeed, under the expected conditions, we are able to obtain satisfactory results about the catenary degree (cf. Theorem 7.8 and Corollary 7.11) that mirror results about commutative Krull monoids. These results, in fact, do not depend very strongly on the particular distance chosen. We then apply these results to classical maximal orders in central simple algebras over global fields (as long as we have the additional property that every stable free left ideal is free), and obtain Theorem 7.12 and Corollary 7.14, showing that the catenary degree in this case is controlled by the catenary degree of a monoid of zero-sum sequences over a certain ray class group. Thus, for instance, the results on catenary degrees in commutative Krull monoids obtained in [GGS11] hold in our noncommutative setting. We summarize some of the consequences in Corollary 7.16. Throughout, we illustrate the limits of extending the commutative theory to the noncommutative setting by way of simple examples of semigroups given by a presentation via the generators and relations. While such semigroups will only serve as isolated examples for us, we note that the study of the interplay of arithmetical invariants and presentations of a commutative semigroup was initiated by P. A. Garcı́a Sánchez and further investigated by various authors (see [BGSG11, CGSL+ 06, Phi10]). We have concentrated the discussion of the main objects of our interest at the end of Section 6, where we discuss Tn (D)• , matrix rings over PIDs, and almost commutative semigroups (which include normalizing Krull monoids), and Section 7, where we discuss arithmetical maximal orders (which, again, include matrix rings over PIDs and normalizing Krull monoids), and in particular classical maximal orders in central simple algebras over global fields. The relationship between arithmetical maximal orders, Krull monoids, Krull rings, and UF-monoids in the sense of P. M. Cohn is discussed in the preliminaries. 2. Preliminaries Notation. We denote by N = {1, 2, 3, . . .} the set of natural numbers, and by N0 = N ∪ {0} the set of non-negative integers. If a, b ∈ R, we write [a, b] = { x ∈ Z : a ≤ x ≤ b } for the discrete interval from a to b. For n ∈ N0 , we write Sn for the group of permutations on [1, n] (with S0 = S1 the trivial group). We write Cn for a cyclic group of order n ∈ N. We will often introduce an arithmetical invariant as a supremum of a subset X ⊂ N0 ∪ {∞} and, by convention, we set sup ∅ = 0. Semigroups and small categories. By a semigroup we always mean a semigroup with a neutral element. A homomorphism of semigroups is always assumed to preserve the neutral element, and an empty product in a semigroup is defined to be equal to the neutral element. All rings are assumed to have an identity element, and all ring homomorphisms preserve the identity. A domain is a ring in which zero is the only zero-divisor, and a principal ideal domain (PID) is a domain in which every left ideal is generated by a single element and every right ideal is generated by a single element. In studying the divisorial one-sided ideal theory of noncommutative semigroups (as will be necessary in Section 7), we are naturally led to consider not only semigroups, but the more general notion of a small category. Hence we will introduce the necessary notions in this setting. A small category is a category for which both the class of objects and the class of morphisms are sets. To a semigroup S we may associate a category with a single object with set of morphisms S and composition of morphisms given by the operation of the semigroup. Conversely, to a small category with a single object 4 N. BAETH AND D. SMERTNIG we can associate the semigroup of endomorphisms on that object. In this way we obtain an equivalence of the category of semigroups and the category of small categories with a single object. We view small categories as generalizations of semigroups with a partial operation, and set up our notation for small categories in a way that facilitates this point of view: In particular, we emphasize the role of the morphisms, while deemphasizing the role of the objects. Let H be a small category. We identify the set of objects of H with the corresponding identity morphisms, and denote the set of identity morphisms of the objects of H by H0 . To be consistent with the language used for semigroups, we shall refer to morphisms of the category H simply as elements of H, writing a ∈ H for a morphism of H, and call functors between small categories homomorphisms. For each a ∈ H we denote by s(a) ∈ H0 its source (domain), and by t(a) ∈ H0 its target (codomain). Writing composition left to right, contrary to the usual convention for categories, but in line with the conventions for groupoids, we write ab for the composition of a and b in H if t(a) = s(b). The set of all isomorphisms (which we shall call units) in H will be denoted by H × . We say that H is reduced if H × = H0 , that is, the only isomorphisms are the identity morphisms, and we say that H is a groupoid if H = H × . For S e, f ∈ H0 we set H(e, f ) = { a ∈ H : s(a) = e and t(a) = f }, and further H(e) = H(e, e), H(e, ·) = f 0 ∈H0 H(e, f 0 ), S and H(·, f ) = e0 ∈H0 H(e0 , f ). For A, B ⊂ H we define AB = { ab ∈ H : a ∈ A, b ∈ B, t(a) = s(b) }, and if a ∈ H, we define aB = {a}B and Ba = B{a}. We say that b ∈ H left divides a ∈ H, and write b |l a, if a ∈ bH. Two elements a, b ∈ H are left coprime if, for all c ∈ H, c |l a and c |l b implies c ∈ H × . We define b |r a and the notion right coprime analogously. A congruence relation ∼ on a category H is, for each pair e, f ∈ H0 , a reflexive, symmetric and transitive relation on H(e, f ) (we tacitly denote all of these relations by ∼ again) satisfying the condition that for all x, x0 , y, y 0 ∈ H with s(x) = s(x0 ), t(x) = t(x0 ) = s(y) = s(y 0 ), t(y) = t(y 0 ) and x ∼ x0 , y ∼ y 0 , we have xy ∼ x0 y 0 . Given a congruence relation ∼ on H, we may define a quotient category H/ ∼ with (H/ ∼)0 = H0 and (H/ ∼)(e, f ) = H(e, f )/ ∼ for all e, f ∈ H0 . We shall often not explicitly specify the source and target of elements, but tacitly assume that the necessary conditions for certain products to be defined are fulfilled: For example, if we write “Let a, b ∈ H such that ab = . . .”, then we shall implicitly assume that a and b are such that t(a) = s(b). We say that H is normalizing if Ha = aH for all a ∈ H. In this case, for all a ∈ H, we have s(a) = t(a). Indeed, a = s(a)a = bs(a) for some b ∈ H with t(b) = s(a), and thus b = a and s(a) = t(a). Thus H(e, f ) = ∅ whenever e, f ∈ H0 are distinct, and H is a union of disjoint semigroups. Clearly, every commutative semigroup is normalizing. If H is a small category and a ∈ H, then a is cancellative if for all b, c ∈ H, ab = ac implies b = c and ba = ca implies b = c (that is, a is both a monomorphism and an epimorphism). The category H itself is called cancellative if each a ∈ H is cancellative. We write H • for the cancellative subcategory of cancellative elements of H. Let H be a cancellative small category. If a, b ∈ H with ab = t(b) = s(a), then bab = b, and hence ba = s(b) = t(a). Similarly, aba = a implies ab = s(a) = t(b). Thus every left (right) invertible element is invertible. If m ∈ N and a1 , . . . , am ∈ H are such that a1 · · · am ∈ H × , then ai ∈ H × for each i ∈ [1, m]. We call two elements a, b ∈ H associated, and write a ' b, if there exist ε, η ∈ H × such that b = εaη. Clearly ' is an equivalence relation and we denote the equivalence class of a ∈ H by [a]' . In general, associativity may not be a congruence relation. In the case of small categories this is partially due to the fact that our notion of a congruence relation is very restrictive. However, we will only care about this relation in the case of semigroups, and will not introduce a more general notion of congruences for small categories. If H × a = aH × for all a ∈ H, then, H × (e, f ) = ∅ for all e, f ∈ H0 which are distinct. Moreover, in this case, ' is a congruence relation and Hred is again cancellative. These conditions are satisfied if H is normalizing. Indeed, suppose H is normalizing, a ∈ H, and ε ∈ H × with t(ε) = s(a). We have already observed that in this case t(ε) = s(ε) = t(ε−1 ). Therefore, since H is normalizing, there exist b, c ∈ H such that εa = ab and ε−1 a = ac. Then a = (εε−1 )a = abc, and by cancellativity bc = s(b). Thus b, c ∈ H × , and hence H × a ⊂ aH × . The other inclusion follows similarly. If H is a small category such that ' is a congruence relation, we define the reduced small category × associated to H as Hred = H/ '. Note that Hred is indeed reduced with Hred = { [e]' : e ∈ H0 }. If × −1 × π : H → Hred denotes the canonical homomorphism, then π (Hred ) = H . If S is a semigroup, we will call Sred the reduced semigroup associated to S. Let Q be a quiver, that is, a directed graph which may contain multiple arrows between each pair of vertices as well as loops. If a is an arrow of Q, we write s(a) for its starting vertex and t(a) for its target vertex. A path from a vertex e of Q to a vertex f of Q is a tuple (e, a1 , . . . , ak , f ) with k ∈ N0 and a1 , . . . , ak arrows of Q such that either k > 0 and e = s(a1 ), t(ai ) = s(ai+1 ) for all i ∈ [1, k − 1], and t(ak ) = f , or k = 0 and e = f . To a quiver Q we associate the path category F ∗ (Q) with objects the vertices of Q and FACTORIZATION THEORY: FROM COMMUTATIVE TO NONCOMMUTATIVE SETTINGS 5 morphisms from a vertex e to a vertex f consisting of all paths from e to f in Q. The composition is given by the natural concatenation of paths. This construction yields a morphism of quivers j : Q → F ∗ (Q) and the pair (F ∗ (Q), j) is characterized by the universal property that any morphism of quivers f : Q → H to a small category H factors through j in a unique way. If X is a set, we may associate to X the quiver consisting of a single vertex and the set of loops X on that vertex. In this special case we recover the notion of a free monoid, the elements of which we may view as words on the alphabet X, and which we shall denote by F ∗ (X). As is usual, we shall write elements of F ∗ (X) as formal products on the alphabet X, instead of adopting the tuple notation that we use for path categories. We write hX | Ri for the semigroup with generators X and relations R, that is, hX | Ri is the quotient of F ∗ (X) by the congruence relation generated by { (u, v) ∈ F ∗ (X) × F ∗ (X) : u = v ∈ R }. By F(X) we denote the (multiplicatively written) free abelian monoid with basis X. Basic notions of factorization theory. Let H be a cancellative small category. An element u ∈ H \ H × is an atom (or irreducible) if u = ab with a, b ∈ H implies either a ∈ H × or b ∈ H × . We denote by A(H) the quiver of all atoms of H, that is, the quiver with vertex set H0 and arrows consisting of atoms of H. When the additional structure of the quiver is not necessary (in particular in the case that H is a semigroup), we will view A(H) simply as the set of atoms. We say that H is atomic if every non-unit element of H can be expressed as a finite product of atoms of H. A sufficient condition for a cancellative small category H to be atomic is that it satisfies the ascending chain condition both on principal left ideals and on principal right ideals. The standard proof from commutative monoids or domains generalizes to this setting; see for example [Sme13, Proposition 3.1]. Transfer homomorphisms are a key tool in the investigation of non-unique factorizations (see [GHK06, Section 3.2]). The notion of a weak transfer homomorphism was introduced in [BBG14] to be able to study sets of lengths in a wider class of noncommutative semigroups than is possible with transfer homomorphisms. In either case, given a cancellative small category H one seeks to find an easier-to-study or more well-understood cancellative small category T , and a homomorphism from H to T , that preserves many properties related to factorizations. In our applications, the target category T will always be a commutative cancellative semigroup. Definition 2.1. Let H and T be cancellative small categories. (1) A homomorphism φ : H → T is called a transfer homomorphism if it has the following properties: (T1) T = T × φ(H)T × and φ−1 (T × ) = H × . (T2) If a ∈ H, b1 , b2 ∈ T and φ(a) = b1 b2 , then there exist a1 , a2 ∈ H and ε ∈ T × such that a = a1 a2 , φ(a1 ) = b1 ε−1 , and φ(a2 ) = εb2 . (2) Suppose T is atomic. A homomorphism φ : H → T is called a weak transfer homomorphism if it has the following properties: (T1) T = T × φ(H)T × and φ−1 (T × ) = H × . (WT2) If a ∈ H, n ∈ N, v1 , . . . , vn ∈ A(T ) and φ(a) = v1 · · · vn , then there exist u1 , . . . , un ∈ A(H) and a permutation σ ∈ Sn such that a = u1 · · · un and φ(ui ) ' vσ(i) for each i ∈ [1, n]. It is easy to see that if H and T are cancellative small categories and φ : H → T is a transfer homomorphism, or T is atomic and φ : H → T is a weak transfer homomorphism, then an element u ∈ H is an atom of H if and only if φ(u) is an atom of T . If H and T are cancellative small categories and φ : H → T is a transfer homomorphism, then H is atomic if and only if T is atomic. If T is atomic and φ : H → T is a weak transfer homomorphism, then H is also atomic. If ' is a congruence relation on a cancellative small category H and Hred is cancellative, it is easy to check that the canonical homomorphism H → Hred is a transfer homomorphism. A composition of two transfer homomorphisms is again a transfer homomorphism, and the same holds for weak transfer homomorphisms. In particular, if φ : H → T is a (weak) transfer homomorphism, ' is a congruence relation on T , and Tred is cancellative, then the induced homomorphism φ : H → Tred is also a (weak) transfer homomorphism. The following example shows that in order to obtain a notion that preserves factorization theoretical invariants it is indeed necessary to require that T is atomic in the definition of a weak transfer homomorphism. Example 2.2. Let P be a countable set, say P = { pn : n ∈ N0 }, and let S = F(P ) be the free abelian monoid with basis P . Let ∼ be the congruence relation on S generated by { pn = p2n+1 : n ∈ N0 }, and let T = S/∼ be the quotient semigroup with canonical homomorphism π : S → T . We claim that T is cancellative. By the universal property of the free abelian monoid, there exists a semigroup homomorphism ϕ : S → (Q, +) such that ϕ(pn ) = 2−n for all n ∈ N0 , and ϕ factors through π to give a homomorphism T → (Q, +) that maps [pn ]∼ to 2−n . It follows that, for all n, k, l ∈ N0 , pkn ∼ pln if and only if k = l. Let 6 N. BAETH AND D. SMERTNIG a, b, c ∈ S be such that ac ∼ bc. By the defining relations of T , there exists an n ∈ N0 and m, k, l ∈ N0 k l m+k such that c ∼ pm ∼ pm+l and hence k = l and a = b. Thus T is n , a ∼ pn , and b ∼ pn . Therefore pn n cancellative. Since S and T are both reduced, the homomorphism π satisfies (T1), and since T obviously contains no atoms (WT2) is trivially satisfied. However, atoms of S are not mapped to atoms of T and, in fact, S is factorial while T is not even atomic. It follows that if T is atomic, then any transfer homomorphism φ : H → T is also a weak transfer homomorphism. However, the converse is not true in general. The following lemma better illustrates the difference between transfer homomorphisms and weak transfer homomorphisms. We omit the proof as the first two claims follow by straightforward induction and the defining properties, and the last claim is an immediate consequence of the second. Lemma 2.3. Let H and T cancellative small categories and let T be atomic. (1) Let φ : H → T be a homomorphism satisfying (T1). Then φ is a transfer homomorphism if and only if the following property holds: If a ∈ H, n ∈ N, v1 , . . . , vn ∈ A(T ) and φ(a) = v1 · · · vn , then there exist u1 , . . . , un ∈ A(H) and ε1 = s(v1 ), ε2 , . . . , εn , εn+1 = t(vn ) ∈ T × such that a = u1 · · · un , and φ(ui ) = εi vi ε−1 i+1 for each i ∈ [1, n]. (2) Suppose that T is a commutative semigroup, and let φ : H → T be a homomorphism satisfying (T1). The following statements are equivalent. (a) φ is a weak transfer homomorphism. (b) If a ∈ H, n ∈ N≥2 , v1 , . . . , vn ∈ A(T ) and φ(a) = v1 · · · vn , then there exist i ∈ [1, n], a0 ∈ H and u ∈ A(H) such that a = a0 u, φ(a0 ) ' v1 · · · vi−1 vi+1 · · · vn , and φ(u) ' vi . Furthermore, the following statements are equivalent. (a) φ is a transfer homomorphism. (b) If a ∈ H, b1 , b2 ∈ T and φ(a) = b1 b2 , then there exist a1 , a2 ∈ H such that a = a1 a2 , φ(a1 ) ' b1 , and φ(a2 ) ' b2 . (c) If a ∈ H, n ∈ N, v1 , . . . , vn ∈ A(T ) and φ(a) = v1 · · · vn , then there exist u1 , . . . , un ∈ A(H) such that a = u1 · · · un and φ(ui ) ' vi for each i ∈ [1, n]. (3) Suppose H and T are commutative semigroups, and let φ : H → T be a homomorphism. Then φ is a transfer homomorphism if and only if it is a weak transfer homomorphism. Remark 2.4. There are examples of atomic semigroups for which there exists a weak transfer homomorphism to some commutative atomic semigroup, but for which there does not exist a transfer homomorphism to any commutative semigroup. Indeed, if D is any commutative atomic domain with atoms u and v such that u2 = v m for some m > 2, and S = T2 (D)• denotes the cancellative semigroup of all 2 × 2 upper triangular matrices with entries in D having nonzero determinant, then there is no transfer homomorphism from S to any commutative semigroup. However, there is a weak transfer homomorphism from S to (D• red )2 . See [BBG14, Example 4.5] for details. In some cases, (weak) transfer homomorphisms do not transfer certain information from T to H. It will therefore occasionally be useful to impose the following strong extra condition. Definition 2.5. Let H and T be cancellative small categories and let φ : H → T be a homomorphism. We say that φ is isoatomic provided that φ(u) ' φ(v) implies u ' v for all u, v ∈ A(H). The following lemma illustrates just how strong the isoatomic condition is when the domain of a weak transfer homomorphism is assumed to be commutative. A more general version of this lemma will be given in Proposition 6.9. Lemma 2.6. Let S and T be commutative atomic cancellative semigroups, and let φ : S → T be an isoatomic (weak) transfer homomorphism. Then φ induces an isomorphism Sred ∼ = Tred . Proof. By definition, T = φ(S)T × , so the induced semigroup homomorphism φred : Sred → Tred is surjective. Suppose that φ(a) ' φ(b) for some a, b ∈ S. Since T is atomic, there exist n ∈ N0 and atoms w1 , . . . , wn in T such that φ(a) ' φ(b) ' w1 · · · wn . Since φ is a weak transfer homomorphism and S is commutative, φ is a transfer homomorphism. Thus there are atoms u1 , . . . , un and v1 , . . . , vn in S such that a ' u1 · · · un , b ' v1 · · · vn , and φ(ui ) ' φ(vi ) ' wi for each i ∈ [1, n]. Since φ is isoatomic, ui ' vi for each i ∈ [1, n] and thus a ' b. We have therefore shown that φ(a) ' φ(b) implies a ' b and hence the induced homomorphism φred : Sred → Tred is an isomorphism. Sets of lengths and invariants derived from them belong to the most basic invariants used in studying non-unique factorizations. We refer the reader to [GHK06, Chapter 4] for a thorough introduction to the FACTORIZATION THEORY: FROM COMMUTATIVE TO NONCOMMUTATIVE SETTINGS 7 study of sets of lengths in the commutative setting. If H is a cancellative small category and a ∈ H \ H × , then L(a) = LH (a) = { n ∈ N : there exist u1 , . . . , un ∈ A(H) with a = u1 · · · un } ⊂ N is called the set of lengths of a. We set L(ε) = {0} for all ε ∈ H × . We call L(H) = { LH (a) : a ∈ H } the system of sets of lengths of H. Let ∅ = 6 L ⊂ Z. A positive integer d ∈ N is a distance of L if there exists an l ∈ L such that L ∩ [l, l + d] = {l, l + d}. We denote by ∆(L) the set of all distances of L. The set of distances of H is defined as [ ∆(H) = ∆(L). L∈L(H) We say that H is half-factorial if |L(a)| = 1 for all a∈ H, equivalently, H is atomic and ∆(H) = ∅. The elasticity of a set L ⊂ N is ρ(L) = sup m n : m, n ∈ L , and ρ({0}) = 0. The elasticity of an element a ∈ H is ρH (a) = ρ(LH (a)) and the elasticity of H is ρ(H) = sup{ ρH (a) : a ∈ H }. Note that H is half-factorial if and only if H is atomic and ρ(H) = 1. (Weak) transfer homomorphisms are a key tool in studying sets of lengths, due to the following straightforward but important result (a proof in the semigroup case for transfer homomorphisms can be found in [Ger13, Proposition 6.4] and for weak transfer homomorphisms in [BBG14, Theorem 3.2]). Lemma 2.7. Let H and T be cancellative small categories. Let φ : H → T be a transfer homomorphism, or let T be atomic and φ : H → T a weak transfer homomorphism. Then LH (a) = LT (φ(a)) for all a ∈ H, and in particular L(H) = L(T ). In the noncommutative setting, (weak) transfer homomorphisms to appropriate commutative semigroups have already been used to study sets of lengths in [BPA+ 11, BBG14, Ger13, Sme13]. Arithmetical maximal orders and Krull monoids. In Section 7 we investigate catenary degrees in arithmetical maximal orders in quotient semigroups, a class of semigroups that was first studied by Asano and Murata in [AM53]. Developing our machinery in this abstract setting allows us to simultaneously treat normalizing and commutative Krull monoids as well as bounded Krull rings in the sense of Chamarie (see [Cha81, MVO12]), and in particular the classical maximal orders in central simple algebras over global fields (see [Rei75]) to which we ultimately apply our abstract results. Therefore we recall the following, referring to [Sme13] for more details. Let Q be a quotient semigroup (that is, a semigroup in which every cancellative element is invertible). A subsemigroup S ⊂ Q is an order in Q if for all q ∈ Q, there exist a, b ∈ S and c, d ∈ S ∩ Q× such that q = ac−1 = d−1 b. Two orders S and S 0 in Q are equivalent, denoted by S ∼ S 0 , if there exist a, b, c, d ∈ Q× such that aSb ⊂ S 0 and cS 0 d ⊂ S. This is an equivalence relation on the orders in Q. A maximal order is an order in Q that is maximal in its equivalence class (with respect to set inclusion). A subset I ⊂ Q is called a fractional left S-ideal if SI ⊂ I, and there exist x, y ∈ Q× such that x ∈ I and Iy ⊂ S. It is called a left S-ideal if moreover I ⊂ S. (Fractional) right S-ideals are defined analogously, and we call I a (fractional) S-ideal if it is both, a (fractional) left and right S-ideal. For a fractional left (respectively right) S-ideal I, we set I −1 = { q ∈ Q | IqI ⊂ I }, and this is a fractional right (respectively left) S-ideal. We define Iv = (I −1 )−1 and call I divisorial if I = Iv . The divisorial fractional left S-ideals form a lattice with respect to set inclusion, where I ∨ J = (I ∪ J)v and I ∧ J = I ∩ J, and so do the divisorial fractional right S-ideals. An order S is bounded if every fractional left S-ideal contains a fractional S-ideal, and every fractional right S-ideal contains a fractional S-ideal. Definition 2.8 ([Sme13, Definition 5.18]). Let S be a maximal order in a quotient semigroup Q. We say that S is an arithmetical maximal order if it has the following properties: (A1) S satisfies both the ACC (ascending chain condition) on divisorial left S-ideals and the ACC on divisorial right S-ideals. (A2) S is bounded. (A3) The lattice of divisorial fractional left S-ideals is modular, and the lattice of divisorial fractional right S-ideals is modular. We note that if S is an arithmetical maximal order and S 0 is a maximal order in Q that is equivalent to S, then S 0 is also an arithmetical maximal order. Analogous ring-theoretic definitions are made for a ring R which is an order in a quotient ring Q. We now summarize the connections between arithmetical maximal orders and more familiar notions. 8 N. BAETH AND D. SMERTNIG (1) Let S be an order in a group Q. If S is an arithmetical maximal order, then S is a Krull monoid in the sense of [Ger13] (that is, S is a cancellative semigroup that is left and right Ore, is a maximal order in its quotient group, and satisfies the ACC on divisorial S-ideals). If, in addition, S is normalizing, then S is an arithmetical maximal order if and only if it is a Krull monoid. In particular, a commutative cancellative semigroup is an arithmetical maximal order (in its quotient group) if and only if it is a commutative Krull monoid (that is, a commutative cancellative semigroup which is completely integrally closed and satisfies the ACC on divisorial ideals). (2) Let S be a normalizing cancellative semigroup. Then S is a UF-monoid in the sense of [Coh85, Chapter 3.1] if and only if Sred is a free abelian monoid, and S is a Krull monoid if and only if Sred is a commutative Krull monoid. It follows that S is a UF-monoid if and only if it is a Krull monoid with trivial divisor class group (that is, every divisorial S-ideal is principal). (3) Let R be a prime PI ring. Then R is a Krull ring if and only if R• is a Krull monoid. Equivalently, R is a Krull ring if and only if it is a maximal order in its quotient ring and satisfies the ACC on divisorial R-ideals (equivalently, on divisorial left and right R-ideals). If R is a Krull ring, then the semigroup (R, ·) is an arithmetical maximal order. (This remains true in more general settings; see [Cha81].) (4) If R is a bounded Dedekind prime ring, then (R, ·) is an arithmetical maximal order. (5) Let K be a global field, and denote by S the set of non-archimedean places of K. For v ∈ S denote by OT v ⊂ K the discrete valuation ring of v. A holomorphy ring in K is a subring O ⊂ K such that O = v∈S\S0 Ov with S0 ⊂ S finite and S0 6= ∅ in the function field case. A central simple algebra A over K is a finite-dimensional K-algebra with center K that is simple as a ring. A classical (O-)order in A is a subring R ⊂ A such that O ⊂ R, KR = A, and R is finitely generated as O-module (see [MR01, Rei75]). A classical maximal (O-)order in A is a classical O-order that is maximal with respect to set inclusion amongst classical O-orders. If R is a classical maximal order in A, then R is a Dedekind prime ring, a PI ring, and in particular a Krull ring. Investigating such classical maximal orders is the focus and main motivation of Section 7. Particular examples of classical maximal orders are, for instance, Mn (O) where O is a ring of algebraic integers and n ∈ N, as well as classical maximal orders in quaternion algebras over number fields, such as the ring of Hurwitz quaternions Z[i, j, k, 1+i+j+k ] with k = ij = −ji and 2 i2 = j 2 = −1. Monoids of zero-sum sequences are examples of commutative Krull monoids and play an important role in studying non-unique factorizations in commutative Krull monoids. Indeed, every commutative Krull monoid possesses a transfer homomorphism to a monoid of zero-sum sequences over a subset of its divisor class group (see [GHK06, Chapter 3.4]). Under certain conditions, this continues to hold true for arithmetical maximal orders, and it is this transfer homomorphism that was exploited in [Sme13] to study sets of lengths in this setting, and that we will use in Section 7 to study catenary degrees. We therefore recall the definition of monoids of zero-sum sequences. Let G be an additive abelian group, GP ⊂ G a subset and let F(GP ) be the (multiplicatively written) free abelian monoid with basis GP . Following the tradition of combinatorial number theory, elements S ∈ F(GP ) are called sequences over GP , and are written in the form S = g1 · · · gl with l ∈ N0 and g1 , . . . , gl ∈ GP . To a sequence S we associate its length, |S| = l, and its sum, σ(S) = g1 + · · · + gl ∈ G. We call the submonoid B(GP ) = { S ∈ F(GP ) : σ(S) = 0G } of F(GP ) the monoid of zero-sum sequences (over GP ). The minimal zero-sum sequences are the atoms of B(GP ), and the Davenport constant is D(GP ) = sup{ |S| : S ∈ A(B(GP )) }, that is, the supremum of the lengths of minimal zero-sum sequences. If S is a normalizing Krull monoid, G is its divisor class group, and GP is the set of classes containing prime divisors, then there exists a transfer homomorphism S → B(GP ) (see [Ger13, Theorems 6.5 and 4.13]). For this reason, monoids of zero-sum sequences, and in particular the Davenport constant, have been the focus of intensive study in combinatorial and additive number theory (see, for instance, [Ger09, Gry13]). Many factorization theoretic invariants of B(GP ) can be bounded (or even expressed) in terms D(GP ). If D(GP ) is finite, the Structure Theorem for Sets of Lengths ([Ger09, Definition 3.2.3]) holds for B(GP ), which implies that sets of lengths are almost arithmetical multiprogressions, with differences described by the set of distances, ∆(B(GP )). In the case G = GP , ∆(B(GP )) is a finite interval starting at 1 (if it is non-empty). Due to the existence of a transfer homomorphism, the same is then true for S itself. Similarly, if S is not half-factorial, its catenary degree is c(S) = max{2, c(B(GP ))} (see [GHK06, Definition 1.6.1] FACTORIZATION THEORY: FROM COMMUTATIVE TO NONCOMMUTATIVE SETTINGS 9 or Section 4 for the definition of the catenary degree, and [GHK06, Lemma 3.2.6 and Theorem 3.2.8] or Corollary 7.11 for this result). Adyan semigroups. Since we will have need to introduce many atomic semigroups defined via generators and relations in order to illustrate various points, pathological cases, and obstructions to creating a noncommutative analogue of the commutative theory, and do not desire to expose the reader to the tedious details of checking whether or not the semigroup is indeed cancellative, we recall the notion of Adyan semigroups. Let hX | Ri be a presentation of a semigroup S with a finite set of generators X and finite set of relations R of the form u = v with u and v non-trivial elements in F ∗ (X). The left graph of the presentation is the graph G(V, E) with vertex set V = X and with an edge {a, b} ∈ E if and only if there is a relation u = v in R where a is the left-most letter in u and b is the left-most letter in v. One similarly defines the right graph of the presentation. A semigroup S is said to be Adyan if it has a presentation such that the left and right graphs of the presentation are acyclic; i.e., if they are forests. For the examples of semigroups in this paper that are defined via generators and relations, it can easily be checked that they are Adyan. Thus it is important to note the following result which allows one to easily verify that these examples are indeed cancellative (see also [Rem80, Theorem 4.6] for another proof and a more general result that allows for infinite sets X and R). Proposition 2.9 ([Ady60]). Let S be an Adyan semigroup. Then S embeds into a group and is therefore cancellative. In particular, if R consists of a single relation u = v (which will often be the case in this manuscript), then S is cancellative if the first letters of u and v are distinct, and the last letters of u and v are distinct. 3. Distances and Factorizations In this section we introduce rigorous notions of factorizations and distances between factorizations. We begin by briefly recalling the concepts of factorizations as well as the usual distance from the commutative setting. A more detailed account can be found in [GHK06, Section 1.2]. Let S be a commutative cancellative semigroup. If a ∈ S and a = u1 · · · uk = v1 · · · vl with k, l ∈ N0 and u1 , . . . , uk , v1 , . . . , vl ∈ A(S) are two representations of a as products of atoms, then one considers these representations to be the same factorization if k = l and there exists a permutation σ ∈ Sk such that ui ' vσ(i) for all i ∈ [1, k]. A fully rigorous notion of factorizations is obtained as follows: Let Sred be the associated reduced semigroup of S. The factorization monoid of S, denoted by Z(S), is the free abelian monoid F(A(Sred )). There is a canonical homomorphism π : Z(S) → Sred mapping a formal product Qk u1 · · · uk in Z(S) to the product i=1 ui in Sred . For a ∈ S, the set Z(a) = ZS (a) = π −1 (aS × ) is the set of factorizations of a. If X is a set and F = F(X) is the free abelian monoid on X, there is a natural notion of a distance function dF : F × F → N0 , defined as follows: If x, y ∈ F , we may write x and y as x = u1 · · · uk v1 · · · vm and y = u1 · · · uk w1 · · · wn with k, m, n ∈ N0 and u1 , . . . , uk , v1 , . . . , vm , w1 , . . . , wn ∈ X such that {v1 , . . . , vm } ∩ {w1 , . . . , wn } = ∅. We then set dF (x, y) = max{m, n}. This is a metric on F having the additional property that it is invariant under translations, that is, dF (xz, yz) = dF (x, y) for all x, y, z ∈ F . Moreover |z| − |z| ≤ dF (z, z 0 ) ≤ max{|z|, |z 0 |} for all z, z 0 ∈ Z(S). Since Z(S) is simply the free abelian monoid on A(Sred ), in this way a notion of a distance between factorizations is obtained. It is this distance function that has been a central tool in the investigation of non-unique factorizations in the commutative setting. For instance, the catenary degree c(S) and the tame degree t(S) are defined in terms of dZ(S) . For a cancellative small category H we cannot directly imitate the approach to defining factorizations that is used in the commutative setting (taking the path category instead of the free abelian monoid) because associativity may not be a congruence relation on H. Instead we shall take the path category on A(H), and afterwards impose a congruence relation to deal with the potential presence of units. This gives rise to the notion of a rigid factorization in cancellative small categories. In the commutative setting, rigid factorizations differ from the usual notion in the commutative sense in that the order of factors matters. In general, there does not seem to be an entirely natural choice of distance between rigid factorizations that also coincides with the usual distance for factorizations in the commutative case. Therefore we introduce an axiomatic notion of a distance. Each distance d gives rise to the notion of d-factorizations, possibly 10 N. BAETH AND D. SMERTNIG coarser than that of rigid factorizations. On the other hand, different distances may give rise to the same notion of a factorization. We focus on what appear to be two reasonably defined distances: The first of these notions, the permutable distance dp , allows for permutations of irreducible factors of an element, and hence gives rise to the notion of permutable factorizations of an element. In a commutative semigroup, dp coincides with the usual distance defined between any two factorizations of an element. The second notion, the rigid distance, instead corresponds more naturally to the notion of rigid factorizations, and hence does not coincide with the usual distance in the commutative setting. In addition, for the semigroup of non zero-divisors of a ring, we shall also introduce distances based on similarity and subsimilarity of atoms, denoted by dsim and dsubsim . For the semigroup of non zero-divisors of a commutative ring, these also coincide with the usual distance of the commutative setting, and have an advantage over the permutable distance in that they correctly reflect the structure of noncommutative rings in the sense that PIDs are dsim - and dsubsim -factorial, while they are not necessarily permutably factorial. We also show that the coarsest possible distance, d|.| , is based on lengths alone, and that a factorization in that distance corresponds to a length, whence sets of lengths naturally reappear as sets of factorizations in this coarse distance. Throughout this section, let H be a cancellative small category. We now recall the notion of a rigid factorization as defined in [Sme13, Section 3]. Let F ∗ (A(H)) denote the path category on the quiver of atoms of H. We define H × ×r F ∗ (A(H)) = { (ε, y) ∈ H × × F ∗ (A(H)) : t(ε) = s(y) }, and define an associative partial operation on H × ×r F ∗ (A(H)) as follows: If (ε, y), (ε0 , y 0 ) ∈ H × ×r F ∗ (A(H)) with ε, ε0 ∈ H × , y = (e, u1 , . . . , uk , f ) ∈ F ∗ (A(H)) and y 0 = (e0 , v1 , . . . , vl , f 0 ) ∈ F ∗ (A(H)), then the operation is defined if t(y) = s(ε0 ), and (ε, y) · (ε0 , y 0 ) = (ε, (e, u1 , . . . , uk ε0 , v1 , . . . , vl , f 0 )) 0 0 0 0 × if k > 0, ∗ while (ε, y) · (ε , y ) = (εε , y ) if k = 0. In this way, H ×r F (A(H)) is again a cancellative small category (with identities { (e, (e, e)) : e ∈ H0 } that we identify with H0 , so that s(ε, y) = s(ε) and t(ε, y) = t(y)). We define a congruence relation ∼ on H × ×r F ∗ (A(H)) as follows: If (ε, y), (ε0 , y 0 ) ∈ H × ×r F ∗ (A(H)) with y, y 0 as before, then (ε, y) ∼ (ε0 , y 0 ) if k = l, εu1 · · · uk = ε0 v1 · · · vl ∈ H and either k = 0 or there exist δ2 , . . . , δk ∈ H × and δk+1 = t(uk ) such that ε0 v1 = εu1 δ2−1 −1 and vi = δi ui δi+1 for all i ∈ [2, k]. Definition 3.1. The category of rigid factorizations of H is defined as Z∗ (H) = H × ×r F ∗ (A(H)) / ∼ . For z ∈ Z∗ (H) with z = [(ε, (e, u1 , . . . , uk , f ))]∼ , we write z = εu1 ∗ · · · ∗ uk and denote the partial operation on Z∗ (H) also by ∗. The length of the rigid factorization z is |z| = k and there is a homomorphism π = πH : Z∗ (H) → H, induced by multiplication in H, explicitly π(z) = εu1 · · · uk ∈ H. For a ∈ H, we define Z∗ (a) = Z∗H (a) = π −1 ({a}) to be the set of rigid factorization of a. Factoring out by the relation ∼ is motivated by the fact that if e ∈ H0 and u, v ∈ A(H) with t(u) = e = s(v), and ε ∈ H × is such that t(ε) = e, then we always have uv = (uε−1 )(εv), but we do not wish to consider these to be distinct factorizations of uv. Working with H × ×r F ∗ (A(H)) instead of F ∗ (A(H)) ensures that, despite factoring out by ∼, every unit of H has a rigid factorization (of length 0). Hence the homomorphism π : Z∗ (H) → H is surjective if and only if H is atomic. In this way we often avoid having to treat units as special cases. Each atom u ∈ A(H) has a unique rigid factorization, as does each unit of H. Moreover, it is easy to see that these unique rigid factorizations of atoms and units of S are precisely the atoms and units of Z∗ (H), and thus we have bijections π |A(Z∗ (H)) : A(Z∗ (H)) → A(H) and π |Z∗ (H)× : Z∗ (H)× → H × . In particular, H × embeds into Z∗ (H) as a subcategory by means of ε 7→ ε = [(ε, (t(ε), t(ε)))]∼ . Thus we may view A(H) and H × as subsets of Z∗ (H). One can verify, directly from the definition of Z∗ (H), that if x, y, x0 , y 0 ∈ Z∗ (H) with x ∗ y = x0 ∗ y 0 and |x| = |x0 |, then there exists ε ∈ H × such that x0 = x ∗ ε−1 and y 0 = ε ∗ y. Thus any representation of a rigid factorization as a product of other rigid factorization is, up to trivial insertions of units, uniquely FACTORIZATION THEORY: FROM COMMUTATIVE TO NONCOMMUTATIVE SETTINGS 11 determined by the lengths of the factors. Below, we will define the notion of rigid factoriality, and by the property just stated, Z∗ (H) will turn out to be rigidly factorial. If H is reduced, then we simply have Z∗ (H) ∼ = F ∗ (A(H)), and in this case we identify these two objects. In particular, if S is a commutative reduced cancellative semigroup, then Z∗ (S) is the free monoid on A(S), while the usual factorization monoid from the commutative setting is the free abelian monoid on A(S). Thus rigid factorizations differ from the usual ones in that the order of atoms matters for rigid factorizations. We shall sometimes write something akin to “Let z = εu1 ∗ · · · ∗ uk ∈ Z∗H (a) be a rigid factorization . . . ”, and we will tacitly assume that we are implicitly choosing k ∈ N0 , ε ∈ H × , and u1 , . . . , uk ∈ A(H) representing the given factorization. With rigid factorizations defined, we are now able to introduce distances between them. Definition 3.2. A global distance on H is a map d : Z∗ (H)×Z∗ (H) → N0 satisfying the following properties. d(z, z) = 0 for all z ∈ Z∗ (H). d(z, z 0 ) = d(z 0 , z) for all z, z 0 ∈ Z∗ (H). d(z, z 0 ) ≤ d(z, z 00 ) + d(z 00 , z 0 ) for all z, z 0 , z 00 ∈ Z∗ (H). For all z, z 0 ∈ Z∗ (H) with s(z) = s(z 0 ) and x ∈ Z∗ (H) with t(x) = s(z) it holds that d(x∗z, x∗z 0 ) = d(z, z 0 ), and for all z, z 0 ∈ Z∗ (H) with t(z) = t(z 0 ) and y ∈ Z∗ (H) with s(y) = t(z) it holds that 0 d(z z 0 ). ∗ y, z0 ∗ y) = d(z, 0 (D5) |z| − |z | ≤ d(z, z ) ≤ max |z|, |z 0 |, 1 for all z, z 0 ∈ Z∗ (H). (D1) (D2) (D3) (D4) Let L = { (z, z 0 ) ∈ Z∗ (H) × Z∗ (H) : π(z) = π(z 0 ) }. A distance on H is a map d : L → N0 satisfying properties (D1) to (D5) under the additional restrictions on z, z 0 and z 00 that π(z) = π(z 0 ) = π(z 00 ). A distance is only defined between two rigid factorizations z and z 0 of a fixed element, while a global distance is defined between arbitrary rigid factorizations. If d is a global distance, then d|L is a distance and we simply write d = d|L . The concept of a distance suffices to introduce d-factorizations and to study catenary degrees. Distances have an advantage over global distances in that they can be extended to the category of principal ideals (see Proposition 7.9). While the particular distances we introduce will generally be global distances, our abstract results will always be stated for distances, the only exception being Lemma 3.7(3), where it is necessary to assume that the given distance is a global distance. The description of ≡p after Definition 6.5 by means of the permutable distance makes use of the fact that the permutable distance is a global distance. Let z, z 0 ∈ Z∗ (H). If |z| = |z 0 | = 0 then z = ε and z 0 = η with ε, η ∈ H × . If, in addition, π(z) = π(z 0 ), then ε = η and hence z = z 0 . In this case, (D5) together with (D1) implies d(z, z 0 ) ≤ max{|z|, |z 0 |}. For a distance, the upper bound in (D5) is therefore equivalently to d(z, z 0 ) ≤ max{|z|, |z 0 |}. In the literature a great number of distances between words in a free monoid have been introduced, see for example [DD13, Chapter 11]. Modifying these to account for the potential presence of units, they prove to be a rich source of possible interesting distances to study on H. We now introduce two general constructions for global distances in the present context. Construction 3.3. (1) Let Ω be a non-empty set of symmetric relations on Z∗ (H) × Z∗ (H), and for each R ∈ Ω let cR ∈ N0 denote its cost, subject to the condition that cR ≥ |z| − |z 0 | for all z, z 0 ∈ Z∗ (H) with zRz 0 . We call R ∈ Ω an edit operation. Let z, z 0 ∈ Z∗ (H). An edit sequence from z to z 0 consists of a finite sequence of relations R1 , . . . , Rm ∈ Ω (repetition is allowed) and factorizations z = z0 , z1 , . . . , zm−1 , zm = z 0 ∈ Z∗ (H) such that zi−1 Ri zi for all i ∈ [1, m]. (Note that the intermediate factorizations may have different products, and even s(zi ) 6= s(zi−1 ) and t(zi ) 6= t(zi−1 ) is permitted.) The cost of the sequence is cR1 + · · · + cRm , and the length of the sequence is m ∈ N0 . We set d(z, z 0 ) ∈ N0 ∪{∞} to be the minimal cost of an edit sequence from z to z 0 . If d(z, z 0 ) < ∞ for all z, z 0 ∈ Z∗ (H) (that is, for any two z, z 0 ∈ Z∗ (H) there exists an edit sequence from z to z 0 ), then d : L → N0 satisfies properties (D1) to (D3). Moreover, d satisfies one inequality of (D5): For any edit sequence of minimal length, m m m X X X 0 d(z, z ) = cRi ≥ |zi | − |zi−1 | ≥ |zi | − |zi−1 | = |z| − |z 0 |. i=1 i=1 i=1 To establish that d is a global distance, it remains to check (D4) and the remaining inequality from (D5). We will use this construction to introduce the rigid distance in Definition 3.4. 12 N. BAETH AND D. SMERTNIG (2) Let ∼ be an equivalence relation on the set of atoms A(H) of H such that, for all u, v ∈ A(H), u ' v implies u ∼ v. We denote by [u]∼ the ∼-equivalence class of u ∈ A(H), and by F = F(A(S)/ ∼) the free abelian monoid on the equivalence classes of A(H) under the equivalence relation ∼. Then there exists a homomorphism ϕ : Z∗ (H) → F such that ϕ(z) = [u1 ]∼ · · · [uk ]∼ for all z = εu1 ∗ · · · ∗ uk ∈ Z∗ (H) with k ∈ N0 , ε ∈ H × , and u1 , . . . , uk ∈ A(H). Let dF : F × F → N0 denote the usual distance on the free abelian monoid F . We obtain a global distance d on H by setting d(z, z 0 ) = dF (ϕ(z), ϕ(z 0 )) for all z, z 0 ∈ Z∗ (H). Thus, if z = εu1 ∗ · · · ∗ uk , z 0 = ηv1 ∗ · · · ∗ vl ∈ Z∗ (H), we compare the sequences of ∼-equivalence classes of u1 , . . . , uk and v1 , . . . , vl up to permutation. Explicitly, there exists a (uniquely determined) n ∈ [0, min{k, l}], subsets I ⊂ [1, k] and J ⊂ [1, l] of cardinality |I| = |J| = n, and a bijection σ : I → J such that ui ∼ vσ(i) for all i ∈ [1, n], while ui 6∼ uj for all i ∈ [1, k] \ I and j ∈ [1, l] \ J. Then d(z, z 0 ) = max{k − n, l − n}. The permutable distance, as well as the similarity and subsimilarity distances, introduced in the following definition, will be constructed in this way. Using these constructions, we now introduce the (global) distances we will focus on. Definition 3.4. (1) In the rigid distance, denoted by d∗ , we allow the replacement of m ∈ N0 consecutive atoms by n ∈ N0 new ones at cost max{m, n, 1}. Explicitly, for all m, n ∈ N0 we define an edit operation Rm,n as follows: If z, z 0 ∈ Z∗ (H), then zRm,n z 0 if and only if there exist x, y, z0 , z00 ∈ Z∗ (H) such that {|z0 |, |z00 |} = {m, n} and one of z = x ∗ z0 ∗ y and z 0 = x ∗ z00 ∗ y, z = z0 ∗ y and z 0 = z00 ∗ y, z = x ∗ z0 and z 0 = x ∗ z00 , z = z0 and 0 z = or z00 holds. We set the cost of Rm,n to be max{m, n, 1} and set Ω = { Rm,n : m, n ∈ N0 }. ∗ The rigid distance d is the distance defined by these edit operations, as described in Construction 3.3(1). (We verify in Lemma 3.6 below that d∗ is a global distance.) (2) The permutable distance, denoted by dp , is defined by means of Construction 3.3(2) by setting ∼ = '. (3) Let R be a ring and S = R• the cancellative semigroup of non zero-divisors of R. Two elements a, a0 ∈ R are similar if R/Ra ∼ = R/Ra0 as left R-modules, and they are subsimilar if there exist monomorphisms R/Ra ,→ R/Ra0 and R/Ra0 ,→ R/Ra. These are equivalence relations on S. If a ' a0 , then a and a0 are similar, and hence subsimilar. Using Construction 3.3(2), similarity therefore gives rise to the similarity distance, denoted by dsim , and subsimilarity gives rise to the subsimilarity distance, denoted by dsubsim . Remark 3.5. (1) If S is a commutative reduced cancellative semigroup, then dp coincides with the usual distance. To differentiate it from a generic distance we will always write dp for the usual distance in the commutative setting. (2) The rigid distance is derived from the editing (or Levenshtein) distance on a free monoid: There, one permits the insertion, deletion and replacement of a single letter in a word at cost 1. The variation from the definition for a free monoid accounts for the nature of the partial operation, in which a one-by-one deletion and insertion of atoms may not be possible, as well as the presence of units. If z, z 0 ∈ Z∗ (H) with d∗ (z, z 0 ) = 0, then z = z 0 since all edit operations have cost at least 1. Thus the rigid distance is sufficiently fine to be able to distinguish between two distinct rigid factorizations. The definition of the edit operations Rm,n seems repetitive. However, since it is possible that s(z) 6= s(z 0 ) or t(z) 6= t(z 0 ), one cannot assume that all the listed cases are special cases of z = x ∗ z0 ∗ y and z 0 = x ∗ z00 ∗ y. It may seem natural to set the cost of Rm,n to max{m, n} instead of max{m, n, 1}. However, it would then be permitted to insert or remove units in arbitrary places at cost 0. It would then be possible to have d∗ (z, z 0 ) = 0 for two distinct factorizations z, z 0 ∈ Z∗ (H), even if π(z) = π(z 0 ). FACTORIZATION THEORY: FROM COMMUTATIVE TO NONCOMMUTATIVE SETTINGS 13 Indeed, consider S = ha, ε | ε2 = 1, εa2 = a2 εi. We first check that S is cancellative. Since the right hand side of the relation ε2 = 1 is trivial, we cannot employ Adyan’s result. However, by mapping 0 1 0 2 ε 7→ and a 7→ , 1 0 1 0 we obtain a homomorphism S → M2 (Z)• . Using the fact that every element of S affords a representation of the form a2m+r (εa)n εs with m, n ∈ N0 and r, s ∈ {0, 1}, one can check directly that this homomorphism is injective. Therefore S can be realized as a subsemigroup of M2 (Z)• and is cancellative. Now note that z = εa ∗ aε and z 0 = a ∗ a are distinct rigid factorizations of a2 . Indeed, suppose otherwise. Then there exists η ∈ S × such that εa = aη. However, S × = {1, ε}, and thus z and z 0 are distinct. However, (a ∗ a)R0,0 (εa ∗ a), and (εa ∗ a)R0,0 (εa ∗ aε) would give an edit sequence of cost 0. (3) In [Coh85, Chapter 3], P. M. Cohn uses the notion of similarity to define a concept of unique factorization in noncommutative rings. Similarly, in [Bru69], the slightly weaker notion of subsimilarity is used to introduce such a concept. If z, z 0 ∈ Z∗ (H) with π(z) = π(z 0 ), then dsim (z, z 0 ) = 0 if and only if z and z 0 are the same factorization in the sense of P. M. Cohn, and similarly dsubsim (z, z 0 ) = 0 if and only if z and z 0 are the same factorization in the sense of Brungs. There is also a purely multiplicative characterization of subsimilarity (see [Bru69, Lemma 2], but note that Brungs assumes that R is a domain): Two elements a, a0 are subsimilar if and only if there exist elements c, c0 ∈ R such that Ra ∩ Rc0 = Ra0 c0 and Ra0 ∩ Rc = Rac, with c and c0 satisfying the additional property that, for all r ∈ R, rc ∈ Rac implies r ∈ Ra and rc0 ∈ Ra0 c0 implies r ∈ Ra0 (this is a weak form of cancellativity for c and c0 ). If R is commutative, then the notions of subsimilarity and similarity coincide with associativity, and hence both of these distances coincide with the usual one in R: If a, a0 ∈ R• are subsimilar, then Ra = annR (R/Ra) = annR (R/Ra0 ) = Ra0 , and hence a ' a0 . The first part of the following lemma shows that any edit sequence consisting of the edit operations which define the rigid distance can be transformed into an edit sequence of equal or lower cost which consists of pairwise disjoint replacements (the idea is related to the use of traces in studying the Levenshtein distance in a free monoid, see [WF74]). The details of the proof are somewhat technical, but essentially, given any edit sequence, we can merge two subsequent overlapping edit operations into a single edit operation whose cost does not exceed the combined cost of the two operations. We then use this characterization to establish that the rigid distance is a global distance. Lemma 3.6. (1) Let z, z 0 ∈ Z∗ (H) and let N ∈ N0 . Then d∗ (z, z 0 ) ≤ N if and only if there exist n ∈ N, x1 , . . . , xn−1 ∈ Z∗ (H) and y1 , y10 , . . . , yn , yn0 ∈ Z∗ (H) such that z = y1 ∗ x1 ∗ y2 ∗ · · · ∗ yn−1 ∗ xn−1 ∗ yn and 0 z 0 = y10 ∗ x1 ∗ y20 ∗ · · · ∗ yn−1 ∗ xn−1 ∗ yn0 P with i∈I max{|yi |, |yi0 |, 1} ≤ N where I = { i ∈ [1, n] : yi 6= s(yi ) or yi0 6= s(yi0 ) }. (2) In the representation in (1) we can, in addition, assume that either (i) for all i ∈ [2, n] the suffixes yi ∗ xi ∗ · · · ∗ xn−1 ∗ yn of z and yi0 ∗ xi ∗ · · · ∗ xn−1 ∗ yn0 of z 0 are left coprime, or (ii) for all i ∈ [1, n − 1] the prefixes y1 ∗ x1 ∗ · · · ∗ xi−1 ∗ yi of z and y10 ∗ x1 ∗ · · · ∗ xi−1 ∗ yi0 of z 0 are right coprime. (3) Let z, z 0 ∈ Z∗ (H) and let x, y ∈ Z∗ (H). If t(x) = s(z) = s(z 0 ), then d∗ (x ∗ z, x ∗ z 0 ) = d∗ (z, z 0 ), and if s(y) = t(z) = t(z 0 ), then d∗ (z ∗ y, z 0 ∗ y) = d∗ (z, z 0 ). (4) The rigid distance d∗ is a global distance on H. Proof. For k, l ∈ N0 , let Rk,l denote the edit operations from Definition 3.4(1), and let Ω denote the set consisting of all such edit operations. We recall: If x, y, x0 , y 0 ∈ Z∗ (H) with x ∗ y = x0 ∗ y 0 and |x| = |x0 |, then there exists ε ∈ H × such that x0 = x ∗ ε−1 and y 0 = ε ∗ y. We will make use of this property throughout the proof. (1) Suppose first that z and z 0 are of the described form. Then we can clearly construct an edit sequence from z to z 0 in the operations from Ω and of cost at most N : We successively replace yi by yi0 for all i ∈ I with cost at most max{|yi |, |yi0 |, 1}. Thus d∗ (z, z 0 ) ≤ N . 14 N. BAETH AND D. SMERTNIG For the converse, suppose that d∗ (z, z 0 ) ≤ N . Fix an edit sequence from z to z 0 with cost at most N and with length m ∈ N0 . For each P i ∈ [1, m], let Ri ∈ Ω and let z = z0 , . . . , zm = z 0 ∈ Z∗ (H) be such m that zi−1 Ri zi for all i ∈ [1, m] and i=1 cRi ≤ N . We proceed by induction on the length m of the edit 0 sequence. If m = 0, then z = z and we simply set n = 2, x1 = z, y1 = y10 = s(z) and y2 = y20 = t(z). Now suppose that m ≥ 1 and that the claim holds for sequences of length m − 1. Note that N ≥ 1, since all edit operations in Ω have cost at least 1. Since z = z0 , . . . , zm−1 is a sequence from z to zm−1 of length m − 1, the induction hypothesis implies that there exist r ∈ N, x̂1 , . . . , x̂r−1 ∈ Z∗ (H) and ŷ1 , ŷ10 , . . . , ŷr , ŷr0 ∈ Z∗ (H) such that z = ŷ1 ∗ x̂1 ∗ ŷ2 ∗ · · · ∗ ŷr−1 ∗ x̂r−1 ∗ ŷr , (3.1) 0 zm−1 = ŷ10 ∗ x̂1 ∗ ŷ20 ∗ · · · ∗ ŷr−1 ∗ x̂r−1 ∗ ŷr0 , P and i∈Iˆ max{|ŷi |, |ŷi0 |, 1} ≤ N − cRm where Iˆ = { i ∈ [1, r] : ŷi 6= s(ŷi ) or ŷi0 6= s(ŷi0 ) }. Since zm−1 Rm z 0 , there exist x̂, ŷ, ẑ, ẑ 0 ∈ Z∗ (H) with max{|ẑ|, |ẑ 0 |, 1} = cRm and such that one of the following holds: zm−1 = x̂ ∗ ẑ ∗ ŷ and z 0 = x̂ ∗ ẑ 0 ∗ ŷ, zm−1 = ẑ ∗ ŷ and z 0 = ẑ 0 ∗ ŷ, zm−1 = x̂ ∗ ẑ and z 0 = x̂ ∗ ẑ 0 , zm−1 = ẑ 0 and or 0 z = ẑ . We first consider the case where zm−1 = x̂ ∗ ẑ ∗ ŷ and z 0 = x̂ ∗ ẑ 0 ∗ ŷ. The other cases will be analogous to special cases of this one. To simplify the notation in what follows, for i, j ∈ [0, r], we set 0 Pi = s(ŷ10 ) ∗ ŷ10 ∗ x̂1 ∗ ŷ20 ∗ · · · ∗ ŷi−1 ∗ x̂i−1 ∗ ŷi0 Sj = 0 ŷj+1 ∗ x̂j+1 ∗ 0 ŷj+2 ∗ ··· ∗ 0 ŷr−1 ∗ x̂r−1 ∗ ŷr0 and ∗ t(ŷr0 ). 0 These are the prefixes of zm−1 ending in ŷi0 , respectively the suffixes of zm−1 starting with ŷj+1 , for 0 0 i, j ∈ [0, r]. Note that P0 = s(ŷ1 ) and Sr = t(ŷr ) are empty products. Let k ∈ [0, r] be maximal and l ∈ [k, r] be minimal such that |Pk | ≤ |x̂| and |Sl | ≤ |ŷ|. We first deal with some extremal cases. If k = 0 and l = r, then we set n = 1, y1 = z and y10 = z 0 . Then X |z 0 | = |x̂| + |ŷ| + |ẑ 0 | ≤ |ŷi0 | + cRm and i∈{1,r} |z| = r−1 X r X i=1 i=1 |x̂i | + |ŷi | ≤ cRm + X max{|ŷi |, |ŷi0 |}, i∈Iˆ and thus max{|z|, |z 0 |, 1} ≤ N . If k = 0 and l < r, then, by enlarging ẑ and ẑ 0 if necessary by at most |ŷl0 | elements, we may assume |Sl | ≤ |ŷ| ≤ |x̂l ∗ Sl |. Then there exist x1 , y1,1 ∈ Z∗ (H) such that x̂l = y1,1 ∗ x1 and ŷ = x1 ∗ Sl . Setting y1 = ŷ1 ∗ x̂1 ∗ · · · ∗ x̂l−1 ∗ ŷl ∗ y1,1 and y10 = x̂ ∗ ẑ 0 , we have z = y1 ∗ x1 ∗ ŷl+1 ∗ x̂l+1 ∗ · · · ∗ x̂r−1 ∗ ŷr 0 z = y10 ∗ x1 ∗ 0 ŷl+1 ∗ x̂l+1 ∗ · · · ∗ x̂r−1 ∗ and ŷr0 . 0 We set n = r − l + 1, yi = ŷi+l−1 and yi0 = ŷi+l−1 for all i ∈ [2, n], and xi = x̂i+l−1 for all i ∈ [2, n − 1]. Then |y1 | = l−1 X i=1 |x̂i | + |y1,1 | + l X |ŷi | ≤ cRm + i=1 X max{|ŷi |, |ŷi0 |} and ˆ i∈I∩[1,l] |y10 | = |x̂| + |ẑ 0 | ≤ |ŷ10 | + cRm + |ŷl0 |. P Thus max{|y1 |, |y10 |, 1} ≤ N − i∈I∩[l+1,r] max{|ŷi |, |ŷi0 |, 1}. ˆ The case k > 0 and l = r is analogous to the previous case. We can assume from now on that k, l ∈ [1, r − 1]. Suppose first that k = l. Comparing the following two representations of zm−1 : 0 zm−1 = x̂ ∗ ẑ ∗ ŷ = ŷ10 ∗ x̂1 ∗ ŷ20 ∗ · · · ∗ ŷr−1 ∗ x̂r−1 ∗ ŷr0 , FACTORIZATION THEORY: FROM COMMUTATIVE TO NONCOMMUTATIVE SETTINGS 15 it follows that there exist xk , xk+1 ∈ Z∗ (H) such that x̂k = xk ∗ ẑ ∗ xk+1 , x̂ = Pk ∗ xk , and ŷ = xk+1 ∗ Sk . Then z = ŷ1 ∗ · · · ∗ ŷk ∗ xk ∗ ẑ ∗ xk+1 ∗ ŷk+1 ∗ · · · ∗ ŷr 0 ŷ10 z = ŷk0 ∗ ··· ∗ 0 yk+1 0 ∗ xk ∗ ẑ ∗ xk+1 ∗ 0 ŷk+1 ∗ ··· ∗ and ŷr0 . 0 Setting n = r + 1, yk+1 = ẑ, = ẑ , xi = x̂i for all i ∈ [1, k − 1], yi = ŷi and yi0 = ŷi0 for all i ∈ [1, k], 0 xi = x̂i−1 for all i ∈ [k + 2, r], and yi = ŷi−1 and yi0 = ŷi−1 for all i ∈ [k + 2, r + 1], the claim follows since 0 max{|ẑ|, |ẑ |, 1} ≤ cRm . 0 Now suppose that k < l with k, l ∈ [1, r − 1]. Enlarging ẑ and ẑ 0 if necessary by at most |ŷk+1 | + |ŷl0 | 0 elements if k + 1 < l, respectively by at most |ŷl | elements if k + 1 = l, we may further assume |Pk | ≤ |x̂| ≤ |Pk ∗ x̂k | and |Sl | ≤ |ŷ| ≤ |x̂l ∗ Sl |. ∗ Then there exist xk , xk+1 , yk+1,1 , yk+1,2 ∈ Z (H) such that x̂k = xk ∗yk+1,1 , x̂l = yk+1,2 ∗xk+1 , x̂ = Pk ∗xk , 0 ŷ = xk+1 ∗ Sl , and ẑ = yk+1,1 ∗ ŷk+1 ∗ x̂k+1 ∗ · · · ∗ x̂l−1 ∗ ŷl0 ∗ yk+1,2 . Thus z = ŷ1 ∗ · · · ∗ ŷk ∗ xk ∗ ẑ ∗ xk+1 ∗ ŷl+1 ∗ · · · ∗ ŷr 0 z = ŷ10 ŷk0 ∗ ··· ∗ 0 ∗ xk ∗ ẑ ∗ xk+1 ∗ 0 yk+1 0 ŷl+1 ∗ ··· ∗ and ŷr0 . 0 We set n = r − l + k + 1, yk+1 = ẑ, = ẑ , xi = x̂i for all i ∈ [1, k − 1], yi = ŷi and yi0 = ŷi0 for all 0 i ∈ [1, k], xi = x̂i−k+l−1 for all i ∈ [k + 2, n − 1], and yi = ŷi−k+l−1 and yi0 = ŷi−k+l−1 for all i ∈ [k + 2, n]. 0 0 0 If k + 1 = l, then max{|ẑ|, |ẑ |, 1} ≤ cRm + |ŷl |, and if k + 1 < l, then max{|ẑ|, |ẑ 0 |, 1} ≤ cRm + |ŷk+1 | + |ŷl0 |. 0 0 Thus, in any case, with I = { i ∈ [1, n] : yi 6= s(yi ) or yi 6= s(yi ) } we have X X max{|yi |, |yi0 |, 1} ≤ max{|ŷi |, |ŷi0 |, 1} + cRm . i∈I i∈Iˆ Hence the claim is verified in the case where zm−1 = x̂ ∗ ẑ ∗ ŷ and z 0 = x̂ ∗ ẑ 0 ∗ ŷ. If zm−1 = ẑ ∗ ŷ and z 0 = ẑ 0 ∗ ŷ, then the proof is similar to the case k = 0 above, noting that it is possible that s(ẑ) 6= s(ẑ 0 ) and hence this case is not strictly a special case where x = t(x). If zm−1 = x̂ ∗ ẑ and z 0 = x̂ ∗ ẑ 0 , then the proof is similar to the case l = r above. If zm−1 = ẑ and z 0 = ẑ 0 , then the proof is similar to the case k = 0 and l = r. (2) We show that the suffixes can be chosen to be left coprime. The basic idea here is that a common left factor of a suffix may be moved into the xi preceding the suffix. Let i ∈ [2, n]. Suppose that yi ∗ xi ∗ · · · ∗ xn−1 ∗ yn = a ∗ b and yi0 ∗ xi ∗ · · · ∗ xn−1 ∗ yn0 = a ∗ c for some a, b, c ∈ Z∗ (H). We may assume 0 0 that |a| is maximal. Then there exist k, l ∈ [i, n] and yk,1 , yk,2 , yl,1 , yl,2 ∈ Z∗ (H) such that yk = yk,1 ∗ yk,2 , 0 0 0 yl = yl,1 ∗ yl,2 , yi ∗ xi ∗ yi+1 ∗ · · · ∗ yk−1 ∗ xk−1 ∗ yk,1 = a, and (3.2) 0 0 0 yi0 ∗ xi ∗ yi+1 ∗ · · · ∗ yl−1 ∗ xl−1 ∗ yl,1 = a. By swapping the roles of z and z 0 if necessary, we may, without restriction, assume k ≤ l. We set x̂i−1 = xi−1 ∗ a, 0 ŷi0 = yl,2 , ŷi = yk,2 ∗ xk ∗ yk+1 ∗ · · · ∗ xl−1 ∗ yl , and x̂j = t(ŷi ) for all j ∈ [i, l − 1] as well as ŷj0 = ŷj = t(ŷi ) for all j ∈ [i + 1, l]. Then, comparing lengths in Equation (3.2), l−1 k−1 l−1 X X X 0 |xj | = |yi | + |yk,1 | − |yj0 | − |yl,1 |, j=i j=k j=i and thus |ŷi | = l−1 X |xj | + j=k l X |yj | + |yk,2 | = j=k+1 l l−1 l X X X 0 |yi | − |yj0 | − |yl,1 |≤ |yi |. j=i j=i j=i Clearly |ŷi0 | ≤ |yl0 |. If I ∩ [i, l] 6= ∅, then max{|ŷi |, |ŷi0 |, 1} ≤ X max{|yj |, |yj0 |, 1}. j∈I∩[i,l] yj0 0 Otherwise, yj = s(yj ) = for all j ∈ [i, l]. Then Equation (3.2) implies k = l and also yk,1 = yl,1 . 0 0 Modifying a by a unit if necessary, we may take yk,1 = yl,1 = t(a), and hence also yk,2 = yl,2 = t(a). Thus ŷi0 = ŷi = s(ŷi ) is trivial. Note that we only need to modify the representation to the right of yi−1 . Thus, working our way from left to right, we may ensure that the suffixes are left coprime. 16 N. BAETH AND D. SMERTNIG (3) We show d∗ (x ∗ z, x ∗ z 0 ) = d∗ (z, z 0 ), and begin by showing d∗ (x ∗ z, x ∗ z 0 ) ≤ d∗ (z, z 0 ). Suppose N = d∗ (z, z 0 ) and take a representation of z and z 0 as in (1). Since s(z) = s(z 0 ), we have s(y1 ) = s(y10 ). Thus we may multiply both representations by x from the left. Again by (1), this implies d∗ (x ∗ z, x ∗ z 0 ) ≤ N . We now show d∗ (x ∗ z, x ∗ z 0 ) ≥ d∗ (z, z 0 ). Let N = d∗ (x ∗ z, x ∗ z 0 ). By (1), there exist n ∈ N, x1 , . . . , xn−1 ∈ Z∗ (H) and y1 , y10 , . . . , yn , yn0 ∈ Z∗ (H) such that x ∗ z = y1 ∗ x1 ∗ y2 ∗ · · · ∗ xn−1 ∗ yn 0 x∗z = y10 ∗ x1 ∗ y20 ∗ · · · ∗ xn−1 ∗ and yn0 with i∈I max{|yi |, |yi0 |, 1} ≤ N where I = { i ∈ [1, n] : yi = 6 s(yi ) or yi0 6= s(yi0 ) }. By (2) we may further 0 assume that y2 ∗ x2 ∗ · · · ∗ xn−1 ∗ yn and y2 ∗ x2 ∗ · · · ∗ xn−1 ∗ yn0 are left coprime. If y1 = y10 = s(y1 ), then x1 = x ∗ x̂0 with x̂0 ∈ Z∗ (H). Cancelling x on the left, we obtain representations of z and z 0 as in (1), and conclude d∗ (z, z 0 ) ≤ d∗ (x ∗ z, x ∗ z 0 ). Now suppose that y1 or y10 is non-trivial. Due to the coprimality condition, we must have y1 ∗ x1 = x ∗ a and y10 ∗ x1 = x ∗ b with a, b ∈ Z∗ (H). Let a = ŷ1 ∗ x̂1 and b = ŷ10 ∗ x̂1 with ŷ1 , ŷ10 , x̂1 ∈ Z∗ (H) and |x̂1 | chosen to be maximal. Since y1 ∗ x1 and y10 ∗ x1 have common right divisor x1 , we have at least |x̂1 | ≥ |x1 | − (|x| − min{|y1 |, |y10 |}). Thus P |ŷ1 | = |y1 | + |x1 | − |x| − |x̂1 | ≤ |y1 | − min{|y1 |, |y10 |} ≤ |y1 |, and similarly |ŷ10 | ≤ |y10 |. Therefore max{|ŷ1 |, |ŷ10 |, 1} ≤ max{|y1 |, |y10 |, 1} and, applying (1) to z = ŷ1 ∗ x̂1 ∗ y2 ∗ · · · ∗ xn−1 ∗ yn 0 z = ŷ10 ∗ x̂1 ∗ y20 ∗ · · · ∗ xn−1 ∗ and yn0 , the claim follows. (4) Let z, z 0 ∈ Z∗ (H). By the general properties of the construction, (D1) to (D3), and one inequality from (D5) hold. It remains to show that d∗ (z, z 0 ) ≤ max{|z|, |z 0 |, 1}, and that (D4) holds. We have zR|z|,|z0 | z 0 , and this operation has cost max{|z|, |z 0 |, 1}. Property (D4) follows from (3). If d and d0 are global distances on H with d(z, z 0 ) ≤ d0 (z, z 0 ) for all z, z 0 ∈ Z∗ (H), we shall say that d is finer than d and d is coarser than d0 . If d and d0 are distances on H with d(z, z 0 ) ≤ d0 (z, z 0 ) for all z, z 0 ∈ Z∗ (H) with π(z) = π(z 0 ), we shall say that d0 is finer than d and d is coarser than d0 . We note some basic properties of distances. 0 Lemma 3.7. Let d be a distance on H. (1) For z1 , z2 , z3 , z4 ∈ Z∗ (H) with π(z1 ) = π(z3 ), π(z2 ) = π(z4 ), t(z1 ) = s(z2 ), and t(z3 ) = s(z4 ) we have d(z1 ∗ z2 , z3 ∗ z4 ) ≤ d(z1 , z3 ) + d(z2 , z4 ). (2) The relation ∼d on Z∗ (H), defined by z ∼d z 0 if and only if π(z) = π(z 0 ) and d(z, z 0 ) = 0, is a congruence relation. (3) Any global distance d on H is coarser than d∗ . Proof. (1) From the triangle inequality (D3) we obtain d(z1 ∗z2 , z3 ∗z4 ) ≤ d(z1 ∗z2 , z3 ∗z2 )+d(z3 ∗z2 , z3 ∗z4 ). The translation invariance (D4) implies d(z1 ∗ z2 , z3 ∗ z2 ) = d(z1 , z3 ) and d(z3 ∗ z2 , z3 ∗ z4 ) = d(z2 , z4 ), and therefore we have d(z1 ∗ z2 , z3 ∗ z4 ) ≤ d(z1 , z3 ) + d(z2 , z4 ). (2) It is immediate that ∼d gives reflexive, symmetric and transitive relations on Z∗ (H)(e, f ) for all e, f ∈ H0 . Let z, z 0 , w, w0 ∈ Z∗ (S) with s(z) = s(z 0 ), t(z) = t(z 0 ) = s(w) = s(w0 ), and t(w) = t(w0 ). Moreover assume that π(z) = π(z 0 ), d(z, z 0 ) = 0, π(w) = π(w0 ) and d(w, w0 ) = 0. We must show that z ∗ w ∼d z 0 ∗ w0 . Since π(w) = π(w0 ), π(z) = π(z 0 ) and π is a homomorphism of small categories, we also have π(z ∗ w) = π(z 0 ∗ w0 ). Moreover, by (1), d(z ∗ w, z 0 ∗ w0 ) ≤ d(z, z 0 ) + d(w, w0 ) = 0. (3) Let d be a global distance on H. Let z, z 0 ∈ Z∗ (H) and let N = d∗ (z, z 0 ). By the definition of d∗ , there exist l ∈ N0 , m1 , n1 , . . . , ml , nl ∈ N0 and z = z0 , . . . , zl = z 0 ∈ Z∗ (H) such that zi−1 Rm,n zi for all i ∈ [1, l] and cRm1 ,n1 + · · · + cRml ,nl = N . By the definition of Rmi ,ni and property (D4) of d, we find d(zi−1 , zi ) ≤ cRmi ,ni for all i ∈ [1, l]. From the triangle inequality (D3) we conclude d(z, z 0 ) ≤ N . By application of Lemma 3.7(3), the rigid distance plays a special role in that it is the finest global distance. Note that d|·| (z, z 0 ) = |z| − |z 0 | also defines a global distance on H. By property (D5), we have d|·| (z, z 0 ) ≤ d(z, z 0 ) for any other global distance d, and similarly d|·| (z, z 0 ) ≤ d(z, z 0 ) if π(z) = π(z 0 ) and d is a distance. Thus, d|·| is the coarsest possible (global) distance. If R is a ring, then dp is finer than dsim (since associated elements are similar), and dsim is finer than dsubsim (since similar elements are subsimilar), and all three of these global distances are coarser than d∗ by the previous lemma. It follows from Lemma 3.7 that every distance d gives rise to a notion of factorizations derived from d by identifying rigid factorizations z and z 0 of an element a ∈ H if d(z, z 0 ) = 0. FACTORIZATION THEORY: FROM COMMUTATIVE TO NONCOMMUTATIVE SETTINGS 17 Definition 3.8. Let d be a distance on H and let a ∈ H. (1) We define Zd (H) = Z∗ (H)/ ∼d and Zd (a) to be the image of Z∗ (a) under the canonical homomorphism Z∗ (H) → Zd (H). An element of Zd (a) is called a d-factorization of a and Zd (H) is the category of d-factorizations. We say that H is d-factorial if |Zd (a)| = 1 for all a ∈ H. (2) We set Zp (H) = Zdp (H) and call these factorizations permutable factorizations. Given z ∈ Z∗ (H) we shall write [z]p for its image in Zp (H). If H is dp -factorial, we say instead that H is permutably factorial. Let z, z 0 ∈ Z∗ (H) with π(z) = π(z 0 ). Since d(z, z 0 ) depends only on the classes of z and z 0 in Zd (S), we may think of d as being defined on { (z, z 0 ) ∈ Zd (S) × Zd (S) : π(z) = π(z 0 ) } whenever this is convenient. Since d∗ (z, z 0 ) = 0 if and only if z = z 0 , Zd∗ (H) = Z∗ (H) is just the category of rigid factorizations. If H is d∗ -factorial, we say instead that it is rigidly factorial. Observe that H is d-factorial if and only if the homomorphism Zd (H) → H induced by π : Z∗ (H) → H is an isomorphism. Remark 3.9. Let z, z 0 ∈ Z∗ (H) with π(z) = π(z 0 ). (1) We have d|·| (z, z 0 ) = 0 if and only if |z| = |z 0 |. Thus H is d|·| -factorial if and only if it is half-factorial. (2) We have dp (z, z 0 ) = 0 if and only if |z| = |z 0 | and there exists a permutation of the factors of z such that they are pairwise associated to those of z 0 . If H is a commutative cancellative semigroup, and a ∈ H, then Zp (a) coincides with the usual notion Z(a) of factorizations of a (but Zp (H) ∼ 6 Z(S) if = S is not reduced). (3) If d and d0 are distances on Z(H) with d0 finer than d and H is d0 -factorial, then H is d-factorial. In particular, we have the following: Let R be a ring. If R• is permutably factorial, then it is dsim -factorial. If R• is dsim -factorial, then it is dsubsim -factorial. Finally, if R is commutative, then all three notions coincide, since then dp = dsim = dsubsim . Since we have identified A(H) with A(Z∗ (H)), and since representations of rigid factorizations as products of atoms are unique up to a trivial insertion of units, it follows immediately that Z∗ (H) is rigidly factorial, and thus in particular, Z∗ (Z∗ (H)) ∼ = Z∗ (H). Similarly, for any distance d, the sets A(H) and H × embed into Zd (H), and Zd (H) is atomic with A(Zd (H)) = A(H). The finer a distance d, the more refined the notion of factorizations that can be derived from d. While d∗ turns out to be a very useful tool, it may not always be practical to study such a fine notion as rigid factorizations. For instance, a commutative cancellative semigroup is rigidly factorial if and only if it is factorial and possesses, up to associativity, a unique prime element (that is, it is a discrete valuation monoid). Thus even commutative PIDs are usually not rigidly factorial. However, every path category is rigidly factorial. Nonetheless, rigid factorizations have been studied in the following settings: Generalizing the study of PIDs, the study of 2-firs (see [Coh85, Chapter 3]) and, on an ideal-theoretic level, saturated subcategories of arithmetical groupoids (see [Sme13]). The study of polynomial decompositions, that is, the study of the factorization properties of the noncommutative semigroup (K[X] \ K, ◦) where K is (usually) a field, also concerns itself with what amounts to rigid factorizations (see [ZM08]). The following lemma shows that (weak) transfer homomorphisms induce homomorphisms on the categories of rigid factorizations. We omit the straightforward proof. Lemma 3.10. Let H and T be cancellative small categories. Let φ : H → T be a transfer homomorphism, or let T be atomic and φ : H → T a weak transfer homomorphism. There exists a unique homomorphism φ∗ : Z∗ (H) → Z∗ (T ) satisfying φ∗ (u) = φ(u) φ∗ (ε) = φ(ε) and for all u ∈ A(H) and ε ∈ H × . Moreover, φ∗ induces the following commutative diagram Z∗ (H) φ∗ πH H φ / Z∗ (T ) /T πT [.]p / Zp (T ) T. Let φ : Z∗ (H) → Zp (T ) denote the homomorphism in the top row. (1) If φ is a transfer homomorphism, then Z∗ (T ) = T × φ∗ (Z∗ (H))T × and Zp (T ) = T × φ(Z∗ (H))T × . In particular, for all a ∈ H, the induced maps Z∗ (a) → Z∗ (φ(a)) and Zp (a) → Zp (φ(a)) are surjective. 18 N. BAETH AND D. SMERTNIG (2) If T is atomic and φ is a weak transfer homomorphism, then Zp (T ) = T × φ(Z∗ (H))T × . In particular, for all a ∈ H, the induced map Zp (a) → Zp (φ(a)) is surjective. In either case, if φ is isoatomic, then the homomorphism φp : Zp (H) → Zp (T ) induced from φ is injective. 4. Catenary Degrees Throughout this section, let H be a cancellative small category. Each notion of a distance d gives rise to a corresponding catenary degree, as well as a monotone catenary degree. These invariants provide a measure of how far away H is from being d-factorial. For basic properties of the catenary degree in the commutative setting, see [GHK06, Section 1.6]. After giving the basic definitions, in Proposition 4.6 we provide a technical result that allows the study of catenary degrees using transfer homomorphisms. This will be applied in Section 7 to arithmetical maximal orders in quotient semigroups. In Proposition 4.8 we prove a transfer result for distances using an isoatomic weak transfer homomorphism. This will be applied at the end of Section 6 to the semigroup Tn (D)• of non zero-divisors of the ring of n × n upper triangular matrices over a commutative atomic domain. Definition 4.1. Let H be atomic, d a distance on H, and a ∈ H. (1) Let z, z 0 ∈ Z∗ (a) and N ∈ N0 . A finite sequence of rigid factorizations z0 , . . . , zn ∈ Z∗ (a), where n ∈ N0 , is called an N -chain (in distance d) between z and z 0 if z = z0 , z 0 = zn , and d(zi−1 , zi ) ≤ N for all i ∈ [1, n]. It is called a monotone N -chain if either |z0 | ≤ |z1 | ≤ · · · ≤ |zn | or |z0 | ≥ |z1 | ≥ · · · ≥ |zn |. (2) The [monotone] catenary degree (in distance d) of a, denoted by cd (a) [cd,mon (a)], is the minimal N ∈ N0 ∪ {∞} such that for any two factorizations z, z 0 ∈ Z∗ (a) there exists a [monotone] N -chain between z and z 0 . (3) The catenary degree (in distance d) of H is cd (H) = sup{ cd (a) : a ∈ H } ∈ N0 ∪ {∞}, and the monotone catenary degree (in distance d) is cd,mon (H) = sup{ cd,mon (a) : a ∈ H } ∈ N0 ∪ {∞}. As in the commutative setting, the monotone catenary degree is usually studied using two auxiliary invariants, the equal catenary degree and the adjacent catenary degree. The equal catenary degree, cd,eq (a), is the smallest N ∈ N0 ∪ {∞} such that for any two factorizations z, z 0 ∈ Z∗ (a) with |z| = |z 0 |, there exists a monotone N -chain between z and z 0 (since |z| = |z 0 |, this means one in which every factorization is of length |z|). We set cd,eq (H) = sup{ cd,eq (a) : a ∈ H } ∈ N0 ∪ {∞}. For a ∈ H and k, l ∈ L(a) write, dk,l (a) = min{ d(z, z 0 ) : z, z 0 ∈ Z∗ (a), |z| = k, |z 0 | = l }. We say that k and l are adjacent in L(a) if L(a) ∩ [k, l] = {k, l}. The adjacent catenary degree of a ∈ H is defined as cd,adj (a) = sup{ dk,l (a) : k, l are adjacent in L(a) } ∈ N0 ∪ {∞}, with cd,adj (H) = sup{ cd,adj (a) : a ∈ H } ∈ N0 ∪ {∞}. It is immediate from the definitions that cd (a) ≤ cd,mon (a) = sup{cd,eq (a), cd,adj (a)}, and hence cd (H) ≤ cd,mon (H) = sup{cd,eq (H), cd,adj (H)}. We denote the catenary degrees associated to d∗ , dp , dsim , and dsubsim by c∗ = cd∗ , cp = cdp , csim = cdsim , and csubsim = cdsubsim , and use analogous conventions for the monotone, equal and adjacent catenary degrees. The following lemma parallels [GHK06, Lemma 1.6.2]. Remark 4.3 shows that in (2) and (3) this is the best we can do in a general noncommutative setting, despite the fact that stronger bounds are available for the usual distance in the commutative setting. Lemma 4.2. Let H be atomic and let d be a distance on H. Let a ∈ H. (1) We have cd (a) ≤ cd,mon (a) ≤ sup L(a), and cd (a) = 0 if and only if cd,mon (a) = 0 if and only if |Zd (a)| = 1. In particular, H is d-factorial if and only if cd (H) = cd,mon (H) = 0. 0 ∗ (2) If z, z ∈ Z (a), then |z| − |z 0 | ≤ d(z, z 0 ). (3) If ∆(L(a)) 6= ∅, then sup ∆(L(a)) ≤ cd (s). In particular, sup ∆(H) ≤ cd (H). (4) If cd (H) = 0, then H is half-factorial. If cd (a) ≤ 1, then L(a) is an interval. FACTORIZATION THEORY: FROM COMMUTATIVE TO NONCOMMUTATIVE SETTINGS 19 Proof. (1) If a ∈ H × , then |Zd (a)| = 1, and cd (a) = cd,mon (a) = sup L(a) = 0. Suppose that a ∈ H is a nonunit and let z, z 0 ∈ Z∗ (a). Then d(z, z 0 ) ≤ max{|z|, |z 0 |, 1} ≤ sup L(a). Thus cd (a) ≤ cd,mon (a) ≤ sup L(a). If |Zd (a)| = 1, then clearly cd (a) = cd,mon (a) = 0. Conversely, suppose that cd (a) = 0. Then there exist n ∈ N0 and z0 , . . . , zn ∈ Z∗ (a) such that z = z0 , z 0 = zn and d(zi−1 , zi ) = 0 for all i ∈ [1, n]. Therefore d(z, z 0 ) = 0 by the triangle inequality. Since z and z 0 are both rigid factorizations of a, we have z ∼d z 0 . Thus |Zd (a)| = 1 and cd,mon (a) = 0. (2) This is simply property (D5). (3) Let d ∈ ∆(L(a)). Then there exist z, z 0 ∈ Z∗ (a) such that d = |z 0 | − |z| and there exists no z 00 ∈ Z∗ (a) with |z| < |z 00 | < |z 0 |. By definition of the catenary degree, there exists a cd (a)-chain in distance d between z and z 0 . By (2), this implies d ≤ cd (a). (4) This is clear by (3). Remark 4.3. The bounds in the previous lemma are weaker than their commutative counterparts. In particular, for a commutative cancellative semigroup S, it is true that sup ∆(S) + 2 ≤ cp (S) and hence even cp (S) ≤ 2 implies that S is half-factorial. We now point out that Lemma 4.2 is the best possible for a general result in the noncommutative setting. Let T = ha, b, c | abc = cbi. Clearly T is reduced with A(T ) = {a, b, c}, and it is easily verified that T is an Adyan semigroup and hence cancellative. Let S be a commutative atomic cancellative semigroup. (1) For all s ∈ S we have either cp (s) = 0 or cp (s) ≥ 2. This fails for the semigroup T , as cp (abc = cb) = 1. (2) If s ∈ S and z, z0 are two distinct factorizations in Zp (s), then dp (z, z 0 ) ≥ |z| − |z 0 | + 2. This fails for T since |abc| − |cb| = 1 = dp (a ∗ b ∗ c, c ∗ b). Moreover, in the cancellative semigroup ha, b | aba = bi, we have d∗ (a ∗ b ∗ a, b) = 2 = |a ∗ b ∗ a| − |b|, showing that the inequality in Lemma 4.2(2) is also best possible for the rigid distance. (3) If s ∈ S and |Zp (s)| ≥ 2, then cp (s) ≥ sup ∆(s) + 2. This fails for T since L(abc = cb) = {2, 3} and thus ∆(abc) = {1} as well as cp (abc) = 1. Example 4.4. We illustrate the terminology of this section by means of a classical example. Consider S = (C[X] \ C, ◦), that is, decompositions of non-constant polynomials with coefficients in C. An atom of S is called an indecomposable polynomial, and a rigid factorization of f ∈ S is called a complete decomposition of f . Ritt’s first theorem ([ZM08, Theorem 2.1]) says that any complete decomposition of f ∈ S can be transformed into any other, by a sequence of transformations in each of which two adjacent indecomposable factors are replaced by two new ones. In our present terminology, this can be expressed simply as c∗ (S) ≤ 2. (Note however that much more refined results on polynomial decompositions are known.) Let H and T be atomic cancellative small categories, and let φ : H → T be a weak transfer homomorphism. Let φ∗ : Z∗ (H) → Z∗ (T ) denote the extension of φ to the categories of rigid factorizations as given in Lemma 3.10. If z, z 0 ∈ Z∗ (H), then d∗ (z, z 0 ) ≥ d∗ (φ∗ (z), φ∗ (z 0 )) ≥ dp (φ∗ (z), φ∗ (z 0 )). If φ is a transfer homomorphism, this together with Lemma 3.10(1) implies c∗ (a) ≥ c∗ (φ(a)) ≥ cp (φ(a)) for all a ∈ H, and c∗ (H) ≥ c∗ (T ) ≥ cp (T ). Moreover, dp (z, z 0 ) ≥ dp (φ∗ (z), φ∗ (z 0 )). Thus Lemma 3.10(2) implies that c∗ (a) ≥ cp (a) ≥ cp (φ(a)) for all a ∈ H, and c∗ (H) ≥ cp (H) ≥ cp (T ). Analogous inequalities hold for the monotone and equal catenary degrees. In the commutative setting, catenary degrees can be studied using transfer homomorphisms. If φ : S → T is a transfer homomorphism of commutative atomic cancellative semigroups, one finds that cp (S) ≤ max{cp (T ), cp (S, φ)}, where cp (S, φ) is a suitably defined catenary degree in the fibers of φ (see [GHK06, Lemma 3.2.6]). The strength of this method lies in the fact that, for a commutative Krull monoid S and its usual transfer homomorphism φ to a monoid of zero-sum sequences, it always holds that cp (T, φ) ≤ 2 (by [GHK06, Theorem 3.2.8]). Thus the catenary degree in the image T controls the catenary degree in S to a very large degree: Unless S is half-factorial, it holds that cp (S) = cp (T ). Aiming for similar results, we now introduce the notion of a catenary degree in the permutable fibers. Definition 4.5 (Catenary degree in the permutable fibers). Let H and T be atomic cancellative small categories, and let d be a distance on H. Suppose that there exists a transfer homomorphism φ : H → T . Denote by φ∗ : Z∗ (H) → Z∗ (T ) its extension to the categories of rigid factorizations as given in Lemma 3.10, and denote by φ : Z∗ (H) → Zp (T ) the composition of φ∗ with the canonical homomorphism Z∗ (T ) → Zp (T ). 20 N. BAETH AND D. SMERTNIG Let a ∈ H, and let z, z 0 ∈ Z∗ (a) with φ(z) = φ(z 0 ) (that is, dp (φ∗ (z), φ∗ (z 0 )) = 0). We say that an N -chain z = z0 , z1 , . . . , zn = z 0 ∈ Z∗ (a) lies in the permutable fiber of z if φ(zi ) = φ(z) for all i ∈ [0, n]. We define cd (a, φ) to be the smallest N ∈ N0 ∪{∞} such that, for any two z, z 0 ∈ Z∗ (a) with φ(z) = φ(z 0 ), there exists an N -chain (in distance d) between z and z 0 , lying in the permutable fiber of z. Moreover, we define cd (H, φ) = sup{ cd (a, φ) : a ∈ H } ∈ N0 ∪ {∞}. The first claim of the following proposition provides a weaker analogue of [GHK06, Proposition 3.2.3.3(c)] for the present setting, while the second statement roughly corresponds to [GHK06, Lemma 3.2.6.2]. Note that to prove the first claim we need to make use of the catenary degree in the permutable fibers, quite unlike the commutative variant. The restriction to T being reduced is made to simplify the proof, but is not essential. We note that the commutative hypothesis on T is essential in the proof. Proposition 4.6. Let T be a commutative reduced cancellative semigroup. Let H be atomic, let d be a distance on H, and suppose φ : H → T is a transfer homomorphism. Denote by φ∗ : Z∗ (H) → Z∗ (T ) the extension of φ to the categories of rigid factorizations (as in Lemma 3.10). Let a ∈ H. (1) Let z ∈ Z∗H (a). If y ∈ Z∗T (φ(a)), then there exist y, y 0 , z 0 ∈ Z∗H (a) such that φ∗ (y) = y, φ∗ (z 0 ) ∼dp φ∗ (z), φ∗ (y 0 ) ∼dp y, d(z 0 , y 0 ) ≤ dp (φ∗ (z), y), and there exist cd (a, φ)-chains between z and z 0 lying in the permutable fiber of z, and between y and y 0 lying in the permutable fiber of y. (2) Let z, z 0 ∈ Z∗H (a), k ∈ N0 , z 1 , . . . , z k ∈ Z∗T (φ(a)) and set z 0 = φ∗ (z) and z k+1 = φ∗ (z 0 ). Then there exist rigid factorizations z = z0 , z1 , . . . , zk , zk+1 = z 0 ∈ Z∗H (a) such that zi and zi+1 are connected by a monotone max{cd (a, φ), dp (z i , z i+1 )}-chain in distance d for all i ∈ [0, k], and φ∗ (zi ) = z i for all i ∈ [1, k]. In particular, cd (a) ≤ max{cp (φ(a)), cd (a, φ)}, cd (H) ≤ max{cp (T ), cd (H, φ)}, cd,mon (a) ≤ max{cp,mon (φ(a)), cd (a, φ)}, cd,mon (H) ≤ max{cp,mon (T ), cd (H, φ)}, cd,eq (a) ≤ max{cp,eq (φ(a)), cd (a, φ)}, cd,eq (H) ≤ max{cp,eq (T ), cd (H, φ)}. Proof. (1) Since T is commutative, dp is the usual distance on T . Thus there exist x, y 0 , z 0 ∈ Z∗ (T ) such that y ∼dp x ∗ y 0 , φ∗ (z) ∼dp x ∗ z 0 and max{|y 0 |, |z 0 |} = dp (φ∗ (z), y). In particular, x ∗ y 0 and x ∗ z 0 are indeed rigid factorization of φ(a). Since φ is a transfer homomorphism, this implies that there exists a rigid factorization z 0 ∈ Z∗H (a) such that φ∗ (z 0 ) = x ∗ z 0 . Then φ∗ (z 0 ) ∼dp φ∗ (z) and, by definition of cd (a, φ), there exists a cd (a, φ)-chain between z and z 0 lying in the permutable fiber of z. Let y ∈ Z∗ (a) be an arbitrary preimage of y under φ∗ . Now let z 0 = εu1 ∗ · · · ∗ ul with l ∈ N0 , ε ∈ H × , u1 , . . . , ul ∈ A(H), and let k = |x|. Then ∗ φ (εu1 ∗ · · · ∗ uk ) = x. Suppose y 0 = v 1 ∗ · · · ∗ v n with n ∈ N0 and v 1 , . . . , v n ∈ A(T ). Then φ(a) = φ(ε−1 a) = φ(u1 ) · · · φ(ul ) = φ(u1 ) · · · φ(uk )v 1 · · · v n , and thus φ(uk+1 · · · ul ) = φ(uk+1 ) · · · φ(ul ) = v 1 · · · v n . If k = l, then n = 0 and y ∼dp x ∼dp φ∗ (z). Setting y 0 = z 0 , we are done. Now suppose that k < l. Then n > 0 and, since φ is a transfer homomorphism, there exist v1 , . . . , vn ∈ A(H) such that uk+1 · · · ul = v1 · · · vn and φ(vi ) = v i for all i ∈ [1, n]. We define y 0 = εu1 ∗ · · · ∗ uk ∗ v1 ∗ · · · ∗ vn (note that s(v1 ) = s(uk+1 ) = t(uk )). Using property (D4), it follows that d(y 0 , z 0 ) = d(v1 ∗ · · · ∗ vn , uk+1 ∗ · · · ∗ ul ). Thus property (D5) implies d(y 0 , z 0 ) ≤ max{n, l − k, 1} = dp (φ∗ (z), y). Now y and y 0 lie in the same permutable fiber, and hence are connected by a cd (a, φ)-chain in the permutable fiber of y. (2) Set z0 = z, and zk+1 = z 0 . We apply (1) inductively to construct z1 , . . . , zk ∈ Z∗H (a) with the desired properties. Suppose that we have constructed zi for some i ∈ [0, k − 1]. Applying (1) to zi and z i+1 , 0 0 we find zi0 , zi+1 , zi+1 ∈ Z∗H (a) such that φ∗ (zi ) ∼dp φ∗ (zi0 ), φ∗ (zi+1 ) ∼dp φ∗ (zi+1 ), φ∗ (zi+1 ) = z i+1 and 0 0 0 d(zi , zi+1 ) ≤ dp (z i , z i+1 ). Since zi and zi lie in the same permutable fiber, there exists a cd (a, φ)-chain between zi and zi0 lying in the permutable fiber of zi . In particular, all the rigid factorizations in this chain 0 have length |zi |. Similarly, between zi+1 and zi+1 there exists a cd (a, φ)-chain in the permutable fiber of 0 0 zi+1 . Since d(zi , zi+1 ) ≤ dp (z i , z i+1 ) we can therefore construct a max{cd (a, φ), dp (z i , z i+1 )}-chain between zi and zi+1 . This chain is obviously monotone, since the only point at which the length can change is from 0 zi0 to zi+1 . The upper bound on cd (a) now follows immediately by lifting chains from the image. Similarly, the upper bounds for the monotone and equal catenary degree follow by lifting monotone chains, respectively chains of equal length. Remark 4.7. Let H be atomic. We have cp (a) ≤ c∗ (a) for all a ∈ H. Suppose H is a commutative semigroup. Then the identity map id : H → H is a transfer homomorphism. Let a ∈ H. Two rigid FACTORIZATION THEORY: FROM COMMUTATIVE TO NONCOMMUTATIVE SETTINGS 21 factorizations z = εu1 ∗ · · · ∗ uk , z 0 = ηv1 ∗ · · · ∗ vl ∈ Z∗ (a) lie in the same permutable fiber of the identity map if and only if [z]p = [z 0 ]p , that is, k = l and there exists a permutation σ ∈ Sk such that ui ' vσ(i) for all i ∈ [1, k]. By writing σ as a product of transpositions, it is therefore easy to construct a 2-chain in distance d∗ between z and z 0 (here we use the commutativity of H to ensure that permuting two atoms does not change the product). Therefore c∗ (a, id) ≤ 2. Applying the previous proposition, in the commutative case we therefore have cp (a) ≤ c∗ (a) ≤ max{2, cp (a)}. Trivially, this remains true if we replace the rigid distance by any distance finer than the permutable distance, but coarser than the rigid distance: While two such distances can be quite different, their catenary degrees cannot differ by much. However, this does not hold in general. Let n ∈ N and let S = ha, b | an bn = bn an i. Then S is cancellative and reduced with A(S) = {a, b}, and it follows immediately that cp (S) = 0 while c∗ (S) = 2n. The following proposition shows that distances and catenary degrees are preserved by isoatomic weak transfer homomorphisms. Proposition 4.8. Let H and T be atomic cancellative small categories, and assume that there exists an isoatomic weak transfer homomorphism φ : H → T . Denote by φp : Zp (H) → Zp (T ) the extension of φ to permutable factorizations (as in Lemma 3.10). Then dp (z, z 0 ) = dp (φp (z), φp (z 0 )) for any two permutable factorizations z and z 0 of a ∈ H. In particular, cp (H) = cp (T ). Proof. If a ∈ H × , the claim is trivially true. Assume from now on that a is not a unit. Without loss of generality, write k = |z| ≤ |z 0 | = l with k ≤ l. Then we can write z = [u1 ∗ · · · ∗ uk ]p and z 0 = [v1 ∗ · · · ∗ vl ]p with ui , vj ∈ A(H) for i ∈ [1, k] and j ∈ [1, l]. Moreover, there exists an m ∈ [1, k] and permutations σ ∈ Sk , τ ∈ Sl such that uσ(i) ' vτ (i) for all i ∈ [1, m] and such that uσ(i) 6' vτ (j) whenever i ∈ [m + 1, k] and j ∈ [m + 1, l]. Note that dp (z, z 0 ) = l − m. We have φp (z) = [φ(u1 ) ∗ · · · ∗ φ(uk )]p and φp (z 0 ) = [φ(v1 ) ∗ · · · ∗ φ(vl )]p with φ(ui ) and φ(vj ) ∈ A(T ) for i ∈ [1, k] and j ∈ [1, l]. There exists n ∈ [1, k] and permutations σ b ∈ Sk , τb ∈ Sl such that φ(uσb(i) ) ' φ(vτb(i) ) for all i ∈ [1, n] and such that φ(uσb(i) ) 6' φ(vτb(j) ) whenever i ∈ [n + 1, k] and j ∈ [n + 1, l]. Note that dp (φp (z), φp (z 0 )) = l − n. Since φ is isoatomic, n = m and therefore dp (z, z 0 ) = dp (φp (z), φp (z 0 )). 5. Divisibility Throughout this section, let H be a cancellative small category. Our goal is to generalize the notion of divisibility of one element by another from the commutative setting, to use this notion to better understand the factorizations introduced in Section 3, and to give another measure of the non-uniqueness of permutable factorizations by generalizing the tame-degree and ω-invariant from the commutative setting. To this end, we begin by defining an abstract divisibility relation. Definition 5.1. A relation o on H is a divisibility relation provided that the following conditions are satisfied. (1) If a o b or a o c for any elements a, b, c ∈ H with t(b) = s(c), then a o bc. (2) For all a ∈ H and ε, η ∈ H × with t(ε) = s(a) and s(η) = t(a), we have a o εaη. (3) For all a ∈ H \ H × and u ∈ A(H), if a o u, then a ' u. (4) If a o ε for some ε ∈ H × , then a ∈ H × . If H is a commutative semigroup, the usual notion of divisibility, a | b if b ∈ aH, is a divisibility relation. In the noncommutative setting, our focus will be on one of the following two relations, each of which clearly satisfies the formal properties of a divisibility relation. As we are mostly interested in when an atom divides a product, the particular choice of divisibility relation will not make a difference as long as H is atomic (see Lemma 5.6(1)). Definition 5.2. Let a and b be two elements of H. (1) We say that a left-right divides b, and write a |l−r b, provided b ∈ HaH. (2) We say that a divides b up to permutation, and write a |p b, if there are permutable factorizations [εu1 ∗ · · · ∗ uk ]p of a and [ηv1 ∗ · · · ∗ vl ]p of b (with k, l ∈ N0 , ε, η ∈ H × and u1 , . . . , uk , v1 , . . . , vl ∈ A(H)) such that 22 N. BAETH AND D. SMERTNIG (i) k ≤ l, and (ii) there exists an injective map σ : [1, k] → [1, l] with ui ' vσ(i) for all i ∈ [1, k]. If H is a commutative semigroup, then a left-right divides b if and only if a divides b, since HaH = aH. If, moreover, H is atomic, then a divides b up to permutation if and only if a divides b. If H is atomic, we can characterize left-right divisibility in terms of rigid factorizations as follows: a |l−r b if and only if for any (equivalently all) rigid factorization z ∈ Z∗ (a) there exist x, y ∈ Z∗ (H) such that x ∗ z ∗ y is a rigid factorization of b. Indeed, if z ∈ Z∗ (a) and x, y ∈ Z∗ (H) are as described, then b = π(x)π(z)π(y) = π(x)aπ(z). Conversely, if b = cad with c, d ∈ H, let z ∈ Z∗ (a), x ∈ Z∗ (c) and y ∈ Z∗ (d). Then x ∗ z ∗ y ∈ Z∗ (b). If H is atomic and a |l−r b, then a |p b. The converse is clearly not true. However, if u ∈ A(H), then u |p b if and only if u |l−r b, as we shall see in Lemma 5.6(1). The notions of left, respectively right, divisibility, do not generally give a divisibility relation due to the failure of property (1) to hold. We now study a general divisibility relation o on H. However, throughout we have in mind the two specific divisibility relations given in Definition 5.2. In fact, we will return at the end of this section to a more thorough investigation of |p . Definition 5.3. Let o be a divisibility relation on H. A non-unit q ∈ H is an almost prime-like element (with respect to o) if, whenever q o ab for some a, b ∈ H with t(a) = s(b), either q o a or q o b. Remark 5.4. (1) It is clear from the definition that the notion of an almost prime-like element in H corresponds to the usual notion of a prime element if H is a commutative semigroup and if either o is |l−r , or H is atomic and o is |p . (2) We will compare the notion of almost prime-like elements to more established concepts below in Remark 5.11. (3) We shall see in Lemma 5.6 that if H is atomic, the notion of almost prime-like elements is in fact independent of the particular divisibility relation chosen. (4) After seeing how almost prime-like elements behave like prime elements in the commutative setting in Proposition 5.7 and Corollary 5.8 and how products of almost prime-like elements do not necessarily give elements with unique permutable factorizations in Example 5.9, we strengthen the definition in 5.10 to prime-like elements. We now show that if H is atomic, then, as in the commutative setting, almost prime-like elements are necessarily atoms of H. Lemma 5.5. Let o be a divisibility relation on H, and let q be an almost prime-like element of H. (1) If q o a1 · · · am for some m ∈ N and elements a1 , . . . , am ∈ H, then q o ai for some i ∈ [1, m]. (2) If q o u1 · · · um for some m ∈ N and atoms u1 , . . . , um ∈ A(H), then q ' ui for some i ∈ [1, m]. (3) If H is atomic, then q is an atom. Proof. (1) We proceed by induction on m. By definition, if m ∈ {1, 2}, then q o a1 or q o a2 . Now suppose that m > 2 and that if q o a1 · · · am−1 , then q o ai for some i ∈ [1, m − 1]. Since q o (a1 · · · am−1 )am and q is almost prime-like, either q o a1 · · · am−1 or q o am . If q o am , then we are done. Otherwise, the induction hypothesis implies q o ai for some i ∈ [1, m − 1]. (2) Applying (1), we find q o ui for some i ∈ [1, m], and then property (3) of the divisibility relation implies q ' ui . (3) Since H is atomic and q is a non-unit, there exist m ∈ N and atoms u1 , . . . , um ∈ A(H) such that q = u1 · · · um . By property (2) of the divisibility relation, we have q o u1 · · · um , and then (2) implies q ' ui for some i ∈ [1, m]. Hence q is an atom. The following lemma shows that if H is atomic, the choice of divisibility relation has no bearing on which elements are almost prime-like. Lemma 5.6. Let H be atomic, and let o and o0 be divisibility relations on H. (1) If u ∈ A(H) and a ∈ H, then u o a if and only if u o0 a. (2) An element q ∈ H is almost prime-like with respect to o if and only if it is almost prime-like with respect to o0 . Proof. (1) Suppose u o a. By property (4) of a divisibility relation, a is not a unit, and hence there exist k ∈ N and atoms u1 , . . . , uk of H such that a = u1 · · · uk . Thus Lemma 5.5(2) implies u ' ui for some FACTORIZATION THEORY: FROM COMMUTATIVE TO NONCOMMUTATIVE SETTINGS 23 i ∈ [1, k]. Then property (2) of o0 implies u o0 ui , and by property (1) we have u o0 a. The converse follows by symmetry. (2) Suppose q is almost prime-like with respect to o, and note that Lemma 5.5(3) implies that q is an atom. Let a, b ∈ H such that q o0 ab. Then q o ab by (1), and hence either q o a or q o b. Using (1) again, q o0 a or q o0 b. The converse follows by symmetry. Products of prime elements in a commutative cancellative semigroup have unique factorization (cf. [GHK06, Proposition 1.1.8]). In fact, if p1 · · · pk c = q1 · · · ql d with each pi and qj prime, with no pi dividing d, and no qj dividing c, then k = l and, up to permutation, pi ' qi for each i. Moreover, c ' d. We now provide, for almost prime-like elements in a cancellative small category, a weaker statement than its commutative counterpart. That this result is necessarily weaker is exhibited in Example 5.9. We first make some notational remarks. The category of rigid factorizations, Z∗ (H), is itself an atomic cancellative small category, and hence |p and |l−r are defined on Z∗ (H). As in Section 3, we may identify A(H) with A(Z∗ (H)) and H × with Z∗ (H)× . If z ∈ Z∗ (H), we say that u ∈ A(H) occurs in z if u |p z (equivalently u |l−r z) in Z∗ (H). The same remarks apply to Zp (H) instead of Z∗ (H) and clearly, if z ∈ Z∗ (H), u occurs in z if and only if u occurs in [z]p ∈ Zp (H). We now show that if an almost prime-like element q occurs in some rigid factorization of an element a, then q occurs in every such factorization of a. Proposition 5.7. Let o be a divisibility relation on H and let a ∈ H. Suppose that z = εu1 ∗ · · · ∗ uk and z 0 = ηv1 ∗ · · · ∗ vl are two rigid factorizations of a, where {u1 , . . . , uk } = {p1 , . . . , pm } ∪ {u0m+1 , . . . , u0k } with pi an almost prime-like atom for all i ∈ [1, m] and where 0 {v1 , . . . , vl } = {q1 , . . . , qn } ∪ {vn+1 , . . . , vl0 } with qj an almost prime-like atom for all j ∈ [1, n]. Further suppose that for all i ∈ [1, m] and j ∈ [n + 1, l] it holds that pi 6 o vj0 , and for all j ∈ [1, n] and i ∈ [m + 1, k] it holds that qj 6 o u0i . Then there is a bijective correspondence between the set of associativity classes of the pi and the set of associativity classes of the qj . Proof. Since εu1 · · · uk = ηv1 · · · vl , we have pi o v1 · · · vl for each i ∈ [1, m]. By Lemma 5.5, this implies that for each i ∈ [1, m], pi o vj for some j ∈ [1, l]. Then pi 6 o vj0 for any j ∈ [n + 1, l] and thus pi o qj for some j ∈ [1, n]. As pi and qj are both atoms, pi ' qj . Therefore each almost prime-like element pi occurring in z is associated to an almost prime-like element qj occurring in z 0 . A symmetrical argument shows that each almost prime-like element qj occurring in z 0 is associated to an almost prime-like element pi occurring in z. The result follows. Corollary 5.8. Let H be atomic, and let q be an atom of H. The following statements are equivalent. (a) q is an almost prime-like element. (b) If a ∈ H, z ∈ Z∗ (a) and q occurs in z, then q occurs in z 0 for all z 0 ∈ Z∗ (a). (c) If a ∈ H, z ∈ Zp (a) and q occurs in z, then q occurs in z 0 for all z 0 ∈ Zp (a). Proof. The equivalence of (b) and (c) is clear by the discussion preceeding Proposition 5.7. If q is an almost prime-like element of H, then (b) holds by Proposition 5.7. Now suppose that (b) holds, and suppose that q |p ab for some a, b ∈ H. If q -p a and q -p b, then q cannot occur in any rigid factorization of a or b. Let z ∈ Z∗ (a) and z 0 ∈ Z∗ (b). Then z ∗ z 0 is a rigid factorization of ab in which q does not occur, but this contradicts q |p ab by Proposition 5.7. Example 5.9. Let S = ha, b, c | aba = ba3 bci. Clearly S is an Adyan semigroup and hence cancellative. Considering the single relation defining S, we see that any word in F ∗ (a, b, c) that contains a (respectively b) can only be rewritten in such a way that it again contains a (respectively b). Therefore the two atoms a and b are almost prime-like elements in S. Since aba = ba3 bc, the atom c is not an almost prime-like element. Considering the relation aba = ba3 bc, we see that the product aba of almost prime-like elements does not have a unique permutable factorization in S. The phenomena exhibited in Proposition 5.7, Corollary 5.8, and Example 5.9 motivate the following definition. In particular we associate to an almost prime-like element q a multi-valued q-adic valuation, that corresponds to the concept of a p-adic valuation of a prime p in the commutative setting (cf. [GHK06, Definition 1.1.9]). Definition 5.10. Let o be a divisibility relation on H, and let q ∈ H be an almost prime-like atom with respect to o. 24 N. BAETH AND D. SMERTNIG (1) Let a ∈ H. We define Vq (a) ⊂ N0 as follows: A non-negative integer n ∈ N0 is contained in Vq (a) if and only if there exist k ∈ N0 and u1 , . . . , uk ∈ A(H) such that a ' u1 · · · uk and n = |{ i ∈ [1, k] : ui ' q }|. In particular Vq (a) = {0} if a ∈ H × . We call Vq (a) the q-adic valuation of a. (2) The almost prime-like element q is prime-like (with respect to o) provided that |Vq (a)| = 1 for all a ∈ H. Note that unlike in the commutative setting, Vq (a) need not be a singleton. Indeed, if S is as in Example 5.9, then Va (aba) = {2, 3} and Vb (aba) = {1, 2}. By considering the Adyan semigroup S = ha, b | aba = ba3 bi, one sees that even if each atom of an atomic cancellative semigroup S is almost prime-like, S need not be permutably factorial. However, if q is an almost prime-like atom and a ∈ H is a non-unit, then 0 ∈ Vq (a) if and only if Vq (a) = {0} (by Proposition 5.7). Remark 5.11. We compare the notion of (almost) prime-like elements in cancellative semigroups and rings to more established concepts. We do so by means of left-right divisibility, but recall that the choice of divisibility relation does not matter if the semigroup or ring is atomic (by Lemma 5.6). Let S be a cancellative semigroup. A proper semigroup ideal P ⊂ S is called a completely prime ideal if, for all a, b ∈ S, ab ∈ P implies a ∈ P or b ∈ P . It is immediate from the definitions that p ∈ S is an almost prime-like element if and only if SpS is a completely prime ideal of S. Now let R be a ring and consider the cancellative semigroup S = R• of non zero-divisors of R. A proper ideal P of R is called a prime ideal if, for all a, b ∈ R, aRb ⊂ P implies a ∈ P or b ∈ P , and P is called a completely prime ideal if, for all a, b ∈ R, ab ∈ P implies a ∈ P or b ∈ P . If p ∈ R is an almost prime-like element, then in general pR and Rp need not even be ideals of R, while the ideal of R generated by p need not even be proper. For instance, let D be a commutative PID and R = Mn (D) with n ∈ N≥2 . An element A ∈ R• is an atom if and only if det(A) is a prime element of D if and only if A is a prime-like element of R• (this follows easily by means of the Smith Normal Form, see also the examples at the end of Section 6). Thus, an (almost) prime-like element A ∈ R• is not contained in any proper ideal of R. Conversely, if P is a prime ideal of Mn (D) then P = Rp = pR = R hpiR with p a prime element of D. However, p is not even an atom in R• since det(p) = pn . Thus elements that generate principal prime ideals (as left ideals, right ideals, or two-sided ideals) need not be almost prime-like. However, suppose that p ∈ R• is such that Rp = pR. One verifies directly: If a ∈ R• and x ∈ R with either xp = a or px = a, then x ∈ R• . In particular R• p = pR• . Thus the following statements are equivalent for a ∈ R• : (a) p |l−r a, (b) p |l a, (c) p |r a, (d) a ∈ pR, (e) a ∈ Rp. This implies that the ideal Rp is a completely prime ideal if and only if p is an almost prime-like element. In [Cha84], an element p in a Noetherian ring R is called a prime element of R if Rp = pR and Rp is a height-1 prime ideal of R and completely prime. Thus any non zero-divisor prime element p of R is an almost prime-like element of R• . As the following lemma shows, the behavior of valuations for prime-like elements is quite similar to the behavior of valuations for prime elements in the commutative setting. Lemma 5.12. Let H be atomic, and let q be an almost prime-like element of H. Then q is prime-like if and only if Vq (a) + Vq (b) = Vq (ab) for all a, b ∈ H with t(a) = s(b). Proof. By definition, q is prime-like if and only if |Vq (a)| = 1 for all a ∈ H. Note that for all a, b ∈ H with t(a) = s(b), we trivially have Vq (a) + Vq (b) ⊂ Vq (ab). Indeed, if m ∈ Vq (a) and n ∈ Vq (b), then there exist rigid factorizations z = εu1 ∗ · · · ∗ uk of a and z 0 = ηv1 ∗ · · · ∗ vl of b with k, l ∈ N0 , ε, η ∈ H × , and u1 , . . . , uk , v1 , . . . , vl ∈ A(H) such that |{ i ∈ [1, k] : ui ' q }| = m and |{ j ∈ [1, l] : vj ' q }| = n. Since z ∗ z 0 is a rigid factorization of ab, we have m + n ∈ Vq (ab). Suppose first that |Vq (a)| = 1 for all a ∈ H. Let m, n ∈ N0 with Vq (a) = {m} and Vq (b) = {n}. Since {m + n} = Vq (a) + Vq (b) ⊂ Vq (ab), and the latter set is a singleton, it must be the case Vq (ab) = {m + n}. We now prove the converse. Let a ∈ H, k ∈ N0 , ε ∈ H × and u1 , . . . , uk ∈ A(H) be such that a = εu1 · · · uk . Then Vq (a) = Vq (ε) + Vq (u1 ) + · · · + Vq (uk ) by hypothesis. Since ε ∈ H × , Vq (ε) = {0}. Since each ui is an atom in H, for each i ∈ [1, k] either Vq (ui ) = {0} (if ui 6' q) or Vq (ui ) = {1} (if ui ' q). As Vq (ui ) is a singleton for all i ∈ [1, k], so is Vq (a). We have the following immediate corollary to Proposition 5.7 which generalizes the familiar result from the commutative setting (cf. [GHK06, Proposition 1.1.8]). FACTORIZATION THEORY: FROM COMMUTATIVE TO NONCOMMUTATIVE SETTINGS 25 Corollary 5.13. Let o be a divisibility relation on H. Let a ∈ H and suppose that z = εu1 ∗ · · · ∗ uk and z 0 = ηv1 ∗ · · · ∗ vl are two rigid factorizations of a, where {u1 , . . . , uk } = {p1 , . . . , pm } ∪ {u0m+1 , . . . , u0k } with pi a prime-like atom for all i ∈ [1, m] and where 0 {v1 , . . . , vl } = {q1 , . . . , qn } ∪ {vn+1 , . . . , vl0 } with qj a prime-like atom for all j ∈ [1, n]. Further suppose that for all i ∈ [1, m] and j ∈ [n + 1, l] it holds that pi 6 o vj0 , and for all j ∈ [1, n] and i ∈ [m + 1, k] it holds that qj 6 o u0i . Then m = n and there exists a permutation σ ∈ Sm such that pi ' qσ(i) for all i ∈ [1, m]. Remark 5.14. (1) Even products of prime-like elements need not have unique permutable factorizations as is exhibited by the following example. Let S = ha, b | a2 = ba2 bi. Then a is prime-like, yet a2 does not have a unique permutable factorization. (2) Let H be a commutative semigroup. For the sake of completeness, we note that neither the concept of almost prime-like elements nor that of prime-like elements coincide with that of absolutely irreducible elements — atoms u such that un has a unique permutable factorization for all n ∈ N. Let m ∈ N, n ∈ N≥2 and S = ha, b | abm a = bn i. Then b is almost prime-like (in fact prime-like if m = n), but is not absolutely irreducible. Conversely, if S 0 = ha, b, c | ab = bci, then a is absolutely irreducible, yet is not almost prime-like. We now study permutable factorizations by means of divisibility relations. By Lemma 5.6 we may consider only the divisibility relation |p . Recall, from Section 3, that H is permutably factorial if |Zp (a)| = 1 for all a ∈ H. Explicitly, H is atomic and for all non-units a ∈ H, whenever a = u1 · · · uk = v1 · · · vl with k, l ∈ N and atoms u1 , . . . , uk , v1 , . . . , vl ∈ A(H), k = l and there exists a permutation σ ∈ Sk with ui ' vσ(i) for all i ∈ [1, k]. We shall now see that for an atomic cancellative small category H, the conditions (1) Every atom is almost prime-like and (2) Every atom is prime-like provide a measure of how close H is to being permutably factorial. Proposition 5.15. H is permutably factorial if and only if H is atomic and every atom of H is prime-like. Proof. Suppose first that H is permutably factorial. Then H is atomic. If u is an atom in H and u |p ab for some a, b ∈ H with t(a) = s(b), then u occurs in the unique permutable factorization [z]p of ab by Lemma 5.5(2). However, [z]p = [x]p ∗ [y]p with [x]p and [y]p being the unique permutable factorization of a and b. Thus, u must occur in either [x]p or [y]p implying u |p a or u |p b, and so u is almost prime-like. Moreover, since H is permutably factorial, |Vq (a)| = 1 for any element a ∈ H and any almost prime-like element q of H. If, conversely, H is atomic, and every atom of H is prime-like, then Corollary 5.13 implies that H is permutably factorial. Applying Lemma 5.12, we immediately obtain the following corollary. Corollary 5.16. H is permutably factorial if and only if H is atomic and the following two conditions are satisfied. (1) Every atom in H is almost prime-like. (2) For every almost prime-like element q ∈ H and for all a, b ∈ H with t(a) = s(b), we have Vq (ab) = Vq (a) + Vq (b). We now briefly consider generalizations of the ω-invariant and the tame degree, which are well-studied invariants in the commutative setting, and measure how far away an atom is from being a prime element. Accordingly, our invariants will give a measure of how far away an atom is from being almost prime-like. Definition 5.17. Let H be atomic and let a, b ∈ H. (1) Define ωp0 (a, b) to be the smallest N ∈ N0 ∪ {∞} with the following property: For all n ∈ N and a1 , . . . , an ∈ H with a = a1 · · · an , if b |p a, then there exists k ∈ [0, N ] and an injective map σ : [1, k] → [1, n] such that the permuted subproduct aσ = s(aσ(1) )aσ(1) · · · aσ(k) is defined, and b |p aσ . Set ωp0 (H, b) = sup{ ωp0 (a, b) : a ∈ H } and ωp0 (H) = sup{ ωp0 (H, u) : u ∈ A(H) }. 26 N. BAETH AND D. SMERTNIG (2) Define ωp (a, b) to be the smallest N ∈ N0 ∪ {∞} with the following property: For all n ∈ N and atoms u1 , . . . , un of H with a = u1 · · · un , if b |p a, then there exists k ∈ [0, N ] and an injective map σ : [1, k] → [1, n] such that the permuted subproduct aσ = s(uσ(1) )uσ(1) · · · uσ(k) is defined, and b |p aσ . Set ωp (H, b) = sup{ ωp (a, b) : a ∈ H } and ωp (H) = sup{ ωp (H, u) : u ∈ A(H) }. Note that ωp0 (H, a) = ωp (H, a) = 0 if and only if a ∈ H × , and ωp0 (H, a) = ωp (H, a) = 1 if and only if a is an almost prime-like element. We always have ωp (H, a) ≤ ωp0 (H, a), and if H is a commutative semigroup, then ωp (H, a) = ωp0 (H, a) = ω(H, a), where ω(H, a) is the usual ω-invariant as defined in the commutative setting (see [GHK06, Definition 2.8.14]). The following example illustrates that ωp (H, a) = ωp0 (H, a) does not hold in general for noncommutative semigroups. Example 5.18. Let S = ha, b, c, d, e | ab = cd, cede = bai. The semigroup is Adyan and hence cancellative. Moreover, S is reduced and atomic with A(S) = {a, b, c, d, e}. We claim ωp (S, a) = 2. Clearly ωp (S, a) ≥ 2, since a |p cd = ab, but a does not permutably divide any permuted subproduct of cd. Suppose k ∈ N and u1 , . . . , uk ∈ A(S) are such that a |p u1 · · · uk . By the defining relations of S, either ui = a for some i ∈ [1, k], k ≥ 2 and ui ui+1 = cd for some i ∈ [1, k − 1], or that k ≥ 4 and ui ui+1 ui+2 ui+3 = cede for some i ∈ [1, k − 4]. In any of these cases we can take a subproduct of at most two elements that is divided up to permutation by a (due to cd = ab in the second and third case). However, ωp0 (S, a) ≥ 3: Let a1 = ce, a2 = d and a3 = e. Then a |p a1 a2 a3 = ba, but clearly a -p ai for any i ∈ [1, 3]. Moreover { ai aj : i, j ∈ [1, 3], i = 6 j } = {ced, ce2 , de, dce, ece, ed}, none of which is divided up to permutation by a. However, even in the noncommutative setting we have the following. Proposition 5.19. H is permutably factorial if and only if H is atomic, ωp0 (H) = ωp (H) ≤ 1 and every almost prime-like element is prime-like. Proof. We have ωp0 (H) = ωp (H) = 0 if and only if H is a groupoid. We may from now on exclude this trivial case, and assume that H is not a groupoid. Suppose first that H is permutably factorial. By Proposition 5.15, H is atomic and every atom of H is prime-like. Thus, for all u ∈ A(H), we have ωp (H, u) = ωp0 (H, u) = 1, and therefore ωp0 (H) = ωp (H) = 1. We now show the converse implication. If ωp0 (H) = ωp (H) = 1, then every atom in H is almost prime-like. By hypothesis, therefore all atoms of H are prime-like, and thus H is permutably factorial by Proposition 5.15. Continuing our discussion of the notion of divisibility up to permutation in Z∗ (H) and Zp (H) preceding Proposition 5.7, let x = εw1 ∗ · · · ∗ wm ∈ Z∗ (H) with m ∈ N0 , ε ∈ H × and w1 , . . . , wm ∈ A(H). We observe that, for z ∈ Z∗ (H) with z = ηu1 ∗ · · · ∗ uk where k ∈ N0 , η ∈ H × and u1 , . . . , uk ∈ A(H), we have x |p z if and only if there exists an injective map σ : [1, m] → [1, k] such that wi ' uσ(i) for all i ∈ [1, m]. Note that this is also equivalent to [x]p |p [z]p in Zp (H). Definition 5.20. Let H be atomic and a ∈ H. For a permutable factorization x ∈ Zp (H), let tp (a, x) denote the smallest N ∈ N0 ∪ {∞} with the following property: If there exists any z0 ∈ Zp (a) such that x |p z0 , and z ∈ Zp (a) is an arbitrary permutable factorization of a, then there exists some z 0 ∈ Zp (a) with x |p z 0 in Zp (H) and with dp (z, z 0 ) ≤ N . For subsets H 0 ⊂ H and Z ⊂ Zp (H), we define tp (H 0 , Z) = sup{ tp (a, z) : a ∈ H 0 , z ∈ Z } ∈ N0 ∪ {∞}. In particular, for u ∈ A(H) we set tp (H, u) = tp (H, {u}), and the (permutable) tame degree of H is defined as tp (H) = tp (H, A(H)) ∈ N0 ∪ {∞}. If H is a commutative semigroup, then tp (H, u) = t(H, u), where t(H, u) denotes the usual tame degree as defined in the commutative setting (see [GHK06, Definition 1.6.4]). We are now able to give a characterization of permutable factoriality in terms of the tame degree. Compare with [GHK06, Theorem 1.6.6] for the commutative analogue. Proposition 5.21. Let H be atomic. The following statements are equivalent. (1) H is permutably factorial. (2) tp (H) = 0 and every almost prime-like element is prime-like. (3) tp (H, Zp (H)) = 0 and every almost prime-like element is prime-like. FACTORIZATION THEORY: FROM COMMUTATIVE TO NONCOMMUTATIVE SETTINGS 27 Proof. It is obvious from the definitions that (3) implies (2). If H is permutably factorial, then every atom of H is prime-like by Proposition 5.15, and by definition of permutable factoriality, |Zp (a)| = 1 for all a ∈ H. Then tp (H, Zp (H)) = 0 follows trivially and thus (1) implies (3). We now show that (2) implies (1). If tp (H) = 0, then if u ∈ A(H) and u |p a for some a ∈ H, u |p z for all z ∈ Zp (a) by definition of the tame degree. Therefore u is almost prime-like by Corollary 5.8. Since u is prime-like by hypothesis, Proposition 5.15 implies that H is permutably factorial. The following example illustrates that, despite providing some insight into factorizations in the noncommutative setting, this noncommutative tame degree does not carry nearly as much information as in the commutative case. Example 5.22. Let S = ha, b | aba = babi. Then tp (S, a) = tp (S, b) = 0 and hence tp (S) = 0. However, S is not permutably factorial and thus the additional hypotheses given in (2) and (3) of Proposition 5.21 cannot be removed. We now show that any isoatomic weak transfer homomorphism preserves the values of t(−) and, under some additional restrictions, of ωp (−), ωp0 (−). We will see specific applications of this in Proposition 6.14 and Proposition 6.16. Proposition 5.23. Let T be an atomic cancellative small category and let φ : H → T be an isoatomic weak transfer homomorphism. Let φp : Zp (H) → Zp (T ) denote the extension of φ to permutable factorizations as in Lemma 3.10. (1) For z, z 0 ∈ Zp (H) we have z |p z 0 if and only if φp (z) |p φ(z 0 ). (2) For a, b ∈ H we have a |p b if and only if φ(a) |p φ(b). (3) Suppose H and T are semigroups. For a ∈ H we have ωp (H, a) ≤ ωp (T, φ(a)) and in particular ωp (H) ≤ ωp (T ). If T is commutative, then ωp (H, a) = ωp (T, φ(a)) and ωp (H) = ωp (T ). (4) Suppose H and T are semigroups. For a ∈ H we have ωp0 (H, a) ≤ ωp0 (T, φ(a)) and in particular ωp0 (H) ≤ ωp0 (T ). If T is commutative, then ωp0 (H, a) = ωp0 (T, φ(a)) and ωp0 (H) = ωp0 (T ). (5) For a ∈ H and x ∈ Zp (H) we have tp (a, x) = tp (φ(a), φp (x)) and in particular tp (H) = tp (T ). Proof. (1) Let k, l ∈ N0 , u1 , . . . , uk , v1 , . . . , vl ∈ A(H), and ε, η ∈ H × be such that z = [εu1 ∗ · · · ∗ uk ]p and z 0 = [ηv1 ∗ · · · ∗ vl ]p . Suppose first that z |p z 0 . Then k ≤ l and there exists an injective map σ : [1, k] → [1, l] such that ui ' vσ(i) for all i ∈ [1, k]. Then it is clear that φ(ui ) ' φ(vσ(i) ) for all i ∈ [1, k]. Since φp (z) = [φ(ε)φ(u1 ) ∗ · · · ∗ φ(uk )]p and φp (z 0 ) = [φ(η)φ(v1 ) ∗ · · · ∗ φ(vl )]p , we have φp (z) |p φp (z 0 ). Now suppose that φ(z) |p φ(z 0 ). Again k ≤ l and there exists an injective map σ : [1, k] → [1, l] such that φ(ui ) ' φ(vσ(i) ) in T . Since φ is isoatomic, ui ' vσ(i) and hence z |p z 0 . (2) Note that a |p b if and only if there exist z ∈ Zp (a) and z 0 ∈ Zp (b) such that z |p z 0 . Since φp restricted to Zp (a) → Zp (φ(a)), respectively Zp (b) → Zp (φ(b)), is surjective by Lemma 3.10(2), the claim follows from (1). (3) Let H and T be semigroups. Suppose first that a |p u1 · · · un for n ∈ N0 and atoms u1 , . . . , un of H. Then φ(a) |p φ(u1 ) · · · φ(un ) by (2). Thus there exists k ∈ [0, n] and an injective map σ : [1, k] → [1, n] such that φ(a) |p φ(uσ(1) ) · · · φ(uσ(k) ) = φ(uσ(1) · · · uσ(k) ), where the product uσ(1) · · · uσ(k) is defined since H is a semigroup. Again by (2), a |p uσ(1) · · · uσ(k) , showing ω(H, a) ≤ ω(T, φ(a)). Let T be commutative. Now suppose that φ(a) |p v1 · · · vn for n ∈ N0 and atoms v1 , . . ., vn of T . Since φ is a weak transfer homomorphism, there exist atoms u1 , . . . , un of H such that φ(ui ) ' vi for all i ∈ [1, n]. Since H is a semigroup, the product u1 · · · un is defined and, since T is a commutative semigroup, φ(u1 · · · un ) ' v1 · · · vn . Therefore φ(a) |p φ(u1 · · · un ), and we have a |p u1 · · · un by (2). Thus, there exists k ∈ [0, n] and an injective map σ : [1, k] → [1, n] with a |p uσ(1) · · · uσ(k) . Then φ(a) |p φ(uσ(1) ) · · · φ(uσ(k) ) by (2) again, and hence φ(a) |p vσ(1) · · · vσ(k) (for this we use the commutativity of T again). Thus ωp (T, φ(a)) ≤ ωp (H, a). Since T = T × φ(H)T × , it follows that ωp (H) = ωp (T ). (4) The proof of (4) is analogous to that of (3). (5) We first show tp (a, x) ≤ tp (φ(a), φp (x)). Let z ∈ Zp (a) and suppose there exists z0 ∈ Zp (a) such that x |p z0 . Then φp (x) |p φp (z0 ) by (1), and φp (z0 ) ∈ Zp (φ(a)). Thus there exists z 0 ∈ Zp (φ(a)) with φp (x) |p z 0 and dp (z 0 , φp (z)) ≤ tp (φ(a), φp (x)). Since the restriction of φp to Zp (a) → Zp (φ(a)) is surjective, there exists z 0 ∈ Zp (a) such that φp (z 0 ) = z 0 . Since φ is isoatomic, Proposition 4.8 implies dp (z 0 , z) = dp (φp (z 0 ), φp (z)) ≤ tp (φ(a), φp (x)). Moreover, (1) implies x |p z 0 and thus we have tp (a, x) ≤ tp (φ(a), φp (x)). 28 N. BAETH AND D. SMERTNIG We now show tp (φ(a), φp (x)) ≤ tp (a, x). Suppose that z ∈ Zp (φ(a)) and there exists z 0 ∈ Zp (φ(a)) such that φp (x) |p z 0 . Again, there exist z, z0 ∈ Zp (a) such that φp (z) = z and φp (z0 ) = z 0 . Then x |p z0 and thus there exists z 0 ∈ Zp (a) such that dp (z 0 , z) ≤ tp (a, x) and x |p z 0 . Hence dp (φ(z 0 ), φ(z)) = dp (z 0 , z) ≤ tp (a, x) and φp (x) |p φp (z 0 ), proving the claim. Since T = T × φ(H)T × , it follows that tp (H) = tp (T ). Corollary 5.24. Let H be a cancellative semigroup possessing an isoatomic weak transfer homomorphism to a commutative atomic cancellative semigroup. Then (1) ρ(b) ≤ sup L(b) ≤ ωp (H, b) for all b ∈ H, (2) ωp (H, u) ≤ tp (H, u) if u ∈ A(H) is not an almost prime-like element, (3) ρ(H) ≤ ωp (H) ≤ tp (H) unless tp (H) = 0, and (4) cp (H) ≤ tp (H). Proof. These inequalities hold whenever H is a commutative semigroup, and hence, by the previous proposition, they also hold if H possesses an isoatomic weak transfer homomorphism to a commutative atomic cancellative semigroup. The next examples show that the inequalities in the previous corollary fail to hold in general. Example 5.25. (1) Let S = ha, b, c | ban−1 = an−1 ci for some n ∈ N≥2 . Since a is almost prime-like, we have tp (a) = 0. Moreover, tp (b) = tp (c) = 1 and thus tp (S) = 1. However, ωp (S, a) = 1, ωp (S, b) = ωp (S, c) = n, and hence ωp (S) = n. (2) Let S = ha, b | ab = ban−1 i, where n ∈ N≥2 . Since a and b are almost prime-like, tp (S, a) = tp (S, b) = 0, whence tp (S) = 0. Similarly ωp (S, a) = ωp (S, b) = 1 and ω(S) = 1. However, it is clear that ρ(S) = n/2. Moreover, Z∗ (am b) = {am ∗ b, am−1 ∗ b ∗ an−1 , . . . , b ∗ am(n−1) }, and hence L(am b) = { m + 1 + k(n − 2) : k ∈ [0, m] }. Thus sup L(am b) = m(n − 1) + 1 and ρ(am b) = m(n−1)+1 , while ωp (S, am b) = m + 1. Finally, cp (am b) = n − 2, and hence cp (S) ≥ n − 2. m+1 6. The abelianization of a noncommutative semigroup In this section we study when the natural homomorphism π : S → Srab from a cancellative semigroup to its reduced abelianization is a weak transfer homomorphism. A necessary and sufficient condition is given in Proposition 6.7 where we also see that whenever π is a weak transfer homomorphism it must be isoatomic. In Proposition 6.12 we show that in this case π satisfies a universal property with regards to weak transfer homomorphisms into commutative reduced cancellative semigroups. Finally, we give applications to the semigroup of non zero-divisors of the ring of n × n upper triangular matrices over a commutative atomic domain, and the semigroup of non zero-divisors of the ring of n × n matrices over a PID. Definition 6.1. Let S be a semigroup and let ≡ab be the smallest congruence relation on S such that ab ≡ab ba for all a, b ∈ S. (1) The abelianization of S is the pair (Sab , π) consisting of Sab = S/≡ab together with the canonical homomorphism π : S → Sab . (2) The reduced abelianization of S is the pair (Srab , π) consisting of Srab = (Sab )red together with the canonical homomorphism π : S → Srab . We denote the corresponding congruence on S by ≡rab . Remark 6.2. (1) Explicitly, the congruence ≡ab is given as follows: Let a, b ∈ S. Then a ≡ab b if and only if there exist m ∈ N and, for each i ∈ [1, m], ki ∈ N and ci,j ∈ S for j ∈ [1, ki ] as well as a permutation σi ∈ Ski such that: a = c1,1 · · · c1,k1 , c1,σ1 (1) · · · c1,σ1 (k1 ) = c2,1 · · · c2,k2 , (6.1) .. . cm−1,σm−1 (1) · · · cm−1,σm−1 (km−1 ) = cm,1 · · · cm,km , cm,σm (1) · · · cm,σm (km ) = b. (2) The abelianization (Sab , π) satisfies the following universal property: Let T be any commutative semigroup, and let φ : S → T be a semigroup homomorphism. Then there exists a unique homomorphism φ : Sab → T such that φ = φ ◦ π. FACTORIZATION THEORY: FROM COMMUTATIVE TO NONCOMMUTATIVE SETTINGS 29 (3) The reduced abelianization (Srab , π) satisfies the following universal property: Let T be any commutative reduced semigroup, and let φ : S → T be a semigroup homomorphism. Then there exists a unique homomorphism φ : Srab → T such that φ = φ ◦ π. If associativity is a congruence relation on S, then (Sred )ab together with a canonical homomorphism π 0 : S → (Sred )ab is defined. Again we see that every homomorphism S → T to a commutative reduced semigroup factors through π 0 in a unique way. Therefore ((Sred )ab , π 0 ) satisfies the same universal property as (Srab , π) and hence the two semigroups must be canonically isomorphic. We identify Srab and (Sred )ab by means of this isomorphism. Lemma 6.3. Let S be a cancellative semigroup, Sab its abelianization, and denote by π : S → Sab the canonical homomorphism. Suppose that Sab is also cancellative. (1) We have π −1 (Sab × ) = S × . (2) Let a ∈ S. Then a ∈ A(S) if and only if π(a) ∈ A(Sab ). (3) If u ∈ A(S), then [u]' = π −1 ([π(u)]' ). × × Proof. (1) Clearly S × ⊂ π −1 (Sab ). Now let a ∈ S be such that π(a) ∈ Sab . Then there exists b ∈ S such that π(a)π(b) = 1, and hence ab ≡ab 1. Using notation as in Equation (6.1), with a replaced by ab and b replaced by 1, we see that cm,σm (1) · · · cm,σm (km ) = 1 for some ci,j in S. Hence, for all j ∈ [1, km ], we have cm,σm (j) ∈ S × . Continuing inductively, ci,j ∈ S × for all i ∈ [1, m] and j ∈ [1, ki ], and hence ab ∈ S × . Therefore a ∈ S × . (2) Suppose a ∈ S \ S × is not an atom. Then a = bc with b, c ∈ S \ S × and (1) implies π(b), π(c) ∈ Sab \ Sab × . Hence π(a) = π(b)π(c) is not an atom. Conversely, suppose π(a) ∈ S \ A(S). If π(a) ∈ Sab × , then a ∈ S × , and hence we may assume that π(a) is not a unit. Since π(a) is not an atom, there exist b, c ∈ Sab \ Sab × such that π(a) = bc. Since π is surjective, there exist b, c ∈ S \ S × such that π(b) = b and π(c) = c. Thus a ≡ab bc. Using the notation of Equation (6.1) to write out this relation, it follows inductively that for all i ∈ [1, m], ci,1 · · · ci,ki is not an atom. Therefore a is not an atom. (3) If a ∈ S with u ' a, then π(u) ' π(a). For the converse direction suppose π(u) ' π(a). It suffices to show u ' a. Let m ∈ N, and ki ∈ N, ci,j ∈ S for all i ∈ [1, m], j ∈ [1, ki ] be as in Equation (6.1). Since u is an atom and u = c1,1 · · · c1,k1 , there exists some j1 ∈ [1, k1 ] such that c1,j1 is an atom, and c1,j ∈ S × for all j ∈ [1, k1 ] \ {j1 }. In particular, u ' c1,j1 . Inductively it follows that for all i ∈ [2, m], there exists ji ∈ [1, ki ] such that ci,ji ∈ A(S) and ci,j ∈ S × for all j ∈ [1, ki ] \ {ji }, and therefore ci−1,ji−1 ' ci,ji . It follows that u ' cm,jm ' a. Remark 6.4. (1) Replacing Sab by Srab in Lemma 6.3, and assuming that Srab is cancellative, we obtain the corresponding statements of the lemma for Srab . (2) Suppose S is in fact a group. Then, by Lemma 6.3(1), Sab is a group. Using the universal property of the abelianization it follows that Sab satisfies the universal property of the abelianization of S as a group. Thus, in this case, Sab is the just the usual abelianization of a group. Definition 6.5. Let S be a semigroup. We define a relation ≡p on S as follows: For a, b ∈ S we set a ≡p b if and only if there exist m ∈ N0 and a1 , . . . , am , b1 , . . . , bm ∈ S such that a ' a1 · · · am , b ' b1 · · · bm and there exists a permutation σ ∈ Sm such that ai ' bσ(i) for all i ∈ [1, m]. If S is atomic, the a1 , . . . , am and b1 , . . . , bm in the definition of ≡p can equivalently be taken to be atoms. In this case, the definition may equivalently be stated as: a ≡p b if and only if there exist rigid factorizations z of a and z 0 of b such that dp (z, z 0 ) = 0. The relation ≡p is obviously reflexive and symmetric, but may not be transitive. If a ' b, then clearly a ≡p b. Lemma 6.6. Let S be a semigroup. The following statements are equivalent. (1) ≡p is transitive. (2) ≡p is a congruence relation. (3) ≡p = ≡rab . Proof. (1) ⇒ (2): The relation is symmetric and reflexive, and since we assume transitivity it is therefore an equivalence relation. Thus we must show that for all a, a0 , b, b0 ∈ S, if a ≡p a0 and b ≡p b0 , then ab ≡p a0 b0 . Since a ≡p a0 , there exist m ∈ N0 , a permutation σ ∈ Sm , and elements a1 , . . . am , a01 , . . . , a0m ∈ S such that a ' a1 · · · am , a0 ' a01 · · · a0m and ai ' a0σ(i) for all i ∈ [1, m]. Similarly, there exist n ∈ N0 , a permutation τ ∈ Sn , and elements b1 , . . . bn , b01 , . . . , b0n ∈ S such that b ' b1 · · · bn , b0 ' b01 · · · b0n and bi ' b0τ (i) for all i ∈ [1, n]. 30 N. BAETH AND D. SMERTNIG If m = 0, then a, a0 ∈ S × and thus ab ' b and a0 b0 ' b0 . Therefore ab ≡p a0 b0 . We argue analogously if n = 0, and may now assume m, n > 0. Without loss of generality, we replace a1 , am , a01 , a0m , b1 , bn , b01 , and b0n by associates such that a = a1 · · · am , a0 = a01 · · · a0m , b = b1 · · · bn , and b0 = b01 · · · b0n . Then ab = (a1 · · · am )(b1 · · · bn ) and a0 b0 = (a01 · · · a0m )(b01 · · · b0n ), each written as a product of m + n atoms of S. Moreover, applying the permutation (σ, τ ), interpreted accordingly as a permutation on [1, m + n], we see that ab ≡p a0 b0 and hence ≡p is a congruence relation on S. (2) ⇒ (3): Let a, b ∈ S. If a ≡p b, then a ≡rab b. From the definition of ≡p it follows that ab ≡p ba. Thus ≡ab ⊂ ≡p ⊂ ≡rab and moreover, S/ ≡p is reduced. Since ≡rab is the minimal congruence containing ≡ab with respect to being reduced, and by assumption ≡p is indeed a congruence, it follows that ≡p = ≡rab . (3) ⇒ (1): Clear, since ≡rab is transitive. Proposition 6.7. Let S be a cancellative semigroup and suppose that Srab is also cancellative. The following statements are equivalent. (1) If a, b ∈ S are such that a ≡p b and a ' u1 · · · um with m ∈ N0 and u1 , . . . , um ∈ A(S), then there exist v1 , . . . , vm ∈ A(S) and a permutation σ ∈ Sm such that b ' v1 · · · vm and ui ' vσ(i) for all i ∈ [1, m]. (2) The canonical homomorphism π : S → Srab is a weak transfer homomorphism. (3) The canonical homomorphism π : S → Srab is an isoatomic weak transfer homomorphism. Moreover, each of (1) to (3) imply the equivalent conditions given in Lemma 6.6. Proof. We first show that (1) implies Lemma 6.6(1). Let a, b, c ∈ S be such that a ≡p b and b ≡p c. By the definition of ≡p there exist m ∈ N0 , u1 , . . . , um , v1 , . . . , vm ∈ A(S) and a permutation σ ∈ Sm such that a ' u1 · · · um , b ' v1 · · · vm and ui ' vσ(i) for all i ∈ [1, m]. By (1) and since b ≡p c, there exist w1 , . . . , wm ∈ A(S) and a permutation τ ∈ Sm such that c ' w1 · · · wm and vi ' wτ (i) for all i ∈ [1, m]. Then ui ' vσ(i) ' wτ (σ(i)) for all i ∈ [1, m], and hence a ≡p c. (1) ⇒ (2): Property (T1) of Definition 2.1(2) holds since π is surjective and by applying Lemma 6.3(1). It remains to verify property (WT2) of a weak transfer homomorphism. Let a ∈ S, let m ∈ N, and let v1 , . . . , vm ∈ A(Srab ) such that π(a) = v1 · · · vm . By the surjectivity of π, there exist u01 , . . . , u0m ∈ S such that π(u0i ) = vi for all i ∈ [1, m], and by Lemma 6.3(2) u0i ∈ A(S) for all i ∈ [1, m]. We thus have π(a) = π(u01 · · · u0m ), whence a ≡rab u01 · · · u0m . Since we have already established that (1) implies the equivalent conditions of Lemma 6.6, ≡rab =≡p . Hence a ≡p u01 · · · u0m , and thus there exist u1 , . . . , um ∈ A(S) and a permutation σ ∈ Sm such that a ' u1 · · · um with ui ' u0σ(i) for all i ∈ [1, m]. Then π(a) = π(u1 ) · · · π(um ) and π(ui ) = π(u0σ(i) ) = vσ(i) . (2) ⇒ (3): By Lemma 6.3(3), π : S → Srab is isoatomic. (3) ⇒ (1): Let a, b ∈ S with a ≡p b, m ∈ N0 , and u1 , . . . , um ∈ A(S) with a ' u1 · · · um . By the definition of ≡p there exist n ∈ N0 and u01 , . . . , u0n , v10 , . . . , vn0 ∈ A(S) as well as a permutation τ ∈ Sn such that a ' u01 · · · u0n , b ' v10 · · · vn0 and u0i ' vτ0 (i) for all i ∈ [1, n]. Since a ≡p b implies a ≡rab b, π(u1 ) · · · π(um ) = π(a) = π(b), and, by Lemma 6.3(2), π(ui ) ∈ A(Srab ) for all i ∈ [1, m]. Since π is a weak transfer homomorphism, there exist v1 , . . . , vm ∈ A(S) and a permutation σ ∈ Sm such that b ' v1 · · · vm and π(vσ(i) ) ' π(ui ) for all i ∈ [1, m]. By Lemma 6.3(3), vσ(i) ' ui for each i ∈ [1, m]. We now illustrate that the equivalent statements of Proposition 6.7 can fail to hold for a semigroup S even if there is a transfer homomorphism from S to a commutative reduced cancellative semigroup T . Example 6.8. Let S = ha, b, c, d | ab = cdi. Clearly S is reduced and is an Adyan semigroup, whence S is cancellative. Then Sab is the free abelian monoid F({α, β, γ, δ}) modulo the congruence relation generated by αβ = γδ, with the canonical homomorphism π : S → Sab being defined by π(a) = α, π(b) = β, π(c) = γ, π(d) = δ. We have π(ab) = αβ = γδ = δγ = π(dc), but the two possible permutable factorizations of ab in S are [a ∗ b]p and [c ∗ d]p , while dc only has the factorization [d ∗ c]p . Therefore the factorization [α ∗ β]p of π(dc) does not lift, and thus π is not a weak transfer homomorphism. However, from the relation imposed, it is clear that there exists a length function ` : S → N0 mapping each of a, b, c and d to 1. The map ` is a transfer homomorphism from S to the commutative semigroup (N0 , +). Thus a noncommutative semigroup may possess a (weak) transfer homomorphism to a commutative semigroup even when the canonical map to the reduced abelianization is not a (weak) transfer homomorphism. The following proposition shows that, if S is a cancellative semigroup with Srab cancellative, the existence of an isoatomic weak transfer homomorphism from S to a commutative cancellative semigroup however does imply that the canonical homomorphism S → Srab is a weak transfer homomorphism, and thus that FACTORIZATION THEORY: FROM COMMUTATIVE TO NONCOMMUTATIVE SETTINGS 31 the equivalent conditions of Proposition 6.7 are satisfied. We note that the transfer homomorphism ` from Example 6.8 is not isoatomic. Proposition 6.9. Let S be a cancellative semigroup. Assume that T is a commutative atomic cancellative semigroup and that there exists an isoatomic weak transfer homomorphism φ : S → T . Then Srab is cancellative, the canonical homomorphism π : S → Srab is an isoatomic weak transfer homomorphism, and φ induces an isomorphism Srab ∼ = Tred . ∼ Proof. It suffices to show that φ induces an isomorphism φrab : Srab → Tred . Then Srab is cancellative, and since φ is an isoatomic weak transfer homomorphism and φrab is an isomorphism, π = φ−1 rab ◦ φ is an isoatomic weak transfer homomorphism. We may, without loss of generality, assume that T is reduced. Since T is commutative, φ factors through π, that is, there exists φrab : Srab → T such that φrab ◦ π = φ. Since T = T × φ(S)T × = φ(S), the induced map φrab is surjective. It remains to show that φrab is injective. Let a, b ∈ Srab be such that φrab (a) = φrab (b), and let a, b ∈ S be such that π(a) = a and π(b) = b. We may assume a 6= 1, and hence a 6∈ S × . We have φ(a) = φ(b) and, by (T1), φ(a) 6= 1. Thus there exist m ∈ N and atoms w1 , . . . , wm ∈ A(T ) such that φ(a) = w1 · · · wm . By (WT2), there exist u1 , . . . , um ∈ A(S), v1 , . . . , vm ∈ A(S) and permutations σ, τ ∈ Sm such that a = u1 · · · um , b = v1 · · · vm and wi = φ(uσ(i) ) = φ(vτ (i) ) for all i ∈ [1, m]. Since φ is isoatomic, uσ(i) ' vτ (i) for all i ∈ [1, m]. Since Srab is commutative and reduced, we have π(a) = π(u1 ) · · · π(um ) = π(uσ(1) ) · · · π(uσ(m) ) = π(vτ (1) ) · · · π(vτ (m) ) = π(v1 ) · · · π(vm ) = π(b), that is, a = b. Remark 6.10. Let S be an atomic cancellative semigroup and let R be a set of representatives for the associativity classes of A(S). Suppose that the equivalent conditions of Proposition 6.7 are satisfied. In this case we can give a construction of Srab in terms of the free abelian monoid F(R). We define a relation ≡S on F(R) as follows: We set 1 ≡S 1 and, for a, b ∈ F(R) \ {1}, we set a ≡S b if and only if there exist k, l ∈ N and u1 , . . . , uk , v1 , . . . , vl ∈ R such that a = u1 · · · uk , b = v1 · · · vl and, for all i ∈ [1, k] and j ∈ [1, l], there exist associated atoms u0i ' ui and vj0 ' vj in S, and permutations σ ∈ Sk and τ ∈ Sl such that u0σ(1) · · · u0σ(k) ' vτ0 (1) · · · vτ0 (l) in S. Since we are assuming that the canonical homomorphism to Srab is a weak transfer homomorphism, it is easy to check that ≡S is transitive. Trivially, ≡S is reflexive and symmetric and thus also a congruence relation. For any x ∈ F(R), we write [x] for its image in F(R)/ ≡S . Let a ∈ S and let k, l ∈ N0 and u01 , . . . , u0k , v10 , . . . , vl0 ∈ A(S) be such that a ' u01 · · · u0k ' v10 · · · vl0 , and, for all i ∈ [1, k] and j ∈ [1, l], let ui ∈ R and vj ∈ R be such that ui ' u0i and vi ' vj0 . From the definition of ≡S it is then clear that u1 · · · uk ≡S v1 · · · vl , and thus we can define a map π : S → F(R)/ ≡S , a 7→ [u1 · · · uk ] (with units mapping to [1]). It is now straightforward to check that π is a homomorphism and that (F(R)/ ≡S , π) satisfies the universal property of the reduced abelianization. Therefore F(R)/ ≡S ∼ = Srab . The following example illustrates that not every atomic cancellative semigroup possesses a weak transfer homomorphism into a commutative semigroup. Example 6.11. Let S = ha, b, c, d, e | abc = dei. Then L(abc) = {2, 3}, while L(bac) = {3}. Hence S does not admit a weak transfer homomorphism into any commutative semigroup. The next proposition shows that if Srab is cancellative, then every weak transfer homomorphism to a commutative reduced cancellative semigroup factors through the canonical homomorphism π : S → Srab . If, moreover, π is a weak transfer homomorphism, then we obtain as an immediate corollary a universal property that characterizes the weak transfer homomorphism π. Proposition 6.12. Let S be a cancellative semigroup with Srab cancellative and let π : S → Srab denote the canonical homomorphism. Suppose that there exists a weak transfer homomorphism φ : S → T to a commutative atomic cancellative semigroup T . Let πred : T → Tred denote the canonical homomorphism. Then there exists a unique transfer homomorphism φrab : Srab → Tred such that πred ◦ φ = φrab ◦ π. In particular, if π is a weak transfer homomorphism, it satisfies the following universal property: If φ : S → T is a weak transfer homomorphism from S to a commutative reduced cancellative semigroup T , then there exists a unique transfer homomorphism φrab : Srab → T such that φrab ◦ π = φ, that is, the 32 N. BAETH AND D. SMERTNIG following diagram commutes. S π φ //T == ∃! φrab Srab Proof. Replacing φ by πred ◦ φ if necessary, we may without loss of generality assume that T is reduced. Since T is commutative and reduced, φ factors through π : S → Srab , that is, there exists a homomorphism φrab : Srab → T such that φ = φrab ◦ π. Clearly, φrab is uniquely determined by this relation, and it remains to show that it is a transfer homomorphism. Since T is atomic, and Srab is commutative, it suffices to show that φrab is a weak transfer homomorphism. Since φ is a weak transfer homomorphism, we have T = φ(S)T × = φ(S) and φ−1 (T × ) = S × , with × T = {1}. The first property immediately implies T = φrab (Srab ). We now show φ−1 rab ({1}) = {1}. Trivially φrab (1) = 1. For the other inclusion, suppose that a ∈ Srab is such that φrab (a) = 1. There exists a ∈ S such that π(a) = a, and hence φ(a) = φrab (a) = 1. Thus a ∈ S × and therefore a = π(a) = 1 in Srab . Hence φrab satisfies (T1). We now check (WT2). Let a ∈ Srab and suppose φrab (a) = w1 · · · wm with m ∈ N, w1 , . . . , wm ∈ A(Tred ). Let a ∈ π −1 ({a}). Since φ is a weak transfer homomorphism, there exist atoms u1 , . . . , um ∈ A(S) and a permutation σ ∈ Sm such that a = u1 · · · um and φ(ui ) = wσ(i) for each i ∈ [1, m]. Now π(ui ) ∈ A(Srab ) and φrab ◦ π(ui ) = φ(ui ) = wσ(i) for each i ∈ [1, m]. Therefore φrab is a weak transfer homomorphism. Examples. We now highlight some examples in which the canonical homomorphism to the reduced abelianization is a weak transfer homomorphism. Rings of Triangular Matrices. Let D be a commutative atomic domain, let n ∈ N, and let R = Tn (D) denote the ring of all n × n upper triangular matrices with entries in D. We study S = Tn (D)• , the multiplicative subsemigroup of non zero-divisors of R consisting of those upper triangular matrices having nonzero determinant. Sets of lengths in this semigroup were studied extensively in [BBG14] where the homomorphism ( δ: Tn (D)• [ai,j ]i,j∈[1,n] → (D• red )n 7→ (ai,i D× )i∈[1,n] , mapping a matrix to the vector of associativity classes of its diagonal entries, was shown to be a weak transfer homomorphism. We now give a lemma which illustrates that δ is, in fact, isoatomic. Moreover we show that associativity, similarity and subsimilarity coincide for atoms of S. Lemma 6.13. Let D be a commutative atomic domain and let A(D) denote a set of representatives for the associativity classes of atoms of D. Let n ∈ N and R = Tn (D). (1) An element A = [ai,j ] ∈ Tn (D)• is an atom if and only if there exists m ∈ [1, n] such that ai,i ∈ D× for all i ∈ [1, n] with i 6= m and am,m ∈ A(D). (2) If A is an atom of Tn (D)• with det(A) associated to a ∈ A(D), then A is associated to the matrix B = [bi,j ] ∈ Tn (D)• where if i = j and (i, j) 6= (m, m), 1 bi,j = a if i = j = m, 0 if i 6= j, and a is the representative of a in A(D). (3) If A is an atom of Tn (D)• , and m ∈ [1, n] is such that the m-th diagonal entry of A is a ∈ A(D), then (6.2) annR (R/RA) = { [bi,j ] ∈ Tn (D) : bi,j ∈ aD for all i, j ∈ [1, m] }. (4) For A, B ∈ A(Tn (D)• ), the following statements are equivalent. (a) A is associated to B. (b) A is similar to B. (c) A is subsimilar to B. (d) annR (R/RA) = annR (R/RB). In particular, dp = dsubsim = dsim on Tn (D)• . FACTORIZATION THEORY: FROM COMMUTATIVE TO NONCOMMUTATIVE SETTINGS 33 Proof. Let S = Tn (D)• . The claim in (1) follows from the fact that δ is a weak transfer homomorphism. (2) We denote by In the n × n identity matrix and, for all i, j ∈ [1, n], by Ei,j the n × n matrix with 1 in the (i, j) position, and 0 in all other positions. By (1) there exists an m ∈ [1, n] such that ai,i is a unit of D for all i ∈ [1, n] with i = 6 m, while am,m ∈ A(S). Let a be the element of A(S) that is associated to am,m . Consider the diagonal matrix U= aa−1 m,m Em,m + n X • a−1 i,i Ei,i ∈ Tn (D) . i=1 i6=m Then, A0 = U A = [a0i,j ] ∈ Tn (D)• , with a0m,m = a, and all other diagonal entries equal to 1. Since A is associated to U A and associativity is transitive, we may assume for the remainder of this proof that A = A0 , that is, all but one of the diagonal entries of A are 1 and that the non-unit diagonal entry am,m is already in the pre chosen set A(D). We now define a sequence of associates of A inductively, successively eliminating rows and columns of A. (i−1) Set A(0) = A. For all i ∈ [1, m − 1], assuming that A(i−1) = [ak,l ], let n X Ci = In − (i−1) ai,j Ei,j . j=i+1 Clearly Ci ∈ Tn (D)× , and we set A(i) = A(i−1) Ci , that is, A(i) is obtained from A(i−1) by eliminating the i-th row (except for the diagonal entry). Setting now A(m) = A(m−1) , we inductively define, for all (j−1) j ∈ [m + 1, n], a matrix A(j) ∈ S: Assuming that A(j−1) = [ak,l ], let C j = In − j−1 X (j−1) ai,j Ei,j . i=1 Again Cj ∈ Tn (D)× , and we set A(j) = Cj A(j−1) , that is, A(j) is obtained from A(j−1) by eliminating the j-th column (except for the diagonal entry). The final matrix A(n) = [bk,l ] is therefore diagonal, with bm,m = am,m , and bi,i = 1 for all i ∈ [1, n] \ {m}. Therefore A is associated to a diagonal matrix as desired. (3) We first recall a description of the ideals of Tn (D). For all i ∈ [1, n] and j ∈ [i, n] let Ii,j be an ideal of D, and suppose that Ii,j ⊂ Ii−1,j for all j ∈ [1, n] and i ∈ [2, j], and that Ii,j ⊂ Ii,j+1 for all j ∈ [1, n − 1] and i ∈ [1, j]. An elementary calculation shows that I = [ai,j ] ∈ Tn (D) : ai,j ∈ Ii,j for all i ∈ [1, n], j ∈ [i, n] is an ideal of R, and it is easy to check that in fact every ideal of R is of this form. Let A ∈ A(S). We will show that Equation (6.2) holds. Since R/RA ∼ = R/RA0 for all A0 ∈ R with 0 A ' A, we may assume without restriction (by (2)), that all off-diagonal entries of A are zero, and that there exist m ∈ [1, n] and a ∈ A(D) such that the m-th diagonal entry of A is equal to a, while all other diagonal entries are equal to 1. It is then easy to check that RA consists of all those n × n upper triangular matrices for which the entries of the m-th column are contained in aD. Therefore all elements of the right-hand side of Equation (6.2) annihilate R/RA. Recall that annR (R/RA) is a two-sided ideal of R necessarily contained in RA. By our description of ideals of R, the set on the right hand side of Equation (6.2) is an ideal of R, and moreover the maximal two-sided ideal of R contained in RA. Thus it must be the annihilator of R/RA and we have established the claim. (4) The implications (a) ⇒ (b) ⇒ (c) ⇒ (d) are immediate from the definitions. (d) ⇒ (a): Let A, B ∈ A(S) be such that annR (R/RA) = annR (R/RB). There exist k, l ∈ [1, n] and a, b ∈ A(D) such that the k-th diagonal entry of A is u, the l-th diagonal entry of B is v and all other diagonal entries of A and B are units. To show A ' B, we need to show that k = l and a ' b in D (using (2)). From the description of annihilator ideals in (3), we must have k = l. Comparing the entries in the upper left corner, aD = bD, that is, a ' b. Since δ is isoatomic, it follows from Proposition 6.9 and Lemma 6.13(2) that Srab ∼ = (D• red )n . Proposition 6.14. Let D be a commutative atomic domain, n ∈ N, and S = Tn (D)• . Then cp (S) = csim (S) = csubsim (S) = cp (D• ) and cp,mon (S) = csim,mon (S) = csubsim,mon (S) = cp,mon (D• ). In particular, Tn (D)• is permutably (dsim -, dsubsim -) factorial if only if D is factorial. Moreover, tp (S) = t(D• ) and ωp (S) = ωp (D• ). 34 N. BAETH AND D. SMERTNIG n Proof. From Proposition 4.8 it follows that cp (Tn (D)• ) = cp ((D• red ) ), and [GHK06, Proposition 1.6.8.1] n implies cp ((D• red ) ) = cp (D• red ), the latter of which is trivially equal to cp (D• ). Since Lemma 6.13(4) implies that dp = dsim = dsubsim on Tn (D)• , the remaining equalities for the catenary degrees follow. The claims for the monotone catenary degrees are shown in the same way. The equality tp (S) = t(D• ) follows from Proposition 5.23 together with [GHK06, Proposition 1.6.8.4], and ωp (S) = ω(D• ) follows similarly. Since D is factorial if and only if cp (D• ) = 0 and S is permutably factorial if and only if cp (S) = 0, the final statement follows. Matrix Rings. We now provide an even more straightforward example which illustrates how simple the abelianization of a somewhat complicated-looking noncommutative semigroup S can be. Let D be a commutative principal ideal domain, let n ∈ N, and let S = Mn (D)• denote the multiplicative semigroup of all n × n matrices with entries in D having nonzero determinant. Factorization invariants of this semigroup were studied in [BPA+ 11]. Every A ∈ S can be put into Smith Normal Form, that is, there exist U , V ∈ Mn (D)× and a diagonal matrix C = [ci,j ] ∈ Mn (D)• with ci+1,i+1 dividing ci,i for all i ∈ [1, n − 1] and such that A = U CV . From this it follows immediately that det : Mn (D)• → D• is a transfer homomorphism (cf. [BPA+ 11, Lemma 2.2]). Therefore A is an atom if and only if c1,1 ∈ A(D) and ci,i ∈ D× for all i ∈ [2, n]. Hence the transfer homomorphism is isoatomic, and thus Srab ∼ = D• red by Proposition 6.9. As in Tn (D), in R = Mn (D) the notions of associativity, similarity and subsimilarity coincide (if A ∈ S is an atom with Smith Normal Form C as above, then annR (R/RA) = annR (R/RC) = Rc1,1 , implying as for the ring of n × n upper triangular matrices, that two atoms with the same annihilator are associated), and thus results analogous to Proposition 6.14 hold. Almost Commutative Semigroups. Recall that if S is a cancellative semigroup on which associativity is a congruence relation and for which Sred is cancellative, the canonical homomorphism π : S → Sred is always an isoatomic transfer homomorphism. However, this is only useful to us if Sred is a semigroup that we understand better than S itself. In this example we consider the case where Sred is commutative. We say that a semigroup S is almost commutative if ab ' ba for all a, b ∈ S. Proposition 6.15. Let S be a semigroup on which ' is a congruence relation. (1) The following statements are equivalent: (a) S is almost commutative. (b) Sred is commutative. (2) Suppose S is almost commutative, and that S and Sred are cancellative. Then Sred = Srab , and the canonical homomorphism π : S → Sred is an isoatomic transfer homomorphism to a commutative reduced cancellative semigroup. Proof. (1) (a) ⇒ (b): Let a, b ∈ Sred and let a, b ∈ S be such that π(a) = a and π(b) = b. Then ab = π(ab) = π(ba) = ba, where the middle equality holds since ab ' ba. (b) ⇒ (a): Let a, b ∈ S. Then π(ab) = π(a)π(b) = π(b)π(a) = π(ba), and hence ab ' ba. (2) The homomorphism π is always an isoatomic transfer homomorphism, and hence it suffices to show that Sred = Srab . By (1), Sred is commutative, whence Sred = (Sred )ab , but we have identified (Sred )ab = Srab . Let S be a normalizing Krull monoid. Then Sred embeds into a free abelian monoid (as a consequence of [Ger13, Lemma 4.6 and Theorem 4.13]), and hence is itself commutative, and in fact a commutative Krull monoid. Thus normalizing Krull monoids are almost commutative, with their associated reduced monoids being commutative Krull monoids that have been well-investigated. We can expect factorization theoretic results about Sred to immediately carry over to S. For instance, we have the following. Proposition 6.16. Let S be a normalizing Krull monoid. Then, for all a ∈ S, ωp (S, a) < ∞ and ωp0 (S, a) < ∞. Proof. Since Sred is a commutative Krull monoid, we have ωp0 (Sred , a) = ωp (Sred , a) < ∞ for all a ∈ Sred by [GH08, Theorem 4.2]. The canonical homomorphism π : S → Sred = Srab from S to its reduced abelianization is an isoatomic transfer homomorphism, and thus the same holds true for S by Proposition 5.23. We conclude this section by giving a construction of another family of semigroups which are almost commutative. FACTORIZATION THEORY: FROM COMMUTATIVE TO NONCOMMUTATIVE SETTINGS 35 Example 6.17. Let T be a commutative reduced cancellative semigroup and let G be a group. Further suppose that there is an action ·:T ×G→G of T on G such that the following two additional conditions hold: (1) for each t ∈ T and all pairs g1 , g2 ∈ G, t · (g1 g2 ) = (t · g1 )(t · g2 ), and (2) for each t ∈ T and all pairs g1 , g2 ∈ G, t · g1 = t · g2 implies g1 = g2 . (Equivalently, there is a homomorphism T → Mono(G) given by t 7→ (g 7→ t · g), with Mono(G) denoting the semigroup of monomorphisms of G.) The semidirect product S = G o T is the semigroup defined on the cartesian product G × T by the operation (g1 , t1 )(g2 , t2 ) = (g1 (t1 · g2 ), t1 t2 ). The identity element of this semigroup is (1G , 1T ) and, since T is reduced, S × = { (g, 1T ) ∈ S : g ∈ G }. S is cancellative: Suppose that g1 , g2 , g3 ∈ G and t1 , t2 , t3 ∈ T are such that (g1 , t1 )(g2 , t2 ) = (g1 , t1 )(g3 , t3 ). Then t1 t2 = t1 t3 , and due to the cancellativity of T , t2 = t3 . Moreover g1 (t1 · g2 ) = g1 (t1 · g3 ) implies t1 · g2 = t1 · g3 and hence, by (2), g2 = g3 . Suppose that g1 , g2 , g3 ∈ G and t1 , t2 , t3 ∈ T are such that (g2 , t2 )(g1 , t1 ) = (g3 , t3 )(g1 , t1 ). Cancellativity of T again implies t2 = t3 . Then g2 (t2 · g1 ) = g3 (t3 · g1 ) = g3 (t2 · g1 ), and hence g2 = g3 . S is normalizing: Let (g, t) ∈ S. Let (g1 , t1 ) ∈ (g, t)S, with (g2 , t2 ) ∈ S such that (g1 , t1 ) = (g, t)(g2 , t2 ). Then (g(t · g2 )(t2 · g)−1 , t2 ) (g, t) = (g(t · g2 )(t2 · g)−1 (t2 · g), t2 t) = (g(t · g2 ), tt2 ) = (g, t)(g2 , t2 ) = (g1 , t1 ), showing that also (g1 , t1 ) ∈ S(g, t). (We used the commutativity of T to conclude t2 t = tt2 .) A symmetrical argument gives the reverse containment and hence S is normalizing. S is almost commutative: Since S is normalizing, associativity is a congruence relation on S. We claim Sred ∼ = T , and indeed, this follows because, for all g ∈ G and t ∈ T , S × (g, t)S × = S × (g, t) = { (g 0 , t) : g 0 ∈ G }, where the first equality holds because S is normalizing. Since Sred ∼ = T is commutative, S is almost commutative. 7. Maximal orders In this final section we study arithmetical maximal orders and right-saturated subcategories of the integral elements of an arithmetical groupoid. We refer the reader to the corresponding subsection of Section 2 on page 7 for the definition of arithmetical maximal orders (Definition 2.8) and a discussion as to how they relate to Krull monoids and classical maximal orders in central simple algebras over global fields. We show that certain conditions imply the existence of a transfer homomorphism from an arithmetical maximal order to a monoid of zero-sum sequences and that this transfer homomorphism has catenary degree in the permutable fibers at most 2. Thus we obtain Theorem 7.8 and Corollary 7.11 which generalize the corresponding result for commutative Krull monoids. We then apply these results to classical maximal orders R in central simple algebras over global fields satisfying the condition that every stable free left R-ideal is free. Thereby we obtain Theorem 7.12 which gives a description of permutable, dsim - and dsubsim -catenary degrees of R• in terms of the well-studied catenary degree of a monoid of zero-sum sequences over a finite abelian group. Finally we note several immediate corollaries to this theorem. We start by recalling the notion of an arithmetical groupoid, which is useful in describing the divisorial one-sided ideal theory of an arithmetical maximal order (see [Sme13, Section 4] for more details and proofs). Definition 7.1. A lattice-ordered groupoid (G, ≤) is a groupoid G together with a relation ≤ on G such that for all e, f ∈ G0 (1) (G(e, ·), ≤|G(e,·) ) is a lattice (we write ∧0e and ∨0e for the meet and join), (2) (G(·, f ), ≤|G(·,f ) ) is a lattice (we write ∧00f and ∨00f for the meet and join), (3) (G(e, f ), ≤|G(e,f ) ) is a sublattice of both G(e, ·) and G(·, f ). Explicitly: For all a, b ∈ G(e, f ) it holds that a ∧0e b = a ∧00f b ∈ G(e, f ) and a ∨0e b = a ∨00f b ∈ G(e, f ). 36 N. BAETH AND D. SMERTNIG If a, b ∈ G and s(a) = s(b) we write a ∧ b = a ∧0s(a) b and a ∨ b = a ∨0s(a) b. If t(a) = t(b) we write a ∧ b = a ∧00t(a) b and a ∨ b = a ∨00t(a) b. By (3) this is unambiguous if both s(a) = s(b) and t(a) = t(b). The restriction of ≤ to any of G(e, ·), G(·, f ) or G(e, f ) will simply be denoted by ≤ again. An element a of a lattice-ordered groupoid is called integral if a ≤ s(a) and a ≤ t(a), and we write G+ for the subset of all integral elements of G. Definition 7.2. A lattice-ordered groupoid G is called an arithmetical groupoid if it has the following properties for all e, f ∈ G0 : (P1) For a ∈ G, a ≤ s(a) if and only if a ≤ t(a). (P2) G(e, ·) and G(·, f ) are modular lattices. (P3) If a ≤ b for a, b ∈ G(e, ·) and c ∈ G(·, e), then ca ≤ cb. Analogously, if a, b ∈ G(·, f ) and c ∈ G(f, ·), then ac ≤ bc. (P4) For every non-empty subset M ⊂ G(e, ·) ∩ G+ , the supremum sup(M ) ∈ G(e, ·) exists, and similarly for M ⊂ G(·, f ) ∩ G+ . If moreover M ⊂ G(e, f ) then supG(e,·) (M ) = supG(·,f ) (M ). (P5) G(e, f ) contains an integral element. (P6) G(e, ·) and G(·, f ) satisfy the ACC on integral elements. Let G be an arithmetical groupoid. The set of integral elements G+ is a reduced subcategory. An element a ∈ G+ is an atom if and only if it is maximal integral, that is, it is maximal in G+ (s(a), ·) \ {s(a)} (equivalently, in G+ (·, t(a)) \ {t(a)}) with respect to ≤. The category G+ is atomic. The groupoid G is a group if and only if it is free abelian with basis A(G+ ) and, in this case, G+ is the free abelian monoid with basis A(G+ ). For all e ∈ G0 , the group G(e) is a free abelian group and, if f ∈ G0 , then every a ∈ G(e, f ) induces an order-preserving group isomorphism G(e) → G(f ) defined by x 7→ a−1 xa that is independent of the choice of a. For e ∈ G0 and x ∈ G(e) we define (x) = { a−1 xa : a ∈ G(e, ·) }, and we set G = { (x) : x ∈ G(e), e ∈ G0 }. For all e ∈ G0 , the map G(e) → G defined by x 7→ (x) is a bijection, and therefore induces the structure of a free abelian group on G. We note that this structure is independent of the choice of e and we call G the universal vertex group. Moreover, with the order induced from any G(e), G is an arithmetical groupoid. The subsemigroup of integral elements, G+ , is the free abelian monoid on A(G+ ), the maximal integral elements of G+ . In particular, G+ is factorial with set of prime elements A(G+ ). For X ∈ G we denote its unique preimage in G(e) by Xe . Let u ∈ A(G+ ) and let x = sup{x0 ∈ G(s(u)) : x0 ≤ u} ∈ G(s(u)). We define η(u) ∈ G as η(u) = (x) and note that η(u) ∈ A(G+ ). Let a ∈ G+ and s(a)u1 ∗· · ·∗uk ∈ Z∗G+ (a). A key result on the factorization theory of G+ is the following: For all s(a)v1 ∗ · · · ∗ vl ∈ Z∗G+ (a) we have l = k and there exists a permutation σ ∈ Sk such that η(ui ) = η(vσ(i) ) for all i ∈ [1, k] (see [Sme13, Proposition 4.12], noting that Φ(u) = η(u) for u ∈ A(G+ )). Thus we can extend η to a homomorphism G+ → G and further to a surjective homomorphism η : G → G, which we call the abstract norm. We also recall that, given any permutation τ ∈ Sk , there exist w1 , . . . , wk ∈ A(G+ ) such that s(a)w1 ∗ · · · ∗ wk ∈ Z∗G+ (a) and η(ui ) = η(wτ (i) ) for all i ∈ [1, k]. We now fix the following notation which we will tacitly assume up to and including Theorem 7.8. Let G be an arithmetical groupoid and let H ⊂ G+ be a right-saturated subcategory (that is, HH −1 ∩ G+ = H). Let η : G → G be the abstract norm. By q(η(H)) we denote the quotient group of η(H), where we may assume q(η(H)) ⊂ G. We set C = G/q(η(H)) and, for G ∈ G, we set [G] = Gq(η(H)) ∈ C. The abelian group C is a kind of class group and we shall use additive notation for it. Finally, we define CM = { [η(u)] ∈ C : u ∈ A(G+ ) } and note the following lemma. The second statement of the lemma was stated as an assumption in [Sme13, Theorem 4.15], but in fact always holds. Lemma 7.3. We have CM = { [P] : P ∈ A(G+ ) }. Let e ∈ G0 and g ∈ CM . Then there exists an element u ∈ A(G+ ) such that s(u) = e and [η(u)] = g. Proof. If u ∈ A(G+ ), then η(u) ∈ A(G+ ), and therefore CM is contained in { [P] : P ∈ A(G+ ) }. We prove the other inclusion. Let P ∈ A(G+ ) and e ∈ G0 . Since G+ (e, ·) satisfies the ACC by (P6), the set { u0 ∈ G(e, ·) : Pe ≤ u0 < e } possesses a maximal element u ∈ G+ (e, ·). Then u is maximal integral, that is, u ∈ A(G+ ). Since Pe is maximal integral in G(e), it is necessarily the case that η(u) = P. Hence [η(u)] = [P]. Thus CM has the claimed form. The second statement follows similarly, by taking P a representative of g. FACTORIZATION THEORY: FROM COMMUTATIVE TO NONCOMMUTATIVE SETTINGS 37 We write F(CM ) for the free abelian monoid on CM , and B(CM ) for the monoid of zero-sum sequences over CM (see Section 2, page 8). Since G+ is a free abelian monoid, there exists a homomorphism ϕ0 : G+ → F(CM ) such that ϕ0 (P) = [P] for all P ∈ A(G+ ). We denote by ϕ : η(H) → B(CM ) the restriction of ϕ0 to η(H). Explicitly, if X ∈ η(H), then there exist uniquely determined k ∈ N0 and P1 , . . . , Pk ∈ A(G+ ) such that X = P1 · · · Pk , and we have ϕ(X ) = [P1 ] · · · [Pk ] ∈ B(CM ). We define θ : H → B(CM ) as θ = ϕ ◦ η. Thus θ is a homomorphism from H to the monoid of zero-sum sequences over CM given as follows: If a ∈ H and s(a)u1 ∗ · · · ∗ uk ∈ Z∗G+ (a), then θ(a) = [η(u1 )] · · · [η(uk )] (note that the factorization is into maximal integral elements of G, and not into atoms of H). We call θ the block homomorphism of H ⊂ G+ . We will also require the following additional hypothesis: (N) for a ∈ G with s(a) ∈ H0 , we have a ∈ HH −1 if and only if η(a) ∈ q(η(H)). In (N) we may equivalently require t(a) ∈ H0 instead of s(a) ∈ H0 (the equivalence of the two statements follows by considering a−1 ). By [Sme13, Theorem 4.15], θ : H → B(CM ) is a transfer homomorphism if (N) holds, and it is this transfer homomorphism that we ultimately investigate. We now provide two easy combinatorial lemmas that will later be useful to obtain lower bounds on the catenary degree. Lemma 7.4. Suppose that CM = −CM and that every class in CM contains at least two distinct prime elements of G+ . Then c∗ (H) ≥ 2. Proof. Let e ∈ H0 and let P, Q ∈ G+ be two distinct prime elements. By assumption we can choose them such that [P] = [Q]. Let u1 ∈ A(G+ ) with s(u1 ) = e and Pe ≤ u1 , so that η(u1 ) = P. Since CM = −CM , Lemma 7.3 implies that there exists an atom u2 ∈ A(G+ ) such that s(u2 ) = t(u1 ) and [η(u2 )] = −[P]. By hypothesis on CM , we may further assume η(u2 ) 6= Q. Our assumption (N) together with [η(u1 u2 )] = 0 ∈ C implies u1 u2 ∈ HH −1 . Moreover, u1 u2 ∈ G+ and H is right-saturated in G+ , thus u1 u2 ∈ H. Similarly, we construct v1 , v2 ∈ A(G+ ) such that s(v1 ) = t(u2 ), s(v2 ) = t(v1 ), η(v1 ) = Q, and [η(v2 )] = −[Q]. As before, we have v1 v2 ∈ H. By [Sme13, Proposition 4.12.4], there exist u01 , u02 , v10 , v20 ∈ A(G+ ) such that η(u01 ) = P, η(u02 ) = η(u2 ), η(v10 ) = Q, η(v20 ) = η(v2 ) and a = u1 u2 v1 v2 = v10 v20 u01 u02 ∈ H. Again v10 v20 and u01 u02 lie in H. This gives rise to two rigid factorizations of a in H, namely u1 u2 ∗ v1 v2 u1 ∗ u2 ∗ v1 ∗ v2 and v10 v20 ∗ u01 u02 and v10 ∗ v20 ∗ u01 if [P] 6= 0 and [Q] 6= 0, and ∗ u02 if [P] = [Q] = 0. That the stated elements are indeed atoms follows since θ : H → B(CM ) is a transfer homomorphism. In each case, the two factorizations are distinct as rigid factorizations with distance at least two, because the factors have different abstract norms. Lemma 7.5. Suppose that C = CM and that C is non-trivial. If C ∼ 6 C2 a cyclic group with two elements, = then H is not half-factorial. If C ∼ = C2 and the non-trivial class contains at least two distinct prime elements P and Q of G+ , then there exist atoms a, b, c, d ∈ A(H) such that ab = cd, η(a) = P 2 , η(b) = Q2 and η(c) = η(d) = PQ. Proof. If C 6∼ = C2 , then B(C) is not half-factorial, and the existence of the transfer homomorphism from H to B(C) implies that neither is H. If C ∼ = C2 , let e ∈ H0 . Let u1 , u2 , v1 , v2 ∈ A(G+ ) with s(u1 ) = e, s(u2 ) = t(u1 ), s(v1 ) = t(u2 ), s(v2 ) = t(v1 ), η(u1 ) = η(u2 ) = P, and η(v1 ) = η(v2 ) = Q. Assumption (N) implies a = u1 u2 ∈ HH −1 and b = v1 v2 ∈ HH −1 . Since moreover a, b ∈ G+ and H is right-saturated in G+ , we find a, b ∈ H. Because η(u1 ), η(u2 ), η(v1 ), and η(v2 ) all lie in the non-trivial class of C, we have that θ(a) and θ(b) are atoms of B(CM ). Since θ : H → B(CM ) is a transfer homomorphism, and therefore also a ∈ A(H) and b ∈ A(H). By [Sme13, Proposition 4.12.4], there exist u02 , v10 ∈ A(G+ ) such that u2 v1 = v10 u02 and η(v10 ) = Q, η(u02 ) = P. As before, c = u1 v10 ∈ A(H) and further d = u02 v1 ∈ A(H). By construction the elements a, b, c and d have the claimed properties. To better leverage results on the transfer of the catenary degree for commutative Krull monoids, we will show that η is, in fact, a transfer homomorphism to a commutative Krull monoid. This will allow us to view θ as a composite of two transfer homomorphisms. The proof is very similar to that of [Sme13, Theorem 4.15], but for the reader’s convenience we shall state it in full. Theorem 7.6. Let G be an arithmetical groupoid, let H be a right-saturated subcategory of G, and suppose that assumption (N) holds. Then η(H) ⊂ G+ is saturated, η(H) is a commutative Krull monoid, and η : H → η(H) is a transfer homomorphism. 38 N. BAETH AND D. SMERTNIG Proof. We first show: If a ∈ H and η(a) = X Y with X , Y ∈ G+ , then there exists x, y ∈ G+ such that a = xy, η(x) = X , and η(y) = Y. Moreover, if X ∈ η(H), then x ∈ H, and if Y ∈ η(H), then y ∈ H. Let a ∈ H with η(a) = X Y for some X , Y ∈ G+ . Let k, l ∈ N0 and P1 , . . . , Pl ∈ A(G+ ) be such that X = P1 · · · Pk and Y = Pk+1 · · · Pl . By [Sme13, Proposition 4.12], there exists a rigid factorization s(a)u1 ∗ · · · ∗ ul ∈ ZG+ (a) such that η(ui ) = Pi for all i ∈ [1, l]. Now set x = s(a)u1 · · · uk ∈ G+ and y = t(uk )uk+1 · · · ul ∈ G+ . Then a = xy, η(x) = X , and η(y) = Y. Now suppose that X ∈ η(H). Since s(x) ∈ H0 and η(x) = X ∈ η(H), assumption (N) implies x ∈ HH −1 ∩ G+ . Because H is right-saturated in G+ , this implies x ∈ H. Now assume that Y ∈ η(H). Then t(y) ∈ H0 , and η(y) = Y ∈ η(H). Applying (N) to y −1 , it again follows that y ∈ HH −1 ∩ G+ . Hence y ∈ H, and the claim is established. We now show that η is a transfer homomorphism. Since H as well as G+ are reduced and η : H → η(H) is surjective by definition, (T1) holds. We have to verify (T2). Let a ∈ H and η(a) = BC with B, C ∈ η(H). We need to show that there exist b, c ∈ H such that a = bc, η(b) = B and η(c) = C. This follows immediately from the claim we just proved. It remains to show that η(H) ⊂ G+ is saturated. Then, since η(H) is a subsemigroup of the free abelian monoid G+ , η(H) is a commutative Krull monoid. Let A, B ∈ η(H) and X ∈ G+ be such that X B = A. We need to show X ∈ η(H). Let a ∈ H with η(a) = A = X B. Again by the claim, there exist b ∈ H and x ∈ G+ such that a = xb, η(b) = B and η(x) = X . Then x = ab−1 ∈ HH −1 ∩ G+ . Since H is right-saturated in G+ , this implies x ∈ H and hence X = η(x) ∈ η(H). Let d be a distance on H. The following is the key result on the catenary degree in the permutable fibers of η. It will ultimately allow us to transfer results on the permutable catenary degree in η(H) (respectively B(CM )) to results on the catenary degree in distance d on H. Proposition 7.7. Let d be a distance on H. (1) Let a ∈ H, z = s(a)a1 ∗· · ·∗am ∈ Z∗H (a) with m ∈ N0 and a1 , . . . , am ∈ A(H), and let σ ∈ Sm be a permutation. Then there exist a01 , . . . , a0m ∈ A(H) such that a = s(a)a01 · · · a0m , η(a0i ) = η(aσ(i) ) for all i ∈ [1, m], and such that there exists a 2-chain in distance d between z and z 0 = s(a)a01 ∗ · · · ∗ a0m . Furthermore, every rigid factorization in the chain has length m, and the sequence of abstract norms of its atoms is the same as the sequence of abstract norms of the atoms in z, up to permutation. (2) cd (H, η) ≤ 2. Proof. (1) We may assume m ≥ 2, as the claim is trivially true otherwise. Since Sm is generated by transpositions of the form (i, i + 1) for i ∈ [1, m − 1], it suffices to prove the claim where σ is such a transposition. Moreover, by property (D4) of a distance, we may even assume that m = 2 and σ = (1 2). Therefore it suffices to prove: If a, b ∈ A(H) with t(a) = s(b), then there exist a0 , b0 ∈ A(H) such that ab = b0 a0 , η(a) = η(a0 ), and η(b) = η(b0 ). Then (D5) implies d(a ∗ b, b0 ∗ a0 ) ≤ 2. Let a = u1 · · · uk and b = v1 · · · vl with k, l ∈ N and u1 , . . . , uk , v1 , . . . , vl ∈ A(G+ ). By [Sme13, Proposition 4.12.4], there exist u01 , . . . , u0k , v10 , . . . , vl0 ∈ A(G+ ) such that u1 · · · uk v1 · · · vl = v10 · · · vl0 u01 · · · u0k with η(u0i ) = η(ui ) for all i ∈ [1, k] and η(vi0 ) = η(vi ) for all i ∈ [1, l]. Set b0 = v10 · · · vl0 and a0 = u01 · · · u0k . Then η(a) = η(a0 ) and η(b) = η(b0 ). Using assumption (N), we find a0 ∈ HH −1 ∩ G+ = H. Similarly, b0 ∈ HH −1 ∩ G+ = H. Using that η is a transfer homomorphism, η(a) = η(a0 ), and η(b) = η(b0 ), it follows that a0 , b0 ∈ A(H) and hence the claim is shown. (2) Let a ∈ H and let z, z 0 ∈ Z∗H (a) with dp (η(z), η(z 0 )) = 0. We must show that there exists a 2-chain of rigid factorizations of a between z and z 0 lying in the permutable fiber of z. Since dp (η(z), η(z 0 )) = 0, z = a1 ∗ · · · ∗ am and z 0 = b1 ∗ · · · ∗ bm with m ∈ N0 , a1 , . . . , am , b1 , . . . , bm ∈ A(H) and such that there exists a permutation σ ∈ Sm with η(aσ(i) ) = η(bi ). Applying (1), we may assume without loss of generality that σ = id, and hence η(ai ) = η(bi ) for all i ∈ [1, m]. Let n ∈ N and let u1 , . . . , un , v1 , . . . , vn ∈ A(G+ ) be such that am = u1 · · · un and bm = v1 · · · vn with η(ui ) = η(vi ) for each i ∈ [1, n]. (This choice is always possible due to [Sme13, Proposition 4.12.4] and since η(bm ) = η(am ).) Let k ∈ [0, n] be minimal such that ul = vl for all l ∈ [k + 1, n]. We proceed by induction on (m, k) using lexicographic order, i.e., (m0 , k 0 ) < (m, k) if and only if m0 < m or m0 = m and k 0 < k. If m ≤ 2, then the claim is trivially true. If m > 2 but k = 0, then am = bm . By the induction hypothesis applied to (m − 1, k 0 ) for some k 0 ∈ N0 , there exists a 2-chain from a1 ∗ · · · ∗ am−1 to b1 ∗ · · · ∗ bm−1 with the corresponding properties. Appending a factor am to each of these rigid factorizations gives a 2-chain from z to z 0 (using property (D4)). FACTORIZATION THEORY: FROM COMMUTATIVE TO NONCOMMUTATIVE SETTINGS 39 We therefore need only consider the case m > 2 and k ≥ 1. Let e = t(uk ) = t(vk ) and c = uk ∧ vk ∈ G+ (·, e). By the choice of k, uk 6= vk , and thus uk ∨ vk = e in G(·, e). Modularity of the lattice G(·, e) 0 therefore implies that the element c has length two in G+ . Consequently c = vk−1 uk = u0k−1 vk for some 0 vk−1 , u0k−1 ∈ A(G+ ). By [Sme13, Proposition 4.12.1] together with [Sme13, Lemma 4.11.4], we find that 0 η(vk−1 ) = η(vk ) and η(u0k−1 ) = η(uk ), so the abstract norms of all these four elements are the same. Since a ≤ uk uk+1 · · · un and a ≤ vk uk+1 · · · un ∈ G(·, t(a)), we have a ≤ cuk+1 · · · un as well. Hence there exists d ∈ G+ with a = dcuk+1 · · · un . Noting that η(c) | η(a(uk+1 · · · un )−1 ) and using (1) to rewrite a1 ∗ · · · ∗ am−1 and b1 ∗ · · · ∗ bm−1 as necessary, we may assume without restriction that η(c) | η(am−1 am (uk+1 · · · un )−1 ), while still preserving η(ai ) = η(bi ) for each i ∈ [1, m]. As in the proof of Theorem 7.6 we can write d = d1 d2 with d1 , d2 ∈ G+ , η(d1 ) = η(a1 · · · am−2 ) and η(d2 cuk+1 · · · un ) = η(am−1 am ). (Here we have used that η(c) | η(am−1 am (uk+1 · · · un )−1 .) Note that d1 ∈ H, by (N) and HH −1 ∩ G+ = H. Similarly, d2 cuk+1 · · · un ∈ H. Since η is a transfer homomorphism, we can take b01 ∗ · · · ∗ b0m−2 to be a rigid factorization of d1 in H with b0i ∈ A(H) and η(b0i ) = η(ai ) for all i ∈ [1, m − 2]. Arguing as we just have, we find a rigid factorization b0m−1 ∗ b0m of d2 cuk+1 · · · un in H satisfying b0m ≤ uk uk+1 · · · un in G(·, t(a)) and η(b0i ) = η(ai ) for i ∈ {m − 1, m}. By the induction hypothesis, there exists a 2-chain from z to z 00 = b01 ∗ · · · ∗ b0m lying in the permutable 0 fiber of z. Since vk−1 uk = u0k−1 vk , and since the abstract norms of all these elements are the same, we 0 0 00 have bm−1 bm = bm−1 b00m with b00m−1 , b00m ∈ A(H) and b00m ≤ vk uk+1 · · · un in G(·, t(a)). By the induction hypothesis, there exists a 2-chain from z 0 to z 000 = b01 ∗ · · · ∗ b0m−2 ∗ b00m−1 ∗ b00m , and by property (D4) of distances, we have d(z 00 , z 000 ) ≤ 2. Hence the claim is shown. Theorem 7.8. Let G be an arithmetical groupoid, η : G → G its abstract norm, H ⊂ G+ a right-saturated subcategory, C = G/q(η(H)) and CM = { [η(u)] ∈ C : u ∈ A(G+ )}. Let θ : H → B(CM ) be the block homomorphism of H ⊂ G+ (see page 37) and let d be a distance on H. Assume that (N) holds, that is, for a ∈ G with s(a) ∈ H0 , we have a ∈ HH −1 if and only if η(a) ∈ q(η(H)). Then θ is a transfer homomorphism and cd (H, θ) ≤ 2. Therefore, for all a ∈ H, cd (a) ≤ max{cp (θ(a)), 2}, cd (H) ≤ max{cp (B(CM )), 2}, cd,mon (a) ≤ max{cp,mon (θ(a)), 2}, cd,mon (H) ≤ max{cp,mon (B(CM )), 2}, cd,eq (a) ≤ max{cp,eq (θ(a)), 2}, cd,eq (H) ≤ max{cp,eq (B(CM )), 2}. Proof. We need only show that θ is a transfer homomorphism with cd (H, θ) ≤ 2. The remaining claims then follow from Proposition 4.6(2). By Proposition 7.7, η : H → η(H) is a transfer homomorphism with cd (H, η) ≤ 2 and η(H) is a commutative Krull monoid. Now, by [GHK06, Proposition 3.4.8], the homomorphism ϕ : η(H) → B(CM ) is a transfer homomorphism with cp (η(H), ϕ) ≤ 2. Since θ = ϕ ◦ η, the map θ is a transfer homomorphism with cd (H, θ) ≤ 2. We now derive, from the previous abstract result, a result for arithmetical maximal orders by means of their divisorial one-sided ideal theory. (See Section 2, page 7 for the definition of an arithmetical maximal order and a short summary of the necessary notions of their divisorial one-sided ideal theory. More details can be found in [Sme13, Section 5].) Let Q be a quotient semigroup and S an order in Q. We set HS = { q −1 (Sa)q : q ∈ Q• , a ∈ S • } to be the category of principal one-sided S 0 -ideals with S 0 conjugate to S and having a cancellative generator. Recall that HS forms a cancellative small category with (HS )0 = { q −1 Sq : q ∈ Q• } such that s(q −1 (Sa)q) = q −1 Sq and t(q −1 (Sa)q) = (aq)−1 Saq for each q ∈ Q• and a ∈ S • , and such that the multiplication of ideals is induced by the multiplication of elements in Q• : q −1 (Sa)q · (aq)−1 (Sb)aq = q −1 (Sba)q. Despite not having a homomorphism S • → HS , we have, for all a ∈ S • and q ∈ Q• , a bijection φa,q : Z∗S (a) → Z∗HS (q −1 (Sa)q) given by −1 −1 εu1 ∗ · · · ∗ uk 7→ q −1 (Huk )q ∗ q −1 u−1 uk · · · u−1 2 (Hu1 )u2 · · · uk q. k (Huk−1 )uk q ∗ · · · ∗ q (See [Sme13, Proposition 5.20], where this is stated in a more restrictive setting, but with a proof that generalizes verbatim.) Observe that if q = 1, the right hand side is essentially a multiplicative way of writing the chain of left H-ideals H ) Huk ) Huk−1 uk ) · · · ) Hu1 · · · uk . In this way, questions about factorization in S • translate into questions about factorization in HS . 40 N. BAETH AND D. SMERTNIG To extend distances from S • to HS we need to impose one additional mild restriction on the distance. If n ∈ Q• normalizes S, that is n−1 Sn = S, it induces an automorphism on S • given by a 7→ n−1 an for a ∈ S • . This automorphism in turn induces an automorphism ψn : Z∗ (S) → Z∗ (S), εu1 ∗ · · · ∗ uk 7→ (n−1 εn)n−1 u1 n ∗ · · · ∗ n−1 uk n, which induces bijections Z∗S (a) → Z∗S (n−1 an) for all a ∈ S • . We say that a distance d on S • is invariant under conjugation by normalizing elements if d(z, z 0 ) = d(ψn (z), ψn (z 0 )) for all z, z 0 ∈ Z∗ (S) with π(z) = π(z 0 ) and for all n ∈ Q• that normalize S. Similarly, the elements of Q• normalizing S act on HS by mapping q −1 (Sa)q 7→ n−1 q −1 (Sa)qn = n−1 q −1 n(Sn−1 an)n−1 qn. This in turn induces an action of the normalizing elements on Z∗ (HS ), where n acts by Ψn : Z∗ (HS ) → Z∗ (HS ), S 0 I1 ∗ · · · ∗ Ik 7→ (n−1 S 0 n)n−1 I1 n ∗ · · · ∗ n−1 Ik n, and by restriction we obtain bijections Z∗HS (q −1 (Sa)q) → Z∗HS (n−1 q −1 n(Sn−1 an)n−1 qn) for all q ∈ Q• and a ∈ S • . Again, we say that a distance d on HS is invariant under conjugation by normalizing elements if d(z, z 0 ) = d(Ψn (z), Ψn (z 0 )) for all z, z 0 ∈ Z∗ (HS ) with π(z) = π(z 0 ) and for all n ∈ Q• that normalize S. Observe that each distance introduced (d∗ , dp , dsim , and dsubsim ) is in fact invariant under any automorphism of S, and that it seems quite reasonable to expect any natural distance to have this property. We now observe how the family of bijections φa,q : Z∗S (a) → Z∗HS (q −1 (Sa)q) behaves with respect to conjugation by normalizing elements. Let z, z 0 ∈ Z∗ (S) and q ∈ Q• . Set a = π(z) and b = π(z 0 ). Then φab,q (z ∗ z 0 ) = φb,q (z 0 ) ∗ φa,bq (z) and φn−1 an,n−1 qn (ψn (z)) = Ψn (φa,q (z)) = φa,qn (z) for each n ∈ Q• that normalizes S. Now let z, z 0 ∈ Z∗ (HS ) with t(z) = s(z 0 ). We may suppose π(z) = q −1 (Sa)q −1 0 0 −1 and π(z 0 ) = (aq)−1 (Sb)(aq) with q ∈ Q• and a, b ∈ S • . Then φ−1 ba,q (z ∗ z ) = φb,aq (z ) ∗ φa,q (z) and −1 −1 • φa,qn (Ψn (z)) = φa,q (z) for each n ∈ Q that normalizes S. The proof of the following proposition is now relatively straightforward, but somewhat cumbersome. Proposition 7.9. Let Q be a quotient semigroup and let S be an order in Q. Let dS be a distance on S • that is invariant under conjugation by normalizing elements. Then there exists a unique distance on HS , denoted by dH , such that −1 0 dH (z, z 0 ) = dS (φ−1 a,q (z), φa,q (z )) for all z, z 0 ∈ Z∗ (HS ) and for all q ∈ Q• and a ∈ S • with π(z) = π(z 0 ) = q −1 (Sa)q. Conversely, if dH is a distance on HS that is invariant under conjugation by normalizing elements, then there exists a unique distance dS on S • such that dS (z, z 0 ) = dH (φa,q (z), φa,q (z 0 )) for all z, z 0 ∈ Z∗ (S) with a = π(z) = π(z 0 ) and q ∈ Q• . In particular, there is a bijection between distances on S • which are invariant under conjugation by normalizing elements and distances on HS which are invariant under conjugation by normalizing elements. Proof. First let dS be a distance on S • that is invariant under conjugation by elements of Q• that normalize S. Let z, z 0 ∈ Z∗ (HS ) with π(z) = π(z 0 ). Let q ∈ Q• and a ∈ S • be such that π(z) = π(z 0 ) = q −1 (Sa)q. Note that, after fixing q, the element a is uniquely determined up to left associativity. We wish to define −1 0 dH by dH (z, z 0 ) = dS (φ−1 a,q (z), φa,q (z )) and need to show that the expression on the right hand side is independent of the choice of q and a. Suppose q 0 ∈ Q• and a0 ∈ S • are such that (q 0 )−1 (Sa0 )q 0 = q −1 (Sa)q. Let z = (q −1 Sq)Ik ∗ · · · ∗ I1 and 0 z = (q −1 Sq)Jl ∗ · · · ∗ J1 with k, l ∈ N0 and I1 , . . . , Ik , J1 , . . . , Jl ∈ HS . If k = 0, then, since π(z) = π(z 0 ), −1 −1 −1 0 0 l = 0. Similarly, l = 0 implies k = 0. In that case dS (φ−1 a,q (z), φa,q (z )) = dS (φa0 ,q 0 (z), φa0 ,q 0 (z )) = 0. From now on we may assume k, l > 0. Following the construction in [Sme13, Proposition 5.20], there exist u1 , . . . , uk , u01 ,. . . , u0k , v1 ,. . . , vl , v10 ,. . . , vl0 ∈ A(S • ) such that (7.1) −1 0 −1 0 −1 Ii = q −1 u−1 (uk ) · · · (u0i+1 )−1 (Su0i )u0i+1 · · · u0k q 0 k · · · ui+1 (Sui )ui+1 · · · uk q = (q ) for all i ∈ [1, k], (7.2) −1 0 0 Jj = q −1 vl−1 · · · vj+1 (Svj )vj+1 · · · vl q = (q 0 )−1 (vl0 )−1 · · · (vj+1 )−1 (Svj0 )vj+1 · · · vl0 q 0 for all j ∈ [1, l], and φ−1 a,q (z) = u1 ∗ · · · ∗ uk , 0 φ−1 a,q (z ) = v1 ∗ · · · ∗ vl , 0 0 φ−1 a0 ,q 0 (z) = u1 ∗ · · · ∗ uk , 0 0 0 φ−1 a0 ,q 0 (z ) = v1 ∗ · · · ∗ vl . FACTORIZATION THEORY: FROM COMMUTATIVE TO NONCOMMUTATIVE SETTINGS 41 We must show dS (u1 ∗· · ·∗uk , v1 ∗· · ·∗vl ) = dS (u01 ∗· · ·∗u0k , v10 ∗· · ·∗vl0 ). Note that n = q(q 0 )−1 ∈ Q• normalizes S. From Equations (7.1) and (7.2) applied with i = k and j = l, we deduce that Su0k = Sn−1 uk n and Svl0 = Sn−1 vl n. Hence there exist εk , ηl ∈ S × such that u0k = εk n−1 uk n and vl0 = ηl n−1 vl n. Inductively, we −1 0 −1 find that there exist ε1 , . . . , εk−1 and η1 , . . . , ηl−1 such that u0i = εi (n−1 ui n)ε−1 vj n)ηj+1 i+1 and vj = ηj (n for all i ∈ [1, k − 1] and j ∈ [1, l − 1]. Thus u01 ∗ · · · ∗ u0k = ε1 n−1 u1 n ∗ · · · ∗ n−1 uk n and v10 ∗ · · · ∗ vl0 = η1 n−1 v1 n ∗ · · · ∗ n−1 vl n. Since a0 = ε1 n−1 u1 · · · uk n = ε1 n−1 an and similarly a0 = η1 n−1 an, we have ε1 = η1 . First using property (D4) of a distance and then the invariance under normalizing elements, we find that dS (ε1 n−1 u1 n ∗ · · · ∗ n−1 uk n, ε1 n−1 v1 n ∗ · · · ∗ n−1 vl n) = dS (n−1 u1 n ∗ · · · ∗ n−1 uk n, n−1 v1 n ∗ · · · ∗ n−1 vl n) = dS (u1 ∗ · · · ∗ uk , v1 ∗ · · · ∗ vl ). −1 0 Hence we may define dH (z, z 0 ) = dS (φ−1 a,q (z), φa,q (z )), and it is clear that in this way dH is uniquely determined. We now check that dH is indeed a distance on H. Properties (D1) to (D3) and (D5) are immediate from the definition and the fact that dS satisfies each of these properties. We now check (D4). Let x, y, z, z 0 ∈ Z∗ (HS ) be such that x ∗ z ∗ y and x ∗ z 0 ∗ y are defined and π(z) = π(z 0 ). We may assume π(x) = q −1 (Sc)q, π(z) = π(z 0 ) = (cq)−1 (Sb)cq and π(y) = (bcq)−1 (Sa)(bcq) with q ∈ Q• and a, b, c ∈ S • . Observe that −1 −1 −1 φ−1 abc,q (x ∗ z ∗ y) = φa,bcq (y) ∗ φb,cq (z) ∗ φc,q (x), and −1 −1 0 0 −1 φ−1 abc,q (x ∗ z ∗ y) = φa,bcq (y) ∗ φb,cq (z ) ∗ φc,q (x). Therefore, using property (D4) of dS , −1 −1 −1 −1 0 −1 dH (x ∗ z ∗ y, x ∗ z 0 ∗ y) = dS (φ−1 a,bcq (y) ∗ φb,cq (z) ∗ φc,q (x), φa,bcq (y) ∗ φb,cq (z ) ∗ φc,q (x)) −1 0 = dS (φ−1 b,cq (z), φb,cq (z )) = dH (z, z 0 ). It remains to check that dH is invariant under conjugation by normalizing elements. Suppose again that z and z 0 are in Z∗ (HS ) with π(z) = π(z 0 ), and let q ∈ Q• and a ∈ S • be such that π(z) = π(z 0 ) = q −1 (Sa)q. Let n ∈ Q• be such that it normalizes S. Then −1 0 −1 −1 0 0 dH (Ψn (z), Ψn (z 0 )) = dS (φ−1 a,qn (Ψn (z)), φa,qn (Ψn (z ))) = dS (φa,q (z), φa,q (z )) = dH (z, z ). We now prove the converse. Suppose that dH is a distance on HS that is invariant under conjugation by normalizing elements. Let z, z 0 ∈ Z∗ (S) with a = π(z) = π(z 0 ) and let q, q 0 ∈ Q• . Noting that q −1 q 0 normalizes S and that φa,q0 (z) = Ψq−1 q0 (φa,q (z)) and φa,q0 (z 0 ) = Ψq−1 q0 (φa,q (z 0 )), dH (φa,q (z), φa,q (z 0 )) = dH (φa,q0 (z), φa,q0 (z 0 )) follows immediately from the invariance of dH under normalizing elements. Thus a unique dS as claimed exists, and we must check that it is a distance on S • . Again, properties (D1) to (D3) and (D5) follow immediately from the corresponding properties of dH . Let us verify (D4), and to this end let x, y, z, z 0 ∈ Z∗ (S) with π(z) = π(z 0 ). Let a = π(x), b = π(y), and c = π(z) = π(z 0 ). Then dS (x ∗ z ∗ y, x ∗ z 0 ∗ y) = dH (φacb,1 (x ∗ z ∗ y), φacb,1 (x ∗ z 0 ∗ y)) = dH (φb,1 (y) ∗ φc,b (z) ∗ φa,cb (x), φb,1 (y) ∗ φc,b (z 0 ) ∗ φa,cb (x)) = dH (φc,b (z), φc,b (z 0 )) = dS (z, z 0 ). Finally, we verify that dS is invariant under conjugation by normalizing elements. Let n ∈ Q• be such that it normalizes S, and let z, z 0 ∈ Z∗ (S) with a = π(z) = π(z 0 ). Then dS (ψn (z), ψn (z 0 )) = dH (φn−1 an,1 (ψn (z)), φn−1 an,1 (ψn (z 0 ))) = dH (Ψn (φa,1 (z)), Ψn (φa,1 (z 0 ))) = dS (z, z 0 ). Remark 7.10. Note that the extension of the rigid distance from S • to HS is, in general, not the rigid distance on HS . Indeed, let R = M2 (Z) so that S = M2 (Z)• , let p ∈ N be prime, and set 0 p 0 1 a= and ε = . 1 0 1 0 42 N. BAETH AND D. SMERTNIG Viewing scalar matrices as elements in Z, a2 = p and ε2 = 1. In S, we have rigid factorizations z =a∗a∗a∗a and z 0 = εa ∗ a ∗ a ∗ aε of a4 = p2 . Since εa 6= aη and aε 6= ηa for all η ∈ S × , these are distinct rigid factorizations with d∗ (z, z 0 ) = 2 and dp (z, z 0 ) = 0. We have φa,1 (z) = Sa ∗ a−1 (Sa)a ∗ a−2 (Sa)a2 ∗ a−3 (Sa)a3 0 φa,1 (z ) = Saε ∗ εa −1 (Sa)aε ∗ εa −2 2 (Sa)a ε ∗ εa −3 and (Sεa)a3 ε. Now Saε 6= Sa since there exists no η ∈ S × with ηa = aε. Moreover, Saε is not equal to any of the other atoms in φa,1 (z) since their left orders differ. Continuing this argument, one finds that the atoms in z are pairwise distinct from those in z 0 . Recalling that HS is reduced, we have dp (φa,1 (z), φa,1 (z 0 )) = d∗ (φa,1 (z), φa,1 (z 0 )) = 4. Let Q be a quotient semigroup, and let S be an arithmetical maximal order in Q. If α denotes the set of maximal orders of Q that are equivalent to S and Fv (α) denotes the divisorial fractional left S 0 -ideals with S 0 ∈ α, then, by [Sme13, Proposition 5.16], Fv (α) is, with a partial operation given by the v-ideal multiplication, an arithmetical groupoid. Then the subcategory Iv (α) of Fv (α) consisting of divisorial left S 0 -ideals with S 0 ∈ α is just the subcategory of integral elements of Fv (α). The category HS is a leftand right-saturated subcategory of Iv (α) (in particular, the usual multiplication on HS coincides with the v-ideal multiplication). We denote by η the abstract norm on Fv (α) and define PS • = { η(Sq) : q ∈ Q• } ⊂ G, C = G/PS • , and CM = { [η(I)] ∈ C : I ∈ Iv (α) is maximal integral }. If we also assume that a divisorial fractional left S-ideal I is principal if and only if η(I) ∈ PS • , then (N) holds for HS . The block homomorphism θ : HS → B(CM ) induces a transfer homomorphism S • → B(CM ), again denoted by θ, by means of θ(a) = θ(Sa) for all a ∈ S • (see [Sme13, Theorem 5.23.2]). Thus we have the following corollary to Theorem 7.8. Recall that this also covers the case of normalizing Krull monoids as investigated in [Ger13] (see Section 2 and [Sme13, Remarks 5.17.2 and 5.24.1]). Corollary 7.11. Let S be an arithmetical maximal order in a quotient semigroup Q and let α denote the set of maximal orders of Q equivalent to S. Let η : Fv (α) → G be the abstract norm of Fv (α), let C = G/PS • , and set CM = { [η(I)] ∈ C : I ∈ Iv (α) maximal integral }. Assume that a divisorial fractional left S-ideal I is principal if and only if η(I) ∈ PS • . Let θ : S • → B(CM ) be the transfer homomorphism induced by the block homomorphism of HS ⊂ Iv (α). Let d be a distance on S • that is invariant under conjugation by normalizing elements. Then cd (S • , θ) ≤ 2. Moreover, for all a ∈ S • , cd (a) ≤ max{cp (θ(a)), 2}, cd (S • ) ≤ max{cp (B(CM )), 2}, cd,mon (a) ≤ max{cp,mon (θ(a)), 2}, cd,mon (S • ) ≤ max{cp,mon (B(CM )), 2}, cd,eq (a) ≤ max{cp,eq (θ(a)), 2}, cd,eq (S • ) ≤ max{cp,eq (B(CM )), 2}. Proof. By setting G = Fv (α), G+ = Iv (α) and H = HS , we are in our previous setting. The additional condition (N) is satisfied by our assumptions on S. By Proposition 7.9, the distance d on S • gives rise to a distance dH on HS . Using the bijections between ∗ ZS (a) and Z∗HS (q −1 (Sa)q), it is now clear that cd (a) = cdH (q −1 (Sa)q) for all q ∈ Q• , and the claim therefore follows from Theorem 7.8. We now apply this abstract machinery to classical maximal orders in central simple algebras over global fields. Let K be a global field, O a holomorphy ring in K, A a central simple algebra over K, and let R be a classical maximal O-order. Then we may identify η with the reduced norm on left and right R-ideals (see [Sme13, Lemma 5.32]). Let F × (O) denote the group of nonzero fractional ideals of O, let PA (O) = { aO : a ∈ K × , av > 0 for all archimedean places v of K where A is ramified }, and C A (O) = F × (O)/PA (O). The ray class group C A (O) is a finite abelian group, and under the identification of the abstract norm with the reduced norm, we find C = CM = C A (O) (see [Sme13, Theorem 5.28 and Section 6] for details). We immediately obtain the following result, which is a direct analogue to the corresponding abstract result for commutative Krull monoids ([GHK06, Corollary 3.4.12]) applied to holomorphy rings in global fields. FACTORIZATION THEORY: FROM COMMUTATIVE TO NONCOMMUTATIVE SETTINGS 43 Theorem 7.12. Let K be a global field, O a holomorphy ring in K, and R a classical maximal O-order in a central simple algebra A over K. Let d be a distance on R• that is invariant under conjugation by normalizing elements. Suppose that every stably free left R-ideal is free, and let θ : R• → B(C A (O)) be the transfer homomorphism induced by the block homomorphism. Then cd (R• ) ≤ max{2, cp (B(C A (O)))}. In particular, c∗ (R• ) = max{2, cp (B(C A (O)))}. Moreover, if C A (O) is non-trivial, then cp (R• ) = csubsim (R• ) = csim (R• ) = max{2, cp (B(C A (O)))}, cp,mon (R• ) = csubsim,mon (R• ) = csim,mon (R• ) = max{2, cp,mon (B(C A (O)))}, cp,eq (R• ) = csubsim,eq (R• ) = csim,eq (R• ) = max{2, cp,eq (B(C A (O)))}, and if C A (O) is trivial, then R• is dsim -factorial and dsubsim -factorial. Proof. We first show that, in R• , subsimilarity already implies similarity, so that dsim and dsubsim coincide. Indeed, let a and a0 be subsimilar elements of R• . Then there exists a nonzero two-sided R-ideal I contained in Ra ∩ Ra0 , and the quotient ring R/I is Artinian and Noetherian. The ideal I is contained in both annR (R/Ra) and annR (R/Ra0 ). As finitely generated R/I-modules, the modules R/Ra and R/Ra0 have finite length. Since each of R/Ra and R/Ra0 embeds into the other, R/Ra and R/Ra0 must be isomorphic as R/I-modules and therefore also as R-modules. The upper bound for cd (R• ) follows from Corollary 7.11. The corollary applies because the assumption that every stably free left R-ideal is free implies the corresponding assumption in Corollary 7.11 (see [Sme13, Lemma 6.2]). Lemma 7.4 implies c∗ (R• ) ≥ 2, and hence c∗ (R• ) = max{2, cp (B(C A (O)))}. We now show csim (R• ) = csubsim (R• ) ≥ cp (B(C A (O))), and for this it suffices to show that two similar atoms u, v ∈ A(R• ) are mapped to the same element by θ. Since in this context η corresponds to the usual reduced norm (see [Sme13, Lemma 5.32]), it suffices to show that nr(Ru) = nr(Rv). Since nr(Ru) and nr(Rv) depend only on the isomorphism class of R/Ru ∼ = R/Rv by [Rei75, Corollary 24.14], nr(Ru) = nr(Rv). Therefore cp (B(C A (O))) ≤ csubsim (R• ) = csim (R• ) ≤ cp (R• ) ≤ max{2, cp (B(C A (O)))}. If |C A (O)| > 2, then cp (B(C A (O))) ≥ 2, which establishes the full claim in this case. If C A (O) is trivial, then R is a PID, and hence dsim -factorial (and thus also dsubsim -factorial). It remains to consider the case where C A (O) ∼ = C2 . Let p, q ∈ spec(O) be two distinct prime ideals representing the non-trivial class of C A (O). Using Lemma 7.5, we can find atoms u, v, w, w0 ∈ A(R• ) such that uv = ww0 , nr(u) = p2 , nr(v) = q2 , and nr(w) = nr(w0 ) = pq. Then u and v are similar to neither w nor w0 , as similar elements have the same reduced norm. Thus cp (R• ) = csim (R• ) = csubsim (R• ) = 2. The statements about the monotone and equal catenary degrees are obtained analogously. Suppose that K is a number field, O = OK is its ring of algebraic integers and, contrary to the assumptions of the previous corollary, there exist stably free left R-ideals that are non-free. Then, by [Sme13, Theorem 1.2], it holds that ∆(R• ) = N, and by Lemma 4.2(3) we have cd (R• ) = ∞ for any distance d. Observe that even for H = G+ we only have c∗ (G+ ) ≤ 2 in general. Thus not even for PIDs that are bounded orders in quotient rings can we expect c∗ (R• ) = 0 but instead only have c∗ (R• ) ≤ 2. We now give a more concrete example to illustrate this fact. Example 7.13. Let K be a field, let D be a quaternion division ring with center K, and denote by · : D → D the anti-involution given by conjugation. Let D[X] be the polynomial ring over K. Then D[X] is a PID and S = D[X]• satisfies the conditions of Corollary 7.11. We have C = CM = 0, whence cp (B(C)) = 0. However, if a ∈ D \ K, then, for all b ∈ D• , (X − a)(X − a) = X 2 − (a + a)X + aaX = (X − bab−1 )(X − bab−1 ) ∈ K[X], and so clearly c∗ (S) = 2 and also cp (S) = 2. Recall however that this ring, being a PID, is dsubsim -factorial and dsim -factorial, and hence we have csubsim (S) = csim (S) = 0. Corollary 7.14. Let K be a global field, O a holomorphy ring in K, and R a classical maximal O-order in a central simple algebra A over K. Suppose that every stably free left R-ideal is free. Then the following statements are equivalent. (a) Every left [right] R-ideal is principal. (b) The ray class group C A (O) is trivial. (c) R• is dsim -factorial. 44 N. BAETH AND D. SMERTNIG (d) R• is dsubsim -factorial. Proof. The set of isomorphism classes of fractional left R-ideals is in bijection with C A (O) via the reduced norm, and hence the equivalence of (a) and (b) holds. The equivalence of (b), (c) and (d) is an immediate consequence of Theorem 7.12 and the fact that d-factoriality is characterized by cd (R• ) = 0. Remark 7.15. (1) If C A (O) is trivial, then cp (R• ) ∈ [0, 2]. There are examples where cp (R• ) = 0 as well as examples where cp (R• ) = 2. For the first, take R = Mn (O) with O a PID and n ∈ N. For an example with cp (R• ) = 2, let K be a number field, O its ring of algebraic integers, and R a classical maximal order in a totally definite quaternion algebra over K such that R is a PID. (Note that, amongst the totally definite quaternion algebras over all number fields, there indeed exist, up to isomorphism, finitely many such classical maximal orders, see, for instance, [KV10, Table 8.1]. For instance, take R to be the ring of Hurwitz quaternions.) Then [R× : O× ] < ∞, while every totally positive prime element p ∈ O that does not divide the discriminant has NK/Q (p) + 1 rigid factorizations, with all atoms being similar. Thus cp (p) = 2, for NK/Q (p) + 1 sufficiently large. The previous corollary can therefore not be extended to permutable factoriality. (2) The investigation of the ωp -invariant is, in the present setting, left open as it does not necessarily transfer via a non-isoatomic transfer homomorphism (i.e., if nr(u) ' nr(v) does not imply u ' v for atoms u, v ∈ R• ). A further investigation will require dealing with additional difficulties similar to the ones in the example just given. To demonstrate the usefulness of our transfer result, we state the following corollary, which is now an immediate consequence of known results about monoids of zero sum sequences. Corollary 7.16 ([GGS11]). Let R and C = C A (O) be as in Theorem 7.12, and let d be any of the distances d∗ , dsim , dsubsim , or dp on R• . Then (1) cd (R• ) ≤ 2 if and only if |C| ≤ 2. (2) cd (R• ) = 3 if and only if C is isomorphic to one of the following groups: C3 , C2 ⊕ C2 , or C3 ⊕ C3 . (3) cd (R• ) = 4 if and only if C is isomorphic to one of the following groups: C4 , C2 ⊕C4 , or C2 ⊕C2 ⊕C2 , or C3 ⊕ C3 ⊕ C3 . Suppose that |C| ≥ 3, C ∼ = Cn1 ⊕ · · · ⊕ Cnr with r ∈ N and 1 < n1 | n2 | · · · | nr , and that the following mild assumption on the Davenport constant of C holds: r j j1 k n X ni ko D(C) + 1 ≤ max nr , 1 + . 2 2 i=1 Then • (1) cd (R• ) = max ∆(R ) + 2 and n (2) cd (R• ) ≤ max nr , 1 3 2D(C) + 12 rnr + 2r o . Proof. The claims follow from Theorem 7.12 and the corresponding results for commutative Krull monoids (cf. Theorem 5.4 and Corollaries 4.3 and 5.6 in [GGS11]). Acknowledgments. We would like to thank Alfred Geroldinger for providing valuable feedback on preliminary versions of this paper and its contents. Moreover, we would like to thank the referee for his careful reading and a very helpful report. References [Ady60] [AM53] [And97] [BBG14] [BG14] [BGSG11] [BPA+ 11] S. I. Adyan. On the embeddability of semigroups in groups. Soviet Math. Dokl., 1:819–821, 1960. K. Asano and K. Murata. Arithmetical ideal theory in semigroups. J. Inst. Polytech. Osaka City Univ. Ser. A. Math., 4:9–33, 1953. D. D. Anderson, editor. Factorization in integral domains, volume 189 of Lecture Notes in Pure and Applied Mathematics, New York, 1997. Marcel Dekker Inc. D. Bachman, N. R. Baeth, and J. Gossell. Factorizations of upper triangular matrices. Linear Algebra Appl., 450:138–157, 2014. N. R. Baeth and A. Geroldinger. Monoids of modules and arithmetic of direct-sum decompositions. Pacific J. Math., 271(2):257–319, 2014. V. Blanco, P. A. Garcı́a-Sánchez, and A. Geroldinger. Semigroup-theoretical characterizations of arithmetical invariants with applications to numerical monoids and Krull monoids. Illinois J. Math., 55(4):1385–1414 (2013), 2011. N. R. Baeth, V. Ponomarenko, D. Adams, R. Ardila, D. Hannasch, A. Kosh, H. McCarthy, and R. Rosenbaum. Number theory of matrix semigroups. Linear Algebra Appl., 434(3):694–711, 2011. FACTORIZATION THEORY: FROM COMMUTATIVE TO NONCOMMUTATIVE SETTINGS [Bru69] [BW13] 45 H.-H. Brungs. Ringe mit eindeutiger Faktorzerlegung. J. Reine Angew. Math., 236:43–66, 1969. N. R. Baeth and R. Wiegand. Factorization theory and decompositions of modules. Amer. Math. Monthly, 120(1):3–34, 2013. [CGSL+ 06] S. T. Chapman, P. A. Garcı́a-Sánchez, D. Llena, V. Ponomarenko, and J. C. Rosales. The catenary and tame degree in finitely generated commutative cancellative monoids. Manuscripta Math., 120(3):253–264, 2006. [Cha81] M. Chamarie. Anneaux de Krull non commutatifs. J. Algebra, 72(1):210–222, 1981. [Cha84] A. W. Chatters. Noncommutative unique factorization domains. Math. Proc. Cambridge Philos. Soc., 95(1):49–54, 1984. [Cha05] S. T. Chapman, editor. Arithmetical properties of commutative rings and monoids, volume 241 of Lecture Notes in Pure and Applied Mathematics. Chapman & Hall/CRC, Boca Raton, FL, 2005. A. W. Chatters and D. A. Jordan. Noncommutative unique factorisation rings. J. London Math. Soc. (2), [CJ86] 33(1):22–32, 1986. H. Cohn and A. Kumar. Metacommutation of Hurwitz primes. Proc. Amer. Math. Soc., 143(4):1459–1469, 2015. [CK15] [Coh85] P. M. Cohn. Free rings and their relations, volume 19 of London Mathematical Society Monographs. Academic Press Inc. [Harcourt Brace Jovanovich Publishers], London, second edition, 1985. [Coh06] P. M. Cohn. Free ideal rings and localization in general rings, volume 3 of New Mathematical Monographs. Cambridge University Press, Cambridge, 2006. [CS03] J. H. Conway and D. A. Smith. On quaternions and octonions: their geometry, arithmetic, and symmetry. A K Peters Ltd., Natick, MA, 2003. [DD13] M. M. Deza and E. Deza. Encyclopedia of distances. Springer, Heidelberg, second edition, 2013. M. Deuring. Algebren. Zweite, korrigierte Auflage. Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 41. [Deu68] Springer-Verlag, Berlin, 1968. [DL07] J. Delenclos and A. Leroy. Noncommutative symmetric functions and W -polynomials. J. Algebra Appl., 6(5):815– 837, 2007. [EN89] D. R. Estes and G. Nipp. Factorization in quaternion orders. J. Number Theory, 33(2):224–236, 1989. [Est91] D. R. Estes. Factorization in quaternion orders over number fields. In The mathematical heritage of C. F. Gauss, pages 195–203. World Sci. Publ., River Edge, NJ, 1991. [FHL13] M. Fontana, E. Houston, and T. Lucas. Factoring ideals in integral domains, volume 14 of Lecture Notes of the Unione Matematica Italiana. Springer, Heidelberg, 2013. [Ger09] A. Geroldinger. Additive group theory and non-unique factorizations. In Combinatorial number theory and additive group theory, Adv. Courses Math. CRM Barcelona, pages 1–86. Birkhäuser Verlag, Basel, 2009. [Ger13] A. Geroldinger. Non-commutative Krull monoids: a divisor theoretic approach and their arithmetic. Osaka J. Math., 50(2):503–539, 2013. [GGRW05] I. Gelfand, S. Gelfand, V. Retakh, and R. L. Wilson. Factorizations of polynomials over noncommutative algebras and sufficient sets of edges in directed graphs. Lett. Math. Phys., 74(2):153–167, 2005. A. Geroldinger, D. J. Grynkiewicz, and W. A. Schmid. The catenary degree of Krull monoids I. J. Théor. Nombres [GGS11] Bordeaux, 23(1):137–169, 2011. A. Geroldinger and W. Hassler. Local tameness of v-Noetherian monoids. J. Pure Appl. Algebra, 212(6):1509–1524, [GH08] 2008. [GHK06] A. Geroldinger and F. Halter-Koch. Non-unique factorizations, volume 278 of Pure and Applied Mathematics (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2006. Algebraic, combinatorial and analytic theory. [GRSW05] I. Gelfand, V. Retakh, S. Serconek, and R. L. Wilson. On a class of algebras associated to directed graphs. Selecta Math. (N.S.), 11(2):281–295, 2005. [GRW01] I. Gelfand, V. Retakh, and R. L. Wilson. Quadratic linear algebras associated with factorizations of noncommutative polynomials and noncommutative differential polynomials. Selecta Math. (N.S.), 7(4):493–523, 2001. [Gry13] D. J. Grynkiewicz. Structural additive theory, volume 30 of Developments in Mathematics. Springer, Cham, 2013. [GY12] K. Goodearl and M. T. Yakimov. From quantum Ore extensions to quantum tori via noncommutative UFDs. 2012. preprint. [HR95] D. Haile and L. H. Rowen. Factorizations of polynomials over division algebras. Algebra Colloq., 2(2):145–156, 1995. [Jac43] N. Jacobson. The Theory of Rings. American Mathematical Society Mathematical Surveys, vol. I. American Mathematical Society, New York, 1943. [Jor89] D. A. Jordan. Unique factorisation of normal elements in noncommutative rings. Glasgow Math. J., 31(1):103–113, 1989. E. Jespers and Q. Wang. Noetherian unique factorization semigroup algebras. Comm. Algebra, 29(12):5701–5715, [JW01] 2001. [KV10] M. Kirschmer and J. Voight. Algorithmic enumeration of ideal classes for quaternion orders. SIAM J. Comput., 39(5):1714–1747, 2010. [Ler12] A. Leroy. Noncommutative polynomial maps. J. Algebra Appl., 11(4):1250076, 16, 2012. [LL04] T. Y. Lam and A. Leroy. Wedderburn polynomials over division rings. I. J. Pure Appl. Algebra, 186(1):43–76, 2004. [LLO08] T. Y. Lam, A. Leroy, and A. Ozturk. Wedderburn polynomials over division rings. II. In Noncommutative rings, group rings, diagram algebras and their applications, volume 456 of Contemp. Math., pages 73–98. Amer. Math. Soc., Providence, RI, 2008. [LLR06] S. Launois, T. H. Lenagan, and L. Rigal. Quantum unique factorisation domains. J. London Math. Soc. (2), 74(2):321–340, 2006. [LO04] A. Leroy and A. Ozturk. Algebraic and F -independent sets in 2-firs. Comm. Algebra, 32(5):1763–1792, 2004. 46 [MR01] [MVO12] [Phi10] [Rei75] [Rem80] [Ret10] [Sme13] [WF74] [ZM08] N. BAETH AND D. SMERTNIG J. C. McConnell and J. C. Robson. Noncommutative Noetherian rings, volume 30 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, revised edition, 2001. With the cooperation of L. W. Small. H. Marubayashi and F. Van Oystaeyen. Prime Divisors and Noncommutative Valuation Theory, volume 2059 of Lecture Notes in Mathematics. Springer, Berlin, 2012. A. Philipp. A characterization of arithmetical invariants by the monoid of relations. Semigroup Forum, 81(3):424– 434, 2010. I. Reiner. Maximal orders. Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], London-New York, 1975. London Mathematical Society Monographs, No. 5. J. H. Remmers. On the geometry of semigroup presentations. Adv. in Math., 36(3):283–296, 1980. V. Retakh. From factorizations of noncommutative polynomials to combinatorial topology. Cent. Eur. J. Math., 8(2):235–243, 2010. D. Smertnig. Sets of lengths in maximal orders in central simple algebras. J. Algebra, 390:1–43, 2013. R. A. Wagner and M. J. Fischer. The string-to-string correction problem. J. Assoc. Comput. Mach., 21:168–173, 1974. M. Zieve and P. Müller. On Ritt’s polynomial decomposition theorems. 2008. preprint. Department of Mathematics and Computer Science, University of Central Missouri, Warrensburg, MO 64093, USA E-mail address: [email protected] Institut für Mathematik und Wissenschaftliches Rechnen, Karl-Franzens-Universität Graz, Heinrichstraße 36, 8010 Graz, Austria E-mail address: [email protected]