{"id":"8c999bf5-50f8-4d7f-a747-582e7b52a154","arxiv_id":"1908.04056","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Nyldon words of fixed length form a circular code, powers of words admit a Nyldon factorization with a long run of the Nyldon conjugate, and both results extend to the new class of Nyldon-like sets.","lead":"This paper proves new structural results about Nyldon words, ordering-based variants of Lyndon words, including that all Nyldon words of a fixed length form a circular code. It also generalizes the theory to a new class of word sets and settles several open problems posed by Charlier, Philibert, and Stipulanti.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.5's contraction invariant is the load-bearing engine for Theorems 3.7 and 4.12, but its proof only handles one split at a time and never re-establishes the order hypotheses needed after contraction; a finite counterexample check would settle it.","rationale":"The reader identifies Lemma 3.5 as the most fragile load-bearing premise, and I concur: it is the step on which unique conjugates, unique factorization, and the circular-code theorem rest. My concern is slightly more specific than the reader's: the proof as written handles only one split of one combined block and does not close the induction for arbitrary sequences after multiple contractions, nor does it explicitly preserve the order-theoretic hypotheses needed by Corollary 3.4 in later iterations. This is a correctness risk because the paper's main applications depend on the invariant surviving every contraction, not just a single step. I am not claiming the lemma is false; a finite exhaustive check over small binary alphabets would likely reveal a counterexample if one exists and would otherwise provide strong evidence for the step. Since the reader already assigned a conditional verdict and no demonstrated flaw is present, the verdict should remain unchanged: conditional acceptance, pending a careful check of Lemma 3.5's induction.","tokens_in":21221,"tokens_out":17163,"duration_ms":180127,"concrete_test":"Write a program that, for binary Nyldon words up to length 7, enumerates all tuples of blocks satisfying the Corollary 3.4 hypothesis by checking, for every permutation and every G-factorization, that the original block boundaries are preserved. Then form C = u_{k-1}u_k and test the invariant for all words built from the reduced block set, including words with multiple occurrences of C, by recomputing all G-factorizations from the recursive definition. A counterexample would refute Lemma 3.5 and with it Theorems 3.7 and 4.12; if no counterexample appears, the same test on nonstandard Nyldon-like orders and longer lengths would still be needed to justify the unstated induction step.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 3.5 is the engine for Theorem 3.7 (unique G-word conjugate), Theorem 3.8 (unique factorization), and Theorem 4.12 (circular code), so any gap in its proof threatens the paper's central claims. The proof shows that a single occurrence of the combined block C = u_{k-1}u_k is not split by a G-factorization, but the invariant required by Corollary 3.4 and by iterative contraction is universal: every word formed from a subset of the current blocks in any order, with any number of occurrences of C, must preserve all current block boundaries. In the proof, when a factorization splits C, Corollary 3.4 is invoked to force q = u_k, but if the word contains another split C to the left, the factor p may itself begin inside that other combined block, so p is not necessarily composed of original blocks in the way the proof assumes. Moreover, after C is formed, the paper never re-establishes the order-theoretic hypotheses of Lemma 3.2(2) and Lemma 3.3 that Corollary 3.4 requires for subsequent contractions. The claim that the invariant survives contraction is asserted by induction, but the induction step is not written out for arbitrary sequences with repeated combined blocks. This is not a demonstrated counterexample, but it is a genuine gap in the argument as written; if the invariant fails, Theorems 3.7 and 4.12 lose their foundation.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":21516,"tokens_out":20622,"duration_ms":194363,"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":[{"comment":"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":"Section 3, Lemma 3.5"},{"comment":"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":"Section 4, Theorem 4.4"},{"comment":"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.","section":"Section 6, Propositions 6.5–6.7"}],"minor_comments":[{"comment":"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":"Section 2, Definition 2.5"},{"comment":"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":"Section 5"},{"comment":"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.","section":"Section 4, Theorem 4.6"},{"comment":"The arXiv text contains several typographical and OCR artifacts, such as split words and repeated 'infinite' in Theorem 6.9; these should be corrected in the final version.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"The main risk is the gap in Lemma 3.5, on which Theorems 3.7, 3.8, 4.10, and 4.12 depend. Since Nyldon words are already known to form a right Hall set, Theorem 3.16 might repair the Nyldon-specific claims, but the Nyldon-like generalization would then lose its advertised elementary proof. The author should either complete the contraction-invariant proof or clearly separate the results that rely on the external right-Hall-set theorem. I also recommend asking the author to state explicitly which results are new versus reproved from Charlier et al."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Emil,\n\nThe 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.\n\nWhat 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.\n\nSoft 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.\n\nSecond, 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.\n\nOverall, 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.","headline":"A genuinely new contribution answering two open problems, with the central claims plausible but the proof of Lemma 3.5 needing careful referee attention.","tokens_in":22051,"tokens_out":6815,"would_cite":true,"duration_ms":65655,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68R15"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["Nyldon words","Lyndon words","circular code","Hall set","Lazard set","unique factorization","combinatorics on words","powers of words"],"falsifier":"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.","tokens_in":20941,"feed_emoji":"🔁","tokens_out":12152,"duration_ms":120542,"temperature":0.7,"pith_summary":"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.","feed_headline":"Nyldon words of fixed length form a circular code","feed_subtitle":"A block-contraction proof also bounds repeated factors in powers and generalizes to Nyldon-like Hall sets.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Introduces Nyldon words, proves unique factorization, poses the open problems on circular codes and powers, and supplies the factorization algorithm the paper analyzes.","marker":"[3]"},{"why":"Supplies the rewriting algorithm for right Hall sets that the paper's block-contraction procedure specializes and proves for Nyldon-like sets.","marker":"[14]"},{"why":"Gives the Hall-set and Lazard-set framework and the equivalence the paper uses to view Nyldon-like sets as a type of Hall set.","marker":"[19]"},{"why":"Provides the definition of circular code and the Lyndon-word circular-code analogue that the paper extends to Nyldon words.","marker":"[1]"},{"why":"Supplies the Hall-set and free-Lie-algebra context and the worked example of the rewriting algorithm.","marker":"[16]"},{"why":"Gives the linear-time Lyndon-factorization algorithm that Section 5 matches for Nyldon factorization.","marker":"[5]"},{"why":"States the inequality on codeword lengths whose equality case Theorem 6.9 verifies for every Lazard-level set.","marker":"[10, 13]"}],"fun_headline_variants":["Fixed-length Nyldon words are circular codes","Circular code proof for Nyldon words via block contraction","Nyldon-like sets inherit circular code property","Block contraction proves Nyldon fixed-length circular code","Nyldon words of fixed length form circular code"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Fixed-length Nyldon words are circular codes","Circular code proof for Nyldon words via block contraction","Nyldon-like sets inherit circular code property","Block contraction proves Nyldon fixed-length circular code","Nyldon words of fixed length form circular code"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000216,"raw_usage":{"total_tokens":1451,"prompt_tokens":985,"completion_tokens":466,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":601,"completion_tokens_details":{"reasoning_tokens":395}},"tokens_in":601,"tokens_out":466,"duration_ms":5140,"temperature":1.0,"reasoning_tokens":395,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:54:22.476748+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Charlier, M","cited_arxiv_id":null,"evidence_quote":"Introduces Nyldon words, proves unique factorization, poses the open problems on circular codes and powers, and supplies the factorization algorithm the paper analyzes."},{"cited_title":"Melan¸ con","cited_arxiv_id":null,"evidence_quote":"Supplies the rewriting algorithm for right Hall sets that the paper's block-contraction procedure specializes and proves for Nyldon-like sets."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the Hall-set and Lazard-set framework and the equivalence the paper uses to view Nyldon-like sets as a type of Hall set."},{"cited_title":"Berstel, D","cited_arxiv_id":null,"evidence_quote":"Provides the definition of circular code and the Lyndon-word circular-code analogue that the paper extends to Nyldon words."},{"cited_title":"Reutenauer","cited_arxiv_id":null,"evidence_quote":"Supplies the Hall-set and free-Lie-algebra context and the worked example of the rewriting algorithm."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the linear-time Lyndon-factorization algorithm that Section 5 matches for Nyldon factorization."}],"review_version":1}