# How Much Different Are Two Words with Different Shortest Periods

Mai Alzamel, Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Ritu Kundu, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń

► To cite this version:

Mai Alzamel, Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Ritu Kundu, et al. How Much Different Are Two Words with Different Shortest Periods. 14th IFIP International Conference on Artificial Intelligence Applications and Innovations (AIAI), May 2018, Rhodes, Greece. pp.168-178, 10.1007/978-3-319-92016-0_16. hal-01821339

HAL Id: hal-01821339

https://inria.hal.science/hal-01821339

Submitted on 22 Jun 2018

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
How much different are two words
with different shortest periods

Mai Alzamel¹, Maxime Crochemore¹,², Costas S. Iliopoulos¹,
Tomasz Kociumaka³, Ritu Kundu¹, Jakub Radoszewski¹,³,
Wojciech Rytter³,*, and Tomasz Waleń³

¹ Department of Informatics, King's College London, London, UK
[mai.alzamel,maxime.crochemore,costas.iliopoulos,ritu.kundu]@kcl.ac.uk

² Université Paris-Est, France

³ Faculty of Mathematics, Informatics and Mechanics,
University of Warsaw, Warsaw, Poland
[kociumaka,jrad,rytter,walen]@mimuw.edu.pl

**Abstract.** Sometimes the difference between two distinct words of the same length cannot be smaller than a certain minimal amount. In particular if two distinct words of the same length are both periodic or quasiperiodic, then their Hamming distance is at least 2. We study here how the minimum Hamming distance $dist(x, y)$ between two words $x, y$ of the same length $n$ depends on their periods. Similar problems were considered in [1] in the context of quasiperiodicities. We say that a period $p$ of a word $x$ is primitive if $x$ does not have any smaller period $p'$ which divides $p$. For integers $p, n$ ($p \le n$) we define $P_p(n)$ as the set of words of length $n$ with primitive period $p$. We show several results related to the following functions introduced in this paper for $p \ne q$ and $n \ge \max(p, q)$.

$$
\begin{align*}
\mathcal{D}_{p,q}(n) &= \min \{ \text{dist}(x, y) : x \in \mathcal{P}_p(n), y \in \mathcal{P}_q(n) \}, \\
N_{p,q}(h) &= \max \{ n : \mathcal{D}_{p,q}(n) \le h \}.
\end{align*}
$$

# 1 Introduction

Consider a word $x$ of length $|x| = n$, with its positions numbered 0 through $n-1$. We say that $x$ has a period $p$ if $x_i = x_{i+p}$ for all $0 \le i < n-p$. Our work can be seen as a quest to extend Fine and Wilf's Periodicity Lemma [14], which is a ubiquitous tool of combinatorics on words.

**Lemma 1 (Periodicity Lemma [14]).** If a word $x$ has periods $p$ and $q$ and $|x| \ge p+q-GCD(p,q)$, then $x$ also has a period $GCD(p,q)$.

Other known extensions of this lemma include a variant with three [10] and an arbitrary number of specified periods [11,16,17,23], the so-called new periodicity lemma [13,3], a periodicity lemma for repetitions that involve morphisms [19], and extensions into periodicity of partial words [4,5,6,7,8,9,22], into abelian [12]

<footnote>* Supported by the Polish National Science Center, grant no 2014/13/B/ST6/00770.</footnote>
and k-abelian [18] periodicity, into bidimenional words [20], and other variations [15,21].

We say that a word $x$ of length $n$ is periodic if it has a period $p$ such that $2p \le n$. For two words $x$ and $y$ of length $n$, by $dist(x, y)$ we denote their Hamming distance being the number of positions $i = 0, \dots, n-1$ such that $x_i \ne y_i$. The following folklore fact gives a lower bound on how different are two distinct periodic words. Its proof can be found in [1].

**Fact 2.** If $x$ and $y$ are distinct periodic words of the same length, then $dist(x, y) \ne 1$.

We present several generalizations of this fact.

Results similar to Fact 2 were presented recently in the context of quasiperiodicity [1]. We say that a word $x$ has a cover $u$ if each position in $x$ is located inside an occurrence of $u$ in $x$. The word $x$ is called quasiperiodic if it has a cover $u$ other than $x$. In [1] the following generalization of Fact 2 was shown: $dist(x, y) > 1$ for any two distinct quasiperiodic words $x, y$ of the same length. This type of fact has potential applications; see [2].

There is a quantitative difference between periods and covers. For example, there are words $x$ and $y$ of length 1024 with shortest covers of length 4 and 5, respectively, and $dist(x, y) = 2$:

$$x = (abaa)^{256} \quad \text{and} \quad y = aaba(abaa)^{255}$$

with covers $abaa$ and $aabaa$. However, if $x$ and $y$ are words of length 1024 with shortest periods 4 and 5, respectively, then we must have $dist(x, y) \ge 357$.

We say that a period $p$ of a word $x$ is primitive if no proper divisor of $p$ is a period of $x$, i.e., if $p' | p$ and $p'$ is a period of $x$, then $p' = p$. We define

$$\mathcal{P}_p(n) = \{ |x| = n, p \text{ is a primitive period of } x \}.$$

The ultimate goal of this work is a characterization of the function $\mathcal{D}_{p,q}$ defined for $p \ne q$ and $n \ge \max(p, q)$ as:

$$\mathcal{D}_{p,q}(n) = \min \{ dist(x, y) : x \in \mathcal{P}_p(n), y \in \mathcal{P}_q(n) \}.$$

As $\mathcal{D}_{p,q}$ is non-decreasing for given $p, q$, it can be described by the following auxiliary function:

$$N_{p,q}(h) = \max \{ n : \mathcal{D}_{p,q}(n) \le h \}.$$

One can note that Lemma 1 can be equivalently formulated as $N_{p,q}(0) < p+q - \text{GCD}(p, q)$. Similarly, an equivalent formulation of Fact 2 is $N_{p,q}(1) < 2q$.

Fine & Wilf [14] also proved that the bound $p+q - \text{GCD}(p, q)$ of Lemma 1 cannot be improved. Consequently, $N_{p,q}(0) = p+q - \text{GCD}(p, q) - 1$. On the other hand, we show that $N_{p,q}(1) = 2q - 1$ only for $p | q$. Hence, the bound $N_{p,q}(1) < 2q$ of Fact 2 is not tight in general.
**Our results.** In Section 2 we consider the case that $p | q$. In the remaining sections, we only consider the case of $p < q$ and $p \nmid q$. In Section 3 we show exact values of the function $\mathcal{D}_{p,q}$ for $p + q - \text{GCD}(p,q) \le n \le 2q$. In Section 4, we show the following bounds valid for arbitrary $n \ge q$:

$$ \lfloor \frac{n-q}{p} \rfloor \le \mathcal{D}_{p,q}(n) \le 2 \lfloor \frac{n-q}{p} \rfloor. $$

We also prove an alternative bound $\mathcal{D}_{p,q}(n) \ge \lfloor \frac{2n}{p+q} \rfloor$ valid for $n \ge p+q$.

<table><caption>**Fig. 1.** Upper table: Values of $N_{3,4}(h)$ for $h = 1, \dots, 5$ together with pairs of words of length $N_{3,4}(h)$ that have the Hamming distance $h$. Lower table: Values of $\mathcal{D}_{3,4}(n)$ for $n = 6, \dots, 17$.</caption><thead><tr><th>h</th><th>N<sub>3,4</sub>(h)</th><th>example</th></tr></thead><tbody><tr><td>1</td><td>6</td><td>a a b a a <b>a</b><br>a a b a a a</td></tr><tr><td>2</td><td>8</td><td>a a b a a <b>b</b>a<br>a a b a a a <b>b</b>a</td></tr><tr><td>3</td><td>10</td><td>a a b a a <b>b</b>a a <b>b</b>a<br>a a b a a a <b>b</b>a a a</td></tr><tr><td>4</td><td>11</td><td>a a b a a <b>b</b>a a <b>b</b>a<br>a a b a a a <b>b</b>a a a <b>b</b></td></tr><tr><td>5</td><td>17</td><td>a a b a a <b>b</b>a a <b>b</b>a a a <b>b</b>a<br>a a b a a a <b>b</b>a a a <b>b</b>a a a <b>b</b>a</td></tr></tbody></table><table><thead><tr><th>h</th><th>N<sub>2,3</sub>(h)</th><th>example</th></tr></thead><tbody><tr><td>0</td><td>3</td><td>a b a<br>a b a</td></tr><tr><td>1</td><td>4</td><td>a b a <b>b</b><br>a b a a</td></tr><tr><td>2</td><td>5</td><td>a b a <b>b</b>a<br>a b a a <b>b</b></td></tr><tr><td>3</td><td>9</td><td>a b a <b>b</b>a <b>b</b>a<br>a b a a <b>b</b>a a <b>b</b></td></tr><tr><td>4</td><td>10</td><td>a b a <b>b</b>a <b>b</b>a a <b>b</b><br>a b a a <b>b</b>a a a <b>b</b></td></tr><tr><td>5</td><td>11</td><td>a b a <b>b</b>a <b>b</b>a a <b>b</b><br>a b a a <b>b</b>a a a <b>b</b>a</td></tr><tr><td>6</td><td>15</td><td>a b a <b>b</b>a <b>b</b>a a <b>b</b>a <b>b</b>a<br>a b a a <b>b</b>a a a <b>b</b>a a <b>b</b>a</td></tr><tr><td>7</td><td>16</td><td>a b a <b>b</b>a <b>b</b>a a <b>b</b>a <b>b</b>a a <b>b</b><br>a b a a <b>b</b>a a a <b>b</b>a a a <b>b</b>a</td></tr></tbody></table>

## 2 Preliminaries

Let us consider a finite alphabet $\Sigma$. If $x$ is a word of length $|x| = n$, then by $x_i \in \Sigma$ for $i = 0, \dots, n-1$ we denote its $i$th letter. We say that a word $v$ is a
factor of a word $x$ if there exist words $u$ and $w$ such that $x = uvw$. A factor $v$ is called a prefix of $x$ if $u$ is an empty word in some such decomposition and a suffix if $w$ is an empty word in some such decomposition. By $x[i..j]$ we denote the factor $x_i...x_j$.

If $x_i = x_{i+p}$ for all $0 \le i < n-p$ for some integer $p$, then $p$ is called a *period* of $x$ and the prefix of $x$ of length $p$ is called a *string period* of $x$. If $x$ has period $p$, then $y$ is called a *periodic extension of x with period p* if $y$ also has period $p$ and has $x$ as a prefix.

We say that a period $p$ is *primitive* if no proper divisor of $p$ is a period of $x$. Note that the shortest period (denoted $p = \mathbf{per}(x)$) is always primitive.

We say that a word $x$ is *primitive* if there exists no other word $u$ and integer $k > 1$ such that $x = u^k$. Note that $p$ is a primitive period of $x$ if and only if the corresponding string period is a primitive word. Two words $x$ and $y$ are each other's cyclic rotations if there exist words $u$ and $v$ such that $x = uv$ and $y = vu$. In this case we also say that $|u|$ is the shift between $x$ and $y$.

For a sequence of positive integers $(a_1, \dots, a_m)$, we define a $(a_1, \dots, a_m)$-decomposition of a word $x$ as a sequence of consecutive factors of $x$ of lengths $a_1, \dots, a_m, a_1, \dots, a_m, \dots$. The sequence ends at the last complete factor that can be cut out of $x$; see Fig. 2 for an example.

<figure><img src="image_2.png" /><figcaption>**Fig. 2.** The (1, 2, 4)-decomposition of ababbababaababaabaab is a ba bbab a ba abab a ab.</figcaption></figure>

If $p \mid q$, we can give a simple complete characterization of functions $N_{p,q}$ and $\mathcal{D}_{p,q}$.

**Fact 3.** If $p \mid q$ and $p < q$, then $\mathcal{D}_{p,q}(n) = \lfloor \frac{n}{q} \rfloor$ and $N_{p,q}(h) = q \cdot (h+1) - 1$.

*Proof.* We first show that $\mathcal{D}_{p,q}(n) \ge \lfloor \frac{n}{q} \rfloor$. Consider a positive integer $n$, words $x \in \mathcal{P}_p(n)$, $y \in \mathcal{P}_q(n)$, and the $(q)$-decompositions of $x$ and $y$: $\alpha_1, \dots, \alpha_k$ and $\beta_1, \dots, \beta_k$. Observe that $\alpha_1 = \dots = \alpha_k$ and $\beta_1 = \dots = \beta_k$ because $q$ is a period of both $x$ and $y$, but $\alpha_1 \ne \beta_1$ because $q$ is a primitive period of $y$, but not a primitive period of $x$. Hence, $\text{dist}(x, y) \ge k$.

As for the other inequality on $\mathcal{D}_{p,q}(n)$, let us take $x = (a^{p-1}b)^{\lfloor n/p \rfloor}a^n \bmod p$ and let $y$ be the word that is obtained from $x$ by changing the letters at positions $i \equiv q-1 \pmod q$ from $b$ to $c$. Then $\text{dist}(x, y) = \lfloor \frac{n}{q} \rfloor$.

Finally, the formula for $N_{p,q}(h)$ follows directly from the other one. $\square$

Henceforth, we will always assume that $p \nmid q$ and $q \nmid p$.
### 3 Exact Values for Small $n$

Let us start with the following useful lemma.

**Lemma 4.** Let $x$ be a word of length $n$ and let $y$ by its cyclic rotation by $s$ characters. If $x \neq y$, then $\text{dist}(x, y) \geq 2$. Moreover, there are two mismatches between $x$ and $y$ located at least $\text{GCD}(n, s)$ positions apart.

*Proof.* Note that $y_i = x_{(i+s) \bmod n}$ for $0 \le i < n$. Since $x \neq y$, we have $x_a \neq y_a = x_{(a+s) \bmod n}$ for some position $a$. Let $k$ be the smallest positive integer such that $x_a = x_{(a+ks) \bmod n}$. Due to $x_{(a+s) \bmod n} \neq x_a$ and $x_{(a+ns) \bmod n} = x_a$, we have $1 < k \le n$. Let $b = (a + (k - 1)s) \bmod n$. Note that $x_b \neq x_a = x_{(b+s) \bmod n} = y_b$. Hence, $a$ and $b$ are positions of two distinct mismatches between $x$ and $y$. Moreover, $b \equiv (a + (k - 1)s) \bmod n \equiv a \pmod{\text{GCD}(n, s)}$. Consequently, these two mismatches are indeed located at least $\text{GCD}(n, s)$ positions apart. $\square$

**Lemma 5.** Consider positive integers $p, q$ satisfying $p < q$ and $p \nmid q$. Let $x$ and $y$ be words of length $n$ such that $p + q - \text{GCD}(p, q) \le n \le q + p \lfloor \frac{q}{p} \rfloor - 1$, $p$ is a period of $x$, and $q$ is a period of $y$ but not a period of $x$. Then

$$ \text{dist}(x, y) \ge \lfloor \frac{n-q}{p} \rfloor + \lfloor \frac{n-q+\text{GCD}(p,q)}{p} \rfloor. $$

*Proof.* Let $u = x[0 \cdot p - 1]$ and let $v$ be the cyclic rotation of $u$ by $q$ characters. Note that $u$ is a string period of $x$, so $u \neq v$; otherwise, $q$ would be a period of $x$. Consequently, Lemma 4 provides two distinct indices $a, b$ such that $u_a \neq v_a$, $u_b \neq v_b$, and $a \le b - \text{GCD}(p, q) < p - \text{GCD}(p, q)$. Let us define

$$ \begin{aligned} A &= \{kp + a : 0 \le k < \lfloor \frac{n-q+\text{GCD}(p,q)}{p} \rfloor \}, \\ B &= \{kp + b : 0 \le k < \lfloor \frac{n-q}{p} \rfloor \}. \end{aligned} $$

Observe that

$$ \max A = \lfloor \frac{n-q+\text{GCD}(p,q)}{p} \rfloor p - p + a \le n - q + \text{GCD}(p,q) - p + a < n - q $$

and

$$ \max B = \lfloor \frac{n-q}{p} \rfloor p - p + b \le n - q - p + b < n - q. $$

Moreover,

$$ \max A \le \lfloor \frac{p[q/p]-1+\text{GCD}(p,q)}{p} \rfloor p - p + a = \lfloor \frac{q}{p} \rfloor p - p + a < q + a \le q + \min(A \cup B), $$

and

$$ \max B \le \lfloor \frac{p[q/p]-1}{p} \rfloor p - p + b = \lfloor \frac{q}{p} \rfloor p - p < q \le q + \min(A \cup B). $$

Consequently, for each $i \in A \cup B$, there are positions $x_i$ and $x_{i+q}$, and all these $2(|A| + |B|)$ positions are distinct. Moreover, observe that for $i \in A$, we
have $x_i = u_a \neq v_a = x_{i+q}$, while for $i \in B$, $x_i = u_b \neq v_b = x_{i+q}$. Thus, for $i \in A \cup B$, we have $x_i \neq x_{i+q}$, but $y_i = y_{i+q}$; hence $x_i \neq y_i$ or $x_{i+q} \neq y_{i+q}$. The positions we consider are distinct, so $dist(x, y) \geq |A \cup B| = |A| + |B| = \lfloor \frac{n-q}{p} \rfloor + \lfloor \frac{n-q+\text{GCD}(p,q)}{p} \rfloor$, as claimed. $\square$

<figure><img src="image_3.png" /><figcaption>Fig. 3. Illustration of the equalities in the bound in Lemma 5 for $\lfloor \frac{q}{p} \rfloor = 1$.</figcaption></figure>

**Lemma 6.** Consider coprime integers $p, q$ satisfying $1 < p < q$. Let $w$ be a word of length $p+q-2$ with periods $p$ and $q$, but without period 1. Moreover, let $n$ be an integer such that $p+q-1 \leq n \leq q + \lfloor \frac{q}{p} \rfloor - 1$, and let $x$ and $y$ be periodic extensions of $w$ of length $n$ preserving periods $p$ and $q$, respectively. Then $\text{per}(x) = p$, $\text{per}(y) = q$, and

$$ \text{dist}(x, y) \leq \lfloor \frac{n-q}{p} \rfloor + \lfloor \frac{n-q+1}{p} \rfloor, $$

*Proof. Claim.* If a position $i$ satisfies $i < q$ or $(i-q) \text{ mod } p < p-2$, then $x_i = y_i$.

*Proof.* The claim is clear for $i < q+p-2$ since due to the common prefix of $x$ and $y$. Thus, we consider a position $i = q+kp+r$ with $1 \leq k < \lfloor \frac{q}{p} \rfloor$ and $0 \leq r < p-2$. We have $x_{q+kp+r} = x_{q+r} = y_{q+r} = y_r = x_r = x_{kp+r} = y_{kp+r} = y_{q+kp+r}$. This is because positions $r < kp+r < q+r$ are within the common prefix of $x$ and $y$. $\square$

Consequently,

$$ \text{dist}(x, y) \leq \{i: q \leq i < n \wedge (i-q) \text{ mod } p \geq p-2\} = \\ \{j: 0 \leq j < n-q \wedge j \text{ mod } p = p-1\} + \{j: 0 \leq j < n-q \wedge j \text{ mod } p = p-2\} = \\ \lfloor \frac{n-q}{p} \rfloor + \lfloor \frac{n-q+1}{p} \rfloor, $$

as claimed. Next, we prove that $p' := \text{per}(x)$ is equal to $p$. Note that $p' \leq p$ by definition of $x$. For a proof by contradiction, suppose that $p' < p$. Note that $w$
has periods $p'$ and $q$. Moreover, $|w| = p + q - 2 \ge p' + q - 1$, so GCD($p'$, $q$) is a period of $w$. Moreover, $n \ge p+q-1 \ge p+\text{GCD}(p', q)-1$, so GCD(GCD($p'$, $q$), $p$) is a period of $x$. However, GCD(GCD($p'$, $q$), $p$) = GCD($p'$, GCD($q$, $p$)) = 1 is not a period of $w$, which is a prefix of $x$.

Similarly, suppose that $q' := \text{per}(y) < q$. We observe that $|w| = p + q - 2 \ge p + q' - 1$, so GCD($p$, $q'$) is a period of $w$. Moreover, $n \ge p+q-1 \ge p+\text{GCD}(p', q') + q - 1$, so GCD(GCD($p$, $q'$), $q$) is a period of $y$. However, GCD(GCD($p$, $q'$), $q$) = GCD($q'$, GCD($p$, $q$)) = 1 is not a period of $w$, which is a prefix of $y$. $\square$

<figure><img src="image_4.png" /><figcaption>Fig. 4. Illustration of the equalities in the lower bound in Lemma 6 for $n = q+2p-2$.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Fig. 5. A periodic prefix of a Fibonacci word and a power of a Fibonacci word that differ only at two positions.</figcaption></figure>

**Theorem 7.** If $p < q$, $p \nmid q$, and $p + q - \text{GCD}(p, q) \le n \le q + \lceil \frac{q}{p} \rceil p - 1$, then

$$ \mathcal{D}_{p,q}(n) = \left\lfloor \frac{n-q}{p} \right\rfloor + \left\lfloor \frac{n + \text{GCD}(p,q) - q}{p} \right\rfloor. \qquad (1) $$

*Proof.* Lemma 5 gives a lower bound of $\mathcal{D}_{p,q}(n)$. Our upper bound is based on Lemma 6. Let $d = \text{GCD}(p, q)$, $p' = \frac{p}{d}$, $q' = \frac{q}{d}$, and $n' = \lfloor \frac{n}{d} \rfloor$. Observe that
1 < p' < q' and p' + q' - 1 ≤ n' ≤ q' + ⌊ q' p' ⌋ p' - 1. Hence, Lemma 6 results in strings x', y' with of length n' with shortest periods p' and q' respectively, and with $dist(x', y') ≤ ⌊ n' - q' p' ⌋ + ⌊ n' - q' + 1 p' ⌋ = ⌊ n - q p ⌋ + ⌊ n - q + GCD(p, q) p ⌋.

Let c be a character occurring neither in x' nor in y'. Let us define x and y so that $x_{id+d-1} = x'_i$ and $y = x_{id+d-1} = y'_i$, and $x_j = y_j = c$ if $j \bmod d \neq d-1$. Note that $dist(x, y) = dist(x', y')$ and $|x| = |y| = n$. Also, observe that due to the choice of the character c, all periods of x and y are larger than $dn'$ or multiples of d. Consequently, $per(x) = dper(x') = dp' = p$ and $per(y) = dper(y') = dq' = q$. This completes the construction. □

**Corollary 8.** The formula (1) of Theorem 7 applies for $p + q - \text{GCD}(p, q) \le n \le 2q$.

**Fact 9.** The function $D_{p,q}(n)$ is non-decreasing for $n \ge p + q - \text{GCD}(p, q)$. Moreover:

$$D_{p,q}(n) = h \iff N_{p,q}(h-1) < n \le N_{p,q}(h)$$

$$N_{p,q}(h) = n \iff D_{p,q}(n) = h < D_{p,q}(n+1)$$

# 4 Bounds for $D_{p,q}(n)$ for Arbitrary $n$

**Lemma 10.** Let $p, q$ be integers such that $p < q$ and $p \nmid q$. Moreover, let $x$ and $y$ be words of length $n \ge q$ such that $p$ is a period of $x$, and $q$ is a period of $y$ but not of $x$. Then $dist(x, y) \ge \lfloor \frac{n-q}{p} \rfloor$.

*Proof.* Since $q$ is not a period of $x$, we have $x_i \neq x_{i+q}$ for some position $i$, $0 \le i < n-q$. Consider a set $J = \{j : 0 \le j < n-q \wedge j \equiv i \pmod p\}$. Since $p$ is a period of $x$, we have $x_j \neq x_{j+q}$ for each $j \in J$; on the other hand, $y_j = y_{j+q}$, so $x_j \neq y_j$ or $x_{j+q} \neq y_{j+q}$. Moreover, $p \nmid q$ implies that the positions $j, j+q$ across $j \in J$ are pairwise distinct. Consequently, $dist(x, y) \ge |J| \ge \lfloor \frac{n-q}{p} \rfloor$. □

**Theorem 11.** If $p < q$, $p \nmid q$, and $n \ge p+q$, then $\lfloor \frac{n-q}{p} \rfloor \le D_{p,q}(n) \le 2 \lfloor \frac{n-q}{p} \rfloor$.

*Proof.* The lower bound follows directly from Lemma 10. The upper bound is obtained using words $(x, y) \in S_{p,q,n}$ with string periods $a^{p-1}b$ and $(a^{p-1}b)^k a^r$ where $q = kp+r$. Indeed, $x$ and $y$ agree on the first $q$ positions. After that, inside each pair of corresponding fragments of length at most $p$ they have at most 2 mismatches. □

**Remark 12.** In general, it is not true that $D_{p,q}(n) \ge \lfloor \frac{n-q}{p} \rfloor$. For example, words $x = cabcacbcacbcacbcac$ and $y = cabcacacbcacbcac$ of length 19, with shortest periods $p = 4$ and $q = 6$, respectively, satisfy $dist(x, y) = 3 < \lfloor \frac{19-6}{4} \rfloor$.

**Theorem 13.** If $p < q$ and $p \nmid q$ and $n \ge p+q$, then $D_{p,q}(n) \ge \lfloor \frac{2n}{p+q} \rfloor$.
*Proof.* We use the following claim:

*Claim.* If $p < q$ and $p \nmid q$, then

(a) $N_{p,q}(1) = q + p - 1$,

(b) $N_{p,q}(2) = q + 2p - \text{GCD}(p, q) - 1$.

*Proof.* Observe that $q + p \le q + 2p - \text{GCD}(p, q) \le q + \lfloor \frac{q}{p} \rfloor p - 1$, so the values below are within the scope of Theorem 7. We have:

$$ \mathcal{D}_{p,q}(q+p-1) = \lfloor \frac{p-1}{p} \rfloor + \lfloor \frac{p+\text{GCD}(p,q)-1}{p} \rfloor = 0 + 1 = 1 $$

$$ \mathcal{D}_{p,q}(q+p) = \lfloor \frac{p}{p} \rfloor + \lfloor \frac{p+\text{GCD}(p,q)}{p} \rfloor = 1 + 1 = 2. $$

This concludes the proof of part (a).

$$ \mathcal{D}_{p,q}(q + 2p - \text{GCD}(p, q) - 1) = \lfloor \frac{2p - \text{GCD}(p,q) - 1}{p} \rfloor + \lfloor \frac{2p-1}{p} \rfloor = 1 + 1 = 2 $$

$$ \mathcal{D}_{p,q}(q + 2p - \text{GCD}(p, q)) = \lfloor \frac{2p - \text{GCD}(p,q)}{p} \rfloor + \lfloor \frac{2p}{p} \rfloor = 1 + 2 = 3. $$

This concludes the proof of part (b). □

Consider words $x \in \mathcal{P}_p(n)$, $y \in \mathcal{P}_q(n)$ and their $(p+q)$-decompositions: $\alpha_1, \dots, \alpha_k$ and $\beta_0, \dots, \beta_{k-1}$. If $\alpha_i = \beta_i$ for some $1 \le i \le k$, then, by the Periodicity Lemma, both $\alpha_i, \beta_i$ have period $\text{GCD}(p, q)$; consequently, both $x$ and $y$ have period $\text{GCD}(p, q)$, a contradiction. Hence, part (a) of the claim implies $\text{dist}(\alpha_i, \beta_i) \ge 2$ for each $i = 1, \dots, k$.

Let $\alpha_{k+1}$ and $\beta_{k+1}$ be the suffixes of $x$ and $y$ starting immediately after the last factors of the corresponding decompositions. If $|\alpha_{k+1}| < \frac{p+q}{2}$, then we already have that

$$ \text{dist}(x, y) \ge 2 \lfloor \frac{n}{p+q} \rfloor = \lfloor \frac{2n}{p+q} \rfloor. $$

Otherwise, by part (b) of the claim applied for the words $\alpha_k \alpha_{k+1}$ and $\beta_k \beta_{k+1}$, we have

$$ \text{dist}(x, y) \ge 2 \left( \lfloor \frac{n}{p+q} \rfloor - 1 \right) + 3 = 2 \lfloor \frac{n}{p+q} \rfloor + 1 = \lfloor \frac{2n}{p+q} \rfloor. $$

In both cases we obtain the desired inequality. □

# 5 Conclusions

The paper studies the following general type of question:

How much dissimilar in a whole should be two objects which are different in some specific aspect?

The answer to this type of question heavily depends on the studied type of the objects. Thus sometimes the answer is completely trivial; for example, two different strings of the same length may differ at only a single position. In this work we show that if we consider different strings of the same length that are additionally periodic, then the implied number of positions where the two strings must differ can be large. The exact number depends on the length of the strings and on their periods.
References

1. A. Amir, C. S. Iliopoulos, and J. Radoszewski. Two strings at hamming distance 1 cannot be both quasiperiodic. *Inf. Process. Lett.*, 128:54–57, 2017.

2. A. Amir, A. Levy, R. Lubin, and E. Porat. Approximate cover of strings. In J. Kärkkäinen, J. Radoszewski, and W. Rytter, editors, *28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017, July 4-6, 2017, Warsaw, Poland*, volume 78 of *LIPIcs*, pages 26:1–26:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017.

3. H. Bai, F. Franek, and W. F. Smyth. The new periodicity lemma revisited. *Discrete Applied Mathematics*, 212:30–36, 2016.

4. J. Berstel and L. Boasson. Partial words and a theorem of Fine and Wilf. *Theor. Comput. Sci.*, 218(1):135–141, 1999.

5. F. Blanchet-Sadri, D. Bal, and G. Sisodia. Graph connectivity, partial words, and a theorem of Fine and Wilf. *Inf. Comput.*, 206(5):676–693, 2008.

6. F. Blanchet-Sadri, K. Corcoran, and J. Nyberg. Fine and Wilf's periodicity result on partial words and consequences. In R. Loos, S. Z. Fazekas, and C. Martín-Vide, editors, *LATA 2007. Proceedings of the 1st International Conference on Language and Automata Theory and Applications.*, volume Report 35/07, pages 115–126. Research Group on Mathematical Linguistics, Universitat Rovira i Virgili, Tarragona, 2007.

7. F. Blanchet-Sadri and R. A. Hegstrom. Partial words and a theorem of Fine and Wilf revisited. *Theor. Comput. Sci.*, 270(1-2):401–419, 2002.

8. F. Blanchet-Sadri, T. Oey, and T. D. Rankin. Fine and Wilf's theorem for partial words with arbitrarily many weak periods. *Int. J. Found. Comput. Sci.*, 21(5):705–722, 2010.

9. F. Blanchet-Sadri, S. Simmons, A. Tebbe, and A. Veprauskas. Abelian periods, partial words, and an extension of a theorem of Fine and Wilf. *RAIRO - Theor. Inf. and Applic.*, 47(3):215–234, 2013.

10. M. G. Castelli, F. Mignosi, and A. Restivo. Fine and Wilf's theorem for three periods and a generalization of Sturmian words. *Theor. Comput. Sci.*, 218(1):83–94, 1999.

11. S. Constantinescu and L. Ilie. Generalised Fine and Wilf's theorem for arbitrary number of periods. *Theor. Comput. Sci.*, 339(1):49–60, 2005.

12. S. Constantinescu and L. Ilie. Fine and Wilf's theorem for Abelian periods. *Bulletin of the EATCS*, 89:167–170, 2006.

13. K. Fan, S. J. Puglisi, W. F. Smyth, and A. Turpin. A new periodicity lemma. *SIAM J. Discrete Math.*, 20(3):656–668, 2006.

14. N. J. Fine and H. S. Wilf. Uniqueness theorems for periodic functions. *Proceedings of the American Mathematical Society*, 16(1):109–114, 1965.

15. R. Giancarlo and F. Mignosi. Generalizations of the periodicity theorem of Fine and Wilf. In S. Tison, editor, *Trees in Algebra and Programming - CAAP'94, 19th International Colloquium, Edinburgh, U.K.*, April 11-13, 1994, *Proceedings*, volume 787 of *Lecture Notes in Computer Science*, pages 130–141. Springer, 1994.

16. S. Holub. On multiperiodic words. *ITA*, 40(4):583–591, 2006.

17. J. Justin. On a paper by Castelli, Mignosi, Restivo. *ITA*, 34(5):373–377, 2000.

18. J. Karhumäki, S. Puzynina, and A. Saarela. Fine and Wilf's theorem for *k*-abelian periods. *Int. J. Found. Comput. Sci.*, 24(7):1135–1152, 2013.

19. F. Manea, R. Mercas, and D. Nowotka. Fine and Wilf's theorem and pseudo-repetitions. In B. Rovan, V. Sassone, and P. Widmayer, editors, *Mathematical*
*Foundations of Computer Science 2012 - 37th International Symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012. Proceedings*, volume 7464 of *Lecture Notes in Computer Science*, pages 668–680. Springer, 2012.

20. F. Mignosi, A. Restivo, and P. V. Silva. On Fine and Wilf's theorem for bidimensional words. *Theor. Comput. Sci.*, 292(1):245–262, 2003.

21. F. Mignosi, J. Shallit, and M. Wang. Variations on a theorem of Fine & Wilf. In J. Sgall, A. Pultr, and P. Kolman, editors, *Mathematical Foundations of Computer Science 2001, 26th International Symposium, MFCS 2001 Marianske Lazne, Czech Republic, August 27-31, 2001, Proceedings*, volume 2136 of *Lecture Notes in Computer Science*, pages 512–523. Springer, 2001.

22. W. F. Smyth and S. Wang. A new approach to the periodicity lemma on strings with holes. *Theor. Comput. Sci.*, 410(43):4295–4302, 2009.

23. R. Tijdeman and L. Q. Zamboni. Fine and Wilf words for any periods II. *Theor. Comput. Sci.*, 410(30-32):3027–3034, 2009.