Conjecture on minimizers of the number of Lyndon factors

Let (n)\ell(n) be the minimum number of Lyndon factors among Lyndon words of length nn:

(n)=min{L(w)w is a Lyndon word with w=n}.\ell(n)=\min\{\mathcal{L}(w)\mid w\text{ is a Lyndon word with }|w|=n\}.

A minimizer conjecture. If ww is a Lyndon word with w6|w|\neq 6 and L(w)=(w)\mathcal{L}(w)=\ell(|w|), then ww is a Sturmian Lyndon word, meaning that there exist distinct letters a,ba,b such that

w{a,b}+,w=apwb,w\in\{a,b\}^{+},\qquad w=ap_wb,

where pwp_w is a central word.

This conjecture characterizes the Lyndon words attaining the minimum possible number of Lyndon factors at each length, apart from the exceptional length 66. It extends the preceding observation that Fibonacci Lyndon words are optimal and addresses the existence of optimal Lyndon words using more than two letters; the source does not state whether the conjecture has been resolved.

Sources & referencesView supporting material

Primary source

Kalle Saari, “Lyndon words and Fibonacci numbers”, arXiv:1207.4233 (2012).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.