Search

We study higher order expansions both in the Berry-Ess\'een estimate (Edgeworth expansions) and in the local limit theorems for Birkhoff sums of chaotic probability preserving dynamical systems. We establish general results under technical assumptions, discuss the verification of these assumptions and illustrate our results by different examples (subshifts of finite type, Young towers, Sinai billiards, random matrix products), including situations of unbounded observables with integrability order arbitrarily close to the optimal moment condition required in the i.i.d. setting., Comment: 66 pages, 2 figures

Rhombus Penrose tilings are tilings of the plane by two decorated rhombi such that the decoration match at the junction between two tiles (like in a jigsaw puzzle). In dynamical terms, they form a tiling space of finite type. If we remove the decorations, we get, by definition, a sofic tiling space that we here call geometrical Penrose tilings. Here, we show how to compute the patterns of a given size which appear in these tilings by two different method: one based on the substitutive structure of the Penrose tilings and the other on their definition by the cut and projection method. We use this to prove that the geometrical Penrose tilings are characterized by a small set of patterns called vertex-atlas, i.e., they form a tiling space of finite type. Though considered as folk, no complete proof of this result has been published, to our knowledge.

In their recent paper [KNS2019], the first author, S. Kiriki, and T. Soma introduced a concept of pointwise emergence to measure the complexity of irregular orbits. They constructed a residual subset of the full shift with high pointwise emergence. In this paper we consider the set of points with high pointwise emergence for topologically mixing subshifts of finite type. We show that this set has full topological entropy, full Hausdorff dimension, and full topological pressure for any H\"older continuous potential. Furthermore, we show that this set belongs to a certain class of sets with large intersection property. This is a natural generalization of [FP2011] to pointwise emergence and Carath\'eodory dimension., Comment: Accepted for publication in Nonlinearity

In this paper we show that a “typical” random product of conservative surface diffeomorphism has positive Lyapunov exponents. We prove that for any compact oriented surface S, any $$r\ge 1$$ , and any $$d\ge 2$$ , there exists a $$C^1$$ -open and $$C^1$$ -dense subset of $${\text {Diff}}^r_{{\text {vol}}}(S)^d$$ such that if $$(f_1, \ldots , f_d)$$ belongs to this subset, the random product generated by them has positive Lyapunov exponents. Our proof also allows us to deal with more general skew products, for example skew products with a volume preserving Anosov diffeomorphism on the basis, or with a subshift of finite type on the basis preserving a measure with product structure. In these cases we prove the $$C^1$$ -density and $$C^r$$ -openness of the existence of positive Lyapunov exponents.

Let $G,H$ be two countable amenable groups. We introduce the notion of group charts, which gives us a tool to embed an arbitrary $H$-subshift into a $G$-subshift. Using an entropy addition formula derived from this formalism we prove that whenever $H$ is finitely presented and admits a subshift of finite type (SFT) on which $H$ acts freely, then the set of real numbers attained as topological entropies of $H$-SFTs is contained in the set of topological entropies of $G$-SFTs modulo an arbitrarily small additive constant for any finitely generated group $G$ which admits a translation-like action of $H$. In particular, we show that the set of topological entropies of $G$-SFTs on any such group which has decidable word problem and admits a translation-like action of $\mathbb{Z}^2$ coincides with the set of non-negative upper semi-computable real numbers. We use this result to give a complete characterization of the entropies of SFTs in several classes of groups., Comment: 4 nicely drawn figures. Last update improves the results of Sec 3.2 and fixes a few typos

International audience; We study the periodicity of subshifts of finite type (SFT) on Baumslag-Solitar groups. We show that for residually finite Baumslag-Solitar groups there exist both strongly and weakly-but-not-strongly aperiodic SFTs. In particular, this shows that unlike Z 2 , but like Z 3 , strong and weak aperiodic SFTs are different classes of SFTs in residually finite BS groups. More precisely, we prove that a weakly aperiodic SFT on BS(m,n) due to Aubrun and Kari is, in fact, strongly aperiodic on BS(1,n); and weakly but not strongly aperiodic on any other BS(m,n). In addition, we exhibit an SFT which is weakly but not strongly aperiodic on BS(1,n); and we show that there exists a strongly aperiodic SFT on BS(n,n).

For sequences of non-lattice weakly dependent random variables, we obtain asymptotic expansions for Large Deviation Principles. These expansions, commonly referred to as strong large deviation results, are in the spirit of Edgeworth Expansions for the Central Limit Theorem. We apply our results to show that Diophantine iid sequences, finite state Markov chains, strongly ergodic Markov chains and Birkhoff sums of smooth expanding maps & subshifts of finite type satisfy these strong large deviation results., 37 pages, 1 figure, original version split into two parts: discrete time (part I) and continuous time (Part II)

We consider several computational problems related to conjugacy between subshifts of finite type, restricted to k-block codes: verifying a proposed k-block conjugacy, deciding if two shifts admit a k-block conjugacy, and reducing the representation size of a shift via a k-block conjugacy. We give a polynomial-time algorithm for verification, and show GI - and NP -hardness for deciding conjugacy and reducing representation size, respectively. Our approach focuses on 1-block conjugacies between vertex shifts, from which we generalize to k-block conjugacies and to edge shifts. We conclude with several open problems.

Let (ΣA,σ) be a topologically mixing subshift of finite type on an alphabet consisting of m symbols. Let φ:ΣA→R be a continuous function. For a positive function ψ:N→R+ and a continuous positive fu...

We propose a general framework for proving that a compact, infinite-dimensional map has an invariant set on which the dynamics is semiconjugated to a subshift of finite type. The method is then applied to certain Poincare map of the Kuramoto-Sivashinsky PDE on the line with odd and periodic boundary conditions and with parameter ν = 0.1212 . We give a computer-assisted proof of the existence of symbolic dynamics and countable infinity of periodic orbits with arbitrary large periods.

Let $A$ be a finite set and $G$ a group. A closed subset $X$ of $A^G$ is called a subshift if the action of $G$ on $A^G$ preserves $X$. If $K$ is a closed subset of $A^G$ such that membership in $K$ is determined by looking at a fixed finite set of coordinates, and $X$ is the intersection of all translates of $K$ under the action of $G$, then $X$ is called a subshift of finite type (SFT). If an SFT is nonempty and contains no finite $G$-orbits, it is said to be weakly aperiodic. A virtually cyclic group has no weakly aperiodic SFT, and Carroll and Penland have conjectured that a group with no weakly aperiodic SFT must be virtually cyclic. Answering a question of Jeandel, we show that lamplighters always admit weakly aperiodic SFTs., 10 pages, 3 figures have been added, some corrections have been made

The classical Domino problem asks whether there exists a tiling in which none of the forbidden patterns given as input appear. In this paper, we consider the aperiodic version of the Domino problem: given as input a family of forbidden patterns, does it allow an aperiodic tiling? The input may correspond to a subshift of finite type, a sofic subshift or an effective subshift. arXiv:1805.08829 proved that this problem is co-recursively enumerable ($\Pi_0^1$-complete) in dimension 2 for geometrical reasons. We show that it is much harder, namely analytic ($\Sigma_1^1$-complete), in higher dimension: $d \geq 4$ in the finite type case, $d \geq 3$ for sofic and effective subshifts. The reduction uses a subshift embedding universal computation and two additional dimensions to control periodicity. This complexity jump is surprising for two reasons: first, it separates 2- and 3-dimensional subshifts, whereas most subshift properties are the same in dimension 2 and higher; second, it is unexpectedly large., Comment: 15 pages, accepted to STACS 2022

Subshifts are sets of colourings-or tilings-of the plane, defined by local constraints. Historically introduced as discretizations of continuous dynamical systems, they are also heavily related to computability theory. In this article, we study a conjugacy invariant for subshifts, known as the projective fundamental group and we show that any finitely presented group can be realized as a projective fundamental group of some SFT.

The classical Domino problem asks whether there exists a tiling in which none of the forbidden patterns given as input appear. In this paper, we consider the aperiodic version of the Domino problem: given as input a family of forbidden patterns, does it allow an aperiodic tiling? The input may correspond to a subshift of finite type, a sofic subshift or an effective subshift. [Grandjean et al., 2018] proved that this problem is co-recursively enumerable (�������-complete) in dimension 2 for geometrical reasons. We show that it is much harder, namely analytic (�������-complete), in higher dimension: d ��� 4 in the finite type case, d ��� 3 for sofic and effective subshifts. The reduction uses a subshift embedding universal computation and two additional dimensions to control periodicity. This complexity jump is surprising for two reasons: first, it separates 2- and 3-dimensional subshifts, whereas most subshift properties are the same in dimension 2 and higher; second, it is unexpectedly large., LIPIcs, Vol. 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), pages 19:1-19:15

Let G be an infinite countable group and A be a finite set. If ∑ ⊆ AG is a strongly irreducible subshift of finite type, we endow a locally compact and Hausdorff topology on the homoclinic equivalence relation ${\cal G}$ on ∑ and show that the reduced C*-algebra $C_r^*\left({\cal G} \right)$ of ${\cal G}$ is a unital simple approximately finite (AF)-dimensional C*-algebra. The shift action of G on ∑ induces a canonical automorphism action of G on the C*-algebra $C_r^*\left({\cal G} \right)$ . We give the notion of noncommutative dynamical entropy invariants for amenable group actions on C*-algebras, and show that, if G is an amenable group, then the noncommutative topological entropy of the canonical automorphism action of G on $C_r^*\left({\cal G} \right)$ is equal to the topology entropy of the shift action of G on ∑. We also establish the variational principle with respect to the noncommutative measure entropy and the topological entropy for the C*-dynamical system ( $C_r^*\left({\cal G} \right)$ , G).

Let $$G=\left\langle S|R_{A}\right\rangle $$ be a semigroup with generating set S and equivalences $$R_{A}$$ among S determined by a matrix A. This paper investigates the complexity of G-shift spaces by yielding the Petersen–Salama entropies [defined in Petersen and Salama (Theoret Comput Sci 743:64–71, 2018)]. After revealing the existence of Petersen–Salama entropy of G-shift of finite type (G-SFT), the calculation of Petersen–Salama entropy of G-SFT is equivalent to solving a system of nonlinear recurrence equations. The complete characterization of Petersen–Salama entropies of G-SFTs on two symbols is addressed, which extends (Ban and Chang in On the topological entropy of subshifts of finite type on free semigroups, 2018. arXiv:1702.04394 ) in which G is a free semigroup.

We show that typical [in the sense of Bonatti and Viana (Ergod Theory Dyn Syst 24(5):1295–1330, 2004) and Avila and Viana (Port Math 64:311–376, 2007)] Holder and fiber-bunched $$\text {GL}_d(\mathbb {R})$$-valued cocycles over subshifts of finite type are uniformly quasi-multiplicative with respect to all singular value potentials. We prove the continuity of the singular value pressure and its corresponding (necessarily unique) equilibrium state for such cocycles, and apply this result to repellers. Moreover, we show that the pointwise Lyapunov spectrum is closed and convex, and establish partial multifractal analysis on the level sets of pointwise Lyapunov exponents for such cocycles.

We prove a new result in the area of hitting time statistics. Currently, there is a lot of papers showing that the first entry times into cylinders or balls are often faster than the Birkhoff's Ergodic Theorem would suggest. We provide an opposite counterpart to these results by proving that the hitting times into shrinking balls are also often much larger than these theorems would suggest, by showing that for many dynamical systems $$ \displaystyle \limsup_{r\to 0} \tau_{B(y,r)}(x)\mu(B(y,r))=+\infty, $$ for an appropriately large, at least of full measure, set of points $y$ and $x$. We first do this for all transitive open distance expanding maps and Gibbs/equilibrium states of H\"older continuous potentials; in particular for all irreducible subshifts of finite type with a finite alphabet. Then we prove such result for all finitely irreducible subshifts of finite type with a countable alphabet and Gibbs/equilibrium states for H\"older continuous summable potentials. Next, we show that the \emph{limsup} result holds for all graph directed Markov systems (far going natural generalizations of iterated function systems) and projections of aforementioned Gibbs states on their limit sets. By utilizing the first return map techniques, we then prove the \emph{limsup} result for all tame topological Collect--Eckmann multimodal maps of an interval, all tame topological Collect--Eckmann rational functions of the Riemann sphere, and all dynamically semi--regular transcendental meromorphic functions from $\mathbb{C}$ to $\widehat{\mathbb{C}}$., Comment: arXiv admin note: text overlap with arXiv:1609.03610

We consider a perturbed system ($$\Sigma_A^+$$,ϕ(ϵ, ·)) with topologically transitive subshift of finite type $$\Sigma_A^+$$ and Holder continuous functions ϕ(ϵ, ·) defined on $$\Sigma_A^+$$ endowed with small parameter ϵ > 0. Through our choice of ϕ(ϵ, ·), we realize the situation that the perturbed system has a unique Gibbs measure μϵ of the potential ϕ(ϵ, ·) for each ϵ > 0 and on the other hand the unperturbed system possesses several Gibbs measures μ1, μ2,…, μm of the limit potential at ϵ = 0. In this paper, we give a necessary and sufficient condition for convergence of the measure μϵ using the notion of Perron complements of Ruelle operators. Our results can be applied also to the problems of convergence of stationary distributions of perturbed Markov chains with holes.

In this work we are going to consider the classical Henon-Devaney map given by \begin{document}$ \begin{eqnarray*} f: \mathbb{R}^2\setminus \{y = 0\} &\rightarrow& \mathbb{R}^2 \\ (x,y) &\mapsto& \left(x+\dfrac{1}{y}, y-\dfrac{1}{y}-x\right) \end{eqnarray*} $\end{document} We are going to construct conjugacy to a subshift of finite type, providing a global understanding of the map's behavior.We extend the coding to a more general class of maps that can be seen as a map in a square with a fixed discontinuity.

The dynamics of symbolic systems, such as multidimensional subshifts of finite type or cellular automata, are known to be closely related to computability theory. In particular, the appropriate tools to describe and classify topological entropy for this kind of systems turned out to be algorithmic. Part of the great importance of these symbolic systems relies on the role they have played in understanding more general systems over non-symbolic spaces. The aim of this article is to investigate topological entropy from a computability point of view in this more general, not necessarily symbolic setting. In analogy to effective subshifts, we consider computable maps over effective compact sets in general metric spaces, and study the computability properties of their topological entropies. We show that even in this general setting, the entropy is always a \begin{document}$ \Sigma_2 $\end{document} -computable number. We then study how various dynamical and analytical constrains affect this upper bound, and prove that it can be lowered in different ways depending on the constraint considered. In particular, we obtain that all \begin{document}$ \Sigma_2 $\end{document} -computable numbers can already be realized within the class of surjective computable maps over \begin{document}$ \{0,1\}^{{\mathbb N}} $\end{document} , but that this bound decreases to \begin{document}$ \Pi_{1} $\end{document} (or upper)-computable numbers when restricted to expansive maps. On the other hand, if we change the geometry of the ambient space from the symbolic \begin{document}$ \{0,1\}^{{\mathbb N}} $\end{document} to the unit interval \begin{document}$ [0,1] $\end{document} , then we find a quite different situation – we show that the possible entropies of computable systems over \begin{document}$ [0,1] $\end{document} are exactly the \begin{document}$ \Sigma_{1} $\end{document} (or lower)-computable numbers and that this characterization switches down to precisely the computable numbers when we restrict the class of system to the quadratic family.

We study mean dimension of shifts of finite type defined on compact metric spaces and give its lower bound when the shift possesses a certain "periodic block" of arbitrarily large length. The result is applied to shift maps on generalized inverse limits with upper semi-continuous closed set-valued functions. In particular we obtain a refinement of some results due to Banic [ 1 ] and Erceg and Kennedy [ 5 ] on the dimension of the inverse limit spaces and topological entropy of their shifts.

This paper establishes a fundamental difference between $\mathbb{Z}$ subshifts of finite type and $\mathbb{Z}^{2}$ subshifts of finite type in the context of ergodic optimization. Specifically, we consider a subshift of finite type $X$ as a subset of a full shift $F$. We then introduce a natural penalty function $f$, defined on $F$, which is 0 if the local configuration near the origin is legal and $-1$ otherwise. We show that in the case of $\mathbb{Z}$ subshifts, for all sufficiently small perturbations, $g$, of $f$, the $g$-maximizing invariant probability measures are supported on $X$ (that is, the set $X$ is stably maximized by $f$). However, in the two-dimensional case, we show that the well-known Robinson tiling fails to have this property: there exist arbitrarily small perturbations, $g$, of $f$ for which the $g$-maximizing invariant probability measures are supported on $F\setminus X$.

We prove strong laws of large numbers under intermediate trimming for Birkhoff sums over subshifts of finite type. This gives another application of a previous trimming result only proven for interval maps. In case of Markov measures we give a further example of St.\ Petersburg type distribution functions. To prove these statements we introduce the space of quasi-H\"older continuous functions for subshifts of finite type., Comment: 19 pages. arXiv admin note: text overlap with arXiv:1706.07369

We consider the open set constructed by M. Shub in [42] of partially hyperbolic skew products on the space $\mathbb{T}^2\times \mathbb{T}^2$ whose non-wandering set is not stable. We show that there exists an open set $\mathcal{U}$ of such diffeomorphisms such that if $F_S\in \mathcal{U}$ then its measure of maximal entropy is unique, hyperbolic and, generically, describes the distribution of periodic points. Moreover, the non-wandering set of such an $F_S\in \mathcal{U}$ contains closed invariant subsets carrying entropy arbitrarily close to the topological entropy of $F_S$ and within which the dynamics is conjugate to a subshift of finite type. Under an additional assumption on the base dynamics, we verify that $F_S$ preserves a unique SRB measure, which is physical, whose basin has full Lebesgue measure and coincides with the measure of maximal entropy. We also prove that there exists a residual subset $\mathcal{R}$ of $\mathcal{U}$ such that if $F_S\in \mathcal{R}$ then the topological and periodic entropies of $F_S$ are equal, $F_S$ is asymptotic per-expansive, has a sub-exponential growth rate of the periodic orbits and admits a principal strongly faithful symbolic extension with embedding.

In this monograph we consider the general setting of conformal graph directed Markov systems modeled by countable state symbolic subshifts of finite type. We deal with two classes of such systems: attracting and parabolic. The latter being treated by means of the former. We prove fairly complete asymptotic counting results for multipliers and diameters associated with preimages or periodic orbits ordered by a natural geometric weighting. We also prove the corresponding Central Limit Theorems describing the further features of the distribution of their weights. These results have direct applications to a wide variety of examples, including the case of Apollonian Circle Packings, Apollonian Triangle, expanding and parabolic rational functions, Farey maps, continued fractions, Mannenville-Pomeau maps, Schottky groups, Fuchsian groups, and many more. This gives a unified approach which both recovers known results and proves new results. Our new approach is founded on spectral properties of complexified Ruelle–Perron–Frobenius operators and Tauberian theorems as used in classical problems of prime number theory.

International audience; In this exploratory paper, I will first introduce a notion of stability, more lengthily described in a previous article. In this framework, I will then exhibit an unstable aperiodic tiling. Finally, by building upon the folkloric embedding of Turing machines into Robinson tilings, we will see that the question of stability is undecidable.