Repetitions in Infinite Palindrome-Rich Words

Aseem R. Baranwal, Jeffrey O. Shallit

TL;DR

This paper investigates "rich words," a class of infinite strings with the maximum possible number of distinct palindromic substrings. The authors construct a novel infinite binary rich word and determine its critical exponent to be $2 + \sqrt{2}/2$, which is conjectured to be the repetition threshold for binary alphabets. This work makes progress on an open problem concerning repetitions in rich words.

What Problem Does This Paper Address?

The study of repetitions in words is a fundamental area in combinatorics on words. A key concept is the "critical exponent" of a word, which measures the highest power of a substring that appears in the word. Another related concept is the "repetition threshold" for an alphabet, which is the smallest possible critical exponent achievable by any infinite word over that alphabet.

This paper focuses on a specific class of words called "rich words." Rich words are defined as infinite words where every factor (substring) contains the maximum possible number of distinct palindromes for its length. While rich words have been studied for their palindromic properties, understanding the repetitions within them, particularly their critical exponents and repetition thresholds, remains an open area with several challenging problems. Specifically, the paper aims to address lower bounds on the repetition threshold for rich words over small alphabets and to construct candidate infinite rich words with small critical exponents.

Methods

The authors employ a combination of theoretical and computational methods:

  • Automata Theory and Formal Languages: They construct an automaton that generates an infinite binary word, denoted by $r$. This automaton is designed to work with the Pell number system, a non-standard positional number system.
  • Morphisms: The word $r$ is defined using a system of morphisms ($\phi$ and $\tau$, and later $f$ and $g$), which are functions that map strings to strings. The equivalence between the word generated by $\tau(\phi^\omega(0))$ and $g(f^\omega(0))$ is rigorously proven using induction.
  • Automatic Theorem Proving (Walnut): The software Walnut is used to verify properties of the constructed word $r$, specifically its palindromic richness. This involves defining predicates that express properties of the word and its factors.
  • Predicate Logic: The richness of the word $r$ is proven by checking if all its prefixes satisfy a specific property related to unioccurrent palindromic suffixes, as stated in Theorem 3.
  • Computational Search: For determining the critical exponent and exploring optimality, the authors leverage computational search, likely involving backtracking algorithms, to find maximal repetitions and analyze their exponents.

Datasets

Not discussed in the paper. The paper focuses on constructing and analyzing a specific infinite word rather than training on or evaluating against existing datasets.

Key Insights and Ideas

  • Constructing a Rich Word with a Low Critical Exponent: The paper successfully constructs a specific infinite binary rich word, $r$, and proves its critical exponent is $2 + \sqrt{2}/2$. This is a significant achievement as it provides a concrete example of a rich word with a relatively low critical exponent, advancing the understanding of repetitions in this class of words.
  • Conjecture on Repetition Threshold: The authors conjecture that the critical exponent of $r$, $2 + \sqrt{2}/2$, is indeed the repetition threshold for binary alphabets. This is supported by computational evidence and provides a strong candidate for this important parameter.
  • Pell Number System for Automata: The use of the Pell number system to define and work with the automaton for the word $r$ is a novel approach. This allows for efficient representation and manipulation of indices within the infinite word.
  • Walnut for Formal Verification: The paper demonstrates the power of automatic theorem provers like Walnut for rigorously verifying complex combinatorial properties of infinite words, such as palindromic richness.

Key Results

  • Construction of Infinite Binary Rich Word: The paper constructs an infinite binary rich word $r = g(f^\omega(0))$ (which is also equal to $\tau(\phi^\omega(0))$).
  • Critical Exponent of $r$: The critical exponent of the word $r$ is determined to be $2 + \sqrt{2}/2$.
  • Conjectured Repetition Threshold for Binary Alphabet: It is conjectured that $RT(2) = 2 + \sqrt{2}/2 \approx 2.7071$.
  • Bounds on Repetition Threshold: The paper provides bounds for the repetition threshold of binary alphabets: $2.700 < RT(2) \leq 2 + \sqrt{2}/2$.
  • Lower Bound for Ternary Alphabet: For an alphabet of size $k=3$, it is shown that $RT(3) \geq 9/4$.

Limitations and Future Work

  • Conjecture vs. Proof: While the critical exponent of $r$ is proven to be $2 + \sqrt{2}/2$, the claim that this is the repetition threshold for binary alphabets is a conjecture, supported by computational evidence. Proving this conjecture would require showing that no other infinite binary rich word can achieve a smaller critical exponent.
  • Larger Alphabets: The paper explores larger alphabets ($k=3, 4$) but only establishes lower bounds for $RT(3)$ ($9/4$). Constructing rich words with small critical exponents over larger alphabets remains an open challenge.
  • Optimality of Critical Exponent: The paper notes that a backtracking computation shows the longest rich binary word with a critical exponent less than 2.700 is of length 1339. This is used to establish bounds but further investigation into the structure of such words could be fruitful.
  • Future Work: The authors suggest several directions:
  • Developing novel methods to prove lower bounds on the repetition threshold for infinite rich words.
  • Constructing infinite rich words over larger alphabets to serve as candidates for their respective repetition thresholds.
  • Implementing faster algorithms for computing maximal runs to improve backtracking search efficiency and compute tighter lower bounds on repetition thresholds.

Summary updated

Abstract

Rich words are characterized by containing the maximum possible number of distinct palindromes. Several characteristic properties of rich words have been studied; yet the analysis of repetitions in rich words still involves some interesting open problems. We address lower bounds on the repetition threshold of infinite rich words over 2 and 3-letter alphabets, and construct a candidate infinite rich word over the alphabet $Σ_2=\{0,1\}$ with a small critical exponent of $2+\sqrt{2}/2$. This represents the first progress on an open problem of Vesti from 2017.
BibTeX
@inproceedings{baranwal2019repetitions,
  author = {Aseem R. Baranwal and Jeffrey O. Shallit},
  title = {{Repetitions in Infinite Palindrome-Rich Words}},
  booktitle = {Words},
  year = {2019},
  doi = {10.1007/978-3-030-28796-2\_7},
}
Figure