# Counting Closed Orbits for the Dyck Shift

Authors: Fahad Alsharari; Mohd Salmi Md. Noorani; Habibulla Akhadkulov
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

The prime orbit theorem and Mertens’ theorem are proved for a shift dynamical system of infinite type called the Dyck shift. Different and more direct methods are used in the proof without any complicated theoretical discussion.


---

## Body

## 1. Introduction and Preliminaries

In number theory, recall that, for functionsf,g:R→R, one says f=Og means that f(x) is bounded with respect to g(x) for all sufficiently large x. That is, there exist constants c and x0 such that
(1)fx<cgx,∀x≥x0,
and fx is asymptotic to g(x), denoted by f~g, if
(2)lim⁡x→∞fxgx=1.
The prime-counting function that gives the number of primes less than or equal to x, for any real number x, is denoted by πx. The prime number theorem (PNT) is the statement
(3)π(x)~xlog⁡(x).However, the asymptotic formula for primesp,
(4)∏p≤x‍1-1p~e-γlog⁡x,
where γ=0.5772… is Euler’s constant and x∈R, is known as Mertens’ theorem of analytic number theory. The logarithmic equivalent of Mertens’ theorem is
(5)∑p≤x‍1p=loglogx+B1+O1log⁡x,
and Mertens’ constant B1=0.2614972128….LetX be a nonempty set and T:X→X a map. The pair (X,T) is said to be a dynamical system. In techniques, a dynamical system is an abstract mathematical model describing the time dependence of point’s position in its space. This is conventionally modeled by the map T whose iterates denote the passage of time. 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 τ=n for a continuous map T:X→X is a set of the form x,Tx,T2x,…,Tn-1x⊂X where Tnx=x for some x∈X and n≥1.LetT:X→X be a map, and define
(6)LTn=x∈X:Tkxk∈N=n,FTn=x∈X:Tnx=x,OTn=τ:τisaclosedorbitofToflenghτ=n,
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. It is well known that the Möbius function, μ(n) of n=1,2,3,…, is
(7)μn=1ifn=1;-1kifnisaproductofkdistinctprimes;0otherwise.Indeed,μn≤1 for any natural number n. Moreover, the sum over all positive divisors of n of the Möbius function is zero except when n=1. The Möbius Inversion Formula [1] is defined as follows. If f,g:N→C are two arithmetic functions satisfying
(8)gn=∑d|n‍fd,∀n,
then
(9)fn=∑d|n‍μndgd,∀n.Let(10)LTn=LTn,FTn=FTn,OTn=OTn.It follows that(11)OTn=LTnn,FTn=∑d∣n‍LTd.
Consequently
(12)FT(n)=∑d∣n‍dOT(d),
and, hence, by Möbius Inversion Formula,
(13)OTn=1n∑d|n‍μndFTd.
Following the analogy between closed orbits and prime numbers, the asymptotic behavior of expressions like
(14)πTN=τ:τ≤N
may be viewed as a dynamical analogue of the prime number theorem and a dynamical analogue of Mertens’ theorem concerns asymptotic estimates for expressions like
(15)MTN=∑n≤N‍OTnehn,
where h denotes the topological entropy of the map T.Parry in [2] 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 shift of finite type (which will be given in detail in the subsequent section), results of Parry and Pollicott [3] and Noorani [4] have shown similar analogy between the number of closed orbits and the prime number theorem. It has been shown that
(16)πTN~ehN+1Neh-1.
Sharp in [5] also obtained an analogy between the number of closed orbits and Mertens’ theorem for hyperbolic maps as follows
(17)MT(N)~log⁡N+C1,
for some constant C1.Several orbit-counting results on the asymptotic behavior of both (14) and (15) for other maps like quasihyperbolic toral automorphism (ergodic but not hyperbolic) can be found, for example, in [6–9].In this paper, analogies between the number of closed orbits of a shift of infinite type called the Dyck shift and both (3) and (4) have been obtained. This paper is organized as follows. In the first section some introduction and preliminaries are given. In the second section the Dyck shift is introduced. The prime orbit theorem and Mertens’ theorem are proved in Section 3.


## 2. The Dyck Shift

LetA be a finite alphabet. On AZ there acts the shift that sends the point (xi)i∈Z∈AZ into the point (xi+1)i∈Z∈AZ. The dynamical systems that are given by the closed shift invariant subsets of AZ, with the restriction of the shift acting on them, are called subshifts. These are studied in symbolic dynamics. An element of An will be known as 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 A is the set A*=⋃n=0∞‍An. A word is called admissible for the subshift X⊂AZ if it appears somewhere in a point of X. Let X⊂AZ and let Bn(X) denote the set of all admissible words of length n in X. Then the language of X is the collection BX=⋃n=0∞‍BnX. The topological entropy of a subshift X⊂AZ is given by
(18)h(X)=lim⁡n→∞1nlog⁡BnX.Subshifts can be also defined using the notion of forbidden sets. LetF be a collection of words over A, that is, F⊂A*, which is called the forbidden set. For any such F, define XF to be the subset of sequences in AZ which do not contain any word in F. Then, the subshift is a subset X of a full shift AZ such that X=XF for some collection F of forbidden blocks over A. If furthermore F is finite, then we call X a subshift of finite type. The golden mean shift which is defined as the shift system over the alphabet A=0,1 having a forbidden set F=11 is a subshift of finite type.The subshift comprises a lot of SFTs (shifts of finite type) in the shift space, which is said to have property A. A class of nonsofic systems, known as the Dyck systems, first suggested by Krieger [10] and named after an early contributor to the study of free groups and formal languages, codifies the rules of matching parentheses, which is one of these shift spaces. The Dyck shift DN which comes from language theory is defined to be the shift system over an alphabet A that consists of N negative symbols and N positive symbols. For an x in the full shift AZ, x is in DN if and only if every finite block appearing in x has a nonzero reduced form. Therefore, the constraint for x cannot be bounded. A beautiful way to describe the Dyck shift is in terms of its syntactic monoid.LetA=l1,l2,…,lM,r1,r2,…,rM. The alphabet consists of M pairs of matching left and right delimiters or symbols. Let M be a monoid (with zero) with generators li,ri, 1≤i≤M, and 1. The relations on the monoid are
(19)li∘rj=1ifi=j,1≤i,j≤M,li∘rj=0ifi≠j,1≤i,j≤M,α∘1=1∘α=α,α∈A∪1,α∘0=0∘α=0,α∈A∪1,0∘0=0.We use a mappingred(): A*→M such that, for
(20)ω=ω1ω2⋯ωn∈A*(n≥1),redω=ω1∘ω2∘⋯∘ωn,redε=1.Definition 1.
The Dyck shiftDM [10] is defined by
(21)DM=x∈AZ:ifi≤j,thenredxi,j≠0,
where x[i,j)=xixi+1⋯xj-1.WhenM=1, D1 is the full shift on two symbols; we will tacitly assume that M≥2. The topological entropy of the Dyck shift DM is already computed as log⁡M+1 in [10].Theorem 2 (see [11]).
The number of points in the Dyck shiftDM having period n is given by
(22)F(n)=2M+1n-∑i=0n/2‍niMi+nn2Mn/2ifniseven;2M+1n-∑i=0(n-1)/2‍niMiifnisodd.


## 3. Counting Closed Orbits

In this section, we prove two theorems that involve the counting of orbits for the Dyck shift, where the first one is the prime orbit theorem and the second one is Mertens’ orbit theorem. However, in order to prove these theorems, we firstly prove the following lemma which plays an important role in proving our main results.Lemma 3.
There exist constants0<c1<1 and c2>1 such that the following inequality holds for all n≥1:
(23)c1M+1n≤Fn≤c2M+1n.Proof.
Assume thatn is even. The case where n is odd can be proved analogously.
Note first that(24)∑i=0n/2‍niMi<M+1n,nn2Mn/2<M+1n.
Therefore, we obtain
(25)Fn=2M+1n1-∑i=0n/2niMiM+1n+nn/2Mn/2M+1n<3M+1n,∀n≥1.
Also
(26)Fn≥M+1n-∑i=0n/2‍niMi+nn2Mn/2=M+1n1-∑i=0n/2niMiM+1n.
Estimating the term 1-∑i=0n/2‍niMi/M+1n using the binomial theorem we obtain
(27)∑i=0n/2niMiM+1n=∑i=0n/2niMi∑i=0n/2-1niMi+nn/2Mn/2+∑i=n/2+1nniMi≤∑i=0n/2niMi∑i=0n/2-1niMi+∑i=n/2+1nniMi.
We set
(28)An≔∑i=0n/2-1‍niMi=∑i=0n/2-1‍nn2-i-1Mn/2-i-1,Bn≔∑i=n+1n‍niMi=∑i=0n/2-1‍nn2+i+1Mn/2+i+1;
using the definition of the binomial coefficient it is easy to prove that
(29)nn2-i-1=nn2+i+1forany0≤i≤n2-1,
and also
(30)Mn/2+i+1≥M2Mn/2-i-1forany0≤i≤n2-1;
utilizing (29) and (30) we obtain
(31)Bn≥M2An.
Applying inequality (31) to (27), we get
(32)∑i=0n/2niMiM+1n≤AnAn+Bn≤AnAn+M2An=11+M2;
hence, inequality (26) implies that
(33)Fn≥M+1n1-11+M2=M21+M2M+1n.
Thus, if we take c1=M2/1+M2 and c2=3, then we are done.Theorem 4 (prime orbit theorem).
LetT:DM→DM be the Dyck shift on a set of M pairs and τ a closed orbit for T. Let π(N) be the number of closed orbits of T not exceeding N and F(n) the number of points having period n under T as given by Theorem 2. Then
(34)π(N)~F(N)N3/4.Proof.
Using Lemma3, we get
(35)∑n≤N‍Fn≤c2∑n≤N‍M+1n=c2M+1N∑n≤N‍M+1n-N≤c211-1/M+1M+1N=c2M+1MM+1N≤c2M+1c1·MFN.
Similarly,
(36)∑n≤N‍Fn≥c1∑n≤N‍M+1n=c1M+1N∑n≤N‍M+1n-N≥c1c2∑n≤N‍M+1n-NFN;
by combining (35) and (36), we obtain
(37)0<c1M+1c2·M≤lim⁡N→∞∑n≤NFnFN≤c2M+1c1·M<∞.
Thus, by Möbius Inversion Formula we have
(38)πN=∑n≤N‍1n∑d∣n‍μndF(d)=∑n≤N‍1n∑d∣n,d<n‍μndF(d)+∑n≤N‍1nF(n).
Subtracting the dominant terms, we obtain
(39)πN-∑n≤N‍1nFn≤∑n≤N‍1n∑d∣n,d<n‍μndFd≤∑n≤N‍1n∑d∣n,d<n‍Fd≤∑n≤N‍∑d∣n,d<n‍Fd;
since d∣n, d<n, then d≤n/2, so
(40)equation39≤∑n≤N‍∑d≤n/2‍F(d)≤∑n≤N‍Fn2=OFN2.
To estimate the dominant terms, let K(N)=N1/4. Then
(41)∑n≤N‍1nFn-∑N-KN≤n≤N‍1nFn≤∑n≤N-KN‍Fn=OFN-KN.
Finally
(42)∑N-KN≤n≤N‍1nFn=F(N)N∑r=0K(N)‍FN-rF(N)·NN-r=F(N)N∑r=0KN‍FN-rFN·∑n=0∞‍rNn=F(N)N∑r=0K(N)‍FN-rFN+FN-rFNrNggggggggggggg+FN-rFNrN2+⋯∑r=0KN‍;
in fact
(43)FN-rFN≤1,∀0≤r≤KN;
then
(44)equation42≤FNN∑r=0K(N)‍FN-rF(N)+rN+rN2hhhhhhhhhhhhh+rN3+⋯FN-rF(N)+rN+rN2∑r=0K(N)‍=F(N)N∑r=0K(N)‍FN-rF(N)+∑r=0K(N)‍∑j=1∞‍rNj≤FNN∑r=0KN‍1+∑r=0KN‍∑j=1∞‍rNj;∑j=1∞r/Nj is a geometric series with r/N as a first term; then we have
(45)=F(N)N∑r=0K(N)‍1+O∑r=0K(N)‍rN=F(N)NKN+1+O∑r=0K(N)‍rN=FNKN+1N+OFN∑r=0KNrN2=FNKN+1N+OF(N)N3/2,
since K(N)=N1/4.
Therefore, it can be seen that from (40), (41), and (45)(46)πN-∑n≤N‍Fnn≤k1FN2,∑n≤N‍F(n)n-∑N-KN≤n≤N‍Fnn≤k2FN-KN,∑N-K(N)≤n≤N‍Fnn-FNKN+1N≤k3F(N)N3/2.
Thus
(47)πN-FNKN+1N≤k1FN2+k2FN-KN+k3F(N)N3/2⟹π(N)·NFNKN+1-1≤k1NFN/2FNKN+1+k2NFN-KNFNKN+1+k3NFNN3/2FNKN+1;
since KN=N1/4⇒KN≤N1/4, then
(48)πN·NFNN1/4+1-1≤k1(N)(F(N/2))FNN1/4+1+k2NFN-N1/4(F(N))(N1/4+1)+k3(N)(F(N))(N3/2)(F(N))(N1/4+1).
Using Lemma 3, we obtain
(49)NFN/2FNN1/4+1≤N3/4·c2M+1N/2c1·M+1N=N3/4·c2c1·M+1N/2⟶0asN⟶∞,NFN-N1/4FNN1/4+1≤N3/4·c2c1·M+1N1/4⟶0hhhhhhihhasN⟶∞.
Thus, letting N→∞ implies that
(50)k1NFN/2FNN1/4+1+k2NFN-N1/4FNN1/4+1+k3NFNN3/2FNN1/4+1⟶0.
So
(51)πN·NFNN1/4+1-1⟶0.
Therefore
(52)πN~FNN1/4+1N,
which is equivalent to
(53)π(N)~F(N)N3/4,
as required.Theorem 5 (Mertens’ orbit theorem).
LetT:DM→DM be the Dyck shift on a set of M pairs and Fn the number of points having period n under T that is given in Theorem 2. Then
(54)MTN=OFN1-e-hNeh-1-log⁡1-1eh+N-1,
where h=log⁡M+1.Proof.
The dynamical Mertens’ theorem asserts that(55)MTN=∑n≤N‍Onehn=∑n≤N‍1nehn∑d∣n‍μndF(d)=∑n≤N‍1nehn∑d∣n,d<n‍μndF(d)+∑n≤N‍F(n)nehn.
Firstly we want to estimate the term
(56)∑n≤N‍1nehn∑d∣n,d<n‍μndF(d).
Note that
(57)μn≤1,∑d∣n,d<n‍Fd≤nFn2∀n∈N.
Hence
(58)∑n=1N‍1nehn∑d∣n,d<n‍μndFd≤∑n=1N‍1nehn·nFn2=∑n=1N‍Fn/2ehn≤∑n=1N‍FN/2ehn=FN2·∑n=1N‍1ehn(isapartialsumofageometricseries)=FN2·e-h-e-hN+11-e-h≤F(N)·e-h-e-hN+11-e-h;
therefore
(59)∑n=1N‍1nehn∑d∣n,d<n‍μndF(d)=OF(N)·1-e-hNeh-1.
Now for
(60)∑n≤N‍Fnnehn,
in order to estimate this partial sum, the following lemma is extremely needed.
Lemma  6.Ifωis a complex number of modulus one and is not a root of unity, then(61)∑n≤N‍ωnn=-log⁡1-ω+ON-1.
Sinceh>0, then 1/eh≠1; therefore we can apply the above lemma. Hence
(62)∑n≤N‍Fnnehn≤∑n≤N‍FNnehn=F(N)-log⁡1-1eh+ON-1.
It follows that
(63)MTN=OFN1-e-hNeh-1-log⁡1-1eh+ON-1.
In fact, from the properties of asymptotic estimates, we have
(64)OOfx=Ofx.
Therefore, we conclude that
(65)MTN=OFN1-e-hNeh-1-log⁡1-1eh+N-1.



---

*Source: 304798-2014-11-12.xml*