Proof. If \(F^*\) is an empty set, then it is conjugate. Otherwise, assume that \((u,v)\) is a nonempty pair that belongs to \(F^*\). Therefore, \((u^\ell,v^\ell)\) for each \(\ell \geq 0\) also belongs to \(F^*\). We can safely assume that \(|u| = |v|\), otherwise each iteration will increase the difference in length between \(u^\ell\) and \(v^\ell\), leading to nonconjugacy of \(E\).

Let \(k = |\alpha_0| + |\beta_0| + |\alpha_1| + |\beta_1|\). Consider the pair \((\alpha_0,\beta_0)(u^\ell,v^\ell)(\alpha_1,\beta_1)\) where \(\ell\) is some value much larger than \(k\), say \(2^k\). Since \(\ell\) is much larger than \(k\) and \((\alpha_0u^\ell \alpha_1,\beta_0v^\ell \beta_1)\) is conjugate, there exist large factors of \(u^\ell\) and \(v^\ell\) that match as shown in Figure 1. Since \(|u| = |v|\), we can infer that \(u\) is a factor of \(vv\), and \(v\) is a factor of \(uu\).

Since \(v\) is an infix of \(uu\), the following holds as shown in Figure 1. There exist words \(x,y,p,\) and \(q\) such that \(v = xy\) and \(u = px = yq\). Since \(|u| = |v|\), length of \(p\) and length of \(y\) are the same, that implies \(p=y\) (since \(u = px = yq)\). Therefore, \(u = yx\). Hence \(u\) and \(v\) are conjugate words. Since the pair \((u,v)\) was arbitrary, \(F^*\) is conjugate. ◻

Proof. If \(E\) is conjugate, then for each \(i \in \{1, \ldots, k\}\), \[(\alpha_0 \cdots \alpha_{i-1},\beta_0 \cdots \beta_{i-1}) E_i^* (\alpha_i \cdots \alpha_k,\beta_i \cdots \beta_k) \subseteq E\] is conjugate. Therefore, from 1 we get that each of \(E_1^*, \ldots, E_k^*\) is conjugate. ◻

Proof. For a word \(w\), find the first nontrivial occurrence of \(w\) in \(ww\), and let the offset be the prefix of \(ww\) before this occurrence. This can be done in linear time using the classical pattern matching algorithm by Knuth-Morris-Pratt [17]. If the length of the offset divides the length of \(w\), the offset is the primitive root of the word \(w\). ◻

Proof. Consider the word \(w = uv\). We show that \(\rho_w \neq \rho_u\) and \(\rho_w \neq \rho_v\). Assume for contradiction that \(\rho_w = \rho_u\). Then \(uv \in (\rho_u)^*\). Since \(u \in (\rho_u)^*\), it follows that \(v \in (\rho_u)^*\) as well. Since primitive root of a word is unique, we get \(\rho_v = \rho_u\), which contradicts the assumption. By a similar argument, we get \(\rho_w \neq \rho_v\). Therefore, \(\rho_w \neq \rho_u\) and \(\rho_w \neq \rho_v\), which completes the proof. ◻

Proof. Suppose, for contradiction, that \(\rho_{w} \sim \rho_u\). Then, we have \(|\rho_{w}| = |\rho_u| = |\rho_{v}|\). Since \(w \in (\rho_{w})^*\) and both \(u\) and \(v\) are factors of \(w\) with lengths divisible by \(|\rho_{w}|\), it follows that \(u, v \in (\rho_{w})^*\). By uniqueness of primitive roots, this implies \(\rho_{u} = \rho_{w} = \rho_{v}\) contradicting \(\rho_{u} \neq \rho_{v}\). ◻

Proof. Two words \(u\) and \(v\) are conjugate if and only if either \(u=v\) or \(|u| = |v|\) and there is exactly one nontrivial occurence of \(v\) in \(uu\).

If \(u\) and \(v\) are distinct conjugates, then \(u=xy\) and \(v=yx\) for some nonempty words \(x,y\), implying \(uu = xyxy = xvy\), where \(v\) occurs nontrivially in \(uu\) exactly once. Conversely, if \(v\) occurs nontrivially in \(uu\) exactly once and \(|u| = |v|\), then there exist words \(x,y,p\) and \(q\) such that \(v = xy\) and \(u = px = yq\). Since \(|u| = |v|\), we get \(|p|=|y|\). This implies \(p=y\) since \(u = px = yq\). Therefore, \(u = yx\). Hence \(u\) and \(v\) are conjugate words.

Therefore, deciding whether a pair of words \((u,v)\) is conjugate can be done by checking if \(u =v\). If not, verify \(|u| = |v|\) and whether \(v\) occurs in \(uu\) nontrivially exactly once. This can be done in linear time using the Knuth-Morris-Pratt algorithm [17]. ◻

Proof. By definition, if pair \((u,v)\) is conjugate, then there exist a cut \((x,y)\) such that \(u=xy\) and \(v=yx\). Assume \(u\) and \(v\) are distinct, and hence \(x\) and \(y\) have to be nonempty. It suffices to show that \(x\) and \(y\) are unique if \(u\) and \(v\) are primitive.

For the sake of contradiction, assume that \((x,y)\) is not unique, i.e., there exists a different cut \((x^\prime,y^\prime)\) for \((u,v)\), i.e., \(u = x^\prime y^\prime\), \(v= y^\prime x^\prime\) and \(x^\prime \neq x, y^\prime \neq y\). WLOG, assume that \(|x| > |x^\prime|\). Therefore there exists a nonempty word \(p\) such that \(x = x^\prime p\) and \(y^\prime=py\). Substituting for \(x\) in \(v\), we get \[v = yx = yx^\prime p\] and substituting for \(y^\prime\) in \(v\), we obtain \[v = y^\prime x^\prime = pyx^\prime \;.\] Therefore \(yx^\prime\) and \(p\) commutes. By 3, they have the same primitive root. Since \(p\) and \(yx'\) are nonempty words, \(v\) is a power of some smaller word. Hence \(v\) is not primitive and it is a contradiction.

In the case where \(u=v\) and \(u\) being primitive, two possible cuts are \((u,\epsilon)\) and \((\epsilon,v)\), i.e., the empty cuts. Imagine there is a nonempty cut \((x,y)\). Since \(u=v\), it follows that \(xy=yx\). Using 3, \(u\) and \(v\) are powers of a smaller word and hence not primitive. Therefore, when \(u\) is primitive and \(u=v\), the only possible cuts are the empty cuts. ◻

Proof. Consider the case when \((u,v)\) is a distinct pair with the unique nonempty cut \((x,y)\). It suffices to show that if any of the equalities hold, there exists a different nonempty cut of the primitive pair \((u,v)\) contradicting [primitive].

1. In the case of [cuta], the other nonempty cut is \((x^{\prime\prime},yx^\prime)\) since \((xy,yx) = (x^{\prime\prime}yx^\prime,yx^\primex^{\prime\prime})\).

2. In the case of [cutb], the other nonempty cut is \((y^{\prime\prime}x,y^\prime)\) since \((xy,yx) = (y^{\prime\prime}xy^\prime,y^\primey^{\prime\prime}x)\).

3. When [cutc] is true, we obtain a different nonempty cut \((xy^\prime,y^{\prime\prime})\) because \((xy,yx) = (xy^\primey^{\prime\prime},y^{\prime\prime}xy^\prime)\).

4. If [cutd] holds, the other nonempty cut is \((x^\prime,x^{\prime\prime}y)\) since \((xy,yx) = (x^\primex^{\prime\prime}y,x^{\prime\prime}yx^\prime)\).

5. If [cute] holds, the other nonempty cut is \((y,x)\) since \((xy,yx) = (yx,xy)\) and \(x \neq y\) (since \(u \neq v\)).

Consider the special case when \(u=v\). If the equality \(u = u^{\prime\prime}u^\prime\) holds, then we obtain \(u = u^\primeu^{\prime\prime} = u^{\prime\prime}u^\prime\). Therefore, \(u^\prime\) and \(u^{\prime\prime}\) commutes. Since \(u^\prime\) and \(u^{\prime\prime}\) are nonempty words, \(u\) is a power of some smaller word using 3. Hence \(u\) is not primitive and it is a contradiction. ◻

Proof. Let \((u^\prime,v^\prime)= (u^n,v^n)\) for some \(n \geq 1\). The lemma is trivially true for \(n = 1\) by the uniqueness of cut of primitive pairs by [primitive].

Consider the case when \(n \geq 2\). Substituting for \(u=xy\) and \(v=yx\) in \(u^\prime\) and \(v^\prime\), \[\begin{align} u^\prime &= \overbrace{u \cdots u}^{n \text{ times}} = xy \cdots xy\\ v^\prime &= v \cdots v = yx \cdots yx \end{align}\] We show that cut in \(u^\prime\) will always be at the end of some \(x\) and all other cases leads to one of Cases [cuta] to [cute] of .

Case 1: When the cut is at the end of \(y\)

I.e., there exists a cut \((p,q)\) for \((u^\prime, v^\prime)\) such that \(p \in (xy)^+\). Then \[\begin{align} u^\prime &= \overbrace{ xy\cdots xy}^{p}\overbrace{ xy\cdots xy}^{q}\\ v^\prime &= yx \cdots yxyx \cdots yx = qp = \overbrace{ xy\cdots xy}^{q}\overbrace{ xy\cdots xy}^{p} \label{cl:eq1} \end{align}\tag{1}\] Equating the suffixes of \(v^\prime\) of length \(|xy|\) in both side of the 1 , we deduce \(xy = yx\), i.e., \(u = v\). It satisfies Case [cute] of . Hence a contradiction.

Case 2: When the cut is strictly within some \(x\) or \(y\)

We will make a further case analysis: when there is an \(xy\) present before the cut, and when there is an \(xy\) present after the cut (since \(n \geq 2\)).

Suppose the cut in \(u^\prime\) is in the \(i^\text{th}\) \(xy\) for \(i > 1\), i.e., there is an \(xy\) present before the cut.

1. When the cut is within \(x\), i.e., there exists a cut \((p,q)\) of \((u^\prime, v^\prime)\) such that \(p \in (xy)^+x^\prime\) where \(x^\prime\) is a nonempty proper prefix of \(x\) and \(x=x^\primex^{\prime\prime}\) for some word \(x^{\prime\prime}\). Now, \[\begin{align} u^\prime &=\overbrace{ \cdots x^\primex^{\prime\prime}yx^\prime}^{p}\overbrace{x^{\prime\prime}y \cdots}^{q}\\ v^\prime &= yx^\primex^{\prime\prime} \cdots yx^\primex^{\prime\prime} = qp = \overbrace{x^{\prime\prime}y \cdots}^{q}\overbrace{ \cdots x^\primex^{\prime\prime}yx^\prime}^{p} \label{cl:eq2} \end{align}\tag{2}\] As before, equating the suffixes of \(v^\prime\) of length \(|xy|\) on both sides of 2 , we obtain \[yx = yx^\primex^{\prime\prime} = x^{\prime\prime}yx^\prime\] Here \(x^\prime\) and \(x^{\prime\prime}\) satisfies Case [cutd] of . Hence a contradiction.

2. When the cut is within \(y\), i.e., there exists a cut \((p,q)\) of \((u^\prime, v^\prime)\) such that \(p \in (xy)^+xy^\prime\) where \(y^\prime\) is a nonempty prefix of \(y\) and \(y=y^\primey^{\prime\prime}\) for some word \(y^{\prime\prime}\). Then, \[\begin{align} u^\prime &=\overbrace{ \cdots xy^\primey^{\prime\prime}xy^\prime}^{p}\overbrace{y^{\prime\prime} \cdots}^{q}\\ v^\prime &= y^\primey^{\prime\prime}x \cdots y^\primey^{\prime\prime}x = qp = \overbrace{y^{\prime\prime} \cdots}^{q}\overbrace{ \cdots xy^\primey^{\prime\prime}xy^\prime}^{p} \label{cl:eq3} \end{align}\tag{3}\] On both sides of the 3 , equating the suffixes of \(v^\prime\) of length \(|xy|\), we get \[yx = y^\primey^{\prime\prime}x = y^{\prime\prime}xy^\prime\] that is Case [cutc] of . Hence a contradiction.

The case when there is an \(xy\) after the cut is symmetric and leads to Cases [cuta] and [cutb] of .

Since we have eliminated all of other cases, the only possible cuts of the pair \((u^\prime,v^\prime)\) are of the form \(((xy)^*x,(yx)^*y)\). ◻

Proof. Let \((u,v) = (u_1,v_1)^{\ell_1}(u_2,v_2)^{\ell_2}\) such that \(\ell_1 > 2\) and \(\ell_2 > \ell_1 + 2\) suffices. \[\begin{align} u &= \overbrace{u_1 \cdots u_1}^{\ell_1 \text{ times}}\overbrace{u_2u_2 \cdots u_2u_2}^{\ell_2 \text{ times}}\\ v &= v_1 \cdots v_1v_2v_2 \cdots v_2v_2 \end{align}\]

If \((u,v)\) is conjugate, then they have a cut say \((p,q)\). If either \(p\) or \(q\) is empty then both the pairs are identical. In this case, \(u_1=x_1y_1=y_1x_1=v_1\) and \(u_2=x_2y_2=y_2x_2=v_2\). By [primitive], either \(x_1=x_2 = \varepsilon\) or \(y_1=y_2=\varepsilon\). Thus, assume that both \(p\) and \(q\) are nonempty. There are two possibilities for a cut of \((u,v)\): when the cut in \(u\) is within \({u_1}^{\ell_1}u_2\) or it is after \({u_1}^{\ell_1}u_2\).

In both the cases we show that either \(x_1 = x_2\), or \(y_1=y_2\) or both.

Case 1: When the cut in \(u\) is within \({u_1}^{\ell_1}u_2\)

In this case, the cut in \(v\) is within the suffix \(v_2^{\ell_1+1}\) since the \(|u_1| = |u_2| = |v_2|\) and \(\ell_2 > \ell_1 + 2\). Substituting \((u_1,v_1)\) and \((u_2,v_2)\) with \((x_1y_1,y_1x_1)\) and \((x_2y_2,y_2x_2)\), \[\begin{align} u &= x_1y_1 \cdots x_1y_1\,x_2y_2 \cdots x_2y_2 = pq\\ v &= y_1x_1 \cdots y_1x_1 \cdots y_2x_2 \underbrace{y_2x_2}_{\text{cut region}} \cdots = qp \end{align}\] Since \(\ell_2 > \ell_1 + 2\), there exist at least one \(y_2x_2\) before the cut in \(v\). We compare the suffixes of \(q\) in both \(u\) and \(v\). Since \(q\) ends with \(x_2y_2\) in \(u\), the cut in \(v\) should be at the end of a \(y_2\) by Case [distinct] of . Note that by Case [same] of , the cut can end after \(x_2\) but then \(u_2=x_2y_2=y_2x_2 = v_2\) and hence either \(x_2 = \varepsilon\) or \(y_2 = \varepsilon\). In both case, we can say that the cut is at the end of a \(y_2\).

Hence \(p\) can be of the form \(x_2\) or \((x_2y_2)^+x_2\) depending upon if the cut in \(v\) is within the last \(y_2x_2\) or not. \[\begin{align} u &= x_1y_1 \cdots x_1y_1x_2y_2 \cdots x_2y_2 = pq\\ v &= \underbrace{y_1x_1 \cdots y_1x_1 \cdots y_2x_2y_2}_{q} \underbrace{x_2 \cdots}_{p} \end{align}\]

Suppose \(p \in (x_2y_2)^+x_2\), then equating the prefixes of \(p\) in \(u\) and \(v\) of length \(|x_2y_2| = |x_1y_1|\) (Since \(|u_1| = |u_2|\)), we obtain \(x_2y_2 = x_1y_1\). Substituting this in \(u\), \[\begin{align} u &= x_1y_1 \cdots x_1y_1x_1y_1 \cdots x_1y_1 = pq\\ v &= \underbrace{y_1x_1 \cdots y_1x_1 \cdots y_2x_2y_2}_{q} \underbrace{x_2y_2 \cdots x_2}_{p} \end{align}\]

Now we compare the prefixes of \(q\) in \(u\) and \(v\). Since \(q\) starts with \(y_1x_1\) in \(v\), from , the cut in \(u\) should be at the end of \(x_1\). Therefore, \(p \in (x_1y_1)^+x_1\) in \(u\). Also, \(p \in (x_2y_2)^+x_2\) in \(v\). Since \(|x_1y_1| = |x_2y_2|\) and \(|x_1|,|x_2| < |x_1y_1|\), we can deduce \(p = (x_1y_1)^{i}x_1 = (x_2y_2)^{i}x_2\) for some \(i\). Hence, \(x_1 = x_2\). Therefore, it implies \(y_1 = y_2\) since \(x_1y_1 = x_2y_2\) and hence, \((u_1,v_1)\) and \((u_2,v_2)\) are identical.

Suppose \(p =x_2\) in \(v\). Here, \(p\) in \(u\) is within the first \(x_1y_1\) since \(|x_1y_1| = |x_2y_2|\). Moreover \(p = x_1\) since the only possible cut in \(u\) will be at the end of \(x_1\) by (comparing the prefixes of \(q\) in \(u\) and \(v\)). Hence \(x_1 = x_2\).

Case 2: Cut in \(u\) is after \({u_1}^{\ell_1}u_2\)

This case is symmetric. For the sake of completeness we prove it.

Substituting \((u_1,v_1)\) and \((u_2,v_2)\) with \((x_1y_1,y_1x_1)\) and \((x_2y_2,y_2x_2)\), \[\begin{align} u &= x_1y_1 \cdots x_1y_1 \cdots x_2y_2 \overbrace{x_2y_2}^{\text{cut region}}\cdots = pq\\ v &= y_1x_1 \cdots y_1x_1y_2x_2 \cdots y_2x_2 = qp \end{align}\]

Note that there is at least one \(x_2y_2\) before the cut. We compare the suffixes of \(p\) in \(u\) and \(v\). Since \(p\) ends with \(y_2x_2\) in \(v\), the cut in \(u\) should be at the end of \(x_2\) by Case [distinct] of . Note that by Case [same] of , the cut can end after \(y_2\) but then \(u_2=x_2y_2=y_2x_2 = v_2\) and hence either \(x_2 = \varepsilon\) or \(y_2 = \varepsilon\). Hence \(q\) is of the form \(y_2\) or \((y_2x_2)^+y_2\) depending upon if the cut in \(u\) is within the last \(x_2y_2\) or not. \[\begin{align} u &= \overbrace{x_1y_1 \cdots x_1y_1 \cdots x_2y_2x_2}^{p}\overbrace{\cdots y_2}^{q}\\ v &= y_1x_1 \cdots y_1x_1y_2x_2 \cdots y_2x_2 = qp \end{align}\]

If \(q \in (y_2x_2)^+y_2\), then comparing the prefixes of \(q\) of length \(|y_2x_2| = |y_1x_1|\) (Since \(|v_1| = |v_2|\)) in \(u\) and \(v\), we obtain \(y_2x_2 = y_1x_1\). Substituting this in \(v\), \[\begin{align} u &= \overbrace{x_1y_1 \cdots x_1y_1 \cdots x_2y_2x_2}^{p}\overbrace{\cdots y_2}^{q}\\ v &= y_1x_1 \cdots y_1x_1y_1x_1 \cdots y_1x_1 = qp \end{align}\]

We compare the prefixes of \(p\) in \(u\) and \(v\). Since \(p\) starts with \(x_1y_1\) in \(u\), the cut in \(v\) should be at the end of \(y_1\) using . Therefore, \(q \in (y_1x_1)^+y_1\) in \(v\) and \(q \in (y_2x_2)^+y_2\) in \(u\). Hence, as before we can deduce that \(y_1 = y_2\). It also implies \(x_1 = x_2\) since \(y_1x_1 = y_2x_2\) and thus \((u_1,v_1)\) and \((u_2,v_2)\) are identical.

If \(q = y_2\). The cut in \(v\) is within first \(y_1x_1\). In fact, \(q=y_1\) since the only possible cut in \(u\) will be at the end of \(y_1\) by (comparing the prefixes of \(p\) in \(u\) and \(v\)). Hence \(y_1 = y_2\). ◻

Proof. We prove \((1) \iff (2)\) for inner witness. The outer witness case is symmetric.

\((2) \Rightarrow(1)\):

Assume that \(z\) is an inner witness of \((\rho_u,\rho_v)\). By induction on \(n\), we prove that \(z\) is also an inner witness of \((\rho_u, \rho_v)^n\) for all \(n \geq 1\), i.e., \(\rho_u^nz = z\rho_v^n\). It is true when \(n=1\). For all \(n > 1\), \[\begin{align} \rho_u^nz &= \rho_u^{n-1}\rho_uz\\ &= \rho_u^{n-1}z\rho_v && \text{(Since \rho_uz=z\rho_v)}\\ &= z\rho_v^{n-1}\rho_v && \text{(Inductive Hypothesis)}\\ &= z\rho_v^n \end{align}\] Since \((u,v)\) is a conjugate pair, there exists an integer \(n \geq 1\) such that \((u,v) = (\rho_u, \rho_v)^n\) by [primitiveconjugates]. Hence, \(z\) is also an inner witness for \((u,v)\).

\((1) \Rightarrow(2)\):

Since \((u,v)\) is conjugate, its primitive root \((\rho_u,\rho_v)\) is conjugate as well by [primitiveconjugates]. Consider the case when \(u \neq v\). It follows that \(\rho_u \neq \rho_v\). According to [primitive], the pair \((\rho_u,\rho_v)\) has a unique cut, denoted as \((x,y)\). From [cutlemmaprop], all cuts of \((u,v)\) are of the form \(((xy)^*x,(yx)^*y)\). From 1, an inner witness of \((u,v)\) belongs to \[((xy)^*x(yx)^*y)^*(xy)^*x = (xy)^*x\] and hence is an inner witness of \((\rho_u,\rho_v)\).

In the case where \(u=v\), it follows that \(\rho_u = \rho_v\). Consequently, any witness \(z\) for the pair \((u,u)\) belongs to the set \(u^*\) that is a subset of \(\rho_u^*\). Thus, \(z\) is also a witness for the pair \((\rho_u,\rho_v)\), since \(\rho_u^*\) consists of witnesses of \((\rho_u,\rho_v)\).

 ◻

Proof. Since \((\rho_1,\rho_2)\) are conjugate, there exists a cut \((x,y)\) such that \(\rho_1 = xy\) and \(\rho_2 = yx\). Moreover, since \(\rho \sim \rho_1 \sim \rho_2\), all three words have the same length, say \(p > 0\). Further, since \(\rho \sim \rho_1 = xy\), we have \(\rho^+ = s \rho_1^*t = s(xy)^* t\) for some words \(s,t\) such that \(|st| = p\).

Assume that \(\rho_1\alpha\rho_2\) is an infix of a word \(w \in \rho^+\). By the previous observation \(w=s(xy)^it\) for some sufficiently large \(i>0\). Firstly, assume \(\rho_1 \neq \rho_2\). Then, the cut \((x,y)\) is non-empty and unique by [primitive]. Since \(\rho_1\) and \(\rho_2\) are primitive, by [same] of , neither \(xy\) nor \(yx\) is equal to any of its non-trivial cyclic shifts. Given that \(\rho_1 \alpha\rho_2 = xy \alphayx\) occurs as an infix of \(w\). We do a case analysis. If \(xy \alphayx\) lies entirely within the factor \((xy)^i\) of \(w\), then by , the factor \(xy\) of \(xy \alphayx\) must align exactly with a factor \(xy\) of \(w\), and likewise \(yx\) should match exactly with a factor \(yx\) of \(w\). As a consequence, \(\alpha\in (xy)^*x\) which is an inner witness of \((\rho_1,\rho_2)\).

Next, assume for the sake of contradiction that \(xy \alphayx\) is a factor of \(s(xy)^i\), but not a factor of \((xy)^i\). Hence a suffix of \(s\) is a prefix of \(xy\) (recall that \(|s| \le p = |xy|\)). Since \(\rho \sim xy\) and \(|s| \le p\), \(s\) is an infix of \(xy\). Hence, the prefix \(xy\) of \(\rho_1\alpha\rho_2\) matches with a nontrivial cyclic shift of \(xy\) in \(w\). This contradicts . A symmetric argument rules out the case when \(xy \alphayx\) is a factor of \((xy)^it\), but not a factor of \((xy)^i\).

When \(\rho_1 = \rho_2\), the only cuts possible are empty cuts (i.e., either \(x\) or \(y\) is empty) by [primitive]. Thus \(\rho_1 = \rho_2 = x\), and the previous argument applies directly, and we get \(\alpha\in x^*\), and hence is an inner witness of \((\rho_1,\rho_2)\). ◻

Proof. Follows from the definition of common witness and 1. ◻

Proof. We prove for common inner witness. The common outer witness case is symmetric. \[\begin{align} z &\text{ is a common inner witness of } G\\ &\iff z \text{ is an inner witness of } (u,v) \text{ for each (u,v) \in G}\\ &\iff z \text{ is an inner witness of } (\rho_u,\rho_v) \text{ for each (u,v) \in G} && \text{ (By \Cref{samewitness})}\\ &\iff z \text{ is a common inner witness of } R(G) \end{align}\] ◻

Proof. We prove \((1) \Rightarrow(2) \Rightarrow(1)\) and \((1) \Rightarrow(5) \Rightarrow(3),(4) \Rightarrow(1)\).

\((2) \Rightarrow(1)\) and \((3),(4) \Rightarrow(1)\) is obvious. We first show \((5) \Rightarrow(3),(4)\). Since all the pairs in \(G\) have the same primitive root, \(R(G)\) is singleton. Thus, \(R(G)\) has infinitely many common inner as well as common outer witnesses by 1. Since \(G\) and \(R(G)\) have the same witnesses ([samewitnessext]), \(G\) also has infinitely many common inner and common outer witnesses.

Now it remains to show that \((1) \Rightarrow(2)\) and \((1) \Rightarrow(5)\). If the set \(G\) has two common witnesses, namely \(z_1\) and \(z_2\), then according to [samewitnessext], \(z_1\) and \(z_2\) are also common witnesses of \(R(G)\). Let \(R(G) = \{(u_i,v_i) \mid i \in I\}\) where \(I\) is an Index set.

Suppose \(z_1\) and \(z_2\) are two common inner witnesses of \(R(G)\). We choose cuts \((x_i,y_i)\) for each \((u_i,v_i) \in R(G)\) such that both \(z_1\) and \(z_2\) belongs to \(\bigcap_{i \in I}(x_iy_i)^*x_i\). Since \(R(G)\) is a set of primitive pairs, \((x_i,y_i)\) is the unique cut of \((u_i,v_i)\) when \(u_i \neq v_i\) by [primitive]. When \(u_i=v_i\), it has only two empty cuts, namely \((\epsilon, u_i)\) and \((u_i,\epsilon)\) (if \(u_i = v_i\)). The inner witnesses obtained using cut \((\epsilon, u_i)\) is a superset of inner witnesses obtained using \((u_i,\epsilon)\). Hence, we can choose cut \((x_i,y_i) = (\epsilon, u_i)\) for pair \((u_i,v_i)\) when \(u_i = v_i\). Therefore, as stated in [cwpattern], both \(z_1\) and \(z_2\) belongs to \(\bigcap_{i \in I}(x_iy_i)^*x_i\).

Without loss of generality, assume that \(|z_1| < |z_2|\). As depicted in 2, a common factor \(w \in \bigcap_{i \in I}(y_ix_i)^{\geq 1}\) exists for each \(u_i^\omega\) that can be repeated one after another in \(u_i^\omega\) to get longer and longer common inner witnesses.

By symmetry, when \(z_1\) and \(z_2\) are both common outer witnesses of \(R(G)\), we get infinitely many common outer witnesses.

Now, WLOG assume that \(z_1\) is a common inner witness and \(z_2\) is a common outer witness of \(R(G)\), where \(z_1 \neq z_2\). Here also we choose cuts \((x_i,y_i)\) for each \((u_i,v_i) \in R(G)\) such that \(z_1\) belongs to \(\bigcap_{i \in I}(x_iy_i)^*x_i\) and \(z_2\) belongs to \(\bigcap_{i \in I}(y_ix_i)^*y_i\). For each distinct primitive pair in \(R(G)\), there exists a unique cut. However, for identical primitive pairs, we fix a cut based on the values of \(z_1\) and \(z_2\). We consider two cases: either \(z_1, z_2 \neq \epsilon\), or exactly one of \(z_1\) and \(z_2\) is equal to \(\epsilon\). In the case where \(z_1, z_2 \neq \epsilon\), for primitive pairs \((u_i,v_i)\) such that \(u_i = v_i\), we can choose either of the two empty cuts as \((x_i,y_i)\), resulting in \(z_1 \in (x_iy_i)^*x_i\) and \(z_2 \in (y_ix_i)^*y_i\). In the second case, if \(z_1 = \epsilon\), we select the cut \((x_i,y_i) = (\epsilon, u_i)\). This choice ensures that \(z_1 \in (x_iy_i)^*x_i\) and \(z_2 \in (y_ix_i)^*y_i\) (since \(z_2 \neq \epsilon\)). Similarly, if \(z_2 = \epsilon\), we choose the cut \((x_i,y_i) = (u_i, \epsilon)\). Consequently, we can conclude that \(z_1\) belongs to \(\bigcap_{i \in I}(x_iy_i)^*x_i\) and \(z_2\) belongs to \(\bigcap_{i \in I}(y_ix_i)^*y_i\).

As shown in 3, concatenating \(z_1 \cdot z_2 \cdot z_1\) in \(u_i^\omega\), we get one more common inner witness \(z_3\) for \(R(G)\). By the above argument, \(R(G)\) has infinitely many common witnesses. Since witnesses of \(R(G)\) are also witnesses of \(G\) ([samewitnessext]), it implies that \(G\) itself has infinitely many common witnesses. This completes the proof of \((1) \Rightarrow(2)\).

In both the cases, we get that \((x_1y_1)^\omega = (x_2y_2)^\omega = \cdots\) and \((y_1x_1)^\omega = (y_2x_2)^\omega = \cdots\). Hence from Fine and Wilf 4, all \(u_i\)’s has the same primitive root. Similarly, all \(v_i\)’s has the same primitive root. This proves \((1) \Rightarrow(5)\). ◻

Proof. We prove \((4) \Rightarrow(3) \Rightarrow(2) \Rightarrow(1) \Rightarrow(4)\). The only nontrivial direction is \((1) \Rightarrow(4)\) that is proved in 4.

\((4) \Rightarrow(3)\)

Follows from [samewitnessext].

\((3) \Rightarrow(2)\)

Suppose there exists a common inner witness \(z\) of the set \(G\). Hence \(\forall (u,v) \in G\), \(u z=z v\). Let \((u',v')\) be any arbitrary element from \(G^*\), i.e., \((u',v') = (u_1\cdots u_n,v_1\cdots v_n)\) for some \(n \geq 1\) and \((u_i,v_i) \in G\) for \(1 \leq i \leq n\). By induction on \(n\), we equate \(u'z= zv'\) as follows. Thus, \(z\) is a common inner witness of \(G^*\). The proof for common outer witness is symmetric. \[\begin{align} u'z &= u_1\cdots u_{n-1}u_n z \\ &= u_1\cdots u_{n-1} z v_n && \text{(Since u_n z = z v_n)}\\ &= zv_1\cdots v_{n-1}v_n && \text{(Inductive Hypothesis)}\\ &= zv' \end{align}\]

\((2) \Rightarrow(1)\)

Follows from 1.

 ◻

Proof. Proof is by induction on the number of pairs in \(R(G)\).

Base Case:

When \(R(G)\) has only 2 pairs, i.e., let \(R(G) = \{(\rho_{u_1},\rho_{v_1}),(\rho_{u_2},\rho_{v_2})\}\). There exist \(\ell_1,\ell_2\) such that \(\ell_2 > \ell_1 + 2, \ell_1 > 2\) and \((\rho_{u_1},\rho_{v_1})^{l_1} (\rho_{u_2},\rho_{v_2})^{l_2} \in (u_1,v_1)^*(u_2,v_2)^*\) and hence it is conjugate. From we get either \(x_1 = x_2\) or \(y_1 = y_2\).

We also consider the case when \(R(G)\) has exactly 3 pairs, i.e., let \(R(G) = \{(\rho_{u_1},\rho_{v_1}),(\rho_{u_2},\rho_{v_2}), (\rho_{u_3},\rho_{v_3})\}\). For \(i,j\in [3]\), there exists set of pairs \(\{(\rho_{u_i},\rho_{v_i})^{\ell_i}(\rho_{u_{j}},\rho_{v_{j}})^{\ell_{j}} \mid \ell_{j} > \ell_i + 2, \ell_i > 2 \} \subset (u_1,v_1)^*(u_2,v_3)^*(u_{3},v_{3})^*\) that is conjugate. Thus, the pairs \((\rho_{u_i},\rho_{v_i})\) and \((\rho_{u_{j}},\rho_{v_{j}})\) satisfy either \(x_i = x_{j}\) or \(y_i = y_{j}\) by where \((x_i,y_i)\) and \((x_j,y_j)\) are cuts of \((\rho_{u_1},\rho_{v_1})\) \((\rho_{u_j},\rho_{v_j})\) respectively. There are 3 cases.

\(1.\)

All pairs in \(R(G)\) are identical. Then there exists cuts \((x_i,y_i)\) for each pair \((\rho_{u_i},\rho_{v_j}) \in R(G)\) for \(i \in [3]\) such that \(x_1 = x_2=x_3 = \varepsilon\). Hence, the proposition holds.

\(2.\)

Exactly one pair in \(R(G)\) is identical. Let \((\rho_{u_1},\rho_{v_1})\) and \((\rho_{u_2},\rho_{v_2})\) are distinct pairs with unique nonempty cuts \((x_1,y_1)\) and \((x_2,y_2)\) respectively. By 3, either \(x_1=x_2\) or \(y_1=y_2\). Assume that \(x_1=x_2\) Also, since \((\rho_{u_3},\rho_{v_3})\) is identical pair, either \(\rho_{u_3}=x_i\) or \(\rho_{u_3}=y_i\) for \(i\in [1,2]\). If there exists an \(i \in [1,2]\) such that \(\rho_{u_3}=x_i\), then \(x_1=x_2 = \rho_{u_3} = x_3\) where \((x_3,y_3) = (\rho_{u_3},\varepsilon)\) is a cut of \((\rho_{u_3},\rho_{v_3})\). Suppose for all \(i \in [1,2]\), \(\rho_{u_3}=y_i\), then \(y_1=y_2 = \rho_{u_3} = y_3\) where \((x_3,y_3) = (\varepsilon,\rho_{u_3})\) is a cut of \((\rho_{u_3},\rho_{v_3})\). Hence, the proposition holds.

\(3.\)

Exactly one pair in \(R(G)\) is non-identical. WLOG assume that \((\rho_{u_1},\rho_{v_1})\) and \((\rho_{u_3},\rho_{v_3})\) are the identical pairs, \((\rho_{u_2},\rho_{v_2})\) is non-identical with unique nonempty cut \((x_2,y_2)\).

Claim 1. \(\rho_{u_1}=\rho_{u_3}\).

Proof. Consider the pair \((u,v)=(u_1,v_1)^j(u_2,v_2)^{l}(u_3,v_3)^j\) where \(j\) and \(l\) are set such that \(|u_2^l| > 4 \cdot |u_1^j| = 4 \cdot |u_3^j|\). Substituting with their primitive roots, we get \[\begin{align} u &= \overbrace{u_1 \cdots u_1}^{B_1}\overbrace{u_2 \cdots u_2}^{B_2}\overbrace{u_3 \cdots u_3}^{B_3} = \rho_{u_1} \cdots \rho_{u_1}x_2y_2 \cdots x_2y_2 \cdots x_2y_2\rho_{u_3} \cdots \rho_{u_3}\\ v &= v_1 \cdots v_1v_2 \cdots v_2v_3 \cdots v_3 =\rho_{u_1} \cdots \rho_{u_1}y_2x_2 \cdots y_2x_2 \cdots y_2x_2\rho_{u_3} \cdots \rho_{u_3} \end{align}\] Let \(B_1,B_2,B_3\) denote the block of \(u_1\)’s, \(u_2\)’s and \(u_3\)’s. Similarly, \(B_1',B_2',B_3'\) denote the block of \(v_1\)’s, \(v_2\)’s and \(v_3\)’s. Since \((u,v)\) is conjuagte, it has a cut \((p,q)\). We do a case analysis on \(p\).

1. \(p\) ends within \(B_1(\rho_{u_1})^{-1}\). In this case, \(p\in \rho_{u_1}^*\) by Case [same] of since there exist atleast a factor \(\rho_{u_1}\) of \(q\) in \(u\) to match with the prefix \(\rho_{u_1}\) of \(q\) in \(v\). On further matching \(q\) in \(u\) and \(v\), since \(|\rho_{u_1}|=|x_2y_2| = |y_2x_2| = |\rho_{u_3}|\), we get \(\rho_{u_1}=x_2y_2 = y_2x_2 = \rho_{u_3}\).

2. \(p\) ends after block \(B_2\rho_{u_3}\). This case is symmetric to the above case, where we get \(q \in \rho_{u_3}^*\) by Case [same] of . On further matching \(p\) in \(u\) and \(v\), since \(|\rho_{u_3}|=|x_2y_2| = |y_2x_2| = |\rho_{u_1}|\), we get \(\rho_{u_3}=x_2y_2 = y_2x_2 = \rho_{u_1}\).

3. \(p\) ends within \(\rho_{u_1}B_2\rho_{u_3}\). WLOG assume that \(p\) ends within the first half of \(\rho_{u_1}B_2\rho_{u_3}\). Since \(|\rho_{u_1}B_2\rho_{u_3}|/2 > |B_2|/2 \geq 2. |u_1^j|\), on matching \(q\) in \(u\) and \(v\), the prefix \(u_1^j\) of \(v\) matches entirely with block \(B_2\) and there exist at least one factor of \(x_2y_2\) following that. Using , the prefix \(p (u_1^j)\) in \(u\) ends in \(x_2\). Since \(|\rho_{u_1}| = |x_2y_2| = |y_2x_2|\), we get \(\rho_{u_1} = y_2x_2 = x_2y_2\), and this contradicts that \((u_2,v_2)\) is a non-identical pair. Similarly, we get a contradiction when \(p\) ends withing second half of \(\rho_{u_1}B_2\rho_{u_3}\).

 ◻

Thus, we get \(\rho_{u_1}=\rho_{u_3}\) when exactly one pair in \(R(G)\) is non-identical. Since \((x_2,y_2)\) is the unique nonempty cut of \((u_2,v_2)\), by 3, either \(x_2=\rho_{u_1} = \rho_{u_3}\) or \(y_2 = \rho_{u_1}= \rho_{u_3}\). In either case the proposition holds.

Inductive Case:

Assume that the statement holds for \(k\) pairs in \(R(G)\), i.e., let \[R(G)= \{(\rho_{u_1},\rho_{v_1}), \ldots, (\rho_{u_k},\rho_{v_k})\}.\] By the induction hypothesis, if \((u_1,v_1)^* \cdots (u_k,v_k)^*\) is conjugate, then either \(x_1=\cdots=x_k \quad \text{or} \quad y_1=\cdots=y_k\). Without loss of generality assume that \(x_1=\cdots=x_k\). We prove that the statement also holds for \(k+1\) pairs.

Let \(G' \supseteq G\) such that \(R(G')=R(G)\cup \{(\rho_{u_{k+1}},\rho_{v_{k+1}})\},\) where \((\rho_{u_{k+1}},\rho_{v_{k+1}})\) is the conjugate primitive root of \((u_{k+1},v_{k+1})\in G'\) and has the same length as the pairs in \(R(G)\). Assume that \((u_1,v_1)^*\cdots (u_k,v_k)^*(u_{k+1},v_{k+1})^*\) is conjugate. Then for every \(i\in[k]\) there exists a set of pairs \[\{(\rho_{u_i},\rho_{v_i})^{\ell_i}(\rho_{u_{k+1}},\rho_{v_{k+1}})^{\ell_{k+1}} \mid \ell_{k+1}>\ell_i+2,\;\ell_i>2 \} \subseteq (u_1,v_1)^*\cdots (u_k,v_k)^*(u_{k+1},v_{k+1})^*\] that is conjugate. Hence, by , for every \(i\in[k]\) the pairs \((\rho_{u_i},\rho_{v_i})\) and \((\rho_{u_{k+1}},\rho_{v_{k+1}})\) satisfy either \[x_i=x_{k+1} \quad\text{or}\quad y_i=y_{k+1},\] where \((x_i,y_i)\) and \((x_{k+1},y_{k+1})\) are cuts of \((\rho_{u_i},\rho_{v_i})\) and \((\rho_{u_{k+1}},\rho_{v_{k+1}})\) respectively.

We partition \(R(G)\) into two sets: \(I=\{(\rho,\rho')\inR(G)\mid \rho=\rho'\}\) containing all identical pairs, and \(J=R(G)\setminus I\) containing all non-identical pairs. We distinguish the following cases.

1. If \(J=\emptyset\), then all pairs in \(R(G)\) are identical. Hence there exist cuts \((x_i,y_i)\) such that \[x_1=\cdots=x_k=\varepsilon .\] If \((\rho_{u_{k+1}},\rho_{v_{k+1}})\) is also identical, we can take \(x_{k+1}=\varepsilon\) and the statement follows.

   If \((\rho_{u_{k+1}},\rho_{v_{k+1}})\) is non-identical, it has a unique nonempty cut \((x_{k+1},y_{k+1})\). By 3 together with 1, for all \(i,j\in[k]\) either \[x_{k+1}=\rho_{u_i}=\rho_{u_j} \quad\text{or}\quad y_{k+1}=\rho_{u_i}=\rho_{u_j}.\] Thus \[\rho_{u_1}=\cdots=\rho_{u_k}=x_{k+1} \quad\text{or}\quad \rho_{u_1}=\cdots=\rho_{u_k}=y_{k+1},\] and the proposition holds.

2. Suppose \(J\neq\emptyset\).

   1. If \(I=\emptyset\), then every pair in \(R(G)\) is non-identical and has a unique nonempty cut \((x_i,y_i)\) for \(i\in[k]\). If \((\rho_{u_{k+1}},\rho_{v_{k+1}})\) is also non-identical with unique cut \((x_{k+1},y_{k+1})\), then by 3 either \(x_i=x_{k+1}\) for some \(i\in[k]\) or \(y_i=y_{k+1}\) for all \(i\in[k]\). In the former case we obtain \(x_1=\cdots=x_k=x_{k+1}\) by the induction hypothesis, and in the latter case \(y_1=\cdots=y_k=y_{k+1}\).

      If \((\rho_{u_{k+1}},\rho_{v_{k+1}})\) is identical, then 3 implies that either \(x_i=\rho_{u_{k+1}}\) for some \(i\in[k]\) or \(y_i=\rho_{u_{k+1}}\) for all \(i\in[k]\). Using the induction hypothesis we again obtain the desired equality.

   2. Suppose both \(I\) and \(J\) are nonempty. Without loss of generality let \[I=\{(\rho_{u_1},\rho_{v_1}),\ldots,(\rho_{u_{j-1}},\rho_{v_{j-1}})\} \text{ and }\] \[J=\{(\rho_{u_j},\rho_{v_j}),\ldots,(\rho_{u_k},\rho_{v_k})\}\] for some \(1<j\le k\). Each pair in \(J\) is non-identical and hence has a unique nonempty cut.

      By the induction hypothesis we obtain \[\label{eq:IJ} \rho_{u_1}=\cdots=\rho_{u_{j-1}}=x_j=\cdots=x_k .\tag{4}\]

      If \((\rho_{u_{k+1}},\rho_{v_{k+1}})\) is non-identical with cut \((x_{k+1},y_{k+1})\), then applying the base case for three pairs yields either \[\rho_{u_1}=x_i=x_{k+1} \quad\text{for some } i\in\{j,\ldots,k\}, \text{ or}\] \[\rho_{u_1}=y_i=y_{k+1} \quad\text{for all } i\in\{j,\ldots,k\}.\] Using 4 we obtain the desired equality of all \(x\)’s or all \(y\)’s.

      If \((\rho_{u_{k+1}},\rho_{v_{k+1}})\) is identical, then 3 implies that either \(x_i=\rho_{u_{k+1}}\) for some \(i\in\{j,\ldots,k\}\) or \(y_i=\rho_{u_{k+1}}\) for all such \(i\). Combining this with 4 and 1 again yields the required equality.

 ◻

Proof. When \(k= 1\), \(G\) has only one pair \((u,v)\) and by assumption it is conjugate. By 1, \((u,v)\) has a witness. From [samewitness], we obtain that the witnesses of \(R(G) = \{(\rho_{u},\rho_{v})\}\) are same as that of \((u,v)\).

Next we assume that \(k >1\). Let \(\approx\) be the equivalence relation on \(G\) whereby \((u,v) \approx (u^\prime,v^\prime)\) if \(\rho_{u} \sim \rho_{u^\prime}\), i.e., the primitive roots of the pairs are conjugates. Assume that \(\approx\) has \(d\) equivalence classes. Clearly \(1 \leq d \leq k\). We do a cases analysis on whether \(d=1\) or otherwise.

If \(\approx\) has only one equivalence class, then the primitive roots of all the pairs in \(G\) are conjugates. Consequently, their lengths are identical. Since \((u_1,v_1)^* \cdots (u_k,v_k)^*\) is conjugate and all the pairs in \(R(G)\) have identical lengths, by [eqlengthprimitivescorr], \(R(G)\) has a common witness.

Now we assume that \(d > 1\). Choose \(d\) pairs \((u_1, v_1), (u_2, v_2), \ldots, (u_d, v_d)\) from each equivalence class. We construct a pair \((u,v) \in (u_1,v_1)^*(u_2,v_2)^* \cdots (u_d,v_d)^* \subseteq (u_1,v_1)^* \cdots (u_k,v_k)^*\) and show that \((u,v)\) is conjugate only if \(R(G)\) has a common witness.

Let \(m\) be the least common multiple of \(|u_1|, \ldots, |u_d|\). Let \(\ell_{ij} = |u_i| + |u_j| - \mathit{gcd}(|u_i|,|u_j|) > 0\) for \(1 \leq i,j \leq d\) and \(i \neq j\). Let \(\ell = \max \;\{\ell_{ij} \mid 1 \leq i,j \leq d, i \neq j\}\). Let \(N\) be a multiple of \(m\) that is \(> 2\ell\).

Let \((u,v) = (u_1,v_1)^{j_1}(u_2,v_2)^{j_2} \cdots (u_d,v_d)^{j_d}\) such that \(j_1, \ldots, j_d > 2\) and \(|u_i^{j_i}| = N\) for each \(1 \leq i \leq d\). \[\begin{align} u &= \overbrace{u_1 \cdots u_1}^{N}\overbrace{u_2 \cdots u_2}^{N} \cdots \overbrace{u_d \cdots u_d}^{N}\\ v &= v_1 \cdots v_1\,v_2 \cdots v_2\, \cdots v_d \cdots v_d \end{align}\]

Since \((u,v)\) is conjugate, it has a cut, say \((p,q)\). Substituting each pair in \((u,v)\) with their primitive roots, we get \[\begin{align} u &= \rho_{u_1} \cdots \rho_{u_1}\rho_{u_2} \cdots \rho_{u_2} \cdots \rho_{u_d} \cdots \rho_{u_d} = pq\\ v &= \rho_{v_1} \cdots \rho_{v_1}\rho_{v_2} \cdots \rho_{v_2} \cdots \rho_{v_d} \cdots \rho_{v_d} = qp \end{align}\] Let \((x_i,y_i)\) be a cut of \((\rho_{u_i},\rho_{v_i})\) for \(1 \leq i \leq d\).

Let \(B_1, B_2, \ldots, B_d\) represent the blocks in \(u\), and let \(B_1^\prime, B_2^\prime, \ldots, B_d^\prime\) represent the blocks in \(v\).

The cut in \(u\) can be either within the first block \(B_1\), or the last block \(B_d\), or anywhere between the first and the last blocks in \(u\). We do a case analysis on all the possible cuts \((p,q)\) of \((u,v)\) and show that there exists a common witness of \(R(G)\) in each of the cases. We can assume that both \(p\) and \(q\) are nonempty. When either \(p\) or \(q\) is empty, then all pairs \((u_i,v_i)\) in \((u,v)\) are identical, and hence either \(x_1 = \cdots = x_d = \varepsilon\) or \(y_1 = \cdots =y_d= \varepsilon\).

Case 1: When the cut in \(u\) is in the first block \(B_1\)

We make a further case analysis depending upon if the cut is within the first half or the second half of the first block.

Suppose the cut in \(u\) is within the first half of the block, i.e., \(p\) is of length at most \(N/2\). In this case, since the length of each block are equal, the cut in \(v\) is within the second half of the last block \(B_d^\prime\), i.e., \(p\) is a suffix of \(v\) of length at most \(N/2\). \[\begin{align} u &= \overbrace{\rho_{u_1} \cdots}^{p}\overbrace{\cdots \rho_{u_1}\rho_{u_2} \cdots \rho_{u_2} \cdots \rho_{u_d} \cdots \rho_{u_d}}^{q}\\ v &= \underbrace{\rho_{v_1} \cdots \cdots \rho_{v_1}\rho_{v_2} \cdots \rho_{v_2} \cdots \rho_{v_d} \cdots}_{q} \underbrace{\cdots \rho_{v_d}}_{p} \end{align}\] We obtain \(q = p^{-1}(B_1B_2 \cdots B_d) = (B_1^\prime B_2^\prime \cdots B_d^\prime)p^{-1} \;.\)

From the above claim, it follows that \(q = q_1pq_2p \cdots pq_d\) and \[p = (x_1y_1)^{m_1}x_1 = (x_2y_2)^{m_2}x_2 = \cdots = (x_dy_d)^{m_d}x_d\] for \(m_1, \ldots, m_d \geq 0\).

From 3, the above equation holds for any two pairs between the equivalence classes. By [cwpattern], we obtain \(p\) is a common inner witness of \(R(G)\).

Next we assume the cut in \(u\) is in the second half of \(B_1\). We compare the prefixes of \(q\) in \(u\) and \(v\) and deduce that there exist a common factor of length at least \(N/2 > \ell > \ell_{12}\) between block \(B_1^\prime\) and block \(B_2\). From 5, \(\rho_{v_1}\) is conjugate to \(\rho_{u_{2}}\), that is in turn is conjugate to \(\rho_{v_{2}}\). From transitivity of conjugacy, \(\rho_{v_1}\) is conjugate to \(\rho_{v_2}\), which contradicts the fact that \((u_1,v_1)\) and \((u_2,v_2)\) belong to different equivalence classes. Hence cut in second half of \(B_1\) is not possible.

Case 2: When the cut in \(u\) is in the last block \(B_d\)

We make a further case analysis depending upon if the cut in \(u\) is in the first half or second half of the last block \(B_d\). The proof is symmetric to that of the previous case. In particular, when the cut is in the second half of the last block, \[q = (y_1x_1)^{m_1}y_1 = (y_2x_2)^{m_2}y_2 = \cdots = (y_dx_d)^{m_d}y_d \;.\] By 3 and [cwpattern], \(q\) is a common outer witness of \(R(G)\).

Case 3: When the cut in \(u\) is within the block \(B_j\) for \(1 < j < d\)

WLOG, assume that the cut in \(u\) is within the first half of the block \(B_j\). In this case the cut in \(v\) will be within the second half of the block \(B_{d-j+1}\). \[\begin{align} u &= \overbrace{\rho_{u_1} \cdots \rho_{u_1} \cdots \rho_{u_j} \cdots}^{p}\overbrace{\cdots \rho_{u_j} \cdots \cdots \cdots \cdots \rho_{u_d} \cdots \rho_{u_d}}^{q}\\ v &= \underbrace{\rho_{v_1} \cdots \rho_{v_1} \cdots \cdots \cdots \rho_{v_{d-j+1}} \cdots}_{q}\underbrace{\cdots \rho_{v_{d-j+1}} \cdots \rho_{u_d} \cdots \rho_{u_d}}_{p} \end{align}\] By matching \(q\) in \(u\) and \(v\), we get \(\rho_{v_1}\) and \(\rho_{u_j}\) shares a common factor of length at least \(N/2 > \ell > \ell_{1j}\) and hence they are conjugates to each other by 5. Since \(\rho_{u_j}\) is conjugate to \(\rho_{v_j}\), by transitivity of conjugacy we obtain \(\rho_{v_1}\) and \(\rho_{v_j}\) are conjugates. This contradicts the fact that \((u_1,v_1)\) and \((u_j,v_j)\) belongs to different equivalence classes. Hence cut in \(B_j\) where \(1 < j < d\) is not possible.

Hence, for a finite set of pairs \(G\), \((u_1,v_1)^* \cdots (u_k,v_k)^*\) is conjugate only if \(R(G)\) has a common witness. By [samewitnessext], we also conclude that \(G\) has a common witness. ◻

Proof. From [infmanycwcorr], if a set has a witness, it has exactly one common witness or infinitely many common witnesses. Given that every finite subset of \(G\) has a common witness, there are two possible cases: a finite subset of \(G\) with a unique witness exists, or every finite subset of \(G\) has infinitely many witnesses.

1. Assume that there exists a finite subset \(G_f\) of \(G\) with exactly one common witness, say \(z\). We claim that \(z\) is a common witness of \(G\) as well. By assumption, the finite set \(G_f \cup \{(u,v)\}\) has a common witness, for any pair \((u,v) \in G\). Moreover, the witness for this set must be \(z\); otherwise, it contradicts the uniqueness of the witness of \(G_f\). This implies that \(z\) is a witness for any pair in \(G\). Hence \(z\) is a common witness of \(G\).

2. Next we assume that every finite subset of \(G\) has infinitely many common witnesses. Take any pair \((u_i,v_i)\) and \((u_j,v_j)\) from \(G\). The set \(\{(u_i,v_i),(u_j,v_j)\}\) is a finite set with infinitely many witnesses by assumption. Therefore, from [infmanycwcorr], both \((u_i,v_i)\) and \((u_j,v_j)\) have the same primitive root. Since primitive roots are unique, the primitive root of every pair in \(G\) is the same. From [samewitness], the witnesses of the primitive root is same as that of the witnesses of each pair in \(G\). Hence, \(G\) has a common witness.

 ◻

Proof. Since \(M\) is conjugate, \((u,v)\) is also conjugate by 1. Consider the pair \((u^\prime,v^\prime) = (\alpha_0,\beta_0)(u,v)^{4n}(\alpha_1,\beta_1)\) where \(n|u| \geq 2 \cdot \textit{(length of the redux of M)}\). Let \((x,y)\) denote a cut of the primitive root of the conjugate pair \((u,v)\).

We now examine the possible cuts, say \((p,q)\), of \((u^\prime,v^\prime)\) and show that in each case, a common witness of \(\{(u,v), (\alpha_1\alpha_0,\beta_1\beta_0)\}\) exists.

Case 1: When the cut in \(u^\prime\) is within \(\alpha_0\)

Then \(p = \alpha_0^\prime\) is a prefix of \(\alpha_0\) and \(\alpha_0=\alpha_0^\prime\alpha_0^{\prime\prime}\) for some word \(\alpha_0^{\prime\prime}\). Substituting \((u,v)\) with powers of \((xy,yx)\), \[\begin{align} u^\prime &= \overbrace{\alpha_0^\prime}^{p}\overbrace{\alpha_0^{\prime\prime}xy\cdots xy \alpha_1}^{q}\\ v^\prime &= \beta_0 yx \cdots yx \beta_1 \end{align}\] Comparing prefixes of \(q\) in \(u^\prime\) and \(v^\prime\), we obtain three possible cases for \(\beta_0\).

1. \(\beta_0\) is a proper prefix of \(\alpha_0^{\prime\prime}\): After matching \(\beta_0\) with the prefix of \(q\) in \(u^\prime\), we find that the remaining suffix of \(\alpha_0^{\prime\prime}\) matches with the prefix of the block \(yx \cdots yx\) in \(v^\prime\). Since the total length of the block \(yx \cdots yx\) is greater than \(4|\alpha_0|\), it follows that \(\alpha_0^{\prime\prime}\) must end within the first half of the block. Furthermore, using Cases [cuta], [cutb], [cute] and [same] of , it should end after a \(y\) since there exists an \(xy\) after \(\alpha_0^{\prime\prime}\) in \(u^\prime\). Thus, we can express \(\alpha_0^{\prime\prime}\) as \[\alpha_0^{\prime\prime} = \beta_0 (yx)^m y \label{sing:eq1}\tag{5}\] for some integer \(m \geq 0\). Continuing to match \(q\) in \(u^\prime\) and \(v^\prime\), we obtain \[\begin{align} u^\prime &= \alpha_0^\prime\alpha_0^{\prime\prime}\overbrace{xy \cdots x}^{=}(yx)^{m}y{\alpha_1} = pq\\ v^\prime &= \underbrace{\beta_0 (yx)^{m}y}_{\alpha_0^{\prime\prime}}\underbrace{xy \cdots x}_{=}\beta_1 = qp = \alpha_0^{\prime\prime}\overbrace{xy \cdots x}^{=}(yx)^{m}y{\alpha_1} \alpha_0^\prime \label{singleton:eq1} \end{align}\tag{6}\] By equating the sets for \(v^\prime\) on both sides of 6 , we get \[\beta_1 = (yx)^{m}y\alpha_1\alpha_0^\prime \;. \label{sing:eq2}\tag{7}\] Concatenating 5 and 7 , we obtain \[(yx)^{m}y\alpha_1\alpha_0 =\beta_1\beta_0(yx)^{m}y \;.\] From 1, we get \((yx)^m y\) is a outer witness for \((\alpha_1\alpha_0, \beta_1\beta_0)\), and it is also a outer witness of \((u,v)\) using [samewitness]. Therefore, \((yx)^m y\) is a common outer witness of \(\{(u,v), (\alpha_1\alpha_0, \beta_1\beta_0)\}\).

2. The case when \(\beta_0 = \alpha_0^{\prime\prime}\): \[\begin{align} u^\prime &= \alpha_0^\prime\alpha_0^{\prime\prime}\overbrace{xy \cdots xy}^{=}{\alpha_1} = pq\\ v^\prime &= \underbrace{\beta_0}_{\alpha_0^{\prime\prime}}\underbrace{yx \cdots yx}_{=}\beta_1 = qp = \alpha_0^{\prime\prime}\overbrace{xy \cdots xy}^{=}{\alpha_1} \alpha_0^\prime \label{singleton:eq2} \end{align}\tag{8}\] Equating \(v^\prime\) on both sides of the 8 , we get that \(xy=yx\) and \[\beta_1 = {\alpha_1} \alpha_0^\prime \;. \label{sing:eq3}\tag{9}\] Appending the equation \(\beta_0 = \alpha_0^{\prime\prime}\) to 9 , we get \(\alpha_1\alpha_0 = \beta_1\beta_0\) . Hence \((\alpha_1\alpha_0,\beta_1\beta_0)\) is conjuagte with \(\varepsilon\) as a witness. Since \(xy=yx\), we can also deduce that \((u,v)\) is an identical pair with \(\varepsilon\) as a witness. Therefore, \(\varepsilon\) is a common witness of \(\{(u,v), (\alpha_1\alpha_0,\beta_1\beta_0)\}\).

3. \(\alpha_0^{\prime\prime}\) is a proper prefix of \(\beta_0\): Since the total length of block \(xy \cdots xy\) is at least 4\(|\beta_0|\), it follows that \(\beta_0\) must end within the first half of the block of \(xy\). Moreover, it should end after an \(x\) by Cases [cutc], [cutd], [cute] and [same] of since there is at least one \(yx\) after \(\beta_0\) in \(v^\prime\). Therefore, \[\beta_0 = \alpha_0^{\prime\prime}(xy)^{m}x \label{sing:4}\tag{10}\] for some integer \(m \geq 0\). Continuing with the analysis, we have: \[\begin{align} u^\prime &= \alpha_0^\prime\overbrace{\alpha_0^{\prime\prime}(xy)^{m}x}^{\beta_0}\overbrace{yx \cdots y}^{=}{\alpha_1} = pq\\ v^\prime &= \beta_0\underbrace{yx \cdots y}_{=}(xy)^{m}x\beta_1 = qp = \overbrace{\alpha_0^{\prime\prime}(xy)^{m}x}^{\beta_0}\overbrace{yx \cdots y}^{=}{\alpha_1} \alpha_0^\prime \label{singleton:eq3} \end{align}\tag{11}\] By equating the sets for \(v^\prime\) on both sides of 11 , we get \[(xy)^{m}x\beta_1 = {\alpha_1} \alpha_0^\prime \;. \label{sing:5}\tag{12}\] Concatenating 10 and 12 , we obtain \[\alpha_1\alpha_0(xy)^{m}x = (xy)^{m}x \beta_1\beta_0 \;.\] From 1, we get \((xy)^m x\) is an inner witness of \((\alpha_1\alpha_0,\beta_1\beta_0)\), and it is also an inner witness for \((u,v)\) using [samewitness]. Thus, \((xy)^m x\) is a common inner witness of \(\{(u,v), (\alpha_1\alpha_0,\beta_1\beta_0)\}\).

Case 2: When the cut in \(u^\prime\) is within the block of \((u,v) \cdots (u,v)\)

Then \(p\) ends within the block of \((u,v)\)’s. There are two cases based on whether the cut in \(u^\prime\) is within the first half or the second half of the block of \((u,v) \cdots (u,v)\).

1. When \(p\) ends within the first half of the block of \((u,v)\)’s: \[\begin{align} u^\prime &= \alpha_0 \overbrace{xy \cdots xy}^{\text{cut region}}\overbrace{xy\cdots xy}^{\geq 2n \text{ times}}\alpha_1 = pq\\ v^\prime &= \beta_0yx \cdots yxyx\cdots yx\beta_1 =qp \end{align}\] We compare the prefixes of \(q\) in \(u^\prime\) and \(v^\prime\). Since the length of the remaining half of the block of \(xy\)’s is still greater than \(2n|u| > 2 |\beta_0|\), it follows that \(\beta_0\) in \(v^\prime\) matches within the block of \(xy\)’s in \(u^\prime\) and there is at least one \(xy\) occurring after it. Moreover, it ends after an \(x\) by Cases [cutc], [cutd], [cute] and [same] of , as there is at least one \(yx\) in \(v^\prime\) after \(\beta_0\). Therefore, \[p\beta_0 = \alpha_0 (xy)^{m}x \label{sing:eq6}\tag{13}\] for some integer \(m \geq 0\). \[\begin{align} u^\prime &= \overbrace{\alpha_0(xy)^{m}x}^{p\beta_0}\overbrace{yx\cdots y}^{=}\alpha_1 = pq\\ v^\prime &= \beta_0\underbrace{yx \cdots y}_{=}(xy)^{m}x\beta_1 = qp = \beta_0\overbrace{yx\cdots y}^{=}\alpha_1p \label{singleton:eq4} \end{align}\tag{14}\] By equating the sets for \(v^\prime\) on both sides of 14 , we get \[\begin{align} (xy)^{m}x\beta_1 = \alpha_1p ~ & \Rightarrow~ (xy)^{m}x\beta_1\beta_0 = \alpha_1p\beta_0 &&\text{(Appending \beta_0)}\\ & \Rightarrow~ (xy)^{m}x\beta_1\beta_0 = \alpha_1\alpha_0(xy)^{m}x &&\text{(Substituting \Cref{sing:eq6})} \end{align}\]

   Therefore we obtain, \[\alpha_1\alpha_0(xy)^{m}x = (xy)^{m}x\beta_1\beta_0 \;.\] From 1, \((xy)^m x\) is an inner witness of \((\alpha_1\alpha_0,\beta_1\beta_0)\), and it is also an inner witness for \((u,v)\) using [samewitness]. Therefore, \((xy)^m x\) is a common inner witness of \(\{(u,v), (\alpha_1\alpha_0,\beta_1\beta_0)\}\).

2. When \(p\) ends within the second half of the block of \((u,v)\)’s: \[\begin{align} u^\prime &= \alpha_0 \overbrace{xy \cdots xy}^{\geq 2n \text{ times}}\overbrace{xy\cdots xy}^{\text{cut region}}\alpha_1 = pq\\ v^\prime &= \beta_0yx \cdots yxyx\cdots yx\beta_1 = qp \end{align}\] We compare the suffixes of \(p\) in \(u^\prime\) and \(v^\prime\). Since the suffix of \(p\) within the block \(xy\) is still greater than \(2n|u| > 2 |\beta_1|\), it follows that the suffix \(\beta_1\) in \(v^\prime\) matches within the block of \(xy\)’s in \(u^\prime\) and there is at least one \(xy\) occurring before it. Moreover, it starts with a \(y\) by Cases [cutc], [cutd], [cute] and [same] of since there is at least one \(yx\) before \(\beta_1\). Hence, \[\beta_1q = (yx)^{m}y\alpha_1 \label{sing:eq8}\tag{15}\] for some integer \(m \geq 0\). \[\begin{align} u^\prime &= \alpha_0\overbrace{xy\cdots x}^{=}\overbrace{(yx)^{m}y\alpha_1}^{\beta_1q} = pq\\ v^\prime &= \beta_0(yx)^{m}y\underbrace{xy \cdots x}_{=}\beta_1 = qp = q\alpha_0\overbrace{xy\cdots x}^{=}\beta_1 \label{singleton:eq5} \end{align}\tag{16}\] By equating \(v^\prime\) on both sides of the 16 , we get \[\begin{align} \beta_0(yx)^{m}y = q\alpha_0 ~ & \Rightarrow~ \beta_1\beta_0(yx)^{m}y = \beta_1q\alpha_0 &&\text{(Concatenating \beta_1 on the left side)}\\ & \Rightarrow~ \beta_1\beta_0(yx)^{m}y = (yx)^{m}y\alpha_1\alpha_0 &&\text{(Substituting \Cref{sing:eq8})} \end{align}\] Therefore, we obtain \[(yx)^{m}y\alpha_1\alpha_0 =\beta_1\beta_0(yx)^{m}y \;.\] From 1, we get \((yx)^m y\) is an outer witness of \((\alpha_1\alpha_0,\beta_1\beta_0)\), and it is also an outer witness for \((u,v)\) using [samewitness]. Therefore, \((yx)^{m}y\) is a common outer witness of \(\{(u,v), (\alpha_1\alpha_0,\beta_1\beta_0)\}\).

Case 3: When the cut in \(u^\prime\) is within \(\alpha_1\)

Then \(q = \alpha_1^{\prime\prime}\) is a suffix of \(\alpha_1\) and \(\alpha_1=\alpha_1^\prime\alpha_1^{\prime\prime}\) for some word \(\alpha_1^\prime\). \[\begin{align} u^\prime &= \overbrace{\alpha_0xy\cdots xy \alpha_1^\prime}^{p}\overbrace{\alpha_1^{\prime\prime}}^{q}\\ v^\prime &= \beta_0 yx \cdots yx \beta_1 \end{align}\] This case is symmetric to Case 1, where the cut in \(u^\prime\) is within \(\alpha_0\).

Thus, the pair \((u',v') \in M\) is conjugate only if there exist a common witness for the set \(\{(u,v),(\alpha_1\alpha_0,\beta_1\beta_0)\}\). ◻

Proof. Since \(M\) is conjugate, \(G^*\) is conjugate by 1. Further, \(G^*\) is conjugate iff \(G\) has a common witness by 6. The set \(G\) has two possibilities: it either has a unique common witness or infinitely many common witnesses using [infmanycwcorr].

Assume that \(G\) has infinitely many common witnesses. From [infmanycwcorr], each pair in \(G\) have the same primitive root, say \((\rho,\rho^\prime)\). The common witnesses of \(G\) are the same as that of the witnesses of \((\rho,\rho^\prime)\) using [samewitnessext]. Since \(M\) is conjugate, \((\alpha_0,\beta_0){(\rho^n,{\rho^\prime}^n)}^*(\alpha_1,\beta_1)\) is conjugate for some \(n \geq 1\). From [monomialcut], there exists a common witness of \(\{(\rho^n,{\rho^\prime}^n), (\alpha_1\alpha_0,\beta_1\beta_0)\}\). Furthermore, the witness of \((\rho,\rho^\prime)\) is the same as the witness of \((\rho^n,{\rho^\prime}^n)\) by [samewitness]. Therefore, we can conclude that there exists a common witness of \(\{(\rho,\rho^\prime),(\alpha_1\alpha_0,\beta_1\beta_0)\}\), and thus of \(G \cup \{(\alpha_1\alpha_0,\beta_1\beta_0)\}\).

Next we assume that \(G\) has a unique common witness. WLOG, assume that \(G\) has a unique common inner witness \(z\). It suffices to show that \(z\) is an inner witness of \((\alpha_1\alpha_0,\beta_1\beta_0)\). Every pair in \(G^*\) has a common witness with \((\alpha_1\alpha_0,\beta_1\beta_0)\) using [monomialcut]. If there exists a pair \((u,v)\) in \(G^*\) such that \(\{(u,v), (\alpha_1\alpha_0,\beta_1\beta_0)\}\) has infinitely many common witnesses, then both \((u,v)\) and \((\alpha_1\alpha_0,\beta_1\beta_0)\) have the same primitive root by [infmanycwcorr]. Since \(z\) is an inner witness of \((u,v)\), \(z\) is an inner witness of its primitive root, and thus also an inner witness of \((\alpha_1\alpha_0,\beta_1\beta_0)\) using [samewitness]. Suppose instead that every pair in \(G^*\) has a unique common witness with \((\alpha_1\alpha_0,\beta_1\beta_0)\). Since \(G\) has a unique common inner witness \(z\), there exists two distinct pairs \((u,v)\) and \((u',v')\) of length greater than \(z\) such that \(z\) is the unique common inner witness for the set \(\{(u,v),(u',v')\}\). These pairs can be expressed as \((u,v) = (zr,rz)\) and \((u',v') = (zr',r'z)\), where \(r \neq r'\). Consider the following three pairs formed using \((u,v)\) and \((u',v')\): \[(u_1,v_1) = (u'uu,v'vv) = (zr'zrzr,r'zrzrz),\] \[(u_2,v_2) = (uu'u,vv'v) = (zrzr'zr,rzr'zrz),\] \[(u_3,v_3) = (uuu',vvv') = (zrzrzr',rzrzr'z).\] For \(1 \leq i,j \leq 3\) with \(i \neq j\), the following properties hold:

1. \(|(u_i,v_i)| = |(u_j,v_j)|\).

2. \(|(\rho_{u_i},\rho_{v_i})| = |(\rho_{u_j},\rho_{v_j})|\). Since \(u_i\) and \(u_j\) (resp. \(v_i\) and \(v_j\)) are conjugates, their primitive roots are conjugates, and hence are of equal length, i.e., \(|\rho_{u_i}| = |\rho_{u_j}|\) (resp. \(|\rho_{v_i}| = |\rho_{v_j}|\)).

3. \((u_i,v_i) \neq (u_j,v_j)\). Otherwise, if \(u_i= u_j\) (or \(v_i=v_j\)), it would follow that \(r'zr=rzr'\) (or, \(r'zrzr=rzrzr'\)), implying that \(r'\) is a outer witness of \((zr,rz) = (u,v)\). Since \(r'\) is also an outer witness of \((u',v') = (zr',r'z)\), it contradicts the assumption that \(z\) is a unique common witness of the set \(\{(u,v),(u',v')\}\). Hence, \(u_i\neq u_j\) and \(v_i \neq v_j\).

4. \((\rho_{u_i},\rho_{v_i}) \neq (\rho_{u_j},\rho_{v_j})\). Since \(u_i \neq u_j\) (resp. \(v_i \neq v_j\)) and \(|(\rho_{u_i}| = |\rho_{u_j}|\) (resp. \(|\rho_{v_i}| = |\rho_{v_j})|)\), we get that \(\rho_{u_i} \neq \rho_{u_j}\) (resp. \(\rho_{v_i} \neq \rho_{v_j})\).

Let \((x_i,y_i)\) be the cut of \((\rho_{u_i},\rho_{v_i})\) for \(1 \leq i \leq 3\). The set \(\{(u_1,v_1),(u_2,v_2), (u_3,v_3)\}\) has a unique common witness, otherwise their primitive roots will be same by [infmanycwcorr] which is a contradiction. Since \(z\) is an inner witness of each \((u_i,v_i)\) , \(z\) is the unique common inner witnesss of \(\{(u_1,v_1),(u_2,v_2), (u_3,v_3)\}\) , and thus of \(\{(\rho_{u_1},\rho_{v_1}), (\rho_{u_2},\rho_{v_2}), (\rho_{u_2},\rho_{v_2})\}\) by [samewitnessext]. Since \((u_1,v_1)^*(u_2,v_2)^*(u_3,v_3)^* \subset G^*\) is conjugate and \(|(\rho_{u_1},\rho_{v_1})| = |(\rho_{u_2},\rho_{v_2})| = |(\rho_{u_3},\rho_{v_3})|\), \(z=x_1 =x_2 = x_3\) using [eqlengthprimitivescorr].

By assumption, each pair \((u_i,v_i)\) has a unique common witness with \((\alpha_1\alpha_0,\beta_0\beta_1)\). Thus, at least two of these three pairs, say \((u_i,v_i)\) and \((u_j,v_j)\), either both have unique common inner witnesses with \((\alpha_1\alpha_0,\beta_1\beta_0)\), or both have unique common outer witnesses with \((\alpha_1\alpha_0,\beta_1\beta_0)\). Assume that the set \(\{(u_i,v_i),(\alpha_1\alpha_0,\beta_1\beta_0)\}\) and \(\{(u_j,v_j),(\alpha_1\alpha_0,\beta_1\beta_0)\}\) both has a unique common inner witness, say \(z_i\) and \(z_j\) respectively. Let \((\alpha,\beta)\) be the primitive root of \((\alpha_1\alpha_0,\beta_1\beta_0)\). There exists integers \(m_i,m_j,n_i,n_j \in \mathbb{N}\) such that \[z_i = (x_iy_i)^{m_i}x_i = (\alpha\beta)^{n_i}\alpha\] \[z_j = (x_jy_j)^{m_j}x_j = (\alpha\beta)^{n_j}\alpha\] Suppose both \(m_i, m_j \geq 1\), then \(x_iy_i\) and \(x_jy_j\) are both equal length prefixes of \((\alpha\beta)^*\alpha\), and hence \(x_iy_i = x_jy_j\), which contradicts that \(\rho_{u_i} \neq \rho_{u_j}\). Hence, we get that either \(m_i = 0\) or \(m_j = 0\). WLOG, assume that \(m_i=0\), i.e., \(x_i = (\alpha\beta)^{n_i}\alpha\) and since \(z = x_i = x_j\), we get \(z \in (\alpha\beta)^*\alpha\), and hence is an inner witness of \((\alpha_1\alpha_0,\beta_1\beta_0)\). Infact, \(z\) is the unique common inner witness of \((u_i,v_i)\) and \((\alpha_1\alpha_0,\beta_1\beta_0)\). Since \(z\) (the unique common inner witness of \(G\)) is also an inner witness of \((\alpha_1\alpha_0,\beta_1\beta_0)\), we get that \(z\) is a common inner witness of \(G \cup \{(\alpha_1\alpha_0,\beta_1\beta_0)\}\).

The case where the set \(\{(u_i,v_i),(\alpha_1\alpha_0,\beta_1\beta_0)\}\) and \(\{(u_j,v_j),(\alpha_1\alpha_0,\beta_1\beta_0)\}\) both has a unique common outer witness is invalid and leads to a contradaction, since we get \(y_i\) and \(y_j\) are equal length prefixes of \((\beta\alpha)^*\beta\), and hence \(y_i = y_j\). This contradicts \(\rho_{u_i} \neq \rho_{u_j}\) since \(x_i = x_j\). ◻

Proof. There are two cases to consider depending upon if \(G \cup \{(\alpha_1\alpha_0,\beta_1\beta_0)\}\) has a common inner or outer witness.

Case \((a)\): When \(z'\) is a common inner witness of \(G \cup \{(\alpha_1\alpha_0,\beta_1\beta_0)\}\)

The following equations hold: \[\begin{align} \alpha_1\alpha_0 z' &= z' \beta_1\beta_0 \label{g1monomialwitness:eq1}\\ u z' &= z' v \text{ ~for any pair } (u,v) \in G^* \end{align}\tag{17}\] We claim that \(z = [\alpha_0z',\beta_0]_R = [\alpha_1,z'\beta_1]_L\) is a common witness for \(M\). There are two cases depending upon whether \(\beta_0\) is a suffix of \(\alpha_0z'\) or vice-versa in 17 .

1. When \(\beta_0\) is a suffix of \(\alpha_0z'\) or equivalently, when \(\alpha_1\) is a prefix of \(z'\beta_1\). We get \(z = \alpha_0z' {\beta_0}^{-1}= \alpha_1^{-1}z'\beta_1\), or equivalently \(\alpha_0z' =z\beta_0\) and \(\alpha_1z = z'\beta_1\). We show that \(z\) is a common inner witness for \(M\).

   For any \((u,v) \in G^*\), \[\begin{align} \alpha_0u\alpha_1 z &= \alpha_0uz'\beta_1 &&\text{(Substituting \alpha_1z = z'\beta_1)}\\ &=\alpha_0z'v\beta_1 &&\text{(z' is an inner witness of (u,v))}\\ &=z\beta_0v\beta_1 &&\text{(Substituting \alpha_0z' =z\beta_0)} \end{align}\]

2. When \(\alpha_0z'\) is a suffix of \(\beta_0\) or equivalently \(z'\beta_1\) is a prefix of \(\alpha_1\). We get \(z = \beta_0(\alpha_0z')^{-1} = (z'\beta_1)^{-1}\alpha_1\), or equivalently \(\alpha_1=z'\beta_1z\) and \(z\alpha_0z' = \beta_0\). We show that \(z\) is a common outer witness for \(M\).

   For any \((u,v) \in G^*\), \[\begin{align} z\alpha_0u\alpha_1 &= z\alpha_0uz'\beta_1z &&\text{(Substituting \alpha_1=z'\beta_1z)}\\ &= z\alpha_0z'v\beta_1z &&\text{(z' is an inner witness of (u,v))}\\ &= \beta_0v\beta_1z &&\text{(Substituting z\alpha_0z' = \beta_0)} \end{align}\]

Case \((b)\): When \(z'\) is a common outer witness of \(G\) and \((\alpha_1\alpha_0,\beta_1\beta_0)\)

Therefore, the following equations hold: \[\begin{align} z' \alpha_1\alpha_0 &= \beta_1\beta_0 z' \label{g1monomialwitness:eq2}\\ z' u &= v z' \text{ ~for any pair } (u,v) \in G^* \end{align}\tag{18}\] We claim that \(z = [\alpha_0,\beta_0z']_R = [z'\alpha_1,\beta_1]_L\) is a witness for \(M\). There are two cases depending upon if \(\alpha_0\) is a suffix of \(\beta_0z'\) or vice-versa in 18 .

1. When \(\alpha_0\) is a suffix of \(\beta_0z'\) or equivalently, \(\beta_1\) is a prefix of \(z'\alpha_1\). We get \(z = \beta_0z' \alpha_0^{-1} = \beta_1^{-1}z'\alpha_1\), or equivalently \(z\alpha_0=\beta_0z'\) and \(z'\alpha_1 =\beta_1z\). We show that \(z\) is a common outer witness for \(M\).

   For any \((u,v) \in G^*\), \[\begin{align} z\alpha_0u\alpha_1 &= \beta_0z'u\alpha_1 &&\text{(Substituting z\alpha_0=\beta_0z')}\\ &=\beta_0vz'\alpha_1 &&\text{(z' is an outer witness of (u,v))}\\ &=\beta_0v\beta_1z &&\text{(Substituting z'\alpha_1 =\beta_1z)} \end{align}\]

2. If \(\beta_0z'\) is a suffix of \(\alpha_0\) or equivalently, \(z'\alpha_1\) is a prefix of \(\beta_1\). Therefore, \(z = \alpha_0(\beta_0z')^{-1} = (z'\alpha_1)^{-1}\beta_1\), or equivalently \(\alpha_0=z\beta_0z'\) and \(z'\alpha_1z=\beta_1\). We show that \(z\) is a common inner witness for \(M\).

   For any \((u,v) \in G^*\), \[\begin{align} \alpha_0u\alpha_1z &= z\beta_0z'u\alpha_1z &&\text{(Substituting \alpha_0=z\beta_0z')}\\ &=z\beta_0vz'\alpha_1z &&\text{(z' is an outer witness of (u,v))}\\ &=z\beta_0v\beta_1 &&\text{(Substituting z'\alpha_1z=\beta_1)} \end{align}\]

Therefore, if there exists a common witness \(z'\) for \(G\) and \((\alpha_1\alpha_0,\beta_1\beta_0)\), then there also exists a common witness \(z\) for \(M\). Furthermore, since the redux remains constant in the word equation that relates the common witness of \(M\) and those of \(G \cup \{(\alpha_1\alpha_0,\beta_1\beta_0)\}\) , each distinct common witness of \(M\) corresponds to a distinct common witness of \(G \cup \{(\alpha_1\alpha_0,\beta_1\beta_0)\}\), and vice-versa. Consequently, if \(z'\) is the unique common witness for \(G \cup \{(\alpha_1\alpha_0,\beta_1\beta_0)\}\) then \(z\) is the unique common witness of \(M\), and conversely.

Suppose the set \(G \cup \{(\alpha_1\alpha_0,\beta_1\beta_0)\}\) has infinitely many witnesses. According to [infmanycwcorr], all the pairs in that set have the same primitive root, let us say \((\rho,\rho^\prime)\). Therefore, \(G^*(\alpha_1,\beta_1)(\alpha_0,\beta_0)\) is a subset of powers of \((\rho,\rho^\prime)\) and is conjugate. Since \(M\) is a cyclic shift of \(G^*(\alpha_1,\beta_1)(\alpha_0,\beta_0)\) and is also conjugate, it is also a subset of powers of a primitive root, let us say \((\rho_m,\rho_m^\prime)\), that is a cyclic shift of \((\rho,\rho^\prime)\). Moreover, \(\alpha_1\) (resp. \(\beta_1\)) is an inner (resp. outer) witness of \((\rho,\rho_m)\) (resp. \((\rho^\prime,\rho_m^\prime)\)). We observe that \((\rho_m,\rho_m^\prime)\) is the primitive root of the redux of \(M\). Hence, \(M\) is a subset of powers of the primitive root of its redux. ◻

Proof. Let \(M = (\alpha_0,\beta_0){G_1}^*(\alpha_1,\beta_1) \cdots (\alpha_{k-1},\beta_{k-1}){G_k}^*(\alpha_k,\beta_k)\) be a sumfree set. For \(i \in \{1, \ldots, k\}\), let \(M_i\) denote the singleton redux of \(M\) keeping only the Kleene star \(G_i^*\), i.e., \[M_i = (\alpha_0 \cdots \alpha_{i-1},\beta_0 \cdots \beta_{i-1})G_i^*(\alpha_i \cdots \alpha_k,\beta_i \cdots \beta_k)\] The proof of \((1) \Rightarrow(2)\) is trivial, i.e., if \(z\) is a common witness of \(M\), then \(z\) is also a common witness of \(M_i \subseteq M\).

We prove \((2) \Rightarrow(1)\). WLOG, assume that \(z\) is a common inner witness of each \(M_i\)’s. If the redux is an empty pair \((\varepsilon,\varepsilon)\), then \(M = {G_1}^*{G_2}^*\cdots {G_k}^*\). It is easy to prove that \(z\) is a common inner witness of \(M\) by showing that for any arbitrary pair \((u_i,v_i) \in G_i^*\), \(u_1 u_2 \cdots u_k z = z v_1v_2 \cdots v_k\). Proof by induction on \(k\). \[\begin{align} u_1 \cdots u_{k-1}u_k z &= u_1 \cdots u_{k-1}z v_k &&\text{(Since u_kz = zv_k)}\\ &=z v_1 \cdots v_{k-1} v_k &&\text{(By Induction Hypothesis)} \end{align}\]

Now, assume that the redux is nonempty. Since each \(M_i\) has a common witness, there exist a common witness, say \(z_i\), for \(G_i \cup \{(\alpha_i \cdots \alpha_k\alpha_0\cdots \alpha_{i-1},\beta_i \cdots \beta_k\beta_0\cdots \beta_{i-1})\}\) by 8. There are 3 possible cases for \(z_i\).

1. \(z_i\) is a unique common inner witness. Therefore, for any pair \((u_i,v_i) \in G_i^*\), \[\begin{align} u_i z_i &= z_i v_i\\ \alpha_i \cdots \alpha_k\alpha_0\cdots \alpha_{i-1}z_i &= z_i\beta_i \cdots \beta_k\beta_0\cdots \beta_{i-1}\\ z=\alpha_0 \cdots \alpha_{i-1}z_i(\beta_0 \cdots \beta_{i-1})^{-1} &= (\alpha_i \cdots \alpha_k)^{-1}z_i\beta_i \cdots \beta_k \text{ (By \Cref{g1monomialwitness} \ref{Thm7:1})} \label{z95m32i46w} \end{align}\tag{19}\]

2. \(z_i\) is a unique common outer witness. Therefore, for any pair \((u_i,v_i) \in G_i^*\), \[\begin{align} z_i u_i &= v_i z_i\\ z_i\alpha_i \cdots \alpha_k\alpha_0\cdots \alpha_{i-1} &= \beta_i \cdots \beta_k\beta_0\cdots \beta_{i-1}z_i\\ z = \alpha_0\cdots \alpha_{i-1}(\beta_0 \cdots \beta_{i-1}z_i)^{-1} &= (z_i\alpha_i \cdots \alpha_k)^{-1}\beta_i \cdots \beta_k \text{ (By \Cref{g1monomialwitness} \ref{Thm7:2})} \label{z95m32o46w} \end{align}\tag{20}\]

3. When \(G_i \cup \{(\alpha_i \cdots \alpha_k\alpha_0\cdots \alpha_{i-1},\beta_i \cdots \beta_k\beta_0\cdots \beta_{i-1})\}\) has infinitely many witnesses, by [infmanycwcorr], it is a set of powers of the same primitive root say \((\rho_i,\rho_i^\prime)\). Therefore \(z_i\) belongs to witnesses of \((\rho_i,\rho_i^\prime)\). From 8 [Thm7:3], the set \(M_i\) reduces to a set of powers of the primitive root of the redux \((\alpha_0 \cdots \alpha_k,\beta_0 \cdots \beta_k)\), say \((\rho,\rho^\prime)\). Note that \(\alpha_i \cdots \alpha_k\) (resp. \(\alpha_0 \cdots \alpha_{i-1}\)) is an inner (resp. outer) witness of \((\rho_i,\rho)\). Similarly \(\beta_i \cdots \beta_k\) (resp. \(\beta_0 \cdots \beta_{i-1}\)) is an inner (resp. outer) witness of \((\rho_i^\prime,\rho^\prime)\).

We show that \(z\) is a common inner witness of \(M\), i.e., for any arbitrary pair \((u_i,v _i) \in G_i^*\) (possibly empty), we prove \(\alpha_0u_1\alpha_1u_2\alpha_2 \cdots \alpha_{k-1}u_k\alpha_kz =z\beta_0v_1\beta_1v_2\beta_2 \cdots \beta_{k-1}v_k\beta_k\). The proof is by induction on the number of singleton reduxes, \(0 \leq i \leq k\).

Base Case

When \(i=0\), it is vacuously true since \(z\) is a witness of the redux.

Inductive Case

Assume for induction that it is true for the first \(i-1\) singleton reduxes, i.e., \[\alpha_0u_1\alpha_1u_2\alpha_2 \cdots u_{i-1}\alpha_{i-1} \cdots \alpha_{k}z =z\beta_0v_1\beta_1v_2\beta_2 \cdots v_{i-1}\beta_{i-1}\cdots\beta_{k} \;.\] We prove it for the first \(i\) singleton reduxes, i.e., we show \[\alpha_0u_1\alpha_1u_2\alpha_2 \cdots u_{i-1}\alpha_{i-1}u_{i}\alpha_{i} \cdots \alpha_{k}z =z\beta_0v_1\beta_1v_2\beta_2 \cdots v_{i-1}\beta_{i-1}v_{i}\beta_{i}\cdots\beta_{k} \;.\] There are 3 possible cases for the common witness \(z_i\) of \(G_i \cup \{(\alpha_i \cdots \alpha_k\alpha_0\cdots \alpha_{i-1},\beta_i \cdots \beta_k\beta_0\cdots \beta_{i-1})\}\).

1. When \(z_i\) is a unique common inner witness. From 19 , \(z = (\alpha_i \cdots \alpha_k)^{-1}z_i\beta_i \cdots \beta_k\). \[\begin{align} \alpha_0&u_1\alpha_1 \cdots u_{i-1}\alpha_{i-1}u_i \alpha_i \alpha_{i+1} \cdots \alpha_k z\\ &= \alpha_0 u_1\alpha_1 \cdots u_{i-1}\alpha_{i-1}u_iz_i\beta_i \cdots \beta_k &&\text{ (Subs. z)}\\ &= \alpha_0 u_1\alpha_1 \cdots u_{i-1}\alpha_{i-1}z_iv_i\beta_i \cdots \beta_k &&\text{ (u_iz_i = z_iv_i)}\\ &= \alpha_0 u_1\alpha_1 \cdots u_{i-1}\alpha_{i-1}\alpha_i \cdots \alpha_kz(\beta_i \cdots \beta_k)^{-1}v_i \beta_i \cdots \beta_k &&\text{ (Subs. z_i)}\\ &= z\beta_0v_1\beta_1 \cdots v_{i-1}\beta_{i-1}\beta_i \cdots \beta_k (\beta_i \cdots \beta_k)^{-1}v_i \beta_i \cdots \beta_k &&\text{ (Inductive Hypothesis)}\\ &= z\beta_0v_1\beta_1 \cdots v_{i-1}\beta_{i-1}v_i \beta_i \cdots \beta_k &&\text{ (Simplifying)} \end{align}\]

2. When \(z_i\) is a unique outer witness. By 20 , \(z = (z_i\alpha_i \cdots \alpha_k)^{-1}\beta_i \cdots \beta_k\). \[\begin{align} \alpha_0 &u_1\alpha_1 \cdots u_{i-1}\alpha_{i-1}u_i \alpha_i \alpha_{i+1} \cdots \alpha_k z\\ &= \alpha_0 u_1\alpha_1 \cdots u_{i-1}\alpha_{i-1}u_i \alpha_i \alpha_{i+1} \cdots \alpha_k(z_i\alpha_i \cdots \alpha_k)^{-1}\beta_i \cdots \beta_k &&\text{(Subs. z)}\\ &= \alpha_0 u_1\alpha_1 \cdots u_{i-1}\alpha_{i-1}u_i z_i^{-1}\beta_i \cdots \beta_k &&\text{(Simplifying)}\\ &= \alpha_0 u_1\alpha_1 \cdots u_{i-1}\alpha_{i-1}{z_i}^{-1}v_i\beta_i \cdots \beta_k &&\text{(u_i = {z_i}^{-1}v_iz_i)}\\ &= \alpha_0 u_1\alpha_1 \cdots u_{i-1}\alpha_{i-1}\alpha_i \cdots \alpha_kz(\beta_i \cdots \beta_k)^{-1}v_i \beta_i \cdots \beta_k &&\text{(Subs. z_i^{-1})}\\ &= z\beta_0v_1\beta_1 \cdots v_{i-1}\beta_{i-1}\beta_i \cdots \beta_k (\beta_i \cdots \beta_k)^{-1}v_i \beta_i \cdots \beta_k &&\text{(Inductive Hypothesis)}\\ &= z\beta_0v_1\beta_1 \cdots v_{i-1}\beta_{i-1}v_i \beta_i \cdots \beta_k &&\text{(Simplifying)} \end{align}\]

3. When \(z_i\) is a witness of the primitive root \((\rho_i,\rho_i^\prime)\) of \(G_i \cup \{(\alpha_i \cdots \alpha_k\alpha_0\cdots \alpha_{i-1},\beta_i \cdots \beta_k\beta_0\cdots \beta_{i-1})\}\) (The case where \(G_i \cup \{(\alpha_i \cdots \alpha_k\alpha_0\cdots \alpha_{i-1},\beta_i \cdots \beta_k\beta_0\cdots \beta_{i-1})\}\) have infinitely many witnesses). Here \((u_i,v_i)\) is some \(m^\mathit{th}\) power of \((\rho_i,\rho_i^\prime)\). Since \(z\) is a witness of a singleton redux, it is also a witness of the redux \((\alpha_0 \cdots \alpha_k,\beta_0 \cdots \beta_k)\), and hence a witness of its primitive root \((\rho,\rho^\prime)\). We also know that \(\alpha_i \cdots \alpha_k\) is an inner witness of \((\rho_i,\rho)\) and \(\beta_i \cdots \beta_k\) is an inner witness of \((\rho_i^\prime,\rho^\prime)\). \[\begin{align} \alpha_0 &u_1\alpha_1 \cdots u_{i-1}\alpha_{i-1}u_i \alpha_i \alpha_{i+1} \cdots \alpha_k z\\ &= \alpha_0 u_1\alpha_1 \cdots u_{i-1}\alpha_{i-1}(\rho_i)^{m} \alpha_i \alpha_{i+1} \cdots \alpha_k z &&\text{(Subs. u_i)}\\ &= \alpha_0 u_1\alpha_1 \cdots u_{i-1}\alpha_{i-1} \alpha_i \alpha_{i+1} \cdots \alpha_k(\rho)^{m} z &&\text{(\alpha_i \cdots \alpha_k is an i.w. of (\rho_i,\rho))}\\ &= \alpha_0 u_1\alpha_1 \cdots u_{i-1}\alpha_{i-1} \alpha_i \alpha_{i+1} \cdots \alpha_kz (\rho^\prime)^{m} &&\text{(z is a witness of (\rho,\rho^\prime))}\\ &= \alpha_0 u_1\alpha_1 \cdots u_{i-1}\alpha_{i-1} \alpha_i \alpha_{i+1} \cdots \alpha_kz (\beta_i \cdots \beta_k)^{-1}({\rho_i}^\prime)^{m}\beta_i \cdots \beta_k &&\text{(\beta_i \cdots \beta_k is an i.w. of (\rho_i^\prime,\rho^\prime))}\\ &= \alpha_0 u_1\alpha_1 \cdots u_{i-1}\alpha_{i-1} \alpha_i \alpha_{i+1} \cdots \alpha_kz (\beta_i \cdots \beta_k)^{-1}v_i\beta_i \cdots \beta_k &&\text{(Subs. v_i = (\rho_i^\prime)^{m})}\\ &= z\beta_0v_1\beta_1 \cdots v_{i-1}\beta_{i-1}\beta_i \cdots \beta_k (\beta_i \cdots \beta_k)^{-1}v_i \beta_i \cdots \beta_k &&\text{(Inductive Hypothesis)}\\ &= z\beta_0v_1\beta_1 \cdots v_{i-1}\beta_{i-1}v_i \beta_i \cdots \beta_k &&\text{(Simplifying)} \end{align}\]

Thus \(z\) is a common inner witness of \(M\). ◻

Proof. Assume that \(G_i^*\) has a unique common witness and let \(\rho\) be an arbitrary primitive word.

Let \(p=(\alpha_i \cdots \alpha_k \alpha_0 \cdots \alpha_{i-1},\; \beta_i \cdots \beta_k \beta_0 \cdots \beta_{i-1})\). Since \(|W(G_i^*)|=1\), there exist at least two pairs \((u_1,v_1), (u_2,v_2) \in G_i^*\) such that \(\rho_{u_1} \neq \rho_{u_2}\). Hence, by [prop:comb], we can construct three pairs in \(G_i^*\) that have pairwise distinct primitive roots. Therefore, there exist two pairs \((u_1,v_1), (u_2,v_2) \in G_i^*\) that have primitive roots different from that of \(p\). Therefore any two pairs from the set \(\{(u_1,v_1), (u_2,v_2), p\}\) has a unique common witness by 2. Moreover, by 7, \[\begin{align} W(\{(u_1,v_1), p\})=W( \{(u_2,v_2),p\})=W(G_i^*). \end{align}\] If either \(\rho_{u_1} \not\sim \rho\) or \(\rho_{u_2} \not\sim \rho\), then we choose the corresponding pair as \((u_i,v_i)\), and hence the claim follows. Otherwise, assume that \(\rho_{u_1} \sim \rho\sim \rho_{u_2}\).

Next consider the words \((u_3,v_3) = (u_1u_2, v_1v_2)\) and \((u_4,v_4) = (u_3u_1, v_3v_1)\). By [prop:nontriv-concat2], we deduce that \(\rho_{u_3} \not \sim \rho\) and \(\rho_{u_4} \not \sim \rho\). If \(\rho_{u_3}\) differs from the primitive root of \(\mathit{fst}(p)\), then \(W(\{(u_3,v_3),p\} = W(G_i^*)\) and \(\rho_{u_3} \not \sim \rho\). Hence the word \((u_i,v_i) = (u_3,v_3)\) satisfies the claim. Otherwise, \(\rho_{u_3}\) is the primitive root of \(\mathit{fst}(p)\). By [prop:comb], \(\rho_{u_3} \not \in \{\rho_{u_1},\rho_{u_2}\}\) since \(\rho_{u_1}\neq \rho_{u_2}\). By applying [prop:comb] again, we get \(\rho_{u_4} \neq \rho_{u_3}\). Hence, the primitive roots of \(u_4\) and \(\mathit{fst}(p)\) differ. Thus, \((u_i,v_i) = (u_4,v_4)\) satisfies the claim. ◻

Proof. We construct a canonical pair \((u,v)\) in \(M\) by choosing, for each \(i \in [1,k]\), a pair \((u_i,v_i) \in G_i^*\) satisfying Item \(1\) of 8. Item \(1.(a)\) holds trivially, while Item \(1.(b)\) follows from 7. It remains to verify Item \(2\) in 8. If \(|W(G_i^*)|=\infty\) for every \(i \in [1,k]\), then Item \(2\) is vacuously satisfied. Otherwise, suppose that there exists an index \(i \in [1,k]\) such that \(|W(G_i^*)|=1\). If there exists \(j\neq i \in [1,k]\)such that \(\rho_{u_i} \not\sim \rho_{u_j}\), then we are done. Otherwise, using 10 we choose a pair \((u_i',v_i')\in G_i^*\) that satisfies \(\rho_{u_i'} \not\sim \rho_{u_i}\) and Item \(1.(b)\). ◻

Proof. . Let \(w_1 = [\alpha_0,p\beta_0]_L\). There are two cases: either \(\alpha_0\) is a prefix of \(p\beta_0\), or \(p\beta_0\) is a prefix of \(\alpha_0\). In either case, we show that \(w_1\) is a witness of \((u_1,v_1)\).

• \(\alpha_0\) is a prefix of \(p\beta_0\): We show that \(w_1\) is an inner witness of \((u_1,v_1)\), and there exists a word \(q_1\) such that \(B_1 = w_1q_1\) and \(B_1' = q_1w_1\).

  Since \(\alpha_0\) is a prefix of \(p\beta_0\) and \(p\) is short, \(w_1 = \alpha_0^{-1}p\beta_0\) is a prefix of \(B_1(u_1)^{-1}\) in \(u\). We match \((p \beta_0)^{-1}u\) with \(\beta_0^{-1}vp^{-1}\). Since \(\beta_0^{-1}vp^{-1}\) starts with \(y_1x_1\) and since there is at least one factor \(x_1y_1\) following \(p\beta_0\), either \(w_1 \in (x_1y_1)^*x_1\) (by Case [distinct] of ) or \(w_1 \in (x_1y_1)^*\) and \(x_1y_1 = y_1x_1\) (by [same] of ). In the former case, \(w_1\) is an inner witness of \((x_1y_1,y_1x_1) = (\rho_{u_1},\rho_{v_1})\) and hence is also an inner witness of \((u_1,v_1)\) by [samewitness]. Similarly, when \(w_1 \in (x_1y_1)^*\) and \(x_1y_1 = y_1x_1\), we get \(w_1\) is an inner witness of \((x_1y_1,y_1x_1)\) as well as \((u_1,v_1)\).

  Let \(q_1 = w_1^{-1}B_1\). Clearly, \(q_1\) is of the form \((y_1x_1)^*y_1\) or \((x_1y_1=y_1x_1)^*\). In both cases, after matching \(q_1\) in block \(B_1'\) of \(v\), we observe that a factor equal to \(w_1\) appears in the suffix of the block of \(B_1'\), i.e., \(B_1' = q_1w_1\) (as shown below). \[\begin{align} u &= \overbrace{\alpha_0\,\overbrace{x_1y_1 \cdots x_1}^{w_1}}^{p\beta_0} \overbrace{\cdots x_1y_1}^{q_1} \, \alpha_1\, x_2y_2 \cdots x_2y_2 \, \alpha_2 \cdots x_ky_k \cdots x_ky_k \,\alpha_k\\ v &= \beta_0\,\underbrace{y_1x_1 \cdots y_1}_{q_1} \underbrace{x_1 \cdots y_1x_1}_{w_1} \, \beta_1 \,y_2x_2 \cdots y_2x_2 \, \beta_2 \, \cdots y_kx_k \cdots \cdots y_kx_k \, \beta_k \end{align}\]

• When \(p\beta_0\) is a prefix of \(\alpha_0\): We show that \(w_1\) is an outer witness of \((u_1,v_1)\), and there exists a word \(q_1\) such that \(B_1 = q_1w_1\) and \(B_1' = w_1q_1\).

  Since \(p\beta_0\) is a prefix of \(\alpha_0\) and \(|\alpha_0| \leq C < j_1\) , \(|w_1| = |(p\beta_0)^{-1}\alpha_0|<|v_1^{j_1}|\). Therefore \(w_1\) is a prefix of \(B_1'(v_1)^{-1}\) in \(v\). On matching \((p \beta_0)^{-1}u\) and \(\beta_0^{-1}vp^{-1}\), since the block \(B_1\) in \(u\) starts with \(x_1y_1\) and since there is at least one factor \(y_1x_1\) in \(B_1'\) after matching \(w_1\), either \(w_1 \in (y_1x_1)^*y_1\) (by Case [distinct] of ) or \(w_1 \in (y_1x_1)^*\) and \(x_1y_1 = y_1x_1\) (by [same] of ). In the former case, \(w_1\) is an outer witness of \((x_1y_1,y_1x_1) = (\rho_{u_1},\rho_{v_1})\) and hence is also an outer witness of \((u_1,v_1)\) by [samewitness]. When \(w_1 \in (y_1x_1)^*\), we get \(x_1y_1 = y_1x_1\) and hence \(w_1\) is an outer witness of \((x_1y_1,y_1x_1)\) as well as \((u_1,v_1)\).

  Let \(q_1= (w_1)^{-1}B_1'\). As in the case above, \(q_1 \in (x_1y_1)^*x_1\) or \(q_1 \in (x_1y_1=y_1x_1)^*\). In both cases, after matching \(q_1\) in block \(B_1\) of \(u\), a factor equal to \(w_1\) appears in the suffix of the block of \(B_1\), i.e., \(B_1 = q_1w_1\) (as shown below).

  \[\begin{align} u &= \overbrace{\alpha_0}^{p\beta_0w_1}\overbrace{x_1y_1 \cdots x_1}^{q_1}\overbrace{y_1\cdots x_1y_1}^{w_1} \, \alpha_1\, x_2y_2 \cdots x_2y_2 \, \alpha_2 \cdots x_ky_k \cdots x_ky_k \,\alpha_k\\ v &= \beta_0\,\,\,\underbrace{y_1x_1 \cdots y_1}_{w_1} \underbrace{x_1 \cdots y_1x_1}_{q_1} \, \beta_1 \,y_2x_2 \cdots y_2x_2 \, \beta_2 \, \cdots y_kx_k \cdots \cdots y_kx_k \, \beta_k \end{align}\]

.Proof by induction on \(i\in [2,k]\). The base case and the inductive step are identical. Hence we treat only the inductive step.

WLOG assume that \(w_{i-1}\) is an inner witness of \((u_{i-1},v_{i-1})\). The case where \(w_{i-1}\) is an outer witness of \((u_{i-1},v_{i-1})\) is symmetric. In this case, \(B_{i-1} = w_{i-1}q_{i-1}\) and \(B_{i-1}' = q_{i-1}w_{i-1}\) (as shown below). Moreover, \(|w_{i-1}| \leq |u_{i-1}^{j_{i-1}}|\).

\[\begin{align} u &= \cdots \alpha_{i-2}\overbrace{x_{i-1}y_{i-1} \cdots x_{i-1}}^{w_{i-1}} \overbrace{\cdots x_{i-1}y_{i-1}}^{q_{i-1}} \, \alpha_{i-1}\, x_iy_i \cdots x_iy_i \cdots \\ v &= \cdots \beta_{i-2}\underbrace{y_{i-1}x_{i-1} \cdots }_{q_{i-1}} \underbrace{x_{i-1} \cdots y_{i-1}x_{i-1}}_{w_{i-1}} \, \beta_{i-1} \,y_ix_i \cdots y_ix_i \cdots \end{align}\]

On matching further, there are two cases for \(w_i = [\alpha_{i-1},w_{i-1}\beta_{i-1}]_L\) as follows.

• When \(\alpha_{i-1}\) is a prefix of \(w_{i-1}\beta_{i-1}\): Here, \(w_i = (\alpha_{i-1})^{-1}w_{i-1}\beta_{i-1}\) begins at the block \(B_i\) in \(u\) as depicted in 4. Since \(|w_i| \leq |w_{i-1}\beta_{i-1}| \leq |u_{i-1}^{j_{i-1}}| + C < |u_i^{j_i}|/2\), \(w_i\) ends within block \(B_i\) and there exists at least one \(x_iy_i\) in \(B_i\) immediately following \(w_i\). Let \(B_i = w_i q_i\) for some word \(q_i\). On further matching \(q\) in \(u\) and \(v\), since the block \(B_i'\) in \(v\) starts with \(y_ix_i\) and since \(q_i\) consists at least one factor \(x_1y_1\), either \(w_i \in (x_iy_i)^*x_i\) (by Case [distinct] of ) or \(w_i \in (x_iy_i)^*\) and \(x_iy_i=y_ix_i\) (by [same] of ). In the former case, \(w_i\) is an inner witness of \((x_iy_i,y_ix_i) = (\rho_{u_i},\rho_{v_i})\) and hence also an inner witness of \((u_i,v_i)\) by [samewitness]. When \(w_i \in (x_iy_i)^*\), we get \(x_iy_i = y_ix_i\) and hence \(w_i\) is an inner witness of \((x_iy_i,y_ix_i)\) as well as \((u_i,v_i)\).

  Since \(B_i = w_iq_i\), after matching \(q_i\) in block \(B_i'\) of \(v\), we observe that a factor equal to \(w_i\) appears in the suffix of the block of \(B_i'\), i.e., \(B_i' = q_iw_i\) (as shown below).

  None

• When \(w_{i-1}\beta_{i-1}\) is a prefix of \(\alpha_{i-1}\): Here, \(w_i = (w_{i-1}\beta_{i-1})^{-1}\alpha_{i-1}\) begins at the block \(B_i'\) in \(v\). Since \(|w_i| \leq |\alpha_{i-1}| \leq C < |u_i^{j_i}|/2\), \(w_i\) ends within block \(B_i'\) and there exists at least one \(y_ix_i\) in \(B_i'\) immediately following \(w_i\). Let \(B_i' = w_i q_i\) for some word \(q_i\). On further matching \(q\) in \(u\) and \(v\), since the block \(B_i\) in \(u\) starts with \(x_iy_i\) and since \(q_i\) contains at least one \(y_ix_i\), either \(w_i \in (y_ix_i)^*y_i\) (by Case [distinct] of ) or \(w_i \in (y_ix_i)^*\) and \(x_iy_i = y_ix_i\) (by [same] of ). In the former case, \(w_i\) is an outer witness of \((x_iy_i,y_ix_i) = (\rho_{u_i},\rho_{v_i})\) and hence also an outer witness of \((u_i,v_i)\) by [samewitness]. When \(w_i \in (y_ix_i)^*\), we get \(x_iy_i = y_ix_i\) and hence \(w_i\) is an outer witness of \((x_iy_i,y_ix_i)\) as well as \((u_i,v_i)\).

  Since \(B_i' = w_iq_i\), after matching \(q_i\) in block \(B_i\) of \(u\), a factor equal to \(w_i\) appears in the suffix of the block of \(B_i\), i.e., \(B_i = q_iw_i\) (as shown below).

  None

Thus, the claim holds for \(i \in \{2, \ldots, k\}\).

. We prove the case when both \(w_1\) and \(w_k\) are inner witnesses of \((u_1,v_1)\) and \((u_k,v_k)\) respectively (as shown below). All other cases are symmetric.

\[\begin{align} u &= \overbrace{\alpha_0\,\overbrace{x_1y_1 \cdots x_1}^{w_1}}^{p\beta_0} \overbrace{\cdots x_1y_1}^{q_1} \, \alpha_1\, x_2y_2 \cdots x_2y_2 \, \alpha_2 \cdots \overbrace{x_ky_k \cdots x_k}^{w_k}\overbrace{\cdots x_ky_k}^{q_k} \,\alpha_k\\ v &= \beta_0\,\underbrace{y_1x_1 \cdots y_1}_{q_1} \underbrace{x_1 \cdots y_1x_1}_{w_1} \, \beta_1 \,y_2x_2 \cdots y_2x_2 \, \beta_2 \, \cdots \underbrace{y_kx_k \cdots}_{q_k}\underbrace{x_k \cdots y_kx_k}_{w_k} \, \beta_k \end{align}\]

We get that \[\begin{align} w_k\beta_k &= \alpha_kp &&\text{ (By matching u and v)}\\ w_k\beta_k\beta_0 &= \alpha_kp\beta_0 &&\text{ (Appending \beta_0)}\\ &= \alpha_k\alpha_0w_1. &&\text{ (Subs. p\beta_0 = \alpha_0w_1)} \qedhere \end{align}\] ◻

Proof. Proof by induction on \(j-i\). Base case is when \(j = i+1\) and the claim holds by 11. WLOG assume \(w_i\) is an inner witness of \((u_i,v_i)\) and the case 1. holds for \(j\) with \(i < j < k\), and we show that it also holds for \(j+1\). There are two cases:

• When \(w_j\) is an inner witness of \((u_j,v_j)\): \(w_j = (\alpha_i \cdots \alpha_{j-1})^{-1}w_i\beta_i \cdots \beta_{j-1}\) (by inductive hypothesis). From 11, we get that \(w_{j+1}\) is a witness of \((u_{j+1},v_{j+1})\) and \[\begin{align} w_{j+1} &= [\alpha_j,w_j\beta_j]_L && \text{(By \Cref{claimblock})}\\ &=[\alpha_j,(\alpha_i \cdots \alpha_{j-1})^{-1}w_i\beta_i \cdots \beta_{j-1}\beta_j]_L && \text{(Subs. w_j)}\\ &=[\alpha_i \cdots \alpha_{j-1}\alpha_j,w_i\beta_i \cdots \beta_{j-1}\beta_j]_L &&\text{(Since [u,v]_L = [wu,wv]_L for all w)} \end{align}\] If \(w_{j+1}\) is an inner witness of \((u_{j+1},v_{j+1})\), then \[\begin{align} w_{j+1}&= (\alpha_j)^{-1}w_j\beta_j\\ &= (\alpha_j)^{-1}(\alpha_i \cdots \alpha_{j-1})^{-1}w_i\beta_i \cdots \beta_{j-1}\beta_j &&\text{ (Subs. w_j by I.H.)}\\ &=(\alpha_i \cdots \alpha_{j-1}\alpha_j)^{-1}w_i\beta_i \cdots \beta_{j-1}\beta_j \end{align}\] Similarly, if \(w_{j+1}\) is an outer witness of \((u_{j+1},v_{j+1})\), then \[\begin{align} w_{j+1}&= (w_j\beta_j)^{-1}\alpha_j\\ &= ((\alpha_i \cdots \alpha_{j-1})^{-1}w_i\beta_i \cdots \beta_{j-1}\beta_j)^{-1}\alpha_j &&\text{ (Subs. w_j by I.H.)}\\ &=(w_i\beta_i \cdots \beta_{j-1}\beta_j)^{-1}\alpha_i \cdots \alpha_{j-1}\alpha_j \end{align}\]

• When \(w_j\) is an outer witness: \(w_j = (w_i\beta_i \cdots \beta_{j-1})^{-1}\alpha_i \cdots \alpha_{j-1}\) (by inductive hypothesis). From 11, we get that \(w_{j+1}\) is a witness of \((u_{j+1},v_{j+1})\) and \[\begin{align} w_{j+1} &= [w_j\alpha_j,\beta_j]_L && \text{(By \Cref{claimblock})}\\ &=[(w_i\beta_i \cdots \beta_{j-1})^{-1}(\alpha_i \cdots \alpha_{j-1})\alpha_j,\beta_j]_L && \text{(Subs. w_j)}\\ &=[\alpha_i \cdots \alpha_{j-1}\alpha_j,w_i\beta_i \cdots \beta_{j-1}\beta_j]_L &&\text{([u,v]_L = [wu,wv]_L for all w)} \end{align}\] If \(w_{j+1}\) is an inner witness of \((u_{j+1},v_{j+1})\), then \[\begin{align} w_{j+1}&= (w_j\alpha_j)^{-1}\beta_j\\ &= ((w_i\beta_i \cdots \beta_{j-1})^{-1}\alpha_i \cdots \alpha_{j-1}\alpha_j)^{-1}\beta_j &&\text{ (Subs. w_j by I.H.)}\\ &=(\alpha_i \cdots \alpha_{j-1}\alpha_j)^{-1}w_i\beta_i \cdots \beta_{j-1}\beta_j \end{align}\] Similarly, if \(w_{j+1}\) is an outer witness of \((u_{j+1},v_{j+1})\), we can show that \(w_{j+1} = (w_i\beta_i \cdots \beta_{j-1}\beta_j)^{-1}\alpha_i \cdots \alpha_{j-1}\alpha_j\).

The case where \(w_i\) is an outer witness of \((u_i,v_i)\) is symmetric. ◻

Proof. WLOG assume that \(w_i\) is an inner witness of \((u_i,v_i)\). The other case is symmetric. Using 12, \[w_k = [\alpha_i \cdots \alpha_{k-1},w_i\beta_i \cdots \beta_{k-1}]_L,\] \[\label{eq:cl6:1} w_i = (\alpha_1 \cdots \alpha_{i-1})^{-1}w_1\beta_1\cdots \beta_{i-1}\tag{21}\]

We perform a case analysis on whether \(w_1\) and \(w_k\) are inner/outer witnesses. Assume that \(w_1\) is as inner witness of \((u_1,v_1)\) and \(w_k\) is an outer witness of \((u_k,v_k)\). Hence, \[\label{eq:cl6:2} w_k = (w_i\beta_i \cdots \beta_{k-1})^{-1}\alpha_i \cdots \alpha_{k-1}\tag{22}\] Using Item 3 of 11, we get that \[\label{eq:cl6:3} w_1 = (w_k\alpha_k\alpha_0)^{-1}\beta_k\beta_0.\tag{23}\] Therefore, \[\begin{align} w_i &=(\alpha_1 \cdots \alpha_{i-1})^{-1}w_1\beta_1\cdots \beta_{i-1} &&\text{ (Using \Cref{eq:cl6:1}}\\ &=(\alpha_1 \cdots \alpha_{i-1})^{-1}(w_k\alpha_k\alpha_0)^{-1}\beta_k\beta_0\beta_1\cdots \beta_{i-1} &&\text{ (Subs. \Cref{eq:cl6:3}}\\ &=(w_k\alpha_k\alpha_0\alpha_1 \cdots \alpha_{i-1})^{-1}\beta_k\beta_0\beta_1\cdots \beta_{i-1}\\ &=((w_i\beta_i \cdots \beta_{k-1})^{-1}\alpha_i \cdots \alpha_{k-1}\alpha_k\alpha_0\alpha_1 \cdots \alpha_{i-1})^{-1}\beta_k\beta_0\beta_1\cdots \beta_{i-1} &&\text{ (Subs. \Cref{eq:cl6:2}}\\ &=(\alpha_i \cdots \alpha_{k-1}\alpha_k\alpha_0\alpha_1 \cdots \alpha_{i-1})^{-1}w_i\beta_i \cdots \beta_{k-1}\beta_k\beta_0\beta_1\cdots \beta_{i-1} \end{align}\] Hence \(w_i\) is also an inner witness of \((\alpha_i \cdots \alpha_k\alpha_0 \cdots \alpha_{i-1},\beta_i \cdots \beta_k\beta_0 \cdots \beta_{i-1})\). All other cases for \(w_1\) and \(w_k\) are analogous. ◻

Proof. Let \[\begin{align} M_i &= (\alpha_0 \cdots \alpha_{i-1}, \beta_0 \cdots \beta_{i-1})G_i^*(\alpha_i \cdots \alpha_k,\beta_i \cdots \beta_k)\\ M_j &= (\alpha_0 \cdots \alpha_{j-1}, \beta_0 \cdots \beta_{j-1})G_j^*(\alpha_j \cdots \alpha_k,\beta_j \cdots \beta_k) \end{align}\] be two singleton reduxes with unique common witnesses \(c_i\) and \(c_j\) respectively. Using 8, we get that the set \(G_i \cup \{(\alpha_i \cdots \alpha_k\alpha_0 \cdots \alpha_{i-1}, \beta_i \cdots \beta_k\alpha_0 \cdots \beta_{i-1})\}\) has a unique common witness, say \(z_i\). Moreover, by construction, \(z_i\) is also the unique common witness of the pairs \((u_i,v_i)\) used in the canonical pair from 9 and \((\alpha_i \cdots \alpha_k\alpha_0 \cdots \alpha_{i-1}, \beta_i \cdots \beta_k\beta_0 \cdots \beta_{i-1})\). Analogously, let \(z_j\) be the unique common witness of the set \(G_j \cup \{(\alpha_j \cdots \alpha_k\alpha_0 \cdots \alpha_{j-1}, \beta_j \cdots \beta_k\alpha_0 \cdots \beta_{j-1})\}\) and \(\{(u_j,v_j),(\alpha_j \cdots \alpha_k\alpha_0 \cdots \alpha_{j-1}, \beta_j \cdots \beta_k\alpha_0 \cdots \beta_{j-1})\}\) where \((u_j,v_j)\) is from 9. From 12, \(z_i=w_i\) and \(z_j =w_j\). WLOG assume that \(i < j\). There are four cases depending on whether \(w_i\) and \(w_j\) is an inner or outer witness.

• When \(w_i\) and \(w_j\) are inner witnesses: By 12, \(w_j = (\alpha_i \cdots \alpha_{j-1})^{-1}w_i\beta_i \cdots \beta_{j-1}\). By 8, \(c_i = [\alpha_0 \cdots \alpha_{i-1}w_i,\beta_0 \cdots \beta_{i-1}]_R\) and \(c_j = [\alpha_0 \cdots \alpha_{j-1}w_j,\beta_0 \cdots \beta_{j-1}]_R\). Assume that \(c_j\) is a common inner witness. We show that \(c_i=c_j\) and it is also an inner witness. \[\begin{align} c_j &= [\alpha_0 \cdots \alpha_{j-1}w_j,\beta_0 \cdots \beta_{j-1}]_R\\ &=\alpha_0 \cdots \alpha_{j-1}w_j(\beta_0 \cdots \beta_{j-1})^{-1} &&\text{(By \Cref{g1monomialwitness})}\\ &= \alpha_0 \cdots \alpha_{j-1}(\alpha_i \cdots \alpha_{j-1})^{-1}w_i\beta_i \cdots \beta_{j-1}(\beta_0 \cdots \beta_{j-1})^{-1} && \text{ (Subs. w_j) }\\ &= \alpha_0 \cdots \alpha_{i-1}w_i(\beta_0 \cdots \beta_{i-1})^{-1} && \text{ (Simplifying) }\\ &= [\alpha_0 \cdots \alpha_{i-1}w_i,\beta_0 \cdots \beta_{i-1}]_R\\ &= c_i \end{align}\] We also deduce that \(c_i\) is also a common inner witness by 8. Similarly, we can show that when \(c_j\) is a common outer witness of \(M_j\), then \(c_i=c_j\) is also a common outer witness of \(M_i\).

• When \(w_i\) and \(w_j\) is a unique common outer witness: the case the similar to above.

• When \(w_i\) is a unique common inner witness and \(w_j\) is a unique common outer witness: By 12, \(w_j = (w_i\beta_i \cdots \beta_{j-1})^{-1}\alpha_i \cdots \alpha_{j-1}\) . By 8, \(c_i = [\alpha_0 \cdots \alpha_{i-1}w_i,\beta_0 \cdots \beta_{i-1}]_R\) and \(c_j = [\alpha_0 \cdots \alpha_{j-1},\beta_0 \cdots \beta_{j-1}w_j]_R\). Assume that \(c_j\) is a common inner witness. We show that \(c_i=c_j\) and it is also an inner witness. \[\begin{align} c_j &= [\alpha_0 \cdots \alpha_{j-1},\beta_0 \cdots \beta_{j-1}w_j]_R\\ &=\alpha_0 \cdots \alpha_{j-1}(\beta_0 \cdots \beta_{j-1}w_j)^{-1} &&\text{(By \Cref{g1monomialwitness})}\\ &=\alpha_0 \cdots \alpha_{j-1}(\beta_0 \cdots \beta_{j-1}(w_i\beta_i \cdots \beta_{j-1})^{-1}\alpha_i \cdots \alpha_{j-1})^{-1} && \text{ (Subs. w_j) }\\ &=\alpha_0 \cdots \alpha_{j-1}(\beta_0 \cdots \beta_{i-1}(w_i)^{-1}\alpha_i \cdots \alpha_{j-1})^{-1} && \text{ (Simplifying) }\\ &=\alpha_0 \cdots \alpha_{i-1}(\beta_0 \cdots \beta_{i-1}(w_i)^{-1})^{-1}\\ &=\alpha_0 \cdots \alpha_{i-1}w_i(\beta_0 \cdots \beta_{i-1})^{-1}\\ &=[\alpha_0 \cdots \alpha_{i-1}w_i,\beta_0 \cdots \beta_{i-1}]_R\\ &=c_i \end{align}\] We also deduce that \(c_i\) is also a common inner witness by 8. Similarly, we can show that when \(c_j\) is a common outer witness of \(M_j\), \(c_i=c_j\) is also a common outer witness of \(M_i\).

• When \(w_i\) is a unique common outer witness and \(w_j\) is a unique common inner witness: the case is similar to above.

 ◻

Proof of [prop:short]. Now we prove that \(M\) has a common witness. Let \(M_i\) for \(i\in [1,k]\) denote the singleton redux of \(M\) obtained from \(M\) by substituting all but \(G_i^*\) by \((\varepsilon,\varepsilon)\). Since \(M\) is conjugate, each of its singleton redux, \(M_i\) for \(i \in [1,k]\) is also conjugate. By 8, each \(M_i\) has a common witness.

Since the redux of \(M\) is nonempty, if a singleton redux has infinitely many common witnesses, then it is a subset of powers of the primitive root of the redux by 8[Thm7:3]. Hence, any witness for the primitive root of the redux is a witness for that singleton redux of \(M\). If all singleton reduxes have infinitely many witnesses, they are all subsets of powers of the primitive root. Hence, all of them share a common witness, and by 9 \(M\) has a common witness.

Otherwise assume that there exists a singleton redux with a unique common witness. By 14, if any two singleton reduxes have unique witnesses, then they are the same. Thus, all singleton reduxes with unique witnesses share a unique witness; Let it be \(z\). Since \(z\) is also a witness for the redux. By [samewitness], it is a witness for any power of the primitive root of the redux. Therefore, \(z\) is also a witness for all singleton reduxes with infinitely many witnesses by 8[Thm7:3]. Hence, \(z\) is a common witness of each singleton reduxes of \(M\). By virtue of 9, \(M\) has a common witness when \(p\) is short. ◻

Proof. There are three cases for a long cut \((p,q)\) in \((u,v)\):

1. The cut \(p\) in \(u\) ends in the second half of the block \(B_i\) for \(1 \leq i < k\).

2. The cut \(p\) in \(u\) ends after the block \(B_{i-1}\) and before the second half of the block \(B_i\) for \(1 < i \leq k\).

3. The cut \(p\) in \(u\) ends in the second half of the block \(B_k\).

Note that whenever the cut \(p\) in \(u\) ends in the first half of block \(B_1\), or ends after the block \(B_k\), either \(p\) or \(q\) is short. Since \(p\) and \(q\) are long, \(|p\beta_0| > |\alpha_0u_1^{j_1-1}| \geq|u_1^{j_1-1}| \geq 2k \cdot \max(C,\ell)\) (since \(j_1 > 2k \cdot \max(C,\ell)\)). Therefore \[\begin{align} \label{eq:124p124} |p| > 2k \cdot \max(C,\ell) - |\beta_0|. \end{align}\tag{24}\]

For \(i \in [1,k]\), let \(B_i^f\) and \(B_i^s\) represent the first and second halves of the block \(B_i\), respectively. Similarly, let \(B_i'^f\) and \(B_i'^s\) represent the first and second halves of the block \(B_i'\), respectively. Clearly, \(|B_i^f| = |B_i'^f|\) and \(|B_i^s| = |B_i'^s|\). Since \(|B_1| > 2k \cdot \max(C,\ell)\) \(|B_1^f|\), we have \(|B_1^s| \geq k \cdot max(C,\ell)\). Similarly, from ?? , we get that for each \(i \in [2,k]\), \[|B_1| + |B_2| + \cdots |B_{i-1}| + C \leq |B_i^f| = |B_i^s|\] \[\begin{align} u' &= \alpha_0\,\overbrace{u_1 \cdots }^{B_1^f} \overbrace{\cdots u_1}^{B_1^s}\alpha_1\overbrace{u_2 \cdots}^{B_2^f}\overbrace{\cdots u_2}^{B_2^s}\alpha_2 \cdots \overbrace{u_k \cdots}^{B_k^f}\overbrace{\cdots u_k}^{B_k^s}\alpha_k \\ v' &= \beta_0\,\underbrace{v_1 \cdots }_{B_1'^f} \underbrace{\cdots v_1}_{B_1'^s} \beta_1 \underbrace{v_2 \cdots}_{B_2'^f}\underbrace{\cdots v_2}_{B_2'^s} \beta_2 \, \cdots \underbrace{v_k \cdots}_{B_k'^f}\underbrace{\cdots v_k}_{B_k'^s} \beta_k \end{align}\] We now show that, in all the above cases for long cut, ?? holds.

• When the cut \(p\) in \(u\) ends in \(B_i^s\) for \(1 \leq i < k\):

  \[\begin{align} u &= \overbrace{\alpha_0 \cdots B_i^f B_i^s}^{p} \alpha_i \cdots B_{k}\alpha_k\\ v &= \beta_0 \cdots {B_i'^f}{B_i'^s} \beta_i \cdots {B_k'^f}\underbrace{B_k'^s\beta_k}_{p} \end{align}\]

  Since \(|p| < |\alpha_0B_1 \cdots \alpha_{i-1}B_i| < |B_1| + \cdots + |B_{i}| + C < |B_k'^s|\), \(p\) in \(v\) is matched/contained in \(B_k'^s\beta_k\). The length of each block \(B_j\) for \(j \in [1,i]\) in \(u\) is at least \(\ell\). Therefore, by virtue of 5, \(\rho_{u_j} \sim \rho_{v_k}\). Hence, for all \(j \in [1,i]\), \[\label{eqcase1:1} \rho_{v_j} \sim \rho_{u_j} \sim \rho_{v_k} \sim \rho_{u_k}.\tag{25}\] Now, on matching the suffixes of \(q\) in \(u\) and \(v\), we get that a prefix of \(B_k\) of length \(|p(\beta_k)^{-1}| - |\alpha_k|\) matches with suffix of \(B_{k-1}'\beta_{k-1}\). Hence, there exists a common factor between blocks \(B_k\) and \(B_{k-1}'\) of length atleast \[\begin{align} |p(\beta_k)^{-1}| - |\alpha_k| - |\beta_{k-1}| &= |p| - |\beta_k|-|\alpha_k| - |\beta_{k-1}| \\ &\geq 2k \cdot \max(C,\ell) - |\beta_0|- |\beta_k|-|\alpha_k| - |\beta_{k-1}| && (\text{By \Cref{eq:124p124}})\\ &\geq 2k \cdot \max(C,\ell) - 2C\\ &\geq 2(k-1) \cdot \max(C,\ell) \\ &> \ell. \end{align}\] By 5, we get that \(\rho_{v_k} \sim \rho_{u_k} \sim \rho_{v_{k-1}} \sim \rho_{u_{k-1}}\). Continuing inductively, for all \(j \in [i+1,k]\), we get that there exists a common factor between blocks \(B_j\) and \(B_{j-1}'\) of length atleast \[\begin{align} |p(\beta_k)^{-1}| - \sum_{n \in [j, \ldots, k]} |\alpha_n| - \sum_{n \in [j-1, \ldots, k-1]}|\beta_{n}| &=|p| -|\beta_k|- \sum_{n \in [j, \ldots, k]} |\alpha_n| - \sum_{n \in [j-1, k-1]}|\beta_{n}| \\ &\geq 2k \cdot \max(C,\ell) - 2C \\ &\geq 2(k-1) \cdot \max(C,\ell) \\ &> \ell. \end{align}\] Hence, for \(j \in [i+1,k]\), by 5, we deduce that \[\label{eq:case1:2} \rho_{u_k} \sim \rho_{v_{k-1}} \sim \rho_{u_{k-1}} \cdots \sim \rho_{v_{i+1}} \sim \rho_{u_{i+1}}.\tag{26}\] By combining Equations 25 and 26 , we get that ?? holds.

• When the cut \(p\) in \(u\) ends after the block \(B_{i-1}\) and before the block \(B_i^s\) for some \(1 < i \leq k\):

  \[\begin{align} u &= \overbrace{\alpha_0 \cdots{B_{i-1}}\alpha_{i-1}{B_i^f}}^{p}\overbrace{{B_i^s} \alpha_i\cdots \alpha_k}^{q} \\ v &= \beta_0 \cdots {B_{i-1}'} \beta_{i-1} {B_i'^f}{B_i'^s} \beta_i \cdots \beta_k \end{align}\]

  In this case, while comparing the prefixes of \(q\) in \(u\) and \(v\), since \(|B_i^f|,|B_i^s| > |B_1| + \cdots |B_{i-1}| + C = |B_1'| + \cdots |B_{i-1}'| + C\), the prefix \(\beta_0 B_1' \cdots B_{i-1}'\beta_{i-1}\) of \(q\) in \(v\) is matched within the block \(B_i\). Since length of each block \(B_j'\) for \(j \in [1,i-1]\) is at least \(\ell\), by virtue of 5, \(\rho_{v_j} \sim \rho_{u_i}\). Therefore, for all \(j \in [1,i-1]\) \[\label{eqcase3:1} \rho_{u_j} \sim \rho_{v_j} \sim \rho_{v_i} \sim \rho_{u_i}.\tag{27}\]

  On further matching \(q\) in \(v\) and \(u\) , there exists a suffix of the block \(B_i'\) of length at least \[\begin{align} |\beta_0 B_1' \cdots B_{i-1}'\beta_{i-1}B_i'| - |\alpha_{i-1}B_i| &= |\beta_0 B_1' \cdots B_{i-1}'\beta_{i-1}| - |\alpha_{i-1}| \\ &\geq |B_1'| - |\alpha_{i-1}| &&(\text{Since i \geq 2})\\ &\geq 2k\max(C,\ell) - |\alpha_{i-1}| \end{align}\] to match with \(\alpha_iB_{i+1}\). Hence, \(B_i'\) and \(B_{i+1}\) share a common factor of length atleast \[\begin{align} 2k\max(C,\ell) - |\alpha_{i-1}| - |\alpha_{i}| &\geq 2k\max(C,\ell) - C \\ &\geq 2(k-1)\max(C,\ell)\\ &> \ell. \end{align}\] From 5, we get that \(\rho_{u_i} \sim \rho_{v_i} \sim \rho_{u_{i+1}} \sim \rho_{v_{i+1}}\).

  Continuing inductively, for all \(j \in [i, k-1]\), we get that blocks \(B_j'\) and \(B_{j+1}\) share a common factor of length atleast \[2k \max(C,\ell) - \sum_{n \in [i-1, j]}|\alpha_n| - \sum_{n \in [i, j-1]}|\beta_{n}| \geq 2(k-1) \cdot \max(C,\ell) > \ell.\]

  From 5, we get that \(\rho_{v_j} \sim \rho_{u_{j+1}}\) for \(j \in [i, k-1]\). By transitivity of conjugacy, we get \[\label{eqcase3:2} \rho_{u_i} \sim \rho_{v_i} \sim \rho_{v_{i+1}} \sim \rho_{v_{i+1}} \sim \cdots \sim \rho_{u_k} \sim \rho_{v_k}.\tag{28}\] Combining Equations 27 and 28 , we get that ?? holds.

• The cut \(p\) in \(u\) ends within \(B_k^s\): \[\begin{align} u &= \overbrace{\alpha_0\,{B_1^f} {B_1^s}\alpha_1{B_2^f}{B_2^s}\alpha_2 \cdots {B_k^f}{B_k^s}}^{p}\overbrace{\alpha_k^{\phantom{f}}}^{q} \\ v &= \beta_0\,{B_1'^f} {B_1'^s} \beta_1 {B_2'^f}{B_2'^s} \beta_2 \, \cdots{B_k'^f}{B_k'^s} \beta_k \end{align}\]

  Since \(q\) is not short, \(|q\alpha_0| > |\beta_0v_1^{j_1-1}| \geq |v_1^{j_1-1}| \geq 2k\max(C,\ell)\) (since \(j_1 > 2k \cdot \max(C,\ell))\). Also, by assumption, \(|q| \leq |B_k'^s\alpha_k|\). While matching the \(q\) in \(u\) and \(v\), there exists a maximal \(i \in [1,k-1]\), such that \(\beta_0B_1' \cdots B_i'^f\) is a proper prefix of \(q\) in \(v\). Since \(|B_j'^f|\) for \(j \in [1,i]\) is atleast \(\geq k\max(C,\ell) > \ell\), and \(|B_j'^f|\) is matched within the block \(B_k\), by virtue of 5, \(\rho_{v_j} \sim \rho_{u_k}\). Therefore, for all \(j \in [1,i]\) \[\label{eqcase4:1} \rho_{u_j} \sim \rho_{v_j} \sim \rho_{v_k} \sim \rho_{u_k}.\tag{29}\]

  If \(i = k-1\), then we are done. Otherwise, assume that \(i \leq k-2\). Now, matching the prefix of \(p\) in \(u\) and \(v\), we get that a suffix of block \(B_{i+1}\) of length atleast \[\begin{align} |\alpha_0 \cdots B_i\alpha_iB_{i+1}| - |q^{-1}(\beta_0B_1' \cdots B_{i+1}'\beta_{i+1})| &= |q| - (|\alpha_0 \cdots \alpha_i| - |\beta_0 \cdots \beta_{i+1}|) \\ &\geq |q|-C \\ &\geq 2k\max(C,\ell) \\ &> \ell \end{align}\] matches with block \(B_{i+2}'\), and hence \(\rho_{u_{i+1}} \sim \rho_{v_{i+2}}\) by 5. Continuing inductively, we get for \(j \in [(i+1),(k-1)]\), block \(B_{j}\) and \(B_{j+1}'\) shares a common factor of length atleast \(2(k-1)\max(C,\ell) > \ell\), and by 5, \[\label{eqcase4:2} \rho_{v_j} \sim \rho_{u_{j}} \sim \rho_{v_{j+1}} \sim \rho_{u_{j+1}}.\tag{30}\] Combining Equations 29 and 30 , we get that ?? holds.

 ◻

Proof. By virtue of Item 3 of 8, if there exists \(G_i^*\), for some \(i\in[1,k]\), with a unique common witness, then every differentially pumped pair \((u,v)\) constructed satisfies \(\rho_{u_j} \not \sim \rho_{u_{\ell}}\) for some \(j,\ell \in [1,k], j \neq \ell\). Therefore, if a a differentially-pumped pair in \(M\) has a long cut, each Kleene closure \(G_i^*\) has infinitely many witnesses, and therefore \(G_i^* \subseteq (\rho_i,\rho_i')^*\) for some primitive pair \((\rho_i,\rho_i')\). Since by 15, \(\rho_i \sim \rho_j\) for all \(i,j\in[1,k]\) the claim follows. ◻

Proof. In the definition of \((u,v)\), recall that \(\ell = 2\cdot \max\{|u_i| \mid i \in [1,k]\} \geq 2\cdot d\).

Firstly, we prove that in the long cut \((p,q)\) of \((u,v)\) there is at most one pair \((\bar{\alpha})_i\) and \((\bar{\beta})_j\) for some \(i,j \in [1,k]\) that are \(d\)-near.

Assume there exist \(i,{i'}, j, {j'} \in [1,k]\) such that \((\bar{\alpha})_i\) and \((\bar{\beta})_j\), as well as, \((\bar{\alpha})_{i'}\) and \((\bar{\beta})_{j'}\) are \(d\)-near. By definition of the pair \((u,v)\), we have \(i=i'\) if and only if \(j=j'\) since a word in \(\bar{\alpha}\) can be \(d\)-near with at most one word in \(\bar{\beta}\) and vice-versa. Hence, assume for the sake of contradiction that \(i \neq i'\) and \(j \neq j'\).

We claim that \(i \neq j\) and \(i' \neq j'\). For the sake of contradiction assume that \(i=j\), i.e., \((\bar{\alpha})_i\) and \((\bar{\beta})_i\) are \(d\)-near. We do a case analysis. When \(i=k\), i.e., when \((\bar{\alpha})_k = \alpha_k\alpha_0\) and \((\bar{\beta})_k = \beta_k\beta_0\) are \(d\)-near then either \(p\) or \(q\) is short since \(\min(|p|,|q|) \leq \max(|\alpha_k\alpha_0|, |\beta_k\beta_0|) + d\). Therefore, \[\begin{align} \min(|p\beta_0|,|q\alpha_0|) &\leq 2C +d \\ &< 2C + \ell\\ &<2k\cdot \max(C,\ell) &&\text{(Since k \geq 2)} \end{align}\]

contradicting the assumption that the cut is long. Next assume that \(i \neq k\). In this case, note that \((\bar{\alpha})_i = \alpha_i\) and \((\bar{\beta})_i = \beta_i\). Since \(\alpha_i\) and \(\beta_i\) are \(d\)-near, matching the suffix \(\alpha_iB_{i+1}\alpha_{i+1} \cdots \alpha_{k-1}B_k\alpha_k\) with \(\beta_iB'_{i+1}\beta_{i+1} \cdots \beta_{k-1}B'_k\beta_k\), we get a suffix of length \(d + \sum_{l=i}^{k}|\alpha_l| - \sum_{l=i}^{k}|\beta_l| \leq d+ C\) either in \(u\) or \(v\) to be matched with the prefix of the other. Thus, \(\min(|p|,|q|) \leq C + d\), and hence \(\min(|p\beta_0|,|q\alpha_0|) \leq 2C + d < 2k\cdot \max(C,\ell)\). Hence, either \(p\) or \(q\) is short, contradicting the assumption that the cut is long. Therefore, we conclude that \(i \neq j\). By a similar argument \(i' \neq j'\).

WLOG we can assume that \(i <i'\). We have two cases: either \(j<j'\) or \(j'<j\). Assume \(j <j'\). Since \((\bar{\alpha})_i\) and \((\bar{\beta})_j\), as well as, \((\bar{\alpha})_{i'}\) and \((\bar{\beta})_{j'}\) are \(d\)-near, by matching the infix of \(u\) and \(v\) defined by \((\bar{\alpha})_i, (\bar{\alpha})_{i'}\) and \((\bar{\beta})_j, (\bar{\beta})_{j'}\), namely \((\bar{\alpha})_iB_{i+1} \cdots B_{i'}(\bar{\alpha})_{i'}\) and \((\bar{\beta})_jB_{j+1}' \cdots B'_{j'}(\bar{\beta})_{j'}\), we note that \[\label{ijeq} \left | \, |(\bar{\alpha})_iB_{i+1} \cdots B_{i'}(\bar{\alpha})_{i'}| - |(\bar{\beta})_jB'_{j+1} \cdots B'_{j'}(\bar{\beta})_{j'}| \, \right | \leq C + 2\cdot d\tag{32}\] If \(i' > j'\), then \(|B_{i'}| > 2 \cdot (|B'_1| + \cdots + |B'_{j'}| + C)\) by definition of pair \((u,v)\). Hence, \[\begin{align} \left | \, |(\bar{\alpha})_iB_{i+1} \cdots B_{i'}(\bar{\alpha})_{i'}| - |(\bar{\beta})_jB'_{j+1} \cdots B'_{j'}(\bar{\beta})_{j'}| \, \right | \geq 1/2\cdot |B_{i'}| > k\cdot \max(C,\ell) > C+2 \cdot d. \end{align}\] Therefore, contradicting 32 . Similarly, the case when \(j' > i'\) also contradicts 32 . Thus, the case of \(j < j'\) leads to a contradiction.

Next assume that \(j' <j\). Observe that \((\bar{\alpha})_iB_{i+1} \cdots B_{i'}(\bar{\alpha})_{i'}\) and \((\bar{\beta})_jB'_{j+1} \cdots B'_k(\bar{\beta})_k B'_1 \cdots B'_{j'}(\bar{\beta})_{j'}\) (or equivalently the factors \((\bar{\alpha})_{i'}B_{i'+1} \cdots B_k(\bar{\alpha})_k B_1 \cdots B_{i}(\bar{\alpha})_{i}\) and \((\bar{\beta})_{j'}B'_{j'+1} \cdots B'_{j}(\bar{\beta})_{j}\)) are the factors defined by \((\bar{\alpha})_i, (\bar{\alpha})_{i'}\) in \(u\) and \((\bar{\beta})_j, (\bar{\beta})_{j'}\) in \(v\)). Let \(d'=\left | \, |(\bar{\alpha})_iB_{i+1} \cdots B_{i'}(\bar{\alpha})_{i'}| - |(\bar{\beta})_jB'_{j+1} \cdots B'_k(\bar{\beta})_k B'_1 \cdots B'_{j'}(\bar{\beta})_{j'}|\, \right |\). Since \((\bar{\alpha})_i\) and \((\bar{\beta})_j\), as well as, \((\bar{\alpha})_{i'}\) and \((\bar{\beta})_{j'}\) are \(d\)-near, \[\label{i39jeq} d' \leq C + 2\cdot d.\tag{33}\] If \(i'\neq k\), then \(|B'_{k}| > 2 \cdot (|B_1| + \cdots + |B_{i'}| + C)\). Hence, \(d' \geq 1/2\cdot |B'_{k}| > C + 2\cdot d\). Therefore, contradicting 33 . The case when \(i' = k\) is symmetric to the above case by considering the factors \((\bar{\alpha})_k B_1 \cdots B_{i}(\bar{\alpha})_{i}\) and \((\bar{\beta})_{j'}B'_{j'+1} \cdots B'_{j}(\bar{\beta})_{j}\) defined by \((\bar{\alpha})_i, (\bar{\alpha})_{i'}\) in \(u\) and \((\bar{\beta})_j, (\bar{\beta})_{j'}\) in \(v\).

Therefore, there does not exist \(i,i',j,j' \in [1,k]\), \((i,j) \neq (i',j')\), such that \((\bar{\alpha})_i\) and \((\bar{\beta})_j\), as well as, \((\bar{\alpha})_i'\) and \((\bar{\beta})_j'\) are \(d\)-near, i.e., there exists at most one pair \((i,j)\) such that \((\bar{\alpha})_i\) and \((\bar{\beta})_j\) are \(d\)-near. Moreover, \(i \neq j\).

For some \(i \in [1,k]\), assume that \((\bar{\alpha})_i \in \bar{\alpha}\) is not \(d\)-near with any word in \(\bar{\beta}\). This implies that in the matching of \(u\) and \(v\) w.r.t. the cut \((p,q)\), the factor \(\rho_i (\bar{\alpha})_i \rho_{i+1}\) (with \(\rho_{i+1} = \rho_1\) when \(i=k\)) is matched within some block of \(\rho_j'^*\) for some \(j \in [1,k]\). Since \(\rho_i \sim \rho_{i+1} \sim \rho_j'\), it follows from [prop:iwredux] that \((\bar{\alpha})_i\) is an inner witness of \((\bar{\rho})_i = (\rho_i,\rho_{i+1})\). Similarly, for any \(i \in [1,k]\), if \((\bar{\beta})_i \in \bar{\beta}\) is not \(d\)-near with any word in \(\bar{\alpha}\), then \((\bar{\beta})_i\) is an inner witness of \((\bar{\rho'})_i = (\rho'_i,\rho'_{i+1})\) (with \(\rho'_{i+1} = \rho'_1\) when \(i=k\)). Hence, the claim is proved. ◻

Proof. Since by assumption \(\;\rho_\ell^{n}(\bar{\alpha})_\ell = (\bar{\alpha})_\ell\rho_{\ell+1}^{n}\) for all \(\ell \in [i,j]\) and \(\forall n\geq 0\), we have \[\begin{align} \rho_i^*(\bar{\alpha})_i \rho_{i+1}^*(\bar{\alpha})_{i+1}\cdots (\bar{\alpha})_{j-1}\rho^*_{j}(\bar{\alpha})_{j}\rho^*_{j+1} &=\rho_i^*(\bar{\alpha})_i \rho_{i+1}^*(\bar{\alpha})_{i+1}\cdots(\bar{\alpha})_{j-1}\rho^*_{j}(\bar{\alpha})_{j}\\ &=\rho_i^*(\bar{\alpha})_i \rho_{i+1}^*(\bar{\alpha})_{i+1}\cdots \rho^*_{j-1} (\bar{\alpha})_{j-1}(\bar{\alpha})_{j}\\ &=\rho_i^*(\bar{\alpha})_i \cdots (\bar{\alpha})_{j} && (\text{By induction on the interval [i,j]}) \end{align}\] By an analogous argument, \[\begin{align} \rho_i^*(\bar{\alpha})_i \rho_{i+1}^*(\bar{\alpha})_{i+1}\cdots (\bar{\alpha})_{j-1}\rho^*_{j}(\bar{\alpha})_{j}\rho^*_{j+1} &=(\bar{\alpha})_i \cdots (\bar{\alpha})_{j}\rho_{j+1}^*. \end{align}\] From the above, we infer that \((\bar{\alpha})_i \cdots (\bar{\alpha})_{j}\) is an inner witness of the pair \((\rho_i, \rho_{j+1})=(\mathit{fst}((\bar{\rho})_i),\mathit{snd}((\bar{\rho})_j)\).

Next assume that \(1 \leq j \leq i \leq k\) and \((\bar{\alpha})_\ell\) is an inner witness of \((\bar{\rho})_\ell = (\rho_{\ell},\rho_{\ell+1})\) (with \(\rho_{\ell+1}= \rho_1\) when \(\ell=k\)), for all \(\ell \in [i,k] \cup [1, j]\). By the above observation, \[\begin{align} \rho_i^*(\bar{\alpha})_i \rho_{i+1}\cdots (\bar{\alpha})_{k}\rho^*_{1} &=(\bar{\alpha})_i \cdots (\bar{\alpha})_{k}\rho_{1}^*\\ &=\rho_{i}^*(\bar{\alpha})_i \cdots (\bar{\alpha})_{k}\label{eq:97} \end{align}\tag{34}\] \[\begin{align} \rho_1^*(\bar{\alpha})_1 \rho_{2}\cdots (\bar{\alpha})_{j}\rho^*_{j+1} &=(\bar{\alpha})_1 \cdots (\bar{\alpha})_{j}\rho_{j+1}^*\\ &=\rho_{1}^*(\bar{\alpha})_1 \cdots (\bar{\alpha})_{j} \label{eq:99} \end{align}\tag{35}\] From the above equations, we get that \[\begin{align} \rho_i^*(\bar{\alpha})_i \rho_{i+1}\cdots (\bar{\alpha})_{k}\rho^*_{1}(\bar{\alpha})_1 \rho_{2}\cdots (\bar{\alpha})_{j}\rho^*_{j+1} &= \rho_i^*(\bar{\alpha})_i \rho_{i+1}\cdots (\bar{\alpha})_{k}\rho^*_{1}(\bar{\alpha})_1 \cdots (\bar{\alpha})_{j} &&\text{(Using \Cref{eq:99})}\\ &= \rho_{i}^*(\bar{\alpha})_i \cdots (\bar{\alpha})_{k}(\bar{\alpha})_1 \cdots (\bar{\alpha})_{j} &&\text{(Using \Cref{eq:97})}\\ &=(\bar{\alpha})_i \cdots (\bar{\alpha})_{k}(\bar{\alpha})_1 \cdots (\bar{\alpha})_{j}\rho_{j+1}^* &&\text{(Similarly)} \end{align}\]

From the above, we infer that \((\bar{\alpha})_i \cdots (\bar{\alpha})_{k}(\bar{\alpha})_1 \cdots (\bar{\alpha})_{j}\) is an inner-witness of the pair \((\rho_i, \rho_{j+1})=(\mathit{fst}((\bar{\rho})_i),\mathit{snd}((\bar{\rho})_j)\). ◻

Proof of [prop:long]. From 4, we get that \(M \subseteq (\alpha_0,\beta_0)(\rho_1,\rho_1')^* (\alpha_{1},\beta_{1}) \cdots (\rho_k,\rho_k')^*(\alpha_k,\beta_k)\) for some \(\rho_1 \sim \rho_1' \sim \cdots \rho_k \sim \rho_k'\). By virtue of 16, there are two cases.

Case 1: When the word \((\bar{\alpha})_i\) is an inner witness of \((\bar{\rho})_i\) for each \(i \in [1,k]\). Notice that by 17, \((\bar{\alpha})_1 \cdots (\bar{\alpha})_{k}\) is an inner witness of \((\rho_1,\rho_1)\), and hence \((\bar{\alpha})_1 \cdots (\bar{\alpha})_{k} \in \rho_1^*\) . We show that \(\mathit{fst}(M)\) is a cyclic shift of \(\rho_1^*\) as follows. \[\begin{align} \mathit{fst}(M) &\subseteq \alpha_0\rho_1^*\alpha_1\rho^*_2\alpha_2 \cdots \rho^*_k\alpha_k\\ &\sim \rho_1^*\alpha_1\rho^*_2\alpha_2 \cdots \rho^*_k\alpha_k\alpha_0\\ &= \rho_1^*(\bar{\alpha})_1\rho^*_2(\bar{\alpha})_2 \cdots \rho^*_k(\bar{\alpha})_k\\ &= \rho_1^*(\bar{\alpha})_1(\bar{\alpha})_2 \cdots(\bar{\alpha})_k &&\text{(By \Cref{interval:associative})}\\ &\subseteq \rho_1^*. &&\text{(Since (\bar{\alpha})_1 \cdots (\bar{\alpha})_{k} is an i.w of (\rho_1,\rho_1)) } \end{align}\] By a similar argument, we show that \(\mathit{snd}(M) \mathrel{\mathpalette\subset@sim\relax}\rho_1'^*\). Therefore, since \(M\) is conjugate, \(M \mathrel{\mathpalette\subset@sim\relax}(\rho_1,\rho_1')^*\) and hence has a common witness. Moreover, since \(\rho_1' \sim \rho_1\), \(\mathit{fst}(M)\) and \(\mathit{snd}(M)\) are cyclic shifts of \(\rho_1^*\).

Case 2: When there exists a unique pair \((i,j)\), \(i\neq j\in[1,k]\), such that for all \(l\in [1,k]\setminus \{i\}\), \((\bar{\alpha})_l\) is an inner witness of the pair \((\bar{\varrho})_l\), and for all \(l \in [1,k]\setminus \{j\}\), \((\bar{\beta})_l\) is an inner witness of the pair \((\bar{\varrho}')_l\). \[\begin{align} \mathit{fst}(M) &\subseteq \alpha_0\rho_1^*\alpha_1\rho^*_2\alpha_2 \cdots \rho^*_k\alpha_k\\ &\sim \rho_1^*\alpha_1\rho^*_2\alpha_2 \cdots \rho^*_k\alpha_k\alpha_0\\ &= \rho_1^*(\bar{\alpha})_1\rho^*_2(\bar{\alpha})_2 \cdots \rho^*_k(\bar{\alpha})_k\\ &\sim (\bar{\alpha})_i\rho_{i+1}^* \cdots (\bar{\alpha})_k \rho_{1}^* (\bar{\alpha})_1 \cdots (\bar{\alpha})_{i-1}\rho^*_i\\ &= (\bar{\alpha})_i \cdots (\bar{\alpha})_k(\bar{\alpha})_1 \cdots (\bar{\alpha})_{i-1}\rho^*_i &&\text{(By \Cref{interval:associative})} \end{align}\]

Therefore, we have \(\mathit{fst}(M) \sim \mathit{snd}(M) \mathrel{\mathpalette\subset@sim\relax}(\bar{\alpha})_i \cdots (\bar{\alpha})_k(\bar{\alpha})_1 \cdots (\bar{\alpha})_{i-1}(\rho_i)^*\). By an analogous argument, \(\mathit{fst}(M) \sim \mathit{snd}(M) \mathrel{\mathpalette\subset@sim\relax}(\bar{\beta})_j \cdots (\bar{\beta})_k(\bar{\beta})_1 \cdots (\bar{\beta})_{j-1}(\rho_j')^*\), and the claim follows. ◻

Proof. Let \(z\) be a common inner witness. Therefore, \(z = (x_1y_1)^{n_1}x_1 = (x_2y_2)^{n_2}x_2\) for some \(n_1,n_2 \geq 0\) where \((x_i,y_i)\) is a cut of the primitive pair \((u_i,v_i)\) for \(i \in \{1,2\}\). We claim either \(n_1\) or \(n_2\) is less than \(2\). Suppose not, i.e., \(n_1 \geq 2\) and \(n_2 \geq 2\). Thus \(u_1^\omega\) and \(u_2^\omega\) share a common prefix of length at least \(|u_1| + |u_2|\). From 4, they have the same primitive root. It implies that \(x_1y_1 = x_2y_2\) since \(u_1\) and \(u_2\) are primitive words. Since \((x_1y_1)^{n_1}x_1 = (x_2y_2)^{n_2}x_2\), \(x_1y_1 = x_2y_2\) and \(|x_1|,|x_2| < |x_1y_1|\), we obtain \(n_1 = n_2\), and hence, \(x_1 = x_2\). This implies \(y_1 = y_2\) and hence, \(y_1x_1 = y_2x_2\). Both \((u_1,v_1)\) and \((u_2,v_2)\) are the same word; thus, they have infinitely many common witnesses, that is a contradiction. Hence \(|z| \leq 2 \cdot \mathit{max}\{|u_1|,|u_2|\}\).

The case for common outer witness is symmetric. ◻

Proof. Since the common witness for a set and its primitive root are the same ([samewitnessext]), we compute the witness set for the primitive roots of the given two conjugate pairs. We can compute the primitive roots in linear time by [computeroot]. Let \(G = \{(u_1,v_1), (u_2,v_2)\}\) be the set of primitive roots of the given conjugate pairs and let \((x_i,y_i)\) be the cut of \((u_i,v_i)\) for \(i \in \{1,2\}\). The cut of the primitive pair \((u_i,v_i)\) can be computed in linear time by finding the first nontrivial occurrence of \(v_i\) in \(u_iu_i\).

One of the following possibilities holds true for \(G\): it has no common witness, a unique common witness, or infinitely many common witnesses. The following algorithm outlines the computation of the witness set of \(G\):

1. Check if the primitive pairs are identical, i.e., verify if \(u_1 = u_2\) and \(v_1 = v_2\). If yes, then \(G\) has infinitely many common witnesses by [infmanycwcorr]. The witness is finitely represented by the primitive pair \((u_1,v_1)\). This step takes linear time w.r.t. the length of the primitive pairs.

2. If the pairs are not identical, then check if \(G\) has a unique common witness using [witlengthG] as follows: WLOG assume that \(|u_1| > |u_2|\). According to [witlengthG], if a unique common witness exists for \(G\), its length is at most \(2 \cdot \max(|u_1|,|u_2|) = 2 \cdot |u_1|\). Thus, it suffices to check whether \((x_1y_1)^\omega\) and \((x_2y_2)^\omega\) share equal prefixes of length \(|x_1|\) or \(|x_1y_1x_1|\), that also end in \(x_2\). If it is satisfied, then \(G\) has a unique common witness. This step can be performed in linear time w.r.t. the length of the primitive pairs.

3. If none of the above holds, then \(G\) has no common witness.

The overall complexity of the algorithm is linear w.r.t the length of the primitive roots of the given pairs. ◻

Proof. If redux of \(M\) is empty, then the witness set of \(M\) is same as the witness set of \(E\) by 6. Now assume that \(M\) has a nonempty redux. From 8, \(M\) has a common witness iff \(E \cup \{(\alpha_1\alpha_0,\beta_1\beta_0)\}\) has a common witness. The common witness of \(M\) is computed from the common witness of \(E\) and \((\alpha_1\alpha_0,\beta_1\beta_0)\).

The idea is to check if a common witness exists for \(E \cup \{(\alpha_1\alpha_0,\beta_1\beta_0)\}\) using 7. If it exists, using that we compute the common witness for \(M\). There are two possibilities for common witnesses of \(E\):

1. \(E\) has a unique common inner (resp. outer) witness \(z\). By [gmonomialcut:2] of 7, it suffices to check if \(z\) is a common inner (resp. outer) witness of \((\alpha_1\alpha_0,\beta_1\beta_0)\). This can be checked in \(\mathcal{O}(m+n)\) time using 1. If so, \(z\) is the common witness of \(E \cup \{(\alpha_1\alpha_0,\beta_1\beta_0)\}\). Now compute the common witness of \(M\) using 8[Thm7:1] (resp. 8[Thm7:2]). This can be computed in \(\mathcal{O}(m+n)\) time. Otherwise, \(E \cup \{(\alpha_1\alpha_0,\beta_1\beta_0)\}\) has no common witness and hence, \(M\) has no common witness by 8.

2. \(E\) has infinitely many common witnesses. In this case, the witnesses of \(E\) are the same as that of its primitive root, say \((\rho,\rho^\prime)\). From [gmonomialcut:1] of 7, it suffices to check if \((\rho,\rho^\prime)\) and \((\alpha_1\alpha_0,\beta_1\beta_0)\) has a common witness. For this, first check if the primitive root of \((\alpha_1\alpha_0,\beta_1\beta_0)\) is equal to \((\rho,\rho^\prime)\). This step takes time \(\mathcal{O}(m +n)\). We have two cases:

   1. If \((\alpha_1\alpha_0,\beta_1\beta_0)\) have same primitive root as that of \(E\), then \(E\) and \((\alpha_1\alpha_0,\beta_1\beta_0)\) have infinitely many common witnesses by [infmanycwcorr]. In this case, \(M\) is a set of powers of the primitive root of the redux by 8[Thm7:3]. Thus \(M\) has infinitely many witnesses. Compute the primitive root of its redux using [computeroot]. This step takes \(\mathcal{O}(m)\) time.

   2. Otherwise, compute the unique common witness of \((\rho,\rho^\prime)\) and \((\alpha_1\alpha_0,\beta_1\beta_0)\) if it exists using [existswitness]. If so, we are back to Case 1; else \(M\) has no common witness. This step takes \(\mathcal{O}(m+n)\) time.

 ◻

Proof. From 9, the witness set of \(M\) is the intersection of the witness sets of its singleton reduxes. Check if each singleton redux of \(M\) has a common witness and compute it using 18. This step takes \(\mathcal{O}(m \cdot (m+n))\). If there is a singleton redux with no common witness, then \(M\) has no common witness by 9.

Assume that \(M\) has a nonempty redux. The algorithm is as follows. Firstly, check if the redux of \(M\) is conjugate using [isconjugate] (in time \(\mathcal{O}(m)\)). If yes, then compute the primitive root of the redux, say \((\rho_m,\rho_m^\prime)\), using [computeroot] (in time \(\mathcal{O}(m)\)). Otherwise, \(M\) has no common witness. There are two cases depending on whether all singleton redux has infinitely many witnesses.

1. If all the singleton reduxes have infinitely many witnesses, then \(M\) is a set of powers of the primitive root of the redux \((\rho_m,\rho_m^\prime)\) by 8[Thm7:3]. Thus, \(M\) has infinitely many common witnesses.

2. If there exists a singleton redux with a unique common witness, say \(z\), then for all other singleton reduxes of \(M\) with a unique witness \(z^\prime\), check if \(z = z^\prime\) (for all other singleton reduxes \(z\) is already a witness by virtue of being a witness of the redux of \(M\)). If so, \(z\) is the unique common witness of \(M\); otherwise \(M\) has no common witness.

This takes \(\mathcal{O}(mn + m)\) time. Consider the case where the redux of \(M\) is empty. Let \(M\) be of the form \(E_1^*E_2^* \cdots E_k^*\). We iterate over \(i \in \{1,\ldots, k-1\}\).

1. If both \(E_i\) and \(E_{i+1}\) has infinitely many witnesses, then the witness set of \(E_i^*\) and \(E_{i+1}^*\) is finitely represented by their primitive roots. Check if the primitive roots are the same. If yes, continue the procedure for \(i=i+1\). Otherwise, check and compute the common witness, say \(z\), of the primitive roots if exists using [existswitness] (in time \(\mathcal{O}(n)\)). If not, then \(M\) has no common witness. Otherwise, check if \(z\) is a common witness of all singleton reduxes \(E_{i+2}^*, \ldots, E_k^*\) (This can be done in \(\mathcal{O}(n)\) for each singleton redux — If a singleton redux has a unique witness then check if it is equal to \(z\). Otherwise, if it has infinitely many witness, then it is represented by a primitive root. It suffices to check if \(z\) is a witness of that primitive root).

2. If either one of \(E_i\) and \(E_{i+1}\) has a unique witness, say \(z\), then check if \(z\) is a common witness of all singleton reduxes \(E_{i+2}^*, \ldots, E_k^*\) .

This step takes \(\mathcal{O}(mn + n)\) time. Overall, it takes \(\mathcal{O}(m \cdot (m+n))\). ◻

Proof. Let \(E\) be a rational expression over the monoid \(\mathbf{M}\). We assume that the rational expression \(E\) is given as a tree \(e\). We take the size of \(e\), denoted as \(|e|\), to be the number of nodes in the tree. We inductively define a tree \(e’\) that has the same language as the sumfree normal form of the expression \(E\) and furthermore, as shown in 6, it is in the shape of a right-comb with the internal nodes of the spine labelled with \(+\)’s (and the leaf of the spine is labelled with \(\emptyset\)) and the pendant left subtrees attached to the spine are sumfree. We call \(e'\) as the SNF tree of \(e\).

We obtain an equivalent sumfree normal form expression and its expression tree \(e'\) by induction on the structure of \(E\). We prove the following invariant along with the construction of \(e’\).

The following definition is used in the analysis below. Let \(N(e’)\) denote the number of summands in \(e’\), i.e., \(N(e’)\) is the number of nodes in the spine of the comb, or equivalently, 1 more than the number of nodes labelled with \(‘+’\) in \(e’\). Hence \(N(e’) \leq |e’|\).

Base Case

When \(E\) is \(\emptyset\) or \(m\in M\), then \(E\) is already sumfree. The tree \(e\) corresponds to a tree with a single node. We take \(e’\) to be the tree with 3 nodes in SNF with the left subtree of the root being \(e\). Hence \(|e’| = 3\) and the claim holds.

Inductive Case

Assume that \(G\) and \(H\) are rational expressions with expression trees \(g\) and \(h\) respectively. Let \(g’\) and \(h’\) denote their SNF trees. By induction hypothesis, \(G \equiv \alpha_1 + \cdots + \alpha_k\) and \(F \equiv \beta_1 + \cdots + \beta_\ell\) such that \(\alpha_i, \beta_j\), \(1\leq i \leq k\), \(1 \leq j \leq \ell\), are sumfree expressions. Also, \(|g’| \leq 2^{2|g|}\) and \(|h’| \leq 2^{2|h|}\).

1. If \(E = G + H\), then by substituting for \(G\) and \(H\), we get an equivalent expression of the desired form. This step takes constant time. To obtain \(e’\) we replace the leaf of the spine of \(g’\) with the root of \(h’\). Clearly, \[\begin{align} |e’| &= |g’| + |h’| - 1\\ &\leq 2^{2|g|} + 2^{2|h|} - 1\\ &\leq 2^{2(|g|+|h|+1)}\\ &= 2^{2|e|}. \end{align}\]

2. If \(E = G\cdot H\), then by substituting \(G\) and \(H\) we get \(E \equiv (\alpha_1 + \cdots + \alpha_k) \cdot (\beta_1 + \cdots + \beta_\ell)\). Distributing the monoid operation over the union, we get \(E \equiv (\alpha_1\beta_1 + \cdots + \alpha_1\beta_\ell) + \cdots + (\alpha_k\beta_1 + \cdots + \alpha_k\beta_\ell)\), that is in the required form. This step takes time quadratic in the maximum among the length of the SNF expressions \(G\) and \(H\).

   Assume there are \(p\)-many (resp. \(q\)-many) pendant subtrees attached to the spine of \(g’\) (resp. \(h’\)). The tree \(e’\) is a right-comb with \(pq\)-many pendant subtrees where each subtree is obtained by the pairwise concatenation of pendant subtrees from \(g’\) and \(h’\) respectively. Clearly, \(N(e’) = N(g’)N(h’) - 1\). \[\begin{align} |e’| &\leq N(g’)N(h’) + |g’|N(h’) + |h’|N(g’) + N(g’)N(h’)\\ &\leq 4|g’||h’|\\ &\leq 4 \cdot 2^{2|g|}2^{2|h|}\\ &\leq 2^{2(|g| + |h| + 1)}\\ &= 2^{2|e|}. \end{align}\]

3. Finally, if \(E = G^*\), then by repeatedly applying the rational identity \((X+Y)^* = (X^* Y^*)^*\), where \(X,Y\) are rational expressions, we get \(E = G^* \equiv (\alpha_1 + \alpha_2 + \cdots + \alpha_k)^* = (\alpha_1^*\alpha_2^* \cdots \alpha_k^*)^*\). This step takes linear time w.r.t. the length of the SNF epression \(G\).

   We obtain the tree \(g’\) corresponding to \(g\), and construct a new tree \(h\) from \(g’\) as follows.

   • Add an intermediate node labelled with \(*\) between each pendant subtree and the spine of \(g’\).

   • Replace each \(+\) labelled nodes in the spine with concatenation.

   • Replace \(\emptyset\) in the leaf of spine with epsilon.

   • Add a new root node labelled with \(*\).

   Now, \(e’\) is obtained by attaching \(h\) as the left subtree of a right-comb in the desired form. Clearly \(N(e’) = 1\). \[\begin{align} |e’| &\leq |g’|+N(g’)+3\\ &\leq |g’|+|g’|+3\\ &\leq 2 \cdot 2^{2|g|}+3\\ &= 2^{2|g|+1}+3\\ &\leq 2 \cdot 2^{2|g|+1} &&\text{(Since |g| \geq 1, 2^{2|g|+1} \geq 8)}\\ &= 2^{2(|g|+1)}\\ &= 2^{2|e|} \end{align}\]

Hence proved that the upper bound on the size of the SNF expression is exponential in the size of the given expression.

Each step of constructing an SNF expression takes polynomial time in the length of its constituent SNF expressions. Therefore, any rational expression can be converted to an equivalent sumfree normal form in exponential time. ◻