New Results on Nyldon Words and Nyldon-like Sets

Swapnil Garg

REVIEW 3 major objections 4 minor 19 references

New Results on Nyldon Words and Nyldon-like Sets

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Nyldon words of each fixed length form a circular code, and high powers of a primitive word factor into almost only its Nyldon conjugate — resolving two open questions.

desk verdict A genuinely new contribution answering two open problems, with the central claims plausible but the proof of Lemma 3.5 needing careful referee attention. read the letter →

arxiv 1908.04056 v3 pith:S4VJH45X submitted 2019-08-12 math.CO

Swapnil Garg This is my paper · ORCID

classification math.CO MSC 68R15

keywords NyldonwordsLyndoncircularcodeHallsetLazarduniquefactorizationcombinatoricsonpowersof

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper establishes two previously open properties of Nyldon words, a recursive analogue of Lyndon words in which factorizations must be nondecreasing instead of nonincreasing. First, Nyldon words of any fixed length form a circular code: a circular arrangement of such words can be cut into Nyldon factors in only one way. Second, for any primitive word $w$ with Nyldon conjugate $n$, sufficiently high powers $w^k$ have a Nyldon factorization that is a bounded prefix, many consecutive copies of $n$, and a bounded suffix, with at most $\lfloor\log_2|w|\rfloor+1$ exceptional factors. Both results are proved for a wider class of Hall sets the paper calls Nyldon-like sets, and the proof supplies a new route to unique factorization. The engine is a block-contraction algorithm that provably never splits a block boundary in any later factorization.

What carries the argument

The load-bearing mechanism is the block-contraction algorithm, a rewriting procedure on circular sequences of blocks. Starting from the letters of a primitive word, it repeatedly merges an adjacent pair $u_{k-1},u_k$ when $u_{k-1}\succ u_k$, and if the first block is smallest it is moved to the end; the process terminates in a single $G$-word, the unique $G$-word conjugate. The crucial lemma (Lemma 3.5) is block preservation: after contracting $u_{k-1}$ and $u_k$, every $G$-factorization of every word formed from a subset of the remaining blocks in any order still respects the new block boundary. This lemma is what turns the algorithm into a proof device: it yields the unique conjugate, the unique factorization, and the circular-code theorem, because the first length-$\ell$ block to form in the algorithm must be one of the original length-$\ell$ $H$-words.

What would settle it

Run the contraction algorithm on a Nyldon-like set and contract a pair $u_{k-1},u_k$ with $u_{k-1}\succ u_k$; then look for a $G$-factorization of some concatenation of the remaining blocks, in any order, that splits $u_{k-1}u_k$. Finding one would refute Lemma 3.5. For the circular-code claim, it suffices to find two distinct sequences of Nyldon words of the same fixed length $\ell$ whose concatenations are cyclic shifts of each other; an exhaustive search over binary alphabets at small $\ell$ would decide this.

Watch

Extended reading notes

Core claim

The central claim, stated for a right Hall set $H$, is that the $H$-words of any fixed length $\ell$ form a circular code; since Nyldon words form a right Hall set, this resolves the open question whether Nyldon words of a fixed length form a circular code. The paper also proves that for a primitive word $w$ with Nyldon conjugate $n$, the power $w^k$, for $k$ large enough, has a Nyldon factorization containing at least $k-(\lfloor\log_2|w|\rfloor+1)$ consecutive factors equal to $n$. These statements are corollaries of a block-contraction algorithm developed for any Nyldon-like set $(G,\prec)$, a set generated recursively exactly like Nyldon words but with an arbitrary total order and the extra condition that if $f,g,fg\in G$ then $f\prec fg$. Along the way the paper proves unique $G$-factorization for every Nyldon-like set, shows that the known Nyldon-factorization algorithm runs in linear time, determines the exact step at which the Lazard procedure has already generated all Nyldon words up to a given length, and proves a Lyndon-word characterization from the recursive definition alone.

Load-bearing premise

The argument stands on Lemma 3.5, the claim that after two adjacent blocks are contracted, every factorization of every word made from the remaining blocks in any order still respects the new block; if that block-preservation property ever fails, the unique-conjugate and circular-code theorems collapse.

Editorial extensions

If this is right

Any circular word has at most one decoding into Nyldon blocks of a fixed length, so a circle can be read unambiguously once the block length is fixed.
For any primitive word $w$, the Nyldon factorization of $w^k$ is eventually almost constant: all but $\lfloor\log_2|w|\rfloor+1$ factors are the Nyldon conjugate of $w$.
Every Nyldon-like set inherits the circular-code and power-factorization properties, so these phenomena are not tied to lexicographic order but to the Hall-set structure.
The known algorithm computes Nyldon factorizations in linear time, matching the classical Lyndon-factorization speed and making large-word factorization practical.
The Lazard procedure generates all Nyldon words up to length $\ell$ long before it terminates, and the number of Nyldon words lexicographically beyond the finishing word is counted exactly.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Beyond the paper, the fixed-length circular-code result suggests trying to assemble a code from Nyldon words of varying lengths by length-blocking, but the paper does not address mixed lengths.
The logarithmic bound $K\le\lfloor\log_2|w|\rfloor+1$ is probably not tight: the paper reports no example with $K>4$, so an exhaustive search over primitive words could test whether $K$ is at most a small constant.
Because Theorem 4.4 holds for all Nyldon-like sets without lexicographic details, a natural next step is to ask whether every right Hall set satisfies a similar power-factorization bound; the paper leaves this open for other Hall-set classes.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Emil,

The real news here is the circular-code theorem for fixed-length words in any right Hall set (Theorem 4.12) and the logarithmic bound K ≤ floor(log2|w|)+1 for powers (Corollary 4.5). The paper also introduces Nyldon-like sets and gives a linear-time algorithm for Nyldon factorization. Those are genuinely new relative to Charlier–Philibert–Stipulanti, and the paper is honest about what comes from prior work.

What I like: the exposition is clear, the examples are actually illustrative (Table 1, the Lazard procedure table, the power-factorization run in Example 4.7), and deriving Melancon's algorithm from the recursive definition is a nice pedagogical choice. The Kraft–McMillan-based proof that every Lazard set satisfies the equality case is elegant and generalizes beyond Nyldon words.

Soft spots, in order of seriousness. First, Lemma 3.5—the contraction invariant behind Theorem 3.7 (unique G-word conjugate) and Theorem 4.12—is underproved. The lemma asserts a universal property: after merging two adjacent blocks, every G-factorization of every word over the new blocks still preserves all block boundaries. The proof only considers one occurrence of the merged block and does not explicitly handle the situation where the word contains other merged blocks to the left; the factor p in the contradiction is assumed to be composable from the original blocks, but that hasn't been re-established after prior contractions. The hypotheses of Lemma 3.2(2) and Lemma 3.3 are not checked for the contracted block sequence. This is not a demonstrated counterexample, but it is a real gap in the write-up, and the main theorems depend on it.

Second, the infection argument in Theorem 4.4 is a sketch. The eight merge types are plausible, but I couldn't verify every transition, especially the 'quirky' step (Merge 8) and the counting claim that the merge counter grows at least as fast as blocks-left shrinks. Third, the case counts in Propositions 6.6 and 6.7 are asserted with minimal detail. Minor: the 'faster than previously thought' claim lacks a cited baseline, and the simultaneous recursive definition of Nyldon-like sets is assumed consistent without proof.

Overall, the central claims look right, and the paper deserves a serious referee. I'd send it out with a request to check Lemma 3.5 carefully—if that holds, the paper is a solid contribution at the level of JCTA. For a reading group on combinatorics on words, yes; outside that, no.

Referee Report

3 major / 4 minor

Summary. The paper studies Nyldon words, the lexicographic dual of Lyndon words, and introduces a recursive class of 'Nyldon-like sets' that includes them. Its main technical tool is an elementary treatment of Melançon's algorithm: the author proves block-preservation lemmas for a contraction procedure and uses them to give new proofs that every primitive word has a unique G-word conjugate and that G-factorizations are unique. On this basis the paper claims (i) Nyldon words of a fixed length form a circular code (Theorem 4.12), resolving Open Problem 46 from Charlier et al.; (ii) a quantitative form of the power-factorization problem (Theorems 4.4–4.6), with K = floor(log2 |w|)+1 for Nyldon words; (iii) a linear-time algorithm for Nyldon factorization (Section 5); (iv) explicit timing results for the right Lazard procedure (Section 6); and (v) a short proof that a word smaller than all its Lyndon proper suffixes is Lyndon (Section 7). The paper is clearly written and contains detailed worked examples for the algorithms.

Significance. If the proofs can be made rigorous, the paper resolves two explicit open problems from Charlier et al. and provides a genuinely new proof mechanism for a class of Hall sets. The block-preservation viewpoint is attractive, and the claimed logarithmic bound in Theorem 4.6 is specific and falsifiable. The linear-time factorization argument in Section 5 is a clean contribution. However, because the central contraction lemma and the infection argument are not fully proved, the paper currently falls short of the standard needed for a definitive journal version. The underlying claims appear plausible and are within the scope of the manuscript, so the right outcome is a careful revision rather than rejection.

major comments (3)

[Section 3, Lemma 3.5] Lemma 3.5 is the engine of the paper: it justifies every contraction step in Melançon's algorithm and underlies Corollary 3.4, Theorem 3.7, Theorem 3.8, Lemma 4.10, and Theorem 4.12. The proof as written only handles a word in which the newly combined block C = u_{k-1}u_k occurs once. In the contradiction argument, the left G-factor p is assumed to have the form u_{k-i}...u_{k-1}; but the invariant stated in Corollary 3.4 must hold for arbitrary sequences of blocks with arbitrary multiplicities, so p may contain another occurrence of C to its left and need not be a consecutive run of the original blocks. The application of Lemma 3.3 to p is therefore not justified. The proof also does not re-verify, after contraction, the preservation property for substrings of the new block system in the full generality required by the induction in Lemma 3.3 and by Corollary 3.4 for subsequent steps. A complete proof needs a formal induction over the number of occurrences of C or an equivalent invariant, or the paper should explicitly invoke Theorem 3.16 whenever the elementary proof is incomplete. This is not a demonstrated counterexample, but it is a genuine gap in the argument as written.
[Section 4, Theorem 4.4] The infection argument is a sketch rather than a rigorous proof. The state (blocks left, merge counter, condition) is not defined precisely for all stages of the algorithm, and the list of eight merge types is asserted to be exhaustive without proof. In particular, the treatment of the 'unclear' condition and of the 'quirky' step (Merge 8) does not provide a formal invariant that would imply the claimed halving bound; the sentence 'Therefore d is at least f + (m-1-f)/2 >= m/2' does not follow from the displayed transition rules without additional argument. Since Theorem 4.4 is the basis for Corollary 4.5 and Theorem 4.6, this gap is load-bearing for the paper's quantitative claims about factorizing powers of words.
[Section 6, Propositions 6.5–6.7] The Lazard-procedure results are not proved to the same standard as the rest of the paper. The crucial assertion in Proposition 6.5 that the separating word ui is 'the lexicographically largest Nyldon word that can still be affixed to the end of a larger Nyldon word' is not formalized. In Propositions 6.6 and 6.7, the case analyses assume without proof that the listed words are the only non-Nyldon words beginning with ui and that the two cases are exhaustive and disjoint; the displayed counts, for example |A|^3 + |A|^2 + 2|A| + 2 in Proposition 6.6, therefore require a full derivation. These propositions are advertised as new results about the Lazard procedure, so the level of rigor is insufficient as written.

minor comments (4)

[Section 2, Definition 2.5] The phrase 'Whenever we add a word to G, we keep the condition ...' should be made more precise: the paper should state explicitly how the order ≺ is extended to the newly added word and why the recursive definition of G and the order can be carried out simultaneously without introducing inconsistencies.
[Section 5] In the proof that Algorithm 2 runs in linear time, the sentence 'the number of additional lexicographic comparisons is at most the number of times two words combine into a bigger word' should be expanded: each while-loop iteration removes one barrier between factors, so the total number of iterations over the whole run is at most |w|-1.
[Section 4, Theorem 4.6] The assertion 'Clearly n starts with its maximal letter' should be proved or accompanied by a reference; it is not immediate from the recursive definition and is used in the argument that the rightmost n-group has at most |w|/2 blocks when it first becomes infected.
[General] The arXiv text contains several typographical and OCR artifacts, such as split words and repeated 'inﬁnite' in Theorem 6.9; these should be corrected in the final version.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main theorems are derived from the recursive Nyldon-like definition and Melançon's externally proven algorithm, with no fitted parameters or target results used as assumptions.

full rationale

The paper's derivation chain is self-contained relative to its stated definitions and external prior results. Nyldon-like sets are defined constructively in Definition 2.5, and the central machinery—Melançon's contraction algorithm—is proved from that definition in Section 3 (Lemmas 3.2–3.5, Corollary 3.4, Theorems 3.7 and 3.8). The main new results (Theorems 4.4, 4.6, and 4.12) are then derived from the algorithm and from previously published results of Charlier, Philibert, and Stipulanti and of Melançon. Those citations are genuinely external: the authors do not overlap with the present paper, and the cited results (e.g., Lemma 4.1 from [3] and Theorem 3.16 from [14]) are independent parameter-free theorems, not the conclusions being proved. In particular, Theorem 4.12 proves that H-words of fixed length form a circular code by using Lemmas 4.10 and 4.11, which in turn rely on the externally established uniqueness of the H-word conjugate under Melançon's algorithm; there is no step where the circular-code conclusion is assumed or where a quantity is fitted to force the result. Similarly, Theorem 6.9 uses the classical Kraft-McMillan inequality as an external benchmark, and its code property is proved by induction on the Lazard construction rather than imported from the theorem being claimed. No self-definitional, fitted-input, self-citation-load-bearing, uniqueness-imported-from-authors, ansatz-smuggled, or renaming pattern is present. Possible proof-gaps in Lemma 3.5 would be correctness concerns, not circularity, since nothing in the argument reduces to its own conclusion by construction.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces no fitted parameters and no experimentally constrained quantities. Its premises are the standard axioms of ordered alphabets, a cited theorem of Melangon for Hall sets, the Kraft-McMillan theorem, and the coherence of the new Definition 2.5, which is not separately proved.

assumptions (4)

domain assumption The alphabet A is finite and totally ordered with at least two elements.
Used throughout; stated in Section 2.
ad hoc to paper Definition 2.5 of a Nyldon-like set is coherent: the set G and the total order ≺ can be built simultaneously so that a word is added exactly when no nondecreasing factorization into smaller G-words exists, while the condition fg∈G implies f≺fg is maintained.
No consistency or existence proof is given for arbitrary alphabets and initial orders; Nyldon words with the lexicographic order are the one demonstrated instance.
standard math Melancon's algorithm works for any right Hall set, as stated in Theorem 3.16 and cited from Melangon [14].
The paper cites this result and builds on it, though it also proves the needed cases for Nyldon-like sets directly.
standard math The Kraft-McMillan inequality is valid and can be applied to infinite codes.
Used in Theorem 6.9 for the Lazard sets.

how reviews work

0 comments

Cite this review

Pith. "Pith review of New Results on Nyldon Words and Nyldon-like Sets." pith.science (2026). https://pith.science/paper/S4VJH45X

@misc{pith2026190804056,
  author       = {Pith},
  title        = {Pith review of: New Results on Nyldon Words and Nyldon-like Sets},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/S4VJH45X}},
  note         = {Machine review of arXiv:1908.04056}
}

read the original abstract

Grinberg defined Nyldon words as those words which cannot be factorized into a sequence of lexicographically nondecreasing smaller Nyldon words. He was inspired by Lyndon words, defined the same way except with "nondecreasing" replaced by "nonincreasing." Charlier, Philibert, and Stipulanti proved that, like Lyndon words, any word has a unique nondecreasing factorization into Nyldon words. They also show that the Nyldon words form a right Lazard set, and equivalently, a right Hall set. In this paper, we provide a new proof of unique factorization into Nyldon words related to Hall set theory and resolve several questions of Charlier et al. In particular, we prove that Nyldon words of a fixed length form a circular code, we prove a result on factorizing powers of words into Nyldon words, and we investigate the Lazard procedure for generating Nyldon words. We show that these results generalize to a new class of Hall sets, of which Nyldon words are an example, that we name "Nyldon-like sets."

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

[1]

Berstel, D

J. Berstel, D. Perrin, and C. Reutenauer. Codes and Autom ata. Encyclopedia of Mathematics and its Applica- tions, Cambridge University Press , 129, 2010

work page 2010
[2]

Bonizzoni, C

P. Bonizzoni, C. D. Felice, R. Zaccagnino, and R. Zizza. I nverse Lyndon words and inverse Lyndon factorizations of words. Adv. Appl. Math. , 101:281–319, 2018

work page 2018
[3]

Charlier, M

E. Charlier, M. Philibert, and M. Stipulanti. Nyldon wor ds. J. Combin. Theory, Ser. A , 167:60–90, 2019. 22 SW APNIL GARG

work page 2019
[4]

K.-T. Chen, R. H. Fox, and R. C. Lyndon. Free diﬀerential c alculus. IV. The quotient groups of the lower central series. Ann. of Math. , 68(1):81–95, 1958

work page 1958
[5]

J.-P. Duval. Factorizing words over an ordered alphabet . J. Algorithms , 4(4):363–381, 1983

work page 1983
[6]

Fischer and V

J. Fischer and V. Heun. Theoretical and practical improv ements on the RMQ-problem, with applications to LCA and LCE. Proceedings of the 17th Annual Symposium on Combinatorial P attern Matching , pages 36–48, 2006

work page 2006
[7]

Nyldon words

D. Grinberg. “Nyldon words”: understanding a class of wo rds factorizing the free monoid increasingly, 2014. https://mathoverflow.net/questions/187451/

work page 2014
[8]

Kasai, G

T. Kasai, G. Lee, H. Arimura, S. Arikawa, and K. Park. Line ar-time longest-common-preﬁx computation in suﬃx arrays and its applications. Proceedings of the 12th Annual Symposium on Combinatorial P attern Matching, pages 181–192, 2001

work page 2001

Show all 19 references

[9]

Ko and A

P. Ko and A. Srinivas. Linear time construction of suﬃx ar rays. Computer Science Technical Reports, Digital Repository @ Iowa State University , 2002

2002
[10]

L. G. Kraft. A device for quantizing, grouping, and codi ng amplitude-modulated pulses. Master’s thesis, Mas- sachusetts Institute of Technology, 1949

1949
[11]

Lothaire

M. Lothaire. Combinatorics on Words . Cambridge University Press, Cambridge, 1997

1997
[12]

R. C. Lyndon. On Burnside’s problem. Trans. Amer. Math. Soc. , 77:202–215, 1954

1954
[13]

McMillan

B. McMillan. Two inequalities implied by unique deciph erability. IEEE Trans. Inf. Theory , 2(4):115–116, 1956

1956
[14]

Melan¸ con

G. Melan¸ con. Combinatorics of Hall trees and Hall word s. J. Combin. Theory, Ser. A , 59(2):285–308, 1992

1992
[15]

Perrin and C

D. Perrin and C. Reutenauer. Hall sets, Lazard sets and c omma-free codes. Discrete Math. , 341:231–243, 2018

2018
[16]

Reutenauer

C. Reutenauer. Free Lie Algebras. Oxford University Press, 1993

1993
[17]

A. I. Shirshov. Subalgebras of free Lie algebras. Mat. Sb. , 75(2):441–452, 1953

1953
[18]

A. I. Shirshov. On free Lie rings. Mat. Sb. N.S. , 45(87):113–122, 1958

1958
[19]

G. Viennot. Alg` ebres de Lie libres et mono ¨ ıdes libres, volume 691 of Lecture Notes in Mathematics . Springer- Verlag, 1978. Massachusetts Institute of Technology, Cambridge, MA 0213 9, USA Email address : swapnilg@mit.edu

1978

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Berstel, D

J. Berstel, D. Perrin, and C. Reutenauer. Codes and Autom ata. Encyclopedia of Mathematics and its Applica- tions, Cambridge University Press , 129, 2010

work page 2010

[2] [2]

Bonizzoni, C

P. Bonizzoni, C. D. Felice, R. Zaccagnino, and R. Zizza. I nverse Lyndon words and inverse Lyndon factorizations of words. Adv. Appl. Math. , 101:281–319, 2018

work page 2018

[3] [3]

Charlier, M

E. Charlier, M. Philibert, and M. Stipulanti. Nyldon wor ds. J. Combin. Theory, Ser. A , 167:60–90, 2019. 22 SW APNIL GARG

work page 2019

[4] [4]

K.-T. Chen, R. H. Fox, and R. C. Lyndon. Free diﬀerential c alculus. IV. The quotient groups of the lower central series. Ann. of Math. , 68(1):81–95, 1958

work page 1958

[5] [5]

J.-P. Duval. Factorizing words over an ordered alphabet . J. Algorithms , 4(4):363–381, 1983

work page 1983

[6] [6]

Fischer and V

J. Fischer and V. Heun. Theoretical and practical improv ements on the RMQ-problem, with applications to LCA and LCE. Proceedings of the 17th Annual Symposium on Combinatorial P attern Matching , pages 36–48, 2006

work page 2006

[7] [7]

Nyldon words

D. Grinberg. “Nyldon words”: understanding a class of wo rds factorizing the free monoid increasingly, 2014. https://mathoverflow.net/questions/187451/

work page 2014

[8] [8]

Kasai, G

T. Kasai, G. Lee, H. Arimura, S. Arikawa, and K. Park. Line ar-time longest-common-preﬁx computation in suﬃx arrays and its applications. Proceedings of the 12th Annual Symposium on Combinatorial P attern Matching, pages 181–192, 2001

work page 2001