# Additional Problem 5: Local Periodicity Lemma with One Don't Care Symbol (Preliminary version)

$$\def\pgcd{\mathit{gcd}}$$

Letter $*$ is called a don't care (hole, joker) and stands for any other letter of the alphabet. It matches any letter including itself. For a string $x$ we write $x[i]\approx x[j]$ if the letters $x[i]$ and $x[j]$ are equal or one of them is the don't care symbol.

An integer $p$ is a local period of $x$ if for each $i\lt |x|-p$ we have $x[i]\approx x[i+p]$. In Periodicity we presented the periodicity lemma.

### Lemma 1 (Periodicity lemma)

If $p$ and $q$ are periods of a word $x$ and satisfy $p+q-\pgcd(p,q)\leq|x|$ then $\pgcd(p,q)$ is also a period of $x$.

Our question is related to an extension of this lemma to words with one don't care symbol. For simplicity we assume $p,q$ are relatively prime.

Show the following local periodicity lemma.
Assume $p,q$ are relatively prime and $x$ is a word with one don't care symbol. Show that if $p$ and $q$ are local periods of $x$ and satisfy $p+q\leq|x|$ then $1$ is also a local period of $x$.

Use the periodicity lemma for standard words.

For $p=5,q=7$ give example of a word $x$ having local periods $p,q$, with one don't care, such that $|x|=p+q-1$, and $x$ has no local period $1$.

## References

• A. Jez, Recompression: A simple and powerful technique for word equations, J. ACM 63(1):4:1-4:51, 2016.
• T. Kociumaka, J. Radoszewski, W. Rytter, and T. Walen, A periodicity lemma for partial words, Inf. Comput. 283 (2022) 104677.