betaFeedback

WorksMathematics

Lengths and Counting of Palindromic Prefixes of Standard Sturmian Words

Abstract

Every standard Sturmian word cdc_\mathbf{d} is determined by a directive sequence d=(di)i≥1\mathbf{d}=(d_i)_{i\ge 1} of positive integers, and its palindromic prefixes are obtained by iterated palindromic closure. We describe the lengths of these prefixes by the numbers j ℓi−1+ℓi−2−2j\,\ell_{i-1}+\ell_{i-2}-2, where ℓn\ell_n is the length of the nn-th standard word and 1≤j≤di1\le j\le d_i, and we show that each nonzero length is attained by exactly one pair (i,j)≠(1,1)(i,j)\neq(1,1). For a purely periodic directive sequence of period kk we then prove that the number πd(N)π_\mathbf{d}(N) of nonempty palindromic prefixes of length at most NN satisfies πd(N)∼d1+⋯+dklog⁡λd log⁡N, π_\mathbf{d}(N)\sim\frac{d_1+\cdots+d_k}{\logλ_\mathbf{d}}\,\log N, where λdλ_\mathbf{d} is the largest eigenvalue of the matrix M(d1)⋯M(dk)M(d_1)\cdots M(d_k). For the Fibonacci word this gives πd(N)∼log⁡N/log⁡φπ_\mathbf{d}(N)\sim\log N/\logφ, where φ=(1+5)/2φ=(1+\sqrt5)/2.

πd(N)∼d1+⋯+dklog⁡λdlog⁡N,\pi_{\mathbf d}(N)\sim\frac{d_1+\cdots+d_k}{\log\lambda_{\mathbf d}}\log N,

where λd\lambda_{\mathbf d} is the largest eigenvalue of the matrix M(d1)⋯M(dk)M(d_1)\cdots M(d_k). For the Fibonacci word this gives πd(N)∼log⁡N/log⁡φ\pi_{\mathbf d}(N)\sim\log N/\log\varphi, where φ=(1+5)/2\varphi=(1+\sqrt{5})/2.

Introduction

Standard Sturmian words are generated by iterated palindromic closure, so their palindromic prefixes form the backbone of the word. They have recently appeared in several lines of work. Dvořákóvá and Hendrychová showed that the palindromic prefixes of standard Sturmian sequences have string attractors of size two, and used this to describe string attractors of pseudopalindromic prefixes of Rote sequences [7]. Dvořákóvá then described string attractors of all factors of episturmian sequences, again through palindromic closures [6]. Fici, Shallit and Simpson proved that every nonempty prefix of a standard episturmian word, and every nonempty factor of a Sturmian word, is a palindromic periodicity [8]. In a different direction, palindromic factorizations of prefixes and factors of aperiodic words have been studied through the palindromic length: Rukavicka investigated how powers can be reduced in an infinite word while keeping the palindromic length bounded [22, 23].

The palindromic prefixes of standard Sturmian words arise from the palindromic closure w(+)w^{(+)} of a finite word ww, that is, the shortest palindrome having ww as a prefix. Droubay, Justin and Pirillo [5] used iterated palindromic closure along a directive word to define standard episturmian words over an arbitrary alphabet. Justin and Pirillo [18] showed that the palindromic prefixes of a standard episturmian word are exactly the words unu_n, n>0n>0, defined by un+1=(unxn)(+)u_{n+1}=(u_nx_n)^{(+)}, where x1x2⋯x_1x_2\cdots is the directive word. They also showed that this recurrence can be written as un+1=unxnunu_{n+1}=u_nx_nu_n if xnx_n does not occur in x1⋯xn−1x_1\cdots x_{n-1}, and un+1=unuP(n)−1unu_{n+1}=u_nu_{P(n)}^{-1}u_n otherwise, with P(n)P(n) the last earlier position of xnx_n [18]. On a two-letter alphabet the directive word 0d11d20d3⋯0^{d_1}1^{d_2}0^{d_3}\cdots gives the characteristic Sturmian word of slope [0;d1+1,d2,d3,…][0;d_1+1,d_2,d_3,\ldots] [9].

Previous studies have addressed various aspects of Sturmian words and their prefixes; however, since a comprehensive review lies beyond the scope of this work, the reader is referred to the literature for further details [10, 3, 21, 4, 11, 19].

In these works the palindromic prefixes are used through their structure. The present paper asks a quantitative question instead: how many palindromic prefixes of a standard Sturmian word have length at most NN, and how does this number grow with NN?

The goal of the paper is to study the palindromic prefixes of standard Sturmian words cdc_{\mathbf{d}} through their directive sequences d=(d1,d2,…)\mathbf{d} = (d_1,d_2,\ldots). We first rederive the lengths of these prefixes as the numbers jℓi−1+ℓi−2−2j\ell_{i-1}+\ell_{i-2}-2, indexed by pairs (i,j)(i,j) with 1≤j≤di1 \le j \le d_i, where ℓn\ell_n is the length of the nn-th standard word. We then use this description to count them: for a purely periodic directive sequence d=(d1,…,dk)∞\mathbf{d} = (d_1,\ldots,d_k)^\infty, we determine the asymptotic behaviour of the number πd(N)\pi_{\mathbf{d}}(N) of nonempty palindromic prefixes of length at most NN in terms of d1+⋯+dkd_1+\cdots+d_k and the largest eigenvalue λd\lambda_{\mathbf{d}} of M(d1)⋯M(dk)M(d_1)\cdots M(d_k).

This paper is organized as follows. § 2 fixes the notation and recalls Sturmian and standard words, the construction of cdc_{\mathbf{d}} by iterated palindromic closure, and the length set of the palindromic prefixes. § 3 contains the main results. Subsection 3.1 derives the length set from the closure construction and shows that each nonzero length corresponds to exactly one pair (i,j)≠(1,1)(i,j) \ne(1,1). Subsection 3.2 proves the asymptotic formula for πd(N)\pi_{\mathbf{d}}(N) in Theorem 3.4. The last two sections contain a discussion of the result and the conclusion.

Preliminaries

Notation and conventions. We work over the binary alphabet A={0,1}A = \{0,1\}. We denote by A∗A^* the set of finite words and by ε\varepsilon the empty word. The length of a word ww is written ∣w∣|w|, and ∣w∣a|w|_a denotes the number of occurrences of the letter aa in ww. A word uu is a factor of ww if w=xuyw = xuy for some words x,yx,y; it is a prefix if x=εx = \varepsilon and a suffix if y=εy = \varepsilon. For a word ww and an integer j≥0j \ge0, wjw^j is the word ww repeated jj times, with w0=εw^0 = \varepsilon. The reversal of w=w1⋯wnw = w_1\cdots w_n is w~=wn⋯w1\widetilde{w} = w_n\cdots w_1, and ww is a palindrome if w=w~w = \widetilde{w}, the empty word and single letters being palindromes. A prefix of a word xx that is a palindrome is called a palindromic prefix of xx. Regarding asymptotics, f(N)∼g(N)f(N) \sim g(N) means that f(N)/g(N)→1f(N)/g(N) \to1 as N→∞N \to\infty, and all logarithms are natural.

Sturmian words and standard words

Definition 2.1 ([12]). The complexity of an infinite word xx is px(n)p_x(n), the number of distinct factors of length nn. An infinite word is aperiodic if it is not ultimately periodic.

Fact 2.2 ([20]). An aperiodic word xx satisfies px(n)≥n+1p_x(n) \ge n+1 for all nn.

Definition 2.3 ([2]). An infinite word xx is Sturmian if px(n)=n+1p_x(n) = n+1 for all n≥0n \ge0.

Fact 2.4 ([2]). An infinite word xx is Sturmian if and only if it is aperiodic and balanced, that is, ∣∣u∣1−∣v∣1∣≤1||u|_1 - |v|_1| \le1 for any two factors u,vu,v of xx of equal length.

Fact 2.5 ([20]). Every Sturmian word has a frequency α\alpha of the letter 11, which is irrational and is called its slope. The set of finite factors of a Sturmian word depends only on α\alpha.

Definition 2.6 ([20]). Given an irrational α∈(0,1)\alpha\in(0,1), the characteristic word cαc_\alpha, called the standard word of slope α\alpha, is the unique Sturmian word of slope α\alpha all of whose prefixes uu have both 0u0u and 1u1u as factors.

The paper uses “standard Sturmian word” for cαc_\alpha.

Definition 2.7. A directive sequence is d=(d1,d2,d3,…)\mathbf{d} = (d_1,d_2,d_3,\ldots) with d1≥0d_1 \ge0 and di≥1d_i \ge1 for i≥2i \ge2. The standard words are

s−1=1,s0=0,sn=sn−1dnsn−2(n≥1).s_{-1}=1,\qquad s_0=0,\qquad s_n=s_{n-1}^{d_n}s_{n-2}\quad(n\ge1).

The word sns_n is a prefix of sn+1s_{n+1} for n≥1n \ge1.

From now on d1≥1d_1 \ge1, so that di≥1d_i \ge1 for all i≥1i \ge1. The sequence (sn)(s_n) converges to an infinite word cdc_{\mathbf{d}}, which is a standard Sturmian word, and every standard Sturmian word is obtained in this way [2]. The lengths are denoted ℓn=∣sn∣\ell_n = |s_n|, with ℓ−1=ℓ0=1\ell_{-1}=\ell_0=1 and ℓn=dnℓn−1+ℓn−2\ell_n=d_n\ell_{n-1}+\ell_{n-2} for n≥1n \ge1. The slope of cdc_{\mathbf{d}} has the continued fraction expansion [20]

α=[0;d1+1,d2,d3,…].(1)\alpha=[0;d_1+1,d_2,d_3,\ldots]. \tag*{(1)}

Definition 2.8 ([13]). A directive sequence d\mathbf{d} is purely periodic of period kk if di+k=did_{i+k}=d_i for all i≥1i \ge1. The notation d=(d1,…,dk)∞\mathbf{d}=(d_1,\ldots,d_k)^\infty is used with d1,…,dk≥1d_1,\ldots,d_k \ge1.

Remark 2.9 [14]. For purely periodic d\mathbf{d} the slope is α=[0;d1+1,(d2,…,dk,d1)∞]\alpha= [0; d_1 + 1, (d_2,\ldots,d_k,d_1)^\infty].

Definition 2.10. For a positive integer d\mathbf{d},

M(d)=(d110),Md=M(d1)M(d2)⋯M(dk).(2)M(d)=\begin{pmatrix} d & 1 \\ 1 & 0 \end{pmatrix}, \qquad M_{\mathbf{d}}=M(d_1)M(d_2)\cdots M(d_k). \tag*{(2)}

The matrix MdM_{\mathbf{d}} has determinant (−1)k(-1)^k and nonnegative integer entries, and some power of it is strictly positive. By the Perron–Frobenius theorem [15], MdM_{\mathbf{d}} has a simple eigenvalue λd>1\lambda_{\mathbf{d}}>1 of largest modulus. This growth constant λd\lambda_{\mathbf{d}} is a root of x2−tr⁡(Md)x+(−1)k=0x^2-\operatorname{tr}(M_{\mathbf{d}})x+(-1)^k=0.

Palindromic prefixes of standard Sturmian words

Definition 2.11. For an infinite word xx, L(x)L(x) denotes the set of lengths of the nonempty palindromic prefixes of xx, and πx(N)=#{n∈L(x):n≤N}\pi_x(N)=\#\{n\in L(x):n\leq N\} for N≥0N\geq0. For x=cdx=c_{\mathbf{d}} the notation πd(N)\pi_{\mathbf{d}}(N) is used.

Definition 2.12. The palindromic closure w(+)w^{(+)} of a finite word ww is the shortest palindrome having ww as a prefix.

Writing w=uvw=uv with vv the longest palindromic suffix of ww, the palindromic closure is w(+)=uvu~w^{(+)}=uv\widetilde{u}, and in particular it is unique. For a directive sequence d\mathbf{d} the directive word is

Δd=a1a2a3⋯=0d11d20d31d4⋯ ,(3)\Delta_{\mathbf{d}}=a_1a_2a_3\cdots=0^{d_1}1^{d_2}0^{d_3}1^{d_4}\cdots, \tag*{(3)}

in which block ii consists of did_i equal letters and the letters alternate from block to block. The words wmw_m are defined by w0=εw_0=\varepsilon and wm+1=(wmam+1)(+)w_{m+1}=(w_ma_{m+1})^{(+)} for m≥0m\geq0.

Theorem 2.13 [2, 5]. The word cdc_{\mathbf{d}} is the limit of the words wmw_m, and the palindromic prefixes of cdc_{\mathbf{d}} are exactly the words wmw_m with $m\geq 0.

The limit statement is Theorem 5 of [2], formulated there with the palindromic left closure and the recursion tn+1=(xntn)(−)t_{n+1}=(x_nt_n)^{(-)} over the alphabet {a,b}\{a,b\}. Droubay, Justin and Pirillo [5] define standard episturmian words by the right closure recursion. In [2] the directive sequence (q0,q1,…)(q_0,q_1,\ldots) satisfies qi−1=diq_{i-1}=d_i, with aa read as 0 and bb read as 1. The length set is

Λ(d)={jℓi−1+ℓi−2−2:i≥1, 1≤j≤di}.(4)\Lambda(\mathbf{d})=\{j\ell_{i-1}+\ell_{i-2}-2:i\geq1,\ 1\leq j\leq d_i\}. \tag*{(4)}

Let δm=∣wm∣\delta_m=|w_m|.

Lemma 2.14 [18]. Let x=am+1x=a_{m+1} for m≥0m\geq0. If xx does not occur in a1⋯ama_1\cdots a_m, then δm+1=2δm+1\delta_{m+1}=2\delta_m+1. Otherwise p=max⁡{q≤m:aq=x}p=\max\{q\leq m:a_q=x\} exists and δm+1=2δm−δp−1\delta_{m+1}=2\delta_m-\delta_{p-1}.

Lemma 2.14 is the length form of Justin’s formula (ux)(+)=uu′−1u(ux)^{(+)}=uu'^{-1}u, where u=u′xu′′u=u'xu'' and xx does not occur in u′′u'' [17]. It is equivalent to the relations un+1=unxnunu_{n+1}=u_nx_nu_n and un+1=unuP(n)−1unu_{n+1}=u_nu_{P(n)}^{-1}u_n of [18 p. 287] with un=wn−1u_n=w_{n-1}; see also [9 Def. 4.18], where ni=δi−1n_i=\delta_{i-1}.

Theorem 2.15 [9]. For every directive sequence d\mathbf{d} with di≥1d_i\geq1 for all i≥1i\geq1,

L(cd)=Λ(d)∖{0},(5)L(c_{\mathbf{d}})=\Lambda(\mathbf{d})\setminus\{0\}, \tag*{(5)}

where the value 0, attained only for i=1i=1 and j=1j=1, is the length of the empty prefix.

A derivation from Theorem 2.13, with the indexing of the lengths by the pairs (i,j)(i,j), is given in § 3.1.

Main results

This section has two parts. Subsection 3.1 derives the lengths of the palindromic prefixes of cdc_{\mathbf{d}} from the closure construction and shows that they are indexed bijectively by the pairs (i,j)(i,j). Subsection 3.2 uses this indexing to count the palindromic prefixes of length at most NN and proves the asymptotic formula for purely periodic d\mathbf{d}.

The length set of the palindromic prefixes

Throughout this subsection di≥1d_i \ge1 for all i≥1i \ge1, which holds automatically for every purely periodic d\mathbf{d} by Definition 2.8. In the length set Λ(d)\Lambda(\mathbf{d}) of (4) we write θi,j:=jℓi−1+ℓi−2−2\theta_{i,j} := j\ell_{i-1} + \ell_{i-2} - 2. The symbols D0=0D_0 = 0 and Di=d1+⋯+diD_i = d_1 + \cdots+ d_i mark the block boundaries of the directive word (3), in which block ii is the run of did_i equal letters at the positions Di−1+1,…,DiD_{i-1} + 1,\ldots,D_i. The words wmw_m are given by w0=εw_0 = \varepsilon and wm+1=(wmam+1)(+)w_{m+1} = (w_m a_{m+1})^{(+)}, and δm=∣wm∣\delta_m = |w_m|.

Since wmw_m is a proper prefix of wm+1w_{m+1}, the lengths satisfy δm<δm+1\delta_m < \delta_{m+1}, so the wmw_m are pairwise distinct and listed in increasing length. By Theorem 2.13,

L(cd)={δm:m≥1}.(6)L(\mathbf{c}_{\mathbf{d}}) = \{\delta_m : m \ge1\}. \tag*{(6)}

Lemma 3.1. (i) The map (i,j)↦m=Di−1+j−1(i,j) \mapsto m = D_{i-1} + j - 1 is a bijection from {(i,j):i≥1, 1≤j≤di}\{(i,j) : i \ge1,\ 1 \le j \le d_i\} onto N={0,1,2,…}\mathbb{N} = \{0,1,2,\ldots\}, and for the mm corresponding to (i,j)(i,j) the letter am+1a_{m+1} is the jj-th letter of block ii.

(ii) θi,j+1−θi,j=ℓi−1\theta_{i,j+1} - \theta_{i,j} = \ell_{i-1} for all i≥1i \ge1 and j≥1j \ge1.

(iii) θi,di+1=θi+1,1\theta_{i,d_i+1} = \theta_{i+1,1} and θi,di=ℓi−2\theta_{i,d_i} = \ell_i - 2 for all i≥1i \ge1.

(iv) θ1,1=0\theta_{1,1} = 0, and θi,j≥1\theta_{i,j} \ge1 for every other pair (i,j)(i,j).

Proof. For fixed ii the parameter jj runs through 1,…,di1,\ldots,d_i, so mm runs through Di−1,…,Di−1D_{i-1},\ldots,D_i-1, and these intervals partition N\mathbb{N}. The position m+1=Di−1+jm+1 = D_{i-1} + j is the jj-th position of block ii. This proves item (i). Item (ii) is immediate from the definition of θi,j\theta_{i,j}. Item (iii) follows from ℓi=diℓi−1+ℓi−2\ell_i = d_i\ell_{i-1} + \ell_{i-2}, which gives

θi,di=diℓi−1+ℓi−2−2=ℓi−2,θi,di+1=ℓi+ℓi−1−2=θi+1,1.(7)\theta_{i,d_i} = d_i\ell_{i-1} + \ell_{i-2} - 2 = \ell_i - 2,\qquad\theta_{i,d_i+1} = \ell_i + \ell_{i-1} - 2 = \theta_{i+1,1}. \tag*{(7)}

For item (iv), θ1,j=jℓ0+ℓ−1−2=j−1\theta_{1,j} = j\ell_0 + \ell_{-1} - 2 = j - 1, which is 00 only for j=1j = 1. Since ℓi≥ℓi−1+ℓi−2\ell_i \ge\ell_{i-1} + \ell_{i-2}, the sequence (ℓi)i≥−1(\ell_i)_{i \ge-1} is nondecreasing with ℓ−1=ℓ0=1\ell_{-1} = \ell_0 = 1, so for i≥2i \ge2 we have ℓi−1≥ℓ1=d1+1≥2\ell_{i-1} \ge\ell_1 = d_1 + 1 \ge2 and ℓi−2≥1\ell_{i-2} \ge1. Hence θi,j≥2+1−2=1\theta_{i,j} \ge2 + 1 - 2 = 1. □

Proposition 3.2. For every i≥1i \ge1 and 1≤j≤di1 \le j \le d_i, the index m=Di−1+j−1m = D_{i-1} + j - 1 satisfies δm=θi,j\delta_m = \theta_{i,j}.

Proof. We argue by induction on m≥0m \ge0. By Lemma 3.1, item (i), every m≥0m \ge0 corresponds to exactly one pair (i,j)(i,j). For m=0m = 0 this pair is (1,1)(1,1), and δ0=0=θ1,1\delta_0 = 0 = \theta_{1,1}. For the induction step the index m≥0m \ge0 corresponds to (i,j)(i,j), the claim holds for all indices up to mm, and x=am+1x = a_{m+1}. It suffices to show δm+1=θi,j+1\delta_{m+1} = \theta_{i,j+1}, because for j<dij < d_i the pair of m+1m+1 is (i,j+1)(i,j+1), and for j=dij = d_i the value θi,di+1\theta_{i,d_i+1} equals θi+1,1\theta_{i+1,1}, which is the value required for the pair (i+1,1)(i+1,1) of m+1m+1, by Lemma 3.1, item (iii).

If j≥2j \ge2, the letter ama_m lies in the same block as xx, so am=xa_m = x, the index pp of Lemma 2.14 equals mm, and δm+1=2δm−δm−1\delta_{m+1} = 2\delta_m - \delta_{m-1}. The index m−1m-1 corresponds to (i,j−1)(i,j-1), so the induction hypothesis and Lemma 3.1, item (ii) give

δm+1=2θi,j−θi,j−1=θi,j+ℓi−1=θi,j+1.(8)\delta_{m+1} = 2\theta_{i,j} - \theta_{i,j-1} = \theta_{i,j} + \ell_{i-1} = \theta_{i,j+1}. \tag*{(8)}

If j=1j = 1 and i=1i = 1, then m=0m = 0 and x=0x = 0 does not occur in the empty word, so δ1=2δ0+1=1\delta_1 = 2\delta_0 + 1 = 1 by Lemma 2.14, which equals θ1,2=2ℓ0+ℓ−1−2\theta_{1,2} = 2\ell_0 + \ell_{-1} - 2.

If j=1j = 1 and i=2i = 2, then m=D1=d1m = D_1 = d_1, the word a1⋯am=0d1a_1 \cdots a_m = 0^{d_1} contains no letter 11, and x=1x = 1. Lemma 2.14 and the induction hypothesis give δm+1=2θ2,1+1\delta_{m+1} = 2\theta_{2,1} + 1, and θ2,1=ℓ1+ℓ0−2=d1\theta_{2,1} = \ell_1 + \ell_0 - 2 = d_1 gives

δm+1=2d1+1=2ℓ1+ℓ0−2=θ2,2.\delta_{m+1} = 2d_1 + 1 = 2\ell_1 + \ell_0 - 2 = \theta_{2,2}.

If j=1j = 1 and i≥3i \ge3, then m=Di−1m = D_{i-1}, and xx is the letter of block ii, which is also the letter of block i−2i-2 and differs from the letter of block i−1i-1. The last occurrence of xx in a1⋯ama_1 \cdots a_m is therefore the last position of block i−2i-2, so p=Di−2p = D_{i-2} in Lemma 2.14. Then p−1=Di−3+di−2−1p-1 = D_{i-3} + d_{i-2} - 1 corresponds to the pair (i−2,di−2)(i-2,d_{i-2}), and p−1<mp-1 < m, so the induction hypothesis and Lemma 3.1, item (iii) give δp−1=θi−2,di−2=ℓi−2−2\delta_{p-1} = \theta_{i-2,d_{i-2}} = \ell_{i-2} - 2. Thus,

δm+1=2θi,1−(ℓi−2−2)=2(ℓi−1+ℓi−2−2)−ℓi−2+2=2ℓi−1+ℓi−2−2=θi,2.(9)\delta_{m+1} = 2\theta_{i,1} - (\ell_{i-2} - 2) = 2(\ell_{i-1} + \ell_{i-2} - 2) - \ell_{i-2} + 2 = 2\ell_{i-1} + \ell_{i-2} - 2 = \theta_{i,2}. \tag*{(9)}

The four situations cover every pair (i,j)(i,j), which completes the induction. □

Corollary 3.3. The map (i,j)↦θi,j(i,j) \mapsto\theta_{i,j} is injective on {(i,j):i≥1, 1≤j≤di}\{(i,j) : i \ge1,\ 1 \le j \le d_i\}, and its image is Λ(d)\Lambda(\mathbf{d}). Consequently each length in L(cd)L(\mathbf{c}_{\mathbf{d}}) is attained by exactly one pair (i,j)≠(1,1)(i,j) \ne(1,1), and L(cd)=Λ(d)∖{0}L(\mathbf{c}_{\mathbf{d}}) = \Lambda(\mathbf{d}) \setminus\{0\}.

Proof. By Lemma 3.1, item (i), the pairs correspond bijectively to the indices m≥0m \ge0, and by Proposition 3.2 the pair of mm has θi,j=δm\theta_{i,j} = \delta_m. Since δm<δm+1\delta_m < \delta_{m+1} for all m≥0m \ge0, the values δm\delta_m are pairwise distinct, so the map is injective. By Lemma 3.1, item (iv), the value 00 occurs only for (1,1)(1,1), and (6) gives the last statement. □

Asymptotic count of palindromic prefixes

The sequence d=(d1,…,dk)∞\mathbf{d} = (d_1,\ldots,d_k)^\infty is purely periodic of period kk, so di≥1d_i \ge1 and di+k=did_{i+k} = d_i for all i≥1i \ge1. The symbol SS stands for d1+⋯+dkd_1+\cdots+d_k. The only facts about palindromic prefixes used below are (6), Proposition 3.2 and Corollary 3.3. By (6), πd(N)=#{m≥1:δm≤N}\pi_{\mathbf d}(N) = \#\{m \ge1 : \delta_m \le N\}. By Lemma 3.1 (i), the map (i,j)↦m=Di−1+j−1(i,j) \mapsto m = D_{i-1}+j-1 is a bijection from {(i,j):i≥1,1≤j≤di}\{(i,j): i \ge1, 1 \le j \le d_i\} onto N\mathbb{N}, under which (1,1)(1,1) corresponds to m=0m=0, and by Proposition 3.2, δm=θi,j\delta_m = \theta_{i,j} for the corresponding pair. By Corollary 3.3, the pairs and the lengths correspond one to one. Therefore

πd(N)=#{(i,j):i≥1, 1≤j≤di, (i,j)≠(1,1), θi,j≤N},θi,j=jℓi−1+ℓi−2−2.\pi_{\mathbf d}(N)=\#\{(i,j): i\ge1,\ 1\le j\le d_i,\ (i,j)\ne(1,1),\ \theta_{i,j}\le N\},\qquad\theta_{i,j}=j\ell_{i-1}+\ell_{i-2}-2.

Theorem 3.4. For every purely periodic d\mathbf d of period kk,

πd(N)∼d1+⋯+dklog⁡λdlog⁡N.(10)\pi_{\mathbf d}(N)\sim\frac{d_1+\cdots+d_k}{\log\lambda_{\mathbf d}}\log N. \tag*{(10)}

Proof. The vectors vn=(ℓn,ℓn−1)Tv_n=(\ell_n,\ell_{n-1})^T satisfy v0=(1,1)Tv_0=(1,1)^T and vn=M(dn)vn−1v_n=M(d_n)v_{n-1} for n≥1n\ge1. Since dpk+s=dsd_{pk+s}=d_s for 1≤s≤k1\le s\le k, the product M(dqk)M(dqk−1)⋯M(d1)M(d_{qk})M(d_{qk-1})\cdots M(d_1) is the qq-th power of B=M(dk)⋯M(d1)B=M(d_k)\cdots M(d_1), and therefore vqk=Bqv0v_{qk}=B^qv_0. Each M(d)M(d) is symmetric with determinant −1-1, so BB is the transpose of MdM_{\mathbf d}, with det⁡B=(−1)k\det B=(-1)^k and tr⁡B=t\operatorname{tr}B=t, where tt denotes tr⁡Md\operatorname{tr}M_{\mathbf d}. The Cayley–Hamilton theorem gives B2=tB−(−1)kIB^2=tB-(-1)^kI. Multiplying by Bqv0B^qv_0 and reading the first coordinate gives

yq+2=tyq+1−(−1)kyq,(11)y_{q+2}=ty_{q+1}-(-1)^ky_q, \tag*{(11)}

for q≥0q\ge0, where yq:=ℓqky_q:=\ell_{qk}, y0=1y_0=1 and y1=ℓky_1=\ell_k. The matrices An=M(d1)⋯M(dn)A_n=M(d_1)\cdots M(d_n), with A0=IA_0=I, are written

An=(PnPn−1QnQn−1),P−1=0, P0=1, Q−1=1, Q0=0.A_n=\begin{pmatrix}P_n&P_{n-1}\\Q_n&Q_{n-1}\end{pmatrix},\qquad P_{-1}=0,\ P_0=1,\ Q_{-1}=1,\ Q_0=0.

The relation An=An−1M(dn)A_n=A_{n-1}M(d_n) gives, for all n≥1n\ge1,

Pn=dnPn−1+Pn−2,Qn=dnQn−1+Qn−2.(12)P_n=d_nP_{n-1}+P_{n-2},\qquad Q_n=d_nQ_{n-1}+Q_{n-2}. \tag*{(12)}

Since P1=d1≥1P_1=d_1\ge1 and Q1=1Q_1=1, induction on nn gives Pn≥1P_n\ge1 for n≥0n\ge0 and Qn≥1Q_n\ge1 for n≥1n\ge1. Since Ak=MdA_k=M_{\mathbf d}, the trace is t=Pk+Qk−1t=P_k+Q_{k-1}. We claim that

t≥1for every k≥1,t≥3 if k≥2.(13)t\ge1\quad\text{for every }k\ge1,\qquad t\ge3\text{ if }k\ge2. \tag*{(13)}

For k=1k=1 we have t=P1+Q0=d1≥1t=P_1+Q_0=d_1\ge1. For k≥2k\ge2, (12) gives Pk=dkPk−1+Pk−2≥Pk−1+Pk−2≥2P_k=d_kP_{k-1}+P_{k-2}\ge P_{k-1}+P_{k-2}\ge2 and Qk−1≥1Q_{k-1}\ge1, hence t≥3t\ge3. The polynomial f(x)=x2−tx+(−1)kf(x)=x^2-tx+(-1)^k satisfies f(1)=1−t+(−1)kf(1)=1-t+(-1)^k. If kk is odd, then f(1)=−t<0f(1)=-t<0 by the first part of (13). If kk is even, then k≥2k\ge2, and f(1)=2−t<0f(1)=2-t<0 by the second part of (13). In both cases f(1)<0f(1)<0. Consequently ff has two real roots with 11 strictly between them. The larger root λ\lambda exceeds 11, and the other root is μ=(−1)k/λ\mu=(-1)^k/\lambda, ∣μ∣=1/λ<1|\mu|=1/\lambda<1 and λ≠μ\lambda\ne\mu. Both roots are eigenvalues of MdM_{\mathbf d}, since ff is its characteristic polynomial, and λ\lambda has the larger modulus. Thus, λ=λd\lambda=\lambda_{\mathbf d}.

The sequence ℓn\ell_n is strictly increasing for n≥0n\ge0: for n≥1n\ge1 it holds that ℓn=dnℓn−1+ℓn−2≥ℓn−1+ℓn−2>ℓn−1\ell_n=d_n\ell_{n-1}+\ell_{n-2}\ge\ell_{n-1}+\ell_{n-2}>\ell_{n-1}, where ℓn−2≥1\ell_{n-2}\ge1 and ℓ−1=ℓ0=1\ell_{-1}=\ell_0=1. Since λ≠μ\lambda\ne\mu, there are constants κ1,κ2\kappa_1,\kappa_2 with κ1+κ2=1\kappa_1+\kappa_2=1 and κ1λ+κ2μ=ℓk\kappa_1\lambda+\kappa_2\mu=\ell_k. The sequence κ1λq+κ2μq\kappa_1\lambda^q+\kappa_2\mu^q has the same first two terms as yqy_q and satisfies the same recurrence, because λ2=tλ−(−1)k\lambda^2=t\lambda-(-1)^k and μ2=tμ−(−1)k\mu^2=t\mu-(-1)^k. Therefore

yq=ℓqk=κ1λq+κ2μqfor all q≥0.(14)y_q=\ell_{qk}=\kappa_1\lambda^q+\kappa_2\mu^q\qquad\text{for all }q\ge0. \tag*{(14)}

Subtracting μ\mu times the equation κ1+κ2=1\kappa_1+\kappa_2=1 from κ1λ+κ2μ=ℓk\kappa_1\lambda+\kappa_2\mu=\ell_k gives κ1(λ−μ)=ℓk−μ\kappa_1(\lambda-\mu)=\ell_k-\mu. Since λ−μ>0\lambda-\mu>0 and ℓk≥ℓ1=d1+1≥2>∣μ∣\ell_k\ge\ell_1=d_1+1\ge2>|\mu|, we get κ1>0\kappa_1>0. Thus, from (14),

ℓqk=κ1λq(1+κ2κ1(μλ)q),andlog⁡ℓqkq⟶log⁡λ(q→∞),(15)\ell_{qk}=\kappa_1\lambda^q\left(1+\frac{\kappa_2}{\kappa_1}\left(\frac{\mu}{\lambda}\right)^q\right),\qquad\text{and}\qquad\frac{\log\ell_{qk}}{q}\longrightarrow\log\lambda\quad(q\to\infty), \tag*{(15)}

where ∣μ/λ∣<1|\mu/\lambda|<1. For n≥kn\ge k the integer q=⌊n/k⌋q=\lfloor n/k\rfloor satisfies qk≤n<(q+1)kqk\le n<(q+1)k, and monotonicity of ℓn\ell_n gives ℓqk≤ℓn≤ℓ(q+1)k\ell_{qk}\le\ell_n\le\ell_{(q+1)k}. Therefore

log⁡ℓqkq⋅q(q+1)k≤log⁡ℓnn≤log⁡ℓ(q+1)kq+1⋅q+1qk.(16)\frac{\log\ell_{qk}}{q}\cdot\frac{q}{(q+1)k}\le\frac{\log\ell_n}{n}\le\frac{\log\ell_{(q+1)k}}{q+1}\cdot\frac{q+1}{qk}. \tag*{(16)}

and both bounds tend to (log⁡λ)/k(\log\lambda)/k as n→∞n\to\infty. Thus, (15) and (16) give

lim⁡n→∞log⁡ℓnn=log⁡λdk.(17)\lim_{n\to\infty}\frac{\log\ell_n}{n}=\frac{\log\lambda_d}{k}. \tag*{(17)}

For N≥0N\ge0 the index I=I(N)=max⁡{i≥0:ℓi≤N+2}I=I(N)=\max\{i\ge0:\ell_i\le N+2\} exists, since ℓ0=1\ell_0=1 and ℓi→∞\ell_i\to\infty, and I(N)→∞I(N)\to\infty as N→∞N\to\infty. For NN large enough that I≥1I\ge1, the definition of II gives ℓI≤N+2<ℓI+1\ell_I\le N+2<\ell_{I+1},

log⁡ℓII≤log⁡(N+2)I<log⁡ℓI+1I+1⋅I+1I.(18)\frac{\log\ell_I}{I}\le\frac{\log(N+2)}{I}<\frac{\log\ell_{I+1}}{I+1}\cdot\frac{I+1}{I}. \tag*{(18)}

Both outer terms tend to (log⁡λ)/k(\log\lambda)/k. Thus, I(N)/log⁡(N+2)→k/log⁡λI(N)/\log(N+2)\to k/\log\lambda, and since log⁡(N+2)/log⁡N→1\log(N+2)/\log N\to1,

I(N)log⁡N⟶klog⁡λ.\frac{I(N)}{\log N}\longrightarrow\frac{k}{\log\lambda}.

The set of pairs counted by πd(N)\pi_d(N) is bounded from both sides as follows. For 1≤i≤I1\le i\le I and 1≤j≤di1\le j\le d_i, the identity θi,j+1−θi,j=ℓi−1>0\theta_{i,j+1}-\theta_{i,j}=\ell_{i-1}>0 gives θi,j≤θi,di=ℓi−2≤ℓI−2≤N\theta_{i,j}\le\theta_{i,d_i}=\ell_i-2\le\ell_I-2\le N. Hence every pair with i≤Ii\le I is counted, except (1,1)(1,1), and

πd(N)≥∑i=1Idi−1.(19)\pi_d(N)\ge\sum_{i=1}^{I}d_i-1. \tag*{(19)}

In the other direction, let (i,j)(i,j) be a pair with θi,j≤N\theta_{i,j}\le N. Since θi,1≤θi,j\theta_{i,1}\le\theta_{i,j}, we get ℓi−1+ℓi−2−2≤N\ell_{i-1}+\ell_{i-2}-2\le N, hence ℓi−1≤N+2\ell_{i-1}\le N+2, and so i−1≤Ii-1\le I by the definition of II. Thus every counted pair has i≤I+1i\le I+1, and

πd(N)≤∑i=1I+1di.(20)\pi_d(N)\le\sum_{i=1}^{I+1}d_i. \tag*{(20)}

Periodicity of dd gives ∑i=1mdi=S⌊m/k⌋+rm\sum_{i=1}^{m}d_i=S\lfloor m/k\rfloor+r_m with 0≤rm≤S0\le r_m\le S, so ∣∑i=1mdi−Sm/k∣≤S\left|\sum_{i=1}^{m}d_i-Sm/k\right|\le S for every m≥0m\ge0. Together with (19) and (20),

SIk−S−1≤πd(N)≤S(I+1)k+S.(21)\frac{SI}{k}-S-1\le\pi_d(N)\le\frac{S(I+1)}{k}+S. \tag*{(21)}

Divide (21) by log⁡N\log N and use I(N)/log⁡N→k/log⁡λdI(N)/\log N\to k/\log\lambda_d. Both outer terms then tend to S/log⁡λdS/\log\lambda_d, since Sk⋅klog⁡λd=Slog⁡λd\frac{S}{k}\cdot\frac{k}{\log\lambda_d}=\frac{S}{\log\lambda_d}. Hence

πd(N)log⁡N⟶Slog⁡λd,(22)\frac{\pi_d(N)}{\log N}\longrightarrow\frac{S}{\log\lambda_d}, \tag*{(22)}

which is (10). □

Corollary 3.5. For every purely periodic dd of period kk,

πd(N)=Slog⁡λdlog⁡N+O(1).\pi_d(N)=\frac{S}{\log\lambda_d}\log N+O(1).

Proof. By (14) and κ1>0\kappa_1 > 0, there are constants c1,c2>0c_1, c_2 > 0 with c1λq≤ℓqk≤c2λqc_1\lambda^q \le\ell_{qk} \le c_2\lambda^q for all q≥0q \ge0, where λ=λd\lambda= \lambda_d. For n≥0n \ge0 and q=⌊n/k⌋q = \lfloor n/k \rfloor, monotonicity of ℓn\ell_n gives ℓqk≤ℓn≤ℓ(q+1)k\ell_{qk} \le\ell_n \le\ell_{(q+1)k}, and λn/k−1<λq≤λn/k\lambda^{n/k-1} < \lambda^q \le\lambda^{n/k}. Hence C1λn/k≤ℓn≤C2λn/kC_1\lambda^{n/k} \le\ell_n \le C_2\lambda^{n/k} with C1=c1/λC_1 = c_1/\lambda and C2=c2λC_2 = c_2\lambda. From ℓI≤N+2<ℓI+1\ell_I \le N + 2 < \ell_{I+1} we obtain

C1λI/k≤N+2,N+2<C2λ(I+1)/k.C_1\lambda^{I/k} \le N + 2,\qquad N + 2 < C_2\lambda^{(I+1)/k}.

that is,

klog⁡((N+2)/C2)log⁡λ−1<I≤klog⁡((N+2)/C1)log⁡λ.\frac{k\log((N+2)/C_2)}{\log\lambda}-1 < I \le\frac{k\log((N+2)/C_1)}{\log\lambda}.

Since log⁡(N+2)−log⁡N≤log⁡3\log(N+2)-\log N \le\log3 for N≥1N \ge1, there is a constant CC with ∣I(N)−klog⁡N/log⁡λ∣≤C|I(N)-k\log N/\log\lambda| \le C for all N≥1N \ge1. Substituting this into (21) gives

Slog⁡λlog⁡N−SCk−S−1≤πd(N)≤Slog⁡λlog⁡N+SCk+Sk+S,\frac{S}{\log\lambda}\log N-\frac{SC}{k}-S-1 \le\pi_d(N) \le\frac{S}{\log\lambda}\log N+\frac{SC}{k}+\frac{S}{k}+S,

which proves the claim. □

Discussion

The description of the lengths of palindromic prefixes in Theorem 2.15 agrees with the one stated in § 3.1 of Fischler’s study of palindromic prefixes [9], where it is attributed to de Luca [2] and to Droubay, Justin and Pirillo [5]. § 3.1 derives it directly from the closure recursion and adds the explicit bijection (i,j)↦m(i,j)\mapsto m of Lemma 3.1 and Corollary 3.3, which is what makes the counting possible. The content specific to this paper is the counting statement. We are not aware of an earlier statement of the asymptotic formula for πd(N)\pi_d(N).

In the literature the abundance of palindromic prefixes is measured by lim sup⁡ni+1/ni\limsup n_{i+1}/n_i, where nin_i is the length of the ii-th palindromic prefix [9]. By Proposition 3.2, the ratios of consecutive lengths are governed by the quotients ℓi−2/ℓi−1=[0;di−1,…,d2,d1+1]\ell_{i-2}/\ell_{i-1}=[0;d_{i-1},\ldots,d_2,d_1+1], so this quantity records the largest relative gap between consecutive palindromic prefixes and depends on the extreme values of the directive sequence. The count πd(N)\pi_d(N) takes all gaps into account, and its constant S/log⁡λdS/\log\lambda_d depends on d\mathbf{d} in a different way.

This constant is the ratio of S/kS/k, the mean of d1,…,dkd_1,\ldots,d_k, to (log⁡λd)/k(\log\lambda_d)/k, the exponential growth rate of ℓn\ell_n per index, by (17). It is not a function of the mean alone, because λd\lambda_d depends on the order of d1,…,dkd_1,\ldots,d_k and not only on their sum. For d=(2,2)∞\mathbf{d}=(2,2)^\infty we have λd=(1+2)2\lambda_d=(1+\sqrt{2})^2 and the constant is 2/log⁡(1+2)≈2.272/\log(1+\sqrt{2})\approx2.27, while for d=(1,3)∞\mathbf{d}=(1,3)^\infty we have λd=(5+21)/2\lambda_d=(5+\sqrt{21})/2 and the constant is 4/log⁡((5+21)/2)≈2.554/\log((5+\sqrt{21})/2)\approx2.55, although both sequences have mean 2. Replacing kk by mkmk multiplies SS by mm and replaces MdM_d by MdmM_d^m, so log⁡λd\log\lambda_d is also multiplied by mm, and the constant does not depend on the choice of period. For d=(1)∞\mathbf{d}=(1)^\infty the theorem gives πd(N)∼log⁡N/log⁡φ\pi_d(N)\sim\log N/\log\varphi with φ=(1+5)/2\varphi=(1+\sqrt{5})/2.

Periodicity enters the proof of Theorem 3.4 only through (17) and the bounded oscillation of the partial sums of did_i. The remaining steps hold for every directive sequence, which gives the following statement.

Proposition 4.1. Let d\mathbf{d} be a directive sequence with di≥1d_i\ge1 for all i≥1i\ge1, and let I(N)=max⁡{i≥0:ℓi≤N+2}I(N)=\max\{i\ge0:\ell_i\le N+2\}. Then

∑i≤I(N)(di−1)≤πd(N)≤∑i≤I(N)+1di.\sum_{i\le I(N)}(d_i-1)\le\pi_d(N)\le\sum_{i\le I(N)+1}d_i.

If log⁡ℓnn→ρ>0\frac{\log\ell_n}{n}\to\rho>0 and 1n∑i≤ndi→d‾∈(0,∞)\frac{1}{n}\sum_{i\le n}d_i\to\overline{d}\in(0,\infty), then πd(N)∼(d‾/ρ)log⁡N\pi_d(N)\sim(\overline{d}/\rho)\log N.

Proof. The two bounds are (19) and (20), whose proofs use only Lemma 3.1 and the monotonicity of ℓn\ell_n. By (18) and the assumption on log⁡ℓn/n\log\ell_n/n, we get I(N)/log⁡N→1/ρI(N)/\log N\to1/\rho. Since ∑i≤Idi=(d‾+o(1))I\sum_{i\le I}d_i=(\overline{d}+o(1))I, dividing the bounds by log⁡N\log N gives the claim. □

The error term in Corollary 3.5 cannot be improved to o(1)o(1). Indeed, the lengths θi,j\theta_{i,j} are pairwise distinct by Corollary 3.3, so πd(N)\pi_{\mathbf d}(N) increases by exactly 1 at each of them, while Slog⁡λdlog⁡N\frac{S}{\log\lambda_{\mathbf d}}\log N changes by o(1)o(1) across such a point. Hence the difference πd(N)−Slog⁡λdlog⁡N\pi_{\mathbf d}(N)-\frac{S}{\log\lambda_{\mathbf d}}\log N has no limit.

Finally, the periodic case is special. For n≥1n \ge1 the number ℓn\ell_n is the denominator of the nn-th convergent of α=[0;d1+1,d2,…]\alpha=[0;d_1+1,d_2,\ldots], so by Lévy’s theorem we have log⁡ℓn/n→ρ=π212log⁡2\log\ell_n/n \to\rho=\frac{\pi^2}{12\log2} for almost every α∈(0,1/2)\alpha\in(0,1/2) [16, 1]. By the Borel–Bernstein theorem [16], for almost every α\alpha the inequality dn≥nlog⁡nd_n \ge n\log n holds for infinitely many nn. For such nn and N=ℓn−2N=\ell_n-2 we have I(N)=nI(N)=n, so Proposition 4.1 gives πd(N)≥dn−1≥nlog⁡n−1\pi_{\mathbf d}(N) \ge d_n-1 \ge n\log n-1, while log⁡N<log⁡ℓn∼ρn\log N < \log\ell_n \sim\rho n. Hence πd(N)/log⁡N\pi_{\mathbf d}(N)/\log N is unbounded, and no asymptotic of the form Clog⁡NC\log N holds for such d\mathbf d.

Conclusion

We derived the lengths of the palindromic prefixes of a standard Sturmian word cdc_{\mathbf d} with directive sequence d\mathbf d, where di≥1d_i \ge1 for all i≥1i \ge1, directly from the construction by iterated palindromic closure. They are the numbers jℓi−1+ℓi−2−2j\ell_{i-1}+\ell_{i-2}-2 with i≥1i \ge1 and 1≤j≤di1 \le j \le d_i, where ℓn\ell_n is the length of the nn-th standard word. The value 0 occurs only for (i,j)=(1,1)(i,j)=(1,1) and corresponds to the empty prefix, and every nonzero length is attained by exactly one pair (i,j)(i,j). The proof tracks the lengths of the closures through the block boundaries of the directive word Δd\Delta_{\mathbf d}.

For a purely periodic directive sequence d=(d1,…,dk)∞\mathbf d=(d_1,\ldots,d_k)^\infty, the counting function πd(N)\pi_{\mathbf d}(N) of nonempty palindromic prefixes of length at most NN satisfies

πd(N)∼d1+⋯+dklog⁡λdlog⁡N\pi_{\mathbf d}(N)\sim\frac{d_1+\cdots+d_k}{\log\lambda_{\mathbf d}}\log N

where λd\lambda_{\mathbf d} is the largest eigenvalue of M(d1)⋯M(dk)M(d_1)\cdots M(d_k). More precisely, Corollary 3.5 gives πd(N)=d1+⋯+dklog⁡λdlog⁡N+O(1)\pi_{\mathbf d}(N)=\frac{d_1+\cdots+d_k}{\log\lambda_{\mathbf d}}\log N+O(1), and this error term cannot be improved to o(1)o(1). The constant does not depend on the choice of period, and for the Fibonacci word it equals 1/log⁡φ1/\log\varphi. The argument rests on two ingredients, the exponential growth of ℓn\ell_n governed by λd\lambda_{\mathbf d} and the bounded oscillation of the partial sums of did_i over one period. The constant is determined by the sum of the did_i over one period together with the growth rate of ℓn\ell_n, and not by the mean of the did_i alone. It differs in nature from the quantity lim sup⁡ni+1/ni\limsup n_{i+1}/n_i, which is governed by the extreme values of the quotients ℓi−2/ℓi−1\ell_{i-2}/\ell_{i-1}.

Proposition 4.1 extends the counting argument to arbitrary directive sequences with di≥1d_i \ge1, and together with the Borel–Bernstein theorem shows that πd(N)/log⁡N\pi_{\mathbf d}(N)/\log N is unbounded for almost every slope. Jasem Hamoud: Moscow Institute of Physics and Technology

Email address: [email protected]

References

  1. [1]K. Dajani, C. Kraaikamp, Ergodic theory of numbers, Carus Mathematical Monographs 29, Mathematical Association of America, Washington, DC, 2002.
  2. [2]A. de Luca, Sturmian words: structure, combinatorics, and their arithmetics, Theoret. Comput. Sci. 183(1) (1997), 45–82.DOI
  3. [3]A. de Luca, G. Fici, Open and closed prefixes of Sturmian words, in: Combinatorics on Words, WORDS 2013, Lecture Notes in Computer Science 8079, Springer, Berlin, Heidelberg, 2013, pp. 132–142.DOI
  4. [4]A. de Luca, G. Fici, L. Q. Zamboni, The sequence of open and closed prefixes of a Sturmian word, Adv. in Appl. Math. 90 (2017), 27–45.DOI
  5. [5]X. Droubay, J. Justin, G. Pirillo, Episturmian words and some constructions de Luca and Rauzy, Theoret. Comput. Sci. 255 (2001), 539–553.DOI
  6. [6]L. Dvořáková, String attractors of episturmian sequences, arXiv:2211.01660 (2022).arxiv.org/abs/2211.01660
  7. [7]L. Dvořáková, V. Hendrychová, String attractors of Rote sequences, Discrete Math. Theor. Comput. Sci. 26(3) (2024), #2, doi:10.46298/dmtcs.12385.DOI
  8. [8]G. Fici, J. Shallit, J. Simpson, Some remarks on palindromic periodicities, arXiv:2407.10564 (2024).arxiv.org/abs/2407.10564
  9. [9]S. Fischler, Palindromic prefixes and episturmian words, J. Combin. Theory Ser. A 113(7) (2006), 1281–1304.arxiv.org/abs/math/0501420
  10. [10]S. Fischler, Palindromic prefixes and diophantine approximation, Monatsh. Math. 151 (2007), 11–37.arxiv.org/abs/math/0509508
  11. [11]D. Gabric, On the properties and structure of bordered words and generalizations, Ph.D. thesis, University of Waterloo, 2022.
  12. [12]A. Glen, On Sturmian and episturmian words, and related topics, Ph.D. thesis, The University of Adelaide, Australia, 2006.
  13. [13]A. Glen, F. Lévé, G. Richomme, Directive words of episturmian words: equivalences and normalization, RAIRO Theor. Inform. Appl. 43 (2009), 299–319.DOI
  14. [14]G. H. Hardy, E. M. Wright, An introduction to the theory of numbers, 6th edition, Oxford University Press, Oxford, 2008.
  15. [15]R. A. Horn, C. R. Johnson, Matrix analysis, 2nd edition, Cambridge University Press, Cambridge, 2013.
  16. [16]M. Iosifescu, C. Kraaikamp, Metrical theory of continued fractions, Mathematics and Its Applications 547, Kluwer Academic Publishers, Dordrecht, 2002.
  17. [17]J. Justin, Episturmian morphisms and a Galois theorem on continued fractions, RAIRO Theor. Inform. Appl. 39(1) (2005), 207–215.DOI
  18. [18]J. Justin, G. Pirillo, Episturmian words and episturmian morphisms, Theoret. Comput. Sci. 276 (2002), 281–313.DOI
  19. [19]S. Li, N. Rampersad, Purely automatic sequences with the uniform distribution property, in: Combinatorics on Words, WORDS 2025, Springer Nature Switzerland, Cham, 15729 2025, pp. 205–216.
  20. [20]M. Lothaire, Algebraic combinatorics on words, Encyclopedia of Mathematics and its Applications 90, Cambridge University Press, Cambridge, 2002.DOI
  21. [21]J. Peltomäki, M. Whiteland, A square root map on Sturmian words, in: Combinatorics on Words, WORDS 2015, Lecture Notes in Computer Science 9304, Springer, Cham, 2015, pp. 197–209.
  22. [22]J. Rukavicka, Palindromic length and reduction of powers, Theoret. Comput. Sci. 930 (2022), 106–115.DOI
  23. [23]J. Rukavicka, Palindromic length of infinite aperiodic words, European J. Combin. 131 (2026), 104237.arxiv.org/abs/2410.12714

Paper details

vlnc:W_w6myfryb
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents