Correspondence between factorability and normalisation in monoids

Basic Information

• Paper ID: 2206.01672
• Title: Correspondence between factorability and normalisation in monoids
• Author: Alen Đurić
• Classification: math.GR (Group Theory)
• Publication Date: December 30, 2024 (arXiv v3)
• Paper Link: https://arxiv.org/abs/2206.01672

Abstract

This paper establishes the relationship between two concepts concerning monoids: the factorability structure introduced for simplifying bar complexes, and quadratic normalisation introduced to generalize quadratic rewriting systems and normalisation arising from Garside families. The paper characterizes factorable monoids within the axiomatic framework of quadratic normalisation. Furthermore, it characterizes quadratic normalisation of class (4,3) through factorability structures and conditions ensuring termination of the associated rewriting systems.

Research Background and Motivation

Problem Background

This research involves two seemingly independent but actually related mathematical concepts:

1. Factorability Structures: Extended by Wang, Hess and others from definitions by Bödigheimer and Visy on groups, originally motivated by structures discovered in abstract symmetric groups. These structures ensure the existence of normal forms with remarkable properties, particularly allowing the reduction of bar complexes to complexes with fewer cells.
2. Quadratic Normalisation: Introduced by Dehornoy and Guiraud, influenced by Krammer, generalizing two classes of celebrated normalisations within the same axiomatic framework: normalisations from quadratic rewriting systems and those from Garside families.

Research Motivation

1. Unifying different theoretical frameworks: Both concepts originate from different sources but both involve normal form theory for monoids
2. Answering explicitly posed questions: References 6 and 7 explicitly mention the need to determine the relationship between these two approaches
3. Establishing theoretical bridges: Providing pathways for importing homological results derived from factorability structures into the quadratic normalisation framework

Limitations of Existing Approaches

• Rewriting systems related to factorability structures do not necessarily terminate
• Quadratic normalisation theory lacks direct connection to topological applications
• The two theoretical frameworks lack unified understanding

Core Contributions

1. Establishing bidirectional correspondence: Establishes bidirectional mappings between factorability structures and quadratic normalisations that are mutually inverse (in technical details)
2. Characterizing factorable monoids: Completely characterizes factorable monoids within the axiomatic framework of quadratic normalisation
3. Category analysis: Proves that quadratic normalisations corresponding to factorability structures are always of class (5,4), and generally cannot be smaller
4. Termination conditions: Provides necessary and sufficient conditions for quadratic normalisations to correspond to factorability structures and characterizes quadratic normalisations of class (4,3)
5. Equivalence results: Proves that class (4,3) is equivalent to factorability plus termination

Methodology Details

Task Definition

The core task of this paper is to establish precise correspondence between two algebraic structures:

• Input: Monoid M and its generating set S
• Objective: Establish a bijection between factorability structures η: M → M² and quadratic normalisations (S,N)
• Constraints: Preserve compatibility of associated rewriting systems

Theoretical Framework

Factorability Structures

For a monoid M and generating subset S, a factorability structure is a mapping η = (η', η̄): M → M² satisfying:

• η'(f) ∈ S₊ is a left factor of f, η̄(f) is the right complement
• The pair (η'(f), η̄(f)) is geodesic
• Satisfies complex compatibility conditions

Quadratic Normalisation

A normalisation (A,N) is a length-preserving mapping N: A* → A* satisfying:

• Restriction to A is the identity mapping
• Locality property: N(u|v|w) = N(u|N(v)|w)
• Quadratic property: Completely determined by properties of length 2 factors

Technical Innovations

Weak Domino Rule

Definition 4.1.1: For a quadratic normalisation (A,N) with N-neutral element e, the domino rule is valid when elements r'₁, r'₂, s₂ in diagram (3.3) are all not equal to e.

Main Theorem

Theorem 4.1.2: A monoid (M,S) admits a factorability structure if and only if it admits a quadratic normalisation (N,S) mod 1 such that the weak domino rule holds for N.

Correspondence Construction

1. From factorability to normalisation:
   • Given factorable monoid (M,S,η)
   • Construct N'φ(w) = Nφ(w)|1^m, where m = |w| - |Nφ(w)|
   • Prove (S,N'φ) is a quadratic normalisation mod 1
2. From normalisation to factorability:
   • Given quadratic normalisation (S,N) satisfying weak domino rule
   • Prove restriction of N is a local factorability structure
   • Construct corresponding factorability structure via Theorem 2.2.6

Category Analysis

Category Definition

The class (m,n) of quadratic normalisation (A,N) measures complexity of normalisation on length 3 words:

• Left class m: N(w) = N₁₂m holds for all length 3 words w
• Right class n: N(w) = N₂₁n holds for all length 3 words w

Key Results

Lemma 4.1.6: Quadratic normalisations corresponding to factorable monoids are of class (5,4).

Proposition 4.2.3: Under strengthened conditions, factorability structures induce quadratic normalisations of class (4,3).

Experimental Setup

Theoretical Verification Methods

As pure mathematical theoretical research, this paper employs rigorous mathematical proof methods:

1. Constructive proofs: Establishing correspondence through explicit construction
2. Counterexample analysis: Providing concrete examples illustrating boundary cases
3. Inductive arguments: Using mathematical induction to prove general results

Key Examples

Example 4.1.7 (Integer Group)

• Setup: Monoid (ℤ,+), generating set {-1,+1}
• Factorability mapping: g ↦ (sgn(g), g - sgn(g))
• Result: Corresponding quadratic normalisation is exactly class (5,4), proving the boundary is tight

Example 4.1.8 (Complex Construction)

• Setup: Complex monoid with 26 generators
• Purpose: Proving left class is at least 5
• Method: Through explicit computation φ₁₂₁₂₁(c₁,b₁,a₁) ≠ φ₁₂₁₂(c₁,b₁,a₁)

Example 4.1.9 (Counterexample)

• Setup: Rewriting system (A,R), A = {a,b₁,...,b₅}
• Rules: abᵢ → abᵢ₊₁ (i even), bᵢa → bᵢ₊₁a (i odd)
• Conclusion: Although class (5,4), does not correspond to any factorability structure

Experimental Results

Main Theoretical Results

Completeness of Correspondence

Corollary 4.1.12:

1. Transformations in both directions are mutually inverse
2. Associated normal forms are identical
3. Associated rewriting systems are equivalent (differing only in length preservation)

Category Characterization

Proposition 4.2.11: For factorable monoid (M,S,η), the following are equivalent:

1. For all s ∈ S₊ and f ∈ M: (sf)' = (sf')' and sf̄ = sf' · f̄
2. For all (f,g,h) ∈ M³: (ημ)₂₁₂₁(f,g,h) = (ημ)₂₁₂(f,g,h)
3. Strengthened local conditions
4. Associated quadratic normalisation is class (4,3)

Termination Results

Corollary 4.2.12: A monoid admits class (4,3) quadratic normalisation if and only if it admits a factorability structure satisfying any one property in Proposition 4.2.11.

Boundary Analysis

• (5,4) is tight: Examples 4.1.7 and 4.1.8 prove improvement to smaller classes is impossible
• Weak domino rule is necessary: Example 4.1.9 proves class conditions alone are insufficient
• (4,3) is equivalent to factorability plus termination: Establishes complete characterization

Related Work

Factorability Structure Theory

• Bödigheimer & Visy (2010): Introduced factorability concept on groups
• Wang (2011) & Hess (2012): Extended to monoids and categories
• Ozornova (2013): Reformulation via discrete Morse theory

Quadratic Normalisation Theory

• Dehornoy & Guirard (2016): Established axiomatic framework for quadratic normalisation
• Krammer (2013): Asymmetric generalization for Artin monoids
• Garside theory: Systematic study of greedy normal forms

Rewriting System Theory

• Cohen (1997): String rewriting and monoid homology
• Brown (1992): Geometry of rewriting systems
• Lafont & Prouté (1991): Church-Rosser property

Conclusions and Discussion

Main Conclusions

1. Complete correspondence: Establishes complete bijection between factorability structures and quadratic normalisations satisfying weak domino rule
2. Category characterization: Factorable monoids correspond to class (5,4) normalisations; with termination conditions correspond to class (4,3)
3. Unified framework: Provides unified understanding of two originally independent theories

Limitations

1. Complexity: Theoretical constructions are quite complex, limiting practical applications
2. Computational complexity: Lacks detailed analysis of algorithmic complexity
3. Generalizability: Primarily addresses monoids; extension to categories requires further work

Future Directions

1. Homological applications: Importing homological results from factorability structures into quadratic normalisation framework
2. Higher class generalization: Studying properties of higher class quadratic normalisations
3. Algorithm implementation: Developing efficient algorithms implementing these theoretical results

In-Depth Evaluation

Strengths

1. Theoretical depth: Establishes profound connections between two important algebraic structures
2. Technical rigor: Complete and technically rigorous proofs
3. Unified perspective: Provides unified framework for theories from different sources
4. Completeness: Not only establishes correspondence but also characterizes boundary cases

Weaknesses

1. Readability: Complex technical details make it difficult for non-specialist readers
2. Practical utility: Practical application value of theoretical results requires further development
3. Computational aspects: Lacks detailed analysis of algorithmic complexity

Impact

1. Theoretical contribution: Provides important theoretical tools for algebraic combinatorics
2. Connecting role: Connects different fields of topology, algebra, and computer science
3. Foundation for future research: Establishes foundation for further theoretical development

Applicable Scenarios

• Homological computations in algebraic topology
• Theoretical analysis of rewriting systems
• Generalized applications of Garside theory
• Study of normal forms in combinatorial group theory

References

This paper cites 25 important references, covering:

• Original papers on factorability structures 1,11,12,15,16,17
• Quadratic normalisation theory 7,13
• Rewriting system theory 3,5,14
• Garside theory 6,9,10
• Related algebraic and topological background 2,4,8