# Word combinatorics terminology 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, $$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.)
• Okay, "bifix-free" is another term for this: encycla.com/Bifix-free_word Jul 5 at 20:04
• @SamHopkins: thanks for this. Jul 5 at 20:11
• They are counted on OEIS:A003000. In Russian literature this is often called "hypersimple", and "unbordered", "bifix-free", or "self-overlap free" are all common, too. Jul 5 at 21:07
• 'unbordered' is what I've seen most commonly. They're often used for instance to define non-trivial automorphisms of subshifts, or to show positive entropy of certain subshifts (essentially because of the replacement property/construction that you point out). Jul 5 at 21:11
• Does Lemma 7.4 (the first paragraph of the proof) in this paper: arxiv.org/pdf/2204.06215.pdf answer your question? Actually, it looks like Salo's thesis has a much more general statement (1.3.5 - 1.3.7) villesalo.com/article/SwSCA.pdf Jul 5 at 21:41

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.

• Thanks Ville for the detailed response. This is very helpful. Jul 8 at 19:02