1 Introduction↩︎

The study of language density can be traced back to the work of Schützenberger in the 60s [1], Berstel in the 70s [2], and Hansel and Perrin in the 80s [3]. The idea also appears in Eilenberg’s monograph [4] and in the monograph by Berstel, Perrin and Reutenauer [5]. These earlier works, motivated mainly by automata theory and the theory of codes, focused on density with respect to Bernoulli measures (see Section 4).

In the present paper, we draw our motivation from symbolic dynamics and turn to ergodic measures on shift spaces. Within this setting, the density of a given language can be understood as the frequency (with respect to some given ergodic measure) of some pattern in the shift space – for example a pattern like “words with an even number of a given letter.” More precisely, given a shift \(X\) on the alphabet \(A\) endowed with a shift-invariant probability measure \(\mu\), and \(L \subseteq A^*\) a language, the density \(\delta_\mu(L)\) of \(L\) under the measure \(\mu\) is defined as the Cesàro limit of \(\mu(\{ u\in L : |u|=n\})\) as \(n\to\infty\), whenever it exists.

We restrict our attention to group languages, i.e. languages recognized by morphisms onto finite groups: by fixing a morphism \(\varphi\colon A^*\to G\) onto a finite group \(G\), we consider a language of the form \(L=\varphi^{-1}(K)\), \(K\subseteq G\). The density of the languages of this form can be understood using a skew product (sometimes called a group extension), which, briefly put, is a dynamical system built from a group \(G\), together with a dynamical system acting on \(G\). In our case, we consider a first dynamical system, a shift \(X\) over \(A\) which supports a measure \(\mu\), which is then enriched through an action on a finite group \(G\) defined via a morphism \(\varphi\). This yields a further dynamical system, the skew product, which is governed both by the dynamics of the original system \(X\), and by the algebraic structure of the group \(G\). A precise definition of the skew products used in this paper may be found at the beginning of Section 3. The key idea in this paper is that the density can be expressed in terms of limits of ergodic sums in a skew product (cf. Theorem [t:first-main]). This allows us to show that the density always exists and, under suitable conditions, to calculate it. This approach is strongly related with foundational work by Furstenberg, Veech, Schmidt, and Zimmer (among others) on ergodic properties of skew products [6]–[10]. Veech’s work in particular is concerned with a special case of the very same notion of density studied here, and it played a key role in guiding our investigation.

Given a shift space \(X\) with an ergodic measure \(\mu\), one of our main results relates the density \(\delta_\mu(L)\) with ergodic measures on the skew product between \(X\) and \(G\), denoted \(G\rtimes_{\varphi}X\), where the skewing function is the cocycle determined by \(\varphi\) (a skewing function which depends only on the symbol at the zero coordinate of elements of the shift). We say that a measure \(\overline{\mu}\) on the skew product projects to \(\mu\) if \(\overline{\mu}(G\times B) = \mu(B)\) for every measurable \(B\subseteq X\).

The result is proved in Section 3. The proof uses the known fact that the skew product always admits an ergodic measure \(\overline{\mu}\) that projects to \(\mu\) (see Lemma 2). A natural candidate for the measure \(\overline{\mu}\) is the product measure \(\nu\times\mu\), where \(\nu\) is the uniform probability measure on \(G\). When \(\nu\times\mu\) happens to be ergodic, then the above formula takes on the following very simple form (see Corollary 1): \[\delta_\mu(L)= \sum_{g \in G} (\nu\times\mu)(\{g\}\times X) \, (\nu\times\mu)(gK\times X)=\sum_{g\in G}(1/|G|)(|gK|/|G|) = |K|/|G|.\] However this is not always the case: see for instance Examples 5, 19, 25 and 26. We also introduce in Section 3.3 a pointwise version of density (Definition 2). This leads to a further proof of the existence of the density of group languages, expressed as an integral over pointwise densities.

In the rest of the paper we apply Theorem [t:first-main] to two cases: when \(\mu\) is a Markov measure on a shift of finite type, and when \(\mu\) is an ergodic measure on a minimal shift space. In the former case, we present a characterization of ergodicity of the product measure \(\nu\times\mu\) when \(\mu\) is an \(r\)-step Markov measure, \(r\geq 1\), meaning that \[\mu(x_m = a \mid x_{[0,m)} = w) = \mu(x_m=a \mid x_{[m-r,m)} = w_{[m-r,m)})\] for all words \(w\) of length \(m\geq r\) such that \(\mu(x_m = a \mid x_{[0,m)} = w)\neq 0\). We define for this purpose a suitable notion of irreducibility, called \(\varphi\)-irreducibility (Definition 3), which leads to the following theorem.

When \(\mu\) is a Bernoulli measure, the above result also follows from the work of Hansel and Perrin [3], which uses a completely different approach based on the theory of codes. We provide a survey of this approach in Section 4.

In the case of minimal shift spaces, we specialize Theorem [t:first-main] into a formula which holds under the condition that \(\nu\times\mu\) is ergodic on the minimal closed invariant subsets of \(G\rtimes_{\varphi}X\). This generalizes the simple formula found when the product measure \(\nu\times\mu\) is ergodic.

Let us briefly present the notion, inspired by [11], which lies at the core of this more general formula. Given a subgroup \(H\leq G\), a map \(\alpha\) from \(X\) to the right coset space \(H\backslash G\) is called a cobounding map mod \(H\) if it satisfies the following coboundary type equation, where \(S\) denotes the shift map: \[\alpha(Sx) = \alpha(x)\varphi(x_0).\]

The term cobounding appears for instance in a paper by Baggett et al. [12]; the terms transfer function and intertwining have also been used with similar meanings in [12]–[14]. As the name suggests, this notion is related with cocycles and coboundaries and more broadly to the long history of cohomology in ergodic theory. Besides [11] and the previously mentioned work of Furstenberg, Veech, Schmidt and Zimmer, we drew inspiration also from [15], [16]. The following theorem is our third main result; its statement uses a natural partial order on cobounding maps which is introduced in Section 7.2.

Behind this last result is a bijection between the minimal closed invariant subsets of \(G\rtimes_{\varphi} X\) and the cobounding maps which are minimal under the aforementioned partial order (Proposition 27). This entails, among other things, that whenever \(X\) is minimal, \(\nu\times\mu\) can be ergodic only when \(G\rtimes_{\varphi} X\) itself is minimal (Corollary 3). The formula in Theorem [t:third-main] is derived from Theorem [t:first-main], where the role of the ergodic measure \(\overline{\mu}\) is played by an appropriate rescaling of the measure \(\nu\times\mu\), with \(\nu\) being the uniform probability measure on \(G\). This rescaling explains the factor \(1/|H|\) in the formula.

Theorem [t:third-main] motivates further study of the structure of the skew products between minimal shifts and finite groups, which includes a characterization of minimality of such skew products in terms of return words (Theorem 20). We first give a combinatorial proof of this characterization using the theory of bifix codes, inspired by ideas from earlier works [17], [18]. Later on, we show that the same conclusion can be reached using cobounding maps (Proposition 30).

Having in mind Theorem [t:third-main], we also provide sufficient conditions for ergodicity of \(\nu\times\mu\) on minimal closed invariant subsets of \(G\rtimes_{\varphi} X\). A first condition is given in Corollary 5 combined with Proposition 32, and a second one, restricted to the case of shift spaces generated by primitive substitutions, is given in Proposition 33. We deduce as a corollary of the second condition that substitutive dendric shifts (definitions are recalled in Section 8) have ergodic skew products with all finite groups, and consequently the density of \(L= \varphi^{-1}(K)\) is simply \(|K|/|G|\), \(K\subseteq G\) (see Corollary 1).

Here is an example of what these results tell us about specific systems. Consider the Fibonacci shift on the two-letter alphabet \(\{a,b\}\), whose definition is recalled in Section 3.4. For each word \(w\) in the language of the shift space, denote by \(|w|_a\) the number of occurrences of \(a\) in \(w\). Then, we can apply Theorem [t:first-main] to deduce that the average probability over sufficiently long words \(w\) that \(|w|_a\) is congruent to \(r\) mod \(m\) is approximately \(1/m\), for each \(r=0,\ldots, m-1\). However the convergence of these probabilities holds only in the sense of Cesàro mean. This specific example with \(m=2\) is developed in detail in Section 3.4.

There have been previous results of a similar nature concerning equidistribution modulo \(m\). For instance, Veech [7], [8] studied the parity of the number of visits to an interval by the orbit of a point under an irrational rotation (see Example 7), and Jager and Liardet [19] studied the congruence classes of the matrices in \(\operatorname{GL}(2,\mathbb{Z})\) associated with continued fraction expansions of real numbers see Example 10. We also revisit these results in Section 9 in the particular case of Sturmian shifts. In each case, it is ergodicity of a relevant skew product that implies equidistribution among cosets. Our approach provides still more examples. These examples include the Thue–Morse shift (explored in Examples 1 and 25) and the case of substitutive dendric shifts (presented in Section 8.2), which includes substitutive Sturmian shifts and substitutive codings of interval exchanges.

Let us give a brief overview of the paper’s structure. Section 2 gives some preliminaries on symbolic dynamics. Section 3 recalls the definition of skew products and gives an elementary proof of our first main result, Theorem [t:first-main], which shows in particular that the density always exists. We also provide an alternative proof of the existence using a pointwise version of density. We then survey the original approach to density under Bernoulli measures in Section 4, relying on notions from algebraic theory of formal languages. The study of the density for shifts of finite type is then handled in Theorem [t:second-main] together with a discussion on various notions of irreducibility. Section 6 contains the material on bifix codes and a characterization of minimal skew products in terms of return words. Our third main result, Theorem [t:third-main], is presented in Section 7, where cobounding maps are studied. The section also contains a simple sufficient condition for ergodicity of the product measure \(\nu\times\mu\) on minimal closed invariant subsets. In Section 8 we take a closer look at shifts generated by primitive substitutions, and we consider particular examples of skew products based on Sturmian shifts in Section 9.

2 Symbolic dynamics↩︎

Let \(A\) be a finite alphabet. Let \(\varepsilon\) stand for the empty word of the free monoid \({A}^*\) and \(A^+ = A^*\setminus\{\varepsilon\}\). We denote by \(A^\mathbb{Z}\) the set of two-sided infinite words on \(A\). For any word \(w\) in the free monoid \(A^*\) (endowed with concatenation), \(|w|\) denotes the length of \(w\) and \(|w|_a\) stands for the number of occurrences of the letter \(a\) in the word \(w\). We start indexing finite words with 0, so that a word \(w\in A^*\) has the form \(w = w_0w_1\ldots w_{n-1}\), where \(n=|w|\). Given \(0\leq i\leq j< n\), we let \[w_{[i,j)} = w_iw_{i+1}\ldots w_j,\] and we extend a similar notation for infinite words.

A factor of a (finite or infinite) word \(w\) is defined as a finite concatenation of consecutive letters occurring in \(w\), i.e. a word \(u\) is a factor of \(w\) if there exist indices \(i\leq j\) such that \(u = w_{[i,j)}\). If \(w\) is a finite word, then \(u\) is a factor of \(w\) precisely when there are words \(p\) and \(s\) such that \(w = pus\). When \(p = \varepsilon\) (resp., \(s = \varepsilon\)), we say that \(u\) is a prefix (resp., suffix) of \(w\).

An infinite word \(x = (x_n)_{n\in\mathbb{Z}}\) is uniformly recurrent if every word occurring in \(x\) occurs in an infinite number of positions with bounded gaps; in other words, for every factor \(w\) of \(x\), there exists a positive integer \(m\) such that for every \(n\), \(w\) is a factor of \(x_{[n,n+m)}\).

We view closed shift-invariant sets of two-sided infinite words as dynamical systems under the map \(S\), called the shift map, defined by \[S\left( (x_n)_{n\in\mathbb{Z}} \right) = (x_{n+1})_{n\in\mathbb{Z}}.\]

A shift space (also shortened to shift) is a pair \((X,S)\) where \(X\) is a topologically closed and shift-invariant subset of \(A^{\mathbb{Z}}\) for some finite alphabet \(A\). We usually shorten \((X,S)\) as \(X\) when we refer to the system \((X,S)\). The language of \(X\) is defined as the set \(\mathcal{L}(X)\) of factors of elements of \(X\) \[\mathcal{L}(X) = \{ x_{[i,j)} \mid x\in X,\;i, j\in\mathbb{Z},\;i\leq j \}.\] When a shift \(X\) is said to be defined on the alphabet \(A\), we assume that \(A\subseteq\mathcal{L}(X)\).

A shift space is said to be minimal if it admits no proper non-empty closed and shift-invariant subset; equivalently the \(S\)-orbit of every element of \(X\) is dense. Note that a shift space \(X\) is minimal if and only if every infinite word \(x \in X\) is uniformly recurrent. On the other hand, a shift space is called irreducible if there exists an element \(x\in X\) with dense \(S\)-orbit. This is equivalent to the following property of \(\mathcal{L}(X)\): for every \(u,v\in\mathcal{L}(X)\), there exists \(w\in A^*\) such that \(uwv\in \mathcal{L}(X)\).

Let \(X\) be a shift space on \(A\) and fix \(w\in\mathcal{L}(X)\). We denote by \(\mathcal{R}_X(w)\) the set of (right) return words to \(w\). It is, by definition, the set of words \(r\) such that \(rw\) is in \(\mathcal{L}(X)\) and has exactly two factors equal to \(w\), one as a prefix and the other one as a suffix; that is, \[\mathcal{R}_X(w) = \{ r\in A^* \mid rw\in\mathcal{L}(X)\cap wA^*\setminus A^+wA^+\}.\]

Let \(X\subseteq A^\mathbb{Z}\) be a shift space equipped with a Borel probability measure \(\mu\). For \(w\in\mathcal{L}(X)\), we denote \[[w]_X=\{x\in X\mid x_{[0,n)}=w\}\] the right cylinder defined by \(w\) (right refers here to the fact this definition involves only non-negative indices). When \(X\) is clear from context, we often drop the subscript \(X\) and write simply \([w]\). Note that we have \(\mu([\varepsilon])=1\) and \[\sum_{a\in A}\mu([wa])=\mu([w]).\]

The measure \(\mu\) is invariant if \(\mu(S^{-1}U)=\mu(U)\) for every Borel set \(U\subseteq X\). Note that \(\mu\) is invariant if and only if, for every \(w\in\mathcal{L}(X)\), \[\sum_{a\in A}\mu([aw])=\mu([w]).\]

Recall that an invariant measure \(\mu\) is ergodic if every Borel set \(U\) which is invariant (i.e. \(S^{-1}U=U\)) has measure \(0\) or \(1\). A well-known equivalent condition is that \(\mu\) is ergodic if and only if \[\label{eq:ergodic} \lim_{n\to\infty}\frac{1}{n}\sum_{i=0}^{n-1}\mu(U\cap S^{-i}V)=\mu(U)\mu(V),\tag{1}\] for every pair \(U,V\) of Borel sets [20]. If instead of converging on average (i.e. in Cesàro’s sense) the sequence \((\mu(U\cap S^{-n}V))_{n\in\mathbb{N}}\) converges directly to \(\mu(U)\mu(V)\) for all pairs of Borel sets \(U,V\), then the measure is said to be mixing.

The shift \(X\) is said to be uniquely ergodic if there is a unique invariant probability measure on \(X\), in which case this unique measure is necessarily ergodic. An important class of uniquely ergodic shifts is given by primitive substitution shifts, whose definition may be recalled in [21] for instance. By a theorem of Michel, every primitive substitution shift is uniquely ergodic [22]. Other important sufficient conditions for unique ergodicity of shift spaces are due to Boshernitzan [23], [24]. More details on such results may be found in [21], [25].

The aim of this paper is to study the density of languages under a given measure \(\mu\), defined as follows.

In other words, \(\delta_\mu(L)\) is the Cesàro limit of \(\mu([L\cap A^n])\) as \(n\to\infty\). Since \(\mu(w)=0\) when \(w\notin\mathcal{L}(X)\), we have of course that \(\delta_\mu(L)=\delta_\mu(L\cap\mathcal{L}(X))\) and \(\delta_\mu(\mathcal{L}(X))=1\). Moreover, it follows from the definition of density that, whenever \(L\) and \(L'\) are disjoint, \[\delta_\mu(L\cup L') = \delta_\mu(L)+\delta_\mu(L').\] There is also a dual rule for the intersection: when \(L\cup L' = A^*\), the density of the intersection is given by \(\delta_\mu(L\cap L') = \delta_\mu(L)+\delta_\mu(L')-1\).

Note however that the density of a general intersection \(L \cap L'\) might not exist, even when the density of both \(L\) and \(L'\) exist. For instance, if we consider the two languages \[L = \{ w\in A^* : |w|\equiv 1\bmod 2\},\qquad L' = \{ w\in A^* : |w|\equiv\lfloor\log_2(|w|)\rfloor \bmod 2\},\] over some fixed finite alphabet \(A\), then it is not hard to see that \(\delta_\mu(L) = \delta_\mu(L') = \frac{1}{2}\), no matter the probability measure \(\mu\). However, the sequence of Cesàro sums \(s_n = \frac{1}{n}\sum_{i=1}^n\mu([L\cap L'\cap A^{i}])\) has two subsequences \((s_{2^{2n}})_{n\in\mathbb{N}}\) and \((s_{2^{2n+1}})_{n\in\mathbb{N}}\) which converge to \(1/3\) and \(1/6\) respectively. Therefore the sequence of Cesàro sums does not converge, and \(L\cap L'\) does not have a density.

An easy observation is that a finite language has zero density for every measure. This observation can be generalized to a larger class of languages called thin languages, see Section 4.

Next we introduce a language that will serve as a guiding example throughout the paper.

3 Group languages and skew products↩︎

We first recall basic definitions on group languages and skew products in Section 3.1. We then prove Theorem [t:first-main] in Section 3.2. The proof uses any ergodic lift to the skew product of the given ergodic measure on the shift space. We also consider in Corollary 1 the special case where the product between the original measure and the uniform probability measure on the group is ergodic. If the shift space is uniquely ergodic, then this is even equivalent to unique ergodicity of the skew product, cf. Proposition 2. We then consider in Section 3.3 a pointwise version of density. Lastly, we focus on the case of the Fibonacci shift in Section 3.4, where we prove that the density considered as a Cesàro mean converges, whereas the sequence of measures \((\mu([L\cap A^n]))_{n\in\mathbb{N}}\) does not converge in the classical sense.

3.1 First definitions↩︎

A rational language is a language recognized by a finite automaton. Equivalently, a language is rational if and only if it is of the form \(\varphi^{-1}(N)\) where \(\varphi\colon A^*\to M\) is a morphism onto a finite monoid \(M\), and \(N\subseteq M\) is a subset.

A group language is a set of the form \(L = \varphi^{-1}(K)\) where \(\varphi\colon A^*\to G\) is a morphism onto a finite group \(G\) and \(K\subseteq G\). Note that such languages are in particular rational, being recognized by finite groups. For more on the topic, see [5].

Let \(X\) be a minimal shift space equipped with an invariant measure \(\mu\). We consider the skew product of \(G\) and \(X\) with respect to \(\varphi\), denoted \(G\rtimes_\varphi X\): it is the dynamical system \(G\rtimes_\varphi X=(G\times X,T_\varphi)\), where \(T_\varphi\) is the transformation defined by \[\label{eq:Tphi} T_\varphi(g,x)=(g\varphi(x_0),Sx).\tag{2}\]

More generally, \(T_\varphi\) satisfies, for every \(n\in\mathbb{Z}\), \[T_\varphi^n(g,x)=(g\varphi^{(n)}(x),S^nx),\] where \(\varphi^{(n)}\) is defined by \[\label{eq:fn} \varphi^{(n)}(x) = \begin{cases} \varphi(x_{[0,n)}) & \text{if}\;n\geq 0;\\ \varphi(x_{[n,0)})^{-1} & \text{if}\;n<0. \end{cases}\tag{3}\]

The map \((n,x)\mapsto \varphi^{(n)}(x)\) is the cocycle defined by \(\varphi\). When the morphism \(\varphi\) is clear from context, we may simply write \(T\) and \(G\rtimes X\). Skew products constitute one of the basic extensions of dynamical systems; see e.g. [20], [26].

Note that the lemma does not say that \(\Psi\) is surjective on \((G\times A)^\mathbb{Z}\), but simply that \(\Psi\) is a topological conjugacy from \(G\rtimes_{\varphi} X\) to the subshift \(\Psi(G\rtimes_{\varphi} X)\).

3.2 A formula for the density↩︎

The aim of this section is to prove our first main result, Theorem [t:first-main]. The proof uses the existence of an ergodic measure \(\overline{\mu}\) on the skew product which projects to \(\mu\) (see Lemma 2 below). This known fact follows from classical results in ergodic theory (see for example [27]–[30]); we provide a proof for the sake of completeness. Let us recall briefly that a factor map between two dynamical systems \((Z,R)\) and \((Y,T)\) is a map \(\pi\colon Z\to Y\) which is onto and satisfies \(\pi\circ R = T\circ\pi\).

Let us recall now our first main result, which expresses the density of a group language in a shift space in terms of an ergodic measure on the skew product \(G\rtimes X\). This will later be specialized for shifts of finite type (Section 5), and then for minimal shifts (Section 7).

In case \(\nu\times\mu\) is ergodic on the skew product, the above theorem yields the following simple formula for the density.

There are however many examples where \(\nu\times\mu\) is not ergodic on the skew product, such as the simple one below.

Next we show that if \(X\) is uniquely ergodic, then ergodicity of \(\nu\times\mu\) implies unique ergodicity of \(G\rtimes_{\varphi} X\). This is used e.g. in Example 9. It was proved by Veech [7] for the case where \(X\) is a binary coding of an irrational rotation and \(G=\mathbb{Z}/2\mathbb{Z}\). We show below how Veech’s argument can be adapted in a straightforward way to the case where \(X\) is any uniquely ergodic shift and \(G\) is a finite group. The result is true more generally when \(G\) is a compact group with normalized Haar measure \(\nu\), cf. [30].

3.3 Pointwise densities↩︎

We show in this section that the concept of density of a language can be adapted to Cesàro averages along orbits of individual points (see Theorem 3). This leads to another proof of the fact the density always exists for group languages (as stated in Theorem [t:first-main]) and an expression for the density as an integral of pointwise densities. For the definition of the pointwise density below, we recall the notation \(\varphi^{(i)}(x) = \varphi(x_{[0,i)})\) from 3 .

The main result of the section, namely Theorem 3, states the a.e. existence of pointwise densities for all group languages under all invariant measures.

We now turn to Theorem 3. First, let us recall part of Birkhoff’s Ergodic Theorem; for a complete statement see [20]. Let \((X,T)\) be a dynamical system with an invariant probability measure \(\mu\). Given an \(\mathrm{L}^1\) map \(f\colon X\to\mathbb{R}\), let us define the time average of \(f\) as \[\overline{f}(x) = \lim_{n\to\infty}\frac{1}{n}\sum_{k=0}^{n-1}f(T^kx),\] whenever it exists. The Ergodic Theorem states that \(\overline{f}\) exists \(\mu\)-a.e and moreover \[\int_X \overline{f}\, d\mu = \int_X f\, d\mu.\]

We now give two examples which show how our equidistribution statement, namely Corollary 1, together with the unique ergodicity result from Proposition 2, can be applied in this pointwise setting. Both examples will be pursued in Section 9 for Sturmian shifts (see Examples 32 and 33).

In the next example, we consider a skew product with a non-Abelian skewing group, namely \(G(2)= \operatorname{GL}(2, {\mathbb{Z}}/2{\mathbb{Z}})\), i.e. the group of \(2 \times 2\) matrices with entries in \(\mathbb{Z}/2\mathbb{Z}\) and determinant \(1\). The example could also be carried out with \(G(m)\) for arbitrary \(m\geq 2\), but we treat only the case \(m=2\) for simplicity. It is inspired by the work of Jager and Liardet [19] (see also [32]–[34] for related works), and is motivated by distribution properties for convergents in continued fraction expansions.

3.4 An example in the substitutive Fibonacci shift↩︎

We now proceed to illustrate Theorem [t:first-main] (and more specifically Corollary 1, see also Example 7) in the substitutive Fibonacci shift, whose precise definition is recalled below. We consider the language \(L = \varphi^{-1}(0)\) where \(\varphi\colon\{a,b\}^*\to\mathbb{Z}/2\mathbb{Z}\) is the morphism defined by \(\varphi(a) = 1\) and \(\varphi(b)=0\); in other words, \[L = \{ w\in \{a,b\}^* : |w|_a \equiv 0 \bmod 2\}.\]

We show that \(\delta_\mu(L)=1/2\) for \(\mu\) the unique ergodic measure on the substitutive Fibonacci shift (Proposition 5), but also that the sequence \((\mu([L\cap A^n]))_{n\in\mathbb{N}}\) does not converge in the classical sense (Proposition 6). In particular, the measure \(\nu\times\mu\) on the skew product is ergodic but not mixing, cf. Remark 1.

Consider the substitution \(\sigma\colon a\mapsto ab, b\mapsto a\), called the Fibonacci substitution. The substitution \(\sigma\) is primitive; thus the shift space \(X=X(\sigma)\) generated by \(\sigma\), called the substitutive Fibonacci shift, or Fibonacci shift for short, is uniquely ergodic by Michel’s theorem (this alternatively follows from Boshernitzan’s criterion [23]). Its unique ergodic measure \(\mu\) viewed as a map on \(\mathcal{L}(X)\) is depicted in Figure 3.

We next prove that the skew product of the Fibonacci shift with \(\mathbb{Z}/2\mathbb{Z}\) for the skewing function determined by \(\varphi\) is also uniquely ergodic, as an application of Michel’s theorem. The argument is a special case of the general method described in Section 8.

As an immediate consequence of Corollary 1 (see also Example 7), we conclude that the density \(\delta_\mu(L)\), where \(L = \{ w\in \{a,b\}^*: |w|_a \equiv 0 \bmod 2\}\), exists and is \(1/2\). In other words, the sequence \((\mu([L\cap A^n]))_{n\in\mathbb{N}}\) converges to \(1/2\) in Cesàro’s sense, even though, as we next show, the sequence itself does not converge (this is in contrast with Example 17 where \(\nu\times \mu\) is mixing). The rest of the section is devoted to the proof of the following result where \(F = (F(n))_{n\in\mathbb{N}}\) is the Fibonacci number sequence (starting with \(F(0)=0\), \(F(1)=1\)).

The proof relies on a number of key facts about the structure of the language of the Fibonacci shift. An important tool is the notion of special word. Recall that, for a general shift space \(X\subseteq A^\mathbb{Z}\), a word \(w\in \mathcal{L}(X)\) is called left special if \(aw, bw\in \mathcal{L}(X)\) for some \(a,b\in A\), \(a\neq b\); it is called right special if instead \(wa, wb\in\mathcal{L}(X)\) for some \(a,b\in A\), \(a\neq b\); and it is called bispecial if it is both left and right special. Since it is Sturmian, the Fibonacci shift has the property that for every \(n\in\mathbb{N}\), \(\mathcal{L}(X)\cap A^n\) contains exactly one left and one right special factor (which might or might not coincide). We next establish two lemmas which are central in the proof of Proposition 6.

4 The case of Bernoulli measures↩︎

This section gives a brief account of the original approach to densities under Bernoulli measures due to Schützenberger [1], Berstel [2], and Hansel and Perrin [3] with an approach based on the algebraic theory of formal languages. Details may be found in the monograph [5].

A probability measure \(\mu\) on the full shift \(A^\mathbb{Z}\) is a Bernoulli measure when the map \(A^*\to [0,1]\) induced by evaluating \(\mu\) on cylinders is a morphism. More explicitly, \[\mu([uv]) = \mu([u])\mu([v]) \quad \text{and}\quad\sum_{a\in A}\mu(a)=1.\] A Bernoulli measure is called positive if \(\mu([a])>0\) for all \(a\in A\). The simplest example of a positive Bernoulli measure is that of the uniform distribution given by \(\mu([a])=1/|A|\).

A first result on densities under Bernoulli measures is the following, which generalizes the simple observation that finite languages have zero density. We say that a language \(L\subseteq A^*\) is thin if there is a word \(w\in A^*\) which does not appear in any word of \(L\) as a factor.

Recall that a rational language is a language recognized by a finite automaton, which may without loss of generality be assumed to be complete. Formally this means that there is a triple \(\mathcal{A}= (Q,i,F)\) where \(Q\) is a finite set of states on which \(A^*\) acts on the right, \(i\in Q\) is the initial state, and \(F\subseteq Q\) is the set of final states, and such that \(L = \{w\in A^*\mid i\cdot w\in F\}\).

For rational languages, we have the following converse of Proposition 7. We provide a sketch of proof using notions from the algebraic theory of formal languages which may be recalled in [5].

Note however that the previous proposition fails for non-rational languages: take for instance \[L=\{a^nw\mid n\ge 0,w\in\{a,b\}^n\}.\] Then one has \(\mu([L\cap A^{2n}])=1/\mu([a])^n\), which implies \(\delta_\mu(L)=0\). However \(L\) is clearly not thin, since every word appears as a suffix.

Next we give a proof of the fact that the density of a rational language under a Bernoulli measure always exists.

We end with a discussion on prefix codes, a notion which also appears later in Section 6. A prefix code is a subset \(U\subseteq A^*\) where no word is a strict prefix of another. Any prefix code must satisfy \(\mu([U])\leq 1\) for any Bernoulli measure \(\mu\), cf. [5].

If \(U\) is a prefix code such that \(\mu([U])=1\), then its average length (relatively to \(\mu\)) is defined as \[\ell(U)=\sum_{p\in U}|p|\,\mu([p]).\] It is well-known that the average length satisfies \[\label{eqAverage} \ell(U)=\mu([P]),\tag{4}\] where \(P\) is the set of proper prefixes of the words in \(U\) [5]. The following is closely related to our second main result, Theorem [t:second-main]. Its proof is based on relations between associated generating functions.

Note that a rational prefix code satisfying \(\mu([U])=1\) must satisfy the assumption \(\ell(U)<\infty\). Indeed, any rational code is thin by [5], hence the set \(P\) of proper prefixes of \(U\) is also thin, which implies \(\mu([P])<\infty\) by [5].

Let \(\varphi\colon A^*\to G\) be a morphism from \(A^*\) onto a finite group \(G\). If \(H\) is a subgroup of \(G\), then the submonoid \(M=\varphi^{-1}(H)\) is generated by the prefix code \(U\) consisting of the nonempty words in \(M\) with no non-trivial prefix in \(M\); we say that \(U\) is a group code. Observe in fact that \(U\) is also equal to the nonempty words in \(M\) with no non-trivial suffix in \(M\), and as a result has the dual property of being a suffix code (no element of \(U\) is suffix of another). Note that sets which are both prefix and suffix codes are called bifix codes; bifix codes will be at the heart of Section 6.1.

5 Densities in shifts of finite type↩︎

The aim of this section is to apply our main density formula (Theorem [t:first-main]) within the setting of shifts of finite type. We provide a simple condition which guarantees topological transitivity of the skew product with a finite group; this in turn implies ergodicity for the product of the uniform probability measure on the group and a Markov measure on the shift. This also includes the case of Bernoulli measures which we already discussed in the previous Section 4.

The question of ergodicity for skew products over Bernoulli measures was studied by Kakutani [38], and the more general Markov case was studied by Bufetov [39]. The latter introduced a condition that he called “strongly connected” to characterize ergodicity of certain skew products involving Markov measures [39]. Restating Bufetov’s criterion in our setting, for consistency of terminology, we rename this condition strong irreducibility; his result was also recently extended in a paper by Lummerzheim et al. [40].

In Section 5.1 we define \(\varphi\)-irreducibility of a subshift with respect to a morphism onto a finite group, which characterizes topological transitivity in skew products. Section 5.2 treats skew products of shift spaces over Markov measures, using the fact that irreducibility implies ergodicity. In Section 5.3 we discuss strong irreducibility, which provides topological transitivity simultaneously for all skew products.

5.1 Shifts of finite type and \(\varphi\)-irreducibility↩︎

Recall that a shift \(X\) is an \(r\)-step shift of finite type (SFT, \(r\geq 1\)) if there is a list \(F\subseteq A^{r+1}\) of forbidden factors of length \(r+1\), with the property that an infinite word \(x \in A^{\mathbb{Z}}\) belongs to \(X\) precisely when none of its factors of length \(r+1\) are in \(F\). Recall also that a shift \(X\) is topologically transitive if for every pair \((U,V)\) of nonempty open sets in \(X\), there is \(n>0\) for which \(S^nU \cap V \neq \varnothing\). This is equivalent with the irreducibility of \(X\), i.e. for every \(u,v\in\mathcal{L}(X)\), there is \(w \in A^*\) such that \(uwv \in \mathcal{L}(X)\). For more on shifts of finite type, see e.g. [20], [41]. Topological transitivity will be used to prove ergodicity for \(r\)-step Markov measures fully supported on \(r\)-step shifts of finite type in Section 5.2.

Clearly \(\varphi\)-irreducibility always implies irreducibility. This is a special case of the following remark.

We shall prove the following result, which shows that \(\varphi\)-irreducibility is precisely the notion needed for topological transitivity of the original shift to propagate to skew products with finite groups.

Before doing so, we establish an intermediate result involving the following notion.

Fiber ergodicity follows from \(\varphi\)-irreducibility for shifts of finite type, as shown next.

It is not hard to see directly that topological transitivity of \(G\rtimes_{\varphi} X\) implies fiber ergodicity (as also follows from Theorem 14); but the converse is false, as shown by the following example.

Finally we prove the following useful property of \(\varphi\)-irreducibility in shifts of finite type. It shows that for shifts of finite type, the task of verifying the condition in Definition 3 can be reduced to a finite set of words.

5.2 Markov measures↩︎

Using the topological transitivity condition from Theorem 14, we establish ergodicity for skew products involving invariant Markov measures. Recall that a measure \(\mu\) on \(A^\mathbb{Z}\) is an \(r\)-step Markov measure, \(r\geq 1\), when for every word \(w\in A^*\) of length \(m\geq r\) such that \(\mu(x_{[0,m)} = w)\neq 0\) and every letter \(a\in A\), \[\mu(x_m = a \mid x_{[0,m)} = w) = \mu(x_{m}=a \mid x_{[m-r,m)} = w_{[m-r,m)}).\]

Invariant Markov measures are also called stationary. The support of an \(r\)-step invariant Markov measure \(\mu\) is an \(r\)-step shift of finite type. We say that an \(r\)-step Markov measure \(\mu\) is irreducible when for all \(u,v\in A^r\), there exists \(m>0\) such that \[\mu(x_{[m,m+r)}=v\mid x_{[0,r)}=u)>0.\]

Notice that this is equivalent to irreducibility of the shift of finite type supporting \(\mu\). It is well known that a Markov measure is ergodic if and only if it is irreducible. The 1-step case may be found in [20], while the general \(r\)-step case can be reduced to \(r=1\) by passing to the higher block shift (whose definition is recalled after Example 17). We shall prove our second main result, which we now recall.

Recall that if \(X\) is \(\varphi\)-irreducible, then it is irreducible, and so under the assumptions of the above theorem, \(\mu\) itself must be ergodic. Recall also, from Lemma 1, that for every morphism \(\varphi\colon A^*\to G\) onto a finite group \(G\) and every shift \(X\), the skew product \(X\rtimes_{\varphi} G\) is topologically conjugate to a subshift of \((G\times A)^\mathbb{Z}\) via the map \[\Psi(g,x)_n=(g\varphi^{(n)}(x),x_n),\quad n\in\mathbb{Z}.\]

Next let us briefly describe how ergodicity for \(r\)-step Markov measures can also be reduced to the 1-step case by passing to the higher block shift. Let \(\mu\) be an invariant \(r\)-step Markov measure, \(r\geq 1\), with support a shift of finite type \(X\). Let \(A_X^{[r]} = \mathcal{L}(X)\cap A^r\), which we view as an alphabet. We define the map \(\beta_r\colon A^\mathbb{Z}\to (A_X^{[r]})^\mathbb{Z}\) by \[\beta_r(x)_i = x_{[i,i+r)}.\] The image \(\beta_r(X)\) forms a shift space on \(A_X^{[r]}\) denoted \(X^{[r]}\), which is called the higher block shift. The image measure of \(\mu\) under \(\beta_r\), denoted \(\mu^{[r]}\), is an invariant 1-step Markov measure on this shift space. Moreover, \(\mu\) is ergodic exactly when \(\mu^{[r]}\) is.

The density of a group language also carries over to the higher block shift, as follows. Given a morphism \(\varphi\colon A^*\to G\) onto a finite group, let \(\varphi^{[r]}\colon A_X^{[r]}\to G\) be the morphism defined by \(\varphi(w) = \varphi(w_0)\) for \(w = w_0\ldots w_{r-1}\in A_X^{[r]}\). To the group language \(L = \varphi^{-1}(K)\), \(K\subseteq G\), corresponds the group language \(L^{[r]} = (\varphi^{[r]})^{-1}(K)\). It is straightforward to check that \(\mu^{[r]}(L^{[r]}\cap (A_X^{[r]})^i) = \mu([L\cap A^i])\), and as a result: \[\delta_\mu(L) = \delta_{\mu^{[r]}}(L^{[r]}).\]

5.3 Strong irreducibility↩︎

We now relate \(\varphi\)-irreducibility to a condition introduced by Bufetov [39], originally under the name strongly connected. The term strictly irreducible was used in Lummerzheim et al. [40]. We make a compromise between the two and use the term strongly irreducible. We shall see below that if it holds, then all skew products by morphisms onto finite groups are topologically transitive; on the other hand, when it fails, such skew products can behave in a variety of manners.

Recall the notation \({\prec} = {\prec_{1_G}}\), used in the proof of Theorem 14 for the relation defined by \(u\prec v\) if and only if there exists \(w\in\mathcal{L}(X)\) such that \(uwv\in\mathcal{L}(X)\) and \(\varphi(uw) = 1_G\).

We then deduce the following. It is our version of Bufetov’s theorem [39] and its generalization by Lummerzheim et al. [40], which we here specialize to the case of skew products with finite groups and morphisms, but generalize to the case of higher step shifts.

At this time we are unsure whether the converse holds when \(r>1\). Nonetheless, the first part of the above combined with Theorem 14 yields the following immediate corollary.

To end this section we give a few examples of shifts of finite type which are or are not strongly irreducible. But first we make the following simple observation, similar to Proposition 15.

6 A characterization of minimality via return words↩︎

We now shift our focus away from shifts of finite type and towards minimal shift spaces. We start by giving a first characterization of minimality for skew products (Theorem 20), stated in terms of return words (Section 2). Its proof, given in Section 6.2, strongly relies on the deep links between the skew products under consideration and bifix codes, recalled in Section 6.1.

We will later provide a further characterization of minimality in Theorem 28, stated in terms of cobounding maps, in the flavor of Anzai’s theorem on ergodicity of skew products [15]. We will also provide an alternate proof of the equivalence between [i:minimalskew-minimal] and [i:minimalskew-return] (Remark 31).

6.1 More on the theory of codes↩︎

We survey some basic notions from the theory of codes, some of which already appeared in Section 4. Again we refer to [5] for additional details.

Recall that a prefix code is a subset \(U\subseteq A^*\) where no word is a strict prefix of another, and likewise a suffix code is a subset of \(A^*\) where no word is a strict suffix of another. Let \(X\) be a shift space. A prefix code \(U\subseteq\mathcal{L}(X)\) is called \(X\)-complete if every word \(w\in\mathcal{L}(X)\) is either a prefix of a word in \(U\) or has a prefix which is an element of \(U\); replacing prefix by suffix in this definition, we obtain the corresponding notion of \(X\)-complete suffix code.

We recall that a set \(U\) is a bifix code if it is both a prefix and a suffix code. It is \(X\)-complete if it is both an \(X\)-complete prefix code and an \(X\)-complete suffix code. When \(X=A^\mathbb{Z}\), we simply say complete instead of \(A^\mathbb{Z}\)-complete, be it for prefix, suffix, or bifix codes.

Let \(\varphi\colon A^*\to G\) be a morphism onto a finite group \(G\). If \(H\leq G\) is a subgroup, then the submonoid \(M=\varphi^{-1}(H)\) of \(A^*\) is uniquely generated by a bifix code \(Z\) (an argument is given in [5]), which is also a group code (as introduced in Section 4). It is in fact a complete bifix code.

Let \(Z\) be a group code. Let \(P\) (resp. \(S\)) be the set of proper prefixes (resp. suffixes) of the words in \(Z\). Note that \(P\) (resp. \(S\)) is also the set of words which have no prefix (resp. suffix) in \(Z\). The \(Z\)-degree \(d(u)\) of a word \(u\in A^*\) is then defined as any of the following numbers, which all coincide [5]:

1. the number of suffixes of \(u\) which are in \(P\);

2. the number of prefixes of \(u\) which are in \(S\);

3. the number of \(Z\)-parses of \(u\), that is, the number of triples \((s,z,p)\) such that \(u=szp\) with \(s\in S\), \(z\in Z^*\) and \(p\in P\).

It follows from the third definition that for every \(u, v, w\in A^*\), the \(Z\)-degrees of \(u\) and \(uvw\) satisfy \[d(v)\le d(uvw).\label{eq:degree}\tag{5}\]

Indeed, if \((s,z,p)\) is a \(Z\)-parse of \(v\), let \(us=s'z'\) with \(s'\in S\) and \(z'\in Z^*\), and \(pw=z''p'\) with \(z''\in Z^*\) and \(p'\in P\). Then \((s'z'zz'',p')\) is a \(Z\)-parse of \(uvw\) which extends \((s,z,p)\). This shows that every parse of \(v\) extends to a parse of \(uvw\).

Let \(X\) be a minimal shift space and let \(U=Z\cap \mathcal{L}(X)\). The \(X\)-degree of \(U\), denoted \(d_X(U)\), is the maximal value of the \(Z\)-degrees of all words in \(\mathcal{L}(X)\). The following is essentially a reformulation of [17]; we include a proof for the convenience of the reader.

The proof makes use of the following simple observation.

The next result uses ideas found in the proof of the main result of [18].

The next example shows that there can be elements of maximal degree which fail the condition \(\varphi(\mathcal{R}_X(u)^*)H=G\). There are in fact even infinitely many of them.

Here is another example with the Thue–Morse shift where \(d_X(U)<[G:H]\). Let \(\varphi\colon \{a,b\}^*\to \mathbb{Z}/n\mathbb{Z}\) be a morphism with \(\varphi(a)=1=-\varphi(b)\). Set \(Z^*=\varphi^{-1}(0)\) and \(U=Z\cap\mathcal{L}(X)\). For every \(n\geq 3\), we have \(U=\{ab,ba,aabb,bbaa,aababb,bbabaa\}\), while \(d_X(U)=3<n\) as soon as \(n>3\).

6.2 Proof of the characterization of minimality↩︎

We are now ready to give the proof of the main theorem of this section.

6.3 Relation with average length↩︎

We finish the section by coming back to the notion of average length discussed in Section 4. Let \(X\) be a minimal shift space on \(A\) and \(\varphi\colon A^*\to G\) be a morphism onto a finite group \(G\). Let \(Z\) be the group code such that \(\varphi^{-1}(1_G)=Z^*\), and \(U = Z\cap \mathcal{L}(X)\), the prefix code considered in Proposition 24. Recall the formula for the average length of \(U\) relative to \(\mu\): \[\ell(U)=\sum_{u\in U}|u|\,\mu([u]).\]

By 4 , one has also \[\ell(U)=\sum_{w\in P}\mu([w]),\] where \(P\) is the set of proper prefixes of some element of \(U\). Moreover, under the hypotheses of Theorem [t:first-main], i.e. ergodicity of the appropriate product measure on the skew product \(G\rtimes_{\varphi} X\), where \(L=Z^*=\varphi^{-1}(1_G)\), the following equalities hold, as an extension of Proposition 12: \[\delta_\mu(L)= \frac{1}{|G|} = \frac{1}{\ell(U)}.\]

Indeed we will see that ergodicity of the skew product entails minimality (Corollary 3), which implies that the restriction of \(\varphi\) on the sets \(\mathcal{R}_X(u)^*\) is onto by Theorem 20. Then, by Proposition 24, the degree \(d_X(U)\) of \(U\) is \(|G|\). We thus are in the scope of [17], which states that \(d_X(U)=\ell(U)\), and so \(\ell(U)=|G|\).

7 Minimal subsets and modular cobounding maps↩︎

We now generalize some results from the previous sections, in particular Theorem [t:first-main] which allows a simple expression of the density under the assumption of ergodicity, and Theorem 20 which characterizes minimality (referring here to the action of the skew product \(T_{\varphi}\) as defined in 2 , since the action of the shift map \(S\) on \(X\) is already assumed to be minimal). We rely on the key notion of modular cobounding map (Definition 6), closely related with the notion of coboundary. It allows in particular to obtain a further characterization of minimality (Theorem 28) inspired by Anzai’s theorem on ergodicity of skew products [15].

We prove first that the minimal skew products under consideration (that is, skew products \(G\rtimes_{\varphi}X\) with \(\varphi\) being a morphism onto a finite group \(G\)) are finite disjoint unions of their minimal closed invariant subsets, all of which have the same measure (Proposition 26). We conclude that ergodicity implies minimality (Corollary 3). Moreover, Proposition 32 together with Corollary 5 provide sufficient conditions for ergodicity on every minimal closed invariant subset of \(G \rtimes_{\varphi} X\). We prove our third main result, Theorem [t:third-main], in Section 7.4 and conclude with examples in Section 7.5.

7.1 Modular coboundaries↩︎

We start by examining the general structure of skew products in terms of minimal closed invariant subsets.

The above result has the following straightforward consequences.

We now proceed to describe the minimal closed invariant subsets of \(G\rtimes_{\varphi} X\), using the following key notion inspired by [11].

We also say that \(\alpha\) is a cobounding map mod \(H\). Observe that if \(\alpha\) is a cobounding map, then \[\alpha(S^nx) = \alpha(x)\varphi^{(n)}(x)\] for all \(n\in\mathbb{Z}\), with \(\varphi^{(n)}\) as in 3 .

As the name suggests, this definition is related to the cohomological equations developed in ergodic theory. These equations have a rich history, as evidenced for instance by [7]–[11], [15], [16]. In particular, we may view a cobounding map as a “certificate” that (the cocycle defined by) \(\varphi\) is a coboundary mod \(H\). The next proposition clarifies the link between cobounding maps and closed invariant subsets. It is a special case of a result of Lemańczyk and Mentzen [11].

7.2 A characterization of minimality via cobounding maps↩︎

There is always at least one cobounding map, namely the constant map \(X\to G\backslash G\), which we call the trivial cobounding map. The corresponding closed invariant subset is then the whole skew product. It is immediately apparent that the existence of a non-trivial cobounding map thus forbids minimality of the skew product. In fact, we have the following consequence of Proposition 27, which is reminiscent of Anzai’s theorem on ergodicity of skew products [15] (see also [20]).

Given two cobounding maps \(\alpha\) and \(\beta\), respectively mod \(H\) and \(K\), write \(\alpha\leq\beta\) if \(H\leq K\) and \(\alpha^{-1}(Hg)\subseteq\beta^{-1}(Kg)\) for all \(g\in G\). This gives a partial order on cobounding maps, which corresponds directly to the ordering of the corresponding closed invariant subsets under inclusion.

The left action of \(G\) on \(G\rtimes_{\varphi} X\) corresponds to the left action on cobounding maps given by \((g\alpha)(x) = g(\alpha(x))\), where \(g\alpha\) is viewed as a cobounding map mod \(H^g = gHg^{-1}\). This cobounding map is such that \(g\alpha(x) = H^gh \iff \alpha(x) = Hg^{-1}h\), hence \(X_{g\alpha} = gX_\alpha\). This shows that the passage from minimal closed invariant subsets to minimal cobounding maps preserves the left action of \(G\). In particular, \(G\) acts transitively on the set of minimal cobounding maps.

7.3 Cobouding maps and return words↩︎

We have established in Theorem 20 a characterization of minimality in terms of return words. Without surprise, we also find links between cobounding maps and return words. This makes the relationship between [i:minimalskew-minimal] and [i:minimalskew-return] in Theorem 20 more transparent (see Remark 31 below).

Roughly speaking, the smaller the subgroup, the more restrictive the coboundary condition, hence the most stringent cobounding maps are the cobounding maps mod 1, where the notation mod 1 refers to working modulo the trivial subgroup. One important fact is that having such cobounding maps turns out to be sufficient for the measure \(\nu\times\mu\) to be ergodic on each of the minimal closed invariant subsets of \(G\rtimes_{\varphi} X\).

We moreover observe that cobounding maps mod 1 are minimal by Proposition 30 [i:minimal]. In this special case, Proposition 30 also yields the following.

7.4 A formula for density in terms of cobounding maps↩︎

The next theorem is our third main result. It gives a simple closed form for the density in terms of any minimal cobounding map under suitable assumptions. It generalizes Corollary 1 within the setting of minimal shift spaces.

Note that when \(G\rtimes_{\varphi} X\) is ergodic, the trivial cobounding map \(\alpha\colon X\to G\backslash G\) is minimal and we recover the formula from Corollary 1: \[\delta_\mu(L) = \frac{1}{|G|}\sum_{k\in K}\sum_{Gg\in G\backslash G}\mu(\alpha^{-1}(Gg))\mu(\alpha^{-1}(Ggk)) = \frac{|K|}{|G|}.\]

Recall from Corollary 3 that the ergodicity assumption from the above theorem is equivalent to \(\nu\times\mu\) being ergodic on any closed invariant subset (which is then necessarily minimal).

7.5 Examples↩︎

We finish the section with two examples that illustrate various aspects of Theorem [t:third-main].

8 Ergodicity for primitive substitutions↩︎

In this section we focus on the special case of shift spaces defined by primitive substitutions. Our main result is a sufficient condition for the minimal closed invariant subsets of skew products to be uniquely ergodic (Proposition 33). As a corollary, we deduce that substitutive dendric shifts have ergodic skew products with all finite groups (Theorem 35). Note that the family of dendric shifts, studied in [17], [18], [44]–[46], encompasses several classical families of shifts, such as Sturmian shifts, codings of interval exchanges, and Arnoux–Rauzy shifts.

8.1 Skew products based on primitive shifts↩︎

Let us fix a primitive substitution \(\sigma\) over a finite alphabet \(A\) and let \(X = X(\sigma)\) be the shift space defined by \(\sigma\). The shift \(X\) is a minimal shift space and we recall that it is uniquely ergodic by Michel’s theorem.

Observe that Example 26 fails both the invertibility property 6 and the property of Corollary 5. At this time we do not know whether the product measure is ergodic on the minimal closed invariant subsets of the skew product. In contrast, here is an example which satisfies both [p:invertible-ergodic] and Corollary 5.

In what follows, we say that a substitution \(\sigma\colon A^*\to A^*\) is invertible if its extension to an endomorphism on the free group \(F_A\) is an automorphism. We now state two further properties when the substitution is assumed to be invertible.

In what follows, we say that a substitution is aperiodic if it generates a shift space that contains no finite orbit. We next establish the following lemma that will be used in the next section. Observe that the generation property expressed below implies the one stated in Theorem 20.

For the sake of completeness, we give an example showing that the converse of the above lemma fails, i.e. invertibility does not guarantee that all \(\mathcal{R}_X(u)\) generate \(F_A\).

8.2 Skew products based on dendric shifts↩︎

We turn now to the dendric case. First, we recall the definition. Let \(X\) be a shift space. For \(w\in\mathcal{L}(X)\), let \(\operatorname{L}(w)=\{a\in A\mid aw\in\mathcal{L}(X)\}\) and \(\operatorname{R}(w)=\{a\in A\mid wa\in\mathcal{L}(X)\}\). We denote by \(\operatorname{E}(w)\) the graph with vertices the disjoint union of \(\operatorname{R}(w)\) and \(\operatorname{L}(w)\) and edges the pairs \((a,b)\in A\times A\) such that \(awb\in\mathcal{L}(X)\); it is called the extension graph of \(w\). A shift space \(X\) is dendric if for every \(w\in \mathcal{L}(X)\), the extension graph \(\operatorname{E}(w)\) is a tree. For instance, every Sturmian shift is dendric [44].

An important result concerning dendric shifts is the so-called Return Theorem by Berthé et al. which we quote next.

Therefore it follows from Theorem 20 that every skew product of a dendric shift and a finite group is minimal.

We also give an example of a shift space which is not dendric.

We recover as a consequence of the following general result the unique ergodicity of the skew product of Section 3.4.

The proof uses Lemmas 8 and 9. Observe that dendric shift spaces in particular fall under the scope of Lemma 9, thanks to the Return Theorem of Berthé et al., stated above as Theorem 34.

We thus obtain, as a direct application of Corollary 1, the following result about the density of group languages in substitutive dendric shifts.

9 Skew products based on Sturmian shifts↩︎

We end with a discussion about earlier related works on skew products based on irrational rotations, mostly by Veech [7], [8] and Jager and Liardet [19]. Due to the nature of the examples involved, and to stay consistent with the relevant literature, it is convenient here to use alphabets consisting of natural numbers, such as \(\{0,1\}\) and \(\{1,2\}\).

Among the first classical examples of skew products, skew translations (i.e. skew products with base an irrational rotation on the unit circle), and their ergodic and spectral properties have been widely investigated; see e.g. [7], [8], [50]–[53] and the classical references [20], [26]. In particular, they have been used to produce examples of interval exchanges that are not uniquely ergodic [54]. Such examples are based on skew products of irrational rotations associated with the group \(\mathbb{Z}/2\mathbb{Z}\), that are minimal and not uniquely ergodic, with the skewing function being the indicator function of an interval [7], [8].

More precisely, let \(\alpha\) be an irrational number in \([0,1]\). We consider the rotation \(R_{\alpha}\colon x \mapsto x + \alpha\) modulo \(1\) defined on \(\mathbb{T}=\mathbb{R}/\mathbb{Z}\). Let \(I=[0, \beta)\) be a semi-open interval of \(\mathbb{T}\). Let \({1}_I\colon {\mathbb{T}} \to \{0,1\}\) be the indicator function of \(I\), i.e. \(1_I(x)=1\) if and only if \(x\in I\). Let \(m \geq 2\) and let \(G=\mathbb{Z}/m\mathbb{Z}\). Let \(\varphi:\{0,1\}^*\to G\) be the morphism defined by \(0\mapsto 0\), \(1 \mapsto 1\). We then consider the skew product \(G\rtimes_I {\mathbb{T}}\) of \(R_{\alpha}\) defined as \[(k, x) \mapsto ( k+ \varphi \circ 1_I (x), x +\alpha)= ( k+ \varphi \circ 1_I (x), R_{\alpha} (x)).\]

Such skew products over rotations are closely related to symbolic skew products such as those considered in the present paper, and more precisely, to skew products over shifts obtained as binary codings of rotations. Let \(I^{\mathrm{c}}\) stand for the complement of \(I\) in \(\mathbb{T}\). We use the notation \(I_0=I\), and \(I_1=I^{\mathrm{c}}\). Let \(x\) be the infinite word in \(\{0,1\}^\mathbb{Z}\) obtained by coding the orbit of \(0\) under \(R_{\alpha}\) with respect to the partition \({\mathcal{I}}=\{I, I^\mathrm{c}\}\), i.e. for any \(n \in \mathbb{Z}\), \(x_n=1\) if and only if \(R_{\alpha}^n(0) \in I\), or in other words, \(x_n = 1_I( R_{\alpha}^n (0))\) for all \(n \in {\mathbb{Z}}\). Let \((X,S)\) be the shift space generated by \(x\). Then this shift is minimal and uniquely ergodic since \(\alpha\) is irrational and \(I\) is semi-open. Indeed, we associate in a bijective way words \(w=w_1 \ldots w_n\) in \(\{0,1\}^n\) with sets \(I_{w} := I_{w_1} \cap R_{\alpha} ^{-1} I_{w_2} \cap \dots \cap R_{\alpha} ^{-n+1} I_{w_n}\) as follows: \(w\) occurs at index \(k\) in \(x\) if and only if \(k \alpha \in I_w\). It is important to stress the fact that \(I\) is assumed to be semi-open. As an illustration of the relevance of this hypothesis, consider the case \(I=[0,\alpha]\), with \(\alpha <1/2\); then, \(00\) occurs only once in the orbit of \(0\) and minimality fails. The fact that \(I\) is semi-open guarantees that if \(I_w\) is not empty, then there are infinitely many \(k\) such that \(k \alpha \in I_w\), by density of the sequence \((k \alpha)_k\), hence the uniform recurrence of \(x\), and thus the minimality of \(X\). When the length of \(I\) equals \(\alpha\) or \(1-\alpha\), such binary codings of rotations are Sturmian.

Not all intervals \(I\) lead to ergodic skew products. In fact, by [7], if \(\alpha\) is not badly approximable, then there exists an interval \(I\) such that the skew product \(G\rtimes_I\mathbb{T}\) of \(R_{\alpha}\) is not ergodic, a result which inspired the elegant characterization of ergodicity from [52] stated in terms of Ostrowski’s numeration. Moreover, as proved in [8], skewing a badly approximable rotation over a finite number of intervals with rational endpoints still provides a uniquely ergodic skew product. However, [55] provides a \(\mathbb{Z}/2\mathbb{Z}\) skew product of a badly approximable rotation that is minimal and not uniquely ergodic, by skewing over the indicator function of a union of two intervals.

In most examples considered in [7], [8], intervals have lengths that do not belong to \(\mathbb{Z}\alpha+ \mathbb{Z}\). We consider here the complementary case of Sturmian shifts. We can then apply Theorem 35 and Corollary 6 when they are furthermore assumed to be generated by a substitution, such as exemplified below. Note also that substitutive Sturmian shifts have been characterized in [56], [57] (in particular, the parameter \(\alpha\) of the underlying rotation is quadratic, and thus badly approximable).

Finally, we consider in the next example, inspired by the work of Jager and Liardet [19], equidistribution properties for convergents in continued fraction expansions.

Acknowledgements↩︎

We would first like to thank the anonymous referees for carefully reading through our paper and for making very helpful comments and suggestions. We warmly thank Samuel Petite for leading us to a mistake in an early version of this paper and France Gheeraert for suggesting a simplification in the proof of Theorem 20. We also thank Olivier Carton and Vincent Delecroix for insightful conversations about the notion of pointwise densities.

The first author is supported by Agence Nationale de la Recherche through the project SymDynAr (ANR-23-CE40-0024) and 2024 ERC Synergy Project DynAMiCs (101167561). The second author was partially supported by the CTU Global Postdoc Fellowship program. The third author is supported by the KIAS Individual Grant (MG094701) at Korea Institute for Advanced Study. The first and fourth authors were supported by the Agence Nationale de la Recherche through the project IZES (ANR-22-CE40-0011).

References↩︎