INTEGER SEQUENCES AND PERIODIC POINTS

G. Everest^{1}, A. J. van der Poorten^{2}, Y. Puri^{1}, and T. Ward^{1}

1 School of Mathematics, University of East Anglia, Norwich NR4 7TJ, United Kingdom

           g.everest@uea.ac.uk, puri@hotmail.com, t.ward@uea.ac.uk

2 ICS, Macquarie University, NSW 2109, Australia

                            alf@math.mq.edu.au

Abstract. Arithmetic properties of integer sequences counting periodic points are studied, and applied to the case of linear recurrence sequences, Bernoulli numerators, and Bernoulli

denominators.

1. Introduction

An existing dialogue between number theory and dynamical systems is advanced. A combinatorial device gives necessary and sufficient conditions for a sequence of non-negative integers to count the periodic points in a dynamical system. This is applied to study linear recurrence sequences which count periodic points. Instances where the p-parts of an integer sequence themselves count periodic points are studied. The Mersenne sequence provides one example, and the denominators of the Bernoulli numbers provide another. The methods give a dynamical interpretation of many classical congruences such as Euler-Fermat for matrices, and suggest the same for the classical Kummer congruences satisfied by the Bernoulli numbers.

Let X denote a set, and T : X → X a map. An element x ∈ X is a periodic point of period n ∈ ℕ if it is fixed under T^{n}, that is T^{n}(x) = x. Let Per_{n}(T) denote the set of points of period n under T. Following [13], call a sequence u = (u_{n})_{n≥1} of non-negative integers realizable if there is a set X and a map T : X → X such that u_{n} = | Per_{n}(T)|.

This subject is example-driven so we begin our account with several of these. Throughout, examples will be referenced as they appear in the Encyclopedia of Integer Sequences.

Example 1.1. (1) Let M_{n} = 2^{n}−1, n ≥ 1 denote the n-th term of the Mersenne sequence A000225. This sequence is of interest in number theory because it is conjectured to contain infinitely many prime terms, and in dynamics because it counts the periodic points in the simplest expanding dynamical system. Let

𝕊^{1} = {z ∈ ℂ | |z| = 1}

denote the complex unit circle. Then the map T : 𝕊^{1} → 𝕊^{1}, T (z) = z^{2}, has | Per_{n}(T)| = M_{n}.

(2) Let L_{n} denote the n-th term of the Lucas sequence A000204. Let X denote the set of all doubly-infinite strings of 0’s and 1’s in which every 0 is followed by a 1, and let T : X → X be the left shift defined by (T x)_{n} = x_{n+1}. Then | Per_{n}(T)| = L_{n}.

(3) The Lehmer-Pierce sequences (generalizing the Mersenne sequence; see [4]) also arise in counting periodic points. Let f(x) denote a monic, integral polynomial with degree d ≥ 1 and roots α_{1}, …, α_{d}. Define

Δ_{n}(f) = ∏_{i} |α_{i}^{n} − 1|,

which is non-zero for n ≥ 1 under the assumption that no α_{i} is a root of unity. When f(x) = x − 2, we obtain Δ_{n}(f) = M_{n}. Sequences of the form (Δ_{n}(f)) were studied by Pierce and Lehmer with a view to understanding the special form of their factors, in the hope of using them to produce large primes. One such, is sequence A001945 corresponding to f(x) = x^{3} − x − 1. In dynamics they arise as sequences of periodic points for toral endomorphisms: Let X = 𝕋^{d} denote the d-dimensional additive torus. The companion matrix A_{f} of f acts on X by multiplication mod 1, T (x) = A_{f}x mod 1. It requires a little thought to check that | Per_{n}(T)| = Δ_{n}(f) under the same ergodicity condition that no α_{i} is a root of unity (see [4]). Notice that the Lehmer-Pierce sequences are the absolute values of integer sequences which could have mixed signs.

The next two examples illuminate the same issue of signed sequences whose absolute value counts periodic points.

(4) The Jacobsthal-Lucas sequence A014551 R_{n} = |(−2)^{n} − 1| counts points of period n for the map z ↦ z^{−2} on 𝕊^{1}.

(5) The sequence S_{n} = |2^{n} + (−3)^{n}| counts periodic points in a certain continuous automorphism of a 1-dimensional solenoid, see [3] or [10].

(6) For a ≥ 1, the shift map T on {0, 1, …, a − 1}^{ℤ} has | Per_{n}(T)| = a^{n}.

(7) If B denotes a square matrix with non-negative integral entries then (trace(B^{n})) is a realizable sequence. To see this, let G_{B} be the labelled graph with adjacency matrix B and T_{B} the edge-shift on the set of labels of infinite paths on G_{B}. Then the number of points of period n for this system is trace(B^{n}) (see [11] for the details).

The sequences above are realizable by continuous maps of compact spaces; it turns out that any realizable sequence is in fact realizable by such a map.

It is natural to ask what is required of a sequence in order that it be realizable. For example, could the Fibonacci sequence A000045, the more illustrious cousin of the Lucas sequence, be realized in this way? The answer is no, and a simple proof will follow in Section 3. In fact a sequence of non-negative integers satisfying the Fibonacci recurrence is realizable if and only if it is a non-negative integer multiple of the Lucas sequence (see [13], [14], [15] and Theorem 2.1 below). However, we will see in Theorem 2.6 that in a precise sense, the Fibonacci sequence is semi-realizable.

2. Statements of Results

If u = (u_{n}) is any sequence of integers, then it is reasonable to ask if the sequence |u| = (|u_{n}|) of absolute values is realizable. For example, the sequence (1, −3, 4, −7, …) is a signed linear recurrence sequence whose absolute values are realizable. A signed sequence u will also be called realizable if |u| is realizable.

Theorem 2.1 recasts [14, Theorem 2.5], concerning realizable binary linear recurrence sequences, in a form that generalizes. The definitions are standard but they will be recalled later. Recall that the ℂ-space of all solutions of a binary recurrence relation has dimension 2. The realizable subspace is the subspace spanned by the realizable solutions. Thus, for the Fibonacci recurrence, the realizable subspace has dimension 1 and is spanned by the Lucas sequence.

Theorem 2.1. Let Δ denote the discriminant of the characteristic polynomial associated to a non-degenerate binary recurrence relation. Then the realizable subspace has

(1) dimension 0 if Δ < 0,

(2) dimension 1 if Δ = 0 or Δ > 0 and non-square,

(3) dimension 2 if Δ > 0 is a square.

Example 2.2. (cf. [14, Example 2.6(2)]) As an example of the third condition, consider the recurrence relation

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

which is satisfied by the Mersenne sequence. The recurrence sequences a2^{n} + b with a, b ∈ ℕ all satisfy (1) and are realizable — see Corollary 3.2.

Theorem 2.1 is proved in [14] using essentially quadratic methods — but it surely has a generalization to higher degree, characterizing the realizable subspace in terms of the factorization of the characteristic polynomial of the recurrence. The second theorem is a partial result in that direction, giving a restriction on the dimension of the realizable subspace under the assumption that the characteristic polynomial has a dominant root.

Theorem 2.3. Let f denote the characteristic polynomial of a non-degenerate linear recurrence sequence with integer coefficients. If f is separable, with ℓ irreducible factors and a dominant root then the dimension of the realizable subspace cannot exceed ℓ. If f(0) ≠ 0 then equality holds if either the dominant root is not less than the sum of the absolute values of the other roots or the dominant root is strictly greater than the sum of the absolute values of its conjugates.

It is not clear if there is an exact result but the deep result of Kim, Ormes and Roush [8] on the Spectral Conjecture of Boyle and Handelman [1] gives a checkable criterion for a given linear recurrence sequence to be realized by an irreducible subshift of finite type.

Example 2.4. Consider the sequences which satisfy the Tribonacci relation

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

The sequence A001644 satisfies (2) and is realizable, since it is the sequence (trace(A_{f}^{n})), where A_{f} is the companion matrix to f(x) = x^{3} − x^{2} − x − 1. Theorem 2.3 says that any realizable sequence which satisfies (2) is a multiple of this one.

Example 2.5. Suppose g denotes a polynomial with ℓ − 1 distinct irreducible factors (possibly repeated). For an integer K, consider the linear recurrence relation with characteristic polynomial

f(x) = (x − K)g(x).

For all sufficiently large K, f has ℓ distinct irreducible factors and the realizable subspace has dimension ℓ.

The third theorem consists of a triple of examples. Given a sequence u and a prime p, write [u_{n}]_{p} for the p-part of u_{n}. Notice that [u]_{p} is always non-negative. A sequence u is locally realizable at p if [u]_{p} is itself realizable, and is everywhere locally realizable if it is locally realizable at p for all primes p. If a sequence is everywhere locally realizable and non-negative then it is realizable by Corollary 3.2 below. Moss has shown [12] that the converse is true for any endomorphism of a locally nilpotent group.

Consider the Bernoulli numbers B, defined by the relation

\frac{t}{e^{t} − 1} = ∑_{n=0}^{∞} B_{n} \frac{t^{n}}{n!};

B_{n} ∈ ℚ for all n, and B_{n} = 0 for all odd n > 1.

Theorem 2.6. Any Lehmer–Pierce sequence is everywhere locally realizable, and hence realizable. The Fibonacci sequence is locally realizable at primes ≡ ±1 modulo 5. Let b_{n} denote the denominator of B_{2n} for n ≥ 1. Then b = (b_{n}) is everywhere locally realizable, and hence realizable.

The sequence b is A002445, a much-studied sequence. The maps in Theorem 2.6 are endomorphisms of groups. Theorem 2.6 and Lemma 3.1 suggest a dynamical interpretation of composite versions of the classical Kummer congruences; see Section 4 below.

3. Combinatorics of periodic points

As pointed out in [14, Example 2.2(1)], the Fibonacci sequence is not realizable. No map can have 1 fixed point and 2 points of period 3 — the image under the map of the non-fixed point of period 3 would have to be a distinct non-fixed point of period 3, and there are no others. More generally, for any prime p, the number of non-fixed points of period p must be divisible by p because their orbits occur in cycles of length p. From this kind of reasoning, the following characterization emerges (see [14, Lemma 2.1]).

Lemma 3.1. Let u be a sequence of non-negative integers, and let u ∗ μ denote the Dirichlet convolution of u with the Möbius function μ. Then u is realizable if and only if (u ∗ μ)_{n} ≡ 0 mod n and (u ∗ μ)_{n} ≥ 0 for all n ≥ 1.

Corollary 3.2. The sum and product of two realizable sequences are both realizable.

Proof. This may be seen either using elementary properties of the Dirichlet convolution or using the realizing maps: if u and v are realizable, then the Cartesian product of the realizing maps realizes (u_{n}v_{n}), while the disjoint union realizes (u_{n} + v_{n}). □

Notice that if n = p^{r}, for a prime p and r > 0 an integer, Lemma 3.1 requires that

u_{p^{r}} ≡ u_{p^{r−1}} mod p^{r}  (3)

for any realizable sequence u.

Corollary 3.3. Let a denote a positive integer and let p and r be as above. Then

a^{p^{r}} ≡ a^{p^{r−1}} mod p^{r}.

Proof. This is the statement of the Euler-Fermat Theorem; a dynamical proof applies (3) to Example 1.1(6). □

This kind of observation — that periodic points in full shifts give simple proofs of many elementary congruences — is folklore; indeed the paper [2] gives a rather complicated proof of Euler–Fermat using a dynamical system.

Lemma 3.1 does more with no additional effort. The following is a generalization of the Euler-Fermat Theorem for integral matrices which will be used in the proof of Theorem 2.1.

Corollary 3.4. Let A denote a square matrix with integer entries and let p and r be as above. Then

trace(A^{p^{r}}) ≡ trace(A^{p^{r−1}}) mod p^{r}.

Proof. It is sufficient to assume A has non-negative entries, since any matrix has such a representative mod p^{r}. The result follows at once from Example 1.1(7). □

We now state the consequences of Lemma 3.1 in their most general form for matrix traces.

Corollary 3.5. Let A denote a square matrix with integer entries and let A_{n} denote the sequence trace(A^{n}). Then for all n ≥ 1

∑_{d|n} A_{d}μ(n/d) ≡ 0 mod n.

4. Proofs

Before the proof of Theorem 2.1, we begin with some notation (for a lively account of the general properties of linear recurrence sequences, see [16]). Let u be a binary recurrence sequence. This means that u_{1} and u_{2} are given as initial values, with all subsequent terms defined by a recurrence relation

u_{n+2} = Bu_{n+1} − Cu_{n}.  (4)

The polynomial f(x) = x^{2} − Bx + C is the characteristic polynomial of the recurrence relation. Write

A_{f} = (\begin{matrix}0 & 1 \\ −C & B \end{matrix})

for the companion matrix of f. The zeros α_{1} and α_{2} of f, are the characteristic roots of the recurrence relation. The sequence is non-degenerate if α_{1}/α_{2} is not a root of unity. The discriminant of the recurrence relation is Δ = B^{2} − 4C. The general solution of the recurrence relation is u_{n} = (γ_{1} + γ_{2}n)α_{1}^{n} if Δ = 0, and u_{n} = γ_{1}α_{1}^{n} + γ_{2}α_{2}^{n} if Δ ≠ 0.

Proof of Theorem 2.1. Assume first that Δ = 0, and let p denote any prime which does not divide α_{1} or γ_{2}. Then the congruence (3) is violated at n = p unless γ_{2} = 0. In that case, |γ_{1}α_{1}^{n}| is realizable and the space this generates is 1-dimensional.

If Δ > 0 is a square, then the roots are rationals and, plainly, must be integers. We claim that for any integers γ_{1} and γ_{2}, the sequence |γ_{1}α_{1}^{n} + γ_{2}α_{2}^{n}| is realizable. In fact (up to multiplying and adding full shifts) this sequence counts the periodic points for an automorphism on a one-dimensional solenoid, see [4] or [10].

The two cases where Δ ≠ 0 is not a square are similar. Write α = s + t\sqrt{Δ}, with s, t ∈ ℚ, for one of the roots of f and let K = ℚ(α) denote the quadratic number field generated by α. Write T_{K|ℚ} : K → ℚ for the usual field trace. The general integral solution to the recurrence is u_{n} = T_{K|ℚ}((a + b\sqrt{Δ})α^{n}), where a and b are both integers or both half-odd integers. Write v_{n} = T_{K|ℚ}(aα^{n}) and w_{n} = T_{K|ℚ}(b\sqrt{Δ}α^{n}). Now v_{n} = a trace(A_{f}^{n}), where A_{f} denotes the companion matrix of f. Hence it satisfies v_{p} ≡ v_{1} mod p for all primes p by Corollary 3.4.

Let p denote any inert prime for K. The residue field is isomorphic to the field 𝔽_{p^{2}}. Moreover, the non-trivial field isomorphism restricts to the Frobenius at the finite field level. Reducing mod p gives the congruence

\sqrt{Δ}α^{p} − \sqrt{Δ}α ≡ \sqrt{Δ}α − \sqrt{Δ}α^{p} mod p.

Thus w_{p} ≡ −w_{1} mod p for all inert primes p. On the other hand, v_{p} ≡ v_{1} mod p for all inert primes p.

If |u_{n}| is realizable then |u_{p}| ≡ |u_{1}| mod p by (3). If u_{p} ≡ −u_{1} mod p for infinitely many primes p then v_{p} + w_{p} ≡ v_{1} − w_{1} ≡ −v_{1} − w_{1} mod p. We deduce that p|v_{1} for infinitely primes and hence v_{1} = 2as = 0. We cannot have s = 0 by the non-degeneracy, so a = 0. If u_{p} ≡ u_{1} mod p then, by a similar argument, we deduce that bt = 0. We cannot have t = 0 again, by the non-degeneracy so b = 0. This proves that when Δ ≠ 0 is not a square, the realizable subspace must have rank less than 2.

Suppose firstly that Δ > 0. We will prove that the rank is precisely 1. In this case, there is a dominant root. If this root is positive then all the terms of u_{n} are positive. If the dominant term is negative then the sequence of absolute values agrees with the sequence obtained by replacing α by −α and the dominant root is now positive. In the recurrence relation (4) C = N_{K|ℚ}(α), the field norm, and B = T_{K|ℚ}(α). We are assuming B > 0. If C < 0 then the sequence u_{n} = trace(A_{f}^{n}) is realizable using Example 1.1(7), because the matrix A_{f} has non-negative entries. If C > 0 the matrix A_{f} may be conjugated to a matrix with non-negative entries (this leaves the sequence of traces invariant). To see this, let E denote the matrix

E = (\begin{matrix}1 & 0 \\ k & 1 \end{matrix}) .

Then

E^{−1}A_{f}E = (\begin{matrix}k & 1 \\ Bk − k^{2} − C & B − k \end{matrix}) .

If B is even, take k = B/2. Then the lower entries in E^{−1}A_{f}E are (B^{2} − 4C)/4 = Δ/4 > 0 and B/2 > 0. If B is odd, take k = (B + 1)/2. Then the lower entries are (B^{2} − 1 − 4C)/4 = (Δ − 1)/4 ≥ 0 and (B − 1)/2 ≥ 0. In both cases we have conjugated A_{f} to a matrix with non-negative entries.

Finally, we must show that when Δ < 0, both sequences v_{n} and w_{n} are not realizable in absolute value. Assume a ≠ 0, and then note that v_{1} = 2as ≠ 0 by the non-degeneracy assumption. For all primes p we have v_{p} ≡ v_{1} by the remark above. Since the roots α_{1} and α_{2} are complex conjugates, |α_{1}| = |α_{2}|. Let β = \frac{1}{2π} arg(α_{1}/α_{2}); β is irrational by the non-degeneracy assumption. The sequence of fractional parts of pβ, with p running through the primes, is dense in (0, 1) (this was proved by Vinogradov [19]; see [18] for a modern treatment). It follows that there are infinitely many primes p for which v_{p}v_{1} < 0. Therefore, if |v_{n}| is realizable then it satisfies v_{p} ≡ v_{1} mod p and −v_{p} ≡ v_{1} mod p for infinitely many primes. We deduce that v_{1} = 0 which is a contradiction. With w_{n} we may argue in a similar way to obtain a contradiction to w_{1} ≠ 0. If |w_{n}| is realizable then Lemma 3.1 says |w_{p^{2}}| ≡ |w_{p}| ≡ |w_{1}| for all primes p. Arguing as before, w_{p^{2}} ≡ w_{1} for both split and inert primes. However, the sequence {p^{2}β}, p running over the primes, is dense in (0, 1). (Again, this is due to Vinogradov in [19] or see [5] for a modern treatment. The general case of {F (p)}, where F is a polynomial can be found in [7].) We deduce that w_{p^{2}}w_{1} < 0 for infinitely many primes. This means w_{p^{2}} ≡ w_{1} mod p and w_{p^{2}} ≡ −w_{1} mod p infinitely often. This forces w_{1} = 0 — a contradiction.

Proof of Theorem 2.3. Let d denote the degree of f. In the first place we assume ℓ = 1, thus f is irreducible. The irreducibility of f implies that the rational solutions of the recurrence are given by u_{n} = T_{K|ℚ}(γα^{n}), where K = ℚ(α), and γ ∈ K. We write γ_{i}, α_{i}, i = 1, …, d for the algebraic conjugates of γ and α. The dominant root hypothesis says, after re-labelling, |α_{1}| > |α_{i}| for i = 2, …, d. We will show that if u is realizable then γ ∈ ℚ.

Let p denote any inert prime. If p is sufficiently large, the dominant root hypothesis guarantees that u_{p}, …, u_{p^{d}} will all have the same sign. Using Lemma 3.1 several times, we deduce that

u_{p} ≡ u_{p^{2}} ≡ ⋯ ≡ u_{p^{d}} ≡ ±u_{1} mod p.

Therefore u_{p} + ⋯ + u_{p^{d}} ≡ ±du_{1} mod p, the sign depending upon the sign of u_{1}. However,

u_{p} + ⋯ + u_{p^{d}} ≡ T_{K|ℚ}(γ) T_{K|ℚ}(α) mod p.

We deduce a fundamental congruence

T_{K|ℚ}(γ) T_{K|ℚ}(α) ≡ ±d T_{K|ℚ}(γα) mod p.

Since this holds for infinitely many primes p, the congruence is actually an equality,

T_{K|ℚ}(γ) T_{K|ℚ}(α) = ±d T_{K|ℚ}(γα).  (5)

The next step comes with the observation that if u_{n} is realizable then u_{rn} is realizable for every r ≥ 1. Thus equation (5) now reads

T_{K|ℚ}(γ) T_{K|ℚ}(α^{r}) = ±d T_{K|ℚ}(γα^{r}).  (6)

Dividing equation (6) by α_{1}^{r} and letting r → ∞ we obtain the equation

T_{K|ℚ}(γ) = ±dγ_{1}.

This means that one conjugate of γ is rational and hence γ is rational.

The end of the proof in the case ℓ = 1 can be re-worked in a way that makes it more amenable to generalization. The trace is a ℚ-linear map on K so its kernel has rank d − 1. Thus every element γ of K can be written q + γ_{0} where q ∈ ℚ and T_{K|ℚ}(γ_{0}) = 0. Noting that T_{K|ℚ}(q) = dq and cancelling d, this simply means equation (6) can be written

u_{r} = ±q T_{K|ℚ}(α^{r}),

for all r ≥ 1 confirming that the realizable subspace has rank ≤ 1.

The general case is similar. Each of the irreducible factors of f generates a number field K_{j}, j = 1, …, ℓ of degree d_{j} = [K_{j} : ℚ]. The solutions of the recurrence look like

u_{n} = ∑_{j=1}^{ℓ} T_{K_{j}|ℚ}(γ_{j}α_{j}^{n}),

where each γ_{j} ∈ K_{j}. Let L denote the compositum of the K_{j}. Using the inert primes of L and noting that each is inert in each K_{j}, we deduce an equation

∑_{j=1}^{ℓ} \frac{d}{d_{j}} T_{K_{j}|ℚ}(γ_{j}) T_{K_{j}|ℚ}(α_{j}) = ±d ∑_{j=1}^{ℓ} T_{K_{j}|ℚ}(γ_{j}α_{j}).  (7)

As before, replace α_{j} by α_{j}^{r}, and cancel d so that

u_{r} = ± ∑_{j=1}^{ℓ} \frac{1}{d_{j}} T_{K_{j}|ℚ}(γ_{j}) T_{K_{j}|ℚ}(α_{j}^{r})

Each γ_{j} can be written γ_{j} = q_{j} + γ_{0j}, where T_{K_{j}|ℚ}(γ_{0j}) = 0. Noting that T_{K_{j}|ℚ}(q_{j}) = d_{j}q_{j} we deduce that

u_{r} = ± ∑_{j=1}^{ℓ} q_{j} T_{K_{j}|ℚ}(α_{j}^{r})

which proves that the realizable subspace has rank ≤ ℓ.

Finally, show that equality holds in the two cases stated. Write u_{n}^{(j)} = T_{K_{j}|ℚ}(α_{j}^{n}), which is not identically zero because no α_{j} = 0. Each sequence u_{n}^{(j)} satisfies the congruence part of Lemma 3.1 and hence any ℤ-linear combination also satisfies the congruence. This is because u_{n}^{(j)} is identical to trace(A_{f_{j}}^{n}), where A_{f_{j}} denotes the companion matrix for f_{j} - hence we can invoke Corollary 3.5. To obtain l linearly independent realizable sequences, suppose α_{1} is the dominant root and take u_{n}^{(1)} together with u_{n}^{(1)} + u_{n}^{(j)} for j = 2, …, l. The non-negativity part of Lemma 3.1 follows from the condition on the dominant root. For the second case, a similar argument shows that for sufficiently large M > 0, the independent sequences u_{n}^{(1)} and Mu_{n}^{(1)} + u_{n}^{(j)} are realizable.

Proof of Theorem 2.6. It is sufficient to construct local maps T_{p} : X_{p} → X_{p} for each prime p. Then Corollary 3.2 guarantees a global realization by defining

T = ∏_{p} T_{p} on X = ∏_{p} X_{p}.

If the maps T_{p} are group endomorphisms then the map T is a group endomorphism.

As motivation, consider the Mersenne sequence. For each prime p, let 𝕌_{p} ⊂ 𝕊^{1} denote the group of all pth power roots of unity. Define the local endomorphism S_{p} : x ↦ x^{2} on 𝕌_{p}. Then | Per_{n}(S_{p})| = [2^{n} − 1]_{p} so S_{p} gives a local realization of the Mersenne sequence. Using the same method of proof, we can easily verify the claim about the Fibonacci sequence. Let F_{n} denote the n-th term and let X denote the group of all p-th power roots of 1. This is naturally a ℤ_{p}-module. Let u denote the golden-mean, thought of as lying in ℤ_{p} by the congruence property on p. Then the map x ↦ x^{−u^{2}} has precisely [F_{n}]_{p} points of period p.

An alternative proof in the Mersenne case uses the S-integer dynamical systems from [3]: for each prime p, define T_{p} to be the automorphism dual to x ↦ 2x on ℤ_{(p)} (the localization at p). Then by [3],

| Per_{n}(T_{p})| = ∏_{q≤∞;q≠p} |2^{n} − 1|_{q} = [2^{n} − 1]_{p}

by the product formula. This approach gives a convenient proof for Lehmer-Pierce sequences in general. We may assume that the polynomial f is irreducible; let K = ℚ(ξ) for some zero of f. Then for each prime p, let S comprise all places of K expect those lying above p, and let T_{p} be the S-integer map dual to x ↦ ξx on the ring of S-integers in K. Then by the product formula

| Per_{n}(T_{p})| = ( ∏_{v|p} |ξ^{n} − 1|_{v})^{−1} = [Δ_{n}(f)]_{p}

as required.

For the Bernoulli denominators, define X_{p} = 𝔽_{p} = ℤ/pℤ. For p = 2 define T_{p} to be the identity. For p > 2, let g_{p} denote an element of (multiplicative) order (p − 1)/2. Define T_{p} : X_{p} → X_{p} to be the endomorphism T_{p}(x) = g_{p}x mod p. Plainly |Per_{n}(T_{p})| = p if and only if p − 1|2n; for all other n, |Per_{n}(T_{p})| = 1. The Clausen von Staudt Theorem ([6], [9]) states that

B_{2n} + ∑ \frac{1}{p} ∈ ℤ,

where the sum ranges over primes p for which p − 1|2n. Thus |Per_{n}(T_{p})| = max{1, |B_{2n}|_{p}} and this shows the local realizability of the Bernoulli denominators.

5. Epilogue

A result similar to the one in Theorem 2.6 for the Fibonacci sequence can be proved for any binary linear recurrence sequence, using the primes which split in the corresponding quadratic field.

Using the same ideas as in the proof of Theorem 2.6 one can prove that the sequence A006953, the denominators of B_{2n}/2n, is everywhere locally realizable. A much more subtle result, due to Moss [12], is that the sequence A001067, the numerators of B_{2n}/2n, is a realizable sequence that is not locally realizable exactly at the irregular primes A000928. Taking these remarks together with n = p^{r} in Lemma 3.1, suggests a dynamical interpretation of the Kummer congruences. These are stated now, for a proof see [9].

Theorem 5.1. If p denotes a prime and p − 1 does not divide n then n ≡ n′ mod (p − 1)p^{r} implies

(1 − p^{n−1})\frac{B_{n}}{n} ≡ (1 − p^{n′−1})\frac{B_{n′}}{n′} mod p^{r+1}.

Finally, experimental evidence suggests the sequence A006863, the denominators of B_{2n}/4n forms a realizable sequence that is not locally realizable at the primes 2, 3, 5, 7, 11, 13 but seems to be locally realizable for all large primes.

6. Acknowledgments

The second author acknowledges the support of EPSRC visiting fellowship award GR/R70200. The third author acknowledges the support of EPSRC postgraduate award 96001638.

References

[1] M. Boyle and D. Handelman. The spectra of nonnegative matrices via symbolic dynamics. Ann. of Math. (2), 133, 249–316 (1991); MR 92d:58057.

[2] Humberton Carillo Calvet and José Ramón Guzmán. A dynamical systems proof of Euler’s generalization of the little theorem of Fermat. Aportaciones Mat. Comun. , 25, 199–202, 1999. XXXI National Congress of the Mexican Mathematical Society; MR 2001i:11005.

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

[4] Graham Everest and Thomas Ward. Heights of polynomials and entropy in algebraic dynamics, Springer-Verlag London Ltd., London, 1999; MR 2000e:11087.

[5] A. Ghosh. The distribution of αp^{2} modulo one Proc. London Math. Soc. (3) 42, 225-269 (1981); MR 82j:10067.

[6] 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; MR 81i:10002.

[7] G. Harman. Trigonometric sums over primes I Mathematika, 28, 249-254 (1981); MR 83j:10045.

[8] Ki Hang Kim, Nicholas S. Ormes and Fred W. Roush. The spectra of nonnegative integer matrices via formal power series. J. Amer. Math. Soc., 13, 773–806 (2000); MR 2001g:15013.

[9] Neal Koblitz. p-adic Numbers, p-adic Analysis, and Zeta-Functions. Springer-Verlag, New York, 1977; MR 57#5964.

[10] D. A. Lind and T. Ward. Automorphisms of solenoids and p-adic entropy. Ergodic Theory Dynamical Systems, 8(3), 411–419, 1988; MR 90a:28031.

[11] Douglas Lind and Brian Marcus. An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, Cambridge, 1995; MR 97a:58050.

[12] Patrick Moss The Arithmetic of Realizable Sequences PhD Thesis, University of East Anglia, 2003.

[13] Y. Puri. Arithmetic of Numbers of Periodic Points. PhD. thesis, Univ. East Anglia, (2001), www.mth.uea.ac.uk/admissions/graduate/phds.html

[14] Y. Puri and T. Ward. Arithmetic and growth of periodic orbits Journal of Integer Sequences, 4, 01.2.1 (2001); MR 2002i:11026.

[15] Y. Puri and T. Ward. A dynamical property unique to the Lucas sequence Fibonnaci Quarterly, 39(5), 398-402 (2001).

[16] A. J. van der Poorten. Some facts that should be better known, especially about rational functions. Number theory and applications (Banff, AB, 1988), 497–528 (1989). Kluwer Acad. Publ., Dordrecht; MR 92k:11011.

[17] N. J. A. Sloane The On-Line Encyclopedia of Integer Sequences; MR 95b:05001.

[18] R. Vaughan. On the distribution of pα modulo one Mathematika, 24, 135-141 (1977); MR 57#12423.

[19] I. M. Vinogradov. A new estimation of a trigonometric sum involving primes Bull. Acad. Sc. URSS Ser. Math., 2, 1–13 (1938).

2000 Mathematics Subject Classification: 11G07, 37B40 . Keywords: periodic points, dynamical systems, linear recurrences, Bernoulli numbers, realizable sequences

(Concerned with sequences \underline{A000225}, \underline{A000204}, \underline{A001945}, \underline{A000045}, \underline{A001644}, \underline{A002445}, \underline{A006953}, \underline{A001067}, \underline{A000928}.)

Received October 18, 2002; revised version received November 12, 2002. Published in Journal of Integer Sequences November 13, 2002.

Return to Journal of Integer Sequences home page.