Word combinatorics terminology question

Question

I'm looking for the name of what I suspect must be a standard property, and also for a possible statement about that property.

First the property: $W=a_0\ldots a_{n-1}$ has this property if for all $1\le k<n$, $a_0\ldots a_{k-1}\ne a_{n-k}\ldots a_{n-1}$.

In particular, this implies that in any finite or infinite word, the blocks containing $W$ are disjoint. For the particular application that I have in mind, I start off with an infinite word $x$, and replace some subwords of $X$ of length $n$ spaced far apart by $W$'s. The consequence of the definition that is useful for me is that if $x$ initially contained no $W$'s, then the only $W$'s in the resulting sequence are those $W$'s that I "manually" inserted.

Is there a name for this property?

Is it the case that if $X$ is any mixing shift of finite type, then $X$ contains a word with this property?

(It's not hard to show that if $X$ is a full shift with an alphabet with two or more symbols, then $X$ contains words with this property.)

Answer 1

Yes you find these in all infinite mixing SFTs. More is true. As mentioned, these words are sometimes called unbordered, I'll use that word.

The following is Theorem 8.3.9 in [1].

Theorem. Let $x \in A^\mathbb{N}$ for any alphabet $A$. If $x$ is not periodic, then for any $m$, there exists an unbordered word $w \sqsubset x$ with $|w| \geq m$.

Here periodic means $x = u^{\mathbb{N}} = uuuuu...$ for a finite-length word $u \in A^*$; and $w \sqsubset x$ means that $w = x_{[i, i+|w|-1]}$ for some $i$, i.e. it appears as a subword. So all you need is a non-periodic point in your subshift, in the weak sense that it's not literally of the form $u^{\mathbb{N}}$. To find these, we can apply the following result. The earliest written reference I know proving something like this is [2, Theorem 3.8], I'll just write a proof.

Theorem. Let $X \subset A^\mathbb{N}$ be an infinite subshift (the shift need not be surjective). Then $X$ has a point which is not periodic.

Proof. We prove the contrapositive. Suppose $X$ has only periodic points. Let $Y \subset A^{\mathbb{Z}}$ be the $\mathbb{Z}$-subshift obtained as limit points of points in $X$. First suppose it is infinite. In this case, suppose that for some $n$, every word of length $n$ has a unique predecessor letter, i.e. $\forall u \in L: \exists! a \in A: au \in L$ where $L$ is the language of $Y$. This clearly implies the subshift $Y$ has at most $|A^n|$ points, contradicting infiniteness. So we can find arbitrarily long words $u$ which can be extended to the left by two distinct letters $a, b$. Taking a limit of such pairs, we obtain that there exists an infinite right tail $x \in A^{\mathbb{N}}$ which can be preceded by two distinct letters in points of $Y$. Thus the same is true in $X$, i.e. $ax, bx \in X$ for some distinct $a, b$. These cannot both be periodic. Next, suppose $Y$ is finite. Then in particular every point in $Y$ is periodic with some period $p$. This is a finite type condition, so because $Y$ is the limit points of $X$ we have that tails of points in $X$ actually have $p$-periodic tails after a bounded prefix (the subshifts $\sigma^n(Y)$ tend to $X$ in Hausdorff metric, so eventually you have to respect forbidden patterns of $X$). But then $X$ has only eventually periodic points, with a bound on the ``eventual'', so $X$ is finite. Square.

Theorem. Let $X \subset A^\mathbb{N}$ or $X \subset A^\mathbb{Z}$ be an infinite subshift. Then there are unbordered words of unbounded length in the language of $X$.

Proof. For $\mathbb{N}$ just combine the above theorems. For $\mathbb{Z}$ cut off the left tail; this preserves infiniteness and gives you an ${\mathbb{N}}$-subshift. Square.

[1] Lothaire, M., Algebraic combinatorics on words, Encyclopedia of Mathematics and Its Applications. 90. Cambridge: Cambridge University Press. xiii, 504 p. \textsterling 60.00/hbk (2002). ZBL1001.68093.>

[2] Ballier, Alexis; Durand, Bruno; Jeandal, Emmanuel, Structural aspects of tilings, Albers, Susanne (ed.) et al., STACS 2008. 25th international symposium on theoretical aspects of computer science, Bordeaux, France, February 21–23, 2008. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-06-4). LIPIcs – Leibniz International Proceedings in Informatics 1, 61-72, electronic only (2008). ZBL1258.05023.