pith. sign in

arxiv: 2605.18034 · v1 · pith:66NSZ3E7new · submitted 2026-05-18 · 🧮 math.CO · cs.DS

On Occurrence-Preserving Morphisms

Kaisei Kishi , Peaker Guo , Cristian Urbina , Hideo Bannai This is my paper

Pith reviewed 2026-05-20 09:37 UTC · model grok-4.3

classification 🧮 math.CO cs.DS
keywords occurrence-preserving morphismsinterference-free morphismscombinatorics on wordsminimal unique substringsFibonacci wordThue-Morse wordnet occurrences
0
0 comments X

The pith

A morphism preserves the exact number of occurrences of one word inside another under repeated substitution precisely when it is interference-free.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper aims to find conditions on a morphism so that the count of how many times a fixed word u appears inside another word v stays the same after the morphism is applied any number of times to both strings. If true, this would let researchers follow the positions of specific patterns through the infinite words built by iterating morphisms, such as the Fibonacci and Thue-Morse words. The authors define interference-free morphisms as those that avoid certain overlapping substitutions that would create or destroy occurrences. They prove this property is necessary and sufficient for occurrence preservation. The result also gives a direct correspondence between the locations of the original occurrences and the locations after substitution.

Core claim

Occurrence-preserving morphisms are exactly the interference-free morphisms. A morphism φ is interference-free when the images of adjacent letters under φ do not overlap in a manner that alters the count of occurrences of φ(u) inside φ(v) compared with the count of u inside v. This equivalence holds for every k and every pair of words u and v.

What carries the argument

Interference-free morphism: a substitution rule whose letter images are placed so that no unintended overlaps affect substring occurrence counts under iteration.

If this is right

  • The starting positions of occurrences of u in v stand in one-to-one correspondence with the starting positions of occurrences of φ^k(u) in φ^k(v).
  • The characterization identifies all minimal unique substrings of the Fibonacci word.
  • The characterization identifies all minimal unique substrings of the Thue-Morse word.
  • Existing proofs about net occurrences in these two words become shorter by using the new bijection of positions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The decision algorithm for interference-freeness could be applied to other infinite morphic words to locate their minimal unique substrings automatically.
  • Recognizable morphisms, already known to be related, may inherit occurrence-preservation results for free.
  • The position bijection might extend to counting net occurrences in words generated by non-uniform morphisms.

Load-bearing premise

Interference-freeness is both necessary and sufficient for preserving occurrence counts under iteration, with no extra hidden restrictions coming from particular overlaps or alphabet size.

What would settle it

Exhibit one concrete morphism together with words u and v and an integer k such that the number of occurrences of u in v equals the number of occurrences of φ^k(u) in φ^k(v), yet the morphism fails the paper's definition of interference-freeness.

Figures

Figures reproduced from arXiv: 2605.18034 by Cristian Urbina, Hideo Bannai, Kaisei Kishi, Peaker Guo.

Figure 6
Figure 6. Figure 6: Illustration of Theorem 33. In the top two factorizations of Fi, each MUS is highlighted in a red rectangle. In the bottom three factorizations of Fi, each net occurrence is colored. Moreover, the colors of the two consecutive net occurrences together are used as the colors to highlight the occurrence of the MUS they correspond to. The uncolored factorization is used in the proof. Proof. It suffices to pro… view at source ↗
read the original abstract

A \emph{morphism} is a mapping that transforms words through letter-wise substitution, where each symbol is consistently replaced by a fixed word. In the field of combinatorics on words, one topic that has attracted considerable attention is the characterization of morphisms that preserve specific properties, such as overlap-freeness, square-freeness, lexicographic order, and primitivity. Continuing this direction, we initiate the study on \emph{occurrence-preserving morphisms}, which address the following fundamental question: given a morphism $\phi$, two words $u$ and $v$, and $k \geq 1$, under what conditions does the number of occurrences of $u$ in $v$ equal the number of occurrences of $\phi^k(u)$ in $\phi^k(v)$? To answer this question, we introduce the notion of \emph{interference-free morphisms}, examine their properties, develop an efficient algorithm for deciding interference-freeness, and uncover a connection to \emph{recognizable morphisms}. We then present a precise characterization of occurrence-preserving morphisms in terms of interference-freeness. As applications of our characterization, we first show that there exists a bijection between the starting positions of the occurrences of $u$ in $v$ and those of $\phi^k(u)$ in $\phi^k(v)$. We then apply the characterization to the Fibonacci and Thue-Morse words to identify their \emph{minimal unique substrings~(MUSs)}. Finally, we exploit the connection between MUSs and \emph{net occurrences} to simplify existing proofs on net occurrences in these words.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The paper introduces occurrence-preserving morphisms φ on words, defined by the property that the number of occurrences of any word u in v equals the number of occurrences of φ^k(u) in φ^k(v) for all k ≥ 1. It defines interference-free morphisms, proves that φ is occurrence-preserving precisely when it is interference-free, gives an efficient decision algorithm for the property, relates it to recognizable morphisms, and applies the result to compute minimal unique substrings (MUSs) in the Fibonacci and Thue-Morse words while simplifying prior arguments on net occurrences.

Significance. If the central characterization is correct, the work supplies a decidable criterion for a natural preservation property of morphisms, together with a concrete algorithm and a link to recognizable morphisms. The applications to automatic sequences (Fibonacci, Thue-Morse) and the explicit bijection between occurrence positions are useful concrete contributions that could facilitate further analysis of factors and net occurrences in morphic words.

major comments (2)
  1. [main characterization theorem / sufficiency proof] Proof of the main characterization (sufficiency direction): the argument that interference-freeness implies occurrence-preservation must explicitly rule out new occurrences of φ(u) that straddle concatenation points φ(a)φ(b) inside φ(v). The current treatment appears to consider only intra-image or non-overlapping placements; when |φ| is non-uniform and an occurrence of φ(u) aligns with a boundary, the count |occ(φ^k(u), φ^k(v))| can increase without violating the stated interference-free condition, undermining the claimed equivalence.
  2. [definitions and main theorem] Definition of interference-freeness and its use in the necessity direction: while necessity follows directly from the definition, the paper should verify that the definition is strong enough to block all possible boundary-crossing configurations for arbitrary alphabet size and non-uniform length morphisms; otherwise the equivalence rests on an implicit restriction not stated in the axioms.
minor comments (3)
  1. [algorithm section] The abstract states that an efficient algorithm exists for deciding interference-freeness; the main text should give its time complexity in terms of the morphism size and alphabet.
  2. [preliminaries] Notation for occ(u, v) and the iteration φ^k should be introduced with a formal definition before the characterization statement.
  3. [applications] The claimed bijection between starting positions of occurrences should be illustrated with a small concrete example (e.g., a short morphism and words u, v) to make the application section easier to follow.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We appreciate the referee's detailed feedback on our manuscript. The comments highlight important aspects of the proof that we will clarify in the revision. Below we respond point by point to the major comments.

read point-by-point responses

  1. Referee: Proof of the main characterization (sufficiency direction): the argument that interference-freeness implies occurrence-preservation must explicitly rule out new occurrences of φ(u) that straddle concatenation points φ(a)φ(b) inside φ(v). The current treatment appears to consider only intra-image or non-overlapping placements; when |φ| is non-uniform and an occurrence of φ(u) aligns with a boundary, the count |occ(φ^k(u), φ^k(v))| can increase without violating the stated interference-free condition, undermining the claimed equivalence.

    Authors: We thank the referee for pointing this out. In the sufficiency proof, the interference-free condition is intended to prevent exactly such boundary-straddling occurrences by ensuring that no new matches are created at the junctions of images. However, to address the concern for non-uniform length morphisms, we will expand the proof with an explicit case analysis that considers all possible alignments of occurrences across image boundaries. This will include showing that if an occurrence straddles, it would imply a violation of interference-freeness for some subword. We agree this clarification strengthens the argument and will incorporate it in the revised version. revision: yes

  2. Referee: Definition of interference-freeness and its use in the necessity direction: while necessity follows directly from the definition, the paper should verify that the definition is strong enough to block all possible boundary-crossing configurations for arbitrary alphabet size and non-uniform length morphisms; otherwise the equivalence rests on an implicit restriction not stated in the axioms.

    Authors: The definition of interference-freeness is formulated in a way that applies generally to any morphism, including those with non-uniform lengths and over arbitrary alphabets. It prohibits the creation of new occurrences that cross image boundaries by considering the possible overlaps in the images. Nevertheless, we acknowledge that an explicit verification or additional lemma demonstrating coverage for all configurations would be beneficial. We will add such a verification in the revised manuscript to make the generality clear. revision: yes

Circularity Check

0 steps flagged

No circularity: characterization derived from newly introduced definitions

full rationale

The paper introduces interference-free morphisms as a fresh concept, develops an algorithm for deciding it, and then states a characterization of occurrence-preserving morphisms in terms of this property. No quoted steps reduce the central claim to a self-definition, a fitted parameter renamed as prediction, or a load-bearing self-citation chain. The derivation chain remains self-contained against external benchmarks, with the necessity and sufficiency directions presented as following from the new definitions rather than presupposing the target result.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

Based solely on the abstract, the work introduces new definitions (interference-free morphisms) on top of standard combinatorics-on-words background; no free parameters or invented physical entities are mentioned.

axioms (1)
  • standard math Standard definitions and properties of morphisms and word occurrences in combinatorics on words
    The paper continues prior work on morphisms preserving properties such as overlap-freeness and square-freeness.
invented entities (1)
  • interference-free morphisms no independent evidence
    purpose: To provide the precise condition for occurrence preservation under iterated morphisms
    New notion introduced to characterize the target property; no independent evidence outside the paper is described in the abstract.

pith-pipeline@v0.9.0 · 5821 in / 1296 out tokens · 38030 ms · 2026-05-20T09:37:25.365388+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

36 extracted references · 36 canonical work pages

  1. [1]

    Morphisms and

    Gabriele Fici and Giuseppe Romana and Marinella Sciortino and Cristian Urbina , editor =. Morphisms and. 50th International Symposium on Mathematical Foundations of Computer Science,. 2025 , doi =

    work page 2025

  2. [2]

    2021 , doi =

    Gonzalo Navarro and Carlos Ochoa and Nicola Prezza , title =. 2021 , doi =

    work page 2021

  3. [3]

    Recognizability of morphisms , volume=

    Marie. Recognizability of morphisms , volume=. Ergod. Th. & Dynam. Sys. , year=. doi:10.1017/etds.2022.109 , number=

    work page doi:10.1017/etds.2022.109 2022

  4. [4]

    An Algorithm That Builds a Set of Strings Given Its Overlap Graph , booktitle =

    Mar. An Algorithm That Builds a Set of Strings Given Its Overlap Graph , booktitle =. 2002 , doi =

    work page 2002

  5. [5]

    Factorizing a String into Squares in Linear Time , booktitle =

    Yoshiaki Matsuoka and Shunsuke Inenaga and Hideo Bannai and Masayuki Takeda and Florin Manea , editor =. Factorizing a String into Squares in Linear Time , booktitle =. 2016 , doi =

    work page 2016

  6. [6]

    On Prefix/Suffix-Square Free Words , booktitle =

    Marius Dumitran and Florin Manea and Dirk Nowotka , editor =. On Prefix/Suffix-Square Free Words , booktitle =. 2015 , doi =

    work page 2015

  7. [7]

    Fredman and J

    Michael L. Fredman and J. Storing a Sparse Table with. 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3-5 November 1982 , pages =. 1982 , doi =

    work page 1982

  8. [8]

    Logarithmic Equal-Letter Runs for

    Andrea Frosini and Ilaria Mancini and Simone Rinaldi and Giuseppe Romana and Marinella Sciortino , editor =. Logarithmic Equal-Letter Runs for. Developments in Language Theory - 26th International Conference,. 2022 , doi =

    work page 2022

  9. [9]

    On the Impact of Morphisms on

    Gabriele Fici and Giuseppe Romana and Marinella Sciortino and Cristian Urbina , editor =. On the Impact of Morphisms on. 34th Annual Symposium on Combinatorial Pattern Matching,. 2023 , doi =

    work page 2023

  10. [10]

    Combinatorial Algorithms - 30th International Workshop,

    Srecko Brlek and Andrea Frosini and Ilaria Mancini and Elisa Pergola and Simone Rinaldi , editor =. Combinatorial Algorithms - 30th International Workshop,. 2019 , doi =

    work page 2019

  11. [11]

    A Characterization of Overlap-Free Morphisms , journal =

    Jean Berstel and Patrice S. A Characterization of Overlap-Free Morphisms , journal =. 1993 , doi =

    work page 1993

  12. [12]

    Acta Mathematica Hungarica , volume=

    Square-free-preserving and primitive-preserving homomorphisms , author=. Acta Mathematica Hungarica , volume=. 2003 , publisher=

    work page 2003

  13. [13]

    On Morphisms Preserving Palindromic Richness , journal =

    Francesco Dolce and Edita Pelantov. On Morphisms Preserving Palindromic Richness , journal =. 2022 , doi =

    work page 2022

  14. [14]

    Characterization of Test-sets for Overlap-free Morphisms , journal =

    Gw. Characterization of Test-sets for Overlap-free Morphisms , journal =. 1999 , doi =

    work page 1999

  15. [15]

    Overlap-free morphisms and finite test-sets , journal =

    Gw. Overlap-free morphisms and finite test-sets , journal =. 2004 , doi =

    work page 2004

  16. [16]

    On Morphisms Preserving Infinite

    Gw. On Morphisms Preserving Infinite. Discret. Math. Theor. Comput. Sci. , volume =. 2007 , doi =

    work page 2007

  17. [17]

    Stepan Holub and Martin Raska , title =. Arch. Formal Proofs , volume =. 2023 , doi =

    work page 2023

  18. [18]

    Arturo Carpi , title =. Int. J. Algebra Comput. , volume =. 1993 , url =. doi:10.1142/S0218196793000123 , timestamp =

    work page doi:10.1142/s0218196793000123 1993

  19. [19]

    C. C. Huang and S. S. Yu , title =. Discret. Math. , volume =. 2008 , doi =

    work page 2008

  20. [20]

    A powerful abelian square-free substitution over 4 letters , journal =

    Veikko Ker. A powerful abelian square-free substitution over 4 letters , journal =. 2009 , doi =

    work page 2009

  21. [21]

    Space-Efficient Online Computation of String Net Occurrences , booktitle =

    Takuya Mieno and Shunsuke Inenaga , editor =. Space-Efficient Online Computation of String Net Occurrences , booktitle =. 2025 , doi =

    work page 2025

  22. [22]

    Algorithmica , volume =

    Takuya Mieno and Yuta Fujishige and Yuto Nakashima and Shunsuke Inenaga and Hideo Bannai and Masayuki Takeda , title =. Algorithmica , volume =. 2022 , doi =

    work page 2022

  23. [23]

    Smyth , title =

    Lucian Ilie and William F. Smyth , title =. Fundam. Informaticae , volume =. 2011 , doi =

    work page 2011

  24. [24]

    Tight Bounds on the Maximum Number of Shortest Unique Substrings , booktitle =

    Takuya Mieno and Shunsuke Inenaga and Hideo Bannai and Masayuki Takeda , editor =. Tight Bounds on the Maximum Number of Shortest Unique Substrings , booktitle =. 2017 , doi =

    work page 2017

  25. [25]

    Shortest Unique Substring Queries on Run-Length Encoded Strings , booktitle =

    Takuya Mieno and Shunsuke Inenaga and Hideo Bannai and Masayuki Takeda , editor =. Shortest Unique Substring Queries on Run-Length Encoded Strings , booktitle =. 2016 , doi =

    work page 2016

  26. [26]

    Faster Computation of

    Enno Ohlebusch and Thomas B. Faster Computation of. String Processing and Information Retrieval - 31st International Symposium,. 2024 , doi =

    work page 2024

  27. [27]

    CoRR , year =

    Shunsuke Inenaga , title =. CoRR , year =

    work page

  28. [28]

    Online Computation of String Net Frequency , booktitle =

    Peaker Guo and Seeun William Umboh and Anthony Wirth and Justin Zobel , editor =. Online Computation of String Net Frequency , booktitle =. 2024 , doi =

    work page 2024

  29. [29]

    Exploiting New Properties of String Net Frequency for Efficient Computation , booktitle =

    Peaker Guo and Patrick Eades and Anthony Wirth and Justin Zobel , editor =. Exploiting New Properties of String Net Frequency for Efficient Computation , booktitle =. 2024 , doi =

    work page 2024

  30. [30]

    Net Occurrences in

    Peaker Guo and Kaisei Kishi , editor =. Net Occurrences in. 36th Annual Symposium on Combinatorial Pattern Matching,. 2025 , doi =

    work page 2025

  31. [31]

    Aho and Margaret J

    Alfred V. Aho and Margaret J. Corasick , title =. Commun. 1975 , doi =

    work page 1975

  32. [32]

    2010 , isbn =

    Jean Berstel and Dominique Perrin and Christophe Reutenauer , title =. 2010 , isbn =

    work page 2010

  33. [33]

    and Salomaa, A

    Rozenberg, G. and Salomaa, A. The Mathematical Theory of L Systems. Advances in Information Systems Science: Volume 6. 1976. doi:10.1007/978-1-4615-8249-6_4

    work page doi:10.1007/978-1-4615-8249-6_4 1976

  34. [34]

    2025 , issn =

    Repetitiveness measures based on string morphisms , journal =. 2025 , issn =. doi:https://doi.org/10.1016/j.tcs.2025.115259 , author =

    work page doi:10.1016/j.tcs.2025.115259 2025

  35. [35]

    R-enum Revisited: Speedup and Extension for Context-Sensitive Repeats and Net Frequencies , booktitle =

    Kotaro Kimura and Tomohiro I , editor =. R-enum Revisited: Speedup and Extension for Context-Sensitive Repeats and Net Frequencies , booktitle =. 2026 , doi =

    work page 2026

  36. [36]

    A Characterization of

    Jean Berstel and Patrice S. A Characterization of. Mathematical Foundations of Computer Science 1993, 18th International Symposium, MFCS'93, Gdansk, Poland, August 30 - September 3, 1993, Proceedings , series =. 1993 , doi =

    work page 1993