Critical exponent of ternary words with few distinct palindromes
L’ubomíra Dvořáková a, Lucas Mol b, Pascal Ochem c · 2025
Read Critical exponent of ternary words with few distinct palindromes by L’ubomíra Dvořáková a, Lucas Mol b, Pascal Ochem c (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-04925.txt.
Introduction
Ľubomíra Dvořáková, Lucas Mol, and Pascal Ochem study endless words over a three-letter alphabet that contain very few palindromes, in a 2025 paper. A palindrome reads the same forward and backward, and words rich or poor in them behave very differently. The team sorts such palindrome-poor words by their critical exponent, a number that measures how much repetition a word allows. Their classification maps exactly which repetition levels occur for words with so few mirrored blocks.
Catalog record
| CREATOR | L’ubomíra Dvořáková a, Lucas Mol b, Pascal Ochem c |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 68 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-04925
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Critical exponent of ternary words with few distinct palindromes L’ubomíra Dvořáková a, Lucas Mol b, Pascal Ochem c Abstract We study infinite ternary words that contain few distinct palindromes. In particular, we classify such words according to their critical exponents. 1 Introduction We consider the trade-off between the number of distinct palindromes and the critical exponent in infinite words. For brevity, every mention of a number of palindromes will refer to a number of distinct palindromes, including the empty word. This trade-off has been recently investigated for binary words [ 9 ] . Removing the constraint on the alphabet size does not give anything new: • 4 palindromes are only obtained by (\texttt{012})^{\omega} , with infinite critical exponent. • With k\geqslant 5 palindromes, the Dejean words on k-1 letters show that the least critical exponent is RT(k-1)^{+} . In this paper, we consider this trade-off in infinite ternary words. Our results completely answer questions of this form: do infinite \beta^{+} -free ternary words with at most p palindromes exist? In each case, we also determine whether there are exponentially or polynomially many such words. The results are summarized in Table 1 . A green (resp. red) cell means that there are exponentially (resp. polynomially) many words. We have labelled the cells that correspond to an item of Theorem 3 , 5 , or 8 . Fleischer and Shallit [ 11 ] have considered the number of ternary words of length n with at most 5 palindromes (sequence A329023 in the OEIS) and proved that it is \Theta\left(\kappa^{n}\right) , where \kappa=1.2207440846\ldots is the root of X^{4}=X+1 . 18 3.f 17 3.e 16 8 3.d 15 14 13 12 11 10 9 8 7 3.c 6 5 3.b 5 3.a 4 (\texttt{012})^{\omega} \tfrac{7}{4}^{+} \tfrac{41}{22}^{+} \tfrac{25}{13}^{+} \tfrac{52}{27}^{+} 2^{+} \tfrac{9}{4}^{+} \tfrac{10}{3}^{+} \infty Table 1 : Infinite \beta^{+} -free ternary words with at most p palindromes. 2 Preliminaries An alphabet \mathcal{A} is a finite set and its elements are called letters . A word u over \mathcal{A} of length n is a finite string u=u_{0}u_{1}\cdots u_{n-1} , where u_{j}\in\mathcal{A} for all j\in\{0,1,\dots,n-1\} . If {\mathcal{A}}=\{\tt 0,\tt 1,\dots,\tt d-1\} , the length of u is denoted |u| and |u|_{\tt f} denotes the number of occurrences of the factor {\tt f}\in\mathcal{A}^{+} in the word u . The Parikh vector \vec{u}\in\mathbb{N}^{d} is the vector defined as {\vec{u}}=(|u|_{\tt 0},|u|_{\tt 1},\dots,|u|_{\tt d-1})^{T} . The set of all finite words over \mathcal{A} is denoted {\mathcal{A}}^{*} . The set {\mathcal{A}}^{*} equipped with concatenation as the operation forms a monoid with the empty word \varepsilon as the neutral element. If w=ux for some u,x\in{\mathcal{A}}^{*} , then wx^{-1}=u . We will also consider the set {\mathcal{A}}^{\omega} of infinite words (that is, right-infinite words) and the set {}^{\omega}\hskip-4.26773pt{\mathcal{A}}^{\omega} of bi-infinite words. A word v is an e - power of a word u if v is a prefix of the infinite periodic word uuu\cdots=u^{\omega} and e=|v|/|u| . We write v=u^{e} . We also call u^{e} a repetition with period u and exponent e . For instance, the Czech word kavka (a kind of bird – jackdaw) can be written in this formalism as (kav)^{5/3} . A word is \alpha^{+} -free (resp. \alpha -free ) if it contains no repetition with exponent \beta such that \beta>\alpha (resp. \beta\geqslant\alpha ). The critical exponent E({\bf u}) of an infinite word {\bf u} is defined as E({\bf u})=\sup\left\{e\in\mathbb{Q}:\ v^{e}\text{ is a factor of }{\bf u}\text{ for a non-empty word }v\right\}. If each factor of {\bf u} has infinitely many occurrences in {\bf u} , then {\bf u} is recurrent . Moreover, if for each factor the distances between its consecutive occurrences are bounded, then {\bf u} is uniformly recurrent . The reversal of the word w=w_{0}w_{1}\cdots w_{n-1} , where the w_{i} are letters, is the word w^{R}=w_{n-1}\cdots w_{1}w_{0} . A word w is a palindrome if w=w^{R} . Consider a factor w of a recurrent infinite word {\bf u}=u_{0}u_{1}u_{2}\cdots . Let j<\ell be two consecutive occurrences of w in \bf u . Then the word u_{j}u_{j+1}\cdots u_{\ell-1} is a return word to w in \bf u . Let \mathcal{L}({\bf u}) denote the set of factors of \bf u . Given a word w\in\mathcal{L}({\bf u}) , we define the sets of left extensions, right extensions and bi-extensions of w in {\bf u} over an alphabet \mathcal{A} respectively as L_{{\bf u}}(w)=\{{\tt i}\in{\mathcal{A}}:{\tt i}w\in\mathcal{L}({\bf u})\},\qquad R_{{\bf u}}(w)=\{{\tt j}\in{\mathcal{A}}:w{\tt j}\in\mathcal{L}({\bf u})\} and B_{{\bf u}}(w)=\{({\tt i},{\tt j})\in{\mathcal{A}}\times{\mathcal{A}}:{\tt i}w{\tt j}\in\mathcal{L}({\bf u})\}. If \#L_{{\bf u}}(w)>1 , then w is called left special (LS) . If \#R_{{\bf u}}(w)>1 , then w is called right special (RS) . If w is both LS and RS, then it is called bispecial (BS) . We define b(w)=\#B_{{\bf u}}(w)-\#L_{{\bf u}}(w)-\#R_{{\bf u}}(w)+1 and we distinguish ordinary BS factors with b(w)=0 , weak BS factors with b(w)<0 and strong BS factors with b(w)>0 . A factor w of an infinite word \bf u is left special if it has at least two left extensions, i.e., {\tt i}w,{\tt j}w are factors of \bf u for at least two distinct letters {\tt i,j}\in\mathcal{A} . A right special factor is defined analogously. A factor is called bispecial if it is both left and right special. A morphism is a map \psi:{\mathcal{A}}^{*}\to{\mathcal{B}}^{*} such that \psi(uv)=\psi(u)\psi(v) for all words u,v\in{\mathcal{A}}^{*} . The morphism \psi is non-erasing if \psi(\tt i)\not=\varepsilon for each {\tt i}\in{\mathcal{A}} . Morphisms can be naturally extended to infinite words by setting \psi(u_{0}u_{1}u_{2}\cdots)=\psi(u_{0})\psi(u_{1})\psi(u_{2})\cdots\, . A fixed point of a morphism \psi:{\mathcal{A}}^{*}\to{\mathcal{A}}^{*} is an infinite word \bf u such that \psi(\bf u)=\bf u . We associate to a morphism \psi:{\mathcal{A}}^{*}\to{\mathcal{A}}^{*} the (incidence) matrix M_{\psi} defined for each k,j\in\{0,1,\dots,d-1\} as [M_{\psi}]_{kj}=|\psi(\tt j)|_{\tt k} . If there exists N\in\mathbb{N} such that M_{\psi}^{N} has positive entries, then \psi is a primitive morphism. By definition, we have for each u\in{\mathcal{A}}^{*} the following relation for the Parikh vectors \vec{\psi(u)}=M_{\psi}\vec{u} . Let {\bf u} be an infinite word over an alphabet \mathcal{A} and let \psi:{\mathcal{A}}^{*}\to{\mathcal{B}}^{*} be a morphism. Consider a factor w of \psi({\bf u}) . We say that (w_{1},w_{2}) is a synchronization point of w if w=w_{1}w_{2} and for all p,s\in\mathcal{L}(\psi({\bf u})) and v\in\mathcal{L}({\bf u}) such that \psi(v)=pws there exists a factorization v=v_{1}v_{2} of v with \psi(v_{1})=pw_{1} and \psi(v_{2})=w_{2}s . We denote the synchronization point by w_{1}\bullet w_{2} . Given a factorial language L and an integer \ell , let L^{\ell} denote the words of length \ell in L . The Rauzy graph of L of order \ell is the directed graph whose vertices are the words of L^{\ell-1} , the arcs are the words of L^{\ell} , and the arc corresponding to the word w goes from the vertex corresponding to the prefix of w of length \ell-1 to the vertex corresponding to the suffix of w of length \ell-1 . An overpal is a word of the form axax^{R}a , where x^{R} is the reversal of the (possibly empty) word x and a is a single letter. Overpals were introduced by Rajasekaran, Rampersad, and Shallit [ 1 ] . A pattern p is a non-empty finite word over the alphabet \Delta=\left\{A,B,C,\dots\right\} of capital letters called variables . An occurrence of p in a word w is a non-erasing morphism h:\Delta^{*}\to\Sigma^{*} such that h(p) is a factor of w . A