We study the computational problem of rigorously describing the asymptotic behavior of topological dynamical systems up to a finite but arbitrarily small pre-specified error. More precisely, we consider the limit set of a typical orbit, both as a spatial object (attractor set) and as a statistical distribution (physical measure), and we prove upper bounds on the computational resources of computing descriptions of these objects with arbitrary accuracy. We also study how these bounds are affected by different dynamical constraints and provide several examples showing that our bounds are sharp in general. In particular, we exhibit a computable interval map having a unique transitive attractor with Cantor set structure supporting a unique physical measure such that both the attractor and the measure are non-computable.

Krieger’s embedding theorem provides necessary and sufficient conditions for an arbitrary subshift to embed in a given topologically mixing $\mathbb {Z}$-subshift of finite type. For certain families of $\mathbb {Z}^d$-subshifts of finite type, Lightwood characterized the aperiodic subsystems. In the current paper, we prove a new embedding theorem for a class of subshifts of finite type over any countable abelian group. Our theorem provides necessary and sufficient conditions for an arbitrary subshift X to embed inside a given subshift of finite type Y that satisfies a certain natural condition. For the particular case of $\mathbb {Z}$-subshifts, our new theorem coincides with Krieger’s theorem. Our result gives the first complete characterization of the subsystems of the multidimensional full shift $Y= \{0,1\}^{\mathbb {Z}^d}$. The natural condition on the target subshift Y, introduced explicitly for the first time in the current paper, is called the map extension property. It was introduced implicitly by Mike Boyle in the early 1980s for $\mathbb {Z}$-subshifts and is closely related to the notion of an absolute retract, introduced by Borsuk in the 1930s. A $\mathbb {Z}$-subshift has the map extension property if and only if it is a topologically mixing subshift of finite type. We show that various natural examples of $\mathbb {Z}^d$ subshifts of finite type satisfy the map extension property, and hence our embedding theorem applies for them. These include any subshift of finite type with a safe symbol and the k-colorings of $\mathbb {Z}^d$ with $k \ge 2d+1$. We also establish a new theorem regarding lower entropy factors of multidimensional subshifts that extends Boyle’s lower entropy factor theorem from the one-dimensional case.

Using tools from computable analysis, we develop a notion of effectiveness for general dynamical systems as those group actions on arbitrary spaces that contain a computable representative in their topological conjugacy class. Most natural systems one can think of are effective in this sense, including some group rotations, affine actions on the torus and finitely presented algebraic actions. We show that for finitely generated and recursively presented groups, every effective dynamical system is the topological factor of a computable action on an effectively closed subset of the Cantor space. We then apply this result to extend the simulation results available in the literature beyond zero-dimensional spaces. In particular, we show that for a large class of groups, many of these natural actions are topological factors of subshifts of finite type.

Under certain conditions, we construct a countable Markov partition for pointwise hyperbolic diffeomorphism $f:M\rightarrow M$ on an open invariant subset $O\subset M$, which allows the Lyapunov exponents to be zero. From this partition, we define a symbolic extension that is finite-to-one and onto a subset of O that carries the same finite f-invariant measures as O. Our method relies upon shadowing theory of a recurrent-pointwise-pseudo-orbit that we introduce. As a canonical application, we estimate the number of closed orbits for f.

We extend previously known two-dimensional multiplication tiling systems that simulate multiplication by two natural numbers p and q in base $pq$ to higher dimensional multiplication tessellation systems. We develop the theory of these systems and link different multiplication tessellation systems with each other via macrotile operations that glue cubes in one tessellation system into larger cubes of another tessellation system. The macrotile operations yield topological conjugacies and factor maps between cellular automata performing multiplication by positive numbers in various bases.

Given a two-sided shift space on a finite alphabet and a continuous potential function, we give conditions under which an equilibrium measure can be described using a construction analogous to Hausdorff measure that goes back to the work of Bowen. This construction was previously applied to smooth uniformly and partially hyperbolic systems by the first author, Pesin, and Zelerowicz. Our results here apply to all subshifts of finite type and Hölder continuous potentials, but extend beyond this setting, and we also apply them to shift spaces with synchronizing words.

Two asymptotic configurations on a full $\mathbb {Z}^d$-shift are indistinguishable if, for every finite pattern, the associated sets of occurrences in each configuration coincide up to a finitely supported permutation of $\mathbb {Z}^d$. We prove that indistinguishable asymptotic pairs satisfying a ‘flip condition’ are characterized by their pattern complexity on finite connected supports. Furthermore, we prove that uniformly recurrent indistinguishable asymptotic pairs satisfying the flip condition are described by codimension-one (dimension of the internal space) cut and project schemes, which symbolically correspond to multidimensional Sturmian configurations. Together, the two results provide a generalization to $\mathbb {Z}^d$ of the characterization of Sturmian sequences by their factor complexity $n+1$. Many open questions are raised by the current work and are listed in the introduction.

In this work we prove that every shift of finite type (SFT), sofic shift, and strongly irreducible shift on locally finite groups has strong dynamical properties. These properties include that every sofic shift is an SFT, every SFT is strongly irreducible, every strongly irreducible shift is an SFT, every SFT is entropy minimal, and every SFT has a unique measure of maximal entropy, among others. In addition, we show that if every SFT on a group is strongly irreducible, or if every sofic shift is an SFT, then the group must be locally finite, and this extends to all of the properties we explore. These results are collected in two main theorems which characterize the local finiteness of groups by purely dynamical properties. In pursuit of these results, we present a formal construction of free extension shifts on a group G, which takes a shift on a subgroup H of G, and naturally extends it to a shift on all of G.

Katok [Lyapunov exponents, entropy and periodic points of diffeomorphisms. Publ. Math. Inst. Hautes Études Sci. 51 (1980), 137–173] conjectured that every $C^{2}$ diffeomorphism f on a Riemannian manifold has the intermediate entropy property, that is, for any constant $c \in [0, h_{\mathrm {top}}(f))$, there exists an ergodic measure $\mu $ of f satisfying $h_{\mu }(f)=c$. In this paper, we obtain a conditional intermediate metric entropy property and two conditional intermediate Birkhoff average properties for basic sets of flows that characterize the refined roles of ergodic measures in the invariant ones. In this process, we establish a ‘multi-horseshoe’ entropy-dense property and use it to get the goal combined with conditional variational principles. We also obtain the same result for singular hyperbolic attractors.

In this paper, we first give a necessary and sufficient condition for a factor code with an unambiguous symbol to admit a subshift of finite type restricted to which it is one-to-one and onto. We then give a necessary and sufficient condition for the standard factor code on a spoke graph to admit a subshift of finite type restricted to which it is finite-to-one and onto. We also conjecture that for such a code, the finite-to-one and onto property is equivalent to the existence of a stationary Markov chain that achieves the capacity of the corresponding deterministic channel.

We prove a generalization of Krieger’s embedding theorem, in the spirit of zero-error information theory. Specifically, given a mixing shift of finite type X, a mixing sofic shift Y, and a surjective sliding block code $\pi : X \to Y$, we give necessary and sufficient conditions for a subshift Z of topological entropy strictly lower than that of Y to admit an embedding $\psi : Z \to X$ such that $\pi \circ \psi $ is injective.

We exhibit, for arbitrary $\epsilon> 0$, subshifts admitting weakly mixing (probability) measures with word complexity p satisfying $\limsup p(q) / q < 1.5 + \epsilon $. For arbitrary $f(q) \to \infty $, said subshifts can be made to satisfy $p(q) < q + f(q)$ infinitely often. We establish that every subshift associated to a rank-one transformation (on a probability space) which is not an odometer satisfies $\limsup p(q) - 1.5q = \infty $ and that this is optimal for rank-ones.

We look at constructions of aperiodic subshifts of finite type (SFTs) on fundamental groups of graph of groups. In particular, we prove that all generalized Baumslag-Solitar groups (GBS) admit a strongly aperiodic SFT. Our proof is based on a structural theorem by Whyte and on two constructions of strongly aperiodic SFTs on $\mathbb {F}_n\times \mathbb {Z}$ and $BS(m,n)$ of our own. Our two constructions rely on a path-folding technique that lifts an SFT on $\mathbb {Z}^2$ inside an SFT on $\mathbb {F}_n\times \mathbb {Z}$ or an SFT on the hyperbolic plane inside an SFT on $BS(m,n)$. In the case of $\mathbb {F}_n\times \mathbb {Z}$, the path folding technique also preserves minimality, so that we get minimal strongly aperiodic SFTs on unimodular GBS groups.

Given a subshift $\Sigma $ of finite type and a finite set S of finite words, let $\Sigma \langle S\rangle $ denote the subshift of $\Sigma $ that avoids S. We establish a general criterion under which we can bound the entropy perturbation $h(\Sigma ) - h(\Sigma \langle S\rangle )$ from above. As an application, we prove that this entropy difference tends to zero with a sequence of such sets $S_1, S_2,\ldots $ under various assumptions on the $S_i$.

We investigate several questions related to the notion of recognizable morphism. The main result is a new proof of Mossé’s theorem and actually of a generalization to a more general class of morphisms due to Berthé et al [Recognizability for sequences of morphisms. Ergod. Th. & Dynam. Sys. 39(11) (2019), 2896–2931]. We actually prove the result of Berthé et al for the most general class of morphisms, including ones with erasable letters. Our result is derived from a result concerning elementary morphisms for which we also provide a new proof. We also prove some new results which allow us to formulate the property of recognizability in terms of finite automata. We use this characterization to show that for an injective morphism, the property of being recognizable on the full shift for aperiodic points is decidable.

We prove an explicit characterization of the points in Thurston’s Master Teapot, which can be implemented algorithmically to test whether a point in $\mathbb {C}\times \mathbb {R}$ belongs to the complement of the Master Teapot. As an application, we show that the intersection of the Master Teapot with the unit cylinder is not symmetrical under reflection through the plane that is the product of the imaginary axis of $\mathbb {C}$ and $\mathbb {R}$.

Motivated by near-identical graphs of two increasing continuous functions—one related to Zaremba’s conjecture and the other due to Salem—we provide an explicit connection between fractals and regular sequences by showing that the graphs of ghost distributions, the distribution functions of measures associated to regular sequences, are sections of self-affine sets. Additionally, we provide a sufficient condition for such measures to be purely singular continuous. As a corollary, and analogous to Salem’s strictly increasing singular continuous function, we show that the ghost distributions of the Zaremba sequences are singular continuous.

For a pseudo-Anosov flow $\varphi $ without perfect fits on a closed $3$-manifold, Agol–Guéritaud produce a veering triangulation $\tau $ on the manifold M obtained by deleting the singular orbits of $\varphi $. We show that $\tau $ can be realized in M so that its 2-skeleton is positively transverse to $\varphi $, and that the combinatorially defined flow graph $\Phi $ embedded in M uniformly codes the orbits of $\varphi $ in a precise sense. Together with these facts, we use a modified version of the veering polynomial, previously introduced by the authors, to compute the growth rates of the closed orbits of $\varphi $ after cutting M along certain transverse surfaces, thereby generalizing the work of McMullen in the fibered setting. These results are new even in the case where the transverse surface represents a class in the boundary of a fibered cone of M. Our work can be used to study the flow $\varphi $ on the original closed manifold. Applications include counting growth rates of closed orbits after cutting along closed transverse surfaces, defining a continuous, convex entropy function on the ‘positive’ cone in $H^1$ of the cut-open manifold, and answering a question of Leininger about the closure of the set of all stretch factors arising as monodromies within a single fibered cone of a $3$-manifold. This last application connects to the study of endperiodic automorphisms of infinite-type surfaces and the growth rates of their periodic points.

We introduce a class of rank-one transformations, which we call extremely elevated staircase transformations. We prove that they are measure-theoretically mixing and, for any $f : \mathbb {N} \to \mathbb {N}$ with $f(n)/n$ increasing and $\sum 1/f(n) < \infty $ , that there exists an extremely elevated staircase with word complexity $p(n) = o(f(n))$ . This improves the previously lowest known complexity for mixing subshifts, resolving a conjecture of Ferenczi.