A Note on the Relation Between Fixed Point and Orbit Count Sequences

Michael Baake and Natascha Neumärker Fakultät für Mathematik Universität Bielefeld Postfach 100131 33501 Bielefeld Germany

                 mbaake@math.uni-bielefeld.de
                naneumae@math.uni-bielefeld.de

Abstract The relation between fixed point and orbit count sequences is investigated from the point of view of linear mappings on the space of arithmetic functions. Spectral and asymptotic properties are derived and several quantities are explicitly given in terms of Gaussian binomial coefficients.

1 Introduction and general setting

Each map of an arbitrary set into itself gives rise to sequences a = (a_{n})_{n∈ℕ} and c = (c_{n})_{n∈ℕ} that count the number of periodic points with period n and the orbits of length n, respectively. In many interesting cases, a_{n} and c_{n} are finite for all n ∈ ℕ, turning a and c into sequences of non-negative integers. They are then related by Möbius inversion as

a_{n} = ∑_{d|n} d c_{d} and c_{n} = \frac{1}{n} ∑_{d|n} μ (\frac{n}{d}) a_{d}.  (1)

Here, μ denotes the Möbius function from elementary number theory [1]. Puri and Ward [10] study these relations as paired transformations between certain non-negative integer sequences, with special emphasis on arithmetic and asymptotic aspects. It is the purpose of this short note, which is based on [8], to extend these transformations to the space of arithmetic functions, on which they act as linear operators, and to investigate their spectral properties and their asymptotic behaviour under iteration, thus generalising results from [10].

Let A = ℂ^{ℕ} denote the set of arithmetic functions. Its elements can be thought of either as functions f : ℕ → ℂ, n ↦ f(n), or as sequences of complex numbers (f_{n})_{n∈ℕ}, hence the notations f(n) and f_{n} are used in parallel; see [1] for details and general notation. Clearly, A is a complex vector space with respect to component-wise addition and the usual scalar multiplication. Additionally, it is equipped with the structure of a commutative algebra (A, +, ∗) with unit element, where ∗ denotes Dirichlet convolution, defined by

(f ∗ g)(n) = ∑_{d|n} f(d) g (\frac{n}{d})

for all n ∈ ℕ. The unit element with regard to this product is δ_{1} = (1, 0, 0, …). When f ∈ A is invertible, the notation f^{−1} refers to its Dirichlet inverse, defined by f ∗f^{−1} = f^{−1}∗f = δ_{1}. Furthermore, f · g denotes the pointwise product where (f · g)(n) = f(n)g(n) for all n ∈ ℕ. Motivated by the transformations (1), we define ‘fix’ and ‘orb’ as mappings from A into itself by a ↦ a′, with

a′_{n} = fix(a)_{n} = ∑_{d|n} d a_{d} and a′_{n} = orb(a)_{n} = \frac{1}{n} ∑_{d|n} μ(\frac{n}{d})a_{d},  (2)

respectively, for all n ∈ ℕ. Denoting by N the arithmetic function n ↦ n, fix and orb can be written as

fix(f) = N · (\frac{1}{N} ∗ f) and orb(f) = \frac{1}{N} · (μ ∗ f).  (3)

This is particularly useful when considering the Dirichlet series of fix(f) and orb(f). In general, the Dirichlet series D_{f} of f ∈ A is defined by

D_{f}(s) = ∑_{m=1}^{∞} \frac{f(m)}{m^{s}} ,

which is viewed as a formal series at this stage. This generating function gives rise to the (formal) identities [1]

D_{f+g} = D_{f} + D_{g} and D_{f∗g} = D_{f} · D_{g}.

Using these in connection with (3), a straightforward calculation shows

Lemma 1. Let D_{a}(s) denote the Dirichlet series of a ∈ A. Then,

D_{fix(a)}(s) = ζ (s) D_{a}(s − 1) and D_{orb(a)}(s) = \frac{1}{ζ (s + 1)} D_{a}(s + 1).

where ζ is Riemann’s zeta function. □

For a discussion of the identities from Lemma 1 in a different context, and for interesting recent development on Dirichlet series as orbit counting generating functions, we refer the reader to [3, Secs. 2 and 10]. We now turn our attention to the structure of fix and orb as linear mappings on A.

2 Spectral properties

When studying fix on A, it is natural to ask for eigenvalues and eigenvectors. Let x be an arithmetic function that satisfies the fixed point condition fix(x)_{n} = ∑_{d|n} d x_{d} = x_{n} for all n ∈ ℕ. Solving for x_{n} yields the recursive relation

x_{n} = \frac{1}{1 − n} ∑_{n>d|n} d x_{d}  (4)

for n > 1, so that all x_{n} are uniquely determined from x_{1}. The x_{n} depend linearly on x_{1}, which is the only degree of freedom in solving (4), wherefore the eigenspace for the eigenvalue 1 is one-dimensional. Setting x_{1} = a_{1} = 1, we denote the resulting solution of (4) by a = (a_{1}, a_{2}, a_{3}, …). Since fix maps multiplicative sequences to multiplicative sequences, it is an interesting question to what extent this is reflected by a.

Lemma 2. Let a satisfy fix(a) = a, with a_{1} = 1. The eigenvector a is multiplicative, so that a_{nm} = a_{n} · a_{m} for all n, m ≥ 1 with (m, n) = 1.

Proof. In order to show multiplicativity by induction on the index, we first note that the claim is true for trivial decompositions such as n · 1, because a_{1} = 1. In particular, it is then true for all natural numbers n ≤ 5 = 2 · 3 − 1. Let (m, n) = 1 with mn > 1 and suppose the a_{k} satisfy the multiplicativity property for all k ≤ mn − 1 (so that a_{k} = a_{d} a_{d′} for all d, d′ with (d, d′) = 1 and d d′ = k). This implies

a_{mn} = \frac{1}{1 − mn} ∑_{\begin{matrix}d|mn \\ d<mn \end{matrix}} d a_{d} = \frac{1}{1 − mn} ∑_{\begin{matrix}d=d_{m}d_{n} \\ d_{m}|m, d_{n}|n \\ d_{m}d_{n}<mn \end{matrix}}(d_{m}a_{d_{m}}) (d_{n}a_{d_{n}})

= \frac{1}{1 − mn}((\underbrace{∑_{d|m} da_{d}}_{=a_{m}} \underbrace{∑_{d′|n} d′a_{d′}}_{=a_{n}}) − mn a_{m}a_{n}) = a_{m} a_{n}.

This argument shows the induction step from mn − 1 to mn. In general, the step from N to N + 1 is trivial when N + 1 is prime, and of the above form otherwise, which completes the induction.

For the remainder of this section, a always denotes the unique solution of fix(a) = a with a_{1} = 1. The recursion in (4) runs over all proper divisors of n and yields an explicit expression for a_{p^{r}} with p prime and r ∈ ℕ. By multiplicativity, this extends to a closed formula for a_{n}.

Proposition 3. Let n > 1 with prime decomposition n = p_{1}^{r_{1}} · . . . · p_{s}^{r_{s}}. Then, the n-th entry of the eigenvector a of Lemma 2 reads

a_{n} = ∏_{k=1}^{s} ∏_{ℓ=1}^{r_{k}} \frac{1}{1 − p_{k}^{ℓ}} .

Proof. Observing that a_{p} = \frac{a_{1}}{1−p}, induction on the exponent r leads to a_{p^{r}} = ∏_{ℓ=1}^{r}(1 − p^{ℓ})^{−1}, from which the statement follows by Lemma 2.

The sequence of denominators is now entry \underline{A153038} of the Online Encyclopedia of Integer Sequences (OEIS) [11]. In particular, |a_{n}| ≤ 1 for all n, and Proposition 3 suggests that the a_{n} become ‘asymptotically small’ in some sense, as n → ∞. Indeed, with

ℓ^{q} = {f ∈ ℂ^{ℕ} | ∑_{n=1}^{∞} |f_{n}|^{q} < ∞},

one obtains the following result.

Proposition 4. The eigenvector a is an element of ℓ^{1+ε} for all ε > 0.

Proof. Substituting p^{k} − 1 = (p − 1) ∑_{j=0}^{k−1} p^{j} in the denominator of |a_{p^{r}}| leads to

∏_{k=1}^{r}(p^{k} − 1) = (p − 1)^{r} ∏_{k=1}^{r} ∑_{j=0}^{k−1} p^{j} ≥ (p − 1)^{r}p^{∑{r \atop k=1} (k−1)} = (p − 1)^{r}p^{r(r−1)/2}.

Since (p − 1)^{r}p^{r(r−1)/2} ≥ p^{r} for r > 2 or p > 2, the inequality |a_{p^{r}}| ≤ \frac{1}{p^{r}} holds in these cases. Besides, one has |a_{p}| = \frac{1}{p−1} = \frac{p}{p−1} · \frac{1}{p} for every prime p. The remaining term a_{2^{2}} = \frac{4}{3} \frac{1}{2^{2}} introduces an additional factor of c = \frac{4}{3} in the estimate of |a_{n}|, to account for the case when 2^{2} is the highest power of 2 that divides n. For n = p_{1}^{r_{1}} · . . . · p_{s}^{r_{s}}, this gives

|a_{n}| ≤ \frac{c}{n} ∏_{\{i|r_{i}=1\}} \frac{p_{i}}{p_{i} − 1}.

This product can be related to Euler’s ϕ-function,

ϕ(n) = n ∏_{p|n} (1 − \frac{1}{p}) = n ∏_{p|n} (\frac{p − 1}{p}) ≤ n ∏_{\begin{matrix}p|n \\ p^{2}∤n \end{matrix}}^{r}(\frac{p − 1}{p}) ,

giving ∏_{\{i|r_{i}=1\}} \frac{p_{i}}{p_{i}−1} ≤ \frac{n}{ϕ(n)}. Using

lim sup_{n→∞} \frac{n}{ϕ(n) log(log n)} = e^{γ},

where γ = lim_{n→∞} (1 + \frac{1}{2} + ⋯ + \frac{1}{n} − log n) denotes Euler’s constant, compare [6, Thm. 328], we obtain

|a_{n}| ≤ \frac{C · log(log(n))}{n}

for some constant C, which implies ∑_{n=1}^{∞} |a_{n}|^{1+ε} < ∞.

In particular, a ∈ ℓ^{2}, and (numerically) one finds ∑_{n=1}^{∞}|a_{n}|^{2} ≈ 2.99635 < 3. Since ∑_{p} \frac{1}{p} diverges and |a_{p}| = \frac{1}{p−1} > \frac{1}{p}, it is clear that the statement of Proposition 4 is not true for ε = 0.

Lemma 5. Let D_{a}(s) be the Dirichlet series of the eigenvector a, with s = σ + it.

(i) D_{a}(s) converges absolutely in S = {s ∈ ℂ | σ > 1}.

(ii) lim_{σ→∞} D_{a}(σ + it) = 1, uniformly in t ∈ ℝ.

Proof. We employ the methods of [1, Chapter 11]. The first claim follows from the absolute convergence of ζ(σ) for σ > 1, because ∑_{m} |\frac{a_{m}}{m^{s}} | ≤ ∑_{m} \frac{|a_{m}|}{m^{σ}} ≤ ζ(σ).

For (ii), observe that a_{1} = 1, wherefore one has

|D_{a}(s) − 1| ≤ ∑_{m=2}^{∞} \frac{1}{m^{σ}} = ζ(σ) − 1,

which tends to 0 (independently of t) as σ → ∞.

Using the fixed point relations fix(a) = a and orb(a) = a, the first equation of Lemma 1 becomes a ‘recursion’ that can be solved for an explicit expression in terms of the Riemann zeta function.

Theorem 6. The Dirichlet series of the fixed point a satisfies

D_{a}(s) = ∏_{ℓ=1}^{∞} \frac{1}{ζ(s + ℓ)} = ∏_{p} ∏_{ℓ≥1} (1 − \frac{1}{p^{s+ℓ}} ) ,

where the infinite product converges on the set S from Lemma 5.

Proof. Using Lemma 1, one inductively obtains D_{a}(s) = \frac{D_{a}(s+m)}{∏_{ℓ=1}^{m} ζ(s+ℓ)} for arbitrary m ∈ ℕ. For m → ∞, the numerator converges to 1, since

D_{a}(s + m) = a_{1} + ∑_{n≥2} \frac{a_{n}}{n^{s}} \frac{1}{n^{m}} ≤ a_{1} + \frac{1}{2^{m}} D_{a}(s).

Due to the asymptotic behaviour ζ(σ + it) = 1 + O(1/2^{σ}) for σ → ∞, the product in the denominator of the resulting expression D_{a}(s) = ∏_{ℓ=1}^{∞} \frac{1}{ζ(s+ℓ)} converges as well, giving the first part of the claim. The second equality follows from the Euler product representation ζ(s + ℓ)^{−1} = ∏_{p}(1 − p^{−(s+ℓ)}) for σ > 1, in which the order of taking products over p and ℓ may be exchanged due to absolute convergence.

Remark. Since a_{1} ≠ 0, a admits a Dirichlet inverse. Its terms can be calculated via to the general recursion formula, compare [1, Thm. 2.8]. The Dirichlet inverse satisfies D_{f^{−1}} = 1/D_{f}, wherefore b := a^{−1} has the Dirichlet series D_{b} = ∏_{ℓ≥1} ζ(s + ℓ). Determining the coefficients of this series leads to an analogue of Proposition 3; the n-th entry of b is

b_{n} = ∏_{j=1}^{s} ∏_{k=1}^{r_{j}} \frac{p_{j}^{k−1}}{p_{j}^{k} − 1} = ∏_{j=1}^{s} \frac{p_{j}^{\frac{1}{2} r_{j}(r_{j}−1)}}{∏_{ℓ=1}^{r_{j}}(p_{j}^{ℓ} − 1)},

with n = p_{1}^{r_{1}} · . . . · p_{s}^{r_{s}} as before; see [8] for details. The first few terms of a and b read

a = (1, −1, −\frac{1}{2}, \frac{1}{3}, −\frac{1}{4}, \frac{1}{2}, −\frac{1}{6}, −\frac{1}{21}, …) and b = (1, 1, \frac{1}{2}, \frac{2}{3}, \frac{1}{4}, \frac{1}{2}, \frac{1}{6}, \frac{8}{21}, …).

Although it appears that a and b share the same denominator sequence, this is not true when the terms are represented as reduced fractions, because cancellation can occur for the b_{n}. The first instance of this phenomenon is b_{12} = \frac{1}{3}, whereas a_{12} = −\frac{1}{6}.

Returning to the task of identifying all eigenvalues and their corresponding eigenspaces, we consider the equation x = λ · fix(x) for λ ≠ 1 or, equivalently,

(λ − n) x_{n} = λ ∑_{n>d|n} d x_{d}

for all n ∈ ℕ. Since fix(x)_{1} = x_{1} by definition, the first term of such an eigenvector has to be 0. In general, if x_{d} = 0 for all d|n with d < n, the n-th term x_{n} will vanish as well, unless λ = n. Thus, the first non-zero term is x_{m} where m = λ, and all eigenvalues are thus natural numbers. For fixed 1 < m ∈ ℕ, the recursion analogous to the case m = 1 given in (4) is

x_{n} = \frac{1}{m − n} ∑_{n>d|n} d x_{d}  (for n ≠ m),  (5)

which shows that x_{n} ≠ 0 if and only if n = km for some k ≥ 1. The recursion for the non-vanishing terms simplifies to

x_{km} = \frac{1}{m(1 − k)} ∑_{k>d|k} dm x_{dm} = \frac{1}{1 − k} ∑_{k>d|k} d x_{dm}

for k > 1,where the only free parameter is now the first non-zero term x_{m}, indicating a one-dimensional eigenspace. Choosing x_{m} = a_{1} = 1, the resulting eigenvector a^{(m)} with eigenvalue m can be expressed in terms of a = a^{(1)}:

a^{(m)}(n) = \begin{cases}a (\frac{n}{m}) , & if m|n; \\ 0, & otherwise. \end{cases}  (6)

In particular, a^{(m)} ∈ ℓ^{1+ε} for all ε > 0 and all m ≥ 1, where a^{(m)} and a clearly have the same norm. Being eigenvectors for different eigenvalues, the a^{(m)} are linearly independent. The next proposition states that they even generate the space of arithmetic functions in the sense of formal linear combinations.

Proposition 7. The eigenvectors of fix form a basis of A, so that ⟨a^{(m)} | m ∈ ℕ⟩_{ℂ} = A, and the representation of f ∈ A as a formal linear combination of the a^{(m)} is unique.

Proof. Let f ∈ A, a = a^{(1)} and b := (a)^{−1}, and set α = f ∗ b. Then, α ∗ a = (f ∗ b) ∗ a = f. On the other hand, one has

(α ∗ a)(k) = ∑_{d|k} α_{d} a^{(d)}(k) = ∑_{m≥1} α_{m} a^{(m)}(k)

for all k ∈ ℕ, so f ∈ ⟨a^{(m)} | m ∈ ℕ⟩_{ℂ}. Uniqueness of the linear combination follows from the uniqueness of the Dirichlet inverse.

The spectrum of an operator T: A → A is defined by

spec(T) := {λ ∈ ℂ | T − λ id is not invertible }.

Note that fix and orb could be investigated as operators on ℓ^{2}, restricting their domains to appropriate invariant subspaces. But since we need a more general setting later when considering their behaviour under iteration, we work with the spectrum as a purely algebraic notion.

Theorem 8. The spectra of fix and orb are

spec(fix) = ℕ and spec(orb) = \{\frac{1}{N} | N ∈ ℕ\} .

Proof. Obviously, fix(f) = λf implies f = 0 if and only if λ ∈ ℂ \ ℕ, so fix − λ id is injective for these λ. Surjectivity can be seen by constructing a preimage f ∈ A of an arbitrary g ∈ A under fix − λ id. To this end, let f_{1} = \frac{g_{1}}{1−λ} and, having already defined f_{1}, …, f_{n−1} for some n > 1, set

f_{n} = \frac{1}{n − λ}(g_{n} − ∑_{n>d|n} d f_{d}).

When λ ∉ ℕ, the resulting arithmetic function f is a term-wise well-defined element of A with fix(f) − λf = g. In summary, fix − λ id is invertible if and only if λ ∈ ℂ \ ℕ. The spectrum of orb can be derived from that of fix by the equivalence

fix(a^{(N)}) = Na^{(N)} ⟺ orb(a^{(N)}) = \frac{1}{N} a^{(N)},

which follows from fix ∘ orb = orb ∘ fix = id.

3 Iterations of the operator fix

Puri and Ward [10] raised the question of the nature of the orbits under fix. In particular, the asymptotic properties of such orbits are sought. In our terminology, this is to ask how elements of A behave under iteration of the operator fix. Starting from δ_{1} = (1, 0, 0, …), the first iterates are the sequences \underline{A000007}, \underline{A000012}, \underline{A000203}, \underline{A001001} and \underline{A038991} – \underline{A038999} of the OEIS, see [10, 11]. Here, we start from the sequences δ_{m}, m ≥ 1, defined via δ_{m}(n) = δ_{m,n} for all n, and give term-wise exact representations of fix^{n}(δ_{m}), from which the corresponding quantities of general starting sequences can later be constructed.

Let y^{(0)} = δ_{1} and y^{(n)} := fix(y^{(n−1)}) for n ≥ 1, so that

y^{(n)}(m) = (fix(y^{(n−1)}))_{m} = (fix^{n}(y^{(0)}))_{m}

holds for all m ≥ 1.

Proposition 9. Let p be a prime and r ∈ ℕ. Then

y^{(n)}(p^{r}) = [\begin{matrix}n + r − 1 \\ r \end{matrix}]_{p} = ∏_{i=0}^{r−1} \frac{1 − p^{n+r−1−i}}{1 − p^{i+1}} ,

where [ \begin{matrix}n \\ r \end{matrix}]_{q} denotes the Gaussian or q-binomial coefficient.

Proof. The claim can be verified by induction in n. By definition of fix, we have

y^{(n+1)}(p^{r}) = fix(y^{(n)})(p^{r}) = ∑_{d|p^{r}} d · y^{(n)}(d) = ∑_{k=0}^{r} p^{k} · y^{(n)}(p^{k})

= 1 + p [\begin{matrix}n \\ 1 \end{matrix}]_{p} + ∑_{k=2}^{r} p^{k} · y^{(n)}(p^{k}).  (7)

Applying Pascal’s identity for Gaussian binomials,

[\begin{matrix}m \\ ℓ \end{matrix}]_{q} = q^{r} [\begin{matrix}m − 1 \\ ℓ \end{matrix}]_{q} + [\begin{matrix}m − 1 \\ ℓ − 1 \end{matrix}]_{q} ,

to the k-th summand in (7) yields

p^{k} [\begin{matrix}n + k − 1 \\ k \end{matrix}]_{p} = [\begin{matrix}n + k \\ k \end{matrix}]_{p} − [\begin{matrix}n + k − 1 \\ k − 1 \end{matrix}]_{p} .

Plugging this and the relation [ \begin{matrix}n \\ 1 \end{matrix} ]_{p} = ∑_{k=0}^{n−1} p^{k} into (7), we obtain

y^{(n+1)}(p^{r}) = [\begin{matrix}n + 1 \\ 1 \end{matrix}]_{p} + ∑_{k=2}^{r} [\begin{matrix}n + k \\ k \end{matrix}]_{p} − [\begin{matrix}n + k − 1 \\ k − 1 \end{matrix}]_{p} = [\begin{matrix}n + r \\ r \end{matrix}]_{p}

which completes the proof.

Corollary 10. For 1 ≠ m ∈ ℕ with prime decomposition m = p_{1}^{r_{1}}p_{2}^{r_{2}} · . . . · p_{k}^{r_{k}}, one has

y^{(n)}(m) = y^{(n)}(p_{1}^{r_{1}}) y^{(n)}(p_{2}^{r_{2}}) · . . . · y^{(n)}(p_{k}^{r_{k}}) = ∏_{j=1}^{k} ∏_{i=0}^{r_{j}−1} \frac{1 − p_{j}^{n+r_{j}−1−i}}{1 − p_{j}^{i+1}} .

Proof. It is easy to check that fix, and hence all iterates fix^{n} with n ≥ 1, preserve multiplicativity. Thus, in view of Proposition 9, the claim follows from δ_{1} being multiplicative.

Remark. A different approach to calculating y^{(n)} exploits the fact that its Dirichlet series D_{y^{(n)}}(s) is known from the context of counting sublattices of ℤ^{n}. Let

h_{n}(m) = |{Λ | Λ is a sublattice of ℤ^{n} of index m}|

and D_{h_{n}}(s) = ∑_{m≥1} \frac{h_{n}(m)}{m^{s}}. Proposition A.1 of [2] states that

h_{n}(m) = ∑_{d_{1}·...·d_{n}=m} d_{1}^{0} · d_{2}^{1} · . . . · d_{n}^{n−1} and D_{h_{n}}(s) = ζ(s) · D_{h_{n−1}}(s − 1),

where the first sum runs over all n-tuples (d_{1}, …, d_{n}) of positive integers with d_{1}·. . .·d_{n} = m. In particular, D_{h_{1}}(s) = ζ(s) = D_{y^{(1)}}(s). On the other hand, Lemma 1 gives D_{y^{(n+1)}}(s) = ζ(s)D_{y^{(n)}}(s−1), so D_{y^{(n)}}(s) = D_{h_{n}}(s) for all n ≥ 1 and thus h_{n}(m) = y^{(n)}(m) for all n, m ≥ 1. For m = p_{1}^{r_{1}} · . . . · p_{k}^{r_{k}}, the coefficient h_{n}(m) can be written as

h_{n}(m) = ∏_{j=1}^{k} ∏_{i=1}^{r_{j}} \frac{p_{j}^{n+i−1} − 1}{p_{j}^{i} − 1} = ∏_{j=1}^{k} [\begin{matrix}n + r_{j} − 1 \\ r_{j} \end{matrix}]_{p_{j}} ,

as shown in [5] and [12], leading to the result of Corollary 10. This also provides a concrete interpretation of the iteration sequences mentioned earlier.

Similarly to calculating fix-eigenvectors a^{(m)} for m > 1, the sequences arising from fixiterations on starting sequences δ_{m} with m > 1 can be related to the case m = 1. From (fix(δ_{m}))_{k} = m · δ_{k,jm} for some j ∈ ℕ, one can conclude inductively

(fix^{n}(δ_{m}))_{k} = \begin{cases}m^{n}· y^{(n)}(\frac{k}{m}), & if m|k; \\ 0, & otherwise. \end{cases}

Since arbitrary elements from A can be written as complex linear combinations of the δ_{m}, we find the following behaviour of general arithmetic sequences under fix-iterations.

Lemma 11. Let f = (f_{1}, f_{2}, …) ∈ A. Then, for all M ≥ 1,

(fix^{n}(f))_{M} = ∑_{k=1}^{M} f_{k} (fix^{n}(δ_{k}))_{M} = ∑_{k|M} f_{k} k^{n}y^{(n)}(\frac{M}{k} ).

As a convolution product, this is

fix^{n}(f) = (f · N^{n}) ∗ y^{(n)}, for all n ∈ ℕ,

where N^{n} denotes the arithmetic function defined by m ↦ m^{n}.

Proof. Note first that, for all M ≥ 1, the value fix(f)_{M} depends on the f_{n} with n|M only. Each single term of fix(f)_{M} can thus be obtained by applying fix to the finite linear combination ∑_{k=1}^{M} f_{k}δ_{k}, resulting in a component-wise well-defined arithmetic function. The last identity follows from the definition of the convolution product.

Given the unbounded spectrum of fix, it is not surprising that the image sequences fix^{n}(f) of a non-negative f component-wise tend to infinity when n → ∞. Nevertheless, the ‘quotient sequences’ (\frac{fix^{n+1}(f)_{M}}{fix^{n}(f)_{M}} )_{n} have a well-defined convergence behaviour for each M as follows.

Theorem 12. Let f be a non-negative arithmetic function and let M ∈ ℕ be such that (fix^{r}(f))_{M} ≠ 0 for some r ∈ ℕ. Then,

lim_{n→∞} \frac{(fix^{n+1}(f))_{M}}{(fix^{n}(f))_{M}} = M .

Proof. Expanding the quotient in question yields

\frac{(fix^{n+1}(f))_{M}}{(fix^{n}(f))_{M}} = ∑_{d|M} d \frac{(fix^{n}(f))_{d}}{(fix^{n}(f))_{M}} = M + ∑_{M>d|M} d \frac{(fix^{n}(f))_{d}}{(fix^{n}(f))_{M}} .

The number of terms in the last sum being independent of n, it suffices to show that, for each divisor d of M, the corresponding summand approaches 0 as n → ∞. Let d_{1} = 1, …, d_{R} = d denote the divisors of d. Then, using Lemma 11, one gets

\frac{(fix^{n}(f))_{d}}{(fix^{n}(f))_{M}} = ∑_{i=1}^{R} \frac{f_{d_{i}} d_{i}^{n} y^{(n)}(\frac{d}{d_{i}} )}{∑_{k|M} f_{k} k^{n}y^{(n)}(\frac{M}{k} )} ≤ ∑_{i=1}^{R} \frac{d_{i}^{n} f_{d_{i}}y^{(n)}(d/d_{i})}{d_{i}^{n} f_{d_{i}}y^{(n)}(M/d_{i})} = ∑_{i=1}^{R} \frac{y^{(n)}(d/d_{i})}{y^{(n)}(M/d_{i})} .

This upper bound can be seen to converge to 0 by splitting numerator and denominator of each summand in the last sum into the factors that arise from the prime decomposition of d/d_{i} and M/d_{i}. For r > s, the quotient

\frac{y^{(n)}(p^{s})}{y^{(n)}(p^{r})} = ∏_{i=0}^{s−1} \frac{1 − p^{n+s−1−i}}{1 − p^{n+r−1−i}} ∏_{i=s}^{r−1} \frac{1 − p^{i+1}}{1 − p^{n+r−1−i}}  (8)

converges to 0 as n → ∞, since the first product tends to p^{s−r} > 0, while the second tends to 0. Being composed of factors such as (8), the quotient (fix^{n}(f))_{d} /(fix^{n}(f))_{M} tends to 0 for all d|M as n → ∞, which proves the claim.

Remark. Unlike fix, the operator orb’s spectrum is bounded by 0 from below and by 1 from above. One would expect orb^{n}(f) to converge to an element of the eigenspace for the largest eigenvalue (λ = 1), hence to a scalar multiple of a^{(1)} = a. Indeed, employing the eigenvector basis representation f = ∑_{m≥1} α_{m}a^{(m)}, one obtains

lim_{n→∞}(orb^{n}f)_{M} = lim_{n→∞} ∑_{m=1}^{M} α_{m}orb^{n}(a^{(m)})_{M} = lim_{n→∞} ∑_{m=1}^{M} α_{m} \frac{1}{m^{n}} a_{M}^{(m)} = α_{1}a_{M}^{(1)}

for all M ∈ ℕ. In other words, orb^{n}(f) ⟶^{n→∞} f_{1} a, for all f ∈ A.

4 Concluding remarks

The eigenvector a has an interesting consequence in the setting of dynamical (or Artin-Mazur) zeta functions, where one considers the generating function

exp (∑_{m=1}^{∞} \frac{f_{m}}{m} z^{m}) = ∏_{m=1}^{∞}(1 − z^{m})^{−orb(f)_{m}},

usually for arithmetic functions f that count (isolated) fixed points of a discrete dynamical system, see [4] for background material. Using a together with a = orb(a), one finds the product identity

exp (∑_{m=1}^{∞} \frac{a_{m}}{m} z^{m}) = ∏_{m=1}^{∞}(1 − z^{m})^{−a_{m}}

or, equivalently, the series identity

∑_{m=1}^{∞} \frac{a_{m}}{m} z^{m} = − ∑_{m=1}^{∞} a_{m} log(1 − z^{m}),

with absolute convergence for |z| < 1. It would be interesting to know whether this gives rise to another interpretation of the meaning of the eigenvector a in this setting.

5 Acknowledgements

It is our pleasure to thank Tom Ward for his interest in this work and to John A. G. Roberts and Johan Nilsson for useful hints on the manuscript. This work was supported by the German Research Council (DFG), within the CRC 701.

References

[1] T. M. Apostol, Introduction to Analytic Number Theory, Springer, New York, 1976.

[2] M. Baake, Solution of the coincidence problem in dimensions d ≤ 4, in R.V. Moody, ed., The Mathematics of Long-Range Aperiodic Order, NATO-ASI Series C489, Kluwer, Dordrecht (1997), pp. 9–44; revised version available at

http://arxiv.org/abs/math/0605222.

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

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

[4] A. Fel’shtyn, Dynamical Zeta Functions, Nielsen Theory and Reidemeister Torsion, Memoirs of the American Mathematical Society, Vol. 147, no. 699, American Mathematical Society, Providence, RI, 2000.

[5] B. Gruber, Alternative formulae for the number of sublattices, Acta Cryst. A53 (1997), 807–808.

[6] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Clarendon Press, Oxford, 1979.

[7] P. Moss, Algebraic realizability problems, PhD thesis, University of East Anglia, Norwich, 2003.

[8] N. Neumärker, Orbitstatistik und relative Realisierbarkeit, Diplomarbeit, Universität Bielefeld, 2007.

[9] Y. Puri, Arithmetic and growth of periodic orbits, PhD thesis, University of East Anglia, Norwich, 2000.

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

[11] N. J. A. Sloane, The Online Encyclopedia of Integer Sequences,

    http://www.research.att.com/∼njas/sequences/.

[12] Y. M. Zou, Gaussian binomials and the number of sublattices, Acta Cryst. A62 (2006),

    409–410. Preprint available at http://arxiv.org/abs/math/0610684.

2000 Mathematics Subject Classification: Primary 37A45; Secondary 11A25. Keywords: dynamical systems, Möbius inversion, arithmetic functions, spectra, asymptotics.

(Concerned with sequences \underline{A000007}, \underline{A000012}, \underline{A000203}, \underline{A001001}, \underline{A038991}, \underline{A038992}, \underline{A038993}, \underline{A038994}, \underline{A038995}, \underline{A038996}, \underline{A038997}, \underline{A038998}, \underline{A038999}, and \underline{A153038}.)

Received December 23 2008; revised version received May 6 2009. Published in Journal of Integer Sequences, May 12 2009.

Return to Journal of Integer Sequences home page.