Pith. sign in

REVIEW 2 major objections 4 minor 34 references

The repetition threshold for binary rich words

T0 review · 2 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 The least possible repetition exponent for infinite binary rich words is $2+\sqrt{2}/2$.

desk verdict The structure theorem is a real contribution, but the final step from Theorem 1 to the claimed repetition threshold skips the entire lower-bound argument. read the letter →

arxiv 1908.03169 v4 pith:3Z534MTV submitted 2019-08-08 math.CO cs.FL

James D. Currie , Lucas Mol , Narad Rampersad This is my paper · ORCID
classification math.COcs.FL MSC 68R15
keywords richwordsrepetitionthresholdcriticalexponentpalindromeSturmianRotecombinatoricsonmorphic
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

Infinite binary rich words—words in which every prefix contains as many distinct palindromes as its length—cannot avoid repetitions entirely, so the meaningful question is how little repetition they can force. This paper proves that the answer is exactly $2+\sqrt{2}/2 \approx 2.707$: every infinite binary rich word contains a repetition of exponent at least that large, and there is an explicit word that attains it. The proof establishes a structure theorem for rich words that avoid $14/5$-powers, showing that every such word has suffixes built by iterating a fixed ternary-to-binary morphism. It then computes the critical exponent of the two extremal words produced by that construction, confirming the conjectured threshold.

What carries the argument

The argument rests on a structure theorem and a morphism calculus. The theorem classifies infinite binary rich words that avoid $14/5$-powers: every such word has, for every $n$, a suffix of the form $f(h^n(w_n))$ or $f(g(h^n(w_n)))$, where $f$, $g$, and $h$ are fixed substitutions (for example, $f$ maps $0 \mapsto 0$, $1 \mapsto 01$, $2 \mapsto 011$) and $w_n$ is a cube-free rich ternary word containing a $0$. The calculus identifies the two extremal words $f(h^\omega(0))$ and $f(g(h^\omega(0)))$ as complementary symmetric Rote words, meaning their first-difference sequences are Sturmian; this allows the exponent of their longest repetitions to be computed from the continued fraction of a slope, yielding the value $2+\sqrt{2}/2$.

What would settle it

Exhibit an infinite binary rich word whose critical exponent is strictly below $2+\sqrt{2}/2$, or find a cube-free rich ternary word $w$ containing a $0$ for which $f(h^n(w))$ or $f(g(h^n(w)))$ has critical exponent below $2+\sqrt{2}/2$; the paper's claim predicts neither exists.

Watch

Extended reading notes

Core claim

The paper's central claim is that the repetition threshold for binary rich words is $2+\sqrt{2}/2$. The main structural result, Theorem 1, states that if an infinite binary rich word avoids repetitions of exponent at least $14/5$, then for every $n \ge 1$ some suffix has the form $f(h^n(w_n))$ or $f(g(h^n(w_n)))$, where $w_n$ is a cube-free rich word over $\{0,1,2\}$ containing a $0$, and $f$, $g$, and $h$ are explicit morphisms. The paper then proves that the two canonical words $f(h^\omega(0))$ and $f(g(h^\omega(0)))$, both complementary symmetric Rote words, have critical exponent exactly $2+\sqrt{2}/2$; from this and Theorem 1 it concludes that no rich binary word can have a smaller critical exponent, so the threshold is exactly $2+\sqrt{2}/2$.

Load-bearing premise

The final inference from the structure theorem to the lower bound relies on the unstated premise that every suffix of the allowed forms attains critical exponent at least $2+\sqrt{2}/2$; the paper computes the critical exponent explicitly only for its two constructed extremal words, not for all words satisfying the structure theorem.

Editorial extensions

If this is right

  • The binary repetition threshold for rich words is now known exactly: $2+\sqrt{2}/2$ is both a lower bound and an attained value.
  • Every infinite binary rich word contains arbitrarily long factors with exponent at least $2+\sqrt{2}/2$, so near-threshold rich words are necessarily repetition-heavy.
  • The structure theorem gives a normal form for $14/5$-free binary rich words, analogous to classical structure theorems for overlap-free words, which may aid future algorithmic studies of these words.
  • With the binary case resolved, the same threshold question remains open for alphabets of size three and larger, where no conjectured value is currently available.

Reading between the lines

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

  • If the unstated monotonicity is correct, then every $14/5$-free binary rich word should have critical exponent exactly $2+\sqrt{2}/2$; the paper exhibits two examples but does not rule out other words with the same value.
  • The morphism calculus suggests that the family of $14/5$-free binary rich words may be generated by iterating $h$ on arbitrary rich seeds, which would make the class amenable to enumeration and could yield upper bounds for larger alphabets through continued fractions of associated slopes.
  • A direct computational test of the structure theorem would be to generate all cube-free rich ternary words containing a $0$, apply the morphisms $f$ and $f\circ g$, and check whether any resulting word has critical exponent below $2+\sqrt{2}/2$; the paper's argument predicts none.
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.

Referee Report

2 major / 4 minor

Summary. The paper studies the repetition threshold for infinite binary rich words. It introduces three morphisms f, g, h on a ternary alphabet and proves a structure theorem (Theorem 1): every infinite binary rich word that avoids 14/5-powers has, for each n ≥ 1, a suffix of the form f(h^n(w_n)) or f(g(h^n(w_n))) for some infinite ternary word w_n. The proof combines a forbidden-factor analysis with induction, using several computer-assisted backtracking checks. In Section 3 the authors show that the two words f(h^ω(0)) and f(g(h^ω(0))) are rich and have critical exponent 2+√2/2, using a connection to complementary symmetric Rote words and Sturmian words. From Theorem 1 and these two examples they conclude (Theorem 2) that the repetition threshold for binary rich words is exactly 2+√2/2, resolving a conjecture of Baranwal and Shallit.

Significance. If the conclusion is fully established, the paper resolves the binary case of Vesti's problem and confirms the Baranwal–Shallit conjecture. The structure theorem is a strong and interesting dichotomy, and the use of Sturmian/Rote theory to compute critical exponents of the extremal words is elegant and mostly self-contained. However, the final deduction of Theorem 2 from Theorem 1 is missing a load-bearing lower-bound argument. The paper also depends on several undocumented backtracking computations. These issues do not undermine the plausibility of the main result, but they prevent the paper, in its current form, from being a complete proof.

major comments (2)
  1. [Section 3, final paragraph] The sentence "Since f(h^ω(0)) and f(g(h^ω(0))) both have critical exponent 2+√2/2, Theorem 2 now follows immediately from Theorem 1" is the entire lower-bound half of Theorem 2, and it does not follow as written. To prove RRT(2)=2+√2/2 one must show not only that some binary rich word attains this exponent, but also that every infinite binary rich word has critical exponent at least 2+√2/2. For the lower bound, suppose w is a rich word with critical exponent < 2+√2/2; then w is 14/5-free, so Theorem 1 applies and gives, for each n ≥ 1, a suffix of the form f(h^n(w_n)) or f(g(h^n(w_n))). The paper computes the critical exponent only for the two particular words obtained when w_n is h^ω(0). No lemma states or proves that an arbitrary rich cube-free w_n (as guaranteed by Lemma 7) yields a word f(h^n(w_n)) or f(g(h^n(w_n))) with critical exponent at least 2+√2/2. The missing statement is precisely a monotonicity property: for all n ≥ 1 and all rich cube-free w, if f(h^n(w)) or f(g(h^n(w))) is 14/5-free, then its critical exponent is at least 2+√2/2. Without this lemma, Theorem 1 is compatible with the existence of rich 14/5-free words of smaller critical exponent, and Theorem 2 is not proved.
  2. [Section 2, Lemma 12 and Observation 3/Table 1] The exclusion of the factor 212 in Lemma 12 rests on an unspecified backtracking computation: "Backtracking by computer ... one finds that the longest right extension of 212 has length 21." The paper does not provide the code, the actual extension, or a certificate that would allow the reader to verify this finite check. The same is true for Observation 3 and for the entries of Table 1, where only the lengths of the longest right extensions are reported, not the extensions themselves. These checks are load-bearing for the induction in Theorem 1, since they rule out factors that drive the structure theorem. To make the proof reproducible, please include the program (or machine-readable certificates) and state the exact search parameters, including whether the search is over 14/5-free or cube-free extensions and how the stopping condition is certified.
minor comments (4)
  1. [Theorem 1 statement] The phrase "For everyn ≥ 1" should read "For every n ≥ 1".
  2. [Theorem 17, after Lemma 16] The text says "the number of 1's in v_{i+1} ... v_{i+ℓ−1} v_ℓ" but Lemma 16 gives the number of 1's in v_i ... v_{i+ℓ−1}; the index appears to be shifted and should be corrected.
  3. [Lemma 16 and Theorem 17] The symbol y is used both for the infinite word Δ(x) in Lemma 16 and for the prefix y' in the repetition y^e y'; this is confusing. Consider renaming the prefix, for example to p or z'.
  4. [Theorem 17, non-primitive z case] The sentence "Since the critical exponent of c_α is 3+√2, the exponent of z cannot be greater than 2" is compressed. Spelling out that z = r^m with m=2 and e=2 would make the argument easier to follow and would remove an unnecessary hurdle for the reader.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main derivation is self-contained, though the final inference from Theorem 1 to Theorem 2 contains a logical gap that is not a circularity.

full rationale

The paper's derivation chain is not circular. The structure theorem (Theorem 1) is proved from scratch using the morphisms f, g, h, finite backtracking checks (Observation 3, Table 1), and lemmas about richness and cube-freeness; it does not presuppose the repetition threshold. The critical exponent computation for u = f(g(h^ω(0))) in Theorem 17 is derived independently from Sturmian word theory, the Rote-word characterization, and cited external results on repetitions in Sturmian words; it is not a fitted parameter or a restatement of the conjecture. The use of Baranwal and Shallit's word f(h^ω(0)) is an external construction, not a self-citation, and the paper independently verifies richness of both words via complementary symmetric Rote words. No step reduces by construction to its own inputs, no fitted quantity is renamed as a prediction, and no load-bearing uniqueness theorem is imported from the authors' prior work. The only substantive concern is logical rather than circular: the final sentence 'Since f(h^ω(0)) and f(g(h^ω(0))) both have critical exponent 2+√2/2, Theorem 2 now follows immediately from Theorem 1' omits the lower-bound half of the repetition-threshold proof, namely showing that every infinite binary rich word covered by the structure theorem has critical exponent at least 2+√2/2. That is an omitted proof or a gap in the written argument, but it is not an equivalence between the theorem and its assumptions. Accordingly, the circularity score is 0.

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

The proof relies on several established results about rich words and Sturmian words, listed here, plus three computer-assisted backtracking assertions that are stated without code. No free parameters are fitted; the 14/5 threshold is a definitional choice, not a parameter fitted to data.

assumptions (6)
  • domain assumption A word is rich if and only if every nonempty prefix has a palindromic suffix that occurs only once.
    Used in Lemma 5 to prove that the morphisms f, g, h preserve non-richness. From Glen et al. [15].
  • domain assumption Complementary symmetric Rote words are rich.
    Used in Theorem 15 to conclude f(h^omega(0)) and f(g(h^omega(0))) are rich. From Blondin Masse et al. [5, Theorem 25].
  • domain assumption The characteristic Sturmian word with slope (3-sqrt(2))/7 has critical exponent 3+sqrt(2).
    Used in Theorem 17 to bound exponents in the Sturmian word c_alpha. From Peltomaki [26, Proposition 4.6.12].
  • domain assumption Repetitions in Sturmian words are characterized by standard and semi-standard words.
    Used in Theorem 17 to restrict the form of z. From Damanik-Lenz [10] and Peltomaki [25, Corollary 4.6].
  • domain assumption The longest factor of c_alpha with period q_{k-2}+q_{k-1} has length 2(q_{k-2}+q_{k-1})+q_{k-1}-2.
    Used in Theorem 17 to bound the exponent E_k. From Justin-Pirillo [17, Theorem 4(i)].
  • ad hoc to paper The backtracking computations confirming Observation 3, Table 1, and Lemma 12's claim about the right-extension of 212 are correct.
    These computer checks are asserted without code or certificates. The constant 14/5 is chosen so that these searches terminate, which is tailored to the paper's needs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The repetition threshold for binary rich words." pith.science (2026). https://pith.science/paper/3Z534MTV

@misc{pith2026190803169,
  author       = {Pith},
  title        = {Pith review of: The repetition threshold for binary rich words},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3Z534MTV}},
  note         = {Machine review of arXiv:1908.03169}
}
abstract

A word of length $n$ is rich if it contains $n$ nonempty palindromic factors. An infinite word is rich if all of its finite factors are rich. Baranwal and Shallit produced an infinite binary rich word with critical exponent $2+\sqrt{2}/2$ ($\approx 2.707$) and conjectured that this was the least possible critical exponent for infinite binary rich words (i.e., that the repetition threshold for binary rich words is $2+\sqrt{2}/2$). In this article, we give a structure theorem for infinite binary rich words that avoid $14/5$-powers (i.e., repetitions with exponent at least 2.8). As a consequence, we deduce that the repetition threshold for binary rich words is $2+\sqrt{2}/2$, as conjectured by Baranwal and Shallit. This resolves an open problem of Vesti for the binary alphabet; the problem remains open for larger alphabets.

Figures

Figures reproduced from arXiv: 1908.03169 by the authors.

Figure 1
Figure 1. The tree showing all possible prefixes of ui+10. 0 2 2 2 1 1 0 0 1 2 1 0 0 [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. The tree showing all possible prefixes of Wi0. By Lemma 7, the word W contains a 0. Replacing W by a suffix if necessary, write W = W1W2W3W4 · · · , where each Wi starts with 0 and contains no other 0. Let i ≥ 1. As above, we enumerate the possible prefixes of Wi0 in the tree of [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. The tree showing all possible prefixes of ui0. • 0210: The word 0210 is not rich. • 0211: The word 11 is in F. • 0212: The word 212 is in F. • 02210: The word 02210 is not rich. • 02211: The word 11 is in F. • 02212: The word 212 is in F. • 0222: The word 222 is a cube. Thus, we conclude from [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages

  1. [1]

    Allouche and J

    J.-P . Allouche and J. Shallit, Automatic Sequences, Cambridge, 2003

    work page 2003

  2. [2]

    Balkov´ a, E

    L. Balkov´ a, E. Pelantov´ a,ˇS. Starosta, Infinite words with finite defect, Adv. Appl. Mat h. 47 (2011), 562–574

    work page 2011

  3. [3]

    Baranwal and J

    A. Baranwal and J. Shallit, Repetitions in infinite palin drome-rich words, in: R. Mercas and D. Reidenbach (Eds.), Proc. WORDS 2019, Lecture Notes in Computer Science, V ol. 11682, Springer, (2019), 93–105

    work page 2019

  4. [4]

    Baranwal and J

    A. Baranwal and J. Shallit, Critical exponent of infinite balanced words via the Pell number system, in: R. Mercas and D. Reidenbach (Eds.), Proc. WORDS 2019, Lecture Notes in Computer Science, V ol. 11682, Springer, (2019), 80–92

    work page 2019

  5. [5]

    Blondin Mass´ e, S

    A. Blondin Mass´ e, S. Brlek, S. Labb´ e, L. Vuillon, Palindromic complexity of codings of rotations, Theoret. Comput. Sci. 412 (2011), 6455–6463

    work page 2011

  6. [6]

    Brlek, S

    S. Brlek, S. Hamel, M. Nivat, C. Reutenauer, The palindro mic complexity of infinite words, Internat. J. Found. Comput. Sci. 15 (2004), 293–306. The repetition threshold for binary rich words 15

    work page 2004

  7. [7]

    Carpi, On Dejean’s conjecture over large alphabets, T heoret

    A. Carpi, On Dejean’s conjecture over large alphabets, T heoret. Comput. Sci. 385 (2007), 137–151

    work page 2007

  8. [8]

    J. D. Currie and N. Rampersad, Dejean’s conjecture holds for n ≥ 27, RAIRO - Theor. Inform. Appl. 43 (2009), 775–778

    work page 2009

Show all 34 references
  1. [9]

    J. D. Currie and N. Rampersad, A proof of Dejean’s conject ure, Math. Comp. 80 (2011), 1063–1070

    2011

  2. [10]

    Damanik and D

    D. Damanik and D. Lenz, The index of Sturmian sequences, European J. Combinatorics 23 (2002), 23–29

    2002

  3. [11]

    de Luca, A

    A. de Luca, A. Glen, L. Q. Zamboni, Rich, Sturmian, and tr apezoidal words, Theoret. Comput. Sci. 407 (2008), 569–573

    2008

  4. [12]

    Dejean, Sur un th´ eor` eme de Thue, J

    F. Dejean, Sur un th´ eor` eme de Thue, J. Combin. Theory Ser. A 13 (1972), 90–99

    1972

  5. [13]

    Droubay, J

    X. Droubay, J. Justin, G. Pirillo, Episturmian words an d some constructions of de Luca and Rauzy, Theoret. Comput. Sci. 255 (2001), 539–553

    2001

  6. [14]

    Glen and J

    A. Glen and J. Justin, Episturmian words: A survey, RAIR O – Theoret. Inform. Appl. 43 (2009), 403–442

    2009

  7. [15]

    A. Glen, J. Justin, S. Widmer, L. Q. Zamboni, Palindromi c richness, European J. Combinatorics 30 (2009), 510-531

    2009

  8. [16]

    A. Hof, O. Knill, B. Simon, Singular continuous spectru m for palindromic Schr¨ odinger operators, Comm. Math. Phys. 174 (1995), 149–159

    1995

  9. [17]

    Justin and G

    J. Justin and G. Pirillo, Fractional powers in Sturmian words, Theoret. Comput. Sci. 255 (2001), 363–376

    2001

  10. [18]

    Karhum¨ aki and J

    J. Karhum¨ aki and J. Shallit, Polynomial versus expone ntial growth in repetition-free binary words, J. Combin. Theory Ser. A 105 (2004), 335–347

    2004

  11. [19]

    Lothaire, Algebraic Combinatorics on Words, Cambri dge, 2002

    M. Lothaire, Algebraic Combinatorics on Words, Cambri dge, 2002

    2002

  12. [20]

    Medkov´ a, E

    K. Medkov´ a, E. Pelantov´ a, L. Vuillon, Derivated sequ ences of complementary symmetric Rote words. Preprint available at https://arxiv.org/abs/1812.03748

    arXiv

  13. [21]

    Mohammad-Noori and J

    M. Mohammad-Noori and J. D. Currie, Dejean’s conjectur e and Sturmian words, European J. Com- bin. 28 (2007), 876–890

    2007

  14. [22]

    Moulin-Ollagnier, Proof of Dejean’s conjecture for alphabets with 5, 6, 7, 8, 9, 10, and 11 letters, Theoret

    J. Moulin-Ollagnier, Proof of Dejean’s conjecture for alphabets with 5, 6, 7, 8, 9, 10, and 11 letters, Theoret. Comput. Sci. 95 (1992), 187–205

    1992

  15. [23]

    J. J. Pansiot, A propos d’une conjecture de F. Dejean sur les r´ ep´ etitions dans les mots, Discrete Appl. Math. 7 (1984), 297–311

    1984

  16. [24]

    Pelantov´ a and ˇStˇ ep´ an Starosta, Languages invariant under more symmetries: Overlapping factors versus palindromic richness, Discrete Math

    E. Pelantov´ a and ˇStˇ ep´ an Starosta, Languages invariant under more symmetries: Overlapping factors versus palindromic richness, Discrete Math. 313 (2013), 24 32–2445. 16 James D. Currie, Lucas Mol, Narad Rampersad

    2013

  17. [25]

    Peltom¨ aki, Characterization of repetitions in Sturmian words: A new proof

    J. Peltom¨ aki, Characterization of repetitions in Sturmian words: A new proof. Inform. Process. Lett. 115 (2015), 886–891

    2015

  18. [26]

    Peltom¨ aki, Privileged W ords and Sturmian W ords, PhD thesis, TUCS Dissertations No

    J. Peltom¨ aki, Privileged W ords and Sturmian W ords, PhD thesis, TUCS Dissertations No. 214, Au- gust 2016. Available at http://www.utupub.fi/handle/10024/124473

    2016

  19. [27]

    Rote, Sequences with subword complexity 2n, J

    G. Rote, Sequences with subword complexity 2n, J. Number Theory 46 (1994), 196–213

    1994

  20. [28]

    Rampersad, J

    N. Rampersad, J. Shallit, ´E. V andomme, Critical exponents of infinite balanced words, Theoret. Comput. Sci 777 (2019), 454–463

    2019

  21. [29]

    Rao, Last cases of Dejean’s conjecture, Theoret

    M. Rao, Last cases of Dejean’s conjecture, Theoret. Com put. Sci. 412 (2011), 3010–3018

    2011

  22. [30]

    Restivo and G

    A. Restivo and G. Rosone, Burrows-Wheeler transform an d palindromic richness, Theoret. Comput. Sci. 410 (2009), 3018–3026

    2009

  23. [31]

    Restivo and S

    A. Restivo and S. Salemi, On weakly square free words, Bu ll. European Assoc. Theoret. Comput. Sci. 21 (1983), 49–56

    1983

  24. [32]

    Restivo and S

    A. Restivo and S. Salemi, Overlap free words on two symbo ls, in: M. Nivat and D. Perrin (Eds.), Automata on Infinite W ords, Lecture Notes in Computer Science, V ol. 192, Springer, Ber lin (1985), 198–206

    1985

  25. [33]

    V esti, Extensions of rich words, Theoret

    J. V esti, Extensions of rich words, Theoret. Comput. Sc i. 548 (2014), 14–24

    2014

  26. [34]

    V esti, Rich square-free words, Theoret

    J. V esti, Rich square-free words, Theoret. Comput. Sci . 687 (2017), 48–61

    2017

Pith tools

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