4
$\begingroup$

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.)
$\endgroup$
7
  • 1
    $\begingroup$ Okay, "bifix-free" is another term for this: encycla.com/Bifix-free_word $\endgroup$ Jul 5 at 20:04
  • $\begingroup$ @SamHopkins: thanks for this. $\endgroup$ Jul 5 at 20:11
  • 2
    $\begingroup$ 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. $\endgroup$ Jul 5 at 21:07
  • 4
    $\begingroup$ '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). $\endgroup$
    – Dan Rust
    Jul 5 at 21:11
  • 2
    $\begingroup$ 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 $\endgroup$
    – Dan Rust
    Jul 5 at 21:41

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks Ville for the detailed response. This is very helpful. $\endgroup$ Jul 8 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.