WorksMathematics
Lengths and Counting of Palindromic Prefixes of Standard Sturmian Words
Abstract
Every standard Sturmian word is determined by a directive sequence of positive integers, and its palindromic prefixes are obtained by iterated palindromic closure. We describe the lengths of these prefixes by the numbers , where is the length of the -th standard word and , and we show that each nonzero length is attained by exactly one pair . For a purely periodic directive sequence of period we then prove that the number of nonempty palindromic prefixes of length at most satisfies where is the largest eigenvalue of the matrix . For the Fibonacci word this gives , where .
where is the largest eigenvalue of the matrix . For the Fibonacci word this gives , where .
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 of a finite word , that is, the shortest palindrome having 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 , , defined by , where is the directive word. They also showed that this recurrence can be written as if does not occur in , and otherwise, with the last earlier position of [18]. On a two-letter alphabet the directive word gives the characteristic Sturmian word of slope [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 , and how does this number grow with ?
The goal of the paper is to study the palindromic prefixes of standard Sturmian words through their directive sequences . We first rederive the lengths of these prefixes as the numbers , indexed by pairs with , where is the length of the -th standard word. We then use this description to count them: for a purely periodic directive sequence , we determine the asymptotic behaviour of the number of nonempty palindromic prefixes of length at most in terms of and the largest eigenvalue of .
This paper is organized as follows. § 2 fixes the notation and recalls Sturmian and standard words, the construction of 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 . Subsection 3.2 proves the asymptotic formula for 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 . We denote by the set of finite words and by the empty word. The length of a word is written , and denotes the number of occurrences of the letter in . A word is a factor of if for some words ; it is a prefix if and a suffix if . For a word and an integer , is the word repeated times, with . The reversal of is , and is a palindrome if , the empty word and single letters being palindromes. A prefix of a word that is a palindrome is called a palindromic prefix of . Regarding asymptotics, means that as , and all logarithms are natural.
Sturmian words and standard words
Definition 2.1 ([12]). The complexity of an infinite word is , the number of distinct factors of length . An infinite word is aperiodic if it is not ultimately periodic.
Fact 2.2 ([20]). An aperiodic word satisfies for all .
Definition 2.3 ([2]). An infinite word is Sturmian if for all .
Fact 2.4 ([2]). An infinite word is Sturmian if and only if it is aperiodic and balanced, that is, for any two factors of of equal length.
Fact 2.5 ([20]). Every Sturmian word has a frequency of the letter , which is irrational and is called its slope. The set of finite factors of a Sturmian word depends only on .
Definition 2.6 ([20]). Given an irrational , the characteristic word , called the standard word of slope , is the unique Sturmian word of slope all of whose prefixes have both and as factors.
The paper uses “standard Sturmian word” for .
Definition 2.7. A directive sequence is with and for . The standard words are
The word is a prefix of for .
From now on , so that for all . The sequence converges to an infinite word , which is a standard Sturmian word, and every standard Sturmian word is obtained in this way [2]. The lengths are denoted , with and for . The slope of has the continued fraction expansion [20]
Definition 2.8 ([13]). A directive sequence is purely periodic of period if for all . The notation is used with .
Remark 2.9 [14]. For purely periodic the slope is .
Definition 2.10. For a positive integer ,
The matrix has determinant and nonnegative integer entries, and some power of it is strictly positive. By the Perron–Frobenius theorem [15], has a simple eigenvalue of largest modulus. This growth constant is a root of .
Palindromic prefixes of standard Sturmian words
Definition 2.11. For an infinite word , denotes the set of lengths of the nonempty palindromic prefixes of , and for . For the notation is used.
Definition 2.12. The palindromic closure of a finite word is the shortest palindrome having as a prefix.
Writing with the longest palindromic suffix of , the palindromic closure is , and in particular it is unique. For a directive sequence the directive word is
in which block consists of equal letters and the letters alternate from block to block. The words are defined by and for .
Theorem 2.13 [2, 5]. The word is the limit of the words , and the palindromic prefixes of are exactly the words with $m\geq 0.
The limit statement is Theorem 5 of [2], formulated there with the palindromic left closure and the recursion over the alphabet . Droubay, Justin and Pirillo [5] define standard episturmian words by the right closure recursion. In [2] the directive sequence satisfies , with read as 0 and read as 1. The length set is
Let .
Lemma 2.14 [18]. Let for . If does not occur in , then . Otherwise exists and .
Lemma 2.14 is the length form of Justin’s formula , where and does not occur in [17]. It is equivalent to the relations and of [18 p. 287] with ; see also [9 Def. 4.18], where .
Theorem 2.15 [9]. For every directive sequence with for all ,
where the value 0, attained only for and , is the length of the empty prefix.
A derivation from Theorem 2.13, with the indexing of the lengths by the pairs , is given in § 3.1.
Main results
This section has two parts. Subsection 3.1 derives the lengths of the palindromic prefixes of from the closure construction and shows that they are indexed bijectively by the pairs . Subsection 3.2 uses this indexing to count the palindromic prefixes of length at most and proves the asymptotic formula for purely periodic .
The length set of the palindromic prefixes
Throughout this subsection for all , which holds automatically for every purely periodic by Definition 2.8. In the length set of (4) we write . The symbols and mark the block boundaries of the directive word (3), in which block is the run of equal letters at the positions . The words are given by and , and .
Since is a proper prefix of , the lengths satisfy , so the are pairwise distinct and listed in increasing length. By Theorem 2.13,
Lemma 3.1. (i) The map is a bijection from onto , and for the corresponding to the letter is the -th letter of block .
(ii) for all and .
(iii) and for all .
(iv) , and for every other pair .
Proof. For fixed the parameter runs through , so runs through , and these intervals partition . The position is the -th position of block . This proves item (i). Item (ii) is immediate from the definition of . Item (iii) follows from , which gives
For item (iv), , which is only for . Since , the sequence is nondecreasing with , so for we have and . Hence . □
Proposition 3.2. For every and , the index satisfies .
Proof. We argue by induction on . By Lemma 3.1, item (i), every corresponds to exactly one pair . For this pair is , and . For the induction step the index corresponds to , the claim holds for all indices up to , and . It suffices to show , because for the pair of is , and for the value equals , which is the value required for the pair of , by Lemma 3.1, item (iii).
If , the letter lies in the same block as , so , the index of Lemma 2.14 equals , and . The index corresponds to , so the induction hypothesis and Lemma 3.1, item (ii) give
If and , then and does not occur in the empty word, so by Lemma 2.14, which equals .
If and , then , the word contains no letter , and . Lemma 2.14 and the induction hypothesis give , and gives
If and , then , and is the letter of block , which is also the letter of block and differs from the letter of block . The last occurrence of in is therefore the last position of block , so in Lemma 2.14. Then corresponds to the pair , and , so the induction hypothesis and Lemma 3.1, item (iii) give . Thus,
The four situations cover every pair , which completes the induction. □
Corollary 3.3. The map is injective on , and its image is . Consequently each length in is attained by exactly one pair , and .
Proof. By Lemma 3.1, item (i), the pairs correspond bijectively to the indices , and by Proposition 3.2 the pair of has . Since for all , the values are pairwise distinct, so the map is injective. By Lemma 3.1, item (iv), the value occurs only for , and (6) gives the last statement. □
Asymptotic count of palindromic prefixes
The sequence is purely periodic of period , so and for all . The symbol stands for . The only facts about palindromic prefixes used below are (6), Proposition 3.2 and Corollary 3.3. By (6), . By Lemma 3.1 (i), the map is a bijection from onto , under which corresponds to , and by Proposition 3.2, for the corresponding pair. By Corollary 3.3, the pairs and the lengths correspond one to one. Therefore
Theorem 3.4. For every purely periodic of period ,
Proof. The vectors satisfy and for . Since for , the product is the -th power of , and therefore . Each is symmetric with determinant , so is the transpose of , with and , where denotes . The Cayley–Hamilton theorem gives . Multiplying by and reading the first coordinate gives
for , where , and . The matrices , with , are written
The relation gives, for all ,
Since and , induction on gives for and for . Since , the trace is . We claim that
For we have . For , (12) gives and , hence . The polynomial satisfies . If is odd, then by the first part of (13). If is even, then , and by the second part of (13). In both cases . Consequently has two real roots with strictly between them. The larger root exceeds , and the other root is , and . Both roots are eigenvalues of , since is its characteristic polynomial, and has the larger modulus. Thus, .
The sequence is strictly increasing for : for it holds that , where and . Since , there are constants with and . The sequence has the same first two terms as and satisfies the same recurrence, because and . Therefore
Subtracting times the equation from gives . Since and , we get . Thus, from (14),
where . For the integer satisfies , and monotonicity of gives . Therefore
and both bounds tend to as . Thus, (15) and (16) give
For the index exists, since and , and as . For large enough that , the definition of gives ,
Both outer terms tend to . Thus, , and since ,
The set of pairs counted by is bounded from both sides as follows. For and , the identity gives . Hence every pair with is counted, except , and
In the other direction, let be a pair with . Since , we get , hence , and so by the definition of . Thus every counted pair has , and
Periodicity of gives with , so for every . Together with (19) and (20),
Divide (21) by and use . Both outer terms then tend to , since . Hence
which is (10). □
Corollary 3.5. For every purely periodic of period ,
Proof. By (14) and , there are constants with for all , where . For and , monotonicity of gives , and . Hence with and . From we obtain
that is,
Since for , there is a constant with for all . Substituting this into (21) gives
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 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 .
In the literature the abundance of palindromic prefixes is measured by , where is the length of the -th palindromic prefix [9]. By Proposition 3.2, the ratios of consecutive lengths are governed by the quotients , so this quantity records the largest relative gap between consecutive palindromic prefixes and depends on the extreme values of the directive sequence. The count takes all gaps into account, and its constant depends on in a different way.
This constant is the ratio of , the mean of , to , the exponential growth rate of per index, by (17). It is not a function of the mean alone, because depends on the order of and not only on their sum. For we have and the constant is , while for we have and the constant is , although both sequences have mean 2. Replacing by multiplies by and replaces by , so is also multiplied by , and the constant does not depend on the choice of period. For the theorem gives with .
Periodicity enters the proof of Theorem 3.4 only through (17) and the bounded oscillation of the partial sums of . The remaining steps hold for every directive sequence, which gives the following statement.
Proposition 4.1. Let be a directive sequence with for all , and let . Then
If and , then .
Proof. The two bounds are (19) and (20), whose proofs use only Lemma 3.1 and the monotonicity of . By (18) and the assumption on , we get . Since , dividing the bounds by gives the claim. □
The error term in Corollary 3.5 cannot be improved to . Indeed, the lengths are pairwise distinct by Corollary 3.3, so increases by exactly 1 at each of them, while changes by across such a point. Hence the difference has no limit.
Finally, the periodic case is special. For the number is the denominator of the -th convergent of , so by Lévy’s theorem we have for almost every [16, 1]. By the Borel–Bernstein theorem [16], for almost every the inequality holds for infinitely many . For such and we have , so Proposition 4.1 gives , while . Hence is unbounded, and no asymptotic of the form holds for such .
Conclusion
We derived the lengths of the palindromic prefixes of a standard Sturmian word with directive sequence , where for all , directly from the construction by iterated palindromic closure. They are the numbers with and , where is the length of the -th standard word. The value 0 occurs only for and corresponds to the empty prefix, and every nonzero length is attained by exactly one pair . The proof tracks the lengths of the closures through the block boundaries of the directive word .
For a purely periodic directive sequence , the counting function of nonempty palindromic prefixes of length at most satisfies
where is the largest eigenvalue of . More precisely, Corollary 3.5 gives , and this error term cannot be improved to . The constant does not depend on the choice of period, and for the Fibonacci word it equals . The argument rests on two ingredients, the exponential growth of governed by and the bounded oscillation of the partial sums of over one period. The constant is determined by the sum of the over one period together with the growth rate of , and not by the mean of the alone. It differs in nature from the quantity , which is governed by the extreme values of the quotients .
Proposition 4.1 extends the counting argument to arbitrary directive sequences with , and together with the Borel–Bernstein theorem shows that is unbounded for almost every slope. Jasem Hamoud: Moscow Institute of Physics and Technology
Email address: [email protected]
References
- [1]K. Dajani, C. Kraaikamp, Ergodic theory of numbers, Carus Mathematical Monographs 29, Mathematical Association of America, Washington, DC, 2002.
- [2]A. de Luca, Sturmian words: structure, combinatorics, and their arithmetics, Theoret. Comput. Sci. 183(1) (1997), 45–82.DOI
- [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]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]X. Droubay, J. Justin, G. Pirillo, Episturmian words and some constructions de Luca and Rauzy, Theoret. Comput. Sci. 255 (2001), 539–553.DOI
- [6]L. Dvořáková, String attractors of episturmian sequences, arXiv:2211.01660 (2022).arxiv.org/abs/2211.01660
- [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]G. Fici, J. Shallit, J. Simpson, Some remarks on palindromic periodicities, arXiv:2407.10564 (2024).arxiv.org/abs/2407.10564
- [9]S. Fischler, Palindromic prefixes and episturmian words, J. Combin. Theory Ser. A 113(7) (2006), 1281–1304.arxiv.org/abs/math/0501420
- [10]S. Fischler, Palindromic prefixes and diophantine approximation, Monatsh. Math. 151 (2007), 11–37.arxiv.org/abs/math/0509508
- [11]D. Gabric, On the properties and structure of bordered words and generalizations, Ph.D. thesis, University of Waterloo, 2022.
- [12]A. Glen, On Sturmian and episturmian words, and related topics, Ph.D. thesis, The University of Adelaide, Australia, 2006.
- [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]G. H. Hardy, E. M. Wright, An introduction to the theory of numbers, 6th edition, Oxford University Press, Oxford, 2008.
- [15]R. A. Horn, C. R. Johnson, Matrix analysis, 2nd edition, Cambridge University Press, Cambridge, 2013.
- [16]M. Iosifescu, C. Kraaikamp, Metrical theory of continued fractions, Mathematics and Its Applications 547, Kluwer Academic Publishers, Dordrecht, 2002.
- [17]J. Justin, Episturmian morphisms and a Galois theorem on continued fractions, RAIRO Theor. Inform. Appl. 39(1) (2005), 207–215.DOI
- [18]J. Justin, G. Pirillo, Episturmian words and episturmian morphisms, Theoret. Comput. Sci. 276 (2002), 281–313.DOI
- [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]M. Lothaire, Algebraic combinatorics on words, Encyclopedia of Mathematics and its Applications 90, Cambridge University Press, Cambridge, 2002.DOI
- [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]J. Rukavicka, Palindromic length and reduction of powers, Theoret. Comput. Sci. 930 (2022), 106–115.DOI
- [23]J. Rukavicka, Palindromic length of infinite aperiodic words, European J. Combin. 131 (2026), 104237.arxiv.org/abs/2410.12714