Could every ultimately periodic word $\eta$ factored $\eta = pq^{\omega}$ such that $pq$ is primitive?

283 Views Asked by At

An infinite word $\eta$ is called ultimately periodic iff $\eta = pq^{\omega}$ for some $p, q \in X^*$. A word $w \in X^*$ is called primitive iff it is not a power of another word, i.e. it could not be written as $w = v^n$ for some $v \in X^*$ and $n > 1$.

If $\eta$ is ultimately periodic, could $p, q$ such choosen that the concatenation $pq$ is primitive?

1

There are 1 best solutions below

4
On

First note that $q$ may be assumed to be primitive, because if $q=r^k$ then $q^{\omega}=r^{\omega}.$ Now if $pq$ is primitive we're done by resetting $p$ as $pq$. Let $x$ be the first symbol of $q$. Then one can peel that off from $q$ and get $q^{\omega}=x(q')^{\omega}$ where $q'$ is a cyclic permutation of $q.$ For example $$(abc)(abc)(abc)\cdots =a(bca)(bca)(bca)\cdots.$$ So we can finish provided we show that at least one of $pq$ and $pqx$ is primitive.

Assume neither is primitive and write each as a nontrivial power, then we arrive at something of the form $R^mx=S^n$, where $R^m=pq$ and $R^mx=S^n=pqx.$ We may assume $R,S$ are primitive, and we have also $m,n \ge 2.$ Denote the lengths of $R,S$ by $r,s$ respectively. If either of these lengths is $1$ the finish is easy, as the string $pq$ then is a concatenation of a single letter, and then either $q$ is that same letter (in which case take $p$ as the empty string so that $pq=q$ is primitive), or else $q$ has other letters and one can take $pq$ as a string of one letter followed by a distinct letter, which is clearly primitive.

Now consider lengths. $R^mx$ has length $rm+1$ and $S^n$ has length $sn$. This means $rm+1=sn,$ from which one gets $\gcd(r,s)=1.$ Suppose first that $r<s.$ Then with subscripts on $S$ interpreted mod $s$ we have $S_{k+r}=S_k$ by matching up the first two terms of $S^n$ against the powers of $R^m$ aligned with them. Since $\gcd(r,s)=1$ the iterates $1,1+r,1+2r,\cdots$ fill out e complete set of subscripts mod $s$ and we get that $S$ is a string of all the same symbol. This can be viewed either as getting us back to a case already considered, or else as a contradiction to our assumption that $S$ is primitive.

A similar finish is possible if we assume $s<r$. There are maybe some details that need some more careful checking, but I believe this approach works. For example one has to be careful, when $k$ is near the value $s$, that adding $r$ to $k$ stays in the region where the two strings are matching up. However I think that works because of there being at least two iterations of either $R$ or $S$ which match up, with maybe a possible mismatch when $k=r$ which won't matter. I can try to fill this gap in if requested.