Overlap-free symmetric D 0 Lwords

Abstract

A D0L word on an alphabet Σ={0,1,…,q-1} is called symmetric if it is a fixed point w=φ(w) of a morphism φ:Σ * → Σ * defined by φ(i)= t 1 + i t 2 + i … t m + i for some word t 1 t 2 … t m (equal to φ(0)) and every i ∈ Σ; here a means a mod q. We prove a result conjectured by J. Shallit: if all the symbols in φ(0) are distinct (i.e., if t i ≠ t j for i ≠ j), then the symmetric D0L word w is overlap-free, i.e., contains no factor of the form axaxa for any x ∈ Σ * and a ∈ Σ.