Periodicity and Unbordered Words: A Proof of Duval?s Conjecture.
Tero Harju, Dirk Nowotka · 2004
Abstract. The relationship between the length of a word and the maximum length of its unbordered factors is investigated in this paper. A word is bordered, if it has a proper prefix that is also a suffix of that word. Consider a finite word w of length n. Let µ(w) denote the maximum length of its unbordered factors, and let ∂(w) denote the period of w. Clearly, µ(w) ≤ ∂(w). We establish that µ(w) = ∂(w), if w has an unbordered prefix of length µ(w) and n ≥ 2µ(w) − 1. This bound is tight and solves a 21 year old conjecture by Duval. It follows from this result that, in general, n ≥ 3µ(w) implies µ(w) = ∂(w) which gives an improved bound for the question asked by Ehrenfeucht and Silberger in 1979. 1