Functorial Orbit Counting

Apisit Pakapongpun and Thomas Ward School of Mathematics University of East Anglia Norwich NR6 5LB, UK

                       t.ward@uea.ac.uk

Abstract

We study the functorial and growth properties of closed orbits for maps. By viewing an arbitrary sequence as the orbit-counting function for a map, iterates and Cartesian products of maps define new transformations between integer sequences. An orbit monoid is associated to any integer sequence, giving a dynamical interpretation of the Euler transform.

1 Introduction

Many combinatorial or dynamical questions involve counting the number of closed orbits or the periodic points under iteration of a map. Here we consider functorial properties of orbitcounting in the following sense. Associated to a map T : X → X with the property that T has only finitely many orbits of each length are combinatorial data (counts of fixed points and periodic orbits), analytic data (a zeta function and a Dirichlet series) and algebraic data (the orbit monoid). On the other hand, the collection of such maps is closed under disjoint unions, direct products, iteration, and other operations. Our starting point is to ask how the associated data behaves under those operations. A feature of this work is that these natural operations applied to maps with simple orbit structures give novel constructions of sequences with combinatorial or arithmetic interest. Routine calculations are suppressed here for brevity; complete details, related results, and further applications will appear in the thesis of the first author [16].

We define the following categories:

• maps 𝔐, comprising all pairs (X, T) where T is a map X → X with F_{T} (n) = |{x ∈ X | T^{n}(x) = x}| < ∞ for all n ⩾ 1;

• orbits 𝔒 = ℕ_{0}^{ℕ}, comprising all sequences (a_{n})_{n⩾1} with a_{n} ⩾ 0 for all n ⩾ 1; and • fixed points 𝔉 ⊆ 𝔒, comprising any sequence a = (a_{n}) with the property that there

is some (X, T) ∈ 𝔐 with a_{n} = F_{T} (n) for all n ⩾ 1.

For (X, T) ∈ 𝔐, a closed orbit of length n under T is any set of the form τ = {x, T x, …, T^{n}x = x} with cardinality |τ| = n, and we write O_{T} (n) for the number of closed orbits of length n. Clearly

F_{T} (n) = ∑_{d|n} d O_{T} (d),  (1)

so

O_{T} (n) = \frac{1}{n} ∑_{d|n} μ(n/d) F_{T} (d),  (2)

and this defines a bijection between 𝔉 and 𝔒 (see Everest, van der Poorten, Puri and the second author [7, 17] for more on the combinatorial applications of this bijection, and for non-trivial examples of sequences in 𝔉; see Baake and Neumärker [3] for more on spectral properties of the operators on 𝔒). Since the space X will not concern us, we will fix it to be some countable set and refer to an element of 𝔐 as a map T.

Recall from Knopfmacher [12] that an additive arithmetic semigroup is a free abelian monoid G equipped with a non-empty set of generators P, and a weight function

∂ : G → ℕ ∪ {0}

with ∂(a + b) = ∂(a) + ∂(b) for all a, b ∈ G, satisfying the finiteness property

P (n) = |{p ∈ P | ∂(p) = n}| < ∞

for all n ⩾ 1. Given T ∈ 𝔐, we define the orbit monoid G_{T} associated to T to be the free abelian monoid generated by the closed orbits of T, equipped with the weight function

∂(a_{1}τ_{1} + ⋯ + a_{r}τ_{r}) = a_{1}|τ_{1}| + ⋯ + a_{r}|τ_{r}|,

and write G_{T} (n) for the number of elements of weight n. Finally, define orbit monoids 𝔊 to be the category of all such monoids associated to maps in 𝔐. Notice that every additive arithmetic semigroup in the sense of Knopfmacher [12] is an orbit monoid, since for any sequence (a_{n}) there is a map T with O_{T} (n) = a_{n} for all n ⩾ 1 (indeed, Windsor [23] shows that the map T may be chosen to be a C^{∞} diffeomorphism of a torus). We will write G_{T} for the sequence (G_{T} (n)), since the sequence determines the monoid up to isomorphism.

As usual, we write ζ = (1, 1, 1, …) and μ = (1, −1, −1, 0, …) for the zeta and Möbius functions viewed as sequences, and use the same symbols to denote their Dirichlet series.

There are natural generating functions associated to an element T ∈ 𝔐. If F_{T} (n) is exponentially bounded then the dynamical zeta function

ζ_{T} (s) = exp ∑_{n⩾1} \frac{s^{n}}{n} F_{T} (n)

converges in some complex disk (see Artin and Mazur [1]). If O_{T} (n) is polynomially bounded then the orbit Dirichlet series

d_{T} (s) = ∑_{n⩾1} \frac{O_{T} (n)}{n^{s}},

converges in some half-plane. The basic relation (1) is expressed in terms of these generating functions by the two identities

ζ_{T} (s) = ∏_{n⩾1}(1 − s)^{− O_{T} (n)} = ∏_{τ} (1 − s^{|τ|})^{−1} ,

where the product is taken over all closed orbits of T, and

d_{T} (s)ζ(s + 1) = ∑_{n⩾1} \frac{F_{T} (n)}{n^{s+1}}.

Finally, a natural measure of the rate of growth in O_{T} is the number

π_{T} (N) = |{τ | |τ| ⩽ N}|

of closed orbits of length no more than N. Asymptotics for π_{T} are analogous to the prime number theorem. In the case of exponential growth, that is under the assumption that lim sup_{n→∞} \frac{1}{n} log O_{T} (n) = h > 0, a more smoothly averaged measure of orbit growth is given by

M_{T} (N) = ∑_{|τ|⩽N} \frac{1}{e^{h|τ|}} ,

and asymptotics for M_{T} are analogous to Mertens’ theorem.

2 Functorial properties

Most functorial properties are immediate, so we simply record them here. Write T_{1} × T_{2} for the Cartesian product of two maps, T_{1} ⊔ T_{2} for the disjoint union, defined by

(T_{1} ⊔ T_{2})(x) = \begin{cases}T_{1}(x), & if x ∈ X_{1}; \\ T_{2}(x), & if x ∈ X_{2}; \end{cases}

and write T^{k} with k ⩾ 1 for the kth iterate of T. Then

1. F_{T_{1}×T_{2}} = F_{T_{1}} F_{T_{2}} (pointwise product);

2. d_{T_{1}⊔T_{2}} = d_{T_{1}} + d_{T_{2}};

3. ζ_{T_{1}⊔T_{2}} = ζ_{T_{1}}ζ_{T_{2}};

4. F_{T^{k}}(n) = F_{T} (kn) for all k ⩾ 1 and n ⩾ 1.

In contrast to the first of these, it is clear that computing the number of closed orbits under the Cartesian product of two maps is more involved.

Lemma 1. O_{T_{1}×T_{2}}(n) = ∑_{{d_{1},d_{2}∈ℕ, \atop lcm(d_{1},d_{2})=n}} O_{T_{1}}(d_{1}) O_{T_{2}}(d_{2}) gcd(d_{1}, d_{2}).

Proof. If (x_{1}, x_{2}) lies on a T_{1} × T_{2}-orbit of length n, then, in particular,

T_{1}^{n}(x_{1}) = x_{1}

and

T_{2}^{n}(x_{2}) = x_{2},

so x_{i} lies on a T_{i}-orbit of length d_{i} for some d_{i} dividing n, for i = 1, 2. On the other hand, if x_{i} lies on a T_{i}-orbit of length d_{i} for i = 1, 2 then the T_{1} × T_{2}-orbit of (x_{1}, x_{2}) has cardinality lcm(d_{1}, d_{2}). On the other hand, if τ_{1}, τ_{2} are orbits of length d_{1}, d_{2} with lcm(d_{1}, d_{2}) = n, then there are d_{1}d_{2} points in the set τ_{1} × τ_{2}, so this must split up into d_{1}d_{2}/n = gcd(d_{1}, d_{2}) orbits of length n under T_{1} × T_{2}.

Example 2. Let T be a map with one orbit of each length, so d_{T} (s) = ζ(s). Then, by Lemma 1 and a calculation,

O_{T ×T} (n) = ∑_{{d_{1},d_{2}∈ℕ, \atop lcm(d_{1},d_{2})=n}} gcd(d_{1}, d_{2}) = ∑_{d|n} σ(d)μ(n/d)^{2},

so

d_{T ×T} (s) = \frac{ζ(s)^{2}ζ(s − 1)}{ζ(2s)} = 1 + \frac{4}{2^{s}} + \frac{5}{3^{s}} + \frac{10}{4^{s}} + \frac{7}{5^{s}} + \frac{20}{6^{s}} + \frac{9}{7^{s}} + \frac{22}{8^{s}} + · · · .  (3)

By identifying an orbit of length n under T with a cyclic group C_{n} of order n, we see from the proof of Lemma 1 that O_{T ×T} (n) is the number of cyclic subgroups of C_{n} × C_{n}, so O_{T ×T} is \underline{A060648}.

Example 2 is generalized in Example 16, where it corresponds to the case P = ∅.

Example 3. Let p be a prime, and assume that O_{T} (n) = p^{n} for all n ⩾ 1, so ζ_{T} (s) = \frac{1}{1−ps}. Then

O_{T ×T} (n) = \frac{1}{n} ∑_{d|n} (μ(n/d) ∑_{d_{1}|d} d_{1}p^{d_{1}} ∑_{d_{2}|d} d_{2}p^{d_{2}} ) = \frac{1}{n} ∑_{d|n} μ(d)p^{2n/d},

which is the number of irreducible polynomials of degree n + 1 over 𝔽_{p^{2}}. In the case p = 2 this gives the sequence \underline{A027377}, and in the case p = 3 this gives \underline{A027381}.

The behavior of orbits under iteration is more involved. To motivate the rather dense formula below, consider the orbits of length n under T^{p} for some prime p. Points on an m-orbit under T lie on an orbit of length m/ gcd(m, p) under T^{p}. If m ≠ n, np then m/ gcd(m, p) ≠ n, so the only points that can contribute to O_{T^{p}}(n) are points lying on n-orbits or on np-orbits under T. Each np-orbit under T splits into p orbits of length n under T^{p}. An n-orbit under T defines an n-orbit under T^{p} only if p ∤ n. It follows that

O_{T^{p}}(n) = \begin{cases}p O_{T} (pn) + O_{T} (n), & if p ∤ n; \\ p O_{T} (pn), & if p|n. \end{cases}  (4)

In order to state the general case, fix the power m and write m = p^{a} = p_{1}^{a_{1}} ⋯ p_{r}^{a_{r}} for the decomposition into primes of m ∈ ℕ; for any set J ⊆ I = {p_{1}, …, p_{r}} write p_{J}^{a_{J}} = ∏_{p_{j}∈J} p_{j}^{a_{j}}. Finally, write D(n) for the set of prime divisors of n.

Theorem 4. Let m = p^{a} and J = J(n) = D(m) \ D(n). Then

O_{T^{m}}(n) = ∑_{d|p_{J}^{a_{J}}} \frac{m}{d} O_{T} (\frac{mn}{d}).  (5)

Proof. Notice that J depends on n, so the formula (5) involves a splitting into cases depending on the primes dividing n, just as in the case of a single prime discussed above. We argue by induction on the length ∑_{i=1}^{r} a_{i} of m. If the length of m is 1, then m is a prime and (5) reduces to (4). Assume now that (5) holds for ∑_{i=1}^{r} a_{i} ⩽ k, and let m have length k; write I = D(m) and J = D(m) \ D(n). We consider the effect of multiplying m by a prime q on the formula (5), and write I′ = D(mq), J′ = D(mq) \ D(n).

If q ∈ D(n) \ I then by (4) we have

O_{T^{mq}}(n) = q O_{T^{m}}(qn) = q ∑_{d|p_{J}^{a_{J}}} \frac{m}{d} O_{T} (\frac{mnq}{d}) = q ∑_{d|p_{J′}^{a_{J′}}} \frac{m}{d} O_{T} (\frac{mnq}{d}),

in accordance with (5).

If q ∈ I ∩ D(n), then I′ = I and J′ = J, so

O_{T^{mq}}(n) = q O_{T^{m}}(qn) = q ∑_{d|p_{J′}^{a_{J′}}} \frac{m}{d} O_{T} (\frac{mnq}{d})

as required.

If q ∉ I ∪ D(n) then

O_{T^{mq}}(n) = q O_{T^{m}}(qn) + O_{T^{m}}(n)
= q ∑_{d|p_{J}^{a_{J}}} \frac{m}{d} O_{T} (\frac{mqn}{d}) + ∑_{d|p_{J}^{a_{J}}} \frac{m}{d} O_{T} (\frac{mn}{d})

= ∑_{d|p_{J}^{a_{J}} q} \frac{qm}{d} O_{T} (\frac{mqn}{d})

as required.

Finally, if q ∈ I \ D(n) then

O_{T^{mq}}(n) = q O_{T^{m}}(qn) + O_{T^{m}}(n)
= q ∑_{d|p_{J\\{q\}}^{a_{J\\{q\}}}} \frac{m}{d} O_{T} (\frac{mqn}{d}) + ∑_{d|p_{J}^{a_{J}}} \frac{m}{d} O_{T} (\frac{mn}{d})

= ∑_{{d|p\begin{matrix}a & _{J} \\ J \end{matrix} q, \atop q∤d}} \frac{mq}{d} O_{T} \frac{mqn}{d} + ∑_{{d|p\begin{matrix}a & _{J} \\ J \end{matrix} q, \atop q|d}} \frac{m}{d/q} O_{T} (\frac{mn/d}{d/q})

= ∑_{d|p_{J}^{a_{J}} q} \frac{qm}{d} O_{T} (\frac{mqn}{d}),

completing the proof.

This defines a family of transformations on sequences, taking O_{T} to O_{T^{k}} for each k ⩾ 1.

Example 5. Let T ∈ 𝔐 have O_{T} (n) = n for all n ⩾ 1, so d_{T} (s) = ζ(s − 1). Then by (2) we have

O_{T^{2}}(n) = \frac{1}{n} ∑_{d|n} μ (\frac{n}{d}) F_{T^{2}}(d) = \frac{1}{n} ∑_{d|n} μ (\frac{n}{d}) σ_{2}(2d)

since F_{T^{2}}(d) = F_{T} (2d) = ∑_{e|2d} e O_{T} (e) = ∑_{e|2d} e^{2}, so

d_{T^{2}}(s) = (5 − \frac{2}{2^{s}} ) ζ(s − 1) = 5 + \frac{8}{2^{s}} + \frac{15}{3^{s}} + \frac{16}{4^{s}} + \frac{25}{5^{s}} + \frac{24}{6^{s}} + \frac{35}{7^{s}} + \frac{32}{8^{s}} + · · · .

Thus O_{T^{2}} is \underline{A091574} (up to an offset).

Example 6. More generally, if d_{T} (s) = ζ(s − 1) and p is a prime, then

O_{T^{p}}(n) = \frac{1}{n} ∑_{d|n} μ (\frac{n}{d}) σ_{2}(pd) = \begin{cases}(p^{2} + 1)n, & if p ∤ n; \\ p^{2}n & if p|n; \end{cases}

so d_{T^{p}}(s) = (p^{2} + 1 − \frac{p}{p^{s}} ) ζ(s − 1). Composite powers are more involved; full details are

in [16]. For example,

O_{T^{4}}(n) = \begin{cases}16n, & if n is even; \\ 21n & if n is odd; \end{cases}

so d_{T^{4}}(s) = (2 − \frac{10}{2^{s}}) ζ(s − 1).

An important family of dynamical systems – those of finite combinatorial rank – have been studied by Everest, Miles, Stevens and Ward [6]. These have the property that their orbit Dirichlet series is “Dirichlet–rational”, that is there is a finite set C ⊆ ℤ with the property that d_{T} (s) is a rational function in the variables {c^{−s} | c ∈ C}. An easy consequence of Theorem 4 is that this property is preserved under iteration.

Corollary 7. If maps S and T have Dirichlet–rational orbit Dirichlet series, then so do S×T and T^{k} for any k ⩾ 1.

Example 8. The quadratic map T : x ↦ 1−cx^{2} on the interval [−1, 1] at the Feigenbaum value c = 1.401155 ⋯ (see Feigenbaum’s lecture notes [8]; this is at the end of a perioddoubling cascade) gives a particularly simple example of a Dirichlet–rational Dirichlet series. This map has

O_{T} (n) = \begin{cases}1, & if n = 2^{k} for some k ⩾ 0; \\ 0 & if not; \end{cases}

so d_{T} (s) = \frac{1}{1−2^{−s}} and O_{T} is (up to an offset) the Fredholm-Rueppel sequence \underline{A036987}. By (1) we have F_{T} (n) = 2⌊n⌋_{2} − 1, where ⌊n⌋_{2} = |n|_{2}^{−1} denotes the 2-part of n, so F_{T} is \underline{A038712}. Using this we see that

O_{T^{2}}(n) = \frac{1}{n} ∑_{d|n} μ (\frac{n}{d}) (2⌊2d⌋_{2} − 1) = \begin{cases}3, & if n = 1; \\ 2, & if n = 2^{k} for some k ⩾ 1; \\ 0, & if not; \end{cases}

so

d_{T^{2}}(s) = \frac{3 − 2^{−s}}{1 − 2^{−s}} .

More generally, the formula for F_{T} shows that

d_{T^{k}}(s) = ⌊k⌋_{2} − 1 + ⌊k⌋_{2}d_{T} (s)

for any k ⩾ 1.

Example 9. With T as in Example 8, a similar calculation using Lemma 1 shows that

d_{T ×T} (s) = \frac{3}{1 − 2^{−(s−1)}} − \frac{2}{1 − 2^{−s}} .

If S ∈ 𝔐 has

O_{S}(n) = \begin{cases}1, & if n = 3^{k} for some k ⩾ 0; \\ 0, & if not; \end{cases}

then O_{T ×S} is \underline{A065333}, the characteristic function of the 3-smooth numbers, so

d_{T ×S}(s) = \frac{1}{(1 − 2^{−s})(1 − 3^{−s})},

d_{T ×T ×S}(s) = \frac{3}{(1 − 2^{−(s−1)})(1 − 3^{−s})} − \frac{2}{(1 − 2^{−s})(1 − 3^{−s})},

and so on.

The thesis of the first author [16] characterizes the existence of “roots”: that is, given a sequence a ∈ 𝔒 and k ⩾ 1 to determine if there is some T ∈ 𝔐 with O_{T^{k}} = a. Instances of no roots, unique roots, and uncountably many roots occur.

3 Multiplicative sequences

Multiplicative sequences in 𝔒 are particularly easy to work with, and in this section we describe simple examples of such sequences, and some properties of their product systems. In particular, we show how simple orbit sequences may factorize (that is, be the orbit sequence of the product of two maps) in many different ways. Since F_{T} and O_{T} are related by convolution with μ and multiplication by n, it is clear that F_{T} is multiplicative if and only if O_{T} is multiplicative. The next lemma is equally straightforward; we include the proof to illustrate how the correspondence between F_{T} and O_{T} may be exploited.

Lemma 10. If any two of O_{T}, O_{S} and O_{T ×S} are multiplicative, then so is the third.

Proof. Assume the first two are multiplicative and gcd(m, n) = 1. Then

O_{T ×S}(mn) = \frac{1}{mn} ∑_{d|mn} μ(\frac{mn}{d}) F_{T ×S}(d) = \frac{1}{mn} ∑_{d|m} ∑_{d′|n} μ(\frac{m}{d})μ(\frac{n}{d′}) F_{T} (dd′) F_{S}(dd′)
= \frac{1}{mn} ∑_{d|m} ∑_{d′|n} μ(\frac{m}{d})μ(\frac{n}{d′}) F_{T} (d) F_{T} (d′) F_{S}(d) F_{S′}(d′)
= \frac{1}{mn} ∑_{d|m} ∑_{d′|n} μ(\frac{m}{d})μ(\frac{n}{d′}) F_{T ×S}(d) F_{T ×S}(d′) = O_{T ×S}(m) O_{T ×S}(n).

Now assume that O_{S} is not multiplicative while O_{T} is, and choose m, n of minimal product with the property that gcd(m, n) = 1 and O_{S}(mn) ≠ O_{S}(m) O_{S}(n). Then, by construction, if ab < mn and gcd(a, b) = 1 we have O_{S}(ab) = O_{S}(a) O_{S}(b), so we must have F_{S}(mn) ≠ F_{S}(m) F_{S}(n). If mn = 1 then

O_{T ×S}(1) = F_{T ×S}(1) = F_{T} (1) F_{S}(1) = O_{T} (1) O_{S}(1) = O_{S}(1) ≠ 1,

so O_{T ×S} is not multiplicative. If mn > 1 then a calculation gives

O_{T ×S}(mn) = \frac{1}{mn} ∑_{{d|m,d′|n, \atop dd′<mn}} μ(\frac{mn}{dd′}) F_{T ×S}(dd′) + \frac{1}{mn} F_{T ×S}(mn)

= \frac{1}{m} ∑_{d|m} μ(\frac{m}{d}) F_{T ×S}(d) · \frac{1}{n} ∑_{d′|n} μ(\frac{n}{d′}) F_{T ×S}(d′)
−\frac{1}{mn} F_{T ×S}(m) F_{T ×S}(n) + \frac{1}{mn} F_{T ×S}(mn)
= O_{T ×S}(m) O_{T ×S}(n) − \frac{1}{mn} F_{T} (mn) \underbrace{F_{S}(m) F_{S}(n)}_{≠F_{S}(mn)}
≠ O_{T ×S}(m) O_{T ×S}(n)

since F_{T} (mn) ⩾ F_{T} (1) = 1, so O_{T ×S} is not multiplicative.

This gives a bijective proof of (3) as follows. Write ℓ(n) for the number of primitive lattices of index n in ℤ^{2}, so that (3) is equivalent to the statement

O_{T ×T} (n) = ∑_{d|n} ℓ(d).

Both sides of this equation are multiplicative, so it is enough to prove this for n = p^{r} a prime power. The primitive lattices of index p^{j} in ℤ^{2} are in one-to-one correspondence with

\{[\begin{matrix}a & b \\ 0 & c \end{matrix}] | ac = p^{j}, a, c ⩾ 1, 0 ⩽ b < p^{j}, gcd(a, b, c) = 1\} .

It follows that ∑_{d|p^{r}} ℓ(d) = p^{r} + 2 ∑_{j=0}^{r−1} p^{j}, in agreement with the formula for O_{T ×T} (p^{r}). Write ℙ for the set of all prime numbers, and for a subset P ⊆ ℙ write P^{c} = ℙ \ P.

Example 11. For any set P of primes, define s_{P} ∈ 𝔒 by

s_{P} (n) = \begin{cases}0, & if p|n for some p ∈ P; \\ 1, & if not. \end{cases}

Lemma 12. If T is a map with O_{T} = s_{P} and k ⩾ 1, then

O_{n}(T^{k}) = \{ \begin{matrix}∏_{p∈Q,p|n} p^{a_{p}} · ∏_{p∈Q,p∤n}σ(p^{a_{p}}) & if p ∤ n for all p ∈ P; \\ 0 & if p|n for some p ∈ P, \end{matrix}

where k = ∏_{p∈P} p^{a_{p}} · ∏_{p∈Q} p^{a_{p}} with P ∩ Q = ∅ is the prime decomposition of k.

Proof. Let J ⊆ P ∪ Q and I ⊆ Q. Then

O_{T^{k}}(n) = ∑_{d|p_{J}^{^{a}J}} (k/d) O_{T} (kn/d)
(where p ∤ n for p ∈ J, p|n for p ∈ (P ∪ Q) \ J)
= ∑ ; d| ∏_{p∤n} p^{ap} ∏_{p∈Q}(p^{a_{p}}/d) O_{T} (p^{a_{p}}n/d),

showing the second case. If p ∤ n for p ∈ I, p|n for p ∈ Q \ I and p ∤ n for any p ∈ P then O_{T} (p^{a_{p}}n/d) = 1, so

O_{T^{k}}(n) = ∑ ; d| ∏_{p∤n} p^{ap} ∏_{p∈Q}(p^{a_{p}}/d)

= (∏_{p∈Q} p^{a_{p}}) ∑ ; d| ∏_{p∤n} p^{ap} 1/d

= ∏_{p∈Q} p^{a_{p}} ( ∑ ; d| ∏_{p∤n} p^{ap} d/∏_{p∤n}p^{a_{p}} )

= ∑ ; d| ∏_{p∤n} p^{ap} (d/∏_{p∤n}p^{a_{p}}) ∏_{p∤n}p^{a_{p}} ∏_{p|n} p^{a_{p}}

= ∏_{p|n} p^{a_{p}} (∏_{p∤n} ∑_{d|p^{ap}} d)
= ∏_{\begin{matrix}p∈Q \\ p|n \end{matrix}} p^{a_{p}} · ∏_{\begin{matrix}p∈Q \\ p∤n \end{matrix}}σ(p^{a_{p}}),

showing the first case.

It is clear from Lemma 1 that if O_{S} = s_{P} and O_{T} = s_{P^{c}} then O_{T ×S} = ζ, so the sequence ζ factorizes in uncountably many ways into the orbit count of two combinatorially distinct systems. Indeed, these sequences provide the only combinatorial factorization of ζ into the orbit count of the product of two systems.

Proposition 13. If S and T are maps with O_{S×T} = ζ, then there is a set P ⊆ ℙ for which O_{T} = s_{p} and O_{S} = s_{P^{c}}.

Proof. It is clear from Lemma 1 that O_{S} and O_{T} take values in {0, 1}, and moreover that {O_{S}(p), O_{T} (p)} = {0, 1} for p ∈ ℙ. Fix a pair of maps satisfying the hypothesis, and let P = {p ∈ ℙ | O_{T} (p) = 0}, so that P^{c} = {p ∈ ℙ | O_{S}(p) = 0}.

Assume that p|n for some p ∈ P, so that O_{T} (p) = 0 and O_{S}(p) = 1. If O_{T} (n) = 1, then

1 = ∑_{lcm(d,d′)=n} gcd(d, d′) O_{T} (d) O_{S}(d′) ⩾ p,

which is impossible, so O_{T} (n) = 0. By symmetry, if p|n for some p ∈ P^{c}, then O_{S}(n) = 0. Now if n ≠ 1 is not divisible by any p ∈ P, then

1 = ∑_{lcm(d,d′)=n} gcd(d, d′) O_{T} (d) O_{S}(d′)
= ∑_{{lcm(d,d′)=n, \atop D(d)⊆P^{c},D(d′)⊆P}} gcd(d, d′) O_{T} (d) O_{S}(d′)

= O_{T} (n) ∑_{d′|n} d′ O_{S}(d′),

so O_{T} (n) = 1. It follows that O_{T} = s_{P}, and by symmetry O_{S} = s_{P^{c}} as required.

Products of the systems in Example 11 enjoy remarkable combinatorial properties, illustrated in the examples below. The calculations in the examples all follow from the next lemma. Let S ⊆ ℙ be a set of primes. Write ⌊n⌋_{S} for the S-part of n, that is

⌊n⌋_{S} = ∏_{p∈S} |n|_{p}^{−1}.

Write gcd(n, S) as shorthand for gcd(n, ∏_{p∈S} p).

Lemma 14. For any set S ⊆ ℙ,

∑_{n⩾1} \frac{⌊n⌋_{S}}{n^{s}} = ζ(s) ∏_{p∈S} (\frac{p^{s} − 1}{p^{s} − p}) .  (6)

Proof. Recall that

∑_{n⩾1,gcd(n,S)=1} \frac{1}{n^{s}} = ∏_{p∈S} (1 − p^{−s}) ζ(s).  (7)

Write S = {p_{1}, … }. Then, writing n = p_{1}^{a_{1}} ⋯ p_{r}^{a_{r}}m with gcd(m, S) = 1,

∑_{n⩾1} \frac{⌊n⌋_{S}}{n^{s}} = ∑_{gcd(m,S)=1} ∑_{a_{1}⩾0}⋯ ∑_{a_{r}⩾0} \frac{p_{1}^{a_{1}} ⋯ p_{r}^{a_{r}}}{(p_{1}^{a_{1}} ⋯ p_{r}^{a_{r}})^{s}m^{s}}

= ∑_{gcd(m,S)=1} \frac{1}{m^{s}} ∑_{a_{2}⩾0}⋯ ∑_{a_{r}⩾0} \frac{p_{2}^{a_{2}} ⋯ p_{r}^{a_{r}}}{(p_{2}^{a_{2}} ⋯ p_{r}^{a_{r}})^{s}} ∑_{a_{1}⩾0} \frac{1}{(p_{1}^{a_{1}})^{s−1}}

= ∑_{gcd(m,S)=1} \frac{1}{m^{s}} ∑_{a_{2}⩾0}⋯ ∑_{a_{r}⩾0} \frac{p_{2}^{a_{2}} ⋯ p_{r}^{a_{r}}}{(p_{2}^{a_{2}} ⋯ p_{r}^{a_{r}})^{s}} (\frac{1}{1 − p_{1}^{−(s−1)}} ) ,

so by induction we have

∑_{n⩾1} \frac{⌊n⌋_{S}}{n^{s}} = ∑_{gcd(m,S)=1} \frac{1}{m^{s}} ∏_{p∈S} (\frac{1}{1 − p^{−(s−1)}} )

= ζ(s) ∏_{p∈S} (1 − p^{−s}) \frac{1}{1 − p^{−(s−1)}}

since I can write ∑_{gcd(m,S)=1} as (1 − p_{1}^{−s}) ∑_{gcd(m,S\{p_{1}})=1} as in (7), as required.

Notice that (6) interpolates between ζ(s) (when S = ∅) and ζ(s − 1) (when S = ℙ). Of course how the abscissa of convergence moves from 1 at S = ∅ to 2 at S = ℙ is rather subtle. A similar argument gives the following.

Lemma 15. Let S be a set of primes. Then

a_{S,n} = ∏_{p∈S} (\frac{1}{p − 1}) (\frac{p + 1}{|n|_{p}} − 2)

for all n ⩾ 1 if and only if

∑_{n⩾1} \frac{a_{S,n}}{n^{s}} = ζ(s) ∏_{p∈S} \frac{p^{s} + 1}{p^{s} − p}.

Proof. First, if q ∉ S and gcd(m, q) = 1, then

a_{S,mq^{k}} = a_{S,m}  (8)

for all k ⩾ 0, since |q|_{p} = 1 for all p ∈ S. Second, we have an extension of the identity (7): if q ∉ S, then

∑_{m⩾1,gcd(m,q)=1} \frac{a_{S,m}}{m^{s}} = (1 − q^{−s}) ∑_{n⩾1} \frac{a_{S,n}}{n^{s}}  (9)

by the usual argument and (8). We now prove the lemma by induction on the cardinality of S. Assume we have the lemma for some set S, and assume that q ∉ S. Write S′ = S ∪{q}, and notice that

∑_{n⩾1} \frac{a_{S′,n}}{n^{s}} = ∑_{n⩾1} \frac{\frac{1}{q−1} (\frac{q+1}{|n|_{q}} − 2) a_{S,n}}{n^{s}}

= (\frac{q + 1}{q − 1}) ∑_{n⩾1} \frac{a_{S,n}/|n|_{q}}{n^{s}} − \frac{2}{q − 1} ∑_{n⩾1} \frac{a_{S,n}}{n^{s}}

= (\frac{q + 1}{q − 1}) ∑_{m⩾1,gcd(m,q)=1} ∑_{k⩾0} \frac{q^{k}a_{S,mq^{k}}}{(q^{k})^{s}m^{s}} − \frac{2}{q − 1} ∑_{n⩾1} \frac{a_{S,n}}{n^{s}}

= (\frac{q + 1}{q − 1}) ∑_{m⩾1,gcd(m,q)=1} \frac{a_{S,m}}{m^{s}} ∑_{k⩾0} \frac{1}{(q^{k})^{s−1}} − \frac{2}{q − 1} ∑_{n⩾1} \frac{a_{S,n}}{n^{s}}

by (8)

= \frac{q + 1}{q − 1} (1 − q^{−s}) \frac{1}{1 − q^{1−s}} ∑_{n⩾1} \frac{a_{S,n}}{n^{s}} − \frac{2}{q − 1} ∑_{n⩾1} \frac{a_{S,n}}{n^{s}}

by (9).

So if we write ϕ(s) = ∑_{n⩾1} \frac{a_{S,n}}{n^{s}}, then

∑_{n⩾1} \frac{a_{S′,n}}{n^{s}} = ϕ(s) ((\frac{q + 1}{q − 1}) (1 − q^{−s}) (\frac{1}{1 − q^{1−s}} ) − \frac{2}{q − 1})

= ϕ(s) (\frac{q^{s} + 1}{q^{s} − q}) ,

showing the lemma for the set S′. All that remains is to check the case of a singleton S = {p}, which is easy.

Example 16. If O_{S} = s_{P} and O_{T} = ζ then, by Lemmas 1 and 15,

d_{S×T} (s) = ∏_{p∈P} (\frac{1−p^{1−s}}{1+p^{−s}} ) \frac{ζ^{2}(s)ζ(s−1)}{ζ(2s)} = ζ(s) ∏_{p∉P} \frac{1+p^{−s}}{1−p^{1−s}} .

Example 17. Taking P = {2}, O_{S} = s_{P}, O_{T} = ζ again, we have

d_{S×T} (s) = (\frac{1−2^{1−s}}{1+2^{−s}} ) \frac{ζ^{2}(s)ζ(s−1)}{ζ(2s)}.

The sequence O_{S×T} = (1, 1, 5, 1, 7, 5, 9, 1, 17, …) is \underline{A035109}, which arises in work of Baake and Moody [2, Eq. (5.10)], where it is shown to count the elements of ℤ^{3} with m distinct colours so that one colour occupies a similarity sublattice of index m while the other colours code the cosets.

Example 18. Let d_{S}(s) = ζ(s − a) and d_{T} (s) = ζ(s − b). Then a calculation shows that

O_{S×T} (n) = \frac{1}{n} ∑_{d|n} μ(n/d)σ_{a+1}(d)σ_{b+1}(d)

(the details are in [16]), so Ramanujan’s formula gives

d_{S×T} (s) = \frac{ζ(s − a)ζ(s − b)ζ(s − a − b − 1)}{ζ(2s − a − b)}.

These examples give an indication of how analytic properties of d_{S} and d_{T} relate to those of d_{T^{k}} and d_{S×T}, and this is pursued in [16].

4 Counting in orbit monoids

Counting in G_{T} involves counting additive partitions, with two changes: some parts may be missing (that is, a “restricted” additive partition) and some parts may come in several versions. Thus the sequence G_{T} is the Euler transform of the sequence O_{T} (see Sloane and Plouffe [18, pp. 20–22]).

Lemma 19. For any map T ∈ 𝔐,

1 + ∑_{n=1}^{∞} G_{T} (n)s^{n} = ∏_{i=1}^{∞} (1 − s^{i})^{− O_{T} (i)} = ζ_{T} (s)  (10)

and

n G_{T} (n) − F_{T} (n) − ∑_{k=1}^{n−1} F_{T} (k) G_{T} (n − k) = 0  (11)

for all n ⩾ 1.

Proof. The first equality in (10) is clear, since the coefficient of s^{n} in the right-hand side counts partitions of n into parts i with multiplicity O_{T} (i); the second equality is the usual Euler product expansion of the dynamical zeta function. The recurrence relation (11) may be seen by expanding the zeta function as

1 + ∑_{n=1}^{∞} G_{T} (n)s^{n} = ∑_{k=0}^{∞} \frac{1}{k!} (∑_{n=1}^{∞} F_{T} (n)\frac{s^{n}}{n} )^{k}

and verifying that (11) satisfies this relation.

Thus the categories 𝔉, 𝔒 and 𝔊 are related as follows,

[figure: 𝔉; generating function; Möbius convolution; 𝔊; Euler; 𝔒]

and we indicate in this section how various growth properties of any one sequence relate to growth properties of the others, mostly by pointing out how these quantities arise in abstract analytic number theory. These results extend those of Puri and Ward [17] concerning relations between growth in F_{T} and in O_{T}, and some related asymptotic results are discussed in the paper of Baake and Neumärker [3]. Before listing these, we discuss some of the statements. It is often possible to estimate F_{T} (n) (or even to have a closed formula for F_{T} (n)), and a reasonable combinatorial replacement for “hyperbolicity” is the assumption (12) of a uniform exponential growth rate in F_{T}, where h plays the role of topological entropy. A similar assumption often used in abstract analytic number theory is (16) (hypotheses of this shape are often called “Axiom A” or “Axiom A^{♯}” in number theory). The assumption (16) is weaker than (12): it is pointed out in [10] that there are arithmetic semigroups with G_{T} (n)e^{−hn} − C_{3} converging to zero exponentially fast for which n F_{T} (n)e^{−hn} does not converge. The hypothesis is weakened further in (17), which is a permissive form of exponential growth rate assumption. The hypothesis (12) fails for many non-hyperbolic systems. If T is a quasihyperbolic toral automorphism or a non-expansive S-integer map with S finite (see [4] or Example 27) then (12) fails since the ratio F_{T} (n + 1)/ F_{T} (n) does not converge as n → ∞. In both cases the conclusions of Theorem 20[1] also fail (see Noorani [15] and Waddington [20] for the case of a quasihyperbolic toral automorphism and [6] for the case of S-integer systems with S finite). As pointed out by Lindqvist and Peetre [14], Meissel considered the sum ∑_{p} \frac{1}{p(log p)^{a}} in 1866, and the dynamical analogue of Meissel’s theorem is given in Theorem 20[4] below. In Theorem 20, [1] is proved here and [2]–[4] are simply interpretations for orbit–counting of well-known results in number theory.

Theorem 20. Let T be a map in 𝔐.

[1] Assume that there are constants C_{1} > 0, h > 0 and h′ < h with

F_{T} (n) = C_{1}e^{hn} + O(e^{h′n}).  (12)

Then

O_{T} (n) = \frac{C_{1}}{n} e^{hn} + O (e^{h′n}/n) ,  (13)

π_{T} (N) = \frac{e^{h(N+1)}}{e^{h} − 1} + O (e^{hN}/N^{3/2}) ,  (14)

and

M_{T} (N) = ∑_{n=1}^{N} \frac{O_{T} (n)}{e^{hn}} = C_{1} ∑_{n=1}^{N} \frac{1}{n} + C_{2} + O (e^{h′′N})  (15)

where h′′ = max{h′ − h, −h/2}, for some constant C_{2}.

[2] Assume that there are constants C_{3} > 0, h > 0 and h′ < h with

G_{T} (n) = C_{3}e^{hn} + O(e^{h′n}).  (16)

Then, for any α > 1,

π_{T} (N) = C_{4} \frac{e^{hN}}{N} + O (e^{hN}/N^{α})

and (equivalently)

F_{T} (N) = e^{hN} + O (e^{hN}/N^{α−1}) .

[3] Assume that there are constants C_{5} > 0, h > 0 with

G_{T} (n) = (C_{5} + r(n)) e^{hn},  (17)

where ∑_{n=0}^{∞} sup_{k⩾n}|r(k)| < ∞. Then

∑_{n=1}^{N} \frac{n O_{T} (n)}{e^{hn}} = N + O(1);  (18)

∑_{n=1}^{N} \frac{O_{T} (n)}{e^{hn}} = log N + C_{6} + O(1/N);  (19)

∏_{n=1}^{N} (1 − e^{−hn})^{O_{T} (n)} = \frac{C_{7}}{N} + O(1/N^{2});

and if in addition ζ_{T} (−e^{h}) ≠ 0 then, for any λ > 1,

O_{T} (n) = \frac{e^{hn}}{n} + O (e^{hn}/n^{λ})  (20)

as n → ∞.

[4] Assume that there are constants C_{8} > 0, h > 0 with

\frac{G_{T} (n)}{e^{hn}} = C_{8} + O (1/ log(n)^{2+ε}) as n → ∞.  (21)

Then

∑_{k=1}^{∞} \frac{O_{T} (k)}{e^{hk}k^{a}} = \frac{1}{a} + C_{9} + O(a)

as a → 0.

Proof. [1] The estimate (13) is easy to see; it is implicit in [17] and [21] for example. By (1), we have

F_{T} (n) ⩾ n O_{T} (n) ⩾ F_{T} (n) − ∑_{d|n,d<n} F_{T} (d),

so

C_{1}e^{hn} + O(e^{h′n}) ⩾ n O_{T} (n) ⩾ C_{1}e^{hn} − n (C_{1}e^{hn/2} + O(e^{h′n/2}))

which gives (13). The proofs of (14) – a dynamical prime number theorem – and (15) – a dynamical Mertens’ theorem – use similar arguments to those in [5] where a more delicate non-hyperbolic problem is studied. Turning to (14), notice that (13) implies that

|π_{T} (N) − ∑_{n=1}^{N} \frac{C_{1}}{n} e^{hn}| = |∑_{n=1}^{N} O (e^{h′n}/n)| = O (e^{h′N}) .

Now

|∑_{n=1}^{N} \frac{C_{1}}{n} e^{hn} − ∑_{n=N−k(N)}^{N} \frac{C_{1}}{n} e^{hn}| ⩽ ∑_{n=1}^{N−k(N)−1} C_{1}e^{hn} = O (e^{h(N−k(N))})

where k(N) = ⌊N^{1/4}⌋. Thus

∑_{n=N−k(N)}^{N} \frac{C_{1}}{n} e^{hn} = \frac{C_{1}e^{hN}}{N} ∑_{r=0}^{k(N)} e^{−hr} (1 − \frac{r}{N} )^{−1}

= \frac{C_{1}e^{hN}}{N} [\frac{e^{h}}{e^{h} − 1} − O (e^{−hk(N)}) + O (∑_{r=0}^{k(N)} \frac{r}{N} )]

= \frac{C_{1}e^{h(N+1)}}{e^{h} − 1} + O (\frac{e^{hN}}{N^{2}} ∑_{r=0}^{k(N)} r)

= \frac{C_{1}e^{h(N+1)}}{e^{h} − 1} + O (e^{hN}/N^{3/2}) .

Finally, notice that

\frac{F_{T} (n)}{ne^{hn}} − \frac{C_{1}}{n} = \frac{1}{n} O (e^{(h−h′)n}) ,  (22)

so

∑_{n=1}^{N} \frac{O_{T} (n)}{e^{hn}} − C_{1} ∑_{n=1}^{N} \frac{1}{n} = ∑_{n=1}^{N} \frac{1}{n} (\frac{F_{T} (n)}{e^{hn}} − C_{1}) + ∑ \frac{1}{n} ∑_{d|n,d<n} μ(n/d)\frac{F_{T} (d)}{e^{hn}}.  (23)

The bound (22) shows that the two terms on the right-hand side of (23) converge, giving (15) without error term. To see the error term, notice that

| ∑_{n=N+1}^{∞} \frac{1}{n} (\frac{F_{T} (n)}{e^{hn}} − C_{1})| ⩽ ∑_{n=N+1}^{∞} \frac{1}{n} O (e^{(h′−h)n}) = O (e^{(h′−h)n})

and

| ∑_{n=N+1}^{∞} \frac{1}{n} ∑_{d|n,d<n} μ(n/d)\frac{F_{T} (d)}{e^{hn}} | ⩽ ∑_{n=N+1}^{∞} (\frac{e^{hn/2}}{e^{hn}} + O (e^{−hn/2})) = O (e^{−hN/2}) .

[2] These are standard results from Knopfmacher [12, Ch. 8].

[3] The results (18)–(20) are shown in [12] to be consequences of Knopfmacher’s Axiom A^{#} in (17); (20) is due to Indlekofer [9].

[4] This is shown by Wehmeier [22].

Standard estimates for the harmonic series allow (15) to be simplified; for example under the hypothesis of Theorem 20[1] we have

M_{T} (N) = C_{1} log N + O(1/N).

Notice that the statements (15) and (19) are versions of what is usually called a dynamical Mertens’ theorem, though they may equally be seen in more elementary terms as consequences of \frac{O_{T} (n)}{e^{hn}} being close to \frac{1}{n} and the Euler–Maclaurin summation formula. Theorem 20[1] has the following kind of consequence: If T is a hyperbolic toral automorphism or mixing shift of finite type with entropy h, then

∑_{|τ|⩽n} \frac{1}{e^{h|τ|}} = log n + C_{10} + O(1/n)

and

∏_{τ} (1 − e^{−h|τ|})^{−1} = \frac{C_{11}}{n} + O(1/n^{2})

where τ runs over the closed orbits of T. A stronger hypothesis than (21),

ζ_{T} (z) ∼ \frac{C_{12}}{1 − e^{h}z}  (24)

as z → e^{−h} with 0 < z < e^{−h}, is considered in [11], where it is shown to give

∑_{n=1}^{N} \frac{O_{T} (n)}{e^{hn}} = ∑_{n=1}^{N} \frac{1}{n} + C_{13} + o(1);

hence

∏_{n=1}^{N} (1 − e^{hn})^{− O_{T} (n)} = C_{12}e^{γ}N + o(N)

and

∑_{n=1}^{N} \frac{F_{T} (n)}{e^{hn}} = N + o(N).  (25)

As pointed out in [11], the hypothesis (24) does not permit any smaller error in (25) for the following reason. For any sequence (w_{n}) of non-negative integers with ∑_{n=1}^{∞} \frac{w_{n}}{n} < ∞, choose (a_{n})with 0 ⩽ a_{n} < n and a_{n} ≡ 2^{n} + w_{n}2^{n} (mod n) and consider a map T with

O_{T} (n) = 1 + (2^{n} + w_{n}2^{n} − a_{n})/n.

This gives property (24), and a calculation shows that the error term in (25) is as big as O (∑_{n=1}^{N} w_{n}).

For a map T ∈ 𝔐 with infinitely many orbits, it is clear that G_{T} is isomorphic to ∑_{ℕ} ℕ_{0} as a semigroup. The information about how many orbits T has of each length is contained in the weight function ∂, and in each example we compute the size of the level set G_{T} (n) for each n ⩾ 1. If the sequence F_{T} is a linear recurrence sequence, then the relation (11) shows that G_{T} is also a linear recurrence sequence. Example 24 shows that G_{T} may satisfy a relation of smaller degree, while Example 23 shows that G_{T} may be of higher degree.

Example 21. Let T : X → X be the golden mean shift, so that F_{T} = (1, 3, 4, 7, …) is the Lucas sequence \underline{A000032}. By (2), O_{T} is \underline{A006206}. Write τ_{i} for the unique orbit of length i for 1 ⩽ i ⩽ 4, and write τ_{5}^{(1)}, τ_{5}^{(2)} for the two orbits of length 5. Then the elements in G_{T} with weight 5 are

τ_{5}^{(1)}, τ_{5}^{(2)}, τ_{4} + τ_{1}, τ_{3} + τ_{2}, τ_{3} + 2τ_{1}, τ_{2} + 3τ_{1}, 2τ_{2} + τ_{1}, 5τ_{1},

so G_{T} (5) = 8. The relation (10) shows that G_{T} (n) is the (n + 1)st Fibonacci number, so G_{T} is \underline{A000045}.

Example 22. Let T ∈ 𝔐 have d_{T} (s) = ζ(s). Then there is a one-to-one correspondence between elements of G_{T} and partitions of natural numbers, so G_{T} is the classical partition function \underline{A000041}.

Example 23. Let T : X → X be the full shift on a symbols, so that ζ_{T} (s) = \frac{1}{1−as}; (10) shows that G_{T} (n) = a^{n} − a^{n−1} for all n ⩾ 1. Thus F_{T} in this case is a linear recurrence of degree 1 while G_{T} is a linear recurrence of degree 2.

Example 24. Let X = ℤ[\frac{1}{6}] and let T : X → X be the map dual to r ↦ \frac{2}{3}r on ℤ[\frac{1}{6}]. Then F_{T} (n) = 3^{n} − 2^{n} is \underline{A001047} (a linear recurrence of degree 2) by [13] so G_{T} (n) = 3^{n−1} by (10), and G_{T} is \underline{A000244} (a linear recurrence of degree 1). More generally, if b > a > 0 are coprime integers, then the dual map to r ↦ \frac{a}{b}r on ℤ[\frac{a}{b}] has

ζ_{T} (s) = \frac{1 − as}{1 − bs},

so G_{T} (n) = (b^{n} − ab^{n−1}) for all n ⩾ 1.

Example 25. The quadratic map T from Example 8 has a particularly simple monoid: G_{T} is the binary partition function \underline{A018819} (the number of partitions of n into powers of 2; by Sloane and Sellers [19] this is also the number of “non-squashing” partitions of n).

Example 26. An example similar in growth rate to Example 25 is studied in [6]: the map dual to x ↦ 2x on the localization ℤ_{(3)} at the prime 3 has F_{T} (n) = |2^{n} − 1|_{3}^{−1}, so

O_{T} (n) = \begin{cases}1, & if n = 1 or 2 · 3^{k}, k ⩾ 1; \\ 0, & if not; \end{cases}

and therefore G_{T} (2n + 1) is the number of partitions of 6n + 3 into powers of 3 for n ⩾ 0, and G_{T} (2n) = G_{T} (2n + 1) for n ⩾ 1.

Example 27. An example of a map that is not hyperbolic but still has exponentially many periodic orbits is given by the simplest non-trivial S-integer map dual to x ↦ 2x on ℤ[1/3]. By [4] this has F_{T} (n) = (2^{n} − 1)|2^{n} − 1|_{3}, and a calculation shows that O_{T} is \underline{A060480}, and thus G_{T} = (1, 1, 3, 4, 10, 13, 33, 56, 10, …).

References

[1] M. Artin and B. Mazur, On periodic points, Ann. of Math. (2) 81 (1965), 82–99.

[2] M. Baake and R. V. Moody, Similarity submodules and semigroups, in Quasicrystals and Discrete Geometry, Fields Inst. Monogr. 10, American Mathematical Society, 1998, pp. 1–13.

[3] M. Baake and N. Neumärker, A note on the relation between fixed point and orbit count sequences, preprint, 2008. Available electronically at

http://arxiv.org/abs/0812.4354.

[4] V. Chothi, G. Everest, and T. Ward, S-integer dynamical systems: periodic points, J. Reine Angew. Math. 489 (1997), 99–132.

[5] G. Everest, R. Miles, S. Stevens, and T. Ward, Orbit-counting in non-hyperbolic dynamical systems, J. Reine Angew. Math. 608 (2007), 155–182.

[6] G. Everest, R. Miles, S. Stevens, and T. Ward, Dirichlet series for finite combinatorial rank dynamics, Trans. Amer. Math. Soc., to appear. Available electronically at

http://arxiv.org/abs/0705.1067.

[7] G. Everest, A. J. van der Poorten, Y. Puri, and T. Ward, Integer sequences and periodic points, J. Integer Seq. 5 (2002), Article 02.2.3.

[8] M. J. Feigenbaum, Scaling function dynamics, in Chaos, Order, and Patterns, NATO Adv. Sci. Inst. Ser. B Phys. 280, Plenum Press, 1991, pp. 1–23.

[9] K.-H. Indlekofer, The abstract prime number theorem for function fields, Acta Math. Hungar. 62 (1993), 137–148.

[10] K.-H. Indlekofer, E. Manstavičius, and R. Warlimont, On a certain class of infinite products with an application to arithmetical semigroups, Arch. Math. (Basel) 56 (1991), 446–453.

[11] K.-H. Indlekofer and S. Wehmeier, Mean behaviour of multiplicative functions on additive arithmetical semigroups, Comput. Math. Appl. 52 (2006), 577–592.

[12] J. Knopfmacher, Analytic Arithmetic of Algebraic Function Fields, Lecture Notes in Pure and Applied Mathematics 50, Marcel Dekker Inc., 1979.

[13] D. A. Lind and T. Ward, Automorphisms of solenoids and p-adic entropy, Ergodic Theory Dynam. Systems 8 (1988), 411–419.

[14] P. Lindqvist and J. Peetre, On a number-theoretic sum considered by Meissel—a historical observation, Nieuw Arch. Wisk. (4) 15 (1997), 175–179.

[15] M. S. M. Noorani, Mertens theorem and closed orbits of ergodic toral automorphisms, Bull. Malaysian Math. Soc. (2) 22 (1999), 127–133.

[16] A. Pakapongpun, Ph.D. thesis, University of East Anglia, Norwich, 2009.

[17] Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seq. 4 (2001), Article 01.2.1.

[18] N. J. A. Sloane and S. Plouffe, The Encyclopedia of Integer Sequences, Academic Press Inc., 1995.

[19] N. J. A. Sloane and J. A. Sellers, On non-squashing partitions, Discrete Math. 294 (2005), 259–274.

[20] S. Waddington, The prime orbit theorem for quasihyperbolic toral automorphisms, Monatsh. Math. 112 (1991), 235–248.

[21] T. Ward, Group automorphisms with few and with many periodic points, Proc. Amer. Math. Soc. 133 (2005), 91–96.

[22] S. Wehmeier, Meissel’s theorem in additive arithmetic semigroups, preprint, http://arxiv.org/abs/math/0509589.

[23] A. J. Windsor, Smoothness is not an obstruction to realizability, Ergodic Theory Dynam. Systems 28 (2008), 1037–1041.

2000 Mathematics Subject Classification: Primary 11B83. Keywords: Closed orbits; iteration; functorial properties; Dirichlet series

Concerned with sequences: \underline{A000032}, \underline{A000041}, \underline{A000045}, \underline{A000244}, \underline{A001047}, \underline{A006206}, \underline{A018819}, \underline{A027377}, \underline{A027381}, \underline{A035109}, \underline{A036987}, \underline{A038712}, \underline{A060480}, \underline{A060648}, \underline{A065333}, \underline{A091574}.

Received October 28 2008; revised version received January 20 2009. Published in Journal of Integer Sequences, February 13 2009.

Return to Journal of Integer Sequences home page.