The Parameterized Periodicity Lemma

Fine and Wilf [Proc. Amer. Math. Soc. 1965] showed that any string of length at least $p+q-d$ with periods $p$ and $q$ also has period $d=\gcd (p,q)$. For parameterized strings, Apostolico and Giancarlo [Discrete Appl. Math. 2008] proved an analogue with length bound $p+q$, assuming that the two induced bijections commute. Ideguchi et al. [SPIRE 2023] removed this assumption and gave the bound $p+q+\min (p,q)(\sigma -1)$, where $\sigma$ is the number of distinct letters. This was later improved by Hamai et al. [SPIRE 2024] to $p+q+\min (p,q)(\sigma -2)$, which was used to bound the number of non-equivalent parameterized squares. In this paper, we establish the optimal Fine–Wilf type bound for parameterized strings. Namely, if a string $s$ containing $\sigma$ distinct letters has parameterized periods $p$ and $q$ and satisfies $\mathrm{\mid }s\mathrm{\mid }\ge p+q+(\sigma -3)d+1$, where $d=\gcd (p,q)$, then $d$ is also a parameterized period of $s$. We also give matching lower-bound instances, proving that our bound is optimal for any $\sigma \ge 2$.