REVIEW 1 major objections 5 minor 15 references
Irreducibility of Endomorphisms of Finitely Generated Free Semigroups
T0 review · 1 major / 5 minor · reviewed 2026-08-02 · deepseek-v4-flash
Pith's one-line read Parikh-positive endomorphisms of free semigroups are reducible exactly when their letter images have a non-trivial factor basis, making irreducibility decidable.
desk verdict Factor-basis idea is salvageable, but Theorem 1 is false as stated because the rank-preserving assumption never makes it into the theorem statement. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the factor basis (Definition 2). Given the set W={φ(a1),...,φ(an)} of letter images of a Parikh-positive endomorphism φ, a factor basis is any set V⊆Σ+ with |V|≤|W| and W⊆V+, i.e., V generates every image word by concatenation. It is non-trivial when V is not simply W and not the whole alphabet Σ. Theorem 1 makes this object the exact criterion for reducibility: φ is reducible exactly when such a non-trivial V exists. The factor basis also underlies the derivation order on factorisations (Definition 4), the factor characterisation in Theorem 2, and the sufficient matrix conditions in Section 5; incidence matrices give a coarser, matrix-level view that is necessary but n
What would settle it
Take a concrete Parikh-positive morphism, such as φ(a)=ab^3ab^2a and φ(b)=b^2a^2b over {a,b}. If an exhaustive search over all candidate pairs (ψ1,ψ2) with bounded image lengths fails to reproduce φ despite the non-trivial factor basis {ab,bba}, the 'if' direction of Theorem 1 would be refuted. Conversely, if a morphism with no non-trivial factor basis is found to have any non-trivial factorisation into endomorphisms, the 'only if' direction fails.
Extended reading notes
Core claim
The paper's main claim is Theorem 1: for any alphabet Σ with at least two letters and any Parikh-positive morphism φ:Σ+→Σ+, writing W={φ(a):a∈Σ}, φ is reducible if and only if there exists a non-trivial factor basis V of W, meaning |V|≤|W|, W⊆V+, V≠W, and V≠Σ. The 'if' direction constructs the two factors from a chosen factorisation of each φ(a) over V; the 'only if' direction shows that any non-trivial composition yields such a factor basis, after possibly adjusting the factorization. The theorem gives a decision procedure: to test reducibility, enumerate candidate factor bases rather than pairs of morphisms. The paper further proves (Theorem 2) that a Parikh-positive morphism μ is a factor
Load-bearing premise
The load-bearing premise is that reducibility is defined only for factorisations in which both factors are endomorphisms over the same alphabet (enforced by considering Parikh-positive morphisms); if factorisations through alphabets of smaller cardinality were allowed, the 'only if' direction of the characterisation would no longer hold.
Editorial extensions
If this is right
- Irreducibility of Parikh-positive endomorphisms is decidable: it is enough to search for factor bases of the image set, never for whole pairs of factor morphisms.
- The characterisation of factors (Theorem 2) provides a decision procedure for 'is μ a factor of φ?' whose search space is limited to factor bases of φ, which can be far smaller than an exhaustive search over morphisms.
- Most morphisms that are not Parikh-positive are automatically reducible (Propositions 1 and 2), so the only genuinely interesting case is the endomorphism case treated by Theorem 1.
- Factorisations into irreducible components are not unique in general; non-injective factors force non-uniqueness, and for a large class of binary morphisms uniqueness is characterised by conditions on the gcds of block lengths (Proposition 13).
- Incidence-matrix factorisation is necessary but not sufficient for morphism reducibility: there are matrices that represent both reducible and irreducible morphisms, and certain matrices—such as strictly positive upper triangular ones—force reducibility for all represented morphisms.
Reading between the lines
- The factor-basis criterion suggests a natural partial order on factorisations via the derivation graph; if the paper's equivalence is extended, this could yield a canonical normal form for endomorphisms under composition with automorphisms, though the paper does not claim this.
- Relaxing the Parikh-positive assumption to allow factorisations through smaller alphabets would likely make the notion coincide with earlier simplification ideas; the paper leaves one exceptional case (exactly one image of length two, all others length one) uncharacterised, and testing that case might reveal how essential the same-alphabet restriction really is.
- The incidence-matrix results open a concrete route to importing known factorisation results for non-negative integer matrices into morphism theory, potentially giving efficient sufficient tests for reducibility before any word-level search.
- For unary alphabets the theorem recovers the classical fact that irreducibility corresponds to prime lengths; by the paper's embedding construction, this yields infinitely many irreducible morphisms over any alphabet, so the prime-counting intuition transfers to this monoid.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces a notion of irreducibility (primality) for endomorphisms of a finitely generated free semigroup: an endomorphism φ:Σ+→Σ+ is irreducible if it cannot be written as a composition φ=ψ2∘ψ1 of two non-automorphisms. The authors restrict attention to Parikh-positive morphisms so that all intermediate alphabets coincide with Σ. The main result, Theorem 1, claims that a Parikh-positive morphism is reducible if and only if its image set W admits a non-trivial factor basis V (i.e., |V|≤|W|, W⊆V+, and V is neither W nor Σ). Section 3 also characterizes when one morphism is a factor of another (Theorem 2) and gives a linear-time test for left-factors (Proposition 8). Section 4 studies non-uniqueness of factorizations and commutativity of morphisms. Section 5 uses incidence matrices to give sufficient conditions for reducibility or irreducibility. The abstract mentions that the main characterization is for 'rank-preserving' endomorphisms.
Significance. If the main characterization were correct, it would give a natural, decidable notion of primality in the endomorphism monoid of a free semigroup, complementing the classical theories of Ehrenfeucht–Rozenberg simplifications and indecomposable codes. The paper is well illustrated with examples, and the factor-basis idea is appealing. However, the central theorem as printed is false, and several side claims (notably Proposition 15) are also false or inadequately justified. The rank-preserving restriction mentioned in the abstract suggests a possible repair, so the underlying approach may still be valuable, but substantial corrections and re-proofs are required before the results can be relied upon.
major comments (1)
- [Section 3, Proposition 8] The claimed linear-time decision procedure for left-factors is not adequately justified. The proof says one may assume V is biprefix, but does not explain how the original left-factor question reduces to the biprefix case, nor why the biprefix replacement preserves the existence of a left-factor. The assertion that each w_j is uniquely decipherable over V relies on V being a code, which is not established from the reduction. This proposition needs a correct argument or should be weakened.
minor comments (5)
- [Section 3, proof of Theorem 1] Typos: 'ψ2(u_i)' should be 'ψ2(v_i)', and 'Assume first that V=W' should probably be 'Assume first that U=W'.
- [Section 3, Proposition 8 proof] There is a formatting error: 'V∩Σ+V=V∩VΣ+ = / 0' should be 'V∩Σ+V = V∩VΣ+ = ∅'.
- [Appendix A] The text says 'In Example 1, we show that φ1 is irreducible', but Example 1 states that φ1 is reducible and φ2 is irreducible; the appendix appears to discuss φ2.
- [Throughout] Several places contain typos such as 'e g.' instead of 'e.g.', and reference [14] has 'Cambrige' instead of 'Cambridge'.
- [Definition 2 and Corollary 1] When a factor basis V has fewer than n elements, the paper often defines a morphism ψ2 by ψ2(ai)=v_i for i≤m, leaving i>m undefined. A convention for extending V to a full endomorphism image set should be stated.
Circularity Check
No significant circularity: the factor-basis characterization is proved by explicit construction, and the paper's only self-citation ([5], the same arXiv paper) is not load-bearing.
full rationale
The derivation chain is self-contained. Theorem 1 states that reducibility is equivalent to the existence of a non-trivial factor basis V of W; this is not a restatement of the definition. The 'if' direction explicitly builds ψ1 and ψ2 from a chosen factorization of each φ(ai) over V, and checks non-automorphism via V≠W and V≠Σ. The 'only if' direction attempts to construct V from a factorization, again by explicit definition. These are translations with independent content, not identities. External theorems (Defect Theorem [8], Neraud's NP-completeness [13], matrix/morphism results [6,10,11,12]) support the claims and are not replaced by self-citations. The only self-citation is [5], which is the same arXiv paper, used in 'Due to space constraints, missing proofs can be found in the appendix or the full version [5]'; since the appendix contains the omitted proofs and no central theorem is justified solely by [5], this is a minor self-reference, not a circular step. For correctness, not circularity: the abstract restricts to 'rank-preserving' endomorphisms, while Theorem 1 states the result for all Parikh-positive morphisms; as printed, Theorem 1 fails for φ(a)=φ(b)=ab, but this is a missing assumption/gap, not a derivation that reduces to its inputs.
Assumptions & free parameters
assumptions (4)
- standard math Standard definitions of free semigroup, morphism, automorphism, and renaming are used.
- domain assumption Only Parikh-positive endomorphisms over the same alphabet are characterized.
- standard math The Defect Theorem [8] and Neraud's NP-completeness result [13] are used as external results.
- standard math Incidence-matrix composition corresponds to morphism composition, following [6].
Cite this review
Pith. "Pith review of Irreducibility of Endomorphisms of Finitely Generated Free Semigroups." pith.science (2026). https://pith.science/paper/HWQDYCRN
@misc{pith2026260315177,
author = {Pith},
title = {Pith review of: Irreducibility of Endomorphisms of Finitely Generated Free Semigroups},
year = {2026},
howpublished = {\url{https://pith.science/paper/HWQDYCRN}},
note = {Machine review of arXiv:2603.15177}
}
abstract
We introduce and investigate the irreducibility of endomorphisms of finitely generated free semigroups, i.e., we investigate when an endomorphism $\varphi: \Sigma^+ \to \Sigma^+$, where $\Sigma$ is any alphabet, can be nontrivially expressed as a composition $\varphi = \psi_2 \circ \psi_1$ of endomorphisms $\psi_1, \psi_2: \Sigma^+ \to \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.
Figures
Reference graph
Works this paper leans on
-
[5]
P. C. Bell, E. Foster & D. Reidenbach:Irreducibility of Semigroup Morphisms. arXiv:2603.15177
-
[1]
N. R. Baeth, H. Chen, G. Heilbrunn, R. Liu & M. Young (2022):Semigroups of non-negative integer-valued matrices.Communications in Algebra50, pp. 1199–1219, doi:10.1080/00927872.2021.1979569
arXiv 2022
-
[2]
N. R. Baeth & M. Enlow (2019):Multiplicative Factorization in Numerical Semigroups.International Journal of Algebra and Computation30, doi:10.1142/S0218196720500058
-
[3]
N. R. Baeth, V . Ponomarenko, D. Adams, R. Ardila, D. Hannasch, A. Kosh, H. McCarthy & R. Rosen- baum (2011):Number theory of matrix semigroups.Linear Algebra and its Applications434, pp. 694–711, doi:10.1016/j.laa.2010.09.028
-
[4]
N. R. Baeth & D. Smertnig (2015):Factorization theory: From commutative to noncommutative settings. Journal of Algebra441, pp. 475–551, doi:10.1016/j.jalgebra.2015.06.007
-
[6]
S. Cautis, F. Mignosi, J. Shallit, M. Wang & S.Yazdani (2003):Periodicity, morphisms and matrices.Theo- retical Computer Science295, pp. 107–121, doi:10.1016/S0304-3975(02)00398-5
-
[7]
A. Ehrenfeucht & G. Rozenberg (1978):Simplifications of Homomorphisms.Information and Control38, pp. 298–309, doi:10.1016/S0019-9958(78)90095-5
-
[8]
T. Harju & J. Karhum ¨aki (2004):Many aspects of defect theorems.Theoretical Computer Science324, pp. 35–54, doi:10.1016/j.tcs.2004.03.051
Show all 15 references
-
[9]
Heilbrunn (2023):Decomposition of Nonnegative Integer-entry Matrices
G. Heilbrunn (2023):Decomposition of Nonnegative Integer-entry Matrices. Master’s the- sis, Franklin and Marshall College. Available athttps://digital.fandm.edu/islandora/ decomposition-nonnegative-integer-entry-matrices
2023
-
[10]
Honkala (2019):A characterization of free pairs of upper triangular free monoid morphisms.Information and Computation267, pp
J. Honkala (2019):A characterization of free pairs of upper triangular free monoid morphisms.Information and Computation267, pp. 110–115, doi:10.1016/j.ic.2019.03.007
2019 doi
-
[11]
Honkala (2024):Commuting Upper Triangular Binary Morphisms.Fundamenta Informaticae191, pp
J. Honkala (2024):Commuting Upper Triangular Binary Morphisms.Fundamenta Informaticae191, pp. 285–298, doi:10.46298/fi.10954
2024 doi
-
[12]
Karhum ¨aki (1984):A Note on Intersections of Free Submonoids of a Free Monoid.Semigroup Forum29, pp
J. Karhum ¨aki (1984):A Note on Intersections of Free Submonoids of a Free Monoid.Semigroup Forum29, pp. 183–205, doi:10.1007/BF02573324
1984 doi
-
[13]
Neraud (1990):Elementariness of a finite set of words is co-NP-complete.RAIRO-Theor
J. Neraud (1990):Elementariness of a finite set of words is co-NP-complete.RAIRO-Theor. Inf. Appl.24(5), pp. 459–470, doi:10.1051/ita/1990240504591
1990
-
[14]
Reutenauer, D
C. Reutenauer, D. Perrin & J. Berstel (2009):Codes and Automata. Cambrige University Press, doi:10.1017/CBO9781139195768. 16Irreducibility of Semigroup Morphisms A Appendix: Exhaustive Search ψ1(a) =a ψ1(a) =a ψ1(a) =a ψ1(a) =a ψ1(a) =a ψ1(a) =a ψ1(a) =a ψ1(b) =b ψ1(b) =ba ψ1(...
2009 doi
-
[15]
We note that automorphisms are closed under composition, thusϕ1 ∼= ϕ3
We can then see that ϕ1 =ψ 2 ◦ψ ′ 2 ◦ϕ3 ◦ψ ′ 1 ◦ψ1. We note that automorphisms are closed under composition, thusϕ1 ∼= ϕ3. Proof of Proposition 7. Letϕbe an reducible morphism, and thereforeϕadmits a non-trivial factor basisV={v 1,v 2, . . . ,vm} ⊂Σ+ wherem≤n. If eϕ=ψ◦ϕfor som...
Reviewed August 2, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.