6533b7d3fe1ef96bd126146e

RESEARCH PRODUCT

A Note on a Conjecture of Duval and Sturmian Words

subject

description

We prove a long standing conjecture of Duval in the special case of Sturmian words. Mathematics Subject Classication. ??????????????. Let U be a nonempty word on a nite alphabet A: A nonempty word B dierent from U is called a border of U if B is both a prex and sux of U: We say U is bordered if U admits a border, otherwise U is said to be unbordered. For example, U = 011001011 is bordered by the factor 011; while 00010001001 is unbordered. An integer 1 k n is a period of a word U = U1 :::U n if and only if for all 1 i n k we have Ui = Ui+k. It is easy to see that k is a period of U if and only if the prex B of U of length n k is a border of U or is empty. Let (U) denote the smallest period of U.T henU is unbordered if and only if (U )i s equal to the length of U; that is (U )= jUj = n. We further denote by (U )t he length of the longest unbordered factor of U. Clearly U is unbordered if and only if (U )= jUj. In general, for any word U we have (U) (U )( cf. Prop. 2.2 of (3)). An interesting question is to ask for which words U does equality hold. In (3) Duval shows that (U )= (U) whenever jU j2(U) 2( cf. Cor. 4.2 in (3)). These notions extend directly to innite words. For an innite word !; if (!) is nite, then ! is periodic of period (!). (cf. (2) and (4)). In (3) Duval conjectured that: Conjecture 1 (Duval 1981). Let U be an unbordered word on an alphabet A and let W be a word of length 2jUj beginning in U and with the property that each factor of W of length greater than jUj is bordered. Then W has period jUj; i.e., W = UU: