Abstract
In this paper, we get crucial estimates of fundamental sums that involve the number of closed orbits of the Dyck shift. These estimates are given as the prime orbit theorem, Mertens’ orbit theorem, Meissel’s orbit theorem and Dirichlet series. Different and more direct methods are used in the proofs without any complicated theoretical discussions.
Similar content being viewed by others
1 Introduction
In number theory, the prime-counting function that gives the number of primes less than or equal to x, for any real number x is denoted by \(\pi(x)\). The prime number theorem (PNT) is the statement
This means that
However, the following asymptotic formula for primes p:
where \(\gamma= 0.5772\ldots\) is Euler’s constant and \(x \in \mathbf{R}\), is known as Mertens’ theorem of analytic number theory. The logarithmic equivalent of Mertens’ theorem is
and Mertens’ constant \(B_{1}= 0.2614972128 \ldots\) , where \(f =O ( g )\) means that \(f(x)\) is bounded with respect to \(g(x)\) for all sufficiently large x.
Also, as pointed out by Lindqvist and Peetre [1], Meissel considered the sum
where \(M = \lim_{x \rightarrow\infty }\sum_{p \leq x}\frac{1}{p} - \ln(\ln x) \approx0.2614972128 \ldots\) .
A Dirichlet series is the complex function defined on \(\{z \in \mathbf{C} : \mathbf{Re}(z) > 1 \}\) by the series
where z and \(a_{n}\) are complex numbers, \(n = 1, 2, 3, \ldots \) . If \(a_{n} = 1\) for all n then the Dirichlet series
becomes the Riemann zeta function [2].
Let X be a non-empty set and \(T: X \rightarrow X\) be a map. The pair \((X, T)\) is said to be a dynamical system. Many dynamical questions involve counting the number of closed orbits or the periodic points under iteration of a map. A closed (periodic) orbit τ of length \(|\tau|= n\) for a continuous map \(T: X \rightarrow X\) is a set of the form \(\{x, Tx, T^{2}x, \ldots, T^{n-1}x \} \subset X\) where \(T^{n}x = x\) for some \(x \in X\) and \(n \geq1\).
Let \(T : X \rightarrow X\) be a map, and define
which are the set of points of least period n under T, the set of points of period n under T, and the set of closed orbits of length n under T, respectively. The Möbius inversion formula [3] is defined as follows. If \(f,g: \mathbf {N} \rightarrow\mathbf{C}\) are two arithmetic functions satisfying
then
where \(\mu(n)\) is the Möbius function. Let
It follows that
and
Consequently
and hence, by the Möbius inversion formula,
Inspired by the functions of an algebraic variety over a finite field we are led to obtain a kind of analogs between number theory and dynamical systems. Following the analogy between closed orbits and prime numbers, the asymptotic behavior of expressions like
may be viewed as a dynamical analog of the prime number theorem and a dynamical analog of Mertens’ theorem concerns asymptotic estimates for expressions like
where h denotes the topological entropy of the map T. Moreover, the dynamical analog of Meissel’s theorem is given as an infinite sum of the form
as \(a \rightarrow0^{+}\).
Furthermore, the dynamical Dirichlet series associated to the map \(T: X \rightarrow X\) is the formal series of the form
which alternatively can be expressed as
where \(\zeta(z)\) is the dynamical zeta function given by
The dynamical zeta function is introduced by [4] and based also on an analogy with the number theory zeta functions attached to a function field over a finite field and is one of the tools used in studying orbit-growth properties of maps.
Parry in [5] initiated a line of research which uses ideas and techniques of analytic number theory to attack problems of this nature. When X has a metric structure with respect to which T is hyperbolic or a shift of finite type, results of Parry and Pollicott [6] and Noorani [7] have shown a similar analogy between the number of closed orbits and the prime number theorem. It has been shown that
Sharp in [8] also obtained an analogy between the number of closed orbits and Mertens’ theorem for hyperbolic maps as follows:
for some constant \(C_{1}\).
Several orbit-counting results on the asymptotic behavior of both (5) and (6) for other maps like quasihyperbolic toral automorphism (ergodic but not hyperbolic), can be found for example in [9–11] and [12].
In this paper, analogs between the number of closed orbits of a shift of infinite type called the Dyck shift and (1), (2), (3), and (4) have been obtained. Instead of using the zeta function approach to prove our results, different and more direct methods are used without any complicated theoretical discussion.
Authors in [13], have obtained analogs between the number of closed orbits of the Dyck shift and only (1) and (2). However, later authors have explored a minor mistake in the proof of the first theorem. In this note, we improve the minor mistake detected in the proof of the first theorem, which yields a more correct estimate. We also obtain sharper estimates for the second theorem in [13].
2 The Dyck shift
A complete introduction to the theory of symbolic dynamics can be found in [14]. Let \(\mathcal{A}\) be a finite alphabet. On \(\mathcal{A}^{\mathbf {Z}}\) there acts the shift that sends the point \((x_{i})_{i \in\mathbf {Z}} \in\mathcal{A}^{\mathbf{Z}}\) into the point \((x_{i+1})_{i \in \mathbf{Z}} \in\mathcal{A}^{\mathbf{Z}}\). The dynamical systems that are given by the closed shift invariant subsets of \(\mathcal {A}^{\mathbf{Z}}\), with the restriction of the shift acting on them, are called subshifts. These are studied in symbolic dynamics. An element of \(\mathcal{A}^{n}\) will be called a word, or a block of length n. A word of length 0 is called an empty word and denoted by ε. The set of all finite words with letters taken from \(\mathcal{A}\) is the set \(\mathcal{A}^{\ast} = \bigcup_{n= 0}^{\infty} \mathcal{A}^{n}\). A word is called admissible for the subshift \(X \subset\mathcal{A}^{\mathbf{Z}}\) if it appears somewhere in a point of X. Let \(X \subset\mathcal{A}^{\mathbf{Z}}\) and let \(\mathcal{B}_{n}(X)\) denote the set of all admissible words of length n in X. Then the language of X is the collection \(\mathcal {B}(X)= \bigcup_{n=0}^{\infty} \mathcal{B}_{n}(X)\). The topological entropy of a subshift \(X \subset\mathcal{A}^{\mathbf{Z}}\) is given by
Let \(\mathcal{A} = \{{\ell_{1}}, {\ell_{2}},\ldots, {\ell _{M}}, {r_{1}}, {r_{2}}, \ldots, {r_{M}} \}\). The alphabet consists of M pairs of matching left and right delimiters or symbols. Let \(\mathcal{M}\) be a monoid (with zero) with generators \({\ell _{i}}\), \({r_{i}}\), \(1 \leq i \leq M\), and 1. The relations on the monoid are
We use a mapping \(\operatorname{red}(\,) : \mathcal{A}^{\ast} \rightarrow\mathcal{M} \) such that for
The Dyck shift \(\mathrm{D}_{M}\) [15] is defined by
where \(x_{[i,j)} = x_{i}x_{i+1} \cdots x_{j-1}\).
When \(M = 1\), \(\mathrm{D}_{1}\) is the full shift on two symbols; we will tacitly assume that \(M \geq2\). The topological entropy of the Dyck shift \(\mathrm{D}_{M}\) is already computed as \(\log (M+1 )\) in [15].
The number of points [16] in the Dyck shift \(\mathrm{D}_{M}\) having period n is given by
3 Counting closed orbits
In this section, we first give a lower bound and an upper bound for the number of periodic points of the Dyck shift and then apply such a result to obtain asymptotic formulas for the dynamical analogs of the prime number theorem, Merten’s theorem, Meissel’s theorem, and Dirichlet series.
Lemma 3.1
There exist constants \(0 < c_{1} < 1\) and \(c_{2}> 1\) such that the following inequality holds for all \(n \geq1\):
where \(F(n)\) denotes the number of periodic points in the Dyck shift.
Proof
Assume that n is even. The case n is odd can be proved analogously. Note then first that
Therefore, we obtain
Also
Estimating the term \([1 - \frac{\sum_{i=0}^{\frac {n}{2}} {n \choose i}M^{i}}{(M+1)^{n}} ]\) using the binomial theorem we obtain
We set
using the definition of the binomial coefficient it is easy to prove that
also
and utilizing (9) and (10) we obtain
Applying inequality (11) to (8), we get
hence, inequality (7) implies that
Thus, if we take \(c_{1}= \frac{M^{2}}{1 + M^{2}}\) and \(c_{2} = 3\), then we are done. □
Theorem 3.2
(Prime orbit theorem)
Let \(\sigma:\mathrm {D}_{M} \rightarrow\mathrm{D}_{M}\) be the Dyck shift. Let \(\pi (N) = \sum_{n \leq N} {O}_{\sigma}(n)\) be the number of closed orbits of σ not exceeding N. Then there exist constants \(C_{1}\) and \(C_{2}\) such that
Proof
For the sake of notation let us denote \(A=M+1\). First of all by using Lemma 3.1, we would like to show that
Indeed,
Similarly
Now using (12) we prove the main theorem. Applying the Möbius inversion formula to the functions \(F(n)\) and \({O}(n)\), where \({O}(n)\) is the number of closed orbits with length n, we have
Subtracting the dominant terms, we obtain
To estimate the dominant terms, let \(K(N)= { \lfloor {N}^{\frac{1}{4}} \rfloor}\). Then
Utilizing Lemma 3.1 we have
Therefore, summarizing (13), (14), and (15) and using \(K(N)\leq N^{\frac{1}{4}}\) we get
Hence we have obtained an upper bound. To obtain the lower bound, first we estimate the following sum for \(n\geq8\):
for all \(n \geq8\). Therefore, using (17) we obtain
This, together with (16), proves the theorem. □
Theorem 3.3
(Mertens orbit theorem)
Let \(\sigma:\mathrm{D}_{M} \rightarrow\mathrm{D}_{M}\) be the Dyck shift and \(\mathcal{M}(N)= \sum_{n \leq N} \frac {O_{\sigma}(n)}{{e}^{h n}}\). Then there exist constants \(C_{3}\) and \(C_{4}\) such that
Proof
The dynamical Mertens theorem asserts that
First of all, we want to estimate the term
Note that
for all natural numbers n. Hence by using Lemma 3.1 we get
since \(e^{hn} = A^{n}\). Now
From (18) and (19), we can conclude that
For the lower bound, using again (17) and Lemma 3.1 we obtain
This and (20) complete the proof. □
Theorem 3.4
(Meissel’s orbit theorem)
Let \(\sigma:\mathrm{D}_{M} \rightarrow\mathrm{D}_{M}\) be the Dyck shift. Then there exist constants \(C_{5}\) and \(C_{6}\) such that
for any \(k> 0\).
Proof
To prove this theorem we first estimate \(O(n)\). By using Lemma 3.1, we get
On the other hand, using equation (17), we obtain
since \(e^{hn} = A^{n}\). Also
To finish this, we use the following inequality:
Calculating the last integral and applying into (23) and (24) gives
□
A simple formula for the zeta function of the Dyck shift \(\mathrm {D}_{M}\) over 2M symbols has been obtained by [17]. He showed that
Keller proved this formula using the so-called circular codes. By circular codes we mean a set C of finite sequences over a finite alphabet \(\mathcal{A}\) such that each two-sided infinite periodic sequence of letters from \(\mathcal{A}\) has at most one decomposition into words from C.
Theorem 3.5
(Dirichlet series)
There exist constants \(C_{7}\) and \(C_{8}\) such that
where \(A = M+1\) and \(\zeta ( z )\) is the zeta function of the Dyck shift.
Proof
By Lemma 3.1, we get
Also
□
References
Lindqvist, P, Peetre, J: On a number theoretic sum considered by Meissel. Nieuw Arch. Wiskd. 15, 175-179 (1997)
Patterson, SJ: An Introduction to the Theory of the Riemann Zeta-Function. Cambridge Studies in Advanced Mathematics, vol. 14. Cambridge University Press, Cambridge (1988)
Hardy, GH, Wright, EM: An Introduction to the Theory of Numbers. Oxford University Press, Oxford (1938)
Artin, M, Mazur, B: On periodic points. Ann. Math. 81(2), 82-99 (1965)
Parry, W: An analogue of the prime number theorem for closed orbits of shifts of finite type and their suspensions. Isr. J. Math. 45, 41-52 (1983)
Parry, W, Pollicott, M: An analogue of the prime number theorem for closed orbits of Axiom A flows. Ann. Math. 118, 573-591 (1983)
Noorani, MSM: Counting closed orbits of hyperbolic diffeomorphisms. Results Math. 50, 241-257 (2007)
Sharp, R: An analogue of Mertens’ theorem for closed orbits of Axiom A flows. Bol. Soc. Bras. Mat. 21, 205-229 (1991)
Everest, D, Miles, R, Stevens, S, Ward, T: Orbit-counting in non-hyperbolic dynamical systems. J. Reine Angew. Math. 608, 155-182 (2007)
Noorani, MSM: Mertens’ theorem and closed orbits of ergodic toral automorphisms. Bull. Malays. Math. Sci. Soc. (2) 22, 127-133 (1999)
Waddington, S: The prime orbit theorem for quasihyperbolic toral automorphisms. Monatshefte Math. 112, 235-248 (1991)
Jaidee, S, Stevens, S, Ward, T: Mertens’ theorem for toral automorphisms. Proc. Am. Math. Soc. 139, 1819-1824 (2011)
Alsharari, F, Noorani, MSM, Akhadkulov, H: Counting closed orbits for the Dyck shift. Abstr. Appl. Anal. 2014, Article ID 304798 (2014)
Marcus, B, Lind, D: An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, Cambridge (1995)
Krieger, W: On the uniqueness of equilibrium state. Math. Syst. Theory 8, 97-104 (1974)
Hamachi, T, Inoue, K: Embedding shifts of finite type into the Dyck shift. Monatshefte Math. 145, 107-129 (2005)
Gerhard, K: Circular codes, loop counting, and zeta-functions. J. Comb. Theory 56, 75-83 (1991)
Acknowledgements
The authors would like to acknowledge the grant: UKM Grant DIP-2014-034 and Ministry of Education, Malaysia grant FRGS/1/2014/ST06/UKM/01/1, DIP-2012-31, AP-2013-009, and Modal Insan Berpusat (RAE3) for financial support. The authors also would like to thank the referee for his/her careful reading of the paper and useful suggestions.
Author information
Authors and Affiliations
Corresponding author
Additional information
Competing interests
The authors declare that they have no competing interests.
Authors’ contributions
All authors contributed equally to this work. All authors read and approved the final manuscript.
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
About this article
Cite this article
Alsharari, F., Noorani, M.S.M. & Akhadkulov, H. Estimates on the number of orbits of the Dyck shift. J Inequal Appl 2015, 372 (2015). https://doi.org/10.1186/s13660-015-0899-6
Received:
Accepted:
Published:
DOI: https://doi.org/10.1186/s13660-015-0899-6