The DOI matches its Crossref record; 8 of the 8 references it cites were found in a registry or an index; none of the 12 sources its claims cite is checked for support yet.
The Lexicographically Least Square-Free Word with a Given Prefix
Open accessAbstract
The lexicographically least square-free infinite word on the alphabet of non-negative integers with a given prefix $p$ is denoted $L(p)$. When $p$ is the empty word, this word was shown by Guay-Paquet and Shallit to be the ruler sequence. For other prefixes, the structure is significantly more complicated. In this paper, we show that $L(p)$ reflects the structure of the ruler sequence for several words $p$. We provide morphisms that generate $L(n)$ for letters $n=1$ and $n\geq3$, and $L(p)$ for most families of two-letter words $p$.
Overview
CoChat Summary
TL;DR
The paper studies the lexicographically least square-free infinite word \(L(p)\) on \(\mathbb N\) with a given prefix \(p\), showing that for several prefixes its structure reduces to the ruler sequence via explicit morphisms. It proves \(L(1)=Y_1\alpha(L(\varepsilon))\) and, for every \(n\ge 3\), \(L(n)=Y_n\rho(\alpha(L(\varepsilon)))\), with \(Y_1\) of length 5177.
Key findings
- For \(L(1)\), there is a morphism \(\alpha\) and a word \(Y_1\) of length 5177 such that \(L(1)=Y_1\alpha(L(\varepsilon))\). For each \(n\ge 3\), there is a finite word \(Y_n\) such that \(L(n)=Y_n\rho(\alpha(L(\varepsilon)))\).
- The morphism \(\alpha\) is \(L\)-commuting over nonempty even-grounded square-free words, and \(\alpha(L(\varepsilon))=01020301201020120210120102012023\cdots\) (OEIS A356676).
- For all letters \(n\), \(L(nn)=nL(n)\); and for all \(n_1\ge 3\), \(n_2\ge 3\), \(L(n_1n_2)=n_1L(n_2)\).
- The paper also gives \(L(012)=01201\lim_{n\to\infty}\rho^{-1}(\alpha(n))\), and shows that for every finite square-free word \(w\), there exists a prefix \(p=x_m\) that generates \(x_mw\).
Methods
- Theoretical combinatorics on words: morphisms, square-free words, chunk decompositions, irreducibility of suffixes, and lexicographic minimality are used to prove structural theorems.
- The main proof tool is Theorem 5, a chunk-decomposition criterion for showing a letter-injective morphism is square-free over a family of words; the morphisms \(\psi_1,\psi_2,\alpha\) are proved square-free over grounded words.
- Finite computations verify square-freeness and irreducibility for specific finite words; the paper cites the Main-Lorentz algorithm for square recognition and a greedy algorithm for computing prefixes of \(L(w)\).
Limitations
- The paper states that it does not have conjectures for the structures of \(L(1n)\) when \(n>1\) and \(L(2n)\) when \(n\notin\{0,2\}\); the structure of \(L(2)\) is only conjectured, namely \(L(2)=2\gamma(L(\varepsilon))\) for a morphism \(\gamma\).
- Several proofs rely on computational verification of finite words, including large constants such as \(Y_1\) of length 5177, \(A\) of length 13747, and the morphism \(\alpha\) with constants \(E,F,G\); the text notes the proofs are “fairly technical.”
- Evident from the text: the results cover only words on \(\mathbb N\) and specific prefix families, not a general classification of all \(L(p)\).
Model-written summary. Check it against the paper before relying on it.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
0 Valid · 1 Not valid · 12 Not checked · 71 Own results and interpretations
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Theorem 2. For each n ⩾ 3 , there exists a finite word Y n such that L ( n ) = Y n ρ ( α ( L ( ε ))) , where α is the morphism in Theorem 1.”
plainstates an association- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Lemma 9. Let w be a grounded square-free word. Then for ℓ ⩾ 0 , every occurrence of ψ 1 ( ℓ ) in ψ 1 ( w ) is a ℓ -chunk.”
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
In the paper
“Hence, by Remark 15 we see that P 2 ( n ) has T ( n -1) = P 0 ( n -1) P 1 ( n -1) P 2 ( n -1) as a suffix.”
What the sources say
- Not matchedcites Remark 15
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Not matched
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“The ruler morphism is not L -commuting over the set of all words on N .”
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: unclear — It is unclear whether the paper’s conclusions depend on it.
- Based: unclear — It is unclear why the paper says it holds.
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Lemma 22. For 0 ⩽ k ⩽ n , k +2 is irreducible at the end of ψ 2 ( nR k [: -1])( k +2) .”
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
67 more claims
Create a free account to see all 84 claims and to verify the 3 references still open.
- It may state two separate claims as one. 7
- Probably not a substantial claim. 6
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
Each contradiction between two passages listed here was confirmed by an independent check.
Rated minor: it would not touch a result — a value no result rests on, a p-value that stays on the same side of the significance level, or a conflict that is clerical, resolved elsewhere in the paper, or outside its own findings.
In the paper
§ 4.1.1 Condition 1: α is square-free over grounded words · p. 22
“Lemma 29. Let n > k > 0 . Then α ( n ) and α ( k ) end with different letters and neither is a prefix of the other.”
§ 4.1.1 Condition 1: α is square-free over grounded words · p. 25
“Since α ( n ) is a prefix of α ( n +1), all α ( n ) for n ⩾ 3 have the same first 13029 letters.”
Rated minor: it would not touch a result — a value no result rests on, a p-value that stays on the same side of the significance level, or a conflict that is clerical, resolved elsewhere in the paper, or outside its own findings.
In the paper
§ 6 Inducing factors · p. 40
“Lemma 60. Let w be a finite square-free word, and let φ w be the morphism defined on the alphabet { 0 , 1 , . . . , m } by φ w ( k ) = r k V k for letters k .”
§ 6 Inducing factors · p. 39
“Let m ( w ) be the total number of square-free restrictions of w , and relabel the square-free restrictions in the lexicographic order as r 0 ( w ) , . . . , r m -1 ( w ), this is called the restriction sequence of w .”
Rated minor: it would not touch a result — a value no result rests on, a p-value that stays on the same side of the significance level, or a conflict that is clerical, resolved elsewhere in the paper, or outside its own findings.
In the paper
§ 6 Inducing factors · p. 39
“In other words, the restriction sequence is the collection of all square-free words that are not longer than w , and are lexicographically less than w .”
§ 6 Inducing factors · p. 39
“Example. For the word w = 2021, we have <!-- formula-not-decoded --> Taking only the square-free r j,k and sorting them lexicographically, we obtain that the restriction sequence of w is r 0 = 0, r 1 = 1, r 2 = 201.”
Citations
Cites
The On-Line Encyclopedia of Integer Sequences
Sloane, N. J. A. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-73086-6_12 · Cited by 3,225
An Algorithm to Test if a Given Circular HDOL-Language Avoids a Pattern.
Cassaigne, J. (1994) · Cited by 32
Linear Time Recognition of Squarefree Strings
Main, M. G., & Lorentz, R. J. (1985) · Combinatorial Algorithms on Words · doi:10.1007/978-3-642-82456-2_18 · Cited by 21
Extremal Infinite Overlap-Free Binary Words
Allouche, J.-P., Currie, J., & Shallit, J. (1998) · The Electronic Journal of Combinatorics · doi:10.37236/1365 · Cited by 17
Avoiding squares and overlaps over the natural numbers
Guay-Paquet, M., & Shallit, J. (2009) · Discrete Mathematics · doi:10.1016/j.disc.2009.06.004 · Cited by 13
Avoiding 3/2-powers over the natural numbers
Rowland, E., & Shallit, J. (2012) · Discrete Mathematics · doi:10.1016/j.disc.2011.12.019 · Cited by 7
Self-citationAvoiding Fractional Powers over the Natural Numbers
Pudwell, L., & Rowland, E. (2018) · The Electronic Journal of Combinatorics · doi:10.37236/6678 · Cited by 4
Self-citationAvoiding 5/4-Powers on the Alphabet of Nonnegative Integers
Rowland, E., & Stipulanti, M. (2020) · The Electronic Journal of Combinatorics · doi:10.37236/9581 · Cited by 3
Self-citation
Research works printed but not linked: 1
- [1][1] J.-P. Allouche, A short walk across combinatorics of words, Da Pitagora a Sch¨ utzenberger Symposium (2018), University of Calabria, in Cosenza and Crotone. http://www-igm.univ-mlv.fr/ ~ berstel/Colloque-Pitagore/ word-survey-march2020.pdf . -
Cited by
Still being checked.
Metadata
- Authors
- Berera, S., Gómez-Colunga, A., Lakerdas-Gayle, J., López, J., Matin, M., Roebuck, D., Rowland, E., Scully, N., & Whidden, J.
- Affiliations
- University of Edinburgh (GB)
- Pennsylvania State University (US)
- University of Waterloo (CA)
- Tulane University (US)
- Delft University of Technology (NL)
- University of St Andrews (GB)
- Hofstra University (US)
- Yale University (US)
- Vassar College (US)
- ORCID
- Rowland, Eric
- Venue
- The Electronic Journal of Combinatorics
- Published
- 2023-07-28
- Volume
- 30
- Issue
- 3
- ISSN
- 1077-8926 (ISSN-L)
- OpenAlex
- W4385360076
- Cited by
- 0
- References
- 8
- FWCI
- 0.00
- Type
- journal article
- Language
- en
- Open access
- diamond
- dx.doi.org
- Licence
- cc-by
- Locations
- The Electronic Journal of Combinatorics (publishedVersion, cc-by)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- National Science Foundation (2113535)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
- Physical Sciences › Mathematics › Discrete Mathematics and Combinatorics › Advanced Combinatorial Mathematics
- Physical Sciences › Mathematics › Theoretical Computer Science › Algorithms and Data Compression
- Keywords
- square-free words, morphisms, infinite words, combinatorics on words
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
A language model drew the claims from the paper on 2026-11-14, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).
A second model labelled each claim on 2026-11-14 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: The Lexicographically Least Square-Free Word with a Given Prefix. https://app.cochat.ai/papers/10.37236/11659
- The paper
- Berera, S., Gómez-Colunga, A., Lakerdas-Gayle, J., López, J., Matin, M., Roebuck, D., Rowland, E., Scully, N., & Whidden, J. (2023). The Lexicographically Least Square-Free Word with a Given Prefix. The Electronic Journal of Combinatorics. https://doi.org/10.37236/11659
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.
