Abstract
It is a fundamental property of non-letter Lyndon words that they can be expressed as a concatenation of two shorter Lyndon words. This leads to a naive lower bound log_{2}(n) + 1 for the number of Lyndon factors that a Lyndon word of length n must have. But this bound is not optimal. In this paper we show that a much more accurate lower bound is log_{phi}(n), where phi = (1 + sqrt{5})/2, the golden ratio. We show that this bound is optimal in that it is attained by the Fibonacci Lyndon words, and that they are the unique Lyndon words doing so. As an application, we introduce a mapping L_{x} that counts the number of Lyndon factors of length at most n of an infinite word x. We show that a recurrent infinite word x is aperiodic if and only if L_x >= L_f, where f is the Fibonacci infinite word, with equality if and only if x is in the shift orbit closure of f.

This publication has 16 references indexed in Scilit: