Boone positive history reconstruction

We prove a stronger assertion: for freely reduced, possibly signed tape words $X,Y$, the equation $L{X}^{\mathrm{\#}}{q}_{j}YR=q$ forces $X,Y$ to be positive and $X{q}_{j}Y=q$ in $\mathrm{\Gamma }$. Freely reduce $L,R$, which does not change their elements. By [F1] their rule-letter counts have a common value $p$. We use strong induction on $p$, under the AC normal-form assumptions.

If $p=0$, the equation is $x^m{X}^{\mathrm{\#}}{q}_{j}Y{x}^n=q$ in $G_0=H\ast F(\bar{Q})$, since the base embeds. Unique reduced syllables give $q_j=q$, $x^m{X}^{\mathrm{\#}}=1$ and $Y{x}^n=1$. Applying $\rho$ shows the freely reduced tape words $X^{\mathrm{\#}},Y$ are empty. Infinite order of $x$ then gives $m=n=0$. Thus $X,Y$ are empty positive words and $X{q}_{j}Y=q$ literally, proving the initial case.

We first establish the tape sign test used at a pinch. Suppose $Z$ is a freely reduced signed tape word and $Z{x}^a\in T_1=⟨sx⟩$. Choose its reduced basis spelling $u$ in $sx$. Then $x^a{u}^{-1}Z=1$ in $H$. Expand $u^{-1}$ in tape stable letters and $x$. This expansion has no tape pinch: opposite successive tape signs of the same label would come from consecutive inverse basis letters, forbidden by basis reduction; opposite signs of different labels are not a pinch. Any cancellations of neighboring $x,x^{-1}$ do not change this observation. The same is true of $Z$, since it is freely reduced. If $Z$ began with $s^{-1}$, the only possible first pinch in $x^a{u}^{-1}Z$ would be across that seam. The last basis letter of $u^{-1}$ would have to be $sx$, giving exactly $sx{s}^{-1}$. For the tape relation $s^{-1}xs=x^2$, such a pinch requires $x\in ⟨x^2⟩$, impossible because $x$ has infinite order and $1$ is not an even integer. If $u$ is empty there is no seam pinch at all. Multiple-letter Britton therefore rules out a negative first letter of $Z$. Thus $Z$ is empty or begins positively.

Suppose $p>0$ and assume the stronger assertion for all smaller counts. By [F1], write $L=L_3{r}_i^{ϵ}{x}^m,R=x^n{r}_i^{-ϵ}{L}_4,$ where $x^m{X}^{\mathrm{\#}}{q}_{j}Y{x}^n$ lies in $A_i$ if $ϵ=-1$, or in $B_i$ if $ϵ=1$. Each of $L_3,L_4$ has $p-1$ rule letters. To treat both orientations uniformly, put $(P,q_c,Q^{\mathrm{\prime }},P^{\mathrm{\prime }},q_d,Q^{\mathrm{\prime }\mathrm{\prime }},\eta )=\{\begin{array}{ll}(F_i,q_{a(i)},G_i,H_i,q_{b(i)},K_i,1),& ϵ=-1,\\ (H_i,q_{b(i)},K_i,F_i,q_{a(i)},G_i,-1),& ϵ=1.\end{array}$ Then the edge subgroup is $E=⟨P^{\mathrm{\#}}{q}_c{Q}^{\mathrm{\prime }},T_{\eta }⟩$ and conjugation by $r_i^{ϵ}$ carries $P^{\mathrm{\#}}{q}_c{Q}^{\mathrm{\prime }}$ to $(P^{\mathrm{\prime }}{)}^{\mathrm{\#}}{q}_d{Q}^{\mathrm{\prime }\mathrm{\prime }}$ and sends $s{x}^{\eta }$ to $s{x}^{-\eta }$.

If instead $Z{x}^a\in T_{-1}$, apply $\theta$. It fixes every signed tape word and sends $Z{x}^a$ to $Z{x}^{-a}\in T_1$, so the same sign test holds. A mirrored test also holds: if $x^{a}Z\in T_{\eta }$, invert to obtain $Z^{-1}{x}^{-a}\in T_{\eta }$. The first-letter test for $Z^{-1}$ says that $Z$ is empty or ends negatively. These conclusions cover both $\eta =1,-1$ and $a=0$ without exception.

Membership of $x^m{X}^{\mathrm{\#}}{q}_{j}Y{x}^n$ in $E$ gives a word in $T_{\eta }$ and $a=P^{\mathrm{\#}}{q}_c{Q}^{\mathrm{\prime }}$. Choose one with the fewest occurrences of $a^{\pm 1}$ and reduce every intervening $T_{\eta }$ basis word. There cannot be zero occurrences, since a tape element has no state syllable. In the product of this expression with the inverse of $x^m{X}^{\mathrm{\#}}{q}_{j}Y{x}^n$, free-product reduction must cancel state letters. A state cancellation entirely among two consecutive $a$ occurrences with opposite signs has intervening coefficient either $Q^{\mathrm{\prime }}u(Q^{\mathrm{\prime }}{)}^{-1}$ or $(P^{\mathrm{\#}}{)}^{-1}u{P}^{\mathrm{\#}}$, where $u\in T_{\eta }$. Its being identity forces $u=1$, so the two inverse occurrences could be removed, contradicting minimality. Therefore the single state letter of the coefficient must cancel with one of these occurrences, and after that no further state occurrences can remain: any further reduction would again remove an inverse pair already excluded by minimality. Exactly one positive $a$ occurs, $q_j=q_c$, and comparison of its left and right coefficients yields $x^m{X}^{\mathrm{\#}}=u{P}^{\mathrm{\#}},Y{x}^n=Q^{\mathrm{\prime }}v(u,v\in T_{\eta })\mathrm{.}$ The state sign is positive because the original coefficient contains $q_j$, not $q_j^{-1}$, in the free state factor.

Reduce $(Q^{\mathrm{\prime }}{)}^{-1}Y$ freely to $Z$. From step 2.2, $Z{x}^n=v\in T_{\eta }$. If any letter of $(Q^{\mathrm{\prime }}{)}^{-1}$ survived the seam cancellation, $Z$ would start negatively, since $Q^{\mathrm{\prime }}$ is positive. This contradicts steps 1.3 and 2.1. Thus $Y=Q^{\mathrm{\prime }}{Y}_1$ as an exact spelling, and $Y_1$ is empty or starts positively. Likewise reduce $X^{\mathrm{\#}}(P^{\mathrm{\#}}{)}^{-1}$ to $Z^{\mathrm{\prime }}$. Then $x^m{Z}^{\mathrm{\prime }}=u\in T_{\eta }$. If any letter from $(P^{\mathrm{\#}}{)}^{-1}$ survived, $Z^{\mathrm{\prime }}$ would end positively; the mirrored test in step 2.1 excludes this. Hence $X=X_{1}P$ as a spelling, and $X_1^{\mathrm{\#}}$ is empty or ends negatively. Both $X_1,Y_1$ are subwords of the original reduced words and so are reduced. These conclusions include completely empty remainders and empty $P,Q^{\mathrm{\prime }}$.

Substituting the spellings from step 3.1 into the coefficient equations and cancelling the terminal/initial tape factors gives $u=x^m{X}_1^{\mathrm{\#}},v=Y_1{x}^n\mathrm{.}$ By [F2]–[F3], the applicable edge isomorphism restricts to $\theta$ on $T_{\eta }$, because it sends each of its basis elements $s{x}^{\eta }$ to $s{x}^{-\eta }$. Thus its values on these particular elements are $\theta (u)=x^{-m}{X}_1^{\mathrm{\#}}$ and $\theta (v)=Y_1{x}^{-n}$. Replacing the central pinch in the original equation gives $(L_3{x}^{-m})X_1^{\mathrm{\#}}(P^{\mathrm{\prime }}{)}^{\mathrm{\#}}{q}_d{Q}^{\mathrm{\prime }\mathrm{\prime }}{Y}_1(x^{-n}{L}_4)=q\mathrm{.}$ This computation is valid for both signs of $ϵ$; for $ϵ=1$ it uses the inverse edge map, which still restricts to the same involution $\theta$.

The word $X_1^{\mathrm{\#}}(P^{\mathrm{\prime }}{)}^{\mathrm{\#}}$ is freely reduced: each factor is reduced, the second is negative, and a nonempty first factor ends negatively by step 3.1. No opposite pair can occur at the seam. Similarly $Q^{\mathrm{\prime }\mathrm{\prime }}{Y}_1$ is reduced, since $Q^{\mathrm{\prime }\mathrm{\prime }}$ is positive and a nonempty $Y_1$ starts positively. Empty factors introduce no seam. Sharp preserves free reduction, so $X_1{P}^{\mathrm{\prime }}$ is also freely reduced. Freely reduce the two auxiliary factors in step 4.1; their rule counts can only decrease and are at most $p-1$. By [F1] their new counts agree. The induction hypothesis therefore applies and makes $X_1{P}^{\mathrm{\prime }}$ and $Q^{\mathrm{\prime }\mathrm{\prime }}{Y}_1$ positive, with $X_1{P}^{\mathrm{\prime }}{q}_d{Q}^{\mathrm{\prime }\mathrm{\prime }}{Y}_1=q\text{in }\mathrm{\Gamma }\mathrm{.}$ Because the two concatenations were freely reduced spellings, their subwords $X_1,Y_1$ are themselves positive. Consequently $X=X_{1}P$ and $Y=Q^{\mathrm{\prime }}{Y}_1$ are positive.

If $ϵ=-1$, the original positive word is $X_1{F}_i{q}_{a(i)}{G}_i{Y}_1$, which rewrites by rule $i$ to $X_1{H}_i{q}_{b(i)}{K}_i{Y}_1=q$. If $ϵ=1$, it is $X_1{H}_i{q}_{b(i)}{K}_i{Y}_1$, which rewrites by the reverse of the same semigroup equation to $X_1{F}_i{q}_{a(i)}{G}_i{Y}_1=q$. Both uses have positive contexts by step 5.1. This completes the induction for signed words. For the special words of the statement, positivity was already given, so the resulting equality is exactly ${\mathrm{\Sigma }}^{\ast }=q$.