{"id":"e0bc55ea-0cd8-402d-8d9d-605382cc7063","arxiv_id":"2603.15177","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A morphism on a free semigroup is irreducible exactly when its image words admit no nontrivial factor basis; the paper proves this and related factorization results.","lead":"This paper defines and studies when an endomorphism of a free semigroup can be written as a composition of two nontrivial endomorphisms, giving a notion of 'prime' morphisms. It characterizes such irreducible morphisms via factor bases and explores non-unique decompositions.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1 is false as stated: the Parikh-positive morphism φ(a)=φ(b)=ab over {a,b} is reducible but has no non-trivial factor basis, contradicting the claimed characterization.","rationale":"The reader's CONDITIONAL verdict was based on proof gaps, a false Proposition 15, and the restriction to same-alphabet factorizations. However, I find a concrete counterexample to the central theorem itself. The issue is not merely a missing proof or an overly narrow definition: Theorem 1 is logically incompatible with Proposition 3. The counterexample is minimal and does not depend on subtleties of intermediate alphabets. The likely repair is to restrict Theorem 1 to rank-preserving morphisms, i.e., those with |W|=|Σ|, matching the abstract; with that hypothesis the counterexample disappears. But as printed, the theorem's statement is false, so the central contribution cannot be accepted. A revision that adds the missing hypothesis and rechecks the proof could potentially make the claim correct, hence REJECT rather than UNVERDICTED.","tokens_in":26301,"tokens_out":8086,"duration_ms":72420,"concrete_test":"Enumerate all subsets V⊆{a,b}+ with |V|≤1 and verify that the only one satisfying {ab}⊆V+ is {ab}. Then compute the explicit factorization ψ1(a)=a, ψ1(b)=a, ψ2(a)=ab, ψ2(b)=aa, and verify ψ2∘ψ1=φ with neither ψ1 nor ψ2 an automorphism. This direct check refutes Theorem 1 as stated. A second confirmatory test: apply the proof of Theorem 1's 'only if' direction to this reducible morphism and observe that the set it constructs has cardinality 2>|W|, so it is not a factor basis under Definition 2.","verdict_should_be":"REJECT","load_bearing_attack":"The central characterization (Theorem 1) fails unless a rank-preserving condition |W|=|Σ| is added. Counterexample: Σ={a,b}, φ(a)=φ(b)=ab. Then W={ab}, so |W|=1<n=2; φ is Parikh-positive. Yet φ is reducible: take ψ1(a)=a, ψ1(b)=a and ψ2(a)=ab, ψ2(b)=aa. Neither is an automorphism, and ψ2∘ψ1(a)=ψ2∘ψ1(b)=ab=φ(a)=φ(b). But W admits no non-trivial factor basis: any factor basis V with |V|≤|W|=1 must be a singleton {v} with ab∈{v}+, forcing v=ab, hence V=W, the trivial basis. (V={a,b} is excluded since |V|=2>|W|.) Thus Theorem 1's 'only if' direction fails. This also directly conflicts with Proposition 3, which declares φ reducible. The proof of the 'only if' direction in Section 3 produces a set of size at most n, not at most |W|, so the argument silently assumes |W|=n. The abstract's restriction to 'rank-preserving' endomorphisms is never stated in Theorem 1, and consequently the theorem as printed is not merely unproven but false.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":26599,"tokens_out":10364,"duration_ms":91990,"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":[{"comment":"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.","section":"Section 3, Proposition 8"}],"minor_comments":[{"comment":"Typos: 'ψ2(u_i)' should be 'ψ2(v_i)', and 'Assume first that V=W' should probably be 'Assume first that U=W'.","section":"Section 3, proof of Theorem 1"},{"comment":"There is a formatting error: 'V∩Σ+V=V∩VΣ+ = / 0' should be 'V∩Σ+V = V∩VΣ+ = ∅'.","section":"Section 3, Proposition 8 proof"},{"comment":"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.","section":"Appendix A"},{"comment":"Several places contain typos such as 'e g.' instead of 'e.g.', and reference [14] has 'Cambrige' instead of 'Cambridge'.","section":"Throughout"},{"comment":"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.","section":"Definition 2 and Corollary 1"}],"recommendation":"major_revision","confidential_remarks":"The main theorem as printed is false; the counterexample in my major comment is decisive. I nevertheless recommend major revision rather than rejection because the abstract's 'rank-preserving' condition points to a plausible fix, and the factor-basis framework may be salvageable. However, the proof of the only-if direction needs substantial rework, and Proposition 15 is false. The paper would benefit from a careful revision that states the rank-preserving hypothesis in Theorem 1, repairs the proof, and corrects or removes the false auxiliary claims."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know. The factor-basis characterization in Theorem 1 is false as stated; the abstract restricts to “rank-preserving” endomorphisms, but that assumption never appears in the theorem. A simple counterexample: over {a,b}, take φ(a)=φ(b)=ab. This is Parikh-positive and reducible (ψ1(a)=ψ1(b)=a, ψ2(a)=ab, ψ2(b)=aa), but W={ab} has no non-trivial factor basis since any singleton basis must be {ab}=W. So the “only if” direction fails whenever |W|<|Σ|.\n\nThat said, the underlying idea is worth engaging. The paper proposes a natural notion of irreducibility where all alphabets stay the same, distinct from Ehrenfeucht–Rozenberg simplifiability and indecomposable codes. Example 2 makes the distinction concrete. The factor-basis technique is sensible, and the worked examples are genuinely illustrative. The incidence-matrix section is a reasonable first pass at a matrix-level perspective.\n\nThe soft spots are serious. The proof of Theorem 1’s only-if direction interchanges the roles of ψ1's images (V) and ψ2's images (U), and the “Assume first that V=W” case is load-bearing but not justified. Proposition 15, on commutativity, is false as stated—conditions on φ2's action on S are missing. Several Section 5 proofs are sketches, and the “full version” reference [5] is the same arXiv ID, so the omitted proofs are self-referential. The abstract’s rank-preserving term is never defined in the text.\n\nFor the right reader—combinatorics on words, morphism factorisation—this could be a real contribution once repaired. The counterexample suggests a fix (require |W|=|Σ|, i.e., rank-preserving), and the rest of the framework may survive. But as printed, the central theorem is wrong, so I would not cite it yet.\n\nSend it to peer review. A good referee can check whether the rank-preserving fix goes through and whether Proposition 15 can be salvaged. It needs heavy revision, not desk rejection.","headline":"Factor-basis idea is salvageable, but Theorem 1 is false as stated because the rank-preserving assumption never makes it into the theorem statement.","tokens_in":27091,"tokens_out":3830,"would_cite":false,"duration_ms":34080,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["20M05","68Q45","68R15"],"pacs":[],"model":"deepseek-v4-flash","headline":"Parikh-positive endomorphisms of free semigroups are reducible exactly when their letter images have a non-trivial factor basis, making irreducibility decidable.","keywords":["irreducible morphisms","free semigroups","endomorphism monoid","factor basis","Parikh-positive morphisms","morphism factorisation","incidence matrices","word combinatorics"],"falsifier":"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.","tokens_in":26176,"feed_emoji":"🔤","tokens_out":8086,"duration_ms":72027,"temperature":0.7,"pith_summary":"The paper introduces a notion of primality for endomorphisms of finitely generated free semigroups: an endomorphism is irreducible when it cannot be written as a composition of two non-renaming endomorphisms over the same alphabet. Its central result is a complete characterisation: for a Parikh-positive endomorphism (one whose letters all appear in the concatenation of the letter images), reducibility holds exactly when the set of letter images has a non-trivial factor basis—a smaller set of words that generates all of those images by concatenation. This turns the infinite search for a factorisation into a finite combinatorial problem, so irreducibility becomes decidable in principle. The paper also characterises when one morphism is a factor of another, analyses when factorisations into irreducible components are unique, and shows how incidence matrices give sufficient conditions for reducibility or irreducibility. A sympathetic reader would care because words, morphisms, and their decompositions are central to combinatorics on words and to the algebraic study of free monoids.","feed_headline":"Non-trivial factor basis reveals every reducible morphism","feed_subtitle":"New theorem turns morphism factorization into a finite search for a generating word set, making primality decidable.","key_machinery":"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","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Reducibility test reduced to finite word set search","Primality of semigroup endomorphisms is decidable","Factor basis criterion for irreducible morphisms","Morphism irreducibility: finite check via factor basis","Reducibility iff nontrivial factor basis exists"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Reducibility test reduced to finite word set search","Primality of semigroup endomorphisms is decidable","Factor basis criterion for irreducible morphisms","Morphism irreducibility: finite check via factor basis","Reducibility iff nontrivial factor basis exists"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00099,"raw_usage":{"total_tokens":4049,"prompt_tokens":776,"completion_tokens":3273,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":520,"completion_tokens_details":{"reasoning_tokens":3211}},"tokens_in":520,"tokens_out":3273,"duration_ms":21064,"temperature":1.0,"reasoning_tokens":3211,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T18:07:39.290913+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":2}