Square-root upper bound conjecture for the length of UPS-factorizations

Let A\operatorname{A} be a finite alphabet. For a finite nonempty rich word ww over A\operatorname{A}, write its UPS-factorization as w=wpwp1w1w=w_pw_{p-1}\cdots w_1, where the factors are palindromes, and let luf(w)=p\operatorname{luf}(w)=p be its length. Set n=wn=|w|. Square-root UPS-factorization conjecture. There is a positive real constant λ\lambda such that, for every finite nonempty rich word ww over A\operatorname{A},

luf(w)λn.\operatorname{luf}(w)\leq \lambda\sqrt{n}.

This would improve the paper's proved upper bound luf(w)μn/eπlnn\operatorname{luf}(w)\leq \mu n/e^{\pi\sqrt{\ln n}} and remains presented as a conjecture in the source.

Sources & referencesView supporting material

Primary source

Josef Rukavicka, “Palindromic factorization of rich words”, arXiv:2110.13078 (2021).

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.