2012/07/17 by Kalle Saari, Saari, Kalle
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithms and Data Compression #Combinatorics (math.CO) #DNA and Biological Computing #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1207.4233
12 pages
openalex publication_date 2012/07/17 · arxiv created 2012/11/16 · arxiv updated 2012/11/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 log2(n) + 1 for the number of distinct 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 logphi(n) + 1, where phi denotes the golden ratio (1 + sqrt5)/2. We show that this bound is optimal in that it is attained by the Fibonacci Lyndon words. We then introduce a mapping Lx that counts the number of Lyndon factors of length at most n in an infinite word x. We show that a recurrent infinite word x is aperiodic if and only if Lx >= Lf, where f is the Fibonacci infinite word, with equality if and only if f is in the shift orbit closure of f.