Source-linked AI summary
Irreducibility of Endomorphisms of Finitely Generated Free Semigroups
Paul C. Bell, Eva Foster, Daniel Reidenbach
TL;DR
The paper asks when an endomorphism of a free semigroup admits a nontrivial factorisation, focusing on rank-preserving endomorphisms. It characterizes reducibility through factor bases and examines factor relations, non-unique irreducible factorizations, and incidence matrices.
Problem
The paper asks whether an endomorphism of a free semigroup can be expressed nontrivially as a composition of endomorphisms.
Source: §1 · p. 1Method
The paper studies rank-preserving endomorphisms through factor-basis characterizations, factor relations, irreducible factorizations, and incidence matrices.
Source: §1 · p. 2, §3 · p. 4, §5 · p. 11Results
A rank-preserving endomorphism is reducible exactly when it has a nontrivial factor basis, and its factorisation into irreducible components need not be unique.
Source: §3 · p. 4, §6 · p. 14Takeaways & Limitations
Irreducibility provides a notion of primality in the endomorphism monoid of the free semigroup.
Source: §1 · p. 1Characterizing rank-preserving endomorphisms with unique factorisation remains an open problem identified by the paper.
Source: §6 · p. 14
Abstract
from arXiv · showhide
We introduce and investigate the irreducibility of endomorphisms of finitely generated free semigroups, i.e., we investigate when an endomorphism $\phi: \Sigma^+ -> \Sigma^+$, where $\Sigma$ is any alphabet, can be nontrivially expressed as a composition $\phi = \psi_2 \circ \psi_1$ of endomorphisms $\psi_1, \psi_2: \Sigma^+ -> \Sigma^+$. We, hence, study a notion of primality in the endomorphism monoid of the free semigroup---a natural and fundamental concept in this algebraic structure. We establish that irreducibility is a nontrivial property for the class of so-called rank-preserving endomorphisms, and we provide a characteristic condition separating the reducible and irreducible endomorphisms. We also characterise when an endomorphism is a factor of another endomorphism, analyse the non-uniqueness of factorisations of a rank-preserving endomorphism into its irreducible components, and investigate the use of incidence matrices to give insights into the (ir-)reducibility of rank-preserving endomorphisms.
1 Introduction
The paper asks when an endomorphism of a free semigroup can be nontrivially factored, focusing on rank-preserving endomorphisms as a setting for studying primality under composition. It characterizes reducibility and factor relations, examines non-unique irreducible factorizations, and uses incidence matrices to study reducibility.
1 Introduction
- Earlier work studied simplifiable morphisms through alphabet reduction, while related code theory allowed prime factorisation but did not require all alphabets to coincide.The paper frames its same-alphabet restriction as a distinct setting for studying compositions.Source: §1 · pp. 1–2
- Restricting to rank-preserving endomorphisms makes the domain, range, and all intermediate alphabets in composition chains coincide.Within this setting, the paper characterizes irreducibility and factor relations, studies non-unique factorizations into irreducible components, and explores incidence matrices.Source: §1 · p. 2
- The paper is organized around characterizing irreducibility and factor relations, examining uniqueness of factorisations, and applying incidence matrices.These topics are treated in Sections 3, 4, and 5, respectively.Source: §1 · p. 2
- Some proofs are omitted from the main text because of space constraints and appear in the full version [6].Source: §1 · p. 2
2 Preliminaries
The preliminaries establish notation for words over an alphabet and define morphisms, endomorphisms, and their factorisations. They also specify related notions such as codes, reversal, and factors of endomorphisms.
2 Preliminaries
- An alphabet is a non-empty set of symbols, and Σ+ is the set of non-empty words over Σ, called the free semigroup generated by Σ.Σ* additionally includes the empty word ε; concatenation joins words in sequence.Source: §2 · p. 2
- The preliminaries define a code by unique decomposition into its words and define reversal by reversing the order of symbols.They also introduce symb(W), the union of symbols appearing in a set of words, and notation for factors, prefixes, and suffixes.Source: §2 · p. 2
- A morphism preserves concatenation and is fully specified by its images on the symbols; an endomorphism has the same alphabet as domain and range.An automorphism is a renaming: an injective endomorphism that maps each symbol to a single symbol.Source: §2 · p. 2
- A factorisation writes ϕ as ψ2 ◦ψ1, while μ is a factor of ϕ when ϕ can be written ψ2 ◦μ ◦ψ1.Left- and right-factors occupy the first and second positions, respectively, in a two-morphism composition.Source: §2 · p. 3
3 Observations and Fundamental Characterisations
This section develops characterisations of reducibility and factorization via factor bases, including their relationship to irreducible factors, when one endomorphism is a factor of another, and the possible non-uniqueness of decompositions of rank-preserving endomorphisms. Examples apply Theorem 2 to rank-preserving endomorphisms to show cases with and without factorisations and a search that may be smaller than exhaustive search.
3 Observations and Fundamental Characterisations
- A morphism between nested alphabets admits a nontrivial decomposition unless exactly one image has length two and all other images have length one.This motivates restricting the subsequent analysis to endomorphisms.Source: §3 · p. 3
- Rank preservation is equivalent to every factor basis having |Σ| members, and such bases must be codes; injectivity alone does not guarantee rank preservation.The related decision problems are NP-complete for existence of a factor basis of size at most |Σ|−1 and co-NP-complete for determining whether every factor basis has size |Σ|.Source: §3 · pp. 3–4
- A rank-preserving endomorphism over an alphabet of size greater than one is reducible exactly when it has a nontrivial factor basis.A nontrivial factor basis is neither the set of morphic images nor the alphabet itself.Source: §3 · p. 4
- Rank-preserving endomorphisms can have multiple nontrivial factor bases and distinct factorizations into irreducible endomorphisms.Example 5 gives two nontrivial bases and two decompositions of ϕ into irreducible factors; another example contrasts a reducible endomorphism with an irreducible one.Source: §3 · pp. 4–6
- A set V is a factor basis of an endomorphism exactly when it is the set of images of letters under a left factor in some factorization of that endomorphism.The result applies to all endomorphisms, not only rank-preserving ones.Source: §3 · p. 6
- An induced endomorphism factors into non-automorphisms exactly when a more-derived nontrivial factor basis exists.This links the most refined factor bases to decompositions into irreducible factors.Source: §3 · p. 7
- Reducibility is preserved under reversal and under equivalence by pre- and post-composition with automorphisms.Equivalent endomorphisms form an equivalence relation.Source: §3 · p. 7
- An endomorphism μ is a factor of ϕ exactly when a factor basis of ϕ, a suitable surjection, and preimage words in τ_V^f satisfy the stated conditions.For each alphabet letter, the theorem requires a word in τ_V^f(ϕ(ai)) that is also generated by the images of μ.Source: §3 · p. 7
Examples illustrating Theorem 2
- A factor basis V of ϕ implies endomorphisms ψ1 and ψ2 with ϕ = ψ2 ◦ µ ◦ ψ1.The proof establishes ϕ(ai) = ψ2(µ(ψ1(ai))) for every i.Source: §3 · p. 8
- For µ(a)=bb, µ(b)=a and ϕ(a)=aaaab, ϕ(b)=baaaa, Theorem 2 shows µ factors ϕ and yields an explicit decomposition of ϕ.Using ψ1(a)=ab, ψ1(b)=ba, ψ2(a)=b, and ψ2(b)=aa gives ϕ = ψ2 ◦ µ ◦ ψ1.Source: §3 · p. 8
- For µ(a)=aab, µ(b)=aba and the stated ϕ, none of its possible factor bases satisfies Theorem 2, so µ is not a factor of ϕ.The example checks candidate bases and surjections, then concludes that none meets the theorem’s condition.Source: §3 · pp. 8–9
- Although the decision procedure appears complex, the examples show its search space can be smaller than exhaustive search over all possible ψ1 and ψ2.The comparison concerns the search space implied by the proof of Theorem 2.Source: §3 · p. 9
4 Uniqueness of Factorisations
The section distinguishes non-uniqueness of irreducible factors from non-uniqueness of their order, and develops conditions for unique or non-unique factorisation. It gives results for unary and binary alphabets and extends the existence of irreducibles to any alphabet.
4 Uniqueness of Factorisations
- Distinct maximally derived factor bases provide a separate source of non-uniqueness: they yield non-unique irreducible factors.The section also distinguishes this from unique irreducible factors whose order may vary.Source: §4 · pp. 9, 11
- On a unary alphabet, every rank-preserving endomorphism has a unique irreducible factorisation up to reordering, and irreducibles are exactly those with ϕ(a) = ap for prime p.Source: §4 · pp. 9–10
- There are infinitely many rank-preserving irreducible endomorphisms over every alphabet.The section obtains the broader-alphabet result through a natural embedding of endomorphisms.Source: §4 · p. 10
- A binary rank-preserving endomorphism has non-unique irreducible factors under Proposition 9’s condition that it has a factor μ with μ(a) ∈ a+(ba+)+ and μ(b) ∈ a+(ba+)∗.The factorization is into irreducible endomorphisms.Source: §4 · p. 10
- For the binary map in Example 11, the factor bases {a2,b} and {a,b5} are both maximally derived, so its factorisation into irreducibles is not unique.The example uses images ϕ(a) = a6b5a4b5 and ϕ(b) = a4b10a4.Source: §4 · p. 10
- Example 12 concludes that the displayed binary rank-preserving endomorphism has a unique factorisation into irreducible components.Its factor basis V = {a,b5} is maximally derived, and the other considered forms do not give another factorisation.Source: §4 · p. 10
- For binary rank-preserving maps with alternating runs and nontrivial gcds of run lengths, Proposition 10 characterizes unique reducibility through prime-power gcd conditions and exclusions on image forms.The conditions address both gcds of the a-runs and b-runs and specify forms that the images must avoid.Source: §4 · p. 11
- A second source of non-unique factorisation is unique irreducible factors in different orders; the section investigates this through commutativity and notes that strong results for all endomorphisms are expected to be challenging.Source: §4 · p. 11
5 Incidence Matrices
Incidence matrices translate endomorphism composition into matrix multiplication, giving necessary constraints and useful sufficient criteria for reducibility, but not a complete characterization.
5 Incidence Matrices
- A rank-reducing endomorphism has an incidence matrix of rank below the alphabet size, but the converse fails, and full matrix rank does not establish irreducibility.The paper gives a rank-one matrix for a rank-preserving map and an example of a full-rank matrix shared by reducible and irreducible maps.Source: §5 · p. 12
- For rank-preserving endomorphisms, composition corresponds to multiplication of incidence matrices.For ϕ = ψ2 ◦ ψ1, P(ϕ) = P(ψ1)P(ψ2).Source: §5 · p. 12
- A reducible rank-preserving endomorphism must have a factorable incidence matrix, but matrix factorability alone does not imply reducibility.Two endomorphisms with the same incidence matrix can differ: one may be reducible and another irreducible.Source: §5 · pp. 11–12
- An incidence matrix with at least two entries greater than 1 represents exclusively reducible rank-preserving endomorphisms.Source: §5 · p. 13
- For alphabets of size n ≥ 3, a positive upper triangular incidence matrix represents exclusively reducible rank-preserving endomorphisms.Source: §5 · p. 13
- The incidence-matrix approach does not fully characterize reducibility for upper triangular rank-preserving endomorphisms over a binary alphabet.The matrix construction loses endomorphism structure needed for that characterization.Source: §5 · p. 13
- A matrix with a non-coprime pair of entries or a dominating row or column cannot represent exclusively irreducible rank-preserving endomorphisms.Such matrices admit at least one reducible rank-preserving endomorphism.Source: §5 · p. 14
- The paper relates matrix structure to endomorphism reducibility and identifies both the benefits and limits of that approach.Source: §5 · p. 14
6 Conclusion
The paper characterizes reducibility and factor relations for rank-preserving endomorphisms, while showing that irreducible factorizations need not be unique. It also identifies open problems in factorization criteria, alphabet scope, and computational complexity.
6 Conclusion
- The paper characterizes reducibility using factor bases and gives conditions for when one endomorphism is a factor of another.Source: §6 · p. 14
- Factorizations of rank-preserving endomorphisms into irreducible components need not be unique, though conditions for uniqueness are given for a large class of binary endomorphisms.Source: §6 · p. 14
- Characteristic conditions for unique factorization, extension of the investigations to larger alphabets, and the decision procedure’s computational complexity remain open problems.Source: §6 · p. 14