Skip to main content
added 98 characters in body
Source Link
Ville Salo
  • 6.7k
  • 1
  • 17
  • 40

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.

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^*$. 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.

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.

added 1 character in body
Source Link
Ville Salo
  • 6.7k
  • 1
  • 17
  • 40

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^*$. 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.

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^*$. 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 $$.

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.

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^*$. 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.

Source Link
Ville Salo
  • 6.7k
  • 1
  • 17
  • 40

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^*$. 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 $$.

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.