Search

In the light of recent developments of the ${\mathcal S}$-adic study of subshifts, we revisit, within this framework, a well-known result on Toeplitz subshifts due to Jacobs--Keane giving a sufficient combinatorial condition to ensure discrete spectrum.We show that the notion of coincidences, originally introduced in the '$70$s for the study of the discrete spectrum of substitution subshifts, together with the ${\mathcal S}$-adic structure of the subshift allow to go deeper in the study of Toeplitz subshifts. We characterize spectral properties of the factor maps onto the maximal equicontinuous topological factors by means of coincidences density.We also provide an easy to check necessary and sufficient condition to ensure unique ergodicity for constant length ${\mathcal S}$-adic subshifts.

We provide an explicit S-adic representation of rank one subshifts with bounded spacers and call the subshifts obtained in this way ''Ferenczi subshifts''. We aim to show that this approach is very convenient to study the dynamical behavior of rank one systems. For instance, we compute their topological rank, the strong and the weak orbit equivalence class. We observe that they have an induced systems that is a Toeplitz subshift having discrete spectrum. We also characterize continuous and non continuous eigenvalues of minimal Ferenczi subshifts.

We give a description of the link between topological dynamical systems and their dimension groups. The focus is on minimal systems and, in particular, on substitution shifts. We describe in detail the various classes of systems including Sturmian shifts and interval exchange shifts. This is a preliminary version of a book which will be published by Cambridge University Press. Any comments are of course welcome.

Minimal Cantor systems of finite topological rank (that can be represented by a Bratteli-Vershik diagram with a uniformly bounded number of vertices per level) are known to have dynamical rigidity properties. We establish that such systems, when they are expansive, define the same class of systems, up to topological conjugacy, as primitive and recognizable ${\mathcal S}$-adic subshifts. This is done establishing necessary and sufficient conditions for a minimal subshift to be of finite topological rank. As an application, we show that minimal subshifts with non-superlinear complexity (like all classical zero entropy examples) have finite topological rank. Conversely, we analyze the complexity of ${\mathcal S}$-adic subshifts and provide sufficient conditions for a finite topological rank subshift to have a non-superlinear complexity. This includes minimal Cantor systems given by Bratteli-Vershik representations whose tower levels have proportional heights and the so called left to right ${\mathcal S}$-adic subshifts. We also exhibit that finite topological rank does not imply non-superlinear complexity. In the particular case of topological rank 2 subshifts, we prove their complexity is always subquadratic along a subsequence and their automorphism group is trivial., Comment: Comments welcome!

Dimension groups are complete invariants of strong orbit equivalence for minimal Cantor systems. This paper studies a natural family of minimal Cantor systems having a finitely generated dimension group, namely the primitive unimodular proper S-adic subshifts. They are generated by iterating sequences of substitutions. Proper substitutions are such that the images of letters start with a same letter, and similarly end with a same letter. This family includes various classes of subshifts such as Brun subshifts or dendric subshifts, that in turn include Arnoux-Rauzy subshifts and natural coding of interval exchange transformations. We compute their dimension group and investigate the relation between the triviality of the infinitesimal subgroup and rational independence of letter measures. We also introduce the notion of balanced functions and provide a topological characterization of bal-ancedness for primitive unimodular proper S-adic subshifts.

We prove decidability results on the existence of constant subsequences of uniformly recurrent morphic sequences along arithmetic progressions. We use spectral properties of the subshifts they generate to give a first algorithm deciding whether, given p $\in$ N, there exists such a constant subsequence along an arithmetic progression of common difference p. In the special case of uniformly recurrent automatic sequences we explicitely describe the sets of such p by means of automata.

Classification is a central problem for dynamical systems, in particular for families that arise in a wide range of topics, like substitution subshifts. It is important to be able to distinguish whether two such subshifts are isomorphic, but the existing invariants are not sufficient for this purpose. We first show that given two minimal substitution subshifts, there exists a computable constant $R$ such that any factor map between these subshifts (if any) is the composition of a factor map with a radius smaller than $R$ and some power of the shift map. Then we prove that it is decidable to check whether a given sliding block code is a factor map between two prescribed minimal substitution subshifts. As a consequence of these two results, we provide an algorithm that, given two minimal substitution subshifts, decides whether one is a factor of the other and, as a straightforward corollary, whether they are isomorphic., Comment: 65 pages

In this article we study automorphisms of Toeplitz subshifts. Such groups are abelian and any finitely generated torsion subgroup is finite and cyclic. When the complexity is non superlinear, we prove that the automorphism group is, modulo a finite cyclic group, generated by a unique root of the shift. In the subquadratic complexity case, we show that the automorphism group modulo the torsion is generated by the roots of the shift map and that the result of the non superlinear case is optimal. Namely, for any $\varepsilon > 0$ we construct examples of minimal Toeplitz subshifts with complexity bounded by $C n^{1+\epsilon}$ whose automorphism groups are not finitely generated. Finally, we observe the coalescence and the automorphism group give no restriction on the complexity since we provide a family of coalescent Toeplitz subshifts with positive entropy such that their automorphism groups are arbitrary finitely generated infinite abelian groups with cyclic torsion subgroup (eventually restricted to powers of the shift).

Moss\'e proved that primitive morphisms are recognizable. In this paper we give a computable upper bound for the constant of recognizability of such a morphism. This bound can be expressed only using the cardinality of the alphabet and the length of the longest image under the morphism of a letter.

A minimal Cantor system is said to be self-induced whenever it is conjugate to one of its induced systems. Substitution subshifts and some odometers are classical examples, and we show that these are the only examples in the equicontinuous or expansive case. Nevertheless, we exhibit a zero entropy self-induced system that is neither equicontinuous nor expansive. We also provide non-uniquely ergodic self-induced systems with infinite entropy.Moreover, we give a characterization of self-induced minimal Cantor systems in terms of substitutions on finite or infinite alphabets.

In this article we characterize measure theoretical eigenvalues of Toeplitz Bratteli-Vershik minimal systems of finite topological rank which are not associated to a continuous eigenfunction. Several examples are provided to illustrate the different situations that can occur.

In this article we give necessary and sufficient conditions that a complex number must satisfy to be a continuous eigenvalue of a minimal Cantor system. Similarly, for minimal Cantor systems of finite rank, we provide necessary and sufficient conditions for having a measure theoretical eigenvalue. These conditions are established from the combinatorial information of the Bratteli-Vershik representations of such systems. As an application, from any minimal Cantor system, we construct a strong orbit equivalent system without irrational eigenvalues which shares all measure theoretical eigenvalues with the original system. In a second application a minimal Cantor system is constructed satisfying the so-called maximal continuous eigenvalue group property., Comment: 45 pages, sections reorganized, examples and applications added

In this article we study the automorphism group ${\rm Aut}(X,\sigma)$ of subshifts $(X,\sigma)$ of low word complexity. In particular, we prove that Aut$(X,\sigma)$ is virtually $\mathbb{Z}$ for aperiodic minimal subshifts and certain transitive subshifts with non-superlinear complexity. More precisely, the quotient of this group relative to the one generated by the shift map is a finite group. In addition, we show that any finite group can be obtained in this way. The class considered includes minimal subshifts induced by substitutions, linearly recurrent subshifts and even some subshifts which simultaneously exhibit non-superlinear and superpolynomial complexity along different subsequences. The main technique in this article relies on the study of classical relations among points used in topological dynamics, in particular, asymptotic pairs. Various examples that illustrate the technique developed in this article are provided. In particular, we prove that the group of automorphisms of a $d$-step nilsystem is nilpotent of order $d$ and from there we produce minimal subshifts of arbitrarily large polynomial complexity whose automorphism groups are also virtually $\mathbb{Z}$., Comment: The paper was reorganized according to the referee's comments and some proofs explained in more detail

We prove that any unimodular Pisot substitution subshift is measurably conjugate to a domain exchange in an Euclidean space which is a finite topological extension of a translation on a torus.This generalizes the pioneer works of Rauzy and Arnoux-Ito providing geometric realizations to any unimodular Pisot substitution without any additional combinatorial condition., Comment: 30p. Modifications after referee's comments

We give conditions on the subgroups of the circle to be realized as the subgroups of eigenvalues of minimal Cantor systems belonging to a determined strong orbit equivalence class. Actually, the additive group of continuous eigenvalues E(X,T) of the minimal Cantor system (X,T) is a subgroup of the intersection I(X,T) of all the images of the dimension group by its traces. We show, whenever the infinitesimal subgroup of the dimension group associated to (X,T) is trivial, the quotient group I(X,T)/E(X,T) is torsion free. We give examples with non trivial infinitesimal subgroups where this property fails. We also provide some realization results., Comment: 18 p

In this note we apply a substantial improvement of a result of S. Ferenczi on $S$-adic subshifts to give Bratteli-Vershik representations of these subshifts., Comment: 6 pages

The $S$-adic conjecture claims that there exists a condition $C$ such that a sequence has a sub-linear complexity if and only if it is an $S$-adic sequence satisfying Condition $C$ for some finite set $S$ of morphisms. We present an overview of the factor complexity of $S$-adic sequences and we give some examples that either illustrate some interesting properties or that are counter-examples to what could be believed to be "a good Condition $C$"., Comment: 25

In this article we study conditions to be a continuous or a measurable eigenvalue of finite rank minimal Cantor systems, that is, systems given by an ordered Bratteli diagram with a bounded number of vertices per level. We prove that continuous eigenvalues always come from the stable subspace associated to the incidence matrices of the Bratteli diagram and we study rationally independent generators of the additive group of continuous eigenvalues. Given an ergodic probability measure, we provide a general necessary condition to be a measurable eigenvalue. Then we consider two families of examples. A first one to illustrate that measurable eigenvalues do not need to come from the stable space. Finally we study Toeplitz type Cantor minimal systems of finite rank. We recover classical results in the continuous case and we prove measurable eigenvalues are always rational but not necessarily continuous., Comment: Ergodic Theory and Dynamical Systems (2010) 26

In this paper are characterized the polynomials, in terms of their coefficients, that have all their orbits dense in the set of 3-adic integers., Comment: Published in Bulletin of the London Mathematical Society in 2009

We prove that the uniform recurrence of morphic sequences is decidable. For this we show that the number of derived sequences of uniformly recurrent morphic sequences is bounded. As a corollary we obtain that uniformly recurrent morphic sequences are primitive substitutive sequences.

In this paper we prove the decidability of the HD0L ultimate periodicity problem.

In this paper I would like to witness the mathematical inventiveness of G. Rauzy through personnal exchanges I had with him. The objects that will emerge will be used to treat the decidability of the HD 0 L $\omega$-equivalence and periodicity problems in the primitive case.

A celebrated result of Morse and Hedlund, stated in 1938, asserts that a sequence $x$ over a finite alphabet is ultimately periodic if and only if, for some $n$, the number of different factors of length $n$ appearing in $x$ is less than $n+1$. Attempts to extend this fundamental result, for example, to higher dimensions, have been considered during the last fifteen years. Let $d\ge 2$. A legitimate extension to a multidimensional setting of the notion of periodicity is to consider sets of $\ZZ^d$ definable by a first order formula in the Presburger arithmetic $<\ZZ;<,+>$. With this latter notion and using a powerful criterion due to Muchnik, we exhibit a complete extension of the Morse--Hedlund theorem to an arbitrary dimension $d$ and characterize sets of $\ZZ^d$ definable in $<\ZZ;<,+>$ in terms of some functions counting recurrent blocks, that is, blocks occurring infinitely often.

The seminal theorem of Cobham has given rise during the last 40 years to a lot of works around non-standard numeration systems and has been extended to many contexts. In this paper, as a result of fifteen years of improvements, we obtain a complete and general version for the so-called substitutive sequences. Let $\alpha$ and $\beta$ be two multiplicatively independent Perron numbers. Then, a sequence $x\in A^\mathbb{N}$, where $A$ is a finite alphabet, is both $\alpha$-substitutive and $\beta$-substitutive if and only if $x$ is ultimately periodic.

We associate in a canonical way a substitution to any abstract numeration system built on a regular language. In relationship with the growth order of the letters, we define the notion of two independent substitutions. Our main result is the following. If a sequence $x$ is generated by two independent substitutions, at least one being of exponential growth, then the factors of $x$ appearing infinitely often in $x$ appear with bounded gaps. As an application, we derive an analogue of Cobham's theorem for two independent substitutions (or abstract numeration systems) one with polynomial growth, the other being exponential.

We prove that a subshift $(X,T)$ is linearly recurrent if and only if it is a primitive and proper $S$-adic subshift. This corrects Proposition 6 in F. Durand ({\it Ergod. Th. & Dynam. Sys. {\bf 20}} (2000), 1061--1078).

In this paper we provide examples of topological dynamical systems having either finite or countable scrambled sets. In particular we study conditions for the existence of Li-Yorke, asymptotic and distal pairs in constant--length substitution dynamical systems. Starting from a circle rotation we also construct a dynamical system having Li--Yorke pairs, none of which is recurrent.

This paper is devoted to the study of limit laws of entrance times to cylinder sets for Cantor minimal systems of zero entropy using their representation by means of ordered Bratteli diagrams. We study in detail substitution subshifts and we prove these limit laws are piecewise linear functions. The same kind of results is obtained for classical low complexity systems given by non stationary ordered Bratteli diagrams.

The purpose of this paper is to study ergodic averages with deterministic weights. More precisely we study the convergence of the ergodic averages of the type $\frac{1}{N} \sum_{k=0}^{N-1} \theta (k) f \circ T^{u_k}$ where $\theta = (\theta (k) ; k\in \NN)$ is a bounded sequence and $u = (u_k ; k\in \NN)$ a strictly increasing sequence of integers such that for some $\delta<1$ $$ S_N (\theta, u) := \sup_{\alpha \in \pRR} | \sum_{k=0}^{N-1} \theta (k) \exp (2i\pi \alpha u_k) | = O (N^{\delta}) \leqno{({\cal H}_1)} $$ i.e., there exists a constant $C$ such that $S_N (\theta, u) \leq C N^{\delta} $. We define $\delta (\theta, u)$ to be the infimum of the $\delta $ satisfying $\H_1$ for $\theta $ and $u$.

A minimal subshift $(X,T)$ is linearly recurrent if there exists a constant $K$ so that for each clopen set $U$ generated by a finite word $u$ the return time to $U$, with respect to $T$, is bounded by $K|u|$. We prove that given a linearly recurrent subshift $(X,T)$ the set of its non-periodic subshift factors is finite up to isomorphism. We also give a constructive characterization of these subshifts.

The present paper explores substitution minimal systems and their relation to stationary Bratteli diagrams and stationary dimension groups. The constructions involved are algorithmic and explicit, and render an effective method to compute an invariant of (ordered) $K$-theoretic nature for these systems. This new invariant is independent of spectral invariants which have previously been extensively studied. Before we state the main results we give some background.

If a non-periodic sequence $X$ is the image by a morphism of a fixed point of both a primitive substitution $\sigma$ and a primitive substitution $\tau$, then the dominant eigenvalues of the matrices of $\sigma$ and of $\tau$ are multiplicatively dependent. This is the way we propose to generalize Cobham's Theorem.

We prove that a sequence is primitive substitutive if and only if the set of its derived sequences is finite; we defined these sequences here.

We study the boundary of the 3-dimensional Rauzy fractal ${\mathcal E} \subset \RR \times \CC$ generated by the polynomial $P(x) = x^4-x^3-x^2-x-1$. The finite automaton characterizing the boundary of ${\mathcal E}$ is given explicitly. As a consequence we prove that the set ${\mathcal E}$ has 18 neighborhoods where 6 of them intersect the central tile ${\mathcal E}$ in a point. Our construction shows that the boundary is generated by an iterated function system starting with 2 compact sets., Comment: 19 pages

We prove linearly repetitive Delone systems have finitely many Delone system factors up to conjugacy. This result is also applicable to linearly repetitive tiling systems., Comment: 15 pages

We give necessary and sufficient conditions to have measurable and continuous eigenfunctions for linearly recurrent Cantor dynamical systems. We also construct explicitly an example of linearly recurrent system with nontrivial Kronecker factor and a trivial maximal equicontinuous factor., Comment: 18 pages

The class of linearly recurrent Cantor systems contains the substitution subshifts and some odometers. For substitution subshifts and odometers measure--theoretical and continuous eigenvalues are the same. It is natural to ask whether this rigidity property remains true for the class of linearly recurrent Cantor systems. We give partial answers to this question.

In this article we generalize Cobham theorem to a large class of substitutions including non primitive and non constant length substitutions.

We say $x \in \{0,1,2 \}^{\NN}$ is a word with Sturmian erasures if for any $a\in \{0,1,2 \}$ the word obtained erasing all $a$ in $x$ is a Sturmian word. A large family of such words is given coding trajectories of balls in the game of billiards in the cube. We prove that the monoid of morphisms mapping all words with Sturmian erasures to words with Sturmian erasures is not finitely generated.

Let U and V be two Bertrand numeration systems, and, a and b the two Parry numbers there are naturally associated with. Suppose they are multiplicatively independent. We prove that, if E is a subset of positive integers which is both U and V recognizable, then E is a finite union of arithmetical progressions.

We give a new proof of the Cobham's first theorem using ideas from symbolic dynamics and of the Cobham-Semenov theorem (in the primitive case) using ideas from tiling dynamics., Comment: 24 pages

In this paper we prove that if two self-similar tiling systems, with respective stretching factors $\lambda_1$ and $\lambda_2$, have a common factor which is a non periodic tiling system, then $\lambda_1$ and $\lambda_2$ are multiplicatively dependent.