## Notes and errata on "Decidability and Universality of Quasiminimal Subshifts"

The main results of my paper are about abstract quasiminimal subshifts under computability restrictions, but there is also a tangent to classical systems, where I prove the following: If a substitution $$\tau$$ has the following property: "In every point of the language of the subshift that $$\tau$$ generates, in every word of length $$m$$ you have a letter $$a$$ such that $$|\tau^n(a)|$$ tends to infinity." then the subshift $$\tau$$ generates is quasiminimal. I conjecture in my paper that in fact every substitution has a quasiminimal associated subshift. In this note, we prove this conjecture.

In [Bérthé-Steiner-Thuswaldner-Yassawi], Proposition 5.15 states that for every non-erasing substitution there are only finitely many languages for points. This is the same thing as quasiminimality by an easy argument (see e.g. Lemma 11 and Proposition 6 in my paper).

Here's their theorem in my language:

Let $$\tau : \Sigma \to \Sigma^+$$ be any substitution. Let $$X_{\tau} \subset \Sigma^{\mathbb{Z}}$$ be the subshift consisting of the points $$x$$ whose finite subwords all appear in some $$\tau^n(a), n \in \mathbb{N}, a \in \Sigma$$. Then $$X_{\tau}$$ is a quasiminimal subshift.

Theorem 7.5.1 in [Allouche-Shallit] (also [Cobham]) shows that a morphic image of the fixed point of a (possibly erasing) substitution is also the symbol-to-symbol substitutive image of a fixed point of a non-erasing substitution. It is not difficult to obtain the general result from this and the above theorem, as images of quasiminimal subshifts under non-erasing morphisms are quasiminimal. A similar idea was also suggested by Wolfgang Steiner in private communication.

Let $$\tau : \Sigma \to \Sigma^*$$ be any substitution. Let $$X_{\tau} \subset \Sigma^{\mathbb{Z}}$$ be the subshift consisting of the points $$x$$ whose finite subwords all appear in some $$\tau^n(a), n \in \mathbb{N}, a \in \Sigma$$. Then $$X_{\tau}$$ is a quasiminimal subshift.

Errata:
• The definition I give of the subshift of a substitution in my paper has an unfortunate typo: In Definition 10, obviously $$j$$ and $$k$$ should range over $$\mathbb{Z}$$ rather than $$\mathbb{N}$$.
• Marie-Pierre Béal, Dominique Perrin and Antonio Restivo pointed out to me that the proof of Lemma 3 is wrong. Specifically, the proof of the "In particular" claim (that is, the last sentence) is wrong. Somehow I missed the subtleties here even though I am clearly very aware of the same difficulties when discussing quasiminimality. The only excuse I can think of is incompetence that this proof was taken from my thesis draft, and was written for primitive substitutions (for which this proof is fine), and I didn't see where the primitivity is needed so I erased it and forgot about it. I believe I have a working proof sketch of this lemma, but I haven't gotten to writing it down in the half a year that I've known about the error, so at this point I'll just add this note without a correction, hopefully I get to this in finite time. If you are interested, bug me about it and I'll have to get on it!

## References

[Allouche-Shallit] Allouche, Jean-Paul, and Jeffrey Shallit. Automatic sequences: theory, applications, generalizations. Cambridge university press, 2003.
[Bérthé-Steiner-Thuswaldner-Yassawi] Berthé, Valérie and Steiner, Wolfgang and Thuswaldner, Jörg M. and Yassawi, Reem. (2018) "Recognizability for sequences of morphisms," Ergodic Theory and Dynamical Systems. Cambridge University Press, pp. 1–36. doi: 10.1017/etds.2017.144.
[Cobham] Cobham, Alan. "On the Hartmanis-Stearns problem for a class of tag machines." IEEE Conference Record of 1968 Ninth Annual Symposium on Switching and Automata Theory. IEEE, 1968.

Last update: 1 Mar 2022