Problem 130: Local periodicity lemma with one don't care symbol
\(
\def\pgcd{\mathit{gcd}}
\)
The problem concerns periodicities occurring inside a word that contains
one occurrence of a don't care symbol (also called hole or joker).
It is a letter, denoted by $*$, that stands for any other letter of the
alphabet, that is, it matches any letter including itself.
For a string $x$, two of its letters, $x[i]$ and $x[j]$, are said to
$\approx$-match, written $x[i]\approx x[j]$,
if they are equal or one of them is the don't care symbol.
Furher, an integer $p$ is a local period of $x$ if for each position $0\leq i\lt |x|-p$, we have $x[i]\approx x[i+p]$.
Recall the Periodicity lemma for usual words
(see Periodicity).
Lemma 1 (Periodicity lemma)
Let $x$ be a word (without don't care symbol) and let $p,q$ be
periods of $x$ that satisfy $p+q-\pgcd(p,q)\leq|x|$.
Then $\pgcd(p,q)$ is also a period of $x$.
The problem is related to an extension of this lemma to
words in which only one don't care symbol occurs.
(Local periodicity lemma)
Let $x$ be a word with one don't care symbol and
$p,q$ be two relatively prime
local periods of $x$ and satisfy $p+q\leq|x|$.
Then $1$ is also a local period of $x$.
Give example of a word $x$ with one don't care symbol
having local periods $p=5$ and $q=7$
with $p+q-1=|x|$ but not having $1$ as local period.
The example in this question shows the inequality in the first question
is tight.
References
-
J. Berstel and L. Boasson,
Partial words and a theorem of Fine and Wilf,
Theor. Comput. Sci. 218(1):135-141, 1999.
-
T. Kociumaka, J. Radoszewski, W. Rytter, and T. Walen,
A periodicity lemma for partial words,
Inf. Comput. 283 (2022) 104677.