On highly palindromic words: the \(n\)-ary case (Q2231750)

A word of length \(m\) over an \(n\)-ary alphabet is called minimal-palindromic if its longest palindromic subword (or scattered factor) has length at most \(\lceil m/n \rceil\). The word \(rws\) over the same alphabet as \(w\) is an MP-extension of \(w\) if \(rws\) is minimal-palindromic. Extending results of [\textit{Š. Holub} and \textit{K. Saari}, Discrete Appl. Math. 157, No. 5, 953--959 (2009; Zbl 1187.68363); \textit{K. Ago} and \textit{B. Bašić}, Discrete Appl. Math. 284, 434--443 (2020; Zbl 1448.68363)], the authors show that any word \(w\) over an \(n\)-ary alphabet, \(n \geq 4\), has an MP-extension of length \(n M_n |w|\), and \(M_n\) is defined as \(M_4 = 4\), \(M_5 = 8\), and \(M_n = 2^{\lceil n/2 \rceil} + 2^{\lceil n/2 \rceil - 1} - 3\) for \(n\geq 6\). As a consequence, for any \(n\), the MP-ratio \(|rws|/|w|\), where \(rws\) is the shortest MP-extension of \(w\), of an \(n\)-ary word \(w\) is well-defined (and finite). Tight upper bounds for the MP-ratio of \(n\)-ary words are known for the cases \(n=2\) and \(n=3\) from the aforementioned references. The authors give a lower bound of \(2n\) on the maximal MP-ratio of \(n\)-ary words. To conclude, the authors show that minimal-palindromic words are abelian unbordered, that is, for every factorisation \(w = xuy\) of a minimal-palindromic word, the word \(x\) cannot be rearranged to obtain \(y\).