Vesa Halava

Tero Harju

Tomi Kärki

Interaction properties of relational periods

Keywords: period, compatibility relation, partial word, Fine, Wilf 2 Similarity relations, Nancy, France

We consider relational periods where the relation is a compatibility relation on words induced by a relation on letters. We introduce three types of periods, namely global, external and local relational periods, and we compare their properties by proving variants of the theorem of Fine and Wilf for these periods.

Introduction

Similarity relations, i.e., compatibility relations on words induced by relations on letters were introduced as a generalization of partial words in [START_REF] Halava | Relational codes of words[END_REF] (i) . There and in [START_REF] Halava | Defect theorems with compatibility relations[END_REF][START_REF] Kärki | Compatibility relation on codes and free monoids[END_REF] the main focus was on the effect of these relations on coding properties and on the defect theorem of words. In the article [START_REF] Halava | The theorem of Fine and Wilf for relational periods[END_REF] we started the study of the interaction properties of periods with respect to similarity relations. By the interaction property we mean that if a sufficiently long word has two periods then it also has another nontrivial period depending on the original periods. The theorem of Fine and Wilf is one of the cornerstones in combinatorics on words. In this theorem the derived period is the greatest common divisor of the original periods [START_REF] Fine | Uniqueness theorems for periodic functions[END_REF]. Actually, this topic was the starting point of the study of partial words in the seminal paper of J. Berstel and L. Boasson in 1999 [START_REF] Berstel | Partial words and a theorem of Fine and Wilf[END_REF]. They proved a variant of the theorem of Fine and Wilf for partial words with one hole. Since then several papers on period properties of partial words has been published [START_REF] Blanchet-Sadri | A periodicity result of partial words with one hole[END_REF][START_REF] Blanchet-Sadri | Periodicity on partial words[END_REF][START_REF] Blanchet-Sadri | Local periods and binary partial words: an algorithm[END_REF][START_REF] Blanchet-Sadri | Partial words and the critical factorization theorem[END_REF][START_REF] Blanchet-Sadri | Partial words and a theorem of Fine and Wilf revisited[END_REF][START_REF] Shur | Partial words and the period interaction property[END_REF]. F. Blanchet-Sadri et al. studied the theorem of Fine and Wilf for partial words with local periods and with arbitrarily many holes. A.M. Shur and Yu.V. Gamzova investigated the case of global periods. We continue the study of this topic by introducing global, external and local relational periods as generalizations of periods of partial words. Using these periods we prove new variants of Fine and Wilf's theorem. Especially, our aim is to compare the interaction properties of different types of periods. is an infinite catenation of a word x ∈ A + , we denote w = x ω . We shall consider rational powers of words, i.e., if w = a 1 a 2 . . . a n , where a i is a letter for each positive integer i ≤ n, and t = k • n + r for 0 ≤ r < n, then w t/n = w k • a 1 a 2 . . . a r .

For a relation R ⊆ X × X, we often write x R y instead of (x, y) ∈ R. The restriction of R on Y ⊆ X is R Y = R ∩ (Y × Y ). A relation R is a compatibility relation if it is both reflexive and symmetric, i.e., (i) ∀x ∈ X : x R x, and (ii) ∀x, y ∈ X : x R y =⇒ y R x. For example, both the identity relation ι X = {(x, x) | x ∈ X} and the universal relation {(x, y) | x, y ∈ X} are compatibility relations on X.

A relation R on words over A is called a similarity relation, if its restriction on letters is a compatibility relation and, for words

u = u 1 • • • u m and v = v 1 • • • v n (u i , v j ∈ A), the relation R satisfies u 1 • • • u m R v 1 • • • v n ⇐⇒ m = n and u i R v i for all i = 1, 2, . . . , m.
Note that R is a compatibility relation. For an arbitrary relation S on letters, S denotes the similarity relation generated by S, i.e., S is the similarity relation induced by the reflexive and symmetric closure of S. For a similarity relation R, words u and v satisfying u R v are said to be R-similar or R-compatible. If the words are not R-compatible, they are said to be R-incompatible. we have abba S baab but, for instance, the words abc and cac are not S-similar.

Example 2 A partial word of length n over an alphabet A is a partial function w : {1, 2, . . . , n} → A.

The domain D(w) of w is the set of positions p ∈ {1, 2, . . . , n} such that w(p) is defined. The set H(w) = {1, 2, . . . , n} \ D(w) is the set of holes of w. A partial word can also be seen as a word over the augmented alphabet A ♦ = A ∪ {♦}, where ♦ is interpreted as a special "do not know" symbol [START_REF] Berstel | Partial words and a theorem of Fine and Wilf[END_REF]. In [START_REF] Halava | Relational codes of words[END_REF] we have shown that using similarity relations the compatibility relation of partial words can be expressed by R ↑ = {(♦, a) | a ∈ A} .

In this case, the word x is called (purely) p-periodic. The smallest integer which is a period of x is called the (minimal) period of x. Here we denote it by π(x), or shortly by π, if the word x is clear from the context. For partial words, two types of periods were defined in [START_REF] Berstel | Partial words and a theorem of Fine and Wilf[END_REF]: A partial word w has a (partial) period p if, for all i, j ∈ D(w), i ≡ j (mod p) =⇒ w(i) = w(j).

A partial word w has a local (partial) period p if i, i + p ∈ D(w) =⇒ w(i) = w(i + p).

For words with compatibility relation on letters, we will now define three types of periods. We call these periods relational periods.

Definition 1 Let R be a compatibility relation on an alphabet A. For a word

x = x 1 • • • x n ∈ A + , an integer p ≥ 1 is (i) a global R-period of x if, for all i, j ∈ {1, 2, . . . , n}, we have i ≡ j (mod p) =⇒ x i R x j ;
(ii) an external R-period of x if there exists a word y = y 1 • • • y p such that, for all i ∈ {1, 2, . . . , n} and j ∈ {1, 2, . . . , p}, we have

i ≡ j (mod p) =⇒ x i R y j .
In this case, the word y is called an external word of x.

(iii) a local R-period of x if, for all i ∈ {1, 2, . . . , n -p}, we have

x i R x i+p .
These definitions generalize naturally to infinite words. For a word x, the minimal global (resp. external, local) R-period is denoted by π R,g (x) (resp. π R,e (x), π R,l (x)). In the sequel, we may omit the subscript R or the argument x if the relation R or the word x is clear from the context. Of course, these periods may coincide. Next we give an example where all the above mentioned minimal periods are different.

Example 3 Let A = {a, b, c, d} and define (d,a)} be a compatibility relations on the alphabet A. Clearly, the minimal pure period π(x) = 8. By the definition of R, we see that 2 is a local R-period of x. Since (x 7 , x 8 ) = (b, d) ∈ R, 1 is not a local period and therefore, we have π R,l (x) = 2. Neither 1 nor 2 is an external R-period of x, since otherwise the letter y 1 or respectively y 2 in the external word y is related to every letter of the alphabet, which is a contradiction. Since y = bab satisfies the conditions of an external word in Def. 1(ii), we have π R,e (x) = 3. Furthermore, since (b, d) ∈ R, we have π R,g (x) > 5. Indeed, π R,g (x) = 6, because of the relation a R d. Hence, for a word x, we have

x = babbbcbd. Let R = {(a, b), (b, c), (c, d),
π = 8 > π g = 6 > π e = 3 > π l = 2.
The next theorem shows how different types of periods are related to each other.

Theorem 1 Every pure period of a word x is a relational (global, external and local) R-period for any compatibility relation R on A. Every global R-period of x is an external R-period of x and a local R-period of x. Thus, for a word x, we always have π ≥ π g ≥ max(π e , π l ).

Proof: Let R be a compatibility relation. By reflexivity, ι ⊆ R, and therefore the first statement holds.

Note that if x = x 1 • • • x n has a period p, then y = x 1 • • • x p is an external word of x.
Similarly, this choice of y also shows that a global R-period is an external R-period. Clearly, a global period satisfies the definition of a local period. For the minimal periods, these considerations imply the inequalities of the statement. ✷

Note that every external period is not necessarily a local period and every local period need not be an external period. For example, in Example 3 the minimal local R-period π l is not an external R-period, and furthermore, π e is not a local R-period. There we have π e > π l . Next we give an example where

π l > π e . Example 4 Let R = {(a, b), (b, c), (c, d), (d, a)} and let x = adcbccccbd.
Consider first the minimal local R-period of x. Since (x 9 , x 10 ) = (x 4 , x 2 ) = (b, d) ∈ R and 3 is a local R-period, we have π l = 3. Since x 1 = a, x 4 = b, x 7 = c and x 10 = d, there cannot exist any external word y = y 1 y 2 y 3 of length 3. Otherwise, y 1 would be compatible with all letters of the alphabet {a, b, c, d}. Hence, 3 is not an external R-period. For the same reason 1 is not an external R-period, but by choosing y = bc, we see that π e = 2. As noted above, 2 is not a local period. Since (a, c) ∈ R, the minimal global period satisfies π g > 7. Actually, π g = 8 since a R b. Clearly, π = 10. Hence,

π = 10 > π g = 8 > π l = 3 > π e = 2.
If the compatibility relation R is also transitive, all relational periods coincide. This is clear, since transitive compatibility relation R is actually a congruence, and there is a one-to-one correspondence between any relational period p of a word w = w

1 • • • w n ∈ Σ * and the pure period p of [w] = [w 1 ] • • • [w n ] ∈ Σ * /R
, where [w] denotes the congruence class of a word w. Hence, we have the following result.

Theorem 2 If a similarity relation R is transitive, then P g (x) = P e (x) = P l (x), where P g (x) (resp. P e (x), P l (x)) is the set of all global (resp. external, local) R-periods of a word x. Moreover,

π g (x) = π e (x) = π l (x).
If R is not transitive, local R-periods differ from global and relational periods by the following property.

Lemma 1 If p is a global R-period or an external R-period, then any multiple of p is a global R-period or an external R-period, respectively. This need not be the case for local R-periods.

Proof: Suppose that p is a global R-period of x and let i ≡ j (mod kp), where k is a nonnegative integer. Then clearly i ≡ j (mod p) and, by the assumption, x i R x j . Hence kp is a global R-period. The proof is similar for external R-periods. Consider then a word x = abc and a relation R = {(a, b), (b, c)} . The word x has 1 as a local R-period, but 2 is not a local R-period. Thus multiples of local R-periods are not necessarily local R-periods. ✷

Finally we note that external periods are not very meaningful with partial words. Namely, any integer p ≥ 1 is an external R ↑ -period of any partial word. Indeed, we may choose y = (♦) p for an external word. Consequently, for partial words, we always have π e = 1.

Variants of the theorem of Fine and Wilf

The theorem of Fine and Wilf [START_REF] Fine | Uniqueness theorems for periodic functions[END_REF] is well-known in combinatorics on words: Theorem 3 If a word x has periods p and q, and is of length at least p + qgcd(p, q), then x also has a period gcd(p, q). J. Berstel and L. Boasson gave a variant of this theorem for partial words with one hole in [START_REF] Berstel | Partial words and a theorem of Fine and Wilf[END_REF].

Theorem 4 Let w be a partial word of length n and suppose that it has local R ↑ -periods p and q. If H(w) is a singleton and if n ≥ p + q, then w is purely gcd(p, q)-periodic.

Furthermore, they showed that this bound on the length is sharp. Generalizations for several holes were considered, for example, by F. Blanchet-Sadri in [START_REF] Blanchet-Sadri | Periodicity on partial words[END_REF] and F. Blanchet-Sadri and R.A. Hegstrom in [START_REF] Blanchet-Sadri | Partial words and a theorem of Fine and Wilf revisited[END_REF], where it was shown that local partial periods p and q force a sufficiently long word to have a (global) partial period gcd(p, q) when certain unavoidable cases (special words) are excluded. The bound on the length depends on the number of holes in the word. On the other hand, A.M. Shur and Yu.V. Gamzova found bounds for the length of a word with k holes such that (global) partial periods p and q imply a (global) partial period gcd(p, q) [START_REF] Shur | Partial words and the period interaction property[END_REF]. These results of partial words with several holes show that finding good formulations for the interaction of periods in the case of arbitrary relational periods is not possible except for equivalence relations. Namely, any non-transitive compatibility relation R must have letter relations (x 1 , x 2 ), (x 2 , x 3 ) ∈ R, but (x 1 , x 3 ) ∈ R for some letters x 1 , x 2 , x 3 . Then the role of the letter x 2 in R is exactly the same as the role of ♦ in R ↑ and all binary counter examples of Fine and Wilf's theorem for partial words apply to words with compatibility relation R over the alphabet {x 1 , x 2 , x 3 }. However, some interaction results can be obtained.

If the relation R is an equivalence relation, we do not have to specify the type of an R-period, since the definitions of the relational periods coincide by Theorem 2. We have the following theorem proved in [START_REF] Halava | The theorem of Fine and Wilf for relational periods[END_REF].

Theorem 5 Let R be an equivalence relation. If a word has R-periods p and q and the length of the word is at least p + qgcd(p, q), then the word has also an R-period gcd(p, q). The bound on the length is strict.

As was mentioned above, the theorem of Fine and Wilf cannot be generalized for relational periods of a non-transitive compatibility relation unless some restrictions on the number of relations (holes) and exclusions of some special cases are given. Despite this fact, it might be possible to get some new interesting variations of the theorem, for example, by assuming that one of the periods is pure and only the other one is relational by the relation R = ι. Unfortunately, this restriction seems to be insufficient in that extent that sometimes no finite bound on the length of the word can be obtained for the interaction of periods. For example, there exists an infinite word with a pure period q and a local R-period p such that it does not have a local R-period gcd(p, q). Example 5 Let R = {(a, b), (b, c)} . Note that every non-transitive compatibility relation must have a subrelation similar to this one such that a and c are not compatible. Consider an infinite word x = (bbcab) ω .

Clearly, w has a pure period q = 5. It also has a local R-period p = 3, since the distance of the letters a and c in x cannot be 3. Since (x 3 , x 4 ) = (a, c) ∈ R, gcd(p, q) = 1 is neither a local period nor a global period by Theorem 1.

In the previous example the notion of a local relational period is too weak for the desired interaction result. However, depending on the type of the relational period p we get diverse results as will be shown in the sequel. One variant of Fine and Wilf's theorem was already considered in [START_REF] Halava | The theorem of Fine and Wilf for relational periods[END_REF]. The following theorem was obtained.

Theorem 6 Let P and Q be positive integers with gcd(P, Q) = d. Denote P = pd and Q = qd. Suppose that a word w has a (pure) period Q and a global R-period P . Let B g = B g (p, q) be defined by Table 1. If |w| ≥ B g d, then also gcd(P, Q) = d is a global R-period of the word w. This bound on the length is sharp.

B g (p, q) p < q p > q p, q odd p + 1 2 q q + q -1 2 p p odd, q even p + 1 2 q p + 1 2 q p even, q odd q + q -1 2 p q + q -1 2 p

Tab. 1: Hence, one global period with one pure period is strong enough to imply another nontrivial global period. Moreover, according to Theorem 1, one global period must also imply an external and a global relational period. However, the optimal bound on the length of the word can be different in these cases. The bound B g in Theorem 6 is just one example of interaction bounds defined more precisely in the following.

Definition 2 Let P ≥ 2 and Q ≥ 3 be positive integers with gcd(P, Q) = d and let t 1 and t 2 be types of relational periods. A positive integer B = B(P, Q) is called the bound of t 1 -t 2 interaction for P and Q, if it satisfies the following conditions:

(i) The bound B is sufficient, i.e., for any similarity relation R and for any word w with length |w| ≥ B having a (pure) period Q and a t 1 -type R-period P , the number gcd(P,

Q) = d is a t 2 -type R-period of w.
(ii) The bound is strict, i.e., there exist a similarity relation R and a word w with length |w| = B -1 having a (pure) period Q and a t 1 -type R-period P such that gcd(P,

Q) = d is not a t 2 -type R-period of w.
Note that in the definition we exclude trivial cases by assuming that P ≥ 2 and Q ≥ 3. Namely, if Q ≤ 2, then the word contains at most two letters. This is the case of Theorem 5, since there are no non-transitive compatibility relations on a binary alphabet.

The following lemma shows that it is sufficient to consider the case where gcd(P, Q) = 1. In the proof we use a standard approach which was also used in the proof of Theorem 5 in [START_REF] Halava | The theorem of Fine and Wilf for relational periods[END_REF].

Lemma 2 Let P and Q be positive integers with gcd(P, Q) = d > 1. Denote P = pd and Q = qd. If B is the bound of t 1 -t 2 -interaction for p and q, then Bd is the bound of t 1 -t 2 -interaction for P and Q.

Proof: Suppose that a word w has a pure period Q and a relational t 1 -type period P . Denote the ith letter of w by w i and assume that |w| ≥ Bd. Let us now consider the word

w (i) = w i w i+d • • • w i+kid , where 1 ≤ i ≤ d and k i = |w|-i d .
Clearly, the word w (i) has a pure period q and a t 1 -type relational

R-period p. Since |w (i) | ≥ B for every i = 1, 2, . . . , d, then 1 is a t 2 -type relational R-period for all the words w (i) . Consequently, d is a t 2 -type relational R-period of w.
In order to prove that the bound Bd is strict, we give an example of a word u of length Bd -1 such that it has a period Q and an R-period P but no R-period d.

Suppose that v = v 1 v 2 • • • v B-1
is a word such that it has a pure period q and a t 1 -type period p, but gcd(p, q) = 1 is not a t 2 -type relational period of v. By the definition of B, such a word exists. Let a be some letter in the alphabet A and define the word u by the following formula:

u = a d-1 v 1 a d-1 v 2 • • • a d-1 v B-1 a d-1 .
Now u has a pure period Q = qd and a t 1 -type period P = pd, but by the properties of v, gcd(P, Q) = d cannot be a t 2 -type R-period of u. ✷

Hence, using our new notation and the previous lemma we may state the result of Theorem 6 in the following way.

Theorem 6 (reformulated) Let p and q be positive integers with gcd(p, q) = 1. The bound of globalglobal interaction for p and q is B g (p, q) given by Table 1.

Global-local interaction

Instead of attaining a global period gcd(p, q) we loosen our requirements and consider the case where the greatest common divisor becomes a local relational period. Theorem 7 Let p and q be positive integers with gcd(p, q) = 1. Let k be the smallest integer satisfying kp ≡ ±1 (mod q). The bound of global-local interaction for p and q is B l (p, q) = q + kp -1 if 1 ≡ q -1 (mod p) and kp ≡ +1 (mod q), q + kp otherwise.

We divide the proof into two parts. In the sequel, we use the notation [n] q for the least positive residue of an integer n (mod q), i.e., [n] q is the positive integer m satisfying 1 ≤ m ≤ q and m ≡ n (mod q). Lemma 3 The bound B l (p, q) defined in Theorem 7 is sufficient.

Proof: Denote B l = B l (p, q). Assume that a word w has a pure period q and a global R-period p. We show that 1 is a local R-period of w if |w| ≥ B l . By the assumption, the word w is a rational power of a word of length q. Thus in w there are at most q different letters. Hence, the word w has a local R-period 1 if and only if, for all n = 1, 2, . . . , q, we have

w [n]q R w [n+1]q .
(1)

We show that, for each n ∈ {1, 2, . . . , q}, there exist integers i n , j n ∈ N such that

[n] q + i n q ≡ [n + 1] q + j n q (mod p) (2)
and both sides of the congruence belong to the set {1, 2, . . . , B l }. This implies together with the global period p of w that Eq. ( 1) must be satisfied if |w| ≥ B l . Case 1. Assume first that kp ≡ 1 (mod q). For n ∈ {1, 2, . . . , q -1}, choose j n = kp-1 q and i n = 0. Note that j n is an integer by the definition of k. Then

(n + 1) + j n q = n + 1 + kp -1 = n + kp ≡ n (mod p).
Clearly, both sides of the congruence belong to {1, 2, . . . , B l }. Furthermore, let j q = kp-1 q + 1 and i q = 0. Now 1 + j q q = 1 + kp -1 + q = q + kp ≡ q (mod p).

The left hand side is less than or equal to B l only if 1 ≡ q -1 (mod p). However, in the special case 1 ≡ q -1 (mod q), we can choose i q = kp-1 q and j q = 0 so that q + i q q = q + kp -1 ≡ q -1 ≡ 1 (mod p).

Now the left hand side is exactly B l . Case 2. Assume that kp ≡ -1 (mod q) and, for n ∈ {1, 2, . . . , q -1}, let i n = kp+1 q and j n = 0. Note that i n is an integer by the definition of k. Hence,

n + i n q = n + kp + 1 ≡ n + 1 (mod p).
Choose furthermore i q = kp+1 q -1 and j q = 0. Then q + i q q = q + kp + 1q ≡ 1 (mod p).

Note that both sides of both congruences belong to the set {1, 2, . . . , B l }. Hence, we have shown that Eq. ( 1) is satisfied for all n = 1, 2, . . . , q, if |w| ≥ B l . Therefore w must have gcd(p, q) = 1 as a local relational period. ✷

Lemma 4

The bound B l (p, q) defined in Theorem 7 is strict.

Proof: We prove that there exists a word w of length B l -1 such that it has a global period p and a pure period q but no local period gcd(p, q) = 1. We show that, at least for one index n ∈ {1, 2, . . . , q}, there is no solution i n , j n of Eq. ( 2) such that both sides of the equation belong to the set {1, 2, . . . , B l -1}. Without contradicting the assumption that p is a global period of w we may then assume that (w [n]q , w [n+1]q ) ∈ R and therefore gcd(p, q) = 1 is not a local R-period of w. Case 1. Let us first assume that kp ≡ 1 (mod q) and 1 ≡ q -1 (mod p). Consider the equation

q + iq ≡ 1 + jq (mod p).
Note that in the solution j = j q = kp-1 q + 1, i = i q = 0, we have 1 + j q q = q + kp = B l . We prove that there is no smaller solution, i.e., there are no integers i and j such that max(q + iq, 1 + jq) < B l . Note that if such a solution exists, then we may assume that either i = 0 or j = 0. Namely, if i > j for some solution, then q + (ij)q ≡ 1 (mod p) is a smaller solution. Similarly, if j > i, then q ≡ 1 + (ji)q (mod p) is a smaller solution. Thus, assume first that, for some j ∈ N, we have q ≡ 1 + jq (mod p) and max(q, 1+jq) < q+kp. Now j > 0. Otherwise, 1+lp = q for some l ∈ N. This means that lp ≡ -1 (mod q). By the definition of k, we have l > k so that 1 ≡ kp (mod q) and 1 < kp < lp = q -1. This is a contradiction. Hence, j = 0 and max(q, 1 + jq) = 1 + jq. Since q ≡ 1 + jq (mod p), there exists s ∈ N such that 1 + jqq = sp. This means that sp ≡ 1 (mod q) and therefore s ≥ k. Thus, we have

max(q, 1 + jq) = 1 + jq = sp + q ≥ kp + q.
Again, we have a contradiction.

Assume next that, for some i ∈ N, we have

q + iq ≡ 1 (mod p)
and max(q+iq, 1) = q+iq < q+kp. Hence, there exists s ∈ N such that q+iq-1 = sp and consequently sp ≡ -1 (mod q). By the definition of k, we again have s > k. Now q > q + iqkp = sp + 1kp > 1.

On the other hand, q + iqkp ≡ -1 (mod q). We conclude that q + iqkp = q -1. Hence,

1 ≡ q + iq ≡ q + iq -kp = q -1 (mod p)
and we end up in a contradiction with our assumption. Thus, let us define a rational power

w = (ac q-2 b) (B l -1)/q
in ternary alphabet {a, b, c} with length B l -1. By the above considerations, if a R c and b R c and gcd(p, q) = 1, then the word w has a period q and a global R-period p. However, 1 is not a local R-period of w if a and b are unrelated by the compatibility relation R.

Case 2. Assume next that kp ≡ 1 (mod q) and 1 ≡ q -1 (mod p). Consider the congruence (q -1) + iq ≡ q + jq (mod p).

Note that in the solution i = i q-1 = 0, j = j q-1 = kp-1 q we have q + j q-1 q = q + kp -1 = B l . Assume then that there is a smaller solution. Again, we may assume that either i = 0 or j = 0. Suppose that, for some j ∈ N, we have q -1 ≡ q + jq (mod p)

and max(q -1, q + jq) < B l . Now jq + 1 = sp for some s ∈ N. As before, we have sp ≡ 1 (mod q). Thus we must have s ≥ k. Hence

max(q -1, q + jq) = q + jq = q + sp -1 ≥ q + kp -1 = B l ;
a contradiction. Suppose then that, for some i ∈ N,

q -1 + iq ≡ q (mod p)
and max(q -1 + iq, q) < B l . Note that i > 0. Now there exists s ∈ N such that iq -1 = sp. Hence sp ≡ -1 (mod q) and s > k. Thus,

max(q -1 + iq, q) = q -1 + iq = q -1 + sp + 1 > q + kp > B l .
Again we end up in a contradiction. In this case, the rational power

w = (c q-2 ab) (B l -1)/q
and the relation R = {(a, c), (b, c)} together with the above calculations show that our bound B l is strict as in the previous case. Case 3. Finally assume that kp ≡ -1 (mod q). Consider the same congruence as in Case 2. However, note that now B l = q + kp. Similarly as above, we see that, for any i ∈ N satisfying q -1 + iq ≡ q (mod p), we must have max(q -1 + iq, q) ≥ kp + q = B l . If j ∈ N satisfies q -1 ≡ q + jq (mod p), then j > 0 and q + jqq + 1 = sp for some positive integer s. We have sp ≡ 1 (mod q) and therefore s > k. It follows that max(q -1, q + jq) = sp + q -1 ≥ (k + 1)p + q -1 = (kp + q) + p -1 > B l .

Hence, the word w = (c q-2 ab) (B l -1)/q and R = {(a, c), (b, c)} show that B l is strict also in this case. ✷ Theorem 7 follows now directly from Lemma 3 and Lemma 4. Note that the value of k can be calculated easily using an elementary theorem by Fermat and Euler. Namely, the smallest solution k ′ of the equation k ′ p ≡ 1 (mod q) is called the reciprocal of p modulo q and, by the theorem,

k ′ = [p ϕ(q)-1 ] q ,
where ϕ is the Euler's totient function. Thus, we have k = min(k ′ , qk ′ ), since (qk ′ )p ≡ -1 (mod q).

Global-external interaction

Under the same assumptions as in the previous section but replacing the local relational periodicity by external periodicity we obtain the next interaction theorem. Like before, [n] q is the least positive residue of an integer n (mod q). Theorem 8 Let p and q be positive integers with gcd(p, q) = 1. Denote h = 1 + q 2 p. The bound of global-external interaction for p and q is

B e (p, q) = min(h + [h] q -1, h + (q -[h] q ) + 1) if q is odd, max(h, h + [h] q -(p + 1)) if q is even.
The proof of the theorem is divided into two lemmata like in the previous section.

Lemma [START_REF] Blanchet-Sadri | Partial words and the critical factorization theorem[END_REF] The bound B e (p, q) defined in Theorem 8 is sufficient.

Proof: Assume that a word w has a pure period q and a global R-period p. Like in Lemma 3, the word w is a rational power of a word of length q and therefore contains at most q different letters. If one of the letters, say a, is R-compatible with all the other letters, then the word w has also an external relational period 1. Namely, y = a is an external word of w. On the other hand, if this is not the case and the considered alphabet A does not contain any letters not occurring in w, then 1 is not an external R-period.

Hence, the existence of such a letter a is crucial for the bound of global-external interaction. We use the following notation. For an integer n ∈ {1, 2, . . . , q}, we define τ (n) = max{m | 1 ≤ m ≤ |w|, m ≡ n (mod q)}. Note that if the word w has q different letters, then τ (n) is the last occurrence of the letter w n in w. Since w has the global relational period p, it follows that w n must be related to all letters in the positions

S(n) = {n + ip | i = 0, 1, . . . , |w| -n p } and
T (n) = {τ (n) -ip | i = 1, 2, . . . , τ (n) -1 p }.
Next we prove that if |w| ≥ B l , then the union S(n) ∪ T (n) contains at least q numbers, i.e.,

|S(n) ∪ T (n)| = 1 + |w| -n p + τ (n) -1 p ≥ q. (3)
Since τ (n) ≡ n (mod q), these numbers form a complete residue system (mod q). Since q is a period of w, this means that w n is R-compatible with all letters w i for i = 1, 2, . . . , q, and therefore 1 is an external R-period of w.

Consider the case where q is odd. Suppose first that |w| ≥ B e = h + [h] q -1, where h = 1 + q-1 2 p. Then the letter w h = w [h]q occurring in the positions h and [h] q is related to all the other letters. Namely, by the definition of B e , we have τ ([h] q ) ≥ h and

1 + |w| -[h] q p + τ ([h] q ) -1 p ≥ 1 + q -1 2 + q -1 2 = q.
Hence, Eq. ( 3) is satisfied for n = [h] q . Suppose next that |w| ≥ B e = h + (q -[h] q ) + 1. Now the letter in position 1 is related to all other letters. Namely, we have τ (1) ≥ B e and

|w| -1 p ≥ τ (1) -1 p ≥ q -1 2 .
Hence, |S(1) ∪ T (1)| ≥ 1 + q-1 2 + q-1 2 = q as above and Eq. ( 3) is satisfied for n = 1. Let us then assume that q is even. Hence h = 1 + q 2 p. We note first that max(h, h

+ [h] q -(p + 1)) = h if and only if [h] q ≤ p + 1. If this is the case, we have |w| -[h] q p ≥ q 2 p + 1 -[h] q p ≥ q 2 -1.
On the other hand, if [h] q > p + 1, we have

|w| -[h] q p ≥ q 2 p + 1 + [h] q -(p + 1) -[h] q p = q 2 -1.
Furthermore, τ ([h] q ) ≥ h in both cases and

τ ([h] q ) -1 p ≥ q 2 p + 1 -1 p = q 2 .
Thus, Eq. ( 3) is satisfied for n = [h] q . ✷ Lemma 6 The bound B e (p, q) defined in Theorem 8 is strict.

Proof: In order to prove that our bound is strict, we show that, for some suitable R, there exists a word w of length B e -1 with a period q and with a global period p such that none of its letters is related to all other letters. We use the notation of Lemma 5. It suffices to prove that, for every integer n ∈ {1, 2, . . . , q}, the set S(n) ∪ T (n) does not contain a complete residue system (mod q), i.e., Eq. ( 3) is not satisfied if |w| = B e -1. Namely then we may define a relation R on the alphabet A = {a 1 , a 2 , . . . , a q } in such a way that w n is R-compatible only with the letters in the positions S(n) ∪ T (n) and hence none of the q different letters is related to all other letters. Then the rational power

w = (a 1 a 2 • • • a q )
Be -1 q has a pure period q and a global period p, but it does not have gcd(p, q) = 1 as an external R-period. We consider four cases: Case 1. Let q be odd and

B e = h+[h] q -1 = q-1 2 p+[h] q . Assume that |w| = B e -1 = q-1 2 p+[h] q -1. Let 1 ≤ n ≤ q and suppose furthermore that n = [h] q + ip + j, where i ∈ Z and 0 ≤ j < p -1. Now |w| -n p = q-1 2 p + [h] q -1 -([h] q + ip + j) p = q -1 2 -i -1.
By the definition of the bound, we have B e = h + [h] q -1 ≤ h + (q -[h] q ) + 1. Since q is odd, the inequality must be strict. This implies that, for any number l ∈ {h, h + 1, . . . , B e }, we have [l] q ≥ [h] q . Therefore,

τ (n) = h + ip + j if n ∈ {1, 2, . . . , [B e ] q -1}, h -q + ip + j if n ∈ {[B e ] q , [B e ] q + 1, . . . , q} and moreover, τ (n) -1 p ≤ 1 + q-1 2 p + ip + j -1 p = q -1 2 + i.
We conclude that the set S(n) ∪ T (n) contains at most ( q-1 2i) + ( q-1 2 + i) = q -1 elements. Hence, it does not form a complete residue system (mod q). Case 2. Let q be odd and

B e = h + (q -[h] q ) + 1 = q-1 2 p + q + 2 -[h] q . Then |w| = B e -1 = q-1 2 p + q + 1 -[h] q .
Like above, denote n = [h] q + ip + j, where i ∈ Z and 0 ≤ j < p -1. By the assumption, h + [h] q -1 ≥ h + q -[h] q + 1 and therefore 2[h] q ≥ q + 2. Thus, we have

|w| -n p = q-1 2 p + q + 1 -[h] q -([h] q + ip + j) p ≤ q-1 2 p -1 -ip -j p = q -1 2 -i -1.
By the same reasoning as in Case 1, we have τ (n) ≤ h + ip + j and

τ (n) -1 p ≤ q -1 2 + i.
This means that Eq. ( 3) is not satisfied for any n. Case 3. Let q be even and |w| = B e -1 = h -1 = q 2 p. For any n ∈ {1, 2, . . . , B}, we have

|w| -n p ≤ q 2 -1 and τ (n) -1 p ≤ q 2 -1.
Thus, again Eq. ( 3) is not satisfied. Case 4. Let q be even and

|w| = B e -1 = h + [h] q -(p + 1) -1 = q 2 p + [h] q -p -1.
As in the previous cases, denote n = [h] q + ip + j, where i ∈ Z and 0 ≤ j < p -1. We have

|w| -n p = q 2 p + [h] q -p -1 -([h] q + ip + j) p = q 2 -i -2.
Next we prove that, for each l ∈ {h, h + 1, . . . , B e -1}, we have [l] q ≥ [h] q . Let us assume the contrary. Then, for some l ∈ {h, h + 1, . . . , B e -1}, we have [l] q = 1. Consider now the number l -q 2 p. On one hand, l -

q 2 p ≡ l - q 2 p + qp ≡ 1 + q 2 p ≡ [h] q (mod q),
and on the other hand, l -

q 2 p ≤ B e -1 - q 2 p < [h] q .
This is a contradiction. Hence, [l] q ≥ [h] q and therefore τ (n) ≤ h + ip + j, and

τ (n) -1 p ≤ q 2 p + 1 + ip + j -1 p = q 2 + i. Thus, |S(n) ∪ T (n)| ≤ 1 + ( q 2 -i -2) + ( q 2 + i) = q -1. ✷

External interactions

In the previous two sections we found interaction bounds for one pure period and one global relational period. On the other hand, Example 5 shows that if we replace the global period by a local period such bounds do not necessarily exist. Is this also true if the global period is replaced by an external period? Let us assume that a word w has a pure period q and an external period p. Let y = y 1 • • • y p be an external word of w, i.e., for every j ∈ {1, 2, . . . , p}, y j R w i whenever i ≡ j (mod p). Denote by Alph(w) the set of the letters occurring in w. The succeeding example shows that some conditions on the letters of the external word are needed for external-global and external-local interactions.

Example 6 Consider a three letter alphabet A = {a, b, c} and let R = {(a, c), (b, c)} . Consider the infinite word w = (a q-1 b) ω for an integer q ≥ 2 and choose p such that gcd(p, q) = 1. Clearly any p is an external R-period of w, since c is related to both a and b. However, 1 is neither a global nor a local R-period of w.

Hence, the example implies the following.

By restricting considerations to the holding external periods it is possible to find a bound of interaction.

Theorem 10 Let p and q be positive integers with gcd(p, q) = 1. The bound of external-global interaction C g (p, q) for a holding external period p and a pure period q is pq. Similarly, the bound of external-local interaction C l (p, q) for a holding external period p and a pure period q is pq.

Proof: Suppose that w is of length pq and it has a pure period q and a holding external period p. Let y = y 1 • • • y p be an external word of w satisfying Eq. ( 4). Consider a letter w n in position n ∈ {1, 2, . . . , q}.

Since q is a period of w, the letter w n occurs in positions n + iq for i = 0, 1, . . . , p -1. These positions form a complete residue system (mod p), which means that w n is related to all letters in Alph(y) by the external period p. By Eq. ( 4), there may exist only one letter in Alph(w) such that it does not occur in y.

If this letter is w n , then it is trivially related to itself and therefore to all letters in Alph(w). On the other hand, if w n ∈ Alph(y), then there exists a position k such that y k = w n . Now y k is related to letters in positions k + jp for j = 0, 1, . . . , q -1, and these positions form a complete residue system (mod q). Hence, y k = w n is related to all letters of w. Since the above considerations hold for all n = 1, 2, . . . , q, all letters in Alph(w) are compatible with all other letters. Hence, 1 is a global and therefore also a local period of w. Modification of the previous example shows that the bound C g (p, q) = C l (p, q) = pq is strict. Assume that R is like in Example 6 and w = (a q-1 b) p-1 a q-1 .

We may choose y = c p-1 a. Namely, y p = a must only be related to letters in positions p + ip for i = 0, 1, . . . , q -2, which are all a's. Hence, w has an external word which satisfies Eq. ( 4), but 1 is neither a local nor a global R-period of w. ✷

For the external-external interaction additional conditions are not necessary.

Theorem 11 Let p and q be positive integers with gcd(p, q) = 1. The bound of external-external interaction for p and q is C(p, q) = 1 + (q -1)p.

Proof: Assume that y = y 1 • • • y p is an external word of w. Clearly, if |w| ≥ C(p, q), then y 1 is related to all letters in Alph(w). Namely, the set {1 + ip | i = 0, 1, . . . , q -1} is a complete residue system (mod q). In order to prove that this bound is strict, consider the rational power

w = (a 1 • • • a q ) (C(p,q)-1)/q
with q different letters a 1 , . . . , a q . Furthermore, let us assume that the alphabet A under consideration has p extra letters not occurring in w. Suppose that these letters are y 1 , . . . , y p . We define that y k , where k ∈ {1, 2, . . . , p}, is not related to the letter a [k+(q-1)p]q , but it is related to all letters w k+ip for i = 0, 1, . . . , q -2. Note that the length of w and the assumption that w has q different letters ensures that this is well defined. Hence, y = y 1 • • • y p is an external word of w. Furthermore, we may assume that two different letters in Alph(w) are not compatible with each other. Hence, no letter in the alphabet A is related to all letters in Alph(w). Therefore, the word w does not have 1 as an external R-period. ✷

Of course, we may as well restrict our considerations to holding external periods like in Theorem 10.

Theorem 12 Let p and q be positive integers with gcd(p, q) = 1. Then the bound of external-external interaction for a holding period p and a pure period q is C e (p, q) = (p -1)q + 1 if p is even and q > p, (q -1)p + 1 otherwise.

Theorem 12 is a direct consequence of the succeeding Lemmata 7 and 8.

Lemma 7

The bound C e (p, q) defined in Theorem 12 is sufficient.

Proof: First of all, Theorem 11 implies that the bound (q -1)p + 1 is sufficient for all external periods. Hence, let us consider the remaining case such that a word w of length |w| ≥ (p -1)q + 1 has a holding external R-period p and a pure period q, where p is even and q > p. Let y = y 1 • • • y p be an external word satisfying Eq. ( 4). Suppose also that gcd(p, q) = 1 is not an external R-period of w.

Since w has a pure period q, it is of the form (w

1 • • • w q ) p-1 w 1 . Denote v = v 1 • • • v pq = (w 1 • • • w q ) p . For 1 ≤ i ≤ p, set W i = {w j | j ≡ i (mod p)} and W = Alph(w). ( 5
)
We also denote

V i = {v j | j > (p -1)q + 1, j ≡ i (mod p)}. (6)
Note that W \ W i ⊆ V i , since |v| = pq. The notation a R Y means that the letter a is compatible with all letters in the set Y. For example, the ith letter y i of the external word y is, by the definition of an external word, compatible with all letters in W i , i.e., y i R W i . Note that if also y i R V i , then y i R W and y i is an external word of w, which contradicts the assumption that 1 is not an external period of w. Furthermore, for each a = v m ∈ V i , we have a = w [m]q+nq for n = 0, 1, . . . , p -2 and a ∈ W j for every j = i. We make two observations. Firstly, we conclude that

y i = y j for i = j. (7)
Otherwise, we have V i ⊆ W j and therefore y i = y j R V i . Hence, y i R W and we get a contradiction the same way as above.

Secondly, we note that

V i \ {y i } = ∅. (8)
Namely, if V i = {y i }, then y i R V i by the reflexivity of R and, consequently, y i R W. As above, this is a contradiction.

Next we show that w 1 = y k for some k = 1, 2, . . . , p. By the structure of w, we have

w 1 ∈ W i , i = 1, 2, . . . , p. (9)
If w 1 does not occur in y, then Eq. ( 4) implies that Alph(y) = W \ {w 1 }. Hence, by the definition of an external word, we have w 1 R Alph(y). Since R is reflexive, this means that w 1 R W. Again, we end up in a contradiction. It also follows that there exists exactly one letter a ∈ V k such that a does not occur in y. Namely, there cannot exist two such letters since this would contradict the holding property Eq. ( 4). Suppose next that all letters of V k occur in y. By Eq. ( 9), we have y k = w 1 R V k , which implies w 1 R W. This is a contradiction. Hence, we have a ∈ V k . Moreover, it holds that

a ∈ V i for i = k. (10)
Let us assume, on the contrary, that a ∈ V i for some i = k. Then a ∈ W j for all j = 1, 2, . . . , p, since a ∈ W j for every j = i and a ∈ W j for every j = k. Thus, a R W, since a R y j for all j and Alph(y) = W \ {a}. Again, this contradicts the fact that 1 is not an external R-period of w. Suppose next that there exists a letter b ∈ V k such that b = y i for some i = k. Consider a letter c = b belonging to V i . Note that by Eq. ( 8) such c exists and by Eq. ( 10) c = a. Hence, there must exist an index j such that y j = c. Since b ∈ V k , we have b ∈ W l for all l = k, especially for l = j. Therefore, y j = c R b. Since this holds for all letters of V i , we conclude that b R W. Again we end up in a contradiction and we may deduce that

V k = {a}. (11)
Consider now the letter y i = x = w 1 in some position i = k. By Eq. ( 8) and by Eq. (10), we have V i \ {x, a} = ∅. Moreover, there exists at least one letter z ∈ V i \ {x} such that if y j = z then x ∈ V j . Otherwise, x ∈ W j and y j = z R x. If x ∈ V j for any j such that y j = z ∈ V i \ {x}, then x R V i and, consequently, x R W, which again implies a contradiction. Suppose next that there exists another letter z ′ ∈ V i \ {x} in a position j ′ of y such that x ∈ V j ′ . This implies that x ∈ W l for all l = j ′ , especially for l = j. Hence, x R y j = z. Since this holds for all z ∈ V i \ {x}, we have x R V i , which is a contradiction. Therefore, the letter z must be unique. In other words, we have

V i \ {x} = {z}. (12)
By the equations Eq. ( 7), Eq. ( 11) and Eq. ( 12) we conclude that, for a letter y i where i = k, there exists a unique index j such that V i \ {y i } = {y j } and V j \ {y j } = {y i }. Hence, there must be a partition of integers {1, 2, . . . , p} \ {k} into pairs, i.e., subsets of cardinality two. Since p is even, this is impossible. Hence, gcd(p, q) = 1 must be an external period of w. ✷

Lemma 8

The bound C e (p, q) defined in Theorem 12 is strict.

Proof: We adopt the notation of Lemma 7. Recall especially definitions [START_REF] Blanchet-Sadri | Partial words and the critical factorization theorem[END_REF]. For each k, also denote

k ′ = [(q -1)p + k] q . ( 13
)
Let C e = C e (p, q). In the sequel, we consider four cases. In each case, we show that it is possible to define a relation R, a word w with period q and of length C e -1 and an external word y = y 1 • • • y p of w in such way that no letter in the alphabet A under consideration is related to all letters in Alph(w), and in addition, y satisfies y i R W i for 1 ≤ i ≤ p and |Alph(w) \ Alph(y)| ≤ 1. These properties imply that w has a holding external period p, but 1 cannot be an external period. Case 1. Assume that q < p and q is even. Then C e = (q -1)p + 1. Set A = {a 1 , . . . , a q } and

w = (a 1 • • • a q ) (Ce-1)/q . ( 14
)
Since q is even, we can make a partition P of the set {k ′ | k = 1, 2, . . . , q} = {1, 2, . . . , q} into pairs, i.e., subsets of cardinality two. If m and n belong to the same subset in P , we denote (m, n) ∈ P and let

(a m , a n ) ∈ R. (15)
Let these be the only R-incompatible pairs. Hence, each letter in A is R-incompatible with exactly one other letter in Alph(w). Taking benefit of the partition P , we set for every i, j ∈ {1, 2, . . . , q} satisfying (i ′ , j ′ ) ∈ P that

y i = a j ′ and y j = a i ′ . (16)
Then

y i = a j ′ R W i = A\{a i ′ } for i ∈ {1, 2, . . . , q}. Furthermore, set y i = y [i]q for i = q+1, q+2, . . . , p. Note that W i ⊆ W [i]q . Namely, if i = [i] q + tq ≤ p, then W i = {w j | j ≡ [i] q + tq (mod p)} ⊆ {w j-tq | j -tq ≡ [i] q (mod p)} = W [i]q ,
since q is a period of w. Hence, y i R W i for all i = 1, 2, . . . , p, and Alph(y) = Alph(w). Case 2. Assume that q < p and q is odd. We have C e = (q -1)p + 1. Let A = {a 1 , . . . , a q , b, c} and set w as in Eq. ( 14). Assume that r,s and t are three different integers in {1, 2, . . . , q}, where s = [(q -1)p + (q + 1)] q . Since q -3 is even, we can make a partition P of the set {1, 2, . . . , q} \ Proof: First of all, Theorem 11 implies that the bound (q -1)p + 1 is sufficient for all external periods. Hence, let us consider the remaining case such that a word w of length |w| ≥ (q -2)p + (q -1) has an inclusive external period p and a pure period q, where q is odd and q ≤ p + 1.

We use the notation of Lemmata 7 and 8. Recall especially that W i = {w j | j ≡ i (mod p)}, W = Alph(w) and k ′ = [(q -1)p + k] q . Hence, by the definition of an external word, y k R W k . Furthermore, set U = {1, 2, . . . , q -1}. Note that since q -1 ≤ p, the set W k is defined for all k ∈ U . Moreover, if k ∈ U , then |w|k ≥ (q -2)p. Since gcd(p, q) = 1 and q is a pure period of w, this implies that

w m ∈ W k = w k+ip i = 0, 1, . . . , |w| -k p ( 18
)
for any m ≡ k ′ (mod q). Since y k R W k , it follows that

y k R w m if m ≡ k ′ (mod q). (19)
Next we state three important properties, which will be needed throughout the proof: (i) If k ∈ U and

y k = w k ′ , then y k R W; (ii) If there exist k, l ∈ U (k = l) such that y k = y l , then y k R W; (iii) If there exist k, l ∈ U (k = l) such that y l = w k ′ and y k ∈ W \ {w l ′ }, then y k R W.
The first statement follows directly from Eq. ( 19), since the similarity relation R is reflexive. Next, consider the second property. By Eq. ( 19), we have y k R (W \ {w k ′ }) and y l R (W \ {w l ′ }). Now k ′ = l ′ , since k, l ∈ {1, 2, . . . , q -1}. Hence, y k R w l ′ and y l R w k ′ by Eq. ( 19). Since y k = y l , we have y k R W.

Finally, consider (iii). Again,

y k R (W \ {w k ′ }) and y l R (W \ {w l ′ }). Since y k ∈ W \ {w l ′ }, we have w k ′ = y l R y k , which implies that y k R W. Note that, if k, l ∈ U (k = l), y l = w k ′ and y k = w l ′ , then relations y k R W k and y l R W l do not imply w k ′ R w l ′ .
If any of the assumptions of (i)-(iii) is satisfied, then the word w necessarily has an external period 1. Namely, y = y k is an external word of w. Thus, from now on we assume that none of them is satisfied.

Assume first that, at least for one index k ∈ U , the letter in the position k ′ occurs also in another position 1 ≤ n ≤ q. Denote w k ′ = w n = a. Since W k must contain a letter which is in a position congruent to n, we have a ∈ W k and W k = W. Thus, y k R W and 1 is an external period of w.

Finally, assume that, for each k ∈ U , the letter w k ′ occurs only in positions congruent to k ′ (mod q). This means that all letters w k ′ (1 ≤ k ≤ q) are different. Moreover, this implies that Alph(y 1 • • • y q-1 ) = W\{w s ′ } for some 1 ≤ s ≤ q, since Alph(y 1 • • • y q-1 ) ⊆ W by Eq. ( 17) and all letters in Alph(y 1 • • • y q-1 ) are different by (ii). Suppose now that s = q. Since q ′ ∈ {k ′ | k ∈ U }, we have y k R w q ′ for 1 ≤ k ≤ q -1 by Eq. ( 19). Since Alph(y 1 • • • y q-1 ) = W \ {w q ′ }, it follows that w q ′ R (W \ {w q ′ }). By the reflexivity of R, we have w q ′ R W and y = w q ′ is an external word of w.

Moreover, the case s = q is impossible. This is based on the fact that q -1 is even. Indeed, assume that y r = w q ′ for some r ∈ U . Now consider n ∈ U \ {r}. Since Alph(y

1 • • • y q-1 ) ⊆ {w k ′ | 1 ≤ k ≤ q},
we have y n = w m ′ for some m ∈ {1, 2, . . . , q}. Since the letters {w k ′ | 1 ≤ k ≤ q} are distinct, the integer m is unique. In addition, m = n by (i) and m = q by (ii). Furthermore, y m = w n ′ by (iii) and therefore m = r, since w q ′ ∈ {w k ′ | k ∈ U }. Thus, m ∈ U \ {r, n}. Since the set U \ {r} has odd number q -2 elements, there cannot be such unique m for each n. This is a contradiction. Hence, we have shown that gcd(p, q) = 1 is an external period of w. ✷ Lemma 10 The bound C(p, q) defined in Theorem 13 is strict.

Proof: Let p and q be positive integers with gcd(p, q) = 1. Denote C = C(p, q) and adopt the notation of Lemma 7 and Lemma 8. In this proof, we want to define a relation R, a word w with period q and of length C -1 and an external word y = y 1 • • • y p of w in such way that no letter in the alphabet A under consideration is related to all letters in Alph(w), and in addition, y satisfies y i R W i for 1 ≤ i ≤ p and Alph(y) ⊆ Alph(w). Consider first the situation where q is odd and q < p. Hence, C = (q -2)p + (q -1). We set A = {a 1 , . . . , a q } and w = (a 1 • • • a q ) (C-1)/q . Case 1. Assume that q < p, q is odd and neither p + 1 nor p -1 is divisible by q. Denote a = a [(q-2)p+(q-1)]q , b = a [(q-2)p+q]q , c = a [(q-1)p+(q-1)]q , d = a [(q-1)p+q]q .

Note that by the above divisibility properties, all these four letters are different. Now {a i ′ | i = 1, 2, . . . , q -2} = A \ {c, d}. Hence, there exist numbers k, l ∈ {1, 2, . . . , q -2} such that a k ′ = a and a l ′ = b. We make a partition P of the set {i ′ | i ∈ {1, 2, . . . , q -2}, i = l} into pairs. This is possible since the set contains an even number q -3 of elements. We use Eq. ( 15) to define R-incompatible pairs of P and, in addition, we set (b, c) ∈ R and (b, d) ∈ R. Let these be the only incompatible pairs. Hence, except for b, all other letters are R-incompatible with exactly one other letter. Now consider an external word y = y 1 • • • y p . For indices i ∈ {1, 2, . . . , q -2} \ {l}, use Eq. ( 16) as before. In addition, set y l = c, y q-1 = y k and y q = d. Moreover, as in Case 1 of Lemma 8, set y i = y [i]q for i = q + 1, q + 2, . . . , p. Now

y l = c R W l = A \ {b}, y q-1 = y k R W q-1 = A \ {a, c}, y q = d R W q = A \ {b, d},
and y i R W i by Eq. ( 16) for all the other indices i ∈ {1, 2, . . . , q -2} \ {l}. Case 2. Assume that q < p, q is odd and p + 1 ≡ 0 (mod q). We use the same notation as in Case 1. Since p + 1 ≡ 0 (mod q), a = d. Clearly b ∈ {c, a}. Now {a i ′ | i = 1, 2, . . . , q -2} = A \ {c, a}. Thus, there does not exist k ∈ {1, 2, . . . , q -2} such that a k ′ = a, but we have l like in Case 1. Define the relation R and the external word y as in Case 1 except that now y q-1 = b. Hence, no letter is related to all other letters occurring in w and y is well defined. Namely,

y q-1 = b R W q-1 = A \ {a, c}.
Case 3. Assume that q < p, q is odd and p-1 ≡ 0 (mod q). Using the notation of Case 1, we conclude that b = c. Clearly a ∈ {b, d}. Now we have {a i ′ | i = 1, 2, . . . , q -2} = A \ {b, d}. Hence, using the notation of Case 1, there exists k but no l in {1, 2, . . . , q -2}. This time we make a partition P of the set {i ′ | i = {1, 2, . . . , q -2}, i = k} into subsets of cardinality two. Define R such that it satisfies Eq. ( 15) and furthermore that (a, b) ∈ R and (a, d) ∈ R. Assume again that these are the only R-incompatible pairs. In addition to Eq. ( 16) set y k = b, y q-1 = b and y q = a. Again no letter is compatible with all other letters and y is well defined, since

y k = b R W k = A \ {a}, y q-1 = b R W q-1 = A \ {a, c}, y q = a R W q = A \ {b, d}.
Case 4. Next assume that q > p + 1 and p is even. Hence, C = (q -1)p + 1. Set A and w as in the previous cases. Make a partition P of the set {i ′ | i = 1, 2, . . . , p} = {qp + 1, qp + 2, . . . , q} into pairs. Define R-incompatible pairs by Eq. ( 15) and use Eq. ( 16) to define the external word y. Since qp ≥ 2, we also set (a, a 1 ) ∈ R for each a ∈ {a 2 , . . . , a q-p }. Hence, no letter is R-compatible with all other letters of Alph(w). Moreover, y i R W i for all i.

In all other cases we may use the constructions in Cases 1, 3 and 4 of Lemma 8. Note that the external words in these cases satisfy the condition Alph(y) ⊆ Alph(w). Note also that if q is odd and q = p + 1, then C(p, q) = (q -2)p + (q -1) = (p -1)q + 1 = C e (p, q) and the construction in Case 4 is suitable for our purposes. Hence, we have shown that in all cases there exists a word w of length C -1 such that it has a pure period q and an external word y = y 1 • • • y p but 1 is not an external R-period of w. Moreover, the external word y satisfies Eq. ( 17) in every case. ✷

Local interactions

Despite the negative result in Example 5 there exist interaction bounds for some integers p and q also in the case where p is local. If no bound B(p, q) of interaction for p and q exists, i.e., there is an infinite word w such that gcd(p, q) is not a t 2 -type period of w, we set B(p, q) = ∞.

Theorem 14 Let p and q be positive integers with gcd(p, q) = 1. Then the bound of local-local interaction for p and q is D l (p, q) = p + q if p -1 ≡ 0 (mod q) or p + 1 ≡ 0 (mod q), ∞ otherwise.

Proof: Let w be a word of length D l = D l (p, q) with a pure period q and a local period p. Suppose that gcd(p, q) = 1. Assume first that p + 1 ≡ 0 (mod q). By the periodicity assumption, we then have

w i R w i+p = w i-1
for all i = 2, 3, . . . , q and furthermore w 1 R w 1+p = w q . Since q is a period of w, 1 is a local R-period of w. On the other hand, if we set R = {(a, c), (b, c)} , the word w = (c q-2 ab) (p+q-1)/q has a pure period q and a local R-period p. However, gcd(p, q) = 1 is not a local R-period of w, since (w q-1 , w q ) ∈ R. Note that in order to check that w has a local period p, it suffices to ensure that the distance from any occurrence of a to any occurrence of b is not p. By the length of w this holds. Namely, we have a = w q-1 R w q-1+p = w q-2 = c and if q = p + 1, then also b = w q R w q-p = w 1 = c.

Assume next that p -1 ≡ 0 (mod q). Now w i R w i+p = w i+1 for all i = 1, 2, . . . , q. As above, this means that w has a local R-period 1. Our bound is strict, since setting again R = {(a, c), (b, c)} , the word w = (ac q-2 b) (p+q-1)/q has a pure period q and a relational R-period p. However, (w q , w q+1 ) ∈ R and 1 is not a local R-period.

Again the length of w ensures that a and b do not have to be related. We only check that a = w 1 R w 1+p = w 2 = c, which is satisfied. Finally, assume that q does not divide p -1 nor p + 1. Then i + p ≡ i + 1 (mod q) and i + p ≡ i -1 (mod q). Thus, if R = {(a, c), (b, c)} , then the infinite word w = (abc q-2 ) ω has a pure period q and a local R-period p, but clearly 1 is not a local R-period of w. ✷

Local periods are also weak when considering other interactions.

Theorem 15 Let p and q be positive integers with gcd(p, q) = 1. The bounds D e (p, q) of local-external interaction and D g (p, q) of local-global interaction do not exist, except for q = 3, in which case D e (p, q) = p + 2 and D g (p, q) = p + 3.

Proof: As usual, denote D e (p, q) = D e and D g (p, q) = D g . Consider first the case where q = 3. Assume that a word w has a pure period 3 and a local R-period p. Recall that [n] q is the least positive residue of an integer n (mod q). If |w| ≥ p + 2, then (d,a) . Define an infinite word w = (w 1 • • • w q ) ω in the following way. Set w 1 = a, w [1+p]q = b, w [1+2p]q = c and w [1+ip]q = d for i = 3, 4, . . . , q -1. Now, by the definition of R, w i R w i+p for all i = 1, 2, . . . , q. Hence, p is a local R-period of w. However, 1 is neither an external nor a global R-period, since no letter is compatible with all the other letters. Hence, D e = D g = ∞. ✷

Summary of bounds

In order to get a clearer picture of all the different variants of Fine and Wilf's theorem represented in the previous sections, we summarize the bounds in Table 2.

By Theorem 1, a global period is a stronger attribute than the other periods, and therefore B g (p, q) ≥ B e (p, q) and B g (p, q) ≥ B l (p, q), for every p and q. Observe also that B-bounds (B g , B e and B l ) are in many cases smaller than the other bounds.

On the other hand, if we compare the bounds of global-external and global-local interaction we see, for example, that This indicates the incomparability of external relational period and local relational period, which was already seen in Examples 3 and 4 with respect to minimal periods. However, in some sense the local period seems to be the weakest. In the case where p is an external period, we get interaction bounds, at least, if we assume extra conditions. In the case of a local period p, bounds usually do not exist. As a final example, we give a complete table (Table 3) of interaction bounds for p = 6 and q = 7.

❳ ❳ ❳ ❳ ❳ ❳ ❳ ❳ ❳ ❳

Example 1

 1 On the binary alphabet {a, b} the only compatibility relation different from the identity relation is the universal relation of all words of equal length. Namely, the relation R = {(a, b)} = {(a, a), (b, b), (a, b), (b, a)} makes all words with equal length similar with each other. On the other hand, over the ternary alphabet {a, b, c}, where S = {(a, b)} = {(a, a), (b, b), (a, b), (b, a), (c, c)},

Theorem 9 Definition 3

 93 No finite bounds exist for external-global and external-local interactions. Because of this, in the formulation of the next theorem we consider only external periods satisfying a special condition. An external period p of a word w is called holding if there exists an external word y = y 1 • • • y p of w satisfying |Alph(w) \ Alph(y)| ≤ 1.

w 1

 1 R w [1+p]3 and w 2 R w [2+p]3 . (20)Since gcd(p, q) = 1, the letter w [1+p]3 is equal to w 2 or w 3 and w [2+p]3 is equal to w 3 or w 1 , respectively. This implies that in the first case y = w 2 is an external word of w, whereas in the second case we may choose y = w 1 . If |w| ≥ p + 3, then in addition to Eq. (20), we have w 3 R w [3+p]3 where w [3+p]3 is equal to either w 1 or w 2 . Hence, we must have w i R Alph(w) for i = 1, 2, 3 and therefore 1 is a global R-period of w. On the other hand, u = (abc) ⌊(p+1)/3⌋ with R = {(a, w [1+p]3 )} and v = (abc) ⌊(p+2)/3⌋ with S = {(a, w [1+p]3 ), (b, w [2+p]3 )} show that the bounds D e and D g are strict for q = 3.Otherwise, let q ≥ 4. Consider a four letter alphabet {a, b, c, d} and set R = (a, b), (b, c), (c, d),

B e ( 5 , 9 )

 59 = 23 > 19 = B l (5, 9), B e (4, 7) = 15 = 15 = B l (4, 7), B e (3, 5) = 8 < 10 = B l (3, 5).

Acknowledgements

We thank the referee of this journal for useful suggestions.

{r, s, t} into pairs. Define R-incompatible pairs by Eq. (15) for indices {1, 2, . . . , q} \ {r, s, t}. Let also (a r , a s ), (a r , b), (a s , a t ), (a t , c) ∈ R. Hence, no letter in A is compatible with all letters of Alph(w).

Use Eq. ( 16) to determine the letters y i , where i = 1, 2, . . . , q and i ′ ∈ {1, 2, . . . , q} \ {r, s, t}. Furthermore, for i = 1, 2, . . . , q, set

Set also y q+1 = a t so that a s is the only letter in Alph(w) not occurring in the external word y. Hence, |Alph(w) \ Alph(y)| ≤ 1. For i = q + 2, q + 3, . . . , p, set y i = y [i]q like in Case 1. We may assume that there are no more incompatible pairs than those mentioned above. Therefore, y i R W i for all i, since

, where W q+1 = Alph(w) \ {a s }. Case 3. Assume that q > p and p is odd. Then C e = (q -1)p + 1. Let the alphabet be A = {a, a q-p+1 , a q-p+2 , . . . , a q } and set w = (a q-p a q-p+1 a q-p+2 • • • a q ) (Ce-1)/q . Since p is odd, we can partition the set {q-p+1, q-p+2, . . . , q-1} and make (p-1)/2 incompatible pairs using Eq. (15). Additionally, set (a q , a) ∈ R. Assume moreover that these are the only R-incompatible pairs. Again, each letter is incompatible with exactly one other letter. Since i ′ = qp + i for all i = 1, 2, . . . , p, we may define y 1 • • • y p-1 using Eq. ( 16). Furthermore, set y p = a. Now

Case 4. Assume that q > p and p is even. We have C e = (p -1)q + 1. Consider a word (w 1 • • • w q ) p-1 where w i = w j if 1 ≤ i, j ≤ q and i ≡ j (mod p). Assume also that A = Alph(w). We make a partition P of the set {qp + 1, qp + 2, . . . , q} into pairs. Note that the set has an even number of elements. Define R-incompatible pairs by Eq. ( 15) and let these be the only R-incompatible pairs. Since {w q-p+1 , w q-p+2 , . . . , w q } = Alph(w) = A, no letter is compatible with Alph(w). As above, i ′ = qp + i for all i = 1, 2, . . . , p and we may define y 1 • • • y p using Eq. ( 16). Now we have y i R W i for all i. Moreover, we have Alph(y) = Alph(w). ✷

On the other hand, it might be more interesting to consider the case where the external word of w consists only of letters occurring in w.

Definition 4 An external period p of a word w is called inclusive if there exists an external word y =

Using this definition we have one more result concerning the external-external interaction.

Theorem 13 Let p and q be positive integers with gcd(p, q) = 1. Then the bound of external-external interaction for an inclusive external period p and a pure period q is C(p, q) = (q -2)p + (q -1) if q is odd and q ≤ p + 1, (q -1)p + 1 otherwise.

Lemma 9 and Lemma 10 imply Theorem 13.

Lemma 9

The bound C(p, q) defined in Theorem 13 is sufficient.

p + 1 2 q if (p < q and p is odd) or (p > q and q is even),

global-local B l = q + kp -1 if 1 ≡ q -1 (mod p) and kp ≡ +1 (mod q), q + kp otherwise.

holding external-global C g = pq holding external-external C e = (p -1)q + 1 if p is even and q > p, (q -1)p + 1 otherwise.

holding external-local C l = pq external-global ∞ inclusive external-external C = (q -2)p + (q -1) if q is odd and q ≤ p + 1 (q -1)p + 1 otherwise.

external-external C = 1 + (q -1)p external-local ∞ local-global D g = p + 3 if q = 3 ∞ otherwise local-external D e = p + 2 if q = 3 ∞ otherwise local-local D l = p + q if p -1 ≡ 0 (mod q) or p + 1 ≡ 0 (mod q), ∞ otherwise.

Tab. 2: Interaction bounds for p and q, where gcd(p, q) = 1, h = 1 + ⌊q/2⌋p and k is the smallest integer such that kp ≡ ±1 (mod q).