Pith. sign in

REVIEW 3 major objections 4 minor 55 references

The Shortest Interesting Binary Words

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

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

Pith's one-line read The paper argues that the binary words 0011 and 001011 are the shortest interesting binary words, since each is the shortest or unique example across dozens of distinct problems in combinatorics on words.

desk verdict A pleasant, useful survey of two very special binary words, but the 'shortest interesting' claim is an aesthetic judgment dressed up as a theorem. read the letter →

arxiv 2412.21145 v2 pith:DBK6DJIX submitted 2024-12-30 math.CO cs.FL

Gabriele Fici This is my paper · ORCID
classification math.COcs.FL MSC 68R15
keywords combinatoricsonwordsbinarypalindromesanti-palindromesLyndondeBruijnrichruns
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 tries to establish that two specific binary words, v=0011 and w=001011, are the shortest 'interesting' binary words. It argues for this by showing that, across a wide range of classical problems in combinatorics on words, these two words are the shortest or the unique example: v is the shortest word with two primitive square factors, the smallest Dyck shuffle square, and the lexicographically least de Bruijn word of order 2; w is the unique asymmetric binary word of length 6, the shortest word with palindromic length 3, the generator of an infinite word with the minimum possible number of palindromic factors, and the lexicographically least generalized de Bruijn word of order 3. If the claim is right, these two small words occupy a special structural position in the field, and many extremal results can be illustrated or tested using them.

What carries the argument

The paper is carried by the two concrete binary words v=0011 and w=001011. In the diagonal lattice representation (0 encodes a downstep, 1 an upstep), v traces a V and w traces a W, and the paper shows that both words reappear as extremal examples across a broad set of definitions: palindromes, anti-palindromes, rich words, Lyndon words, Dyck words, de Bruijn words, runs, bispecial factors, minimal forbidden factors, attractors, balanced words, and shuffle squares. Their role is to serve as the minimal or unique nontrivial instances where these notions take their extreme values, with the supporting results borrowed from the literature and, in places, given short proofs or sketches.

What would settle it

A literature-wide count of distinct properties for which each binary word of length at most 5 is the shortest or unique example; if any such word matches or exceeds the number of properties realized by 0011 and 001011, the claim of minimality fails.

Watch

Extended reading notes

Core claim

The central claim is that v=0011 and w=001011 are the shortest binary words that can reasonably be called interesting, because each is the shortest or unique example for a long list of properties studied in combinatorics on words. The paper demonstrates this by surveying properties: v is an anti-palindrome (its mirror image differs in every position), a Lyndon word, a Dyck word, a rich word, a minimal anti-square, the shortest word with two primitive rooted squares, the lexicographically least binary de Bruijn word of order 2, and a word with the maximum number of distinct factors for its length; w is the unique asymmetric binary word of length 6, a word of palindromic length 3 that is minimal with this property, the shortest word with no attractor of size 2, a word whose rotations are all rich while its square is not, the lexicographically least generalized de Bruijn word of order 3, and the generator of an infinite periodic word containing the minimum possible number of palindromic factors.

Load-bearing premise

The argument depends on accepting that the list of properties surveyed (palindromic richness, Lyndon decompositions, de Bruijn properties, runs, factor complexity, and so on) is what makes a word interesting; if 'interesting' means something broader, shorter words might qualify.

Editorial extensions

If this is right

  • Any general theorem about binary words of length at most 6 must account for v and w, since they already realize the extremal values of many classical parameters.
  • The infinite word w∞ is, up to rotation and complement, the unique binary word with the minimum possible 9 distinct palindromic factors, making it the natural extremal example for palindromic-factor lower bounds.
  • The sharp bound 7 in the overlap-free factorization theorem is pinned down by w, which has two distinct overlap-free decompositions.
  • The words v and w are respectively the lexicographically least binary de Bruijn word of order 2 and the lexicographically least generalized binary de Bruijn word of order 3, so they sit at the start of the standard de Bruijn constructions.
  • Because w is a rotation of its own Burrows-Wheeler transform, it provides a rare small example relevant to the open problem of characterizing BWT fixed points.

Reading between the lines

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

  • A natural quantitative extension of the paper's thesis would be to score every binary word of length at most 6 by how many distinct extremal properties it realizes; the prediction is that v and w (together with their mirror images and complements) dominate, and that no word of length 5 or less has a comparable profile.
  • The same 'shortest interesting words' question could be posed over larger alphabets or for circular words, where an analogous small set of words might concentrate the extremal behaviors.
  • The morphisms built from w in the paper (e.g., 0 ↦ 0w, 1 ↦ w) suggest a general recipe for constructing infinite binary words with very few palindromic factors, which could be tested beyond the aperiodic example given.
  • Since w∞ has the minimal palindromic-factor count, w could serve as a benchmark input for algorithms that count or avoid palindromes in streams.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. This paper argues that the binary words v=0011 and w=001011 are 'the shortest interesting binary words.' The argument is a survey: the author lists numerous properties (anti-palindromes, rich words, palindromic length, Lyndon factorizations, runs, de Bruijn words, balanced/unbalanced words, attractors, bispecial factors, etc.) for which v and w are extremal or characteristic examples, with citations to the literature and a few short propositions.

Significance. If the central claim were made precise, the paper could serve as a useful annotated bibliography of properties shared by two small words. Its value as a survey is real: it collects a large number of known theorems and examples in one place. However, the central assertion is not a theorem: 'interesting' is undefined, and minimality is not established by the evidence. The manuscript's strength is its compilation of references; its weakness is the mismatch between the title/abstract claim and the informal evidence.

major comments (3)
  1. [Abstract and Section 1] The central claim 'the shortest interesting binary words' is not precisely defined. The paper never specifies what makes a binary word 'interesting', which properties count, how they are weighted, or why the list in Sections 2-5 is representative. As a result, the minimality claim cannot be checked, and the conclusion is an aesthetic judgment rather than a theorem. The author's own hedge ('probably the shortest binary words that are not too trivial', Section 1) acknowledges this. Either define the class of properties under which minimality is asserted and prove it, or restate the aim as a survey of notable properties of v and w.
  2. [Sections 2, 3, and 5] Several 'shortest' or 'minimal' assertions are load-bearing for the paper's claim but are cited without proof or precise theorem numbers, e.g. 'no binary word of length smaller than 6 is asymmetric' (Section 2), 'w=001011 is a binary word of minimal length having palindromic length 3' (Section 2), 'the maximal value of sigma for a word of length 6 is 6, realized by w' (Section 3), and 'the shortest binary word having no attractor of size 2 is w' (Section 5). For each such statement, please provide the exact source (theorem number and page) or a proof, since the survey's cumulative evidence depends on these facts.
  3. [Section 1] The selection of properties is not justified against alternative short words. The paper does not compare v and w with 01, 10, 010, or 0110 under any systematic criterion, and 'too trivial' is never made precise. A different but equally defensible list of properties (e.g., being a palindrome, being a square, having a square factor) would single out other short words, so the evidence as presented cannot rule out a shorter 'interesting' word. The paper needs either a formalization of interestingness or an explicit statement that the claim is about the particular list of properties surveyed.
minor comments (4)
  1. [Section 2, Proposition 1] In the proof, 'the derivative of a palindrome is either the word 1n' should read '1^n' (the word consisting of n copies of the character 1).
  2. [Section 3] The word 'morphsim' should be 'morphism'.
  3. [Section 3] The definition of an anti-square as 'a word of the form uu, where u is the complement of u' is self-contradictory; presumably the intended definition is u followed by the complement of u. Please correct.
  4. [Section 4] The phrase 'this can be proved by exercise' should be replaced by a reference or a short proof.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the paper is an expository survey; the informal 'shortest interesting' claim is underdefined but not reduced to the paper's own inputs.

full rationale

The paper does not derive its central claim from a fitted parameter, a self-referential definition, or a self-citation chain. It is an expository survey that catalogues independently established properties of the words v=0011 and w=001011, each attributed to specific external results (e.g., palindromic length, runs, Lyndon factorizations, de Bruijn properties, attractors, minimal unbalanced words). The self-citations [23], [24], and [25] cite published theorems by the author and coauthors; those theorems are external evidence for individual properties, not constructions that presuppose that v or w is 'interesting', so they are not load-bearing circularity. The phrase 'shortest interesting binary words' is not a formal theorem: 'interesting' is never defined, and the selection of properties is informal. That makes the headline claim unfalsifiable as a mathematical statement, but this is a rigor or framing issue, not a circular reduction: no equation or definition forces the conclusion from the premises. The sketch proofs of Proposition 6 and Proposition 9 are terse and partly assert classifications without full proof, but their statements are independent combinatorial facts and do not use the target conclusion as an input. Accordingly, the appropriate finding is no significant circularity.

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

The paper introduces no free parameters, new axioms, or invented entities. It defines a few new terms (e.g., Pansiot pre-palindrome) but these are definitions, not unproved assumptions. The central claim relies on the correctness of cited external results and standard definitions in combinatorics on words.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Shortest Interesting Binary Words." pith.science (2026). https://pith.science/paper/DBK6DJIX

@misc{pith2026241221145,
  author       = {Pith},
  title        = {Pith review of: The Shortest Interesting Binary Words},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DBK6DJIX}},
  note         = {Machine review of arXiv:2412.21145}
}
read the original abstract

I will show that there exist two binary words (one of length 4 and one of length 6) that play a special role in many different problems in combinatorics on words. They can therefore be considered \textit{the shortest interesting binary words}. My claim is supported by the fact that these two words appear in dozens of papers in combinatorics on words.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

55 extracted references · 54 canonical work pages

  1. [1]

    Allouche, J

    J.-P. Allouche, J. D. Currie, and J. O. Shallit. Extremal Infinite Overlap-Free Binary Words. Electron. J. Comb. , 5, 1998

    work page 1998

  2. [2]

    Y. H. Au. Generalized de Bruijn words for primitive words and powers. Discret. Math. , 338(12):2320–2331, 2015

    work page 2015

  3. [3]

    Bannai, T

    H. Bannai, T. I, S. Inenaga, Y. Nakashima, M. Takeda, and K. Tsuruta. The ”Runs” Theorem. SIAM J. Comput. , 46(5):1501–1514, 2017

    work page 2017

  4. [4]

    Baranwal, J

    A. Baranwal, J. D. Currie, L. Mol, P. Ochem, N. Rampersad, and J. Shallit. Antisquares and critical exponents. Discret. Math. Theor. Comput. Sci. , 25(2):#11, 2023. 11

    work page 2023

  5. [5]

    Bassino, J

    F. Bassino, J. Cl´ ement, and C. Nicaud. Lyndon words with a fixed standard right factor. In J. I. Munro, editor, Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, January 11-14, 2004 , pages 653–654. SIAM, 2004

    work page 2004

  6. [6]

    Becher and P

    V. Becher and P. A. Heiber. On extending de Bruijn sequences. Inf. Process. Lett., 111(18):930–932, 2011

    work page 2011

  7. [7]

    J. Berstel. Axel Thue’s papers on repetitions in words: a translation. Publications du LaCIM , 20, 1995

    work page 1995

  8. [8]

    J. Berstel. Sturmian and Episturmian Words (A Survey of Some Recent Results). In S. Bozapalidis and G. Rahonis, editors, Algebraic Informatics, Second International Conference, CAI 2007, Thes- saloniki, Greece, May 21-25, 2007, Revised Selected and Invited Papers , volume 4728 of Lecture Notes in Computer Science , pages 23–47. Springer, 2007

    work page 2007

Show all 55 references
  1. [9]

    Boasson and O

    L. Boasson and O. Carton. Rational Selecting Relations and Selectors. In A. Dediu, E. Formenti, C. Mart ´ ın-Vide, and B. Truthe, editors,Language and Automata Theory and Applications - 9th International Conference, LATA 2015, Nice, France, March 2-6, 2015, Proceedings , volum...

    2015

  2. [10]

    Borchert and N

    A. Borchert and N. Rampersad. Words with many palindrome pair factors. Electron. J. Comb. , 22(4):4, 2015

    2015

  3. [11]

    Borel and F

    J.-P. Borel and F. Laubie. Quelques mots sur la droite projective r´ eelle. Journal de th´ eorie des nombres de Bordeaux, 5(1):23–51, 1993

    1993

  4. [12]

    Brlek, S

    S. Brlek, S. Hamel, M. Nivat, and C. Reutenauer. On the palindromic complexity of infinite words. International Journal of Foundations of Computer Science , 15:293–306, 2004

    2004

  5. [13]

    Bulteau and S

    L. Bulteau and S. Vialette. Recognizing binary shuffle squares is NP-hard. Theor. Comput. Sci. , 806:116–132, 2020

    2020

  6. [14]

    Carpi and A

    A. Carpi and A. de Luca. Words and special factors. Theor. Comput. Sci., 259(1-2):145–182, 2001

    2001

  7. [15]

    Carpi and A

    A. Carpi and A. de Luca. Harmonic and gold Sturmian words. Eur. J. Comb. , 25(5):685–705, 2004

    2004

  8. [16]

    J. D. Currie and P. Lafrance. Avoidability index for binary patterns with reversal. Electron. J. Comb., 23(1):1, 2016

    2016

  9. [17]

    J. D. Currie and N. Rampersad. Cubefree words with many squares. Discret. Math. Theor. Comput. Sci., 12(3):29–34, 2010

    2010

  10. [18]

    A. de Luca. On the combinatorics of finite words. Theoret. Comput. Sci. , 218:13–39, 1999

    1999

  11. [19]

    de Luca, A

    A. de Luca, A. Glen, and L. Q. Zamboni. Rich, Sturmian, and trapezoidal words. Theoret. Comput. Sci., 407:569–573, 2008

    2008

  12. [20]

    de Luca and F

    A. de Luca and F. Mignosi. Some Combinatorial Properties of Sturmian Words. Theor. Comput. Sci., 136(2):361–285, 1994

    1994

  13. [21]

    Droubay, J

    X. Droubay, J. Justin, and G. Pirillo. Episturmian words and some constructions of de Luca and Rauzy. Theor. Comput. Sci. , 255(1-2):539–553, 2001. 12

    2001

  14. [22]

    Dvoˇ r´ akov´ a, P

    L. Dvoˇ r´ akov´ a, P. Ochem, and D. Opoˇ censk´ a. Critical Exponent of Binary Words with Few Distinct Palindromes. Electron. J. Comb. , 31(2), 2024

    2024

  15. [23]

    G. Fici. On the structure of bispecial Sturmian words. J. Comput. Syst. Sci. , 80(4):711–719, 2014

    2014

  16. [24]

    G. Fici, J. Shallit, and J. Simpson. Some remarks on palindromic periodicities. ArXiv preprint arXiv:2407.10564 [math.CO]. Available at https://arxiv.org/abs/2407.10564., 2024

    2024 arXiv

  17. [25]

    Fici and L

    G. Fici and L. Q. Zamboni. On the least number of palindromes contained in an infinite word. Theoret. Comput. Sci. , 481:1–8, 2013

    2013

  18. [26]

    A. S. Fraenkel and J. Simpson. How Many Squares Can a String Contain? J. Comb. Theory, Ser. A, 82(1):112–120, 1998

    1998

  19. [27]

    Fredricksen and J

    H. Fredricksen and J. Maiorana. Necklaces of beads in k colors and k-ary de Bruijn sequences. Discret. Math., 23(3):207–210, 1978

    1978

  20. [28]

    A. E. Frid, S. Puzynina, and L. Q. Zamboni. On palindromic factorization of words. Adv. Appl. Math., 50(5):737–748, 2013

    2013

  21. [29]

    Frosini, I

    A. Frosini, I. Mancini, S. Rinaldi, G. Romana, and M. Sciortino. Logarithmic Equal-Letter Runs for BWT of Purely Morphic Words. In V. Diekert and M. V. Volkov, editors, Developments in Language Theory - 26th International Conference, DLT 2022, Tampa, FL, USA, May 9-13, 2022, P...

    2022

  22. [30]

    Gabric, S

    D. Gabric, S. Holub, and J. O. Shallit. Maximal state complexity and generalized de Bruijn words. Inf. Comput. , 284:104689, 2022

    2022

  23. [31]

    A. Glen, J. Justin, S. Widmer, and L. Q. Zamboni. Palindromic richness. European J. Combin. , 30:510–531, 2009

    2009

  24. [32]

    C. Guo, J. O. Shallit, and A. M. Shur. On the combinatorics of palindromes and antipalindromes. CoRR, abs/1503.09112, 2015

    2015 arXiv

  25. [33]

    Harju, M

    T. Harju, M. Huova, and L. Q. Zamboni. On generating binary words palindromically. J. Comb. Theory, Ser. A , 129:142–159, 2015

    2015

  26. [34]

    X. He, E. Huang, I. Nam, and R. Thaper. Shuffle squares and reverse shuffle squares. Eur. J. Comb., 116:103883, 2024

    2024

  27. [35]

    Henshall, N

    D. Henshall, N. Rampersad, and J. O. Shallit. Shuffling and Unshuffling. Bull. EATCS, 107:131– 142, 2012

    2012

  28. [36]

    P. M. Higgins. Burrows-Wheeler transformations and de Bruijn words. Theor. Comput. Sci. , 457:128–136, 2012

    2012

  29. [37]

    Holub and K

    S. Holub and K. Saari. On highly palindromic words. Discret. Appl. Math. , 157(5):953–959, 2009

    2009

  30. [38]

    R. M. Kolpakov and G. Kucherov. Finding Maximal Repetitions in a Word in Linear Time. In 40th Annual Symposium on Foundations of Computer Science, FOCS ’99, 17-18 October, 1999, New York, NY, USA , pages 596–604. IEEE Computer Society, 1999. 13

    1999

  31. [39]

    Lapointe

    M. Lapointe. Combinatoire des mots: Mots parfaitement amassants, triplets de Markoff et graphes chenilles. PhD thesis, UQAM, 2020

    2020

  32. [40]

    A. Lempel. On a Homomorphism of the de Bruijn Graph and its Applications to the Design of Feedback Shift Registers. IEEE Trans. Computers, 19(12):1204–1209, 1970

    1970

  33. [41]

    Lothaire

    M. Lothaire. Algebraic Combinatorics on Words . Encyclopedia of Mathematics and its Applica- tions. Cambridge Univ. Press, New York, NY, USA, 2002

    2002

  34. [42]

    Mantaci, A

    S. Mantaci, A. Restivo, G. Rosone, F. Russo, and M. Sciortino. On Fixed Points of the Burrows- Wheeler Transform. Fundam. Informaticae, 154(1-4):277–288, 2017

    2017

  35. [43]

    Melan¸ con

    G. Melan¸ con. Lyndon factorization of Sturmian words. Discret. Math., 210(1-3):137–149, 2000

    2000

  36. [44]

    M´ etivier

    Y. M´ etivier. Calcul de longueurs de cha ˆ ınes de r´ e´ ecriture dans le mono ¨ ıde libre.Theor. Comput. Sci., 35:71–87, 1985

    1985

  37. [45]

    Mignosi, A

    F. Mignosi, A. Restivo, and M. Sciortino. Words and forbidden factors. Theor. Comput. Sci. , 273(1-2):99–117, 2002

    2002

  38. [46]

    L. Mol, N. Rampersad, and J. O. Shallit. Dyck Words, Pattern Avoidance, and Automatic Se- quences. In A. E. Frid and R. Mercas, editors, Combinatorics on Words - 14th International Conference, WORDS 2023, Ume ˚ a, Sweden, June 12-16, 2023, Proceedings, volume 13899 of Lec- tur...

    2023

  39. [47]

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

    1984

  40. [48]

    N. Prezza. String attractors. CoRR, abs/1709.05314, 2017

    2017 arXiv

  41. [49]

    Raffinot

    M. Raffinot. On maximal repeats in strings. Inf. Process. Lett., 80(3):165–169, 2001

    2001

  42. [50]

    Rampersad and J

    N. Rampersad and J. Shallit. Words avoiding reversed subwords. J. Combin. Math. Combin. Comput., 54:157–164, 2005

    2005

  43. [51]

    O. Ravsky. On the palindromic decomposition of binary words. Journal of Automata, Languages and Combinatorics , 8(1):75–83, 2003

    2003

  44. [52]

    Restivo and S

    A. Restivo and S. Salemi. Overlap-free words on two symbols. In M. Nivat and D. Perrin, editors, Automata on Infinite Words, Ecole de Printemps d’Informatique Th´ eorique, Le Mont Dore, France, May 14-18, 1984, volume 192 of Lecture Notes in Computer Science, pages 198–206. Sp...

    1984

  45. [53]

    Richomme and P

    G. Richomme and P. S´ e´ ebold. Characterization of Test-sets for Overlap-free Morphisms.Discret. Appl. Math. , 98(1-2):151–157, 1999

    1999

  46. [54]

    J. O. Shallit. On the maximum number of distinct factors of a binary string. Graphs Comb. , 9(2-4):197–200, 1993

    1993

  47. [55]

    J. Simpson. Palindromic periodicities. ArXiv preprint arXiv:2402.05381 [math.CO]. Available at https://arxiv.org/abs/2402.05381., 2024. 14

    2024 arXiv

Pith tools

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