An abelian periodicity lemma
Denote the length of a word \(w\) by \(|w|\) and the Parikh vector of \(w\) by \({\mathcal P}(w)\), which records the number of occurrences of each letter in \(w\). For two words \(u\) and \(v\), \({\mathcal P}(u)={\mathcal P}(v)\) if and only if \(u\) is a permutation of \(v\) and \({\mathcal P}(u)\leq {\mathcal P}(v)\) if and only if \(u\) can be obtained by permuting and, possibly, deleting some of the letters of \(v\). A word \(w\) has \textit{abelian period} \(p\) if \(w=u_0u_1u_2\cdots u_mu_{m+1}\), where \(m \geq 1\), \(|u_1|=|u_2|=\cdots=|u_m|=p\), \(|u_0|>0\), and \({\mathcal P}(u_0) \leq {\mathcal P}(u_1)={\mathcal P}(u_2)=\cdots={\mathcal P}(u_m)\geq {\mathcal P}(u_{m+1})\). The reviewer et al. [``Fine and Wilf's theorem for abelian periods in partial words'', in: Proceedings of the 13th Mons theoretical computer science days, 2010. Amiens: Univ. de Picardie Jules Verne (2010)] proved that if a word \(w\) has abelian periods \(p\) and \(q\) with \(\operatorname{gcd}(p,q)=d\), \(d> 1\), and \(\left||u_{0}|-|v_{0}|\right|\) is a multiple of \(d\), then \(w\) has at most cardinality \(d\) for \(\left|w\right|\geq 2 \,\operatorname{lcm}(p,q)-1\). They conjectured that if a word \(w\) has abelian periods \(p\) and \(q\) with \(\operatorname{gcd}(p,q)=d\), \(d> 1\), and \(\left|\left|u_0\right|-\left|v_0\right|\right|\) is not a multiple of \(d\), then \(w\) has at most cardinality \(d\) for \(\left|w\right|\geq 2 \, \operatorname{lcm}(p,q)-2\) and they proved that their conjecture is true under some conditions on \(p\) and \(q\). In this very interesting paper, the author proves that the conjecture is true. Thus, a word \(w\) having abelian periods \(p\) and \(q\) with \(\operatorname{gcd}(p,q)=d\), \(d\geq1\), has at most cardinality \(d\) for \(\left|w\right|\geq 2 \, \operatorname{lcm}(p,q)-1\).
scientific article; zbMATH DE number 6680851