Arithmetic and growth of periodic orbits

Yash Puri^{1}and Thomas Ward

School of Mathematics, University of East Anglia, Norwich NR4 7TJ, U.K.

Email: t.ward@uea.ac.uk

Abstract

Two natural properties of integer sequences are introduced and studied. The first, exact realizability, is the property that the sequence coincides with the number of periodic points under some map. This is shown to impose a strong inner structure on the sequence. The second, realizability in rate, is the property that the sequence asympototically approximates the number of periodic points under some map. In both cases we discuss when a sequence can have that property. For exact realizability, this amounts to examining the range and domain among integer sequences of the paired transformations

Per_{n} = ∑_{d|n} d Orb_{d};  Orb_{d} = \frac{1}{n} ∑_{d|n} μ(n/d)Per_{d}  ORBIT

that move between an arbitrary sequence of non-negative integers Orb counting the orbits of a map and the sequence Per of periodic points for that map. Several examples from the Encyclopedia of Integer Sequences arise in this work, and a table of sequences from the Encyclopedia known or conjectured to be exactly realizable is given.

1The first author gratefully acknowledges the support of E.P.S.R.C. grant 96001638

1. Introduction

Let T : X → X be a map. Three measures of growth in complexity for T are given by the number of points with period n,

f_{n}(T) = #{x ∈ X | T^{n}x = x},

the number of points with least period n,

f_{n}^{∗}(T) = #{x ∈ X | T^{n}(x) = x and #{T^{k}x}_{k∈ℤ} = n},

and the number of orbits of length n,

f_{n}^{o}(T) = f_{n}^{∗}(T)/n.

In this note we assume that f_{n}(T) is finite for n ≥ 1 and give some results on what arithmetic properties the sequence (f_{n}(T)) may have, and show when the growth in (f_{n}(T)) is related to the growth in (f_{n}^{∗}(T)). It will be convenient to adopt the following notation: a sequence a_{1}, a_{2}, a_{3}, … is denoted (a_{n}) or simply a.

Definition 1.1. Let ϕ = (ϕ_{n}) be a sequence of non-negative integers. Then

(1) ϕ ∈ ER (exactly realizable) if there is a set X and a map T : X → X for which f_{n}(T) = ϕ_{n} for all n ≥ 1;

(2) ϕ ∈ RR (realizable in rate) if there is a set X and a map T : X → X for which f_{n}(T)/ϕ_{n} → 1 as n → ∞.

None of the results below are changed if the realizing maps are required to be homeomorphisms of a compact X, but this is not pursued here.

2. Exact realization

The set of points with period n under T is the disjoint union of the set of points with least period d under T for d dividing n, so

f_{n}(T) = ∑_{d|n} f_{d}^{∗}(T).  (1)

Equation (1) may be inverted via the Möbius inversion formula to give

f_{n}^{∗}(T) = ∑_{d|n} μ(n/d)f_{d}(T),  (2)

where μ(·) is the Möbius function. On the other hand, the set of points with least period n comprises exactly f_{n}^{o} orbits each of length n, so

0 ≤ f_{n}^{∗}(T) = ∑_{d|n} μ(n/d)f_{d}(T) ≡ 0 mod n.  (3)

It is clear (since one may take X = ℕ and make T to be a permutation with the appropriate number of cycles of each length) that these are the only conditions for membership in ER.

Lemma 2.1. Let ϕ be a sequence of non-negative integers. Then ϕ ∈ ER if and only if ∑_{d|n} μ(n/d)ϕ_{d} is non-negative and divisible by n for all n ≥ 1.

Everything that follows is a consequence of this lemma. Before considering properties of ER as a whole, some examples are considered. The sequences that arise here are therefore close in spirit to the ‘eigensequences’ for the transformation MÖBIUS discussed in [1] with the additional requirement that the sequence f^{∗} be divisible by n and nonnegative.

Example 2.2. (1) The Fibonacci sequence A000045 is not in ER. Using (3) we see that f_{3} − f_{1} must always be divisible by 3, but the Fibonacci sequence begins 1, 1, 2, 3, . . .. By contrast the golden mean shift (see [10]) shows that the closely related Lucas sequence A000204 is in ER. This will be dealt with in greater generality in Section 2.2 below.

(2) For any map T, equation (3), when n is a prime p, states that

f_{p}(T) ≡ f_{1}(T) mod p.

If A ∈ GL_{k}(ℤ) is an invertible integer matrix with no unit root eigenvalues, then the periodic points in the corresponding automorphism of the k-torus show that

det(A^{p} − I) ≡ det(A − I) mod p

for all primes p.

(3) Similarly, if B ∈ M_{k}(ℕ) is a matrix of non-negative integers, the associated subshift of finite type (see [10]) shows that

trace(B^{p}) ≡ trace(B) mod p

for all primes p. When k = 1 this is Fermat’s little theorem. When B = [2], so f_{n} = 2^{n}, f_{n}^{o} is the sequence A001037 (shifted by one) counting irreducible polynomials of degree n over 𝔽_{2}.

(4) The subshifts of finite type give a family of elements of ER of exponential type. Another family comes from Pascal’s triangle: if k > 1, 1 ≤ j < k and a_{n} = \binom{kn}{jn}, then a ∈ ER. For k = 2 and j = 1, if f_{n} = f_{n}(T) for the realizing map T, then f_{n}^{∗} is the sequence A007727 counting 2n-bead black and white strings with n black beads and fundamental period 2n.

(5) Connected S-integer dynamical systems (see [3], [13] for these and the next example): a subset S ⊂ {2, 3, 5, 7, 11, … } and a rational ξ ≠ 0 are given with the property that |ξ|_{p} > 1 ⟹ p ∈ S. The resulting system constructs a map T : X → X for which

f_{n}(T) = ∏_{p≤∞} |ξ^{n} − 1|_{p}.

With ξ = 2, S = {2, 3, 5, 7} this gives the sequence

1, 1, 1, 1, 31, 1, 127, 17, 73, 341, 2047, 13, 8191, 5461, 4681, …

in ER.

(6) Zero-dimensional S-integer dynamical systems: a prime p is fixed, a subset S of the set of all irreducible polynomials in 𝔽_{p}[t] and a rational function ξ ∈ 𝔽_{p}(t) are given, with the property that |ξ|_{f} > 1 ⟹ f ∈ S. The resulting system constructs a map T : X → X for which

f_{n}(T) = |ξ^{n} − 1|_{t^{−1}} × ∏_{f∈S} |ξ^{n} − 1|_{f}

where |·|_{t^{−1}} is used to denote the valuation ‘at infinity’ induced by |t|_{t^{−1}} = p. Taking p = 2, S = {t − 1} and ξ = t gives the formula

f_{n}(T) = 2^{n−2^{ord_{2}(n)}}

and the sequence A059991 in ER.

2.1. Algebra in ER. The set ER – or the ring K_{0}(ER) – has a very rich structure. Say that a sequence a ∈ ER factorizes if there exists sequences b, c ∈ ER with a_{n} = b_{n}c_{n} for all n ≥ 1, and is prime if such a factorization requires one of b or c to be the constant sequence (1).

Lemma 2.3. ER contains the constant sequences and is closed under addition and multiplication. Elements of ER may have infinitely many non-trivial factors. There are non-trivial primes in ER.

Proof. The constant sequence (1) is in ER since it is realized by taking X to be a singleton. The condition in Lemma 2.1 is closed under addition. On the other hand, if ϕ and ψ are exactly realized by systems (X, T) and (Y, S), then (X × Y, T × S) exactly realizes (ϕ_{n} · ψ_{n}). For each k ≥ 1 define a sequence r^{(k)} by r_{n}^{(k)} = 0 for 1 < n ≤ k and r_{n}^{(k)} = 1 for n > k or n = 1. Then a^{(k)} ∈ ER, where a_{n}^{(k)} = ∑_{d|n} dr_{d}^{(k)}. Since for each n the sequence a_{n}^{(1)}, a_{n}^{(2)}, a_{n}^{(3)}, … has only finitely many terms not equal to 1, the product ∏_{k≥1} a^{(k)} = (1, 3, 16, 245, 1296, 41160, …) is an element of ER with infinitely many non-trivial factors. Finally, the sequence (1, 3, 1, 3, …) is a non-trivial prime in ER. □

In [9, Sect. 6] a periodic point counting argument is used to show that the full p-shift, for p a prime, is not topologically conjugate to the direct product of two dynamical systems. In that argument, special properties of subshifts of finite type are needed (specifically, the fact that f_{p^{k}}(T) = 1 for all k ≥ 1 implies that f_{n}(T) = 1 for all n ≥ 1 for such systems). This result does not follow from the arithmetic of ER alone: for example, (3^{n}) ∈ ER factorizes into (1, 3, 1, 3, …) × (3, 3, 3^{3}, 3^{3}, …) in ER (neither of which can be realized using a subshift of finite type). A similar factorization is possible for (p^{n}) and any odd prime p (see [11] for the details).

Lemma 2.4. There are no non-constant polynomials in ER. There are non-trivial multiplicative sequences in ER, but there are no completely multiplicative sequences apart from the constant sequence (1).

Proof. Assume that

P (n) = c_{0} + c_{1}n + ⋯ + c_{k}n^{k}

with c_{k} ≠ 0, k ≥ 1, and that (P (n)) ∈ ER. After multiplying the divisibility condition (3) by the least common multiple of the denominators of the (rational) coefficients of P, we produce a polynomial with integer coefficients satisfying (3). It is therefore enough to assume that the coefficients c_{i} are all integers. Let (f_{n}) and (f_{n}^{∗}) be the periodic points and least periodic points in the corresponding system (X, T), and let p be any prime. By (2),

f_{p^{2}}^{∗} = f_{p^{2}} − f_{p},

so

f_{p^{2}}^{o} = \frac{f_{p^{2}}^{∗}}{p^{2}} = \frac{f_{p^{2}} − f_{p}}{p^{2}}
= \frac{1}{p^{2}} (c_{1}p^{2} + c_{2}p^{4} + ⋯ + c_{k}p^{2k} − (c_{1}p + c_{2}p^{2} + ⋯ + c_{k}p^{k}))
∈ −\frac{c_{1}}{p} + ℤ,

and therefore p divides c_{1} for all primes p, showing that c_{1} = 0. Now let q be another prime, and recall that

μ(1) = 1, μ(p) = −1, μ(q) = −1, μ(p^{2}) = 0, μ(p^{2}q) = 0, μ(pq) = 1.

Since c_{1} = 0,

f_{n} = c_{0} + n^{2}(c_{2} + c_{3}n + ⋯ + c_{k}n^{k−2}),  (4)

and by (3)

p^{2}q|f_{p^{2}q} − f_{pq} − f_{p^{2}} + f_{p} = f_{p^{2}q}^{∗},

so

\frac{f_{p^{2}} − f_{p}}{p^{2}q} ∈ ℤ

by (4). It follows that

c_{0}(1 − 1) + c_{2}(p^{4} − p^{2}) + c_{3}(p^{6} − p^{3}) + ⋯ + c_{k}(p^{2k} − p^{k}) ∈ qℤ

for all primes q and p (since f_{p^{2}} − f_{p} is certainly divisible by p^{2}). So

c_{0}(1 − 1) + c_{2}(p^{4} − p^{2}) + c_{3}(p^{6} − p^{3}) + ⋯ + c_{k}(p^{2k} − p^{k}) = 0;

taking the limit as p → ∞ of \frac{1}{p^{2k}} (f_{p^{2}} − f_{p}) shows that c_{k} = 0. This contradiction proves the first statement.

There are many multiplicative sequences in ER: if f^{∗} is any multiplicative sequence, then so is the corresponding sequence f (see [7, Theorem 265]). A multiplicative sequence ϕ is completely multiplicative if ϕ_{nm} = ϕ_{n}ϕ_{m} for all n, m ≥ 1. Assume that ϕ ∈ ER is completely multiplicative, with f the realising sequence. For p a prime and any r ≥ 1,

f_{p^{r}}^{∗} = f_{p^{r}} − f_{p^{r−1}} = f_{p}^{r} − f_{p}^{r−1}

by (2). It follows that

p^{r}|f_{p}^{r−1}(f_{p} − 1).

With r = 1 this implies that f_{p} = 1 + pk_{p} for all p, k_{p} ∈ ℕ_{0}. Now

p^{r}|(1 + pk_{p})^{r−1}pk_{p}

for all p and r ≥ 1. It follows that k_{p} ≡ 0 mod p^{r} for all r ≥ 1, so k_{p} = 0 for all p. It follows that f_{p} = 1 for all primes p, so f_{n} = 1 for all n ≥ 1. □

Examples show that the additive convolution (∑_{i+j=n+1,1≤i,j≤n} ϕ_{i}ψ_{j}) of sequences ϕ, ψ ∈ ER is not in general in ER. Similarly, the multiplicative convolution (∑_{d|n} ϕ_{d}ψ_{n/d}) is not in general in ER. There is also no closure under quotients: (2^{n}) ∈ ER is term-by-term divisible by the constant sequence (2) ∈ ER, but (2^{n−1}) ∉ ER.

2.2. Binary recurrence sequences. In this section we expand on the observation made in Example 2.2.1 by showing that ER only contains special binary recurrences.

Theorem 2.5. If Δ = a^{2} + 4b is not a square, and (a, a^{2} + 2b) = 1, then a sequence u with u_{1}, u_{2} ≥ 1 satisfying the recurrence

u_{n+2} = au_{n+1} + bu_{n} for n ≥ 1  (5)

is in ER if and only if \frac{u_{2}}{u_{1}} = \frac{a^{2}+2b}{a}.

As an application, Example 2.2.1 becomes the sharper result that the Lucasian sequence a, b, a + b, a + 2b, 2a + 3b, … lies in ER if and only if b = 3a. Moreover, if f_{1} = 1, f_{2} = 1, f_{3} = 2, … is the Fibonacci sequence, then an easy consequence of Theorem 2.5 is that for any k ≥ 1 the sequence f_{k}, f_{k+1}, f_{k+2}, … is not in ER. The more general case with square discriminant, a and a^{2} + 2b having a common factor and arbitrary u_{1}, u_{2} is dealt with in [11]. Proof. First assume that \frac{u_{2}}{u_{1}} = \frac{a^{2}+2b}{a}. Then, by the assumption, the sequence u is a multiple of the sequence a, a^{2} +2b, a^{3} +3ab, … which is in ER because the subshift of finite type corresponding to the matrix

[\begin{matrix}a & b \\ 1 & 0 \end{matrix}] realizes it (and therefore any multiple of it).

Conversely, assume that u is a sequence in ER satisfying (5). Write x for the sequence

x : 2b, 2ab, 2(a^{2}b + b^{2}), …

and y for the sequence

y : 2ab, 2(a^{2}b + 2b^{2}), …,

both satisfying the recurrence (5). Notice that

2bu_{n} = Ax_{n} + By_{n},

for integers A and B. By (3), for any prime p

Ax_{p} + By_{p} ≡ Ax_{1} + By_{1} mod p.  (6)

On the other hand, it is well-known that x_{p} ≡ 2b(\frac{Δ}{p}) mod p (where (\frac{Δ}{p}) is the Legendre symbol), and y_{p} ≡ 2ab mod p (by the previous paragraph: y is in ER). So (6) implies that

2bA ((\frac{Δ}{p}) − 1) ≡ 0 mod p  (7)

for all primes p.

We now claim that the Legendre symbol (\frac{Δ}{p}) is −1 for infinitely many values of the prime p. This completes the proof of Theorem 2.5, since (7) forces A = 0 and hence u is a multiple of \frac{1}{2b}y, namely a, a^{2} +2b, . . ..

To see the claim, choose c such that (c, Δ) = 1 and the Jacobi symbol (\frac{c}{Δ}) = −1. Then by Dirichlet, there are infinitely many primes p with p ≡ c mod Δ and p ≡ 1 mod 4. For such primes, (\frac{p}{Δ}) = (\frac{Δ}{p}) = −1, which completes the proof. □

The case of square discriminant is much more involved. A full treatment is in [11]; here we simply show by examples that the result as stated no longer holds in general.

Example 2.6. (1) There are infinitely many possible values of the ratio \frac{u_{2}}{u_{1}} for binary recurrent sequences in ER satisfying

u_{n+2} = u_{n+1} + 2u_{n}.  (8)

To see this we construct two different realizing examples and then take linear integral combinations of them. The first is the subshift of finite type T corresponding to the matrix A =

[\begin{matrix}1 & 2 \\ 1 & 0 \end{matrix}]. This system has (by [10, Proposition 2.2.12]) f_{n}(T) =

trace(A^{n}), which is the sequence of Jacobsthal–Lucas numbers A014551:1, 5, 7, 17, … (shifted by one) and has initial ratio 5. On the other hand, the algebraic dynamical system S dual to x ↦ −2x on the discrete group ℤ[\frac{1}{2}] has (see, for example, [3, Lemma 5.2]) f_{n}(S) = |(−2)^{n} − 1|, which begins 3, 3, 9, 15, … and has ratio 1. Now we may apply Lemma 2.3 as follows. If s, t ∈ ℕ then (tf_{n}(T) + sf_{n}(S)) in ER is a sequence satisfying (8). It follows that the set of possible ratios \frac{u_{2}}{u_{1}} contains the infinite set \{\frac{5t+3s}{t+3s} | s, t ∈ ℕ\}.

(2) A simpler example is given by the Mersenne recurrence. Since (2^{n}) and (1) are both in ER, for any t, s ≥ 0 the sequence (t2^{n} + s) satisfying the recurrence

u_{n+2} = 3u_{n+1} − 2u_{n}  (9)

is in ER. Thus the set of possible ratios \frac{u_{2}}{u_{1}} for exactly realizable solutions of (9) contains the infinite set \{\frac{4t+s}{2t+s} | s, t ∈ ℕ\} .

For higher order recurrences with companion polynomials irreducible over the rationals, it is clear that some analogue of Theorem 2.5 holds. The rational solutions of a kth order reccurence form a rational k-space; the smallest subspace contained in ER has dimension strictly smaller than k. Is this dimension always 1?

3. Realization in rate

Write ⌊x⌋ for the greatest integer less than or equal to x and ⌈x⌉ for the smallest integer greater than or equal to x. In this section we assume that sequences are never zero. Different complications arise from zeros of sequences and these are discussed in detail in [11].

Theorem 3.1. Let α, β be positive constants.

(1) If ϕ_{n} → ∞ with \frac{ϕ_{n}}{n} → 0, then ϕ ∉ RR.

(2) The sequence (⌊n^{α}⌋) ∈ RR if and only if α > 1.

(3) The sequence (⌊β^{n}⌋) ∈ RR if and only if β ≥ 1.

Proof. 1. Assume that ϕ ∈ RR and let f be the corresponding sequence of periodic points. Then \frac{f_{n}}{ϕ_{n}} → 1, so \{\frac{f_{n}}{ϕ_{n}} \} is bounded. It follows that \{\frac{f_{n}^{∗}}{ϕ_{n}} = \frac{n}{ϕ_{n}} f_{n}^{o}\} is bounded, and hence f_{n}^{∗} = nf_{n}^{o} = 0 for all large n. This implies that f_{n} is bounded, and so \frac{f_{n}}{ϕ_{n}} → 0, which contradicts the assumption.

2. For α ∈ (0, 1) this follows from part 1. Suppose therefore that (n) ∈ RR. Then there is a sequence f ∈ ER with f_{n}/n → 1, so for p a prime, pf_{p}^{o} = f_{p}^{∗} = f_{p} − f_{1}^{∗}, and therefore f_{p}^{o} → 1 as p → ∞. Since f_{p}^{o} is an integer, it follows that f_{p}^{o} = 1 for all large p. Now let q be another large prime. Then

\frac{f_{pq}}{pq} = \frac{f_{pq}^{∗} + f_{p}^{∗} + f_{q}^{∗} + f_{1}^{∗}}{pq} = \frac{f_{pq}^{∗}}{pq} + \frac{1}{p} + \frac{1}{q} + \frac{f_{1}^{∗}}{pq} ,

so

\frac{1}{p} + \frac{1}{q} + \frac{f_{1}^{∗}}{pq} − \frac{f_{pq}}{pq} ∈ ℤ.

Fix p large and let q tend to infinity to see that

\frac{1}{p} ∈ ℤ,

which is impossible. The same argument shows that f_{n}/n cannot have any positive limit as n → ∞.

For α > 1, let f_{n}^{o} = ⌈n^{α−1} ∏_{p|d}(1 − p^{−α})⌉, where the product runs over prime divisors only. Then

∑_{d|n} d^{α} ∏_{p|d}(1 − p^{−α}) = n^{α} ≤ ∑_{d|n} df_{d}^{o} = f_{n} ≤ n^{α} + ∑_{d|n} d,

so 0 ≤ f_{n} − ϕ_{n} ≤ o(n^{α}).

3. This is clear: for β < 1 the sequence is eventually 0; for β > 1 the construction used in part 2. works. □

There are sequences growing more slowly than n^{α} in RR: in [11, Chap. 5] it is shown that (⌊Cn^{s}(log n)^{r}⌋) ∈ RR for any r ≥ 1, C > 0, s ≥ 1.

4. Comparing orbits with periodic points

As is well-known, if f^{∗} grows fast enough, then f grows very much like f^{∗} (though not conversely in the case of super-exponential growth: cf. Theorem 4.2 below). Throughout this section f_{n} = f_{n}(T) and f_{n}^{∗} = f_{n}^{∗}(T) for some map T.

Remark 4.1. That f_{n}^{∗} is close to f_{n} when f_{n} is growing exponentially has been commented on by Lind in [8, Sect. 4]. He points out, using (2), that if T is the automorphism of the 2-torus corresponding to the

matrix [\begin{matrix}2 & 1 \\ 1 & 1 \end{matrix}] then f_{20}^{∗}(T) is only 0.006% smaller than f_{20}(T). The

sequence f of periodic points for this map is A004146.

Theorem 4.2. (1) If \frac{1}{n} log f_{n}^{∗} → C ∈ [0, ∞] then \frac{1}{n} log f_{n} → C

also.

(2) \frac{1}{n} log f_{n}^{∗} → C ∈ (0, ∞) if and only if \frac{1}{n} log f_{n} → C.

(3) If \frac{1}{n} log f_{n} → ∞ then \{\frac{1}{n} log f_{n}^{∗}\} may be unbounded with infinitely many limit points.

Proof. 1. If \frac{1}{n} log f_{n}^{∗} → ∞ then \frac{1}{n} log f_{n} → ∞ also, since f_{n} ≥ f_{n}^{∗} for all n. If \frac{1}{n} log f_{n}^{∗} → C ∈ [0, ∞), then (for n large enough to have f_{n}^{∗} ≠ 0)

\frac{1}{n} log f_{n}^{∗} ≤ \frac{1}{n} log f_{n} = \frac{1}{n} log (∑_{d|n} f_{d}^{∗})

≤ \frac{1}{n} log n + \frac{1}{n} log max_{d|n}\{f_{d}^{∗}\}.

For each such n, choose ñ ∈ {d | d|n, f_{d}^{∗} ≥ f_{d′}^{∗} ∀ d′|n} so that f ∗ ; ñ =

max_{d|n}\{f_{d}^{∗}\} and \frac{ñ}{n} ≤ 1. Then

\frac{1}{n} log f_{n} ≤ \frac{1}{n} log n + \frac{ñ}{n} · \frac{1}{ñ} log f ∗ ; ñ
≤ \frac{1}{n} log n + \frac{1}{ñ} log f ∗ ; ñ → C.

2. It is enough to show that if \frac{1}{n} log f_{n} → C ∈ (0, ∞) then \frac{1}{n} log f_{n}^{∗} → C also. For r ≥ 1,

f_{r} ≥ f_{r}^{∗} = − ∑_{d|r,d≠r} f_{d}^{∗} + f_{r} ≥ f_{r} − ∑_{d|r,d≠r} f_{d}.

Let R be an upper bound for \{\frac{1}{n} log f_{n} | f_{n} ≠ 0\} and pick ϵ ∈ (0, 3C). Choose N so that

r > N ⟹ e^{r(C−ϵ)} ≤ f_{r} ≤ e^{r(C+ϵ)}.

Then for r > 2N (so that r^{∗}, N ≤ ⌊\frac{r}{2}⌋),

f_{r} ≥ f_{r}^{∗} ≥ f_{r} − ∑_{n=1}^{N} f_{n} − ∑_{n=N+1}^{⌊r/2⌋} f_{n}
≥ f_{r} − (Ne^{NR} + (r/2 − N)e^{r(C+ϵ)/2})
≥ f_{r} (1 − Ne^{NR−r(C−ϵ)} − (r/2 − N)e^{−r(C−3ϵ)/2}) ,

and the bracketed expression converges to 1 as r → ∞. Taking logs and dividing by r gives the result.

3. Write p_{1}, p_{2}, … for the sequence of primes. Let n_{r} = p_{r}p_{r+1}, and define a sequence (f_{k}^{∗}) as follows. For k not of the form n_{r}, define f_{k}^{∗} = k · 2^{k^{3}}. For k of the form n_{r} define f_{k}^{∗} according to the following scheme:

f_{n_{1}}^{∗} = n_{1}2^{n_{1}}
f_{n_{2}}^{∗} = n_{2}2^{n_{2}}, f_{n_{3}}^{∗} = n_{3}2^{2n_{3}}
f_{n_{4}}^{∗} = n_{4}2^{n_{4}}, f_{n_{5}}^{∗} = n_{5}2^{2n_{5}}, f_{n_{6}}^{∗} = n_{6}2^{3n_{6}}
f_{n_{7}}^{∗} = n_{7}2^{n_{7}}, f_{n_{8}}^{∗} = n_{8}2^{2n_{8}}, f_{n_{9}}^{∗} = n_{9}2^{3n_{9}}, f_{n_{10}}^{∗} = n_{10}2^{4n_{10}}

and so on. Then \frac{1}{n} log f_{n} → ∞ off the n_{r}’s clearly. Along the sequence (n_{r}),

f_{n_{r}} = f_{n_{r}}^{∗} + f_{p_{r}}^{∗} + f_{p_{r+1}}^{∗} + f_{1}^{∗} ≥ f_{p_{r+1}}^{∗},

so

\frac{1}{n_{r}} log f_{n_{r}} ≥ \frac{1}{p_{r}p_{r+1}} log (p_{r+1} · 2^{p_{r+1}^{3}}) → ∞.

On the other hand, along a subsequence of n_{r}’s chosen to have f_{n_{r}}^{∗} = n_{r}2^{ℓn_{r}} for a fixed ℓ ∈ ℕ (which will exist by construction), we realize ℓ log 2 as a limit point of the sequence \frac{1}{n} log f_{n}^{∗}. □

Finally, we turn to comparing these growth rates in a sub-exponential setting. For polynomial growth, the next result shows that f and f^{∗} are forced to behave very differently.

Theorem 4.3. Let C and α be positive constants.

(1) For α > 1, the set \{\frac{f_{n}^{∗}}{n^{α}} \} is bounded if and only if \{\frac{f_{n}}{n^{α}} \} is bounded.

(2) For α > 1, \frac{f_{n}}{n^{α}} → 0 if and only if \frac{f_{n}^{∗}}{n^{α}} → 0.

(3) If \frac{f_{n}}{n^{α}} → C for some α > 1, then \{\frac{f_{n}^{∗}}{n^{α}} \} has infinitely many limit points.

(4) If \frac{f_{n}^{∗}}{n^{α}} → C for some α ≥ 1, then \{\frac{f_{n}}{n^{α}} \} has infinitely many limit points.

Proof. 1. Let R be an upper bound for \{\frac{f_{n}^{∗}}{n^{α}} \}. Then

\frac{f_{n}}{n^{α}} ≤ \frac{1}{n^{α}} ∑_{d|n} Rd^{α} = R ∑_{d|n} (\frac{d}{n})^{α} ≤ R ∑_{d=1}^{∞} \frac{1}{d^{α}} < ∞.

The converse is obvious.

2. One direction is clear. Assume that \frac{f_{n}^{∗}}{n^{α}} → 0. Fix ϵ > 0; choose M_{1} ∈ ℕ so that

n > M_{1} ⟹ \frac{f_{n}^{∗}}{n^{α}} < \frac{ϵ}{1 + β}

where β = ∑_{k=1}^{∞} \frac{1}{k^{α}}. Choose M_{2} so that

n > M_{2} ⟹ ∑_{r=1}^{M_{1}} \frac{f_{r}^{∗}}{n^{α}} < \frac{ϵ}{1 + β} .

Then for n ≥ max{M_{1}, M_{2}},

0 ≤ \frac{f_{n}}{n^{α}} = ∑_{d|n} \frac{f_{d}^{∗}}{n^{α}} ≤ ∑_{r=1}^{M_{1}} \frac{f_{r}^{∗}}{n^{α}} + ∑_{d|n,d>M_{1}} \frac{f_{r}^{∗}}{n^{α}}

= ∑_{r=1}^{M_{1}} \frac{f_{r}^{∗}}{n^{α}} + ∑_{d|n,d>M_{1}} +\frac{d^{α}}{n^{α}} · \frac{f_{d}^{∗}}{d^{α}}

≤ \frac{ϵ}{1 + β} + \frac{ϵ}{1 + β} ∑_{d|n,d>M_{1}} \frac{d^{α}}{n^{α}}

≤ \frac{ϵ}{1 + β} + β \frac{ϵ}{1 + β} ≤ ϵ.

3. Assume that \frac{f_{n}}{n^{α}} → C > 0. Then \frac{f_{p}^{∗}}{p^{α}} → C along primes. For a fixed prime p,

\frac{f_{p^{r}}^{∗}}{p^{rα}} = \frac{f_{p^{r}}}{p^{rα}} − \frac{f_{p^{r−1}}}{p^{(r−1)α}} · \frac{1}{p^{α}} → (1 − \frac{1}{p^{α}} ) C

as r → ∞.

4. Assume that \frac{f_{n}^{∗}}{n^{α}} → C > 0. Then \frac{f_{p}}{p^{α}} → C along primes. For fixed prime p and q prime,

\frac{f_{pq}}{(pq)^{α}} = \frac{f_{pq}^{∗} + f_{q}^{∗} + f_{p}^{∗} + f_{1}^{∗}}{(pq)^{α}} → (1 + \frac{1}{p^{α}} ) C

as q → ∞. □

Remark 4.4. For the case \frac{f_{n}^{∗}}{n} → C > 0 in Theorem 4.3, \frac{f_{n}}{n} is unbounded: similar arguments show that

\frac{f_{p_{1}p_{2}...p_{m}}}{p_{1}p_{2} … p_{m}} ≥ ∑_{i=1}^{m} \frac{1}{p_{i}} → ∞

as m → ∞.

5. Examples

Few of the standard sequences turn out to be in ER. Here we list a few that are, and one that nearly is. In some cases the proof proceeds by exhibiting a realizing map, in others by proving the congruence. Section 6 contains a table with many sequences from the Encyclopedia in ER; in particular all sequences realized by oligomorphic permutation groups from [2] that fall in ER are listed.

Example 5.1. (1) Many trivial sequences are in ER, among them

A000004, A000012, A000079 (shifted by one), A000203.

(2) Also A023890, the sum of non-prime divisors, is in ER since it corresponds to having one orbit of each composite length.

(3) Also A000984 (shifted by one). As pointed out in Example 2.2.4, the sequence of central binomial coefficients \binom{2n}{n} is in ER for a combinatorial reason. Similarly the sequences of the form \binom{kn}{jn} are all in ER: these include A005809 (k = 3, j = 1).

(4) The sequence A001035 (shifted by one) counts the number of distinct posets on n labeled elements. The first 16 terms of this sequence are known, and so the congruence (3) can be verified for n ≤ 16. However, the sequence is not in ER. We are grateful to Greg Kuperberg for suggesting the following explanation. Write P(n) for the set of poset structures on ℤ/nℤ. Then for d|n, there is an injection ϕ_{d,n} : P(d) → P(n) obtained by pulling back a poset structure using the canonical homomorphism ℤ/nℤ → ℤ/dℤ. For certain values of n, including all prime values, we claim that those posets that do not appear in the image of one of these injections come in families of size a multiple of n, which gives the congruence (3). by Möbius inversion. Translation gives an action of ℤ/nℤ on P(n); if a given poset lies on a free orbit then that orbit is the family. In general, suppose that the stabilizer of an orbit is ℤ/(n/d)ℤ, but it is not in the image of ϕ_{d,n}. Then there is a natural action of the wreath product ℤ/dℤwrS_{n/d} defined by permuting the points in each coset of ℤ/(n/d)ℤ and adding a multiple of n/d. If n is the product of two primes (and for many other n) then the size of the orbits of this action are divisible by n. However, at n = 18 there are orbits of size ±6 mod 18, so here we expect the congruence (3) to fail.

(5) The sequence A001945: 1, 1, 1, 5, 1, 7, 8, 5, 19, … is in ER since it counts the periodic points in the automorphism of the 3-torus

given by the matrix [\begin{matrix}0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{matrix}]. This sequence has been studied

computationally for prime appearances (see [4]) and it comes from the cubic polynomial with smallest Mahler measure (see [6]).

(6) The large class of elliptic divisibility sequences (see [5]) and Somos sequences seem never to fall in ER.

(7) Three interesting sequences that seem to be in ER are the Euler sequence A000364 and the sequences A006953, A006954 connected with the Bernoulli numbers.

Example 5.2. Sequences in ER arise from the combinatorics of an iterated map. It is a natural question to ask what an orbit of ORBIT looks like, and whether there are any asymptotic properties associated to it. The simplest orbit starts with the unit sequence A000007. Applying ORBIT iteratively to this gives the following sequence of sequences (in each case, the sequence counts the number of periodic points in a map which has the number of orbits of length n given by the nth entry in the previous sequence). 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, (A000007) 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 (A000012) 1, 3, 4, 7, 6, 12, 8, 15, 13, 18, 12, 28, 14, 24, 24, 31, 18, 39, 20 (A000203) 1, 7, 13, 35, 31, 91, 57, 155, 130, 217, 133, 455, 183, 399, 403 (A001001) 1, 15, 40, 155, 156, 600, 400, 1395, 1210, 2340, 1464, 6200, 2380, 6000 1, 31, 121, 651, 781, 3751, 2801, 11811, 11011, 24211, 16105, 78771, 30941 1, 63, 364, 2667, 3906, 22932, 19608, 97155, 99463, 246078, 177156 1, 127, 1093, 10795, 19531, 138811, 137257, 788035, 896260, 2480437 1, 255, 3280, 43435, 97656, 836400, 960800, 6347715, 8069620, 24902280 1, 511, 9841, 174251, 488281, 5028751, 6725601, 50955971, 72636421 1, 1023, 29524, 698027, 2441406, 30203052, 47079208, 408345795 1, 2047, 88573, 2794155, 12207031, 181308931, 329554457, 3269560515 1, 4095, 265720, 11180715, 61035156, 1088123400, 2306881200 1, 8191, 797161, 44731051, 305175781, 6529545751, 16148168401 1, 16383, 2391484, 178940587, 1525878906, 39179682372, 113037178808 1, 32767, 7174453, 715795115, 7629394531, 235085301451 1, 65535, 21523360, 2863245995, 38146972656, 1410533397600

The arithmetic and growth properties of these sequences will be explored elsewhere. The sequence of first, second and third terms comprise A000012, A000225, and A003462 respectively.

6. Summary

Being exactly realizable is a strong symmetry property of an integer sequence. In this table we summarize the sequences from the Encyclopedia found to be exactly realizable, together with the corresponding sequence counting the orbits, and any other information. All the sequences are expected to have realizing maps – the inclusion of a map means that we know of a map that is natural in some sense (for example, has a finite description or is algebraic). Direct proofs of the congruence are cited in some brief fashion – a question mark indicates that we do not know a proof and seek one, e means it is easy, and a combinatorial counting problem suggests why the number of orbits is a non-negative integer. The combinatorial counting problems and maps are labelled as follows.

• POLY: the orbits count the number of irreducible polynomials over a finite field.

• NECK(k): the orbits count the number of aperiodic necklaces with n beads in k colours.

• NECK: the orbits count a family of necklaces with constraint – see the encyclopedia entry for details.

• KUMMER: follows from the Kummer and von Staudt congruences.

• COMB: follows from standard combinatorics arguments.

• CHK: the orbit sequence is a ‘CHK’ transform.

• S(1):S-integer map with ξ = 2, S = {2, 3}, k = ℚ.

• S(2):S-integer map with ξ = t, S = {t + 1}, k = 𝔽_{2}(t).

• R: irrational circle rotation. Of course there are often many ways to fill in the last column. If there is a natural realizing map, then that fact in itself is usually the best proof of the congruence. Sequences marked with a question mark in the first column are not known to be in ER at all: they just seem to satisfy the congruence for the first twenty or so terms. A star indicates that the initial term of the sequence is shifted by one. Of course any nonnegative integer sequence at all can appear in the second column, so the selection here is based on the following arbitrary criterion: either the periodic point sequence or the orbit counting sequence is ‘interesting’.

f_{n}(T)  f_{n}^{o}(T)  T  Proof of (3)
A000004  A000004 R  e
A000012  A000007 singleton  e
A000079*  A001037 full 2-shift  POLY
A000203  A000012 -  e
A000204  A006206 golden mean shift NECK
A000244*  A027376* full 3-shift  POLY
A000302*  A027377* full 4-shift  POLY
A000351*  A001692* full 5-shift  POLY
A000364*?  A060164 -  -
A000400*  A032164 full 6-shift  NECK(6)
A000420*  A001693 full 7-shift  POLY
A000593  A000035* -  e
A000670*  A060223 e
A000984*  A060165 -  COMB
A001001  A000203 -  e
A001018*  A027380* full 8-shift  POLY
A001019*  A027381* full 9-shift  POLY
A001020*  A032166 full 11-shift  NECK(11)
A001021*  A032167 full 12-shift  NECK(12)
A001022*  A060216 full 13-shift  NECK(13)
A001023*  A060217 full 14-shift  NECK(14)
A001024*  A060218 full 15-shift  NECK(15)
A001025*  A060219 full 16-shift  NECK(16)
A001026*  A060220 full 17-shift  NECK(17)
A001027*  A060221 full 18-shift  NECK(18)
A001029*  A060222 full 19-shift  NECK(19)
A001157  A000027 -  e
A001158  A000290* -  e
A001641?  A060166 -  -
A001642?  A060167 -  -
A001643?  A060168 -  -
A001700  A022553 -  -

A001945  A060169 auto of 𝕋^{3}  -
A004146*  A032170 auto of 𝕋^{2}  CHK
A005809*  A060170 -  COMB
A006953?  A060171 -  KUMMER?
A006954?  A060479 -  KUMMER?
A011557*  A032165* full 10-shift  NECK(10)
A023890  A005171 -  e
A027306*  A060172 -  COMB
A035316  A010052* -  e
A047863*  A060224 -  -
A048578  A060477 4-shift ∪ singleton -
A056045 A060173 - COMB
0,2,0,6,0,8,0,14,... A000035 -  e
A059928  A060478 auto of 𝕋^{10}  e
A059990  A060480 S(1)  -
A059991  A060481 S(2)  -

Table 1: Exactly realizable sequences.

References

[1] M. Bernstein and N.J.A. Sloane. Some canonical sequences of integers, Linear Algebra Appl. , 226/228:57–72, 1995.

[2] Peter J. Cameron. Sequences realized by oligomorphic permutation groups, J. Integer Seq. , 3:Article 00.1.5, html document (electronic), 2000.

[3] Vijay Chothi, Graham Everest, and Thomas Ward. S-integer dynamical systems: periodic points. J. Reine Angew. Math. , 489:99–132, 1997.

[4] Manfred Einsiedler, Graham Everest, and Thomas Ward. Primes in sequences associated to polynomials (after Lehmer). LMS J. Comput. Math. , 3:125–139 (electronic), 2000.

[5] Manfred Einsiedler, Graham Everest, and Thomas Ward. Primes in elliptic divisibility sequences. LMS J. Comput. Math. , 4:1–13 (electronic), 2001.

[6] Graham Everest and Thomas Ward, Heights of polynomials and entropy in algebraic dynamics , Springer-Verlag, London, 1999.

[7] G.H. Hardy and E.M. Wright. An introduction to the Theory of Numbers. The Clarendon Press Oxford University Press, New York, fifth edition, 1979.

[8] D.A. Lind. Dynamical properties of quasihyperbolic toral automorphisms. Ergodic Theory Dynamical Systems , 2(1):49–68, 1982.

[9] D.A. Lind. The entropies of topological Markov shifts and a related class of algebraic integers. Ergodic Theory Dynamical Systems , 4(2):283–300, 1984.

[10] Douglas Lind and Brian Marcus. An Introduction to Symbolic Dynamics and Coding . Cambridge University Press, Cambridge, 1995.

[11] Y. Puri. Arithmetic Properties of Periodic Orbits . PhD thesis, The University of East Anglia, 2000.

[12] N.J.A. Sloane. Online Encyclopedia of Integer Sequences .

[13] Thomas Ward. Almost all S-integer dynamical systems have many periodic points. Ergodic Theory Dynamical Systems , 18:471–486 (1998).

(Concerned with sequences A000004, A000007, A000012, A000027, A000035, A000045, A000079, A000203, A000204, A000225, A000244, A000290, A000302, A000351, A000364, A000400, A000420, A000593, A000670, A000984, A001001, A001018, A001019, A001020, A001021, A001022, A001023, A001024, A001025, A001026, A001027, A001029, A001035, A001037, A001157, A001158, A001641, A001642, A001643, A001692, A001693, A001700, A001945, A003462, A004146, A005171, A005809, A006206, A006953, A006954, A007727, A010052, A011557, A014551, A022553, A023890, A027306, A027376, A027377, A027380, A027381, A032164, A032165, A032166, A032167, A032170, A035316, A047863, A048578, A056045, A059928, A059990, A059991, A060164, A060165, A060166, A060167, A060168, A060169, A060170, A060171, A060172, A060173, A060216, A060217, A060218, A060219, A060220, A060221, A060222, A060223, A060224, A060477, A060478, A060479, A060480, A060481.)

Received March 20, 2001. Published in Journal of Integer Sequences, Oct 14, 2001.

Return to Journal of Integer Sequences home page.