A new characteristic property of the palindrome prefixes of a standard Sturmian word

GIUSEPPE PIRILLO IAMI CNR Viale Morgagni 67/A 50134 FIRENZE, Italy

We use notions and terminology of theoretical computer science (see [1, 2, 3, 4, 5]). The words u and v are conjugate and we write u ∼ v if there exist words s and t such

that u = st and v = ts.

Let φ : {a, b}^{∗} → {a, b}^{∗} be the morphism given by φ(a) = ab, φ(b) = a. Let f_{0} = b and, for n ≥ 0,

f_{n+1} = φ(f_{n}).

For n ≥ 2, let g_{n} = f_{n−2}f_{n−1} and let h_{n} be the longest common prefix of f_{n} and g_{n}. For example, for n ≤ 5, we have: f_{1} = a, f_{2} = ab, f_{3} = aba, f_{4} = abaab, f_{5} = abaababa, g_{2} = ba g_{3} = aab, g_{4} = ababa, g_{5} = abaabaab h_{2} = ϵ, h_{3} = a, h_{4} = aba, h_{5} = abaaba. Notice that, for n ≥ 0, |f_{n}| is the n^{th} element of the sequence of Fibonacci numbers

F_{n}. We have F_{0} = 1, F_{1} = 1 and, for each n ≥ 2, F_{n} = F_{n−1} + F_{n−2}; for 0 ≤ n ≤ 13 the Fibonacci numbers F_{n} are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377. For each n ≥ 2, f_{n} = f_{n−1}f_{n−2} implying that for each n ≥ 1, f_{n} is a prefix of f_{n+1}.

Hence there exists a unique infinite word, namely the Fibonacci word (see [1, 2, 3, 4, 5]) denoted by f such that, for each n ≥ 1, f_{n} is a prefix of f and we have

f = abaababaabaababaababaabaababaabaababaababa . . ..

Some very well known facts concerning f are collected in Lemma 1.

Lemma 1. For each n ≥ 2, i) (Near–commutative property) f_{n+2} = f_{n+1}f_{n} = f_{n}g_{n+1} = h_{n+2}xy and g_{n+2} = f_{n}f_{n+1} = f_{n+1}g_{n} = h_{n+2}yx, where x, y ∈ {a, b}, x ≠ y and

xy = \{ \begin{matrix}ab & if n is even \\ ba & if n is odd. \end{matrix}

ii) the words h_{n}ab and h_{n}ba are conjugate, i.e. f_{n} ∼ g_{n} (for instance, aba ∼ aab, abaab ∼ ababa, abaababa ∼ abaababa and so on).

Definition. An infinite word s = s_{1}s_{2}s_{3} ⋯, s_{i} ∈ {a, b} is Sturmian if there exist reals α, ρ ∈ [0, 1], such that either for all i

s(i) = a if ⌊ρ + (n + 1)α⌋ = ⌊ρ + nα⌋, s(i) = b otherwise

or for all i

s(i) = a if ⌈ρ + (n + 1)α⌉ = ⌈ρ + nα⌉, s(i) = b otherwise.

The infinite word is proper Sturmian if α is irrational. The infinite word is periodic Sturmian if α is rational. The infinite word is standard Sturmian if ρ = 0.

The Fibonacci word is a very particular case of Sturmian word (see [1, 2, 3, 4, 5]). We are convinced that looking carefully at the property of the Fibonacci word one can discover properties of Sturmian words. The previous mentioned fact suggested us the following result.

Proposition. A word w is a palindrome prefix of some standard Sturmian word if and only if wab and wba are conjugate.

Proof. ”only if” part. It is possible to say that this part is well known, in any case for an accurate proof one must use some notions defined in [2] (P AL, P ER, Stand, …).

”if” part. This part seems to be unknown and, in our knowledge, it is never mentioned in the literature.

Now let w be written on an arbitrary alphabet and be such that wab ∼ wba. If |w| = 0 or |w| = 1 the statement is easily verified. So suppose that |w| > 1 We know that, for some words u, v we have wab = uv and wba = vu. If |u| = 1 then u = a and w = a^{|w|} which is a palindrome prefix of a standard Sturmian

word.

So suppose |u| ≥ 2. If |v| = 1 then v = b and w = b^{|w|} which is a palindrome prefix of a standard Sturmian

word.

So we can suppose |u| ≥ 2 and |v| ≥ 2. If, without loss of generality, for instance |u| ≤ |v| we easily see that u is a prefix of v and so w is a fractional power of both u and v.

Pose p = |u| and q = |v| and d = MCD(p, q). If d were greater than 1 then |w| = p + q − 2 ≥ p + q − d and, by a result of Fine and Wilf [5], w should have period d and consequently u = h^{p/d} and v = h^{q/d} for some non empty word h which is clearly impossible as u has suffix ba and v has suffix ab. So d = 1.

Now let us show that alph(w) = {a, b}. If it is not the case, suppose that |alph(w)| ≥ 3 and w is one the words of minimal length such that wab ∼ wba. Suppose |u| < |v| and put q = kp + r, 0 ≤ r < p. We can write v = u^{k}v_{1} with v_{1} a prefix of u of length r. Put also v_{1} = v′′ab. By the conjugation relation of wab and wba we get u′bav′′ = v′′abu′ = w′ for some word w′. We have w′ab ∼ w′ba. As alph(w′ab) = alph(wab) and |w′| < |w| we have a contradiction. Consequently alph(wab) = {a, b}.

As d = 1 we can apply Theorem 2 of [2] and so w is a palindrome prefix of a standard Sturmian word.

Bibliography

[1]. J. Berstel and P. Séébold, Algebraic Combinatorics on words, to appear.

[2]. A. de Luca, Sturmian words: structure, combinatorics, and their aritmetics, Theoretical Computer Science 183 (1997) 45-82.

[3]. X. Droubay, J. Justin and G. Pirillo Episturmian words and some constructions of de Luca and Rauzy, Theoretical Computer Science, to appear.

[4]. J. Justin and G. Pirillo Decimations and Sturmian words, Informatique théorique et Applications, vol. 31, 3 (1997), 271-290.

[5]. M. Lothaire, Combinatorics on words, Addison-Wesley, 1982.