ω-Lyndon words
Pith reviewed 2026-05-25 11:26 UTC · model grok-4.3
The pith
Every infinite word factors uniquely into a non-increasing product of ω-Lyndon words.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
Every infinite word may be written uniquely as a non-increasing product of ω-Lyndon words, where an infinite word x is ω-Lyndon if x is smaller than each of its proper suffixes and a finite word w is ω-Lyndon if w^ω is smaller than v^ω for each proper suffix v of w.
What carries the argument
The ω-Lyndon word (defined via the given order on infinite words or their powers), which serves as the indivisible factor in the unique non-increasing product decomposition.
If this is right
- Every infinite word possesses at least one factorization into ω-Lyndon words.
- The factorization is always unique.
- The result holds for any total order obeying the stated compatibility condition with infinite powers.
- Finite ω-Lyndon words are precisely those whose infinite repetitions are minimal among the repetitions of their suffixes.
Where Pith is reading between the lines
- The factorization might support efficient algorithms analogous to those already known for classical Lyndon words.
- It could interact with existing notions of periodicity or repetition thresholds for infinite words.
- Similar decompositions might be definable for bi-infinite words, though the paper does not pursue this.
Load-bearing premise
The total order on infinite words must satisfy that if one finite prefix raised to infinite power is smaller than another, then all infinite extensions preserve that inequality.
What would settle it
An explicit infinite word over a two-letter alphabet that admits two different non-increasing factorizations into ω-Lyndon words, or an infinite word with no such factorization at all.
read the original abstract
Let $\A$ be a finite non-empty set and $\preceq $ a total order on $\A^\nats$ verifying the following lexicographic like condition: For each $n\in \nats$ and $u, v\in \A^n,$ if $u^\omega \prec v^\omega$ then $ux\prec vy$ for all $x, y \in \A^\nats.$ A word $x\in \A^\nats$ is called $\omega$-Lyndon if $x\prec y$ for each proper suffix $y$ of $x.$ A finite word $w\in \A^+$ is called $\omega$-Lyndon if $w^\omega \prec v^\omega$ for each proper suffix $v$ of $w.$ In this note we prove that every infinite word may be written uniquely as a non-increasing product of $\omega$-Lyndon words.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript defines ω-Lyndon words on A^ℕ (infinite words smaller than all proper suffixes) and on A^+ (finite words w where w^ω is smaller than v^ω for proper suffixes v), under a total order ≼ on A^ℕ satisfying the stated compatibility condition (if u^ω ≺ v^ω then ux ≺ vy for all x,y). It proves that every infinite word factors uniquely as a non-increasing product of such ω-Lyndon words.
Significance. If the result holds, the paper supplies an explicit conditional generalization of the classical Lyndon factorization theorem to infinite words. The upfront statement of the order condition as a premise for consistency, the two-part definition, and the uniqueness claim are clear strengths; the result is falsifiable via the given order hypothesis.
major comments (1)
- Abstract (central claim): the asserted proof of unique non-increasing factorization relies on the order condition for both consistency of the ω-Lyndon definitions and the uniqueness argument, but the derivation steps that invoke the condition to establish uniqueness are not visible, leaving a verification gap for the load-bearing claim.
Simulated Author's Rebuttal
We thank the referee for identifying a potential verification gap in the uniqueness argument. We address the single major comment below and will revise the manuscript accordingly to improve clarity.
read point-by-point responses
-
Referee: [—] Abstract (central claim): the asserted proof of unique non-increasing factorization relies on the order condition for both consistency of the ω-Lyndon definitions and the uniqueness argument, but the derivation steps that invoke the condition to establish uniqueness are not visible, leaving a verification gap for the load-bearing claim.
Authors: The order condition is invoked at two key points in the uniqueness proof: first in the proof of Lemma 3.3 (to show that if a factorization is not non-increasing then a suffix comparison contradicts the ω-Lyndon property via the given lexicographic-like hypothesis), and second in the final paragraph of Theorem 3.4 (to rule out alternative factorizations by ensuring that any reordering would violate the total order compatibility). We agree that these invocations are not signposted explicitly enough for a reader to trace them without re-deriving the lemmas. We will revise the manuscript by adding parenthetical references to the order condition at each invocation and by inserting a short paragraph immediately after the statement of Theorem 3.4 that isolates the two places where the hypothesis is essential. revision: yes
Circularity Check
No significant circularity
full rationale
The paper states an explicit compatibility condition on the total order ≼ at the outset, then defines ω-Lyndon words (both infinite and finite) directly from that order and the standard suffix relation. The central theorem asserts unique non-increasing factorization of any infinite word under precisely this hypothesis. No parameters are fitted, no result is renamed as a prediction, and no load-bearing step reduces to a self-citation or to the target statement by construction. The derivation chain is therefore self-contained against the stated assumptions.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption The total order ≼ on A^ℕ satisfies: for each n and u,v in A^n, if u^ω ≺ v^ω then ux ≺ vy for all x,y in A^ℕ.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.