\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