PERIODICITY AND THE GOLDEN RATIO

We prove a periodicity theorem on words that has strong analogies with the Critical Factorization theorem. The Critical Factorization theore m states, roughly speaking, a connection between local and global peri ods of a word; the local period at any position in the word is there d efined as the shortest repetition (a square) ''centered'' in that posi tion. We here take into account a different notion of local period by considering, for any position in the word, the shortest repetition ''i mmediately to the left'' from that position. In this case a repetition which is a square does not suffices and the golden ratio phi (more pr ecisely its square (phi(2) = 2.618...) surprisingly appears as a thres hold for establishing a connection between local and global periods of the word. We further show that the number (phi(2) is tight for this r esult. Two applications are then derived. In the firts we give a chara cterization of ultimately periodic infinite words. The second applicat ion concerns the topological perfectness of some families of infinite words. (C) 1998 Published by Elsevier Science B.V. All rights reserved .