Correspondence between factorability and normalization in monoids

0. Introduction

This paper investigates combinatorial properties of a certain class of monoids, seen from two different viewpoints, with a goal of unifying the two. The main result answers the question, explicitly mentioned in [6, 7], of determining the relation between these two approaches.

0.1. Factorability structures

The notion of factorability structure on monoids and categories is an extension by Wang [17] and Heß [11] of the definition of factorability structure on groups introduced by Bödigheimer and Visy [1] and Visy [16]. Their motivation was to abstract the structure, discovered in symmetric groups, that ensures the existence of a normal form admitting some remarkable properties. In particular, this normal form allows a reduction of the bar complex to a complex having considerably fewer cells, well adapted for computing homology of the algebraic structure in question.

This reduction is achieved using the theory of collapsing schemes, introduced in a topological flavor by Brown [3], elaborated for the algebraic setting by Cohen [5], and rediscovered (under the name of discrete Morse theory) by Forman [8]. The idea is to establish, for every nonnegative integer n, a bijection (called collapsing scheme in [3], and Morse matching in discrete Morse theory) between a class of n-cells called redundant and a class of $\left(n+1\right)$-cells called collapsible in such a way that collapsing matched pairs preserves the homotopy type.

The idea of factorability for a given monoid M and its generating set S is to determine a convenient way to split off a generator from an element of the monoid. This is achieved by the notion of factorability structure consisting of a factorization map $\eta =\left({\eta }^{\prime },\overline{\eta }\right):M\to M^2$ subject to several axioms ensuring, in particular, a compatibility with the multiplication in the monoid. In a manner of speaking, $\eta$ acts on an element f of M by splitting off a generator ${\eta }^{\prime }\left(f\right)$.

For every factorability structure, there is an associated rewriting system that is confluent but not necessarily terminating. However, termination is obtained under the additional assumption that, for all s in S and f in M, the following equalities hold:

Section 1 fixes basic terminology to be used throughout the paper. Basic notions and some results concerning factorability are recollected in Sec. 2.

0.2. Quadratic normalizations

Assume that a monoid is generated by a set S. By a normalization, we mean a syntactic transformation of an arbitrary word over S into a “canonical” one, called normal. Quadratic normalizations in monoids, introduced by Dehornoy and Guiraud [7] (influenced by Krammer [13]), generalize, under the same axiomatic setting, two well-known classes of normalizations: those arising from quadratic rewriting systems, as studied in [10] for Artin–Tits monoids and in [2, 4] for plactic monoids; and those arising from Garside families, as investigated in [6], resulting from successive generalizations of the greedy normal form in braid monoids, originating in the work of Garside [9]. Quadratic normalizations admit the following locality properties: a word is normal if, and only if, its length-two factors are normal; and the procedure of transforming a word into a normal one consists of a finite sequence of rewriting steps, each of which transforms a length-two factor.

The notion of class of a quadratic normalization is defined in order to measure the complexity of normalizing length-three words. The class $\left(m,n\right)$ means that every length-three word admits at most m rewriting steps starting from the left, and at most n rewriting steps starting from the right.

The class $\left(4,3\right)$ is explored in great detail in [7] as it exhibits exceptionally favorable computational properties. In particular, the rewriting system associated to a quadratic normalization of class $\left(4,3\right)$ is always convergent.

Quadratic normalizations are recalled in Sec. 3.

0.3. Contributions

We establish a correspondence between factorability structures and quadratic normalizations for monoids, despite the different origins and motivations for these two notions. By a correspondence, we mean maps (in both directions) that are inverse to each other, up to technicalities, between appropriate subclasses. Moreover, this bijection is compatible with the associated rewriting systems.

Since the rewriting system associated with a factorability structure is not necessarily terminating, whereas the rewriting system associated with a quadratic normalization of class $\left(4,3\right)$ is always terminating, it has already been known that a quadratic normalization corresponding to a factorability structure is not necessarily of class $\left(4,3\right)$.

It is shown here that a quadratic normalization corresponding to a factorability structure is always of class $\left(5,4\right)$ and not smaller in general. A necessary and sufficient condition is given for a quadratic normalization to correspond to a factorability structure. Thereby, we characterize factorable monoids in terms of quadratic normalizations, thus adding another important family of monoids to those unified under the axiomatic framework of quadratic normalizations.

In particular, a quadratic normalization of class $\left(4,3\right)$ always yields a factorability structure, but not vice versa. However, the converse does hold under the stronger condition described as follows. For a monoid M, consider the map $F:=\eta \circ \mu$ from the set $M^2$ to itself, with $\mu :M^2\to M$ denoting the multiplication in M. Denote by $F_1$ (respectively, $F_2$) the application of F to the first two elements (respectively, the second and the third element) of a triple in $M^3$. In general, a factorability structure for M and its generating set S ensures the equality

for each S-word $\left(r,s,t\right)$ such that $F_2{F}_1{F}_2\left(r,s,t\right)$ contains no 1. The stronger condition states that this equality holds for every $\left(r,s,t\right)$ in $S^3$. Since this condition is implied by the class $\left(4,3\right)$, quadratic normalizations of class $\left(4,3\right)$ are characterized in terms of factorability structures.

Furthermore, we show that this stronger condition is equivalent to the aforementioned additional assumption (0.1) which is known to grant termination of the rewriting system associated with a factorability structure. Simply put, the class $\left(4,3\right)$ equals factorability plus termination.

One of the benefits of the established correspondence between factorability structures and quadratic normalizations is that it provides a way of importing the results concerning homology, derived from the former (see e.g. [12, 16, 17]) to the framework of the latter, with the hope of generalizing them to higher classes. This would be our next step in the current direction of research.

To simplify the presentation, we are considering exclusively monoids, but results stated here (recalled ones as well as new ones) mostly extend to categories, seen as monoids with partial multiplication. As a reminder that a monoid is thought of as a monoid of endomorphisms (of an object), we tend to use letters f, g and h for elements of a monoid.

1. Preliminaries

1.1. Normal forms and rewriting systems

If S is a set, $S^{\ast }$ denotes the free monoid over S. Elements of S and $S^{\ast }$ are called S-letters and S-words, respectively. So, an S-word is a finite sequence^a of S-letters, e.g. $\left(s_1,\dots ,s_n\right)$. The prefix S- is sometimes left out when the considered generating set is evident from the context. The product in $S^{\ast }$ of two words u and v is denoted by $u|v$. A letter s is customarily identified with the single-letter word $\left(s\right)$. Accordingly, a word $\left(s_1,\dots ,s_n\right)$ can be written as the product (in $S^{\ast }$) of its letters: $s_1|\cdots |s_n$.

A monoid M is said to be generated by a set S, often written as $\left(M,S\right)$, if M is a homomorphic image of the free monoid $S^{\ast }$. Such a homomorphism is called an evaluation map and denoted ${EV}:S^{\ast }\to M$. A normal form for M with respect to S is a set-theoretic section, denoted by ${NF}$, of the evaluation map. To rephrase it, a normal form maps elements of M to distinguished representative words in $S^{\ast }$.

The length of w in $S^{\ast }$ is denoted by $\left|w\right|$. For an element f of M, the minimal S-length of an S-word representing f is denoted by $\left|f\right|$. A normal form ${NF}$ for a monoid M with respect to a generating set S is called geodesic if, for every f in M, the inequality $\left|{NF}\left(f\right)\right|\le \left|w\right|$ holds for every S-word w representing f, i.e. such that ${EV}\left(w\right)=f$.

A (word) rewriting system is a pair $\left(S,R\right)$ consisting of a set S and a binary relation R on $S^{\ast }$, whose elements are called rewriting rules. An element $\left(u,v\right)$ of R is also written as $u\to v$ to stress the fact that it is directed. Seeing relations between words not as equalities but as rewriting rules is a key concept of rewriting theory.

For a rewriting rule $\left(u,v\right)$, and for w and $w^{\prime }$ in $S^{\ast }$, a pair $\left(w|u|w^{\prime },w|v|w^{\prime }\right)$ is called a rewriting step. For u and v in $S^{\ast }$, we say that urewrites to v if there is a finite composable sequence of rewriting steps, such that the source of the first step of the sequence is u and the target of the last step is v. A word u is called irreducible with respect to R if there is no rewriting step whose source is u.

A rewriting system $\left(S,R\right)$ is called:

•	Confluent if any two rewriting sequences starting with the same word can be completed in such a way that they eventually reach a common result;
•	Normalizing if every u in $S^{\ast }$ rewrites to at least one irreducible word;
•	Terminating if it admits no infinite rewriting sequence;
•	Convergent if it is both confluent and terminating;
•	Reduced (or minimal) if for every rewriting rule $u\to v$, the word v is irreducible with respect to R, and the word u is irreducible with respect to $R\backslash \left\{\left(u,v\right)\right\}$;
•	Strongly reduced if it is reduced and, in addition, every element of S is irreducible;
•	Quadratic if the source and target of every element of R are of length 2.

The monoid presented by a rewriting system $\left(S,R\right)$ is the quotient M of the free monoid $S^{\ast }$ by the congruence relation generated by R. If $\left(S,R\right)$ is confluent, the irreducible word to which a word w rewrites, if it exists, is denoted by $ŵ$. If $\left(S,R\right)$ is convergent, the map $M\to S^{\ast }$ defined by $f\mapsto ŵ$, with ${EV}\left(w\right)=f$, is the normal form associated with the rewriting system $\left(S,R\right)$.

Remark 1.1. If a generating set S of a monoid M is a subset of M, then elements of S can be regarded in two ways: as length-one words in $S^{\ast }$, and as elements of M. When a rewriting system presenting M with respect to S is strongly reduced, this makes no essential difference, so elements of S are denoted in the same way, regardless of the viewpoint, relying on the context to provide the proper interpretation. In particular, one can say that a generating set contains (or that it does not contain) 1, the identity element of a monoid. This phrasing is the custom in the context of factorability (see [11, 12, 15]), but not in the context of normalization where a generating set is commonly distinguished from its image under the evaluation map (see [7]). So, we will emphasize such situation by calling S a generating subset, not just a generating set, of M. When we characterize factorable monoids in terms of quadratic normalizations (Sec. 4.1), the corresponding normalizations will be eligible to share this custom so there will be no need to emphasize it.

For technical reasons, in the rest of this paper, the letter S will be reserved for the following purpose.

Convention 1.2. When the letter S is used to denote a generating set of a monoid, it is understood that S is a pointed set^b whose basepoint is a letter, customarily denoted by e, representing the identity of the considered monoid. In accordance with Remark 1.1, the basepoint of S is denoted by 1 if S is a generating subset of the considered monoid.

On the other hand, if we exclude this letter from S, we write $S_{+}$ for the resulting generating set.

1.2. Divisibility in monoids

A monoid M is said to be left-cancellative (respectively, right-cancellative) if, for every f, g and $g^{\prime }$ in M, the equality $fg=f{g}^{\prime }$ (respectively, $gf=g^{\prime }f$) implies the equality $g=g^{\prime }$.

An element f of a monoid M is called a left divisor of g in M, and g is called a right multiple of f, denoted by $f\preccurlyeq g$, if there is an element $f^{\prime }$ in M such that $f{f}^{\prime }=g$. If M is left-cancellative, then the element $f^{\prime }$ is uniquely determined and called the right complement offing.

2. Factorability Structures

This section recalls the notion of factorability structure. Section 2.1 recollects the basic terminology. In Sec. 2.2, we recall an alternative approach to factorability through the notion of local factorability. Certain notions are redefined here in order to overcome the issues arising from the original definition, which are pointed out in Sec. 2.3. Finally, Sec. 2.4 recalls the rewriting system associated with a factorability structure. For elaboration, the reader is referred to [12, 15].

2.1. Factorability structures

Convention 2.1. Let us adopt the convention that elements of a finite sequence are indexed starting from the leftmost one, as in $\left(s_1,s_2,\dots ,s_n\right)$, thereby not following the convention used in [12] where elements are indexed starting from the rightmost one. The purpose is to make the notions that concern factorability more easily comparable (in Sec. 4) with those concerning normalization.

A pair $\left(f,g\right)$ in $M^2$ is called geodesic if $\left|fg\right|=\left|f\right|+\left|g\right|$.

Let M be a monoid, and let S be a generating subset of M. A factorization map for $\left(M,S\right)$ is a map $\eta =\left({\eta }^{\prime },\overline{\eta }\right):M\to M^2$ satisfying the following conditions:

•	For f in $M\backslash \left\{1\right\}$, the element ${\eta }^{\prime }\left(f\right)$ in $S_{+}$ is a left divisor of f, and the element $\overline{\eta }\left(f\right)$ is a right complement of ${\eta }^{\prime }\left(f\right)$ in f;
•	The pair $\left({\eta }^{\prime }\left(f\right),\overline{\eta }\left(f\right)\right)$ is geodesic;
•	$\eta$ maps 1, the identity element of M, to $\eta \left(1\right)=\left(1,1\right)$.

Whenever confusion is unlikely, ${\eta }^{\prime }\left(f\right)$ and $\overline{\eta }\left(f\right)$ are abbreviated to $f^{\prime }$ and $\overline{f}$, respectively.

Example 2.2. Assume that M is a free commutative monoid generated by a nonempty finite totally ordered set. Define $\eta =\left({\eta }^{\prime },\overline{\eta }\right):M\to M^2$ by setting ${\eta }^{\prime }\left(f\right)$ to be the least left divisor of f, lying in the generating set. Note that this is well defined since the left cancellation property of M implies uniqueness of right complements, so knowing ${\eta }^{\prime }\left(f\right)$ determines $\overline{\eta }\left(f\right)$.

Notation 2.3. Let A be a set, and let F be a map from $A^k$ to $A^l$. Then the (partial) map $F_i:A^{\ast }\to A^{\ast }$ consists of applying F to k consecutive elements starting from the position i, i.e. to the elements at the positions $i,i+1,\dots ,i+k-1$.

Example 2.4. For the sake of illustration, take the set $A=\left\{a,b,c\right\}$ totally ordered by $a<b<c$. We write ${<}^{\ast }$ for the lexicographic extension of $<$ to $A^{\ast }.$ Let $F:A^2\to A^2$ map each length-two word w to the ${<}^{\ast }$-minimal word obtained by simply permuting letters of w if needed. Then we have

The multiplication in M is denoted by $\mu :M^2\to M$, and $\mu \left(f,g\right)$ is often abbreviated to $f\cdot g$ or $fg$.

Definition 2.5 ([12, Definition 2.1]). Let M be a monoid, and let S be a generating subset of M. A factorability structure on $\left(M,S\right)$ is a factorization map $\eta :M\to M^2$ such that, denoting the map $\eta \circ \mu :M^2\to M^2$ by F, for every triple in $M^3$, the three maps

coincide or each map reduces the sum of the lengths of the elements of the triple. If $\eta :M\to M^2$ is a factorability structure on $\left(M,S\right)$, we call the triple $\left(M,S,\eta \right)$ a factorable monoid.

Assume that $\left(M,S,\eta \right)$ is a factorable monoid. The normal form associated with the factorability structure $\eta$, or the $\eta$-normal form, for short, is the map ${{NF}}_{\eta }:M\to S^{\ast }$ defined as

Example 2.6. The map $F:A^2\to A^2$ in Example 2.4 can be regarded as a composition $\eta \circ \mu$ of the multiplication in $A^{\ast }$ and a factorability structure splitting off the least letter. For $f=bacabc$, we get

For a factorable monoid $\left(M,S,\eta \right)$, an M-word x is said to be stable at theith position if $F_i\left(x\right)=x$; it is everywhere stable if it is stable at the ith position for every i in $\left\{1,\dots ,\left|x\right|-1\right\}$. The normal form ${{NF}}_{\eta }$ admits the following locality property.

Lemma 2.7 ([11, Remark 2.1.27]). Let $\left(M,S,\eta \right)$ be a factorable monoid. Then for every f in M, the $\eta$-normal form is everywhere stable.

Although it may appear that [11, Remark 2.1.27] uses an extra condition, namely, “the recognition principle”, this is not the case since this condition is automatically satisfied in a factorable monoid (see [11, Lemma 2.2.2]).

2.2. Local factorability structure

There is an alternative definition of factorability by use of the notion of local factorability, due to Moritz Rodenhausen. In order to resolve an issue detected in the original definition of local factorability (to be addressed in the next section), we introduce the following notation.

Notation 2.8. Let A be a set, and let $\phi$ be a map from $A^2$ to itself. The composite map $\underrightarrow{\phi }:A^{\ast }\to A^{\ast }$ is defined as

Note that, in the above composition, ${\phi }_{\left|w\right|-1}$ is applied last, taking the rightmost length-two factor of ${\phi }_{\left|w\right|-2}\cdots {\phi }_1\left(w\right)$ as an argument. In particular, if w has length 1, then $\underrightarrow{\phi }\left(w\right)=w.$

Definition 2.9. Let S be a pointed set with basepoint 1, and let $\phi$ be a map from $S^2$ to itself. The normalization map associated with the map $\phi$ is a map $N_{\phi }$ from $S^{\ast }$ to itself, defined as follows:

(1)	$N_{\phi }$ of the empty word is the empty word;
(2)	$N_{\phi }$ of a word containing 1 equals $N_{\phi }$ of the same word with 1 removed; and
(3)	$N_{\phi }\left(s_1,\dots ,s_n\right):=\left\{\begin{array}{cc}\underrightarrow{\phi }\left(s_1|N_{\phi }\left(s_2,\dots ,s_n\right)\right)\hfill & \text{if it contains no }1,\hfill \\ N_{\phi }\left(\underrightarrow{\phi }\left(s_1|N_{\phi }\left(s_2,\dots ,s_n\right)\right)\right)\hfill & \text{otherwise}.\hfill \end{array}\right.$

Remark 2.10. Note that, by recursion, the computation of $N_{\phi }\left(s_1,\dots ,s_n\right)$ terminates and its length is bounded by n. Namely, all the recursive calls for $N_{\phi }$ are made on words of smaller length: directly in (2) and in the first case of (3); and indirectly in the second case of (3), which calls for (2). The length of $N_{\phi }\left(s_1,\dots ,s_n\right)$ is less than or equal to the length of $\underrightarrow{\phi }\left(s_1|N_{\phi }\left(s_2,\dots ,s_n\right)\right)$, which is less than or equal to the length of $N_{\phi }\left(s_2,\dots ,s_n\right)$ plus 1.

We state anew the definition of local factorability structure on $\left(M,S\right)$, using Definition 2.9.

Definition 2.11. Let M be a monoid and let S be a generating subset of M. A local factorability structure is a map $\phi$ from $S^2$ to itself, having the following properties:

(1)	M admits the presentation $$〈S_{+}|\left\{\left(s,t\right)=\phi \left(s,t\right)|s,t\in S_{+}\right\}〉;$$
(2)	$\phi$ is idempotent;
(3)	$\phi \left(1,s\right)$ equals $\left(s,1\right)$ for every s in $S_{+}$;
(4)	For every $\left(r,s,t\right)$ in $S_{+}^3$, the equality $${\phi }_1{\phi }_2{\phi }_1{\phi }_2\left(r,s,t\right)={\phi }_2{\phi }_1{\phi }_2\left(r,s,t\right)$$ holds or ${\phi }_2{\phi }_1{\phi }_2\left(r,s,t\right)$ contains 1;
(5)	The normalization map associated with $\phi$ satisfies $$N_{\phi }\left(r,s,t\right)=N_{\phi }\left({\phi }_1\left(r,s,t\right)\right),$$ for every $\left(r,s,t\right)$ in $S^3$.

By Definition 2.9, for every S-word w, the word $N_{\phi }\left(w\right)$ contains no 1. If we add to $N_{\phi }\left(w\right)$ a string of 1’s on the right, then the result is called an extended form of $N_{\phi }\left(w\right)$.

Lemma 2.12 ([15, Lemma 2.3.5]). Let S be a pointed set with basepoint $1$, and let $\phi$ be a map from $S^2$ to itself. If $\phi$ formally satisfies the second, the third and the fourth condition of Definition 2.11, then ${\phi }_1{\phi }_2{\phi }_1{\phi }_2\left(r,s,t\right)$ is an extended form of $N_{\phi }\left(r,s,t\right)$ for every S-word $\left(r,s,t\right)$.

A factorability structure is equivalent to a local factorability structure, in the following sense.

Theorem 2.13 ([12, Theorem 3.4]).

(1)	If $\left(M,S,\eta \right)$ is a factorable monoid, then the restriction of the map $\eta \mu$ to $S^2$ defines a local factorability structure on M.
(2)	Conversely, one can construct a factorability structure out of a local factorability structure by setting $\eta \left(1\right)=\left(1,1\right)$ and $$\eta \left(f\right)=\left(r_1,{EV}\left(r_2,\dots ,r_n\right)\right)for{N}_{\phi }\left(w\right)=\left(r_1,r_2,\dots ,r_n\right),$$ with w being any S-word representing f.
(3)	These constructions are inverse to each other.
(4)	By this correspondence, for f in M, the $\eta$-normal form ${{NF}}_{\eta }\left(f\right)$ equals $N_{\phi }\left(w\right)$ for any S-word w representing f.

The proof of Theorem 2.13 can be found in [15, Sec. 2.3].

Remark 2.14. Here are some observations about local factorability structures that will be used implicitly from now on.

•	The property (3) of Theorem 2.9 implies $N_{\phi }\left(s\right)=s$ for every s in $S_{+}$.
•	For every S-word $\left(s,t\right)$, the first element of $\phi \left(s,t\right)$ cannot be equal to 1 unless the second element is equal to 1. Namely, assume the opposite: $\phi \left(s,t\right)=\left(1,t^{\prime }\right)$ for $t^{\prime }\ne 1$. Then the idempotency of $\phi$ gives $\phi \left(1,t^{\prime }\right)=\left(1,t^{\prime }\right)$, which contradicts the property (3) of Definition 2.11.
•	Note that, by Theorem 2.13, the equality $\phi \left(s,t\right)=\left(1,1\right)$ holds if, and only if, $st=1$ in M.

2.3. Deviation from the original definition

As Convention 2.1 hints, the original definition of factorization map, which separates a right divisor, is reformulated in Sec. 2.1 to separate a left divisor, instead. The definition of local factorability structure is also modified.

Let us recall the original definition of local factorability structure, in order to justify its present modification (Definition 2.11). For simplicity, we still assume Convention 1.2, so we do not actually copy the original verbatim, but we do preserve its essence (as well as the convention of indexing from the right).

Here is a recollection of [12, Definition 3.3]. Let M be a monoid, and let S be a generating subset of M. A local factorability structure on $\left(M,S\right)$ is a map $\phi$ from $S^2$ to itself, having the following properties:

(1)	M admits the presentation $$〈S_{+}|\left\{\left(t,s\right)=\phi \left(t,s\right)|s,t\in S_{+}\right\}〉;$$
(2)	$\phi$ is idempotent;
(3)	$\phi \left(s,1\right)$ equals $\left(1,s\right)$ for every s in $S_{+}$;
(4)	For every $\left(t,s,r\right)$ in $S_{+}^3$, applying any ${\phi }_i$ to the triple ${\phi }_2{\phi }_1{\phi }_2\left(t,s,r\right)$ leaves it unchanged, or ${\phi }_2{\phi }_1{\phi }_2\left(t,s,r\right)$ contains 1;
(5)	$\text{NF}\left(t,s,r\right)=\text{NF}\left({\phi }_1\left(t,s,r\right)\right)$ for all $\left(t,s,r\right)$ in $S_{+}^3$.

Here, the map $\text{NF}$ from $S^{\ast }$ to itself is defined inductively on the length of the word, as follows:

•	$\text{NF}$ of the empty word is the empty word;
•	$\text{NF}\left(s\right)$ equals s for all s in $S_{+}$;
•	$\text{NF}$ of a word containing 1 equals $\text{NF}$ of the same word with 1 removed; and
•	$\text{NF}\left(s_n,\dots ,s_1\right):=\left\{\begin{array}{cc}{\phi }_{n-1}\cdots {\phi }_1(\text{NF}(s_n,\dots ,s_2),s_1)\hfill & \text{if it contains no}1,\hfill \\ \text{NF}({\phi }_{n-1}\cdots {\phi }_1(\text{NF}(s_n,\dots ,s_2),s_1))\hfill & \text{otherwise}.\hfill \end{array}\right.$

Remark 2.15. Note that there is a flaw in the above definition. Since $\phi$ is defined on the domain $S^2$, it is not clear what should one do when one gets the expression of the form $\phi \left(s\right)$, where s is a single element of $S_{+}$. However, such an expression may indeed occur if $\phi$ is applied just after $\text{NF}$ has eliminated 1 and thus shortened the word in question. For instance, take $s_2=1$. Then

which is not defined. We have resolved this issue by introducing Notation 2.8.

Remark 2.16. Note that, in [12, 15], the map $\text{NF}:S^{\ast }\to S^{\ast }$ is called the normal form. In this text (following [7]), however, a normal form is a map from the presented monoid, not from the free monoid over a generating set (recall Sec. 1.1). Accordingly, we do not call the map $N_{\phi }$, which is an analogue of $\text{NF}$, a normal form. Instead, we call such a syntactic transformation (of arbitrary words to normal ones) a normalization map (as in Definition 2.9).

2.4. Rewriting system associated with factorability

A rewriting system is associated with a factorable monoid in a canonical way.

Lemma 2.17 ([12, Lemma 5.1]). Let $\left(M,S,\eta \right)$ be a factorable monoid. If R is the set of rewriting rules of the form

for all $S_{+}$-words s and t such that $\left(s,t\right)$ is not stable, then $\left(S_{+},R\right)$ is a confluent, strongly reduced rewriting system presenting M. Here, if $\overline{\eta }\left(st\right)=1$, then the rewriting rule is interpreted as $\left(s,t\right)\to st$.

Remark 2.18. Observe that, strictly speaking, the presentation given by the property (1) of Definition 2.11 (of local factorability structure) is not the same as the one obtained by turning rewriting rules into equations in Lemma 2.17. Namely, if $st$ lies in S (respectively, equals 1), then the former contains the relation $\left(s,t\right)=\left(st,1\right)$ (respectively, $\left(s,t\right)=\left(1,1\right)$), whereas the latter has $\left(s,t\right)=st$ (respectively, $\left(s,t\right)=1$). However, one can obtain the latter from the former simply by removing the rightmost occurrence of 1, and vice versa.

The associated rewriting system in Lemma 2.17 is not necessarily terminating, even if S is finite and M is left-cancellative. The reader is referred to [12, Appendix] for an example of a factorable monoid whose associated rewriting system is not terminating. The following result gives a sufficient condition for the rewriting system associated with a factorable monoid to be terminating.

Theorem 2.19 ([12, Theorem 7.3]). Let $\left(M,S,\eta \right)$ be a factorable monoid. If the equalities

hold for all s in $S_{+}$ and f in M, then the associated rewriting system is terminating.

3. Quadratic Normalizations

This section recalls the notion of quadratic normalization. After presenting basic notions concerning normalization in Sec. 3.1, we recollect the notion of quadratic normalization in Sec. 3.2. Then we focus on a particular class of quadratic normalizations in Sec. 3.3. The rewriting system associated with a quadratic normalization is recalled in Sec. 3.4. Finally, Sec. 3.5 recalls the notion of left-weighted normalization. For technical elaboration, see [7].

3.1. Normalization and normal form

Having already hinted in the Introduction that a normalization is a syntactic transformation of an arbitrary word to a normal one, here we recall a formal definition.

Definition 3.1. Let A be a set, and let N be a map from $A^{\ast }$ to itself. The pair $\left(A,N\right)$ is called a normalization if

(1)	N is length-preserving;
(2)	Restriction of N to A is the identity map;
(3)	The equality $$N\left(u|v|w\right)=N\left(u|N\left(v\right)|w\right)$$ holds for all A-words u, v, w.

The map N is called a normalization map. An A-word w such that $N\left(w\right)=w$ is called N-normal.

A normalization for a monoidM is a normalization $\left(S_{+},N\right)$ such that M admits the presentation

Remark 3.2. Recall that the usage of the letter S, as well as the subscript $+$ in $S_{+}$ (or the absence of it), is explained by Convention 1.2. The letter S is not used in Definition 3.1 (of normalization), in order to point out that normalization itself is a purely syntactic notion, as opposed to the notion of normalization for a monoid.

Example 3.3 ([7, Example 2.2]). Assume that $\left(A,<\right)$ is a totally ordered nonempty finite set. Let ${<}^{\ast }$denote the lexicographic extension of $<$ to $A^{\ast }$. The image under N of an A-word w is defined as the ${<}^{\ast }$-minimal word obtained by permuting letters of w. Then $\left(A,N\right)$ is a normalization for the free commutative monoid over A.

Note that the definition of normalization for a monoid M implies that there is a nontrivial monoid homomorphism, also known as grading, from M to the additive monoid of nonnegative integers, such that the degree, i.e. image under grading, of every s in $S_{+}$ equals 1. Namely, set the degree of f in M to be the common length of all the $S_{+}$-words representing f (which is well defined due to the property (1) of normalization). Such monoids $\left(M,S_{+}\right)$ are called graded. In other words, M is graded with respect to a generating set $S_{+}$ if all $S_{+}$-words representing the same element of M are equal in length.

Remark 3.4 ([7, Proposition 2.6]). In a graded monoid, a normalization and a normal form are just different aspects of looking at the same notion. Indeed, given a normalization $\left(S_{+},N\right)$ for a monoid M, a normal form ${NF}$ for M with respect to $S_{+}$ is obtained by setting ${NF}\left(f\right)=N\left(w\right)$ for any $S_{+}$-word w representing f. Conversely, if ${NF}$ is a normal form for a graded monoid M with respect to a generating set $S_{+}$, then one obtains a normalization map by setting $N\left(w\right)={NF}\left({EV}\left(w\right)\right)$. These two correspondences are inverse to each other.

On the other hand, if a monoid $\left(M,S_{+}\right)$ is not graded, i.e. if an element of M may be represented by $S_{+}$-words of different lengths, then a new letter representing 1 can be introduced to formally preserve length. For a normalization $\left(S,N\right)$, we say that an element e of S is N-neutral if the equalities

hold for every S-word w. We say that $\left(S,N\right)$ is a normalization mod e for a monoid M if e is an N-neutral element of S and M admits the presentation Note that there can be at most one N-neutral element. We write ${\pi }_e$ for the canonical projection from $S^{\ast }$ onto $S_{+}^{\ast }$, which removes all the occurrences of e. This extends the equivalence between normalization and normal form from graded monoids to monoids in general.

Proposition 3.5 ([7, Proposition 2.9]).

(1)	If $\left(S,N\right)$ is a normalization mod e for a monoid M, then a geodesic normal form ${NF}$ for M with respect to S is obtained by ${NF}\left(f\right)={\pi }_e\left(N\left(w\right)\right)$ for any S-word w representing f.
(2)	Conversely, let ${NF}$ be a geodesic normal form for a monoid M with respect to a generating set $S_{+}$. Write ${{EV}}^e$ for the extension of the evaluation map ${EV}:S_{+}^{\ast }\to M$ to $S^{\ast }$by putting ${{EV}}^e\left(e\right)=1$. Then a normalization $\left(S,N\right)$ mod e for M is provided by the map $$N\left(w\right)={NF}\left({{EV}}^e\left(w\right)\right)|e^m,$$ with m denoting the number of letters e to be added in order to formally preserve length, namely, $m=\left|w\right|-\left|{NF}\left({{EV}}^e\left(w\right)\right)\right|$.
(3)	These two correspondences are inverse to each other.

Remark 3.6 ([7, Remark 2.10]). If a monoid $\left(M,S_{+}\right)$ is graded and ${NF}$ is a normal form on $\left(M,S_{+}\right)$, then there are two normalizations arising from ${NF}$, provided by Remark 3.4 and Proposition 3.5(2), respectively. To make a clear distinction, let us temporarily write $N_{+}$ for the normalization map of the former. The normalizations $\left(S_{+},N_{+}\right)$ and $\left(S,N\right)$ are closely related as the map ${\pi }_e\circ N$ is identically equal to the map $N_{+}\circ {\pi }_e$. Therefore, it suffices to formally consider normalizations mod e for monoids.

3.2. Quadratic normalizations

Let us extend Notation 2.3.

Notation. For a finite sequence of positive integers $u=\left(i_1,\dots ,i_n\right)$, we denote the composite map $F_{i_n}\circ \cdots \circ F_{i_1}$ (note that $F_{i_1}$ is applied first) by $F_u$, often omitting commas in u if all its components are single-digit numbers.

If $\left(A,N\right)$ is a normalization, let $\overline{N}$ denote the restriction of N to the set of all length-two A-words.

Definition 3.7. A normalization $\left(A,N\right)$ is quadratic if the following two requirements are met:

(1)	An A-word w is N-normal (meaning $N\left(w\right)=w$) if, and only if, every length-two factor of w is N-normal.
(2)	For every A-word w, there exists a finite sequence of positions u, depending on w, such that $N\left(w\right)={\overline{N}}_u\left(w\right)$.

Example 3.8. The normalization given in Example 3.3 is quadratic. Indeed, a word is ${<}^{\ast }$-minimal if, and only if, its every length-two factor is ${<}^{\ast }$-minimal; and each word can be ordered by switching pairs of adjacent letters that are not ordered as expected.

An advantage of a quadratic normalization is that it is completely determined by the restriction $\overline{N}$.

Proposition 3.9 ([7, Proposition 3.6]).

(1)	If $\left(S_{+},N\right)$ is a quadratic normalization for a monoid M, then $\overline{N}$ is idempotent and M admits the presentation $$〈S_{+}|\left\{s|t=\overline{N}\left(s|t\right)|s,t\in S_{+}\right\}〉.$$
(2)	If $\left(A,N\right)$ is a quadratic normalization, then an element e of A is N-neutral if, and only if, the following equalities hold for every s in A: $$\overline{N}\left(s|e\right)=\overline{N}\left(e|s\right)=\overline{N}\left(s\right)|e.$$
(3)	If $\left(S,N\right)$ is a quadratic normalization mod e for a monoid M, then $\overline{N}$ is idempotent and M admits the presentation $$〈S_{+}|\left\{s|t={\pi }_e\left(\overline{N}\left(s|t\right)\right)|s,t\in S_{+}\right\}〉.$$

If $\left(A,N\right)$ is a quadratic normalization, then the image under N of an A-word is computed by sequentially applying $\overline{N}$ to length-two factors at various positions. For length-three words, there are only two such positions. Since $\overline{N}$ is idempotent, it suffices to consider alternating sequences of positions. This motivates the notion of class, which measures the complexity of normalizing length-three words. For a nonnegative integer m, we write $12\left[m\right]$ (respectively, $21\left[m\right]$) for the alternating sequence $121\dots$ (respectively, $212\dots$) of length m. A quadratic normalization $\left(A,N\right)$ is said to be of left-classm (respectively, right-classn) if the equality $N\left(w\right)={\overline{N}}_{12\left[m\right]}\left(w\right)$ (respectively, $N\left(w\right)={\overline{N}}_{21\left[n\right]}\left(w\right)$) holds for every length-three A-word w. A quadratic normalization $\left(A,N\right)$ is of class $\left(m,n\right)$ if it is of left-class m and of right-class n.

Example 3.10. Let us consider the quadratic normalization given in Example 3.3. If A has only one element, then there is only one A-word of length 3 and it is N-normal. So, $\left(A,N\right)$ is of class $\left(0,0\right)$ in this case.

If A has at least two elements, then, for every length-three A-word w, the words ${\overline{N}}_{121}\left(w\right)$ and ${\overline{N}}_{212}\left(w\right)$ are N-normal. Namely, assuming that the word $a|b|c$ is normal, compute ${\overline{N}}_{121}$ and ${\overline{N}}_{212}$ of $c|b|a$ (which provides the worst-case scenario):

Therefore, $\left(A,N\right)$ is of class $\left(3,3\right)$ in this case. A smaller class cannot be obtained in general, as witnessed by ${\overline{N}}_{12}\left(b|b|a\right)=b|a|b$ and ${\overline{N}}_{21}\left(b|a|a\right)=a|b|a$, with a and b being any two A-letters such that $a<b$.

A class of a quadratic normalization $\left(A,N\right)$ can be characterized by relations involving only the restriction $\overline{N}$.

Proposition 3.11 ([7, Proposition 3.14]). A quadratic normalization $\left(A,N\right)$ is

(1)	Of left-class m if, and only if, the following three maps coincide on $A^3:$ $${\overline{N}}_{12\left[m\right]},{\overline{N}}_{12\left[m+1\right]},{\overline{N}}_{21\left[m+1\right]}.$$
(2)	Of right-class n if, and only if, the following three maps coincide on $A^3:$ $${\overline{N}}_{21\left[n\right]},{\overline{N}}_{21\left[n+1\right]},{\overline{N}}_{12\left[n+1\right]}.$$
(3)	Of class $\left(m,m\right)$ if, and only if, the map ${\overline{N}}_{12\left[m\right]}$ coincides with the map ${\overline{N}}_{21\left[m\right]}$ on $A^3$.

The minimal left-class of $\left(A,N\right)$ is the smallest natural number m such that $\left(A,N\right)$ is of left-class m if such m exists, and $\infty$ otherwise. The minimal right-class n of $\left(A,N\right)$ is defined analogously. Then the minimal class of $\left(A,N\right)$ is the pair $\left(m,n\right)$.

Lemma 3.12 ([7, Lemma 3.13]). The minimal class of quadratic normalization is either of the form $\left(m,n\right)$ with $\left|m-n\right|\le 1$, or $\left(\infty ,\infty \right)$.

For example, the minimal class of the quadratic normalization considered in Example 3.10 is $\left(3,3\right)$ if the generating set has at least two elements.

3.3. Quadratic normalizations of class $\left(4,3\right)$

The class $\left(4,3\right)$ has particularly nice computational properties (see [7, Sec. 4]), not shared by higher classes (see [7, Example 3.23]), thanks to the diagrammatic tool called the domino rule. Let A be a set, and let F be a map from $A^2$ to itself. We say that the domino rule is valid for F if, for all $r_1$, $r_2$, $r_1^{\prime }$, $r_2^{\prime }$, $s_0$, $s_1$, $s_2$ in A such that $F\left(s_0|r_1\right)=r_1^{\prime }|s_1$ and $F\left(s_1|r_2\right)=r_2^{\prime }|s_2$, the following implication holds: if $r_1|r_2$ and $r_1^{\prime }|s_1$ and $r_2^{\prime }|s_2$ are fixed points of F, then so is $r_1^{\prime }|r_2^{\prime }$. The domino rule is expressed by the commutative diagram

where arcs denote fixed points of F: the solid ones are assumptions, and the dashed one is the expected conclusion.

Proposition 3.13 ([7, Lemma 4.2]). A quadratic normalization $\left(A,N\right)$ is of class $\left(4,3\right)$ if, and only if, the domino rule is valid for $\overline{N}$.

The domino rule allows one to devise a simple universal recipe for computing the images under a normalization map. We refer the reader to [7, Proposition 4.4] for details, while here we only recall the key step.

Lemma 3.14 ([7, Lemma 4.5]). If $\left(A,N\right)$ is a quadratic normalization of class $\left(4,3\right)$, then, for every s in A and every N-normal A-word $r_1|\cdots |r_n$, we have

Remark 3.15. Note, in particular, that Lemma 3.14 implies that the leftmost letter of $N\left(s|r_1|\cdots |r_n\right)$ does not depend on $r_2,\dots ,r_n$, but only on s and $r_1$. We will use this observation in Sec. 4.2.

By Proposition 3.11(2), if $\left(A,N\right)$ is a quadratic normalization of class $\left(4,3\right)$, then the maps ${\overline{N}}_{1212}$, ${\overline{N}}_{212}$ and ${\overline{N}}_{2121}$ coincide on $A^3$. One of the major results of [7] is the converse: every idempotent map satisfying such condition arises from a quadratic normalization of class $\left(4,3\right)$, in the following sense.

Proposition 3.16 ([7, Proposition 4.7]). Let A be a set, and let F be a map from $A^2$ to itself. If F is idempotent, and if the maps $F_{1212}$, $F_{212}$ and $F_{2121}$ coincide on $A^3$, then there is a quadratic normalization $\left(A,N\right)$ of class $\left(4,3\right)$ such that the map $\overline{N}$ is identically equal to the map F.

Quadratic normalizations of class $\left(4,3\right)$ are thus fully axiomatized.

3.4. Rewriting system associated with quadratic normalization

There is a simple correspondence between quadratic normalizations and quadratic rewriting systems.

Proposition 3.17 ([7, Proposition 3.7]).

(1)	If $\left(S_{+},N\right)$ is a quadratic normalization for a monoid M, then a quadratic, reduced, normalizing and confluent rewriting system $\left(S_{+},R\right)$ presenting M, is obtained by defining R as the set of rewriting rules of the form $$s|t\to \overline{N}\left(s|t\right),$$ for all s and t in $S_{+}$ such that $s|t$ is not N-normal.
(2)	Conversely, if $\left(S_{+},R\right)$ is a quadratic, reduced, normalizing and confluent rewriting system presenting a monoid M, then $\left(S_{+},N\right)$ is a quadratic normalization for M, with $$N\left(w\right)=ŵ,$$ for all w in $S_{+}^{\ast }$.
(3)	These two correspondences are inverse to each other.

Proposition 3.17(1) can be adapted to a case where there is an N-neutral element. In fact, an N-neutral element does not affect termination of the associated rewriting system.

Proposition 3.18 ([7, Proposition 3.9]).

(1)	If $\left(S,N\right)$ is a quadratic normalization mod e for a monoid M, then a reduced, normalizing and confluent rewriting system $\left(S_{+},R\right)$ presenting M, is obtained by defining R as the set of rewriting rules of the form $$s|t\to {\pi }_e\left(\overline{N}\left(s|t\right)\right),$$ for all s and t in $S_{+}$ such that $s|t$ is not N-normal.
(2)	If the rewriting system in Proposition 3.17(1) terminates, then so does the one in $(1)$.

The rewriting system associated with a quadratic normalization in Proposition 3.17 need not be terminating (see [7, Proposition 5.7]). However, it is terminating for quadratic normalizations of class $\left(4,3\right)$.

Proposition 3.19 ([7, Proposition 5.4]). If $\left(A,N\right)$ is a quadratic normalization of class $\left(4,3\right)$, then the associated rewriting system is convergent. More precisely, every rewriting sequence starting from an element of length n has length at most $2^n-n-1$.

3.5. Left-weighted normalization

Before closing this section, let us recall (from [7, Sec. 6.2]) a notion to be used in the next section. A normalization $\left(A,N\right)$ for a monoid M is called left-weighted if, for all $s,t,s^{\prime },t^{\prime }$ in A, the equality $s^{\prime }|t^{\prime }=\overline{N}\left(s|t\right)$ implies the left divisibility $s\preccurlyeq s^{\prime }$ in M.

Proposition 3.20 ([7, Proposition 6.10]). Let M be a left-cancellative monoid M containing no nontrivial invertible element. If $\left(S,N\right)$ is a quadratic normalization mod 1 for M, then the following are equivalent.

•	Every N-normal word $r_1|\cdots |r_n$ has the following property for all $i<n:$  $$forallt\in Sandh\in M,t\preccurlyeq hr{}_i{r}_{i+1}\mathrm{\text{implies}}t\preccurlyeq h{r}_i.$$(3.4)
•	The normalization $\left(S,N\right)$ is of class $\left(4,3\right)$ and is left-weighted.

The normal form $r_1|\cdots |r_n$ having the property (3.4) is called S-greedy (at the ith position). It can be expressed diagrammatically as follows. Commutativity of the diagram

without the dashed arrow implies the existence of a dashed arrow making the square (and thus also the triangle) commute. The arc joining $r_i$ and $r_{i+1}$ signifies that the word $r_i|r_{i+1}$ is greedy. This notion is extensively studied in Garside theory. To an interested reader, we recommend the monograph [6] on the subject.

4. Correspondence between Factorability Structures and Quadratic Normalizations

In this section, a correspondence between factorability structures and quadratic normalizations is established. Section 4.1 gives a characterization of factorable monoids in terms of quadratic normalizations. Section 4.2 shows that, although a quadratic normalization corresponding to a factorable monoid is not of class $\left(4,3\right)$ in general, it is so if a defining condition of local factorability structure is strengthened in a suitable way. Finally, the strengthened definition is shown to imply the additional assumption introduced in [12] (and recalled in Theorem 2.19) in order to reach termination of the associated rewriting system. This results in a characterization of quadratic normalizations of class $\left(4,3\right)$ in terms of factorability structures.

4.1. Characterization of factorable monoids

In this section, a necessary and sufficient condition is given, in terms of quadratic normalizations, for a monoid to be factorable. This is achieved through a syntactic correspondence between a local factorability structure and the restriction of a quadratic normalization map to length-two words. The property (4) of Definition 2.11 (of local factorability structure) is going to be essential in deriving our main result so, for convenience, we are going to express it compactly using the domino rule.

Definition 4.1. Let $\left(A,N\right)$ be a quadratic normalization with the N-neutral element e. The weak domino rule is valid for $\overline{N}$ if the domino rule is valid for $\overline{N}$ whenever none of the elements $r_1^{\prime }$, $r_2^{\prime }$, $s_2$ of the diagram (3.3) equals e.

Now, we can state the main result.

Theorem 4.2. A monoid $\left(M,S\right)$ admits a factorability structure if, and only if, it admits a quadratic normalization $\left(N,S\right)$ mod 1 such that the weak domino rule is valid for $\overline{N}$.

The rest of this section presents a proof. First we verify that a factorability structure yields a quadratic normalization, rather canonically. Assume that $\left(M,S,\eta \right)$ is a factorable monoid. Since $N_{\phi }$ is not length-preserving in general, it does not make a suitable candidate for a normalization map in the sense of Sec. 3.1. To repair this, let us introduce the following notation.

Notation. Let $\left(M,S,\eta \right)$ be a factorable monoid. Denote by $N_{\phi }^{\prime }$ a pointwise length-preserving extended form of $N_{\phi }$, defined as follows:

Lemma 4.3. If $\left(M,S,\eta \right)$ is a factorable monoid, then $\left(S,N_{\phi }^{\prime }\right)$ is a quadratic normalization mod 1 for M.

Proof. Recalling the relation between factorability structure $\eta$ and local factorability structure $\phi$, expressed by Theorem 2.13, let us check that $\left(S,N_{\phi }^{\prime }\right)$ has, mutatis mutandis, the three properties of Definition 3.1 (of normalization). Properties (1) and (2) are satisfied by construction. Indeed, $N_{\phi }^{\prime }$ is length-preserving and $N_{\phi }^{\prime }\left(s\right)=s$ for every s in S, by definition. Note that Lemma 2.7 implies the property (3). Namely, since the normal form associated with the factorability structure is everywhere stable, then so is $N_{\phi }$, due to Theorem 2.13 (4). This property is then transferred to $N_{\phi }^{\prime }$ as well, by construction. In particular, the equality $N_{\phi }^{\prime }\left(u|v|w\right)=N_{\phi }^{\prime }\left(u|N_{\phi }^{\prime }\left(v\right)|w\right)$ holds for all S-words u, v, w.

Let us verify that the obtained normalization $\left(S,N_{\phi }^{\prime }\right)$ is quadratic. The property (3) of Definition 2.9 (of the normalization map $N_{\phi }$) implies the property (2) of Definition (3.7) (of quadratic normalization) and, consequently, also the right-to-left implication of the property (1) of Definition 3.7. The other direction of the property (1) of Definition 3.7 follows from Lemma 2.7.

Finally, Lemma 2.17, together with Remark 2.18, provides a presentation showing that $\left(S,N_{\phi }^{\prime }\right)$ is a normalization mod 1 for M. □

We say that $\left(S,N_{\phi }^{\prime }\right)$ is the quadratic normalization corresponding to the factorability structure $\eta$.

Remark 4.4. A note on formality is in order before we continue. As announced by Remark 1.1, we have tried to respect the two original conventions: of taking a generating set S to be a subset of a factorable monoid; and of distinguishing S from its image under an evaluation map arising from a normalization. Now, however, that we consider those quadratic normalizations $\left(S,N\right)$ that correspond to factorability structures, we interchangeably write e and 1 for an N-neutral S-letter, depending on whether we take the viewpoint of normalization or factorability.

Remark 4.5. Note that, by construction, the restriction $\overline{N_{\phi }^{\prime }}$ of $N_{\phi }^{\prime }$ to length-two words is identically equal to the local factorability structure of $\left(M,S,\eta \right)$. This fact will be often used implicitly.

Having obtained a quadratic normalization, we want to determine its class.

Lemma 4.6. If $\left(M,S,\eta \right)$ is a factorable monoid, then the quadratic normalization corresponding to $\eta$ is of class $\left(5,4\right)$.

Proof. Denote by $\phi$ the local factorability structure corresponding to $\eta$ in the sense of Theorem 2.13. If $\left(r,s,t\right)$ is an S-word, then Lemma 2.12 says that the word $N_{\phi }^{\prime }\left(r,s,t\right)$ equals the word ${\phi }_{2121}\left(r,s,t\right)$. We conclude that quadratic normalization $\left(S,N_{\phi }^{\prime }\right)$ is of right-class 4. Then Lemma 3.12 grants the left-class 5. □

The following example demonstrates that the minimal right-class of a quadratic normalization corresponding to a factorability structure is not smaller than 4, in general.

Example 4.7 ([11, Example 2.1.13]). Consider the monoid $\left(\mathbb{Z},+\right)$ with respect to the generating set $\left\{-1,+1\right\}$. The factorization map is defined by

where $\text{sgn}:\mathbb{Z}\to \left\{-1,0,+1\right\}$ denotes the sign function. One can check that this is a factorable monoid.^c Note that ${\phi }_{212}\left(1,-1,-1\right)$ equals $\left(0,-1,0\right)$, whereas ${\phi }_{2121}\left(1,-1,-1\right)$ equals $\left(-1,0,0\right)$. Therefore, the minimal right-class of the corresponding quadratic normalization is at least 4; then it is exactly 4, by Lemma 4.6.

The next example, adapted from [12, Appendix, Proposition 7], shows that the minimal left-class of a quadratic normalization corresponding to a factorability structure is not smaller than 5 in general.

Example 4.8. Let $S_{+}$ be the following set:

Define a map $\phi :S^2\to S^2$ as follows: and $\left(s,t\right)\stackrel{\phi }{\mapsto }\left(s,t\right)$ if $\left(s,t\right)$ is not listed above.

By [12, Appendix, Proposition 7], the map $\phi$ is a local factorability structure. Let us determine the class of the corresponding quadratic normalization.

Computing ${\phi }_{1212}\left(c_1,b_1,a_1\right)$ gives

whereas Hence, the minimal left-class is at least 5.

The above computation also gives ${\phi }_{212}\left(c_1,b_1,a_1\right)=\left(c_2,e_2,1\right)$, whereas

Thus, the minimal right-class is at least 4, as expected according to Lemma 3.12.

The previous two examples witness that the estimate of class in Lemma 4.6 is as good as one can hope for. On the other hand, observe that not every quadratic normalization of class $\left(5,4\right)$ is corresponding to a factorability structure, as demonstrated by the following example, adapted from [7, Example 3.15].

Example 4.9. Let $A=\left\{a,b_1,b_2,b_3,b_4,b_5\right\}$, and let R consist of the rules $a{b}_i\to a{b}_{i+1}$ for $i<5$ even, and $b_{i}a\to b_{i+1}a$ for $i<5$ odd. The rewriting system $\left(A,R\right)$ is clearly quadratic and reduced. Note that it is also terminating because each rewriting rule only increases the index of a letter b in a word. Furthermore, it is confluent, as illustrated by the following diagram (it suffices to investigate the so-called critical pairs, see e.g. [14, Sec. 1]):

Denote by $\left(A,N\right)$ the quadratic normalization associated with $\left(A,R\right)$ by Proposition 3.17. Let us determine the minimal class of $\left(A,N\right)$. If a length-three word does not begin and end with the letter a, then it is either N-normal or it becomes N-normal in a single step. On the other hand, normalizing $a|b_1|a$ takes four steps starting from the right (or five steps starting from the left): The minimal class of $\left(A,N\right)$ is thus $\left(5,4\right)$.

However, the normalization $\left(A,N\right)$ is not corresponding to any factorability structure. To see this, observe that

whereas Therefore, $\overline{N}$ fails to admit the property (4) of Definition 2.11 (of local factorability structure). We conclude (by Remark 4.5) that $\overline{N}$ does not correspond to a factorability structure.

A natural question to ask is: among quadratic normalizations of class $\left(5,4\right)$, what distinguishes those that correspond to a factorability structure? Example 4.9 suggests a candidate (by what it is lacking): simply impose the weak domino rule upon quadratic normalization of class $\left(5,4\right)$. Before testing sufficiency of these two properties combined, let us notice that they are not independent from each other.

Lemma 4.10. Let $\left(S,N\right)$ be a quadratic normalization having an N-neutral element e. If the weak domino rule is valid for $\overline{N}$, then $\left(S,N\right)$ is of class $\left(5,4\right)$.

Proof. Let $\left(r,s,t\right)$ be an S-word. If

then so it takes at most three steps starting with ${\overline{N}}_2$ to normalize $\left(r,s,t\right)$.

Otherwise, ${\overline{N}}_{212}\left(r,s,t\right)$ contains e by the weak domino rule. Denote $\left(a,b,c\right):={\overline{N}}_{212}\left(r,s,t\right).$

Case 1.	If e occurs exactly once in the triple $\left(a,b,c\right)$, then it cannot be at the leftmost position in ${\overline{N}}_{21}\left(r,s,t\right)$. So, it has to be at the rightmost position in ${\overline{N}}_{212}\left(r,s,t\right)$. In other words, c has to be equal to e. Consequently $$N\left(a,b,c\right)={\overline{N}}_1\left(a,b,c\right)={\overline{N}}_{2121}\left(r,s,t\right).$$(4.1)
Case 2.	If e occurs exactly twice in the triple $\left(a,b,c\right)$, then either $a\ne e$ or $b\ne e$. In each case, the equalities (4.1) hold.
Case 3.	If e occurs three times in the triple $\left(a,b,c\right)$, then clearly the equalities (4.1) hold.

Therefore, $\left(S,N\right)$ is of right-class 4, hence of class $\left(5,4\right)$, by Lemma 3.12. □

The following proposition shows that adding the weak domino rule to the properties of quadratic normalization (and thus granting the class $\left(5,4\right)$ by Lemma 4.10) suffices to yield factorability.

Proposition 4.11. Let $\left(S,N\right)$ be a quadratic normalization mod e for a monoid M. If the weak domino rule is valid for $\overline{N}$, then $\overline{N}$ is a local factorability structure.

Proof. The following list shows that the map $\overline{N}$ has, mutatis mutandis, all the properties of Definition 2.11 (of local factorability structure).

(1)	By Proposition 3.9(3), M admits the presentation $$〈S_{+}|\left\{s|t={\pi }_e\left(\overline{N}\left(s|t\right)\right)|s,t\in S_{+}\right\}〉.$$ Although this presentation is not the same as the one in Definition 2.11, the two are equivalent (see Remark 2.18).
(2)	By the property (3) of Definition 3.1 (of normalization), $\overline{N}$ is idempotent.
(3)	By Proposition 3.9(2), the equality $\overline{N}\left(e|s\right)=s|e$ holds for all s in $S_{+}$.
(4)	This property is explicitly assumed.
(5)	By Lemma 4.10, the normalization $\left(S,N\right)$ is of class $\left(5,4\right)$. By the definition of right-class 4, the N-normal word $N\left(r,s,t\right)$ equals ${\overline{N}}_{2121}\left(r,s,t\right)$, which further equals ${\overline{N}}_{12121}\left(r,s,t\right)$ by the definition of left-class 5. Hence, $N\left(r,s,t\right)$ equals $\left(N\circ {\overline{N}}_1\right)\left(r,s,t\right)$ for all $\left(r,s,t\right)$ in $S_{+}^3$.

 □

We have, thus, proved one direction of Theorem 4.2. The other one follows from Remark 4.5, as the restriction to length-two words of a quadratic normalization corresponding to a factorability structure has all the properties of the corresponding local factorability structure and, in particular, the weak domino rule is valid. Thereby, we have completed the proof of Theorem 4.2.

The following corollary is an immediate consequence.

Corollary 4.12.

(1)	Associating a factorability structure to a quadratic normalization such that the weak domino rule is valid, and associating a quadratic normalization to a factorability structure (the weak domino rule being valid automatically), as given above, are inverse transformations.
(2)	The normal forms associated with a factorability structure and the corresponding quadratic normalization are the same.
(3)	The rewriting systems associated with a factorability structure and the corresponding quadratic normalization are equivalent, the only difference being dummy letters to preserve length in the latter.

4.2. Factorability in relation to quadratic normalization of class $\left(4,3\right)$

Having established a general correspondence between a factorability structure and a quadratic normalization in the previous section, we are now going to further elaborate these links in the case when the quadratic normalization involved is of class $\left(4,3\right)$. First we emphasize a particular, yet important, consequence of Proposition 4.11.

Corollary 4.13. If $\left(S,N\right)$ is a quadratic normalization of class $\left(4,3\right)$ mod 1 for a monoid M, then $\overline{N}$ is a local factorability structure.

Although the converse does not hold in general, it does so in the case of graded monoids (as defined in Sec. 3.1).

Lemma 4.14. Let $\left(M,S,\eta \right)$ be a factorable monoid. If $\left(M,S_{+}\right)$ is graded, then $\left(S_{+},N_{\phi }\right)$ is a quadratic normalization of class $\left(4,3\right)$.

Proof. In addition to the conclusion of Lemma 4.3 that $\left(S_{+},N_{\phi }\right)$ is a quadratic normalization, let us show how the existence of grading ensures the right-class 3. By the property (4) of Definition 2.11 (of local factorability structure), for every $\left(r,s,t\right)$ in $S_{+}^3$, the equality

holds or ${\left(N_{\phi }\right)}_{212}\left(r,s,t\right)$ contains 1 but, since M is graded, the latter case cannot occur. Therefore, $\left(S_{+},N_{\phi }\right)$ is of right-class 3. Then the property of being of left-class 4 follows from Lemma 3.12. □

Let us pin down those defining properties of quadratic normalization of class $\left(4,3\right)$ mod 1 for M that do not necessarily arise from a factorability structure on M. In other words, we are looking for a (not too restrictive) property that would complement a factorability structure to a quadratic normalization of class $\left(4,3\right)$. The property (4) of Definition 2.11 (of local factorability structure) grants the equality

only for $S_{+}$-words $\left(r,s,t\right)$ such that ${\phi }_{212}\left(r,s,t\right)$ contains no 1. On the other hand, the right-class 3 (i.e. the domino rule) requires the equality (4.2) to hold for every S-word $\left(r,s,t\right)$, regardless of whether ${\phi }_{212}\left(r,s,t\right)$ contains 1 or not. Therefore, in order for a factorability structure to induce a quadratic normalization of class $\left(4,3\right)$, it suffices to strengthen the condition (4) of Definition 2.11, as follows.

Proposition 4.15. Let $\left(M,S,\eta \right)$ be a factorable monoid. If the equality (4.2) holds for each $S_{+}$-word $\left(r,s,t\right)$ such that ${\phi }_{212}\left(r,s,t\right)$ contains $1$, then $\left(S,N_{\phi }^{\prime }\right)$ is a quadratic normalization of class $\left(4,3\right)$ mod 1 for M.

Proof. Lemma 4.3 says that $\left(S,N_{\phi }^{\prime }\right)$ is a quadratic normalization mod 1 for M.

To obtain the class $\left(4,3\right)$, what remains to be shown is that the equality (4.2) holds for all $\left(r,s,t\right)$ in ${\left(S\right)}^3\backslash S_{+}^3$. If t equals 1, then ${\phi }_1\left(r,s,t\right)$ equals $\phi \left(r,s\right)|1$, which is everywhere stable. If s equals 1, then ${\phi }_{21}\left(r,s,t\right)$ equals $\phi \left(r,t\right)|1$, which is everywhere stable. If r equals 1, then ${\phi }_{121}\left(r,s,t\right)$ equals ${\phi }_{212}\left(r,s,t\right)$ which equals $\phi \left(s,t\right)|1$, which is, again, everywhere stable. □

We have shown that a quadratic normalization of class $\left(4,3\right)$ yields a factorability structure (Corollary 4.13), but not vice versa (Examples 4.7 and 4.8 or Theorem 4.2). However, a factorability structure does yield a quadratic normalization of class $\left(4,3\right)$ under a stronger condition on local factorability (Proposition 4.15). Therefore, under the same condition, the rewriting system associated with a factorable monoid is terminating, by Proposition 3.19 and Corollary 4.12(3).

From another point of view, recall that Theorem 2.19 ensures termination of the rewriting system associated with a factorable monoid, under an additional assumption on the factorization map. It is then natural to ask what is the relation between the additional condition of Proposition 4.15 and the additional assumption of Theorem 2.19, which are both known to ensure termination of the associated rewriting system.

In the rest of this section, we investigate the relation between these two optional properties of a factorable monoid $\left(M,S,\eta \right)$: for each $S_{+}$-word $\left(r,s,t\right)$ such that ${\phi }_{212}\left(r,s,t\right)$ contains 1, Condition

and, for all s in $S_{+}$ and f in M, Assumption

Remark 4.16. Note that Assumption (4.4) is trivially valid in the case where f lies in S or in the case where $\left(s,f\right)$ is stable.

It has already been known that Assumption (4.4) implies Condition (4.3), as follows.

Lemma 4.17 ([12, Lemma 7.1]). Let $\left(M,S,\eta \right)$ be a factorable monoid. If Assumption (4.4) is valid for all s in $S_{+}$ and f in M, then the maps ${\left(\eta \mu \right)}_{212}$ and ${\left(\eta \mu \right)}_{2121}$ coincide on $M^3$.

Corollary 4.18. Let $\left(M,S,\eta \right)$ be a factorable monoid. If Assumption (4.4) is valid for all s in $S_{+}$ and f in M, then Condition (4.3) is satisfied for all $\left(r,s,t\right)$ in $S_{+}^3$.

For the reader’s convenience, we adapt the proof of Lemma 4.17 here, to prove Corollary 4.18.

Proof. If Assumption (4.4) is valid for all s in $S_{+}$ and f in M, then the maps ${\eta }_1{\mu }_1$ and ${\mu }_2{\eta }_1{\mu }_1{\eta }_2$ coincide on $S_{+}\times M$. Composing each of these two maps with ${\mu }_2$ and then composing ${\eta }_2$ with the obtained composite map, we see that the maps ${\eta }_2{\eta }_1{\mu }_1{\mu }_2$ and ${\eta }_2{\mu }_2{\eta }_1{\mu }_1{\eta }_2{\mu }_2$ coincide on $S_{+}\times M^2$. Note that the map ${\eta }_2{\eta }_1$ produces the $\eta$-normal form by definition, and that the restriction of the map ${\eta }_2{\mu }_2{\eta }_1{\mu }_1{\eta }_2{\mu }_2$ to $S_{+}^3$ coincides with the map ${\phi }_2{\phi }_1{\phi }_2$. Therefore, every image under ${\phi }_2{\phi }_1{\phi }_2$ is everywhere stable by Lemma 2.7. Thus, Condition (4.3) is satisfied for all $\left(r,s,t\right)$ in $S_{+}^3$. □

In the opposite direction, a partial result has already been known. Namely, Condition (4.3) implies Assumption (4.4) under certain, quite restrictive, additional requirements imposed on both the monoid and the normalization. The next lemma is a straightforward adaptation of [6, Proposition IV1.49]; it is also hinted in the proof of [15, Corollary 7.4.5].

Remark 4.19. Relying on Theorem 4.2 and Corollary 4.12(2) in particular, we are going to abuse terminology by saying “the normal form” without specifying whether it arises from factorability or normalization.

Lemma 4.20. Let M be a left-cancellative monoid containing no nontrivial invertible element. If $\left(S,N\right)$ is a left-weighted quadratic normalization of class $\left(4,3\right)$ mod 1 for M, then Assumption (4.4) is valid for all s in $S_{+}$ and f in M.

Proof. We need to show that the equalities ${\left(sf\right)}^{\prime }={\left(s{f}^{\prime }\right)}^{\prime }$ and $\overline{sf}=\overline{s{f}^{\prime }}\cdot \overline{f}$ hold for all s in $S_{+}$ and f in M.

By the definition of factorability structure, we have ${\left(s{f}^{\prime }\right)}^{\prime }\preccurlyeq s{f}^{\prime }$, and $f^{\prime }\preccurlyeq f$ hence also $s{f}^{\prime }\preccurlyeq sf$. The transitivity gives ${\left(s{f}^{\prime }\right)}^{\prime }\preccurlyeq sf$, and the assumption that $\left(S,N\right)$ is left-weighted then yields ${\left(s{f}^{\prime }\right)}^{\prime }\preccurlyeq {\left(sf\right)}^{\prime }$.

By Corollary 4.12(2), the normal form of f has the form $f^{\prime }|r_2|\cdots |r_n$. Hence, ${\left(sf\right)}^{\prime }\preccurlyeq sf=s{f}^{\prime }{r}_2\cdots r_n$. Since ${\left(sf\right)}^{\prime }$ lies in S and $f^{\prime }|r_2|\cdots |r_n$ is normal, we obtain ${\left(sf\right)}^{\prime }\preccurlyeq s{f}^{\prime }$ by the property (3.4) in Proposition 3.20. That yields ${\left(sf\right)}^{\prime }\preccurlyeq {\left(s{f}^{\prime }\right)}^{\prime }$ due to the assumption that $\left(S,N\right)$ is left-weighted.

Since M is a left-cancellative monoid containing no nontrivial invertible element, we conclude that ${\left(sf\right)}^{\prime }={\left(s{f}^{\prime }\right)}^{\prime }$. Then $\overline{sf}=\overline{s{f}^{\prime }}\cdot \overline{f}$ follows from the left cancellation property. □

We want to find out whether Condition (4.3) implies Assumption (4.4) in general, i.e. without all the additional requirements of the previous lemma, or is the latter strictly stronger than the former. Let us begin by considering length-two words.

Lemma 4.21. Let $\left(M,S,\eta \right)$ be a factorable monoid. If Condition (4.3) is satisfied for each $S_{+}$-word $\left(r,s,t\right)$ such that ${\phi }_{212}\left(r,s,t\right)$ contains $1$, then Assumption (4.4) is valid for all s in $S_{+}$ and length-two f in M.

Proof. The idea is to equate two different expressions of the normal form of $sf$. Fix arbitrary s in $S_{+}$ and a length-two element f of M.

First compute the $\eta$-normal form of $sf$, by definition,

Next we compute the same normal form in a different manner. Since the length of f equals 2, we know that $\overline{f}$ lies in $S_{+}$. Hence, $\left(s,f^{\prime },\overline{f}\right)$ lies in $S_{+}^3$. So we have another length-three $S_{+}$-word evaluating to $sf$. By the property (4) of Definition 2.11 (of local factorability structure) and Condition (4.3), the word ${\left(\eta \mu \right)}_{212}\left(s,f^{\prime },\overline{f}\right)$ is everywhere stable, hence also normal by Lemma 4.3 and the property (1) of Definition 3.7 (of quadratic normalization). Therefore, ${\left(\eta \mu \right)}_{212}\left(s,f^{\prime },\overline{f}\right)$ is the normal form of the evaluation of $\left(s,f^{\prime },\overline{f}\right)$, i.e. of $sf$. Since computing ${\left(\eta \mu \right)}_{212}\left(s,f^{\prime },\overline{f}\right)$ depends on whether any 1 occurs in the process, we consider the following cases:

Case 1.

If $s{f}^{\prime }$ is not an element of S, then $$\begin{array}{ccc}\hfill \left(s,f^{\prime },\overline{f}\right)& \hfill \stackrel{{\left(\eta \mu \right)}_2}{\mapsto }\hfill & \left(s,f^{\prime },\overline{f}\right)\stackrel{{\left(\eta \mu \right)}_1}{\mapsto }\left({\left(s{f}^{\prime }\right)}^{\prime },\overline{s{f}^{\prime }},\overline{f}\right)\hfill \\ \hfill & \hfill \stackrel{{\left(\eta \mu \right)}_2}{\mapsto }\hfill & \left({\left(s{f}^{\prime }\right)}^{\prime },{\left(\overline{s{f}^{\prime }}\cdot \overline{f}\right)}^{\prime },\overline{\overline{s{f}^{\prime }}\cdot \overline{f}}\right).\hfill \end{array}$$ Comparing the result to (4.5) yields Assumption (4.4), by Corollary 4.12(2). Indeed, equating the first components of the obtained expressions gives ${\left(sf\right)}^{\prime }={\left(s{f}^{\prime }\right)}^{\prime }$. Equating the second and the third components gives $\overline{sf}=\overline{s{f}^{\prime }}\cdot \overline{f}$.

Case 2.

If $s{f}^{\prime }$ is an element of $S_{+}$, then $$\left(s,f^{\prime },\overline{f}\right)\stackrel{{\left(\eta \mu \right)}_2}{\mapsto }\left(s,f^{\prime },\overline{f}\right)\stackrel{{\left(\eta \mu \right)}_1}{\mapsto }\left({\left(s{f}^{\prime }\right)}^{\prime },1,\overline{f}\right)\stackrel{{\left(\eta \mu \right)}_2}{\mapsto }\left({\left(s{f}^{\prime }\right)}^{\prime },\overline{f},1\right).$$(4.6) Again, equating the first components of the result and (4.5) gives ${\left(sf\right)}^{\prime }={\left(s{f}^{\prime }\right)}^{\prime }$. Equating the second and the third components now gives $\overline{sf}=\overline{f}$, but note that, in the present case, this equality is equivalent to $\overline{sf}=\overline{s{f}^{\prime }}\cdot \overline{f}$.

Finally, observe that the case $s{f}^{\prime }=1$ cannot occur. Namely, if $s{f}^{\prime }$ were equal to 1, then applying ${\left(\eta \mu \right)}_1$ after (4.6) would yield $\left(\overline{f},1,1\right)$ since $\overline{f}$ is in $S_{+}$, and that would contradict Condition (4.3). □

Lemma 4.21 suggests itself as an induction base case, which we are going to achieve in Proposition 4.22. First we introduce some notation, in order to simplify exposition.

Notation. If $\left(r_1,r_2,\dots ,r_n\right)$ is the normal form of f in M, then the product $r_1{r}_2\cdots r_{n-1}$ in M is denoted by $\underline{f}$.

Proposition 4.22. Let $\left(M,S,\eta \right)$ be a factorable monoid. If Condition (4.3) is satisfied for each $S_{+}$-word $\left(r,s,t\right)$ such that ${\phi }_{212}\left(r,s,t\right)$ contains 1, then Assumption (4.4) is valid for all s in $S_{+}$ and f in M.

Proof. By Proposition 4.15, the quadratic normalization corresponding to the given factorability structure is of class $\left(4,3\right)$. Then Remark 3.15 (on Lemma 3.14) implies the equality ${\left(sf\right)}^{\prime }={\left(s{f}^{\prime }\right)}^{\prime }$ for all s in $S_{+}$ and f in M.

We need to show that the equality $\overline{sf}=\overline{s{f}^{\prime }}\cdot \overline{f}$ also holds for all s in $S_{+}$ and f in M. We are going to achieve this using induction on the length of f. Let $P\left(n\right)$ be the statement: the equality $\overline{sf}=\overline{s{f}^{\prime }}\cdot \overline{f}$ holds for all s in $S_{+}$ and f of length n in M. The statement $P\left(2\right)$ (respectively, $P\left(1\right)$) holds by Lemma 4.21 (respectively, trivially).

Let n be an integer greater than 2, and suppose that the statement $P\left(n-1\right)$ holds. Fix an arbitrary s in $S_{+}$ and f of length n in M. Since the length of $\underline{f}$ equals $n-1$, the equality $\overline{s\underline{f}}=\overline{s{f}^{\prime }}\cdot \overline{\underline{f}}$ holds by the inductive hypothesis.^d Note that notation $\overline{\underline{f}}$ is not ambiguous since $\overline{\left(\underline{f}\right)}$ equals $\underline{\left(\overline{f}\right)}$ due to the fact that the normal form is everywhere stable. Denote the normal form of f by $\left(r_1,r_2,\dots ,r_n\right)$. Multiplying the equality $\overline{s\underline{f}}=\overline{s{f}^{\prime }}\cdot \overline{\underline{f}}$ by $r_n$ on the right yields

Hence, it suffices to show that the equality $\overline{s\underline{f}}\cdot r_n=\overline{sf}$ holds.

Let us compute the normal forms of $\overline{s\underline{f}}$ and $\overline{sf}$ using Lemma 3.14. Denoting $s_1:=s$ and $t_i|s_i:=\overline{N}\left(s_{i-1}|r_i\right)$ for $i\in \left\{2,\dots ,n-1\right\}$, we obtain

and as displayed by the diagram with arcs having the same meaning as in the diagram (3.3). Therefore, $\overline{s\underline{f}}=t_2{t}_3\cdots t_{n-1}{s}_{n-1}$. Multiplying by $r_n$ on the right yields which, together with the equality (4.7), implies $P\left(n\right)$. □

The results of this section enable the following characterization.

Proposition 4.23. Let $\left(M,S,\eta \right)$ be a factorable monoid. Then the following properties are equivalent:

(1)	For all s in $S_{+}$ and f in M, the equalities ${\left(sf\right)}^{\prime }={\left(s{f}^{\prime }\right)}^{\prime }$and $\overline{s}f=\overline{s{f}^{\prime }}\cdot \overline{f}$ hold.
(2)	For all $\left(f,g,h\right)$ in $M^3$, the equality $${\left(\eta \mu \right)}_{2121}\left(f,g,h\right)={\left(\eta \mu \right)}_{212}\left(f,g,h\right)$$ holds.
(3)	For each $S_{+}$-word $\left(r,s,t\right)$ such that ${\phi }_{212}\left(r,s,t\right)$ contains 1, the equality $${\left(\eta \mu \right)}_{2121}\left(r,s,t\right)={\left(\eta \mu \right)}_{212}\left(r,s,t\right)$$ holds.
(4)	The quadratic normalization $\left(S,N_{\phi }^{\prime }\right)$ mod 1 for M is of class $\left(4,3\right)$.

Proof. It has already been known (Lemma 4.17) that (1) implies (2), which, in turn, clearly implies (3). The properties (3) and (4) are equivalent by the definitions of the notions concerned. Finally, Proposition 4.22 says that (3) implies (1). □

Let us observe that Proposition 4.23 can also be read another way, thanks to Theorem 4.2, as a characterization of monoids admitting a quadratic normalization of class $\left(4,3\right)$ among factorable monoids.

Corollary 4.24. A monoid admits a quadratic normalization of class $\left(4,3\right)$ if, and only if, it admits a factorability structure having any of the properties 1–3 of Proposition 4.23.

Acknowledgments

I warmly thank Viktoriya Ozornova for supervising this work and for numerous remarks that highly improved the quality of this text. I am also grateful to the anonymous referee for meaningful suggestions. This program has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 754362.

Notes

^a In the broader context of categories, words are generalized to paths of composable morphisms.

^b That is a set equipped with a distinguished element, called basepoint, enjoying a special treatment in the given context.

^c Technically speaking, this is a factorable group by [16, Example 3.2.2], and a weakly factorable monoid. Hence, it is also a factorable monoid by [11, Proposition 2.1.28].

^d Statement $P\left(1\right)$ could not serve as the base case because $\overline{\underline{f}}$ in the inductive hypothesis would not be defined, which is why we needed Lemma 4.21.