Counting Lyndon factors

zbMATH Open1375.68095arXiv1701.00928MaRDI QIDQ2401409FDOQ2401409

Jamie Simpson, W. F. Smyth, Amy Glen

Publication date: 8 September 2017

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: In this paper, we determine the maximum number of distinct Lyndon factors that a word of length $n$ can contain. We also derive formulas for the expected total number of Lyndon factors in a word of length $n$ on an alphabet of size $sigma$, as well as the expected number of distinct Lyndon factors in such a word. The minimum number of distinct Lyndon factors in a word of length $n$ is $1$ and the minimum total number is $n$, with both bounds being achieved by $x^n$ where $x$ is a letter. A more interesting question to ask is what is the minimum number of distinct Lyndon factors in a Lyndon word of length $n$? In this direction, it is known (Saari, 2014) that an optimal lower bound for the number of distinct Lyndon factors in a Lyndon word of length $n$ is $lceillo{g}_{phi}(n)+1ceil$, where $phi$ denotes the golden ratio $(1+sqrt5)/2$. Moreover, this lower bound is attained by the so-called finite "Fibonacci Lyndon words", which are precisely the Lyndon factors of the well-known "infinite Fibonacci word" -- a special example of a "infinite Sturmian word". Saari (2014) conjectured that if $w$ is Lyndon word of length $n$, $ne6$, containing the least number of distinct Lyndon factors over all Lyndon words of the same length, then $w$ is a Christoffel word (i.e., a Lyndon factor of an infinite Sturmian word). We give a counterexample to this conjecture. Furthermore, we generalise Saari's result on the number of distinct Lyndon factors of a Fibonacci Lyndon word by determining the number of distinct Lyndon factors of a given Christoffel word. We end with two open problems.

Full work available at URL: https://arxiv.org/abs/1701.00928

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Lyndon words and Fibonacci numbers
• On a class of Lyndon words extending Christoffel words and related to a multidimensional continued fraction algorithm
• scientific article; zbMATH DE number 1948508
• Lyndon factorization of Sturmian words
• The standard factorization of Lyndon words: an average point of view

zbMATH Keywords

Lyndon wordChristoffel wordLyndon factor

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Sturmian words: structure, combinatorics, and their arithmetics
• Sturmian words, Lyndon words and trees
• Factorizing words over an ordered alphabet
• On Burnside's Problem
• Sturmian and Episturmian Words
• Some combinatorial properties of Sturmian words
• Descriptions of the Characteristic Sequence of an Irrational
• Lyndon words and Fibonacci numbers
• Free differential calculus. IV: The quotient groups of the lower central series
• Determination of [nθ] by its Sequence of^*Differences
• On Sturmian and episturmian words, and related topics

Cited In (5)

• The standard factorization of Lyndon words: an average point of view
• Partitioned factors in Christoffel and Sturmian words
• Title not available (Why is that?)
• Computing longest (common) Lyndon subsequences
• Computing longest Lyndon subsequences and longest common Lyndon subsequences

This page was built for publication: Counting Lyndon factors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2401409)