An abelian periodicity lemma
type: Item
instance of: scholarly article
title: An abelian periodicity lemma
zbMATH Open document ID: 1362.68241
published in: Theoretical Computer Science
publication date: 2017-02-06T00:00:00Z
review text: 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\).
reviewed by: F. Blanchet-Sadri
Mathematics Subject Classification ID: 68R15
zbMATH DE Number: 6680851
zbMATH Keywords: periodicity lemma
zbMATH Keywords: abelian periodicity
author: Jamie Simpson
MaRDI profile type: Publication
full work available at URL: j.tcs.2015.12.014
OpenAlex ID: W2283259025
Wikidata QID: Q124813705
cites work: The “Runs” Theorem
cites work: Abelian periods, partial words, and an extension of a theorem of Fine and Wilf
cites work: Q3396591
cites work: Uniqueness Theorems for Periodic Functions
cites work: Abelian squares are avoidable on 4 letters
DOI: 10.1016/J.TCS.2015.12.014
description: scientific article; zbMATH DE number 6680851