Equations Enforcing Repetitions Under Permutations

Abstract

The notion of repetition of factors in words is central to combinatorics on words. A recent generalisation of this concept considers repetitions under permutations: give an alphabet $\Sigma$ and a morphism or antimorphism f on $\Sigma ^*$, whose restriction to $\Sigma$ is a permutation, w is an [f]-repetition if there exists $\gamma \in \Sigma ^*$ such that $w=f^{i_1}(\gamma )f^{i_2}(\gamma )\cdots f^{i_k}(\gamma )$, for some $k\ge 2$. In this paper, we extend a series of classical repetition enforcing word equations to this general setting to obtain a series of word equations whose solutions are [f]-repetitions.

D. Nowotka—Research supported by DFG grant NO 872/3-2 (jda, dn), DFG grant MA 5725/1-2 (flm), BMBF HPSV grant 01IH15006A (fpa).

1 Introduction

The study of repetitive sequences in words is one of the central topics of combinatorics on words, with applications in e.g., pattern matching and stringology in general, data compression, bioinformatics (see [10, 13]). Part of the investigations on this topic deal with repetition enforcing relations or equations. Basically, a repetition enforcing relation for words is a relation, or a statement, that holds only for words that can be expressed as repetitions (i.e., repeated concatenation) of some (other) word. For instance, it is well known (see, e.g., [12]) that a word w is a factor, other than prefix of suffix, of the word ww if and only if $w\in \{t\}^+$ for some shorter word t, i.e., w is a repetition. Another prominent example of a repetition enforcing statement is the Theorem of Fine and Wilf [6] (FWT): if $\alpha =u^\ell$ and $\beta =v^k$ and $\alpha$ and $\beta$ share a common prefix of length at least $|u|+|v|-\gcd (|u|,|v|)$, then both u and v are repetitions of some word t, i.e., $u,v\in \{t\}^+$. The equation of Lyndon and Schützenberger [14] (LSE) is an example of a repetition enforcing equation: if $u^\ell = v^mw^n$ holds, for some words u, v, w and $\ell ,m,n\ge 2$, then there exists a word t such that $u,v,w\in \{t\}^+$, so u, v, w are repetitions of the same root.

Pseudo-repetitions were introduced [4, 5], as a generalisation of classical repetitions, inspired by molecular biology. A word w is a pseudo-repetition (more precisely, f-repetition) if it equals a repeated concatenation of one of its prefixes t and its image f(t) under some morphism or antimorphism (for short “anti-/morphism”) f, thus $w\in t\{t,f(t)\}^+$. To fit the biological motivation, in [5] f was defined as an antimorphic involution (i.e., $f^2(w)=w$ for all words w). More interesting to us, if f is not restricted, pseudo-repetitions generalise not only repetitions (when f is the identity morphism), but also palindromes (when f is the mirror image); both these concepts are central in combinatorics on words, so their generalisations are of intrinsic theoretical interest. Initial results (see [3, 5]) concerned generalisations of the FWT, of the LSE, and of other repetition enforcing results to the setting of f-repetitions for antimorphic involutions f. For instance, Czeizler et al. [3] introduced a different generalisation of LSE. They considered equations of the form $u_1u_2\cdots u_\ell = v_1v_2\cdots v_m w_1w_2\cdots w_n,$ where $u_i \in \left\{ u, \theta (u)\right\}$ for all $1 \le i \le \ell$, $v_j \in \left\{ v, \theta (v)\right\}$ for all $1 \le j \le m$, and $w_k \in \left\{ w, \theta (w)\right\}$ for all $1 \le k \le n$, and studied under which conditions $u,v,w \in \left\{ t,\theta (t)\right\} ^+$ yield for some word t. That is, they studied the case when u, v, w are generalised repetitions (more precisely, $\theta$-repetitions). A complete characterisation of the conditions under which the aforementioned equation has only $\theta$-repetitive solutions was obtained in [17].

Going a step further, the case of f-repetitions (over an alphabet $\Sigma$) for an anti-/morphism f that acts as a permutation on $\Sigma$ (anti-/morphic permutation) was considered in [15], where a series of results in the style of the FWT were given. Introduced in [15], but only briefly studied in that paper, was also a more general notion of repetition, that we will call here an [f]-repetition. If f is an anti-/morphic permutation and $w=f^{i_1}(\gamma )f^{i_2}(\gamma )\cdots f^{i_k}(\gamma )$, for some $k\ge 2$, then w is called [f]-repetition of root $\gamma$. A variant of the FWT was shown for [f]-repetitions in the case when f is a morphism. This notion also appears in a series of papers regarding avoidability of patterns under anti-/morphic permutations: in [16] the avoidability of patterns of the form $\pi ^i(x)\pi ^j(x)\pi ^k(x)$, i.e., $[\pi ]$-cubes, for $\pi$ a variable that can be replaced by anti-/morphic permutations, was studied, while in [2] the avoidability of general $[\pi ]$-repetitions was considered. Finally, algorithmic problems like deciding whether a word is an [f]-repetition [7, 8] or whether a word contains [f]-repetitions [1, 9, 18] for different types of functions (including anti-/morphic permutations) were investigated. However, we are not aware of any algorithmic results regarding [f]-repetitions.

In this paper we analyse a series of [f]-repetition enforcing word equations, for an anti-/morphic permutation f. We first analyse the morphic case, and we show that a series of classical repetition enforcing equations are extendible to this more general setting. For instance we show that both $f^a(x)f^b(y)=f^c(y)f^d(x)$ and $f^a(u)f^b(u)=xf^c(u)y$ with $x,y\ne \varepsilon$ enforce x, y resp. u to be an [f]-repetition each with one root.

Our main result is an extension of the LSE: if $f^{i_1}(u)\dots f^{i_r}(u)f^{j_1}(v)\dots f^{j_s}(v)=f^{k_1}(w)\dots f^{k_t}(w)$ for some $r,s,t\ge 2$, then u, v, w are [f]-repetitions of the same root t. These results complement the generalised FWT obtained in this setting in [15]. In the case when f is antimorphic, we show that the equation $f^a(u)f^b(u)=xf^c(u)y$ may have solutions which are not [f]-repetitions. Thus, following the results of [3, 5], we characterise exactly the equations $f^{a_1}(u)f^{a_2}(u)f^{a_3}(u)=xf^{b_1}(u)f^{b_2}(u)y$, with $x,y\ne \varepsilon$, whose solutions are [f]-repetitions. We use this characterisation to show a result in the style of the FWT and to define a class of extensions of the LSE that only have solutions which are [f]-repetitions.

The paper is organised as follows: we first give the basic definitions and recall some preliminary results, then we present the results for the case when f is a morphic permutation, and finally we present the results for when f is an antimorphic permutation. Due to space restrictions some proofs are omitted.

2 Preliminaries

Let $\mathbb {N}$ be the set of natural numbers, $\mathbb {N}_0=\mathbb {N}\cup \{0\}$ and $\mathbb {N}_{\ge k}=\{x\in \mathbb {N}_0\mid x\ge k\}$. For $n\in \mathbb {N}$, [n] denotes $\{1,\ldots , n\}$ and $[n]_0=[n]\cup \{0\}$. For the set of integers $\mathbb {Z}$, $a\equiv _k b$ holds if and only if $a,b\in \mathbb {Z}$ have the same remainder modulo $k\in \mathbb {N}$ and $\mathbb {Z}_k$ denotes the quotient ring of integers modulo k. For $m,n\in \mathbb {N}$, let $\gcd (m,n)$ denote their greatest common divisor.

Let $\Sigma$ be a finite alphabet. In this paper $\Sigma ^*$ denotes the set of all words over $\Sigma$, $\varepsilon$ the empty word, $\Sigma ^+:=\Sigma ^*\backslash \{\varepsilon \}$, and for the word’s length |w|, $\Sigma ^{\le k}:=\{w\in \Sigma ^{*}|\,|w|\le k\}$. For two words u and v, set $d_{u,v}:=\gcd (|u|,|v|)$.

For some words x, y, u is a factor of w, if $w=xuy$; u is a prefix of w if $x=\varepsilon$ and a suffix if $y=\varepsilon$. A word u is said to occur strictly inside another word w if u is a factor of w, other than a prefix or a suffix. Moreover, $w=u^{-1}v$, whenever $v=uw$. The powers of w are defined recursively by $w^0=\varepsilon$, $w^n=ww^{n-1}$ for $n \ge 1$. If w cannot be expressed as a power of another word, then w is said to be primitive.

We say that $f:\Sigma ^*\rightarrow \Sigma ^*$ is a morphism (resp., antimorphism) if $f(xy)=f(x)f(y)$ (resp., $f(xy)=f(y)f(x)$) for any words $x,y\in \Sigma ^*$. Note that, to define an anti-/morphism it is enough to define f(a) for all $a\in \Sigma$. If f is a bijective morphism (resp., antimorphism), then we call f a morphic (resp., antimoprhic) permutation. If f is a permutation of $\Sigma$ then $\mathrm {ord}(f)$ denotes the smallest positive number such that $f^{\mathrm {ord}(f)}(a)=a$ for all $a\in \Sigma$. If f is a morphic permutation then $f^{\mathrm {ord}(f)}(w)=w$ and if f is an antimorphic permutation then $f^{2\mathrm {ord}(f)}(w)=w$, for all $w\in \Sigma ^*$. This leads to the fact that the exponents of an anti-/morphic permutation f can be considered to be elements of $\mathbb {Z}_{\mathrm {ord}(f)-1}$ resp. $\mathbb {Z}_{2\mathrm {ord}(f)-1}$, i.e. $f^{a-b}$ is for all $a,b\in \mathbb {Z}$ a well-defined iteration of f.

For an anti-/morphic permutation f, a word $w\in \Sigma ^{*}$ is said to be an [f]-repetition if there exists $t\in \Sigma ^+$, $k\ge 2$, and $i_1,\ldots ,i_k \in \mathbb {Z}$ such that $w=f^{i_1}(t)f^{i_2}(t)\cdots f^{i_k}(t)$. In this case, t is called the root of the [f]-repetition w. If w is not an [f]-repetition, then w is [f]-primitive. For instance, the word $w=abcaab$ is $[\mathrm{Id_\Sigma }]$-primitive, where $\mathrm{Id_\Sigma }$ is the identical morphism on $\Sigma$, and [f]-primitive for some morphism or antimorphism f with $f(a)=b$, $f(b)=a$ and $f(c)=c$. However, for the morphism $f(a)=c$, $f(b)=a$ and $f(c)=b$, $w=abf(ab)ab=abcaab$, thus, w is an [f]-power in this setting; $abbcab=abf^2(ab)ab$ is also an [f]-repetition as well.

In the following, several classical repetition enforcing results are recalled. The first one is folklore (see, e.g., [12]). The next three are classical results of Fine and Wilf and Lyndon and Schützenberger, respectively.

Theorem 1

(1-in-2). A word $w\in \Sigma ^*$ is a repetition iff w occurs strictly inside ww.

Theorem 2

(Fine and Wilf [6]). Let $u,v\in \Sigma ^*$. If two words $\alpha \in u\{u,v\}^*$ and $\beta \in v\{u,v\}^*$ have a common prefix of length at least $|u|+|v|-d_{u,v}$, then u and v are powers of a common word of length $d_{u,v}$. The bound $|u|+|v|-d_{u,v}$ is optimal.

Theorem 3

(Lyndon and Schützenberger [14]). Let $u,v,w \in \Sigma ^*$. Then $uv = vw$ if and only if there exist words $p,q \in \Sigma ^*$, such that $u = (pq)^i, w = (qp)^i$, and $v = (pq)^jp$ for some $i, j\ge 0$ and pq is primitive.

Theorem 4

(Lyndon and Schützenberger [14]). If $u^\ell = v^m w^n$ for some words $u,v,w \in \Sigma ^*$ and $\ell , m, n \ge 2$, then $u,v,w \in \left\{ t\right\} ^*$ for some word $t \in \Sigma ^*$.

Theorem 2 was extended in [15] for [f]-repetitions.

Theorem 5

Let $u,v\in \Sigma ^*$ and $f:\Sigma ^*\rightarrow \Sigma ^*$ be a morphic permutation with $ord(f)=k+1$. Let $S(u,v)=\{u,f(u),\ldots , f^k(u), v,f(v), \ldots , f^k(v)\}^*$. If two words $\alpha \in uS(u,v)$ and $\beta \in vS(u,v)$ have a common prefix of length at least $|u|+|v|-d_{u,v}$, then there exists a $t\in V^*$, such that $u,v\in t\{t,f(t),\ldots ,f^k(t)\}^*$.

Theorem 3 was extended in the setting of anti-/morphic involutions in [5]. Theorem 4 was extended for [f]-repetitions where f is an antimorphic involution in a series of papers that culminated in [17], where a full characterisation of the triples $(\ell ,m,n)$ for which $u_1u_2\cdots u_\ell = v_1v_2\cdots v_m w_1w_2\cdots w_n,$, where $u_i \in \left\{ u, f(u)\right\}$ for all $1 \le i \le \ell$, $v_j \in \left\{ v, f(v)\right\}$ for all $1 \le j \le m$, and $w_k \in \left\{ w, f(w)\right\}$ for all $1 \le k \le n$, has only solutions which are [f]-repetitions was given.

3 The Morphic Case

In this section some well known equations which only have repetitions as solutions are generalised to equations whose solutions are repetitions under morphic permutations. These results are used to ultimately show that a version of Theorem 4 holds for [f]-repetitions in the case that f is a morphic permutation.

Some basic lemmas are first established, which provide some fundamental combinatorial tools for proving the later results. They focus on two very well-known equations, namely $xy=xy$ and $xy=yz$ with $x,y,z\in \Sigma ^+$, and describe their solutions in this more general setting.

Lemma 6

Let $x,y\in \Sigma ^+$, f a morphic permutation on $\Sigma ^{*}$, and $a,b,c,d\in [\mathrm {ord}(f)]_0$ with $f^a(x)f^b(y)=f^c(y)f^d(x)$. Then there exists a $t\in \Sigma ^+$ such that x, y are [f, t]-repetitions.

Proof

Theorem 5 can be applied for $\alpha =f^a(x)f^b(y)$, $\beta =f^c(y)f^d(x)$, $u=f^a(x)$, and $v=f^c(y)$. Clearly, $\alpha$ and $\beta$ have a common prefix of length $|\alpha |=|\beta |=|u|+|v|$, it follows that there exists t such that $f^a(x),f^c(y)\in t\{t,f(t),\ldots ,f^{\mathrm {ord}(f)-1}(t)\}^*$. Consequently, x, y are [f, t]-repetitions.    $\square$

While Lemma 6 provides a direct analogy to the standard setting, for which the “repetition-enforcing” nature of the equation is folklore, it is also possible to provide the following more specific insight which is essential to the proofs.

Lemma 7

Let $x,y\in \Sigma ^+$ with $x=x_1x_2$ such that $|x_1|=|x_2|$, f a morphic permutation on $\Sigma ^{*}$, and $a,b,c\in [\mathrm {ord}(f)]_0$ with

$$\begin{aligned} yx_1x_2=f^a(x_1)f^b(x_2)f^c(y) \end{aligned}$$

Then there exists a $t\in \Sigma ^+$ such that $x,y,f^a(x_1)f^b(x_2)$ are [f, t]-repetitions.

Lemma 8

Let $x,y\in \Sigma ^+$, f a morphic permutation on $\Sigma ^{*}$ and $a,b,c,d\in [\mathrm {ord}(f)]_0$. The equation

$$\begin{aligned} f^a(x)f^b(y)=f^c(y)f^d(z) \end{aligned}$$

holds if and only if there exist $u,v\in \Sigma ^{*}$, $i,s,r,q\in \mathbb {N}_0$ with

$$\begin{aligned} x=uv,\quad z=f^{q}(v)f^{q+r}(u),\quad and \quad y=f^{s+r}(uv)\dots f^{s+ir}(uv)f^{s+(i+1)r}(u). \end{aligned}$$

If Theorem 3 holds for three words x, y, z (i.e., $xy=yz$) then the words x and z are conjugate, $x\sim z$ for short. It is well known that the conjugacy relation is an equivalence relation. When working in the setting of equations under morphic permutations, this relation can be extended to f-conjugacy. For a morphic permutation f, the words $x,y\in \Sigma ^*$ are said to be f-conjugate (written $x\sim _f y$) if there exist $a,b,c,d \in [\mathrm {ord}(f)]_0$ such that $f^a(x)f^b(y)=f^c(y)f^d(z)$ – so if they satisfy the equation addressed in Lemma 8. It can be seen that $x\sim _f y$ follows from $x\sim y$. More interestingly however, while $\sim _f$ is symmetrical and reflexive, it is not transitive (unless f is the identical morphism). Accordingly, $\sim _f$ is an equivalence if and only if f is the identity morphism.

The following lemma extends another fundamental result mentioned in Theorem 1, and may be proved by reducing to the case considered by Lemma 6 (see Fig. 1).

Fig. 1.

x, y reoccur each twice within $f^c(y)$, such that - except for permutation application - the pattern $xy=yx$ occurs (shown by the dotted and dashed lines), so Lemma 6 may be applied.

Lemma 9

Let $f:\Sigma ^{*}\rightarrow \Sigma ^{*}$ be a morphic permutation and $a,b,c\in [\mathrm {ord}(f)]_0$. If $u\in \Sigma ^{*}$ is [f]-primitive, then for $x,y\in \Sigma ^{*}$ with

$$\begin{aligned} f^a(u)f^b(u)=xf^c(u)y \end{aligned}$$

either $x=\varepsilon$ or $y=\varepsilon$ follows.

Lemma 7 can be extended in a similar fashion.

Lemma 10

Let $f:\Sigma ^{*}\rightarrow \Sigma ^{*}$ be a morphic permutation and $a,b,c,d\in [\mathrm {ord}(f)]_0$. If $u\in \Sigma ^{*}$ is [f]-primitive and $u=u_1u_2$, with $|u_1|=|u_2|$, then for $x,y\in \Sigma ^{*}$ with

$$\begin{aligned} f^a(u)f^b(u)=xf^c(u_1)f^{d}(u_2)y \end{aligned}$$

either $x=\varepsilon$ or $y=\varepsilon$ follows.

In the rest of this section it will be shown that Lyndon and Schützenberger’s result can be reproven without any additional restrictions in the setting of repetitions under morphic permutations. In this setting, the LSE is defined for words $u,v,w\in \Sigma ^+$ by

$$\begin{aligned} f^{a_1}(u)\dots f^{a_r}(u)f^{c_1}(v)\dots f^{c_s}(v)=f^{b_1}(w)\dots f^{b_t}(w), \end{aligned}$$

(1)

for $r,s,t\in \mathbb {N}_{\ge 2}$, $a_i,b_k,c_j\in [\mathrm {ord}(f)]_0$, $i\in [r]$, $k\in [s]$, $j\in [t]$, and a morphic permutation f on $\Sigma ^{*}$. For simplicity, the following notations are sometimes used: $\alpha _1=f^{a_1}(u)\dots f^{a_r}(u), \alpha _2=f^{c_1}(v)\dots f^{c_s}(v)$, and $\beta =f^{b_1}(w)\dots f^{b_t}(w)$. The intention is to show that there exists a word t such that $u,v,w\in \{t,f(t),\ldots ,f^{\mathrm {ord}(f)-1}(t)\}^*$, and thus that the equation, when augmented by the presence of morphic permutations, remains a repetition enforcing relation.

In order to show that indeed u, v, and w are [f]-repetitions with the same root under these conditions, the proof is divided into various cases. To begin with, the cases in which the us and vs “fit” exactly inside the ws and vice-versa are given.

Lemma 11

If Eq. 1 holds for $r,s,t\ge 2$, and $|u|\mid |w|$ or $|v|\mid |w|$ holds, then u, v, w are [f]-repetitions.

Lemma 12

If Eq. 1 holds for $r,s,t\ge 2$, and $|w|\mid |u|$ or $|w|\mid |v|$ holds, then u, v, w are [f]-repetitions.

The following lemma demonstrates how, in some cases, the extension of the FWT (Theorem 5), may be applied. This is straightforward if the theorem may be applied from both endpoints, in opposite directions, showing first that u and w share an f-root and then that v and w share an f-root. In fact, as the lemma states, it is sufficient to be able to apply the theorem in just one direction – although this requires more effort to prove.

Lemma 13

In Eq. 1, if $\alpha _1$ and $\beta$ have a common prefix of length at least $|w|+|u|-d_{u,w}$ or $\alpha _2$ and $\beta$ have common suffix of length at least $|w|+|v|-d_{v,w}$, then u, v, and w are [f]-repetitions.

Fig. 2.

If the parts of permutations of u and the one permutation of v are each long enough, Theorem 5 can be applied from either side.

Following from Lemma 13 (see also Fig. 2), it is now possible to show that the equation is repetition enforcing provided r, s and t are large enough.

Theorem 14

If Eq. 1 holds with r, s, t at least 3 or with $t\ge 4$ and r, s at least 2, then one of the conditions of Lemma 13 also holds. Hence, there exists a word t such that $u,v,w\in \{t,f(t),\ldots ,f^{\mathrm {ord}(f)-1}(t)\}^*$.

Recalling the original LSE (Theorem 4), the claim is nearly proven for the permutation setting as well. It remains to prove the cases for r, s, t being 2, respectively. In order to accomplish this, the following auxiliary result is needed.

Lemma 15

Let $w_1,w_2,$ be in $\Sigma ^+$, f a permutation, and $a,b,c,d\in \mathbb {N}$. If $w_1f^a(w_2)=f^b(x)f^c(w_2)f^d(x)$ holds, then there exists a suffix $x'$ of a permutation of x and there exists $n_1,\dots , n_r\in \mathbb {N}$ for $r\in \mathbb {N}$ with

$$\begin{aligned} w_2=x'f^{n_1}(x)\dots f^{n_r}(x). \end{aligned}$$

Remark 16

For $f^a(w_1)w_2=f^b(x)f^c(w_1)f^d(x)$ an analogous result can be obtained.

The case that $r=s=t=2$ is one of the most straightforward remaining cases, and is addressed first.

Lemma 17

If Eq. 1 holds for $r=s=t=2$, then u, v, and w are [f]-repetitions.

Fig. 3.

In the case of $r=s=t=2$ the pattern $u_1u_2=u_2u_1$ - neglecting the permutations - occurs in the second w.

Proof

Consider w.l.o.g. $2|u|>|w|$. Choose $u_1,u_2\in \Sigma ^+$ with $f^{a_2}(u)=u_1u_2$ such that $u_1\in \mathrm {Suff}(f^{b_1}(w))$ and $u_2\in \mathrm {Pref}(f^{b_2}(w))$. This implies $f^{b_1}(w)=f^{a_1-a_2}(u_1)f^{a_1-a_2}(u_2)$ $u_1$ and

$$\begin{aligned} f^{b_2-b_1+a_1-a_2}(u_1)f^{b_2-b_1+a_1-a_2}(u_2)f^{b_2-b_1}(u_1) =f^{b_2}(w) =u_2f^{c_1}(v)f^{c_2}(v). \end{aligned}$$

By this $2|u_1|=2|v|$ follows. Moreover, since $f^{b_2-b_1}(u_1)$ and $f^{c_2}(v)$ are suffixes of $f^{b_2}(w)$, $f^{b_2-b_1}(u_1)=f^{c_2}(v)$ holds. Substituting this result in $f^{b_2}(w)$ leads to

$$\begin{aligned} f^{b_2-b_1+a_1-a_2}(u_1)f^{b_2-b_1+a_1-a_2}(u_2) = u_2f^{c_1-c_2+b_2-b_1}(u_1) \end{aligned}$$

By Lemma 6 follows the existence of a $\gamma \in \Sigma ^{*}$ such that $u_1,u_2$ are $[f,\gamma ]$-repetitions and consequently u, v, and w are [f]-repetitions as well (Fig. 3).

Lemma 18

If Eq. 1 holds for $t=3$ and $r=s=2$ then u, v, and w are [f]-repetitions. Similarly, f Eq. 1 holds for $r=2$ and $s=t=3$, then u, v, and w are [f]-repetitions.

Lemma 19

If Eq. 1 holds for $s=t=2$ and $r\ge 3$ then u, v, and w are [f]-repetitions.

Lemma 20

If Eq. 1 holds for $t=2$ and $r,s\ge 3$ then u, v, and w are [f]-repetitions.

From the preceding lemmas, we can conclude with the following main result.

Theorem 21

If Eq. 1 holds for $t,r,s\ge 2$ then u, v, and w are [f]-repetitions.

4 The Antimorphic Case

Firstly, note that the results of Lemma 9 do not hold in the case of antimorphic permutations.

Remark 22

Consider the equation $f^{a}(w)f^{b}(w)=xf^{c}(w)y$, where f is an antimorphism. The following counterexamples show that this equation is not repetition enforcing, no matter the values of a, b, c; in all cases, $\Sigma =\{\mathtt {a},\mathtt {b}\}$ and f is the mirror image on $\Sigma ^{*}$. Let $w=\mathtt {a}\mathtt {a}\mathtt {b}\mathtt {a}$, which is not a [f]-repetition. However, for a even and b, c odd, $f^{a}(w)f^b(w)=\mathtt {a}\mathtt {a}\mathtt {b}\mathtt {a}\mathtt {a}\mathtt {b}\mathtt {a}\mathtt {a}= \mathtt {a}\mathtt {a}\mathtt {b}f^c(w) \mathtt {a}$ holds. By Lemma 25, it follows immediately that the equation $f^{a}(w)f^{b}(w)=xf^{c}(w)y$ when a is odd and b, c even, a, c odd and b even, and a, c even and b odd, may have solutions which are not [f]-repetitions. If a, b are even and c odd, for the same w and f, we have $f^{a}(w)f^b(w)=\mathtt {a}\mathtt {a}\mathtt {b}\mathtt {a}\mathtt {a}\mathtt {a}\mathtt {b}\mathtt {a}= \mathtt {a}f^c(w) \mathtt {a}\mathtt {b}\mathtt {a}$. Again, it is an immediate consequence that when a, b are odd and c is even then $f^{a}(w)f^{b}(w)=xf^{c}(w)y$ may have solutions which are not [f]-repetitions.

Following the ideas of [11], an extension of Lemma 9 to the antimorphic case can be obtained by considering equations of the form

$$\begin{aligned} f^{a_1}(w)f^{a_2}(w)f^{a_3}(w)=xf^{b_1}(w)f^{b_2}(w)y \end{aligned}$$

for f antimorphic permutation on $\Sigma$, $a_1,a_2,a_3,b_1,b_2\in \mathbb {N}_0$, $w,x,y\in \Sigma ^{*}$, $0<|x|,|y|<|w|$. Our goal is to identify under which restrictions on $a_1,a_2,a_3,b_1,b_2$ the equation above enforces (for some f that makes the equality between the sides of the equation hold) that x, y, w are [f]-repetitions.

The main difference to the morphic case is that when iterating an antimorphic permutation f, $f^{i}(w)$ preserves the order of letters of w when i is even, and reverses it when i is odd; in the morphic case, the order was preserved for all exponents. Therefore, it seems a good approach to classify the equations considered above by the parity of their exponents. In the following, e (from even) and o (from odd) are used for 0 and 1 resp., for convenience. Moreover for each number a let $\overline{a}$ denote its residue class modulo 2.

Definition 23

Define the set of all these equations by

$$\begin{aligned} \mathcal {E}:=\{&f^{a_1}(w)f^{a_2}(w)f^{a_3}(w)=xf^{b_1}(w)f^{b_2}(w)y\mid f \,\, antimorphic \,\, permutation, \\&w,x,y\in \Sigma ^{*}, 0<|x|,|y|<|w|,a_1,a_2,a_3,b_1,b_2\in \mathbb {N}_0\}. \end{aligned}$$

The equations

$$\begin{aligned}E:&f^{a_1}(w)f^{a_2}(w)f^{a_3}(w)=xf^{b_1}(w)f^{b_2}(w)y \,\, and\\ E':&f^{a'_1}(w)f^{a'_2}(w)f^{a'_3}(w)=x'f^{b'_1}(w)f^{b'_2}(w)y' \end{aligned}$$

are called equivalent ($E\sim E'$) if $(\overline{a_1},\overline{a_2}, \overline{a_3},\overline{b_1},\overline{b_2})=(\overline{a'_1},\overline{a'_2}, \overline{a'_3},\overline{b'_1},\overline{b'_2})$ A class of equivalent equations will be denoted by the quintuple $(\overline{a_1},\overline{a_2}, \overline{a_3}\mid \overline{b_1},\overline{b_2})$. Such a class (resp., quintuple) is called repetition enforcing if every equation in the class it defines has only solutions which are [f]-repetitions.

Remark 24

Note that $\sim$ is an equivalence relation. Thus, the quotient set $\mathcal {E}/\!\!\sim$ is well defined. Since the elements of $\mathcal {E}$ are defined by five parameters, which are further reduced by the factorization w.r.t. $\sim$ to their canonical representative from $\mathbb {Z}_2$, then $\mathcal {E}$ has only 32 elements. Since all equivalent equations are associated to the same quintuple of elements of $Z_2$, these quintuples can be used as canonical representatives for the classes of $\mathcal {E}/\!\!\sim$.

In order to further group together classes of equation, it is worth noting the following.

Lemma 25

Let f be an antimorphic permutation on $\Sigma$. Consider the equations

$$\begin{aligned} f^{i_1}(w)\cdots f^{i_k}(w)=xf^{j_1}(w)\cdots f^{j_{k-1}}(w)y,0<|x|,|y|<|w| \end{aligned}$$

(2)

$$\begin{aligned} f^{i_1-1}(u)\cdots f^{i_k-1}(u)=xf^{j_1-1}(u)\cdots f^{j_{k-1}-1}(u)y, 0<|x|,|y|<|u| \end{aligned}$$

(3)

$$\begin{aligned} f^{i_k+1}(w)\cdots f^{i_1+1}(w)=f(y)f^{j_{k-1}+1}(w)\cdots f^{j_{1}+1}(w)f(x),\! 0\!<\!|x|,|y|\!<\! |w| \end{aligned}$$

(4)

$$\begin{aligned} f^{i_k}(u)\cdots f^{i_1}(u)=f(y)f^{j_{k-1}}(u)\cdots f^{j_{1}}(u)f(x), 0<|x|,|y|<|u| \end{aligned}$$

(5)

All the solutions of equation (i) are [f]-repetitions if and only if all solutions of equation (j) are [f]-repetitions, with $1\le i,j\le 4$.

Following the ideas of Lemma 25, it makes sense to define the following relation.

Definition 26

Two elements $E=(a_1,a_2,a_3\mid b_1,b_2)$ and $E'=(a_1',a_2'$, $a_3'\mid b_1',b_2')$ of $\mathcal {E}/\!\!\sim$ are called dual () if either $E=E'$ or one of the following cases holds (all the sums below are done in $Z_2$):

• 1. $(a_1',a_2',a_3'\mid b_1',b_2')=(a_3+1,a_2+1,a_1+1\mid b_2+1,b_1+1)$ (equating to the application of f to E)

• 2. $(a_1',a_2',a_3'\mid b_1',b_2')=(a_1+1,a_2+1,a_3+1\mid b_1+1,b_2+1)$ (equating to $f^z(w)=f^{z-1}(f(w))$ for $z\in \mathbb {Z}_2$)

• 3. $(a_1',a_2',a_3'\mid b_1',b_2')=(a_3,a_2,a_1\mid b_2,b_1)$ (equating to the application of 1. and 2.)

Remark 27

Since is also an equivalence relation the above mentioned 32 classes can be reduced to the following 10 classes of

The following lemma is a direct consequence of Lemma 25.

Lemma 28

(Duality Lemma). Let C be a class of and $E_1,E_2$ be in C. If $E_1$ is repetition-enforcing than $E_2$ as well.

For eight of the ten classes of it is shown that they are repetition-enforcing. In the remaining cases, counter-examples will be given.

Lemma 29

Classes 3 (represented by $(e,e,e\mid o,o)$) and 7 (represented by $(e,e,o\mid o,o)$) are not repetition-enforcing.

Proof

Equations of these classes that have solutions which are not [f]-repetitions can be obtained by extending the examples in Remark 22.

Consider $w=\mathtt {a}\mathtt {a}\mathtt {b}\mathtt {a}$ and f the mirror image on $\Sigma =\{\mathtt {a},\mathtt {b}\}$. Although w is not an [f]-repetition, the following holds: $w w w = \mathtt {a}\mathtt {a}\mathtt {b}\mathtt {a}\mathtt {a}\mathtt {a}\mathtt {b}\mathtt {a}\mathtt {a}\mathtt {a}\mathtt {b}\mathtt {a}= \mathtt {a}f(w) f(w) \mathtt {a}\mathtt {b}\mathtt {a},$ so class 3 is not repetition enforcing.

Also, the following holds $w w f(w) = \mathtt {a}\mathtt {a}\mathtt {b}\mathtt {a}\mathtt {a}\mathtt {a}\mathtt {b}\mathtt {a}\mathtt {a}\mathtt {b}\mathtt {a}\mathtt {a}= \mathtt {a}f(w) f(w) \mathtt {b}\mathtt {a}\mathtt {a},$ so class 7 is not repetition enforcing.

For some classes the repetition enforcement can be proven by Lemma 9 from the morphic case (Fig. 4). This is possible since the word $f^{b_1}(w)$ occurs inside $f^{a_1}(w)f^{a_2}(w)$ and $a_1,a_2,b_1$ are even (for short, e occurs in ee) in all equations contained in the classes 1, 2, 4, and 5. In class 10 we again have that e occurs in ee: $f^{a_2}(w)$ is a factor of $f^{b_1}(w)f^{b_2}(w)$, and $a_2,b_1,b_2$ are all even. Class 8 may appear to be different but in fact it contains a similar structure. The characteristic of the aforementioned pattern is, that - neglecting the permutations for a moment - a word is split into $w=xy$ and x occurs also as a suffix and y also as an infix. Having a deeper look into the representative of class 8 reveals that a prefix x of $f^{b_1}(w)$ is a suffix of $f^{a_1}(w)$ and a suffix y of $f^{b_2}(w)$ is a prefix of $f^{a_3}(w)$ with $|xy|=|w|$. So, $f^{a_1-a_3}(y)$ is a prefix of $f^{a_1}(w)$. Therefore, $f^{a_1}(w)$ is a factor of $f^{a_1-a_3}(w)f^{b_1}(w)$ and $a_1,a_1-a_3,b_1$ are all even. Accordingly, the following lemma holds.

Fig. 4.

With the aforementioned abbreviations e and o for an arbitrary even resp. odd permutation of f the classes 1, 2, 4, and 5 are given by the first picture. Class 10 is represented by the second picture and the picture below shows that the necessary 1-in-2 pattern (here visualised as a grey T) occurs if the middle part is ignored.

Lemma 30

The classes 1, 2, 4, 5, 8 and 10 are repetition-enforcing.

Before showing that class 9 is also repetition enforcing, several more definitions are needed. If $w=f^{i_1}(s)f^{i_2}(s)\cdots f^{i_k}(s)$, for some $s\in \Sigma ^{*}$ and $k\ge 1$, and $i_j \not \equiv _2 i_{j+1}$ for all $1\le j\le k-1$, then w is called an alternating [f, s]-repetition. If the word w is an alternating [f, s]-repetition for some s, but this word s is not important to us, then we just say that w is an alternating [f]-repetition.

It can be shown that if w is an alternating [f, s]-repetition then $f^{a_1}(w)f^{a_2}(w)f^{a_3}(w)$ is also an alternating [f, s]-repetition, where $a_1\equiv _2 a_3 \not \equiv _2 a_2$. Indeed, assume $a_1,a_3$ are even, and $a_2$ is odd (the other case is similar). If $w=f^{i_1}(s)f^{i_2}(s)\cdots f^{i_k}(s)$, for some $s\in \Sigma ^{*}$ and $k\ge 1$, and $i_j \not \equiv _2 i_{j+1}$ for all $1\le j\le k-1$, then

$$\begin{aligned} f^{a_1}(w)f^{a_2}(w)f^{a_3}(w)=&f^{a_1+i_1}(s)\cdots f^{a_1+i_k}(s)\cdot \\&f^{a_2+i_k}(s)\cdots f^{a_2+i_1}(s) \cdot \\&f^{a_3+i_1}(s)\cdots f^{a_3+i_k}(s). \end{aligned}$$

As $a_1+i_k$ has a different parity then $a_2+i_k$, and $a_2+i_1$ has a different parity then $a_3+i_1$, the claim follows.

Next, it is shown that class 9 is repetition enforcing, and, moreover, that if w is a solution of an equation from the respective class, then w is an alternating [f, s]-repetition for some word s.

Lemma 31

Class 9 is repetition-enforcing. More precisely, if

$$\begin{aligned} f^{a_1}(w)f^{a_2}(w)f^{a_3}(w)=xf^{b_1}(w)f^{b_2}(w)y \end{aligned}$$

with $x,y\ne \varepsilon$ and $(a_1,a_2,a_3\mid b_1,b_2)$ in class 9, then there exists $s\in \Sigma ^{*}$ such that $xf^{b_1}(w)$ and w are alternating [f, s]-repetitions.

The fact that class 6 is also repetition-enforcing follows now.

Lemma 32

Class 6 is repetition-enforcing.

Proof

Consider the equation $E: f^{a_1}(w)f^{a_2}(w)f^{a_3}(w)=xf^{b_1}(w)f^{b_2}(w)y$ corresponding to the representative of class 6. Then y is a suffix of $f^{a_3}(w)$. Thus $f^{b_2-a_3}(y)$ is a prefix of $f^{b_2}(w)$ (as $b_2-a_3$ is odd and $f^{b_2}(w)=f^{b_2-a_3}(f^{a_3}(w))$). By the alignment of $f^{b_2}(w)$ inside $f^{a_2}(w)f^{a_3}(w)$, It follows that $f^{b_2-a_3}(y)$ is a suffix of $f^{a_2}(w)$. Therefore, y is a prefix of $f^{a_2+a_3-b_2}(w)$ and $a_2+a_3-b_2$ is odd. Therefore, we get that $f^{a_2}(w)f^{a_3}(w)$ occurs inside $f^{b_1}(w)f^{b_2}(w)f^{a_2+a_3-b_2}(w)$, which leads to an equation represented by $(o,e,o\mid e,o)$, so from class 9. Such equations are repetition enforcing, by Lemma 32.

To conclude this section we propose a series of applications of our repetition enforcing results. In the first one, a repetition enforcing result in the style of FWT is presented.

Theorem 33

Let $u,v\in \Sigma ^{+}$ such that $|u|<|v|$. Let f be an antimorphic permutation of $\Sigma$ and $\alpha = f^{i_1}(u)f^{i_2}(u)\cdots f^{i_k}(u)$, $\beta =f^{j_1}(v)f^{j_2}(v)\cdots f^{j_p}(v)$ be two words such that: $k,p\ge 3$, $j_t \not \equiv _2 j_{t+1}$ for all $1\le t\le p-1$, and the common prefix of $\alpha$ and $\beta$ is longer than $2|v|+|u|$. Then there exists $\gamma \in \Sigma ^{+}$ such that $v,u\in \{f^i(\gamma )\mid 0\le i\le 2 \mathrm {ord}(f)\}^+$.

The second application shows that an extension of the LSE is repetition enforcing.

Theorem 34

Let f be an antimorphic permutation of an alphabet $\Sigma$. Consider the equation:

$$\begin{aligned} f^{i_1}(u)\dots f^{i_r}(u)f^{j_1}(v)\dots f^{j_s}(v)=f^{k_1}(w)\dots f^{k_t}(w), \end{aligned}$$

with $r,s\ge 3$, $t\ge 6$, and $i_p\not \equiv _2 i_{p+1}$ for $1\le p\le r-1$, $j_p\not \equiv _2 j_{p+1}$ for $1\le p\le s-1$, $k_p\not \equiv _2 k_{p+1}$ for $1\le p\le t-1$. Then there exists $\gamma$ such that $u,v,w\in \{f^i(\gamma )\mid 0\le i\le 2 \mathrm {ord}(f)\}^+$.

5 Further Directions

In this paper we presented a series of equations on words whose solutions are necessarily repetitions under anti-/morphic permutations. The main problem that still remains open is to characterise exactly the triples (r, s, t) for which the equation

$$\begin{aligned} f^{i_1}(u)\dots f^{i_r}(u)f^{j_1}(v)\dots f^{j_s}(v)=f^{k_1}(w)\dots f^{k_t}(w), \end{aligned}$$

with f antimorphic permutation, has only solutions which are [f]-repetitions. While Theorem 21 shows that the classical result of Lyndon and Schützenberger is preserved in the generalised case of morphic permutations, we expect that in the case of antimorphic permutations the results obtained in [17] for restricted case of antimorphic involutions should still hold.