1

Order and quasiperiodicity in episturmian words

∗ Amy Glen LaCIM,Universit´eduQu´ebec`aMontre´al, C.P.8888,succursaleCentreville,Montre´al,Qu´ebec,CANADA,H3C3P8 † Extended Abstract

Introduction

July 13, 2007

In this paper, we build upon previous work concerning inequalities characterizing Sturmian and episturmian words – see [19, 29, 30, 14, 16]. First let us recall from [29] the following notion relating tolexicographic order. LetAbe atotally orderedﬁnite alphabet consisting of at least two letters. To any inﬁnite wordxover A, we can associate two inﬁnite words min(x) and max(x) such that any preﬁx of min(x) (resp. max(x)) is thelexicographicallysmallest (resp. greatest) amongst the factors ofxMore precisely, ifof the same length. we denote by min(x|k) (resp. max(x|k)) the lexicographically smallest (resp. greatest) factor ofxof length kfor the given order, then min(x|k) and max(x|k) are clearly preﬁxes of the respective words min(x|k+ 1) and max(x|kSo we can deﬁne, by taking limits, the following two inﬁnite words+ 1).

min(xlim min() = x|k) k→∞

and

max(xlim max() = x|k). k→∞

An important point here is that, for any aperiodic inﬁnite wordxwhich is uniformly recurrent, min(x) is aninﬁnite Lyndon word, i.e., it is (strictly) lexicographically smaller than all of its proper suﬃxes for the given order onA. In 2003, Pirillo [28] (also see [29]) proved that, for inﬁnite wordsson a 2letter alphabet{a, b}with a < b, the inequalityas≤min(s)≤max(s)≤bscharacterizesstandard Sturmian words(aperiodic and periodic). Equivalently, an inﬁnite sequences= (sn)n≥0over{a, b}is standard Sturmian if and only if

k as≤T (s)≤bs,

for allk≥0,

(1.1)

k k where T is thekth iterate of theshift map: T ((sn)n≥0) = (sn+k)n≥0(cf.our analogue for episturmian sequences – Corollary 3.2). Actually, this result was known much earlier, dating back to the work of P. Veerman [38, 39] in the mid 80’s. Since that time, these ‘Sturmian inequalities’ have been rediscovered numerous times under diﬀerent guises, as discussed in our survey paper [4]. In the case of an arbitrary ﬁnite alphabetA, Pirillo [29] generalized the above inequalities by proving that an inﬁnite wordsoverAisstandard episturmian(orepistandardfor short) if and only if, for any lexicographic order, we have as≤min(s) wherea= min(A).(1.2) Moreover,sis astrictepistandard word (i.e., astandard ArnouxRauzy sequence[7, 37]) if and only if (1.2) holds with strict equality for any order [19]. In a similar spirit, Glen, Justin, and Pirillo [16] recently proved the following characterization of allepisturmian words.

Proposition 1.1.[16]A recurrent inﬁnite wordtoverAis episturmian if and only if there exists an inﬁnite wordssuch that, for any lexicographic order, we haveas≤min(t)wherea= min(A).

From the proof of the above result, it is not immediately clear what form is taken by the inﬁnite words, if it exists. We now prove further (in Section 3) thatsis in fact the ‘unique’ epistandard word with the same set of factors ast, i.e., the corresponding epistandard word in theshift orbit closureoft(see Section 2). As the title of this paper suggests, these results have a connection withquasiperiodicityexactly?. What Well, roughly speaking, an inﬁnite wordxisquasiperiodicif there exists a ﬁnite wordusuch that the ∗ Email:amy.glen@gmail.com(with the support of CRMISMLaCIM) † Same as the full version, but all proofs (and some lemmas) have been omitted.

1