\magnification1200
\def\slva{\vskip 4truemm}

\centerline{\bf A new characteristic property of the palindrome prefixes}

\centerline{\bf of a standard Sturmian word}

\slva\slva\slva

\centerline {GIUSEPPE PIRILLO}

\centerline {IAMI CNR}

\centerline {Viale Morgagni 67/A}

\centerline {50134 FIRENZE, Italy}



\slva\slva\slva



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\sim v$ if
there exist words $s$ and $t$
such that $u=st$ and $v=ts$.

Let
$\varphi :\{a, b\}^*
\rightarrow \{a, b\}^*$
be the morphism
given by
$\varphi(a)=ab$, $\varphi(b)=a$.
Let $f_0=b$ and,
for $n\ge 0$,

$$f_{n+1}=\varphi(f_n).$$

For $n\ge 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\le 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=\epsilon$,

$h_3=a$,

$h_4=aba$,

$h_5=abaaba$.


Notice that,
for $n\ge 0$,
$\vert f_n\vert$ 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\ge 2$,
$F_n=F_{n-1}+F_{n-2}$;
for $0\le n\le 13$
the Fibonacci numbers $F_n$ are
1, 1, 2, 3, 5, 8, 13, 21, 34, 55,
89, 144, 233, 377.
For each $n\ge 2$,
$f_n=f_{n-1}f_{n-2}$
implying that for each $n\ge 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\ge 1$,
$f_n$ is a prefix of $f$
and we have

\centerline{$f=
abaababaabaababaababaabaababaabaababaababa \dots $.}

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

\slva

{\bf Lemma 1.}
{\it For each $n\ge 2$,
i) (Near--commutative property)
$f_{n+2}=f_{n+1}f_n=
f_ng_{n+1}=h_{n+2}xy$ and
$g_{n+2}=f_nf_{n+1}=
f_{n+1}g_n=h_{n+2}yx$,
where $x,y\in \{a,b\}$, $x\not= y$
and

$$
xy=
\cases{
ab &\hbox{if $n$ is even}\cr
ba & \hbox{if $n$ is odd.}
}$$

ii) the words
$h_nab$ and $h_nba$ are conjugate,
i.e. $f_n\sim g_n$
(for instance, $aba\sim aab$,
$abaab\sim ababa$,
$abaababa\sim abaababa$ and so on).
 }

\slva

{\bf Definition.}
{\it
An infinite word
$s=s_1s_2s_3\cdots , s_i\in \{a,b\}$
is {\it Sturmian}
if there exist reals
$\alpha ,\rho \in [0,1]$,
such that either
for all $i$

$$s(i)=a \,\,{\rm if}\,\,
\lfloor \rho +(n+1)\alpha \rfloor
=\lfloor \rho +n\alpha \rfloor , \,\,\,s(i)=b \,\,{\rm otherwise}$$

\noindent or for all $i$

$$s(i)=a \,\,{\rm if}\,\,
\lceil \rho +(n+1)\alpha \rceil
=\lceil \rho +n\alpha \rceil , \,\,\,s(i)=b \,\,{\rm otherwise.}$$

The infinite word is proper Sturmian if $\alpha$ is irrational.

The infinite word is periodic Sturmian if $\alpha$ is rational.

The infinite word is standard Sturmian if $\rho =0$.
}

\slva

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

\slva

{\bf Proposition.}
{\it A word $w$
is a palindrome prefix of some standard Sturmian word
if and only if $wab$ and $wba$
are conjugate.}

\slva

{\bf Proof.}
{\bf "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]
($PAL$, $PER$, $Stand$, $\dots$).

{\bf "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\sim wba$.

If $\vert w\vert =0$ or $\vert w\vert =1$ 
the statement is easily verified.
So suppose that $\vert w\vert >1$

We know that, for some words $u,v$
we have
$wab=uv$ and $wba=vu$.

If $\vert u\vert =1$
then $u=a$
and $w=a^{\vert w\vert}$
which is a palindrome prefix of a standard Sturmian word.

So suppose $\vert u\vert \ge 2$.

If $\vert v\vert =1$
then $v=b$
and $w=b^{\vert w\vert}$
which is a palindrome prefix of a standard Sturmian word.

So we can suppose
$\vert u\vert \ge 2$
and $\vert v\vert \ge 2$.
If, without loss of generality,
for instance $\vert u\vert \le \vert v\vert$
we easily see that $u$ is a prefix of $v$
and so $w$ is a fractional power of both $u$ and $v$.

Pose $p=\vert u\vert$
and $q=\vert v\vert$
and $d=MCD(p,q)$.
If $d$ were greater than 1
then $\vert w\vert =p+q-2\ge 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
$\vert alph(w)\vert \ge 3$ and $w$ is one the words
of minimal length such that
$wab\sim wba$.
Suppose $\vert u\vert <\vert v\vert$
and put
$q=kp+r$, $0\le r<p$.
We can write $v=u^kv_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\sim w'ba$.
As $alph(w'ab)=alph(wab)$
and
$\vert w'\vert <\vert w\vert $
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.

\slva

{\bf Bibliography}

[1]. J. Berstel and P. S\'e\'ebold,
{\it Algebraic Combinatorics on words}, to appear.

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

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

[4]. J. Justin and G. Pirillo
{\it Decimations and Sturmian words},
Informatique th\'eorique et Applications,
vol. 31, {\bf 3} (1997), 271-290. 

[5]. M. Lothaire, {\it Combinatorics on words}, Addison-Wesley, 1982.
\end


