1 Introduction

Let X be a compact metric space equipped with a continuous map \(T:X \rightarrow X\). For the discrete dynamical system (X, T), recall that a point \(x \in X\) is periodic with period \(n \in \mathbb {N}\) if \(T^n(x)=x\). Moreover, if \(T^k(x) \ne x\) for \(k = 1,2,\ldots ,n-1\), then it has the prime period n. Its (prime) closed orbit is then defined as

$$\begin{aligned} \tau (x) = \left\{ x, T(x), \ldots , T^{n-1}(x)\right\} . \end{aligned}$$

In many instances, the distribution of closed orbits are closely related to the complexity of a system. For this reason, some counting functions are introduced as a way to describe the growth of the closed orbits. These are called the prime orbit counting function

$$\begin{aligned} \pi (N)=\sum _{\begin{array}{c} \tau \\ |\tau |\le N \end{array}} 1 \end{aligned}$$

and the pair of Mertens’ orbit counting functions

$$\begin{aligned} \mathcal {M}(N)=\prod _{\begin{array}{c} \tau \\ |\tau |\le N \end{array}} \left( 1-\frac{1}{e^{h|\tau |}}\right) \quad \text {and}\quad \mathscr {M}(N)=\sum _{\begin{array}{c} \tau \\ |\tau |\le N \end{array}}\frac{1}{e^{h|\tau |}} \end{aligned}$$

where \(N \in \mathbb {N}\), h is the topological entropy of the system (which is assumed to be positive) and \(\tau \) runs through the closed orbits of size \(|\tau |\).

These functions arise as the analogues for the counting functions for primes in number theory. In particular, the prime number theorem and Mertens’ theorem state that

$$\begin{aligned} \sum _{\begin{array}{c} p \\ p\le N \end{array}}1 \sim \frac{N}{\ln N}, \quad \prod _{\begin{array}{c} p \\ p\le N \end{array}}\left( 1-\frac{1}{p}\right) \sim \frac{e^{-\gamma }}{\ln N} \quad \text {and}\quad \sum _{\begin{array}{c} p \\ p\le N \end{array}} \frac{1}{p} = \ln \ln N + M +o(1) \end{aligned}$$

where \(\gamma \) and M are Euler–Mascheroni constant and Meissel–Mertens constant, respectively, and p runs through primes (see [1]). These theorems motivate an analogous problem in the theory of dynamical systems, which is to obtain the asymptotic behaviours of the orbit counting functions for a system (see [2]).

As one approach, the analysis on the Artin–Mazur zeta function [3] of a system can lead to the desired asymptotic results. For a system (X, T), its Artin–Mazur zeta function is defined as

$$\begin{aligned} \zeta (z) = \exp \left( \sum _{n=1}^{\infty }\frac{F(n)}{n}z^n\right) \end{aligned}$$

where \(z \in \mathbb {C}\) (in its disc of convergence) and F(n) is the number of periodic points of period n. The next theorem summarizes how the analiticity of the zeta function implies the asymptotic behaviours of the orbit counting functions.

Theorem 1

[4] Let (X, T) be a discrete dynamical system with topological entropy \(h>0\) and Artin–Mazur zeta function \(\zeta (z)\). Suppose that there exists a function \(\alpha (z)\) such that it is analytic and non-zero for \(|z |<Re^{-h}\) for some \(R>1\), and

$$\begin{aligned} \zeta (z)= \frac{\alpha (z)}{(1-e^{hp}z^p)^m} \end{aligned}$$

for \(|z |<e^{-h}\) for some \(m, p \in \mathbb {N}\). Then,

$$\begin{aligned} \pi (N)&\sim mp \cdot \frac{e^{hp\left( \left\lfloor \frac{N}{p} \right\rfloor +1\right) }}{(e^{hp}-1)\cdot N}, \quad \mathcal {M}(N) \sim \frac{p^m e^{-m\gamma }}{\alpha (e^{-h}) \cdot N^m} \quad \text {and}\\ \mathscr {M}(N)&= m \ln \left\lfloor \frac{N}{p} \right\rfloor + m \gamma + \ln \alpha (e^{-h}) - C +o(1) \end{aligned}$$

where \(\gamma \) is Euler–Mascheroni constant and C is a positive constant specified as

$$\begin{aligned} C = \sum _{\tau } \left( \ln \left( \frac{1}{1-e^{-h|\tau |}}\right) - \frac{1}{e^{h|\tau |}}\right) . \end{aligned}$$
(1)

To sum up, we require \(\zeta (z)\) to satisfy the following: (i) it extends to a meromorphic function in the region \(\left\{ z\in \mathbb {C} \mid |z |<{\textit{Re}}^{-h} \right\} \), (ii) it has no zero in the said region, and (iii) there are exactly p poles in this region, which have the same order m and are of the form \(\omega e^{-h}\), where \(\omega \) runs through pth roots of unity.

In the literature, this approach was used to determine the orbit growths of ergodic toral automorphisms [5, 6] and several types of shift spaces. These include shifts of finite type [2, 7], periodic-finite-type (PFT) shifts [4], Dyck and Motzkin shifts [8], and bouquet-Dyck shifts [9]. Similar results can be deduced for beta shifts [10], negative beta shifts [11] and shifts of quasi-finite type [12], albeit these findings are not stated in their respective papers.

While we focus on the approach via zeta function, there are other methods to obtain the orbit growth of a system, such as using orbit Dirichlet series [13], orbit monoids [14] and estimates on the number of periodic points [15,16,17]. Furthermore, similar research problem has been studied for group actions on dynamical systems, and some recent results include the orbit growths of nilpotent group shifts [18], algebraic flip systems [19] and flip systems for shifts of finite type [20]. Since our introduction on this subject is rather short, we encourage readers to explore those papers above, and additionally the expository chapters by Nordin et al. [21] and Ward [22].

Our attention now is on sofic shifts (see [23]). Sofic shifts are a class of shift spaces constructed from labelled graphs. Examples are shifts of finite type and PFT shifts. The zeta function for the sofic shifts has long been known, and in fact, it is a rational function. However, it is implicitly expressed in terms of several signed subset matrices, making it rather sophisticated.

The orbit growth of the sofic shifts is yet to be determined completely. A sofic shift with specification property [12] (which is equivalent to topological mixing in this case) is a shift of quasi-finite type, so its orbit growth is deduced from the result in [12] and Theorem 1. However, this finding does not cover the case for a general irreducible sofic shift.

As mentioned above, PFT shifts are a particular type of sofic shifts. In [4], we had obtained the orbit growth of irreducible PFT shifts with irreducible Moision–Siegel (MS) presentations [24, 25]. Our result is shown in the next theorem. However, this result is incomplete because it does not cover the case for irreducible PFT shifts with reducible MS presentations.

Theorem 2

Let \(\mathcal {X}\) be an irreducible PFT shift of period \(T \in \mathbb {N}\) with topological entropy \(\ln \lambda >0\). Suppose that its MS presentation is irreducible. Then,

$$\begin{aligned} \pi (N)&\sim kT \cdot \frac{ \lambda ^{kT\left( \left\lfloor \frac{N}{kT}\right\rfloor +1\right) }}{N(\lambda ^{kT}-1)},\quad \mathcal {M}(N) \sim \frac{kTe^{-\gamma }}{\alpha N} \quad \text {and}\\ \mathscr {M}(N)&= \ln \left\lfloor \frac{N}{kT}\right\rfloor + \gamma + \ln \alpha -C +o(1) \end{aligned}$$

where kT is the period of the MS presentation for some \(k\in \mathbb {N}\), \(\gamma \) is the Euler–Mascheroni constant, \(\alpha \) is a positive constant specified by

$$\begin{aligned} \alpha = \lim _{z \rightarrow \lambda ^{-1}} (1-\lambda ^{kT}z^{kT})\cdot \zeta (z) \end{aligned}$$
(2)

where \(\zeta (z)\) is its Artin–Mazur zeta function, and C is another positive constant specified in (1).

Hence, our paper here aims to obtain the orbit growth, i.e. the asymptotic behaviours of the orbit counting functions, for a general sofic shift. Suprisingly, the well-known work by Lind and Marcus [23] on sofic shifts, especially on their minimal right-resolving presentations, is sufficient to lead to our result. We will demonstrate our result to obtain the orbit growth of any PFT shift for the sake of completeness to our previous work in [4]. Our main results can be found in Theorems 4 and 8. At the end, we provide a short remark on the application of our finding towards the finite group and homogeneous extensions of a sofic shift.

We shall point out that an earlier version of this paper can be found in [26]. However, it does not include our current result here about the orbit growth of PFT shifts.

2 Sofic Shifts and Their Orbit Growth

2.1 Sofic Shifts

Now, we briefly discuss some background on sofic shifts and their important properties. All these facts can be found in [23].

Let \(G=(V,E)\) be a finite directed graph with vertex set V and edge set E. For an edge \(e \in E\), denote its initial and terminal vertices as \(i(e) \in V\) and \(t(e) \in V\), respectively. We assume that each vertex is neither a source nor a sink, i.e. it must have incoming and outgoing edges. For a finite set \(\mathcal {A}\), let \(\mathcal {L}:E \rightarrow \mathcal {A}\) be the label of each edge with an element of \(\mathcal {A}\). The pair \(\mathcal {G}=(G, \mathcal {L})\) is called a labelled graph.

A sequence \(\{e_k\}_{k=1}^n\) of edges is called a path of length n if \(t(e_{k})=i(e_{k+1})\) for \(k=1,2,\ldots ,n-1\). The label of the path is the corresponding sequence \(\left\{ \mathcal {L}(e_k)\right\} _{k=1}^n\). We define a bi-infinite path \(\{e_k\}_{k\in \mathbb {Z}}\) and its label \(\left\{ \mathcal {L}(e_k)\right\} _{k\in \mathbb {Z}}\) in a similar way. Denote \(\mathcal {P}_\infty (\mathcal {G})\) as the set of bi-infinite paths in \(\mathcal {G}\).

Let \(\mathcal {A}\) be equipped with the discrete topology. So, the set \(\mathcal {A}^{\mathbb {Z}}\) of bi-infinite sequences from \(\mathcal {A}\) is equipped with the product topology. The sofic shift presented by \(\mathcal {G}\) is the set

$$\begin{aligned} \mathcal {X} = \left\{ x \in \mathcal {A}^\mathbb {Z} \mid x = \left\{ \mathcal {L}(e_k)\right\} _{k\in \mathbb {Z}}\;\text {for some }\;\{e_k\}_{k\in \mathbb {Z}} \in \mathcal {P}_\infty (\mathcal {G})\right\} \end{aligned}$$

paired together with a (left) shift map \(\sigma : \mathcal {X} \rightarrow \mathcal {X}\), which maps \(x = \{x_k\}_{k\in \mathbb {Z}}\) to \(\sigma (x) = \{x_{k+1}\}_{k\in \mathbb {Z}}\). The graph \(\mathcal {G}\) is called a presentation of \(\mathcal {X}\).

An element \(x \in \mathcal {X}\) is a called a point. A finite sequence \(w=a_1a_2 \ldots a_n\) from \(\mathcal {A}\) is called a word of length \(|w |=n\) if there exist \(x \in \mathcal {X}\) and \(k\in \mathbb {Z}\) such that \(x_k x_{k+1}\ldots x_{k+n-1} = w\). Denote \(\mathcal {B}(\mathcal {X})\) as the set of words in \(\mathcal {X}\). The shift \(\mathcal {X}\) is said to be irreducible if for all \(w, \tilde{w} \in \mathcal {B}(\mathcal {X})\), either \(w\tilde{w} \in \mathcal {B}(\mathcal {X})\) or there exists \(u \in \mathcal {B}(\mathcal {X})\) such that \(wu\tilde{w} \in \mathcal {B}(\mathcal {X})\).

Any word in \(\mathcal {X}\) is the label of some path in \(\mathcal {G}\). It is possible to have more than one such path for each word. This is similarly true for points as well. Besides that, the sofic shift itself can be presented by different labelled graphs. We will choose a presentation that has some useful properties.

A labelled graph is said to be right-resolving if for every vertex, its outgoing edges have different labels. Any sofic shift has a presentation of this form. In fact, we can proceed further to obtain the minimal right-resolving presentation, which is the one with the fewest vertices among all right-resolving presentations. For an irreducible sofic shift, this presentation is unique up to graph isomorphism.

Recall that a non-negative square matrix A is irreducible if for every pair of indices i and j, there exists \(n \in \mathbb {N}\) such that the ij-entry of \(A^n\), denoted as \((A^n)_{ij}\), is positive. In this case, its period is defined as \(\gcd \{n \in \mathbb {N} \mid (A^n)_{ii}>0\}\) and this value is the same for any index i. We can define the irreducibility and period of a directed graph based on its adjacency matrix. Equivalently, a graph G is irreducible if for any pair of vertices v and \(\tilde{v}\), there exists a path from v to \(\tilde{v}\).

For a labelled graph \(\mathcal {G}=(G, \mathcal {L})\), its adjacency matrix \(A_\mathcal {G}\) is the adjacency matrix of the underlying graph G. The irreducibility and period of \(\mathcal {G}\) is defined according to G. If \(\mathcal {G}\) is irreducible, then its sofic shift is also irreducible. The converse is false. However, a sofic shift is irreducible if and only if its minimal right-resolving presentation is also irreducible.

A word \(w \in \mathcal {B}(\mathcal {X})\) is said to be synchronising in \(\mathcal {G}\) if all paths with the label w end at the same terminal vertex. If \(\mathcal {X}\) is irreducible and \(\mathcal {G}\) is its minimal right-resolving presentation, then any word \(w \in \mathcal {B}(\mathcal {X})\) can be extended into a synchronising word \(w\tilde{w}\) in \(\mathcal {G}\) for some \(\tilde{w} \in \mathcal {B}(\mathcal {X})\). In this case, it is guaranteed that \(\mathcal {X}\) has a synchronising word in \(\mathcal {G}\).

A right-resolving presentation \(\mathcal {G}\) of an irreducible sofic shift \(\mathcal {X}\) can be modified to become its minimal right-resolving presentation. For this purpose, we define the follower set of a vertex in \(\mathcal {G}\) as the set of labels of paths that begin at that vertex. We form an equivalence relation on the vertex set V as follows: \(v \in V\) is related to \(\tilde{v} \in V\) if both have the same follower set. Now, construct the merged graph of \(\mathcal {G}\) as follows:

  1. (i)

    the vertices are the equivalence classes \(C_i\) under this relation,

  2. (ii)

    for vertices \(C_i\) and \(C_j\), there exists an edge with label \(a \in \mathcal {A}\) from \(C_i\) to \(C_j\) if there exist vertices \(v_i \in C_i\), \(v_j \in C_j\) and an edge with label a from \(v_i\) to \(v_j\) in the original graph \(\mathcal {G}\).

For an irreducible right-resolving presentation \(\mathcal {G}\), its merged graph is the minimal right-resolving presentation of \(\mathcal {X}\).

A right-resolving presentation can also be used to determine the topological entropy of a sofic shift. For any choice of a right-resolving presentation \(\mathcal {G}\), the topological entropy of \(\mathcal {X}\) is given by \(h\left( \mathcal {X}\right) =\ln \rho \left( A_\mathcal {G}\right) \), where \(\rho \left( A_\mathcal {G}\right) \) denotes the spectral radius of the adjacency matrix \(A_\mathcal {G}\).

A sofic subshift of \(\mathcal {X}\) is a subset \(\mathcal {Y} \subseteq \mathcal {X}\) such that it is itself a sofic shift. Their topological entropies are related by \(h\left( \mathcal {Y}\right) \le h\left( \mathcal {X}\right) \). Furthermore, if \(\mathcal {X}\) is irreducible, then the equality holds true if and only if \(\mathcal {Y} = \mathcal {X}\).

Any labelled graph \(\mathcal {G}\) can be decomposed into several irreducible subgraphs \(\mathcal {H}_i\), which are called the irreducible components of \(\mathcal {G}\). This produces the corresponding irreducible sofic subshifts \(\mathcal {Y}_i\) from the original shift \(\mathcal {X}\). The topological entropy of \(\mathcal {X}\) can be found as \(h\left( \mathcal {X}\right) = \max _i h\left( \mathcal {Y}_i\right) \). If \(\mathcal {X}\) is irreducible, then there exists a maximal irreducible component of \(\mathcal {G}\) that presents \(\mathcal {X}\).

The Artin–Mazur zeta function of a sofic shift is relatively complicated in closed form. For this purpose, let \(\mathcal {G}\) be a right-resolving presentation of \(\mathcal {X}\) with the underlying graph \(G=(V,E)\). For simplicity, we denote the vertex set as \(V=\{1,2,\ldots ,S\}\) where \(S=|V |\). Observe that for each \(a \in \mathcal {A}\) and \(v \in V\), there is at most one outgoing edge from v with label a. If such an edge exists, then we denote the terminal vertex as v(a).

We construct a labelled graph \(\mathcal {G}_j\) for \(j=1,2,\ldots ,S\) from \(\mathcal {G}\). Its vertex set \(\mathcal {V}_j\) is the collection of subsets of V with j distinct vertices. For each subset \(v^{(j)} \in \mathcal {V}_j\), arrange the vertices in increasing order, i.e. \(v^{(j)} = \{v_1,v_2,\ldots ,v_j\}\) where \(v_1< v_2< \ldots < v_j\). For every \(v^{(j)},\tilde{v}^{(j)} \in \mathcal {V}_j\) and \(a \in \mathcal {A}\), there is an edge from \(v^{(j)}\) to \(\tilde{v}^{(j)}\) if all vertices \(v_1(a), v_2(a), \ldots , v_j(a)\) are defined, distinct and contained in \(\tilde{v}^{(j)}\). The label of this edge is a if \(\left\{ v_1(a), v_2(a), \ldots , v_j(a)\right\} \) is an even permutation of \(\tilde{v}^{(j)}\), or \(-a\) otherwise.

Define the signed subset matrix \(A_j\) from \(\mathcal {G}_j\) as follows: for \(v^{(j)},\tilde{v}^{(j)} \in \mathcal {V}_j\), the \(v^{(j)} \tilde{v}^{(j)}\)-entry of \(A_j\) is the number of edges with positive labels minus the number of edges with negative labels from \(v^{(j)}\) to \(\tilde{v}^{(j)}\). Note that \(\mathcal {G}_1\) is simply \(\mathcal {G}\), so \(A_1\) is the adjacency matrix \(A_\mathcal {G}\).

From the above setting, the Artin–Mazur zeta function of \(\mathcal {X}\) is given by

$$\begin{aligned} \zeta (z) = \prod _{j=1}^{S} \left( \det \left( I_j-A_j z\right) \right) ^{(-1)^j} \end{aligned}$$
(3)

where \(I_j\) is the identity matrix (of the same size to \(A_j\)). Since each determinant gives out a polynomial in terms of z, the zeta function is a rational function.

2.2 Orbit Growth of Sofic Shifts

As explained above, any sofic shift can be decomposed into several irreducible sofic subshifts, which can be studied separately. So, it is sufficient to consider an irreducible sofic shift from now on. Moreover, the topological entropy of an irreducible sofic shift is zero if and only if it is finite, and in fact, it is entirely a single closed orbit. To avoid triviality, we can also assume that the topological entropy is positive.

Let \(\mathcal {X}\) be an irreducible sofic shift with positive topological entropy. Let \(\mathcal {G}\) be its minimal right-resolving presentation. Our assumption implies that its adjacency matrix \(A_\mathcal {G}\) is irreducible. Denote p and \(\lambda \) as the period and spectral radius of \(A_\mathcal {G}\) respectively. The assumption also implies that \(\lambda >1\). By Perron–Frobenius theory, there are exactly p eigenvalues of \(A_\mathcal {G}\) with modulus \(\lambda \), of the form \(z_k=\lambda \cdot \exp \left( \frac{2k\pi }{p}\varvec{i}\right) \) for \(k=0,1,\ldots ,p-1\), and they are simple (see [23]).

Our aim is to apply Theorem 1 to deduce the orbit growth of \(\mathcal {X}\). From (3), observe that

$$\begin{aligned} \zeta (z) = \prod _{j=1}^S \prod _{\mu }(1-\mu z)^{(-1)^j} \end{aligned}$$

where \(\mu \) runs through non-zero eigenvalues of \(A_j\). So, any zero or pole of \(\zeta (z)\) is in the form \(\mu ^{-1}\). As per Theorem 1, we will show that \(\zeta (z)\) can be written as

$$\begin{aligned} \zeta (z) = \frac{\alpha (z)}{1-\lambda ^p z^p}, \quad \alpha (z) = \prod _{j=1}^S \prod _{\begin{array}{c} \mu \\ |\mu |< \lambda \end{array}}(1-\mu z)^{(-1)^j} \end{aligned}$$

and moreover, the desired function \(\alpha (z)\) is analytic and non-zero for \(\vert z |<R \lambda ^{-1}\) where

$$\begin{aligned} R = \min _{\begin{array}{c} \mu \\ |\mu |< \lambda \end{array}}\left\{ \frac{\lambda }{|\mu |}\right\} . \end{aligned}$$

Equivalently, we require that each \(z_k^{-1}\) is a simple pole of \(\zeta (z)\), while all zeros and other poles are located at or beyond radius \(R\lambda ^{-1}\). The former statement is true based on Perron–Frobenius theory above. For the latter, by comparing spectral radii, it is sufficient to prove that \(\rho (A_j)< \lambda \) for \(j \ne 1\).

Now for \(j=2,3,\ldots ,S\), define \(\tilde{\mathcal {G}}_j\) as the labelled graph \(\mathcal {G}_j\) but all negative labels become positive instead. Note that \(\tilde{\mathcal {G}}_j\) is indeed right-resolving. Let \(\tilde{A}_j\) be its adjacency matrix. Clearly, we have \(\left|\left( A_j\right) _{uv}\right|\le (\tilde{A}_j)_{uv}\) for each uv-entry, and consequently \(\rho (A_j) \le \rho (\tilde{A}_j)\) (see [23]). Next, we prove that \(\rho (\tilde{A}_j) < \lambda \) for \(j \ne 1\).

Lemma 3

\(\rho (\tilde{A}_j) < \lambda \) for \(j \ne 1\).

Proof

Let \(\tilde{\mathcal {X}}_j\) be the sofic shift presented by \(\tilde{\mathcal {G}}_j\). It is easy to see that \(\tilde{\mathcal {X}}_j \subseteq \mathcal {X}\). Indeed, due to the constructions of \(\mathcal {G}_j\) and \(\tilde{\mathcal {G}}_j\), any bi-infinite path in \(\tilde{\mathcal {G}}_j\) gives j corresponding bi-infinite paths in \(\mathcal {G}\). All these paths have the same label.

We claim that \(\tilde{\mathcal {X}}_j \ne \mathcal {X}\) for \(j \ne 1\). Take a synchronising word \(w \in \mathcal {B}(\mathcal {X})\) in \(\mathcal {G}\). Let \(x \in \mathcal {X}\) be a point containing w, i.e. there exists \(k \in \mathbb {Z}\) such that \(x_k x_{k+1}\ldots x_{k+|w |-1} = w\). For the sake of contradiction, suppose that \(x \in \tilde{\mathcal {X}}_j\). There exists a bi-infinite path \(\tilde{p}\) in \(\tilde{\mathcal {G}}_j\) with label x. This path gives bi-infinite paths \(p_1, p_2, \ldots , p_j\) in \(\mathcal {G}\). Since w is synchronising in \(\mathcal {G}\), the edges at coordinate \(k+|w |-1\) for the paths \(p_1,p_2, \ldots ,p_j\) have the same terminal vertex v in \(\mathcal {G}\). Hence, the edge at the said coordinate for the path \(\tilde{p}\) has the terminal vertex \(\{v\}\) in \(\tilde{\mathcal {G}}_j\). This is a contradiction since any vertex in \(\tilde{\mathcal {G}}_j\) is a subset of j distinct vertices from \(\mathcal {G}\). Overall, this shows that \(x \not \in \tilde{\mathcal {X}}_j\) and consequently \(\tilde{\mathcal {X}}_j \subsetneq \mathcal {X}\).

Since \(\tilde{\mathcal {X}}_j\) is a proper subshift of \(\mathcal {X}\), the topology entropy of \(\tilde{\mathcal {X}}_j\) is strictly less than that of \(\mathcal {X}\). This implies that

$$\begin{aligned} \ln \rho (\tilde{A}_j) = h(\tilde{\mathcal {X}}_j) < h(\mathcal {X}) = \ln \lambda \end{aligned}$$

and hence \(\rho (\tilde{A}_j) < \lambda \). \(\square \)

Tracing back the arguments above, we deduce the orbit growth of \(\mathcal {X}\) based on Theorem 1.

Theorem 4

Let \(\mathcal {X}\) be an irreducible sofic shift with topological entropy \(\ln \lambda >0\). Suppose that its minimal right-resolving presentation has period p. Then,

$$\begin{aligned} \pi (N)&\sim \frac{p \lambda ^{p\left( \left\lfloor \frac{N}{p}\right\rfloor +1\right) }}{N(\lambda ^p-1)},\quad \mathcal {M}(N) \sim \frac{pe^{-\gamma }}{\alpha N} \quad \text {and}\\ \mathscr {M}(N)&= \ln \left\lfloor \frac{N}{p}\right\rfloor + \gamma + \ln \alpha -C +o(1) \end{aligned}$$

where \(\gamma \) is the Euler–Mascheroni constant, \(\alpha \) is a positive constant specified by

$$\begin{aligned} \alpha = \lim _{z \rightarrow \lambda ^{-1}} (1-\lambda ^pz^p)\cdot \zeta (z) \end{aligned}$$

where \(\zeta (z)\) is the Artin–Mazur zeta function in (3), and C is another positive constant specified in (1).

Remark 1

For an irreducible sofic shift, the period of the sofic shift is defined as \(\gcd \{n \in \mathbb {N} \mid F(n)>0\}\), where F(n) is the number of periodic points of period n. This period is a divisor of the period of the minimal right-resolving presentation, but they are not necessarily equal (see [23]). Notice that the period of the presentation (which is p) appears in the asymptotic results above, instead of the period of the sofic shift itself. This is interesting to see that the period of the presentation is more prominent in determining the orbit growth.

3 Periodic-Finite-Type Shifts and Their Orbit Growth

Since PFT shifts are a certain type of sofic shifts, we can deduce their orbit growth from Theorem 4. However, we hope to obtain a more specific result. As we shall see, a PFT shift is commonly constructed from some sets of forbidden words instead of a labelled graph. So, we want to relate the number of such sets with the orbit growth. We will discuss this later on.

3.1 Periodic-Finite-Type Shifts

Here, we provide some background on PFT shifts and their important properties. All these facts can be found in [4, 24, 25].

Consider a finite set \(\mathcal {A}\). Let \(\mathcal {S}\) be the set of all finite sequences constructed from \(\mathcal {A}\). For a finite sequence \(w \in \mathcal {S}\) and bi-infinite sequence \(x \in \mathcal {A}^\mathbb {Z}\), we say that w occurs in x at coordinate \(i \in \mathbb {Z}\) if \(x_ix_{i+1}\ldots x_{i+|w |-1} = w\), and denote it as \(w \prec _i x\).

For some \(T \in \mathbb {N}\), we construct finite subsets \(\mathcal {F}_0,\mathcal {F}_1,\ldots ,\mathcal {F}_{T-1}\) of \(\mathcal {S}\) (which can be empty). An element from the subsets is called a forbidden word. Define the set \(\mathcal {X} \subseteq \mathcal {A}^\mathbb {Z}\) as follows: \(x \in \mathcal {X}\) if there exists \(s \in \{0,1,\ldots ,T-1\}\) such that for all \(i \in \mathbb {Z}\), we have \( w\not \prec _{s+i} x\) for all \(w \in \mathcal {F}_{i \text { mod } T}\). The periodic-finite-type (PFT) shift constructed from \(\mathcal {F}_0,\mathcal {F}_1,\ldots ,\mathcal {F}_{T-1}\) is the set \(\mathcal {X}\) equipped with the shift map \(\sigma \) as defined previously. We call T the (PFT)-period of \(\mathcal {X}\). For special case \(T=1\), the shift \(\mathcal {X}\) is called a shift of finite type.

Intuitively, each point \(x \in \mathcal {X}\) has its own initial coordinate s such that no forbidden word from \(\mathcal {F}_0\) occurs at coordinate s, no forbidden word from \(\mathcal {F}_1\) occurs at coordinate \(s+1\), and so on. This is similarly true for going backwards.

A PFT shift can be constructed from different collections of such sets, and even different periods (see Example 1). In fact, we can modify the sets such that all forbidden words in the sets have the same length.

A PFT shift is a sofic shift, i.e. it can be presented by a labelled graph. Let \(\mathcal {X}\) be a PFT shift of period T such that all forbidden words have the same length \(\ell \in \mathbb {N}\). We construct a labelled graph for \(\mathcal {X}\), which is a T-partite graph, as follows:

  1. (i)

    the vertex set is partitioned into some subsets (or parts) \(V_0, V_2, \ldots , V_{T-1}\) such that \(V_j = \mathcal {A}^{\ell } {\setminus } \mathcal {F}_j\) for all \(j \in \{0,1, \ldots ,T-1\}\), where \(\mathcal {A}^{\ell }\) is the set of all finite sequences from \(\mathcal {A}\) of length \(\ell \);

  2. (ii)

    for all j, there exists an edge from vertex \(v=a_1a_2\ldots a_{\ell } \in V_j\) to vertex \(\tilde{v}=b_1b_2\ldots b_{\ell } \in V_{j+1\;\text {mod}\;T }\) if \(a_2a_3\ldots a_\ell = b_1b_2\ldots b_{\ell -1}\), and its label is \(b_{\ell }\).

We call this graph as Moision–Siegel (MS) presentation of \(\mathcal {X}\).

Remark 2

The MS presentation constructed in [4, 24, 25] requires further modification that all sets except \(\mathcal {F}_0\) are empty. However, this is not needed here.

Note that MS presentation is right-resolving. Unfortunately, the irreducibility of a PFT shift is not equivalent to the irreducibility of its MS presentation. If the presentation is irreducible, then the shift itself is irreducible. However, the converse is false (see Example 1).

The Artin–Mazur zeta function of a PFT shift had been obtained in closed form in [25]. Then in [4], it was used in our approach to determine the orbit growth of irreducible PFT shifts with irreducible MS presentations as shown in Theorem 2. However, we will skip the details of the zeta function since it is not needed in our work here.

3.2 Orbit Growth of Periodic-Finite-Type Shifts

The construction of a PFT shift depends on the number of sets of forbidden words, or equivalently, the PFT-period. We can expect that this period affects its orbit growth too. Indeed, by comparing the results of Theorems 2 and 4, we observe that the period p of the minimal right-resolving presentation is a multiple of the PFT-period T, though so far, this is only true for an irreducible PFT shift with irreducible MS presentation. Our target now is to extend this finding to any irreducible PFT shift, and then obtain its orbit growth.

Let \(\mathcal {X}\) be a PFT shift with period T. By previous reason, we shall assume that \(\mathcal {X}\) is irreducible and its topological entropy is positive. We assume that all forbidden words have the same length \(\ell \).

We shall highlight that there are two issues with the current form of \(\mathcal {X}\), as described below.

  1. (i)

    The period T may be unnecessarily large due to repetition. If so, a smaller period shall be sufficient to describe \(\mathcal {X}\).

  2. (ii)

    Its MS presentation may be reducible despite that \(\mathcal {X}\) is irreducible.

We will show that there is a collection of sets of forbidden words such that the period is as small as possible, and the resulting MS presentation is irreducible.

Proposition 5

Let \(\mathcal {X}\) be an irreducible PFT shift with period T constructed from the sets \(\mathcal {F}_0, \mathcal {F}_1, \ldots , \mathcal {F}_{T-1}\). Then, there exist \(\mathcal {T}\) and sets \(\tilde{\mathcal {F}}_0, \tilde{\mathcal {F}}_1, \ldots , \tilde{\mathcal {F}}_{\mathcal {T}-1}\) of forbidden words such that

  1. (i)

    \(\tilde{\mathcal {F}}_0, \tilde{\mathcal {F}}_1, \ldots , \tilde{\mathcal {F}}_{\mathcal {T}-1}\) construct the same PFT shift \(\mathcal {X}\),

  2. (ii)

    all forbidden words have the same length,

  3. (iii)

    \(\tilde{\mathcal {F}}_0, \tilde{\mathcal {F}}_1, \ldots , \tilde{\mathcal {F}}_{\mathcal {T}-1}\) are not a repeated sequence (thus, \(\mathcal {T}\) is minimal), and

  4. (iv)

    the MS presentation based on \(\tilde{\mathcal {F}}_0, \tilde{\mathcal {F}}_1, \ldots , \tilde{\mathcal {F}}_{\mathcal {T}-1}\) is irreducible.

Proof

We can assume that all forbidden words in \(\mathcal {F}_0, \mathcal {F}_1, \ldots , \mathcal {F}_{T-1}\) have the same length \(\ell \). Let \(\mathcal {G}\) be the MS presentation based on the original sets. Since \(\mathcal {X}\) is irreducible, we can find a maximal irreducible component \(\tilde{\mathcal {G}}\) of \(\mathcal {G}\) which presents \(\mathcal {X}\). The irreducibility implies that \(\tilde{\mathcal {G}}\) is a T-partite graph. Denote the partition of the vertex set of \(\tilde{\mathcal {G}}\) as \(\tilde{V}_0, \tilde{V}_1, \ldots ,\tilde{V}_{T-1}\).

Now, construct the new sets \(\tilde{\mathcal {F}}_0, \tilde{\mathcal {F}}_1, \ldots , \tilde{\mathcal {F}}_{T-1}\) such that \(\tilde{\mathcal {F}}_j = \mathcal {A}^\ell {\setminus } \tilde{V}_j\) for all j. Choose the smallest \(\mathcal {T}\), which is a multiple of T, such that \(\tilde{\mathcal {F}}_0, \tilde{\mathcal {F}}_1, \ldots , \tilde{\mathcal {F}}_{\mathcal {T}-1}\) forms the sequence \(\tilde{\mathcal {F}}_0, \tilde{\mathcal {F}}_1, \ldots , \tilde{\mathcal {F}}_{T-1}\) by repeating itself \(\nicefrac {T}{\mathcal {T}}\) times. It is easy to check that \(\mathcal {T}\) and \(\tilde{\mathcal {F}}_0, \tilde{\mathcal {F}}_1, \ldots , \tilde{\mathcal {F}}_{\mathcal {T}-1}\) satisfy all properties above, so we skip the proof here. \(\square \)

We shall call the setting above as a minimal form of \(\mathcal {X}\). The period \(\mathcal {T}\) is called the minimal period of \(\mathcal {X}\). Note that a minimal form is not unique since the collection of sets \(\tilde{\mathcal {F}}_0, \tilde{\mathcal {F}}_1, \ldots , \tilde{\mathcal {F}}_{\mathcal {T}-1}\) can vary (see Example 1). However, we will show later that \(\mathcal {T}\) is indeed unique (see Corollary 7).

Since the MS presentation of a minimal form of \(\mathcal {X}\) is right-resolving and irreducible, its merged graph is indeed the minimal right-resolving presentation. Interestingly, the latter presentation is found to be a \(\mathcal {T}\)-partite graph too.

Proposition 6

Let \(\mathcal {X}\) be an irreducible PFT shift in minimal form with period \(\mathcal {T}\). Then, its minimal right-resolving presentation is a \(\mathcal {T}\)-partite graph.

Proof

Let \(\ell \) be the length of all forbidden words, and \(\mathcal {G}\) be the MS presentation of the minimal form. Denote the partition of its vertex set as \(V_0, V_1, \ldots , V_{\mathcal {T}-1}\). Consider the equivalence relation in the merged graph of \(\mathcal {G}\). We claim that two vertices \(v_i \in V_i\) and \(v_j \in V_j\) with \(i \ne j\) are in different equivalence classes. In other words, we will show that \(v_i\) and \(v_j\) have distinct follower sets in \(\mathcal {G}\).

Without loss of generality, let \(i<j\). Note that there exists a pair \(V_k\) and \(V_{k+j-i \text { mod }\mathcal {T}}\) for some k such that \(V_k \ne V_{k+j-i \text { mod }\mathcal {T}}\). Otherwise, the partition \(V_0, V_1, \ldots , V_{\mathcal {T}-1}\) and hence the sets \(\tilde{\mathcal {F}}_0, \tilde{\mathcal {F}}_1, \ldots , \tilde{\mathcal {F}}_{\mathcal {T}-1}\) are repeated sequences. This contradicts the properties of the minimal form of \(\mathcal {X}\).

Suppose that there exists \(v \in V_k\) such that \(v \not \in V_{k+j-i \text { mod }\mathcal {T}}\). Denote the vertex \(v_i \in V_i\) as the word \(v_i=a_1a_2\ldots a_{\ell }\). Since \(\mathcal {G}\) is irreducible, there exists a path from \(v_i\) to v in \(\mathcal {G}\). We choose such path p of length at least \(\ell \). Denote its label as \(w=b_1b_2 \ldots b_{|w|}\). Observe that p passes through the following vertices:

$$\begin{aligned} v_i = a_1a_2\ldots a_{\ell }&\in V_i,\\ a_2a_3\ldots a_{\ell } b_1&\in V_{i+1},\\ a_3a_4\ldots a_{\ell } b_1 b_2&\in V_{i+2\,\text {mod}\,\mathcal {T}},\\&\vdots \\ v = b_{|w|-\ell +1}b_{|w|-\ell +2} \ldots b_{|w|}&\in V_k. \end{aligned}$$

This shows that w ends with the word v. We claim that there is no path with label w that begins at \(v_j \in V_j\). Indeed, if such path exists, then we can use the argument above to show that it ends with the vertex \(v \in V_{k+j-i\,\text {mod}\,\mathcal {T}}\). This contradicts our initial assumption above.

This implies that \(v_i\) and \(v_j\) have distinct follower sets. The opposite case where \(v \in V_{k+j-i\,\text {mod}\,\mathcal {T}}\) but \(v \not \in V_k\) is proved similarly as above with \(v_j\) instead. Since each equivalence class can only contain vertices in the same part of the partition, the resulting merged graph of \(\mathcal {G}\), which is its minimal right-resolving presentation, is still a \(\mathcal {T}\)-partite graph. \(\square \)

Corollary 7

For an irreducible PFT shift, its minimal period is unique.

Proof

Consider two minimal forms of an irreducible PFT shift \(\mathcal {X}\) with minimal periods \(\mathcal {T}_1\) and \(\mathcal {T}_2\). The merged graphs of their MS presentations are indeed the minimal right-resolving presentations of \(\mathcal {X}\), which are \(\mathcal {T}_1\)-partite and \(\mathcal {T}_2\)-partite graphs, respectively. The minimal right-resolving presentations are unique up to graph isomorphism, so \(\mathcal {T}_1 =\mathcal {T}_2\). \(\square \)

Remark 3

Given two minimal forms, their MS presentations may not be isomorphic. Actually, we can prove that their presentations are related by graph amalgamation and splitting (see [23]). However, these notions are not needed in our work here.

Finally, we can now deduce the orbit growth of any irreducible PFT shift. Proposition 6 implies that the period of its minimal right-resolving presentation is a multiple of its minimal period. Hence, Theorem 4 implies the desired orbit growth, which is shown below.

Theorem 8

Let \(\mathcal {X}\) be an irreducible PFT shift of minimal period \(\mathcal {T}\) with topological entropy \(\ln \lambda >0\). Then,

$$\begin{aligned} \pi (N)&\sim k\mathcal {T} \cdot \frac{ \lambda ^{k\mathcal {T}\left( \left\lfloor \frac{N}{k\mathcal {T}}\right\rfloor +1\right) }}{N(\lambda ^{k\mathcal {T}}-1)},\quad \mathcal {M}(N) \sim \frac{k\mathcal {T}e^{-\gamma }}{\alpha N} \quad \text {and}\\ \mathscr {M}(N)&= \ln \left\lfloor \frac{N}{k\mathcal {T}}\right\rfloor + \gamma + \ln \alpha -C +o(1) \end{aligned}$$

where \(k\mathcal {T}\) is the period of its minimal right-resolving presentation for some \(k \in \mathbb {N}\), \(\gamma \) is the Euler–Mascheroni constant, \(\alpha \) is a positive constant specified in (2), and C is another positive constant specified in (1).

Example 1

Set \(\mathcal {A}=\{0,1\}\). Let \(\mathcal {X}\) be a PFT shift constructed from the following sets:

$$\begin{aligned} \mathcal {F}_0&=\{01,10,11\}, \quad \mathcal {F}_1=\{10,11\}, \quad \mathcal {F}_2=\{11\}, \\ \mathcal {F}_3&=\mathcal {F}_0, \quad \mathcal {F}_4=\mathcal {F}_1, \quad \mathcal {F}_5=\{01,11\}. \end{aligned}$$
Fig. 1
figure 1

The MS presentation of \(\mathcal {X}\) based on the sets \(\mathcal {F}_0, \mathcal {F}_1, \ldots ,\mathcal {F}_5\)

Full size image
Fig. 2
figure 2

The MS presentation of \(\mathcal {X}\) based on the sets \(\tilde{\mathcal {F}}_0, \tilde{\mathcal {F}}_1, \tilde{\mathcal {F}}_2\)

Full size image
Fig. 3
figure 3

The minimal right-resolving presentation of \(\mathcal {X}\)

Full size image
Fig. 4
figure 4

The MS presentation of \(\mathcal {X}\) based on the sets \(\mathcal {F}'_0, \mathcal {F}'_1, \mathcal {F}'_2\)

Full size image
  1. (a)

    MS presentation

    The corresponding MS presentation is shown in Fig. 1. Observe that the vertex \(01 \in V_2\) is a sink. So, the presentation is reducible. By removing the vertex and its incoming edge, the resulting graph is irreducible and still presents \(\mathcal {X}\) (see [23]). This implies that \(\mathcal {X}\) is irreducible. This example shows that an irreducible PFT shift does not necessarily produce an irreducible MS presentation.

  2. (b)

    Minimal form and minimal right-resolving presentation

    We follow the proof of Proposition 5 to obtain the minimal form of \(\mathcal {X}\) with the following sets:

    $$\begin{aligned} \tilde{\mathcal {F}}_0=\{01,10,11\}, \quad \tilde{\mathcal {F}}_1=\{10,11\}, \quad \tilde{\mathcal {F}}_2=\{01,11\}. \end{aligned}$$

    The corresponding MS presentation is shown in Fig. 2. We can obtain the minimal right-resolving presentation of \(\mathcal {X}\) in Fig. 3 by forming the merged graph of the above presentation.

    Now, consider the PFT shift constructed from the following sets:

    $$\begin{aligned} \mathcal {F}'_0&= \{001, 010, 011, 101, 110, 111\},\\ \mathcal {F}'_1&= \{010, 011, 100, 101, 110, 111\},\\ \mathcal {F}'_2&= \{001, 011, 100, 101, 110, 111\}. \end{aligned}$$

    The corresponding MS presentation is shown in Fig. 4. We can verify that these sets construct the same shift \(\mathcal {X}\) and in fact, this is a minimal form of \(\mathcal {X}\). This example shows that a minimal form of an irreducible PFT shift is not unique, but the minimal period remains the same.

    As a side note, the graph in Fig. 4 can be formed from the one in Fig. 2 by in-splitting the vertex \(00 \in \tilde{V}_0\) into the vertices \(000, 100 \in V'_0\). This example demonstrates that the MS presentations of minimal forms are related by graph amalgamation and splitting, as previously mentioned in Remark 3.

  3. (c)

    Orbit growth

    We obtain the zeta function of \(\mathcal {X}\) by using Fig. 3 and following its construction in (3). It is given as

    $$\begin{aligned} \zeta (z) = \frac{1+z+z^2}{1-2z^3}. \end{aligned}$$

    We calculate the values of constants in Theorem 8 as follows:

    $$\begin{aligned} \lambda = 2^{\frac{1}{3}}, \quad \mathcal {T}=3, \quad k=1, \quad \alpha = \frac{1}{2-2^{\frac{2}{3}}}. \end{aligned}$$

    Hence, the orbit growth of \(\mathcal {X}\) is given by

    $$\begin{aligned} \pi (N)&\sim \frac{6 \cdot 2^{\left\lfloor \frac{N}{3}\right\rfloor }}{N},\quad \mathcal {M}(N) \sim \frac{3\left( 2-2^{\frac{2}{3}}\right) e^{-\gamma }}{N} \quad \text {and}\\ \mathscr {M}(N)&= \ln \left\lfloor \frac{N}{3}\right\rfloor + \gamma - \ln \left( 2-2^{\frac{2}{3}}\right) -C +o(1). \end{aligned}$$

4 Additional Remark: Finite Group and Homogeneous Extensions of Sofic Shifts

As another consequence, our result in Theorem 4 is crucial to prove Chebotarev-like theorems for finite group extensions of sofic shifts, which is similar to the case for shifts of finite type [2, 27, 28]. Here, we provide a simple explanation about this topic.

Let \(\mathcal {X}\) be a sofic shift equipped with the shift map \(\sigma \). Consider a finite group K and a function \(\Psi :\mathcal {X} \rightarrow K\) which depends on the first two coordinates, i.e. if \(x = \{x_k\}_{k \in \mathbb {Z}}\) and \(y = \{y_k\}_{k \in \mathbb {Z}}\) in \(\mathcal {X}\) satisfy \(x_0x_1=y_0y_1\), then \(\Psi (x)=\Psi (y)\). The finite group extension of \(\mathcal {X}\) under K is the product \(\mathcal {X} \times K\) paired with a map \(\hat{\sigma }: \mathcal {X} \times K \rightarrow \mathcal {X} \times K\) where \(\hat{\sigma }(x,g) = \left( \sigma (x), \Psi (x)g\right) \). We also define a free action of K on \(X \times K\) by \(h \cdot (x, g) = (x, gh)\) for any \(h \in K\).

Under this setting, each closed orbit \(\tau \) of \(\mathcal {X}\) is associated with a conjugacy class of K. This is called the Frobenius class of \(\tau \), which is denoted by \([\tau ]\). The class \([\tau ]\) is precisely the conjugacy class for the element

$$\begin{aligned} \Psi \left( \sigma ^{|\tau |-1}(x)\right) \Psi \left( \sigma ^{|\tau |-2}(x)\right) \ldots \Psi \left( x\right) \in K \end{aligned}$$

regardless on the choice of \(x \in \tau \).

Now, we can count the closed orbits which have the same Frobenius class via our orbit counting functions. In other words, for a conjugacy class C of K, define \(\pi _C(N)\), \(\mathcal {M}_C(N)\) and \(\mathscr {M}_C(N)\) similarly, except they sum over the closed orbits with the Frobenius class C. We can follow the same arguments in [2, 27, 28] and apply our result here to obtain the asymptotic behaviours of these counting functions. For instance, if \(\hat{\sigma }\) is topologically mixing on \(\mathcal {X} \times K\), then

$$\begin{aligned} \pi _C(N)&\sim \frac{|C |}{|K |} \cdot \frac{\lambda ^{N+1}}{N(\lambda -1)},\quad \mathcal {M}_C(N) \sim \frac{e^{-\gamma \nicefrac {|C |}{|K |}}}{\beta N^{\nicefrac {|C |}{|K |}}} \quad \text {and}\\ \mathscr {M}_C(N)&= \frac{|C |}{|K |} \ln N + \frac{|C |}{|K |}\gamma + \ln \beta - \mathcal {C} +o(1) \end{aligned}$$

where \(\ln \lambda \) is the topological entropy of \(\mathcal {X}\), \(\gamma \) is the Euler–Mascheroni constant, and \(\beta \) and \(\mathcal {C}\) are some positive constants. We can also prove similar theorems for the finite homogeneous extensions of sofic shifts, and again, the arguments follow similarly as in [27, 28].

5 Conclusion

In this paper, we have obtained the orbit growth of sofic shifts via their Artin–Mazur zeta function in Theorem 4. It was long expected that sofic shifts exhibit somewhat exponential orbit growth due to their rational zeta function. Indeed, our work here has obtained the precise form of the orbit growth. Consequently, this result leads to the orbit growths of the PFT shifts in Theorem 8 and the finite group and homogeneous extensions of sofic shifts.

As a side note, the approach via zeta function is applicable to any discrete dynamical system, as long as its zeta function fulfills the assumptions in Theorem 1. However, it is often very difficult to verify these assumptions for some systems due to the sophisticated form of their corresponding zeta function. As an example in symbolic dynamics, this situation can be seen in sofic-Dyck shifts [29], in which their zeta function is expressed implicitly in terms of several power series. In fact, the zeta function is an algebraic function, thus it is more difficult to study for its analyticity.

Sofic-Dyck shifts are a massive class of shift spaces, which also include sofic shifts. Our future work aims to determine the orbit growth of the sofic-Dyck shifts, or if not, their subshifts such as Markov–Dyck shifts [30] and shift spaces mentioned in [31]. Some advanced theories in other mathematical fields may be required for this purpose. We hope that this paper provides a new interest, insight and idea to the readers to tackle the problem on the orbit growth of those shift spaces.