Lyndon factors and the Fibonacci word
Author:
Preprint
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.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Fine and Wilf words for any periods IITheoretical Computer Science, 2009
- Palindromic prefixes and episturmian wordsJournal of Combinatorial Theory, Series A, 2006
- Algebraic Combinatorics on Words2002
- Fine and Wilf's theorem for three periods and a generalization of Sturmian wordsTheoretical Computer Science, 1999
- Sturmian words, Lyndon words and treesTheoretical Computer Science, 1997
- Squares, cubes, and time-space efficient string searchingAlgorithmica, 1995
- Factorizing words over an ordered alphabetJournal of Algorithms, 1983
- A combinatorial property of the Fibonacci wordsInformation Processing Letters, 1981
- Periodicity and unbordered segments of wordsDiscrete Mathematics, 1979
- Necklaces of beads in k colors and k-ary de Bruijn sequencesDiscrete Mathematics, 1978