An Improved Version of Hmelevskii’s Theorem on Three-Variable Word Equations

Straightforward computation. $◀$

We need to study the question of when ${\varphi }^j(w)$ is a word, or when ${\varphi }^j\circ h$ is an M-morphism. For that purpose, we give some additional definitions.

A word $w\in {\{a,b\}}^{+}$ is called an alternating block, or just block for short, if neither $aa$ nor $bb$ is a factor of $w$. In other words, $w$ is an alternating block if and only if it is a nonempty factor of some word in ${(ab)}^{\ast }$.

An alternating block decomposition (ABD) of $w\in {\{a,b\}}^{\ast }$ is a sequence $(u_1,\mathrm{\dots },u_n)$ of alternating blocks such that $w=u_1\mathrm{\cdots }{u}_n$ and for all $i\in \{1,\mathrm{\dots },n-1\}$, the last letter of $u_i$ is the same as the first letter of $u_{i+1}$.

We split $w$ in the middle of every occurrence of the factors $aa$ and $bb$. This gives an ABD, and no other way of splitting $w$ into factors can give an ABD. $◀$

For a word $w\in {\{a,b\}}^{\ast }$ with an ABD $(u_1,\mathrm{\dots },u_n)$, we define its $a$-degree

and $b$-degree

For $c\in \{a,b\}$ and for $h\in \mathrm{MM}(\{x,y,z\},\mathrm{\Sigma })$ such that $h(x),h(y),h(z)\in {\{a,b\}}^{\ast }$, we define

Let the ABD of $w$ be $(u_1,\mathrm{\dots },u_n)$. By Lemma 8, every block $u_i$ that is not of the form $b{(ab)}^k$ with or of the form ${(ab)}^{k}a$ with is mapped to a word that begins and ends with the same letter as $u_i$. In particular, if , then ${\varphi }^j(u_i)\in {\{a,b\}}^{\ast }$ for all $i$ and therefore ${\varphi }^j(w)\in {\{a,b\}}^{\ast }$.

If $j\ge {\mathrm{deg}}_b(w)$, then there is at least one $i$ such that $u_i=b{(ab)}^k$ with . For all such $i$, ${\varphi }^j(u_i)=b{(ab)}^{k-j}={(a^{-1}{b}^{-1})}^{j-k-1}{a}^{-1}$. If $i\ge 2$, then $u_{i-1}$ ends with $b$ and thus ${\varphi }^j(u_{i-1})$ ends with either $b$ or $a^{-1}$. Similarly, if $i\le n-1$, then ${\varphi }^j(u_{i+1})$ begins with either $b$ or $a^{-1}$. This means that when we calculate ${\varphi }^j(w)$ as the product of the images of the blocks, no cancellation can happen. Therefore, the reduced form of ${\varphi }^j(w)$ still has $a^{-1}$ in it, and ${\varphi }^j(w)$ is not in ${\{a,b\}}^{\ast }$.

The case $j\le -{\mathrm{deg}}_a(w)$ is analogous to the case $j\ge {\mathrm{deg}}_b(w)$. $◀$

The next theorem shows why we are interested in the morphism $\varphi$: It allows us to give a greatly simplified formulation of certain old results. This is then useful when applying the theorem.

Let and $f\in \mathrm{MM}(\{a,b\},\mathrm{\Sigma })$. First, we check that $f\circ {\varphi }^j\circ h$ is an M-morphism (instead of being just a G-morphism): implies for all $t\in \{x,y,z\}$, so we can use Lemma 11 to see that ${\varphi }^j(h(t))\in {\{a,b\}}^{\ast }$ for all $t\in \{x,y,z\}$, and it follows that $f\circ {\varphi }^j\circ h\in \mathrm{MM}(\{x,y,z\},\mathrm{\Sigma })$. If $(u,v)\in \mathrm{Eq}(h)$, then $h(u)=h(v)$ and thus $(f\circ {\varphi }^j\circ h)(u)=(f\circ {\varphi }^j\circ h)(v)$. This shows that $f\circ {\varphi }^j\circ h\in \mathrm{Sol}(\mathrm{Eq}(h))$ and that the right-hand side of (1) is a subset of the left-hand side.

The fact that every nonperiodic morphism in $\mathrm{Sol}(\mathrm{Eq}(h))$ is in

follows from the results in [19]: Theorem 5.2 gives an equivalent equation for each $\mathrm{Eq}(h)$, and Lemmas 6.1–6.6 then solve these equations. In each case, it can be easily checked that the formulas that give the nonperiodic solutions match $f\circ {\varphi }^j\circ h$. This shows that the left-hand side of (1) is a subset of the right-hand side. $◀$

It is an interesting question whether Theorem 12 could be proved in another way without having to use the rather large and cumbersome case analysis in [19].

Every nonperiodic $g\in \mathrm{Sol}(E)$ is equivalent to some $h\in H$, and then $g\in \mathrm{Sol}(\mathrm{Eq}(g))=\mathrm{Sol}(\mathrm{Eq}(h))$.

On the other hand, if $f\in \mathrm{Sol}(\mathrm{Eq}(h))$ for some $h\in H\subseteq \mathrm{Sol}(E)$, then $E\in \mathrm{Eq}(h)$ and thus $f\in \mathrm{Sol}(\mathrm{Eq}(h))\subseteq \mathrm{Sol}(E)$. $◀$

The next lemma is a modified version of Theorem 8.2 in [19].

Let $G_1$ be the set of morphisms of the types BM1, BM3, BM6. Let $G_2,\mathrm{\dots },G_6$ be similar sets for the different permutations of the variables. Let $G_7$ be the set of morphisms of the types BM2, BM4, BM5. Let $G_8,G_9$ be similar sets for the different permutations of the variables (we need only three permutations instead of six because of symmetry). Then $G={\bigcup }_{k=1}^9{G}_k$. If we can find suitable sets $H_k$ such that

then (2) follows.

Morphisms in $G_1$ can be written as $[a,a^{p}b{a}^q,w]$ for some $w\in {\{a,b\}}^{\ast }$. It was proved in [15] that $E$ can have such a solution for at most one pair $(p,q)$. If we fix $p$ and $q$ and replace $x$ by $a$ and $y$ by $a^{p}b{a}^q$ in $E$, we get a nontrivial one-variable equation with constants, and solving this one-variable equation gives us the possible values for $w$. It is known that if such an equation has infinitely many solutions, then there are $u,v$ such that for each $k$, the morphism that maps the remaining variable $z$ to ${(uv)}^{i}u$ is a solution, and there are no other solutions, see [14]. Thus we get a set $H_1$ that is either finite or of the form (3) and satisfies (5). Similarly, we can find sets $H_2,\mathrm{\dots },H_6$.

For morphisms in $G_7$, we can use Lemma 13 to find a set $H_7$ that is either finite or of the form (4) and satisfies (5). Similarly, we can find sets $H_8$ and $H_9$. $◀$

For a fixed $j$, the set

clearly has a parametric representation in ${ℛ}_0(2,0)$, and the same is then true for a finite union of such sets. This takes care of the case where ${\mathrm{deg}}_b(h)$ is finite. If ${\mathrm{deg}}_b(h)$ is infinite and $h=[u,v,w]$, then the ABDs of $u,v,w$ do not contain blocks of the form $b{(ab)}^i$, and therefore ${\varphi }^j$ maps every block either to itself, or, in the case of blocks of the form ${(ab)}^{i}a$, to ${(ab)}^{i+j}a$. This means that ${\varphi }^j(u)$ can be written in the form

where $u_0,\mathrm{\dots },u_n\in {\{a,b\}}^{\ast }$ do not depend on $j$, and ${\varphi }^j(v)$ and ${\varphi }^j(w)$ can be written in a similar form. Thus we get a parametric representation in ${ℛ}_1(2,1)$. $◀$

The following idea that was used in the proof of Lemma 16 is useful also later: If ${\mathrm{deg}}_b(u)=\mathrm{\infty }$, that is, the ABD of $u$ does not contain blocks of the form $b{(ab)}^i$, then ${\varphi }^j(u)$ can be written in the form (6), and it essentially corresponds to a parametric word in ${𝒫}_1(2,1)$. We use this kind of reasoning in the following lemmas without explaining it in detail like above.

If $p=q=0$, then ${\mathrm{deg}}_b(h_i)=1$ for all $i$ and the set (7) is

which has a parametric representation in ${ℛ}_1(2,1)$. For the rest of the proof, assume that $p\ge 1$ or $q\ge 1$. Then ${\mathrm{deg}}_b(h_i)={\mathrm{deg}}_b({(uv)}^{i}u)$ for all $i$.

Let us first assume that some conjugate of $uv$ begins and ends with the same letter $c$. Let this conjugate be $ts$, where $uv=st$. We can write (7) as

Here, we can use Lemma 16 for the first two sets, so it is enough to consider the third set. For $i\ge 2$, ${(uv)}^{i}u=s{(ts)}^{i-1}tu$. Here $ts$ begins and ends with $c$, $s$ is either empty or ends with $c$, and $tu$ is either empty or begins with $c$. Therefore, the ABD of $s{(ts)}^{i-1}tu$ consists of the ABD of $s$ followed by $i-1$ copies of the ABD of $ts$ followed by the ABD of $tu$. For all $i\ge 2$, ${\mathrm{deg}}_b(h_i)=inf({\mathrm{deg}}_b(s),{\mathrm{deg}}_b(ts),{\mathrm{deg}}_b(tu))$, which does not depend on $i$. If ${\mathrm{deg}}_b(h_i)$ is finite, then we have a finite union of sets of the form

In each set, $j$ is a constant. We can write $i^{\prime }=i-2$ and ${({\varphi }^j(ts))}^{i-1}={({\varphi }^j(ts))}^{i^{\prime }}{\varphi }^j(ts)$. Then $i^{\prime }$ runs through all natural numbers and we can think of it as a numerical parameter. Thus we get a parametric representation in ${ℛ}_1(2,1)$. If ${\mathrm{deg}}_b(h_i)$ is infinite, then we have

where ${\varphi }^j(a)={(ab)}^{j}a$ and ${\varphi }^j(a^{p}b{a}^q)={({(ab)}^{j}a)}^{p-1}ab{({(ab)}^{j}a)}^q$ if $p\ge 1$ and ${\varphi }^j(a^{p}b{a}^q)={({(ab)}^{j}a)}^{p}ba{({(ab)}^{j}a)}^{q-1}$ if $q\ge 1$. Thus we can think of $j$ and $i-2$ as numerical parameters, and we get a parametric representation in ${ℛ}_2(2,2)$.

Let us then consider the case where no conjugate of $uv$ begins and ends with the same letter. This means that $uv\in {(ab)}^{\ast }\cup {(ba)}^{\ast }$. There are four subcases:

• $\mathrm{■}$

  $u,v\in {(ab)}^{\ast }$,

• $\mathrm{■}$

  $u,v\in {(ba)}^{\ast }$,

• $\mathrm{■}$

  $u\in {(ab)}^{\ast }a$, $v\in b{(ab)}^{\ast }$,

• $\mathrm{■}$

  $u\in b{(ab)}^{\ast }$, $v\in {(ab)}^{\ast }a$.

The first three are simple: In all these subcases, ${\mathrm{deg}}_b(h_i)={\mathrm{deg}}_b(uv)={\mathrm{deg}}_b(u)=\mathrm{\infty }$, and (7) can be written simply as

which has a parametric representation in ${ℛ}_2(2,2)$.

The fourth subcase is the most complicated one. Example 18 illustrates this case for some particular values of $u$ and $v$. It might be easier to get the basic idea from that example than from the general proof below.

Let $u={(ba)}^{r}b$ and $v={(ab)}^{s}a$. Then ${(uv)}^{i}u={(ba)}^{(r+s+1)i+r}b$. Let $t=r+s+1$. Let $k,l$ be such that $j=tk+l$ and . Let $m,n$ be such that $r-l=tm+n$ and . Then ${(uv)}^{i}u={(ba)}^{ti+r}b$ and

We have ${\mathrm{deg}}_b(h_i)={\mathrm{deg}}_b({(uv)}^{i}u)=ti+r+1$ and therefore we can rewrite the condition using the following sequence of equivalences:

At this point, $r,s,t$ are fixed, while $k,l,m,n$ depend on $j$. However, since there are only finitely many possible values for $l$, we can consider these separately. If we fix $l$, then $m$ and $n$ are also fixed. The part of (7) corresponding to a particular value of $l$ is