On (Almost) Realizable Subsequences of Linearly Recurrent Sequences

Florian Luca School of Mathematics

University of the Witwatersrand 1 Jan Smuts Avenue Braamfontein 2050

Johannesburg South Africa

and

Max Planck Institute for Software Systems

Saarland Information Campus E1 5

66123 Saarbrücken

Germany

and

Centro de Ciencias Matemáticas UNAM Morelia México

florian.luca@wits.ac.za

Thomas Ward

Department of Mathematical Sciences Durham University Durham DH1 3LE

England

tbward@gmail.com

Abstract

We show that if (u_{n})_{n≥1} is a simple linearly recurrent sequence of integers whose minimal recurrence of order k involves only positive coefficients that has positive initial terms, then (Mu_{n^{s}})_{n≥1} is the sequence of periodic point counts for some map for a suitable positive integer M and s any sufficiently large multiple of k!. This extends a result of Moss and Ward who proved the same result for the Fibonacci sequence.

1 Introduction

A sequence of nonnegative integers (a_{n})_{n≥1} is called realizable if there is some set X and a map T: X → X such that

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

and is called almost realizable if it is realizable after multiplication by a positive integer.

A simple example of realizability is the shift map T: (x_{n})_{n∈ℤ} ↦ (x_{n+1})_{n∈ℤ} on the golden mean shift space

X = {x = (x_{n})_{n∈ℤ} ∈ {0, 1}^{ℤ} | (x_{k}, x_{k+1}) ≠ (1, 1) for all k ∈ ℤ}.

This has

Fix(T^{n}) = #\{x ∈ X | T^{n}(x) = x\} = Trace (\begin{matrix}1 & 1 \\ 1 & 0 \end{matrix})^{n} = L_{n}  (1)

where (L_{n})_{n≥1} = (1, 3, 4, 7, …) is the Lucas companion \underline{A000204} of the Fibonacci sequence; we refer to Puri and Ward [11] for more on this example.

A simple example of almost realizability is given by \underline{A000079}, namely the sequence

(2^{n−1})_{n≥1} = (1, 2, 4, …)

of powers of 2. Clearly this is not realizable, since a map T witnessing this would have the property that Fix(T) = 1, and hence must have Fix(T^{2}) odd. However the shift map as above on the full 2-shift X = {0, 1}^{ℤ} has Fix(T^{n}) = 2^{n} for all n ≥ 1, showing that the sequence becomes realizable after multiplication by 2. We refer to Moss and Ward [8] for this and other examples, and the references therein for background on this concept.

Our purpose here is to show that for a large class of linear recurrence sequences the subsequence obtained by sampling along a sufficiently large power of the index is almost realizable.

2 Realizable subsequences

Realizable sequences can be characterized in algebraic terms as follows. The sequence (a_{n})_{n≥1} of non-negative integers is realizable if and only if it satisfies the following two conditions:

(D) ∑_{d|n} μ(n/d)a_{d} ≡ 0 (mod n) for all n ∈ ℕ, and

(S) ∑_{d|n} μ(n/d)a_{d} ≥ 0 for all n ∈ ℕ.

Here μ denotes the classical Möbius function. We call (D) the Dold condition and (S) the sign condition. The equivalence is clear, because the sum arising in (D) and in (S) is the number of points that lie on a closed orbit of minimal length n under iteration of a map that witnesses realizability of (a_{n})_{n≥1}.

We write (F_{n})_{n≥1} for \underline{A000045}, namely the Fibonacci sequence (1, 1, 2, …). Moss [7] showed that (5F_{n^{2}})_{n≥1}, the sequence \underline{A054783} multiplied by 5, is realizable. Moss and Ward [8] extended this to show that (5F_{n^{2k}})_{n≥1}, is realizable for k ≥ 1 while (MF_{n^{2k+1}}) is not realizable for any choice of M = M_{k} ≥ 1 for any k ≥ 0. These arguments use congruence properties specific to the Fibonacci sequence, which makes one wonder to what extent such a result can be extended to other linearly recurrent sequences.

Here we generalize the above result to simple linearly recurrent sequences satisfying some positivity conditions. Our result is quite general, and its proof uses elementary algebraic number theory rather than congruences specific to a given sequence.

Let (u_{n})_{n≥1} be a linearly recurrent sequence of integers of order k. That is, it satisfies a recurrence relation of the form

u_{n+k} = a_{1}u_{n+k−1} + ⋯ + a_{k}u_{n}

for all n ≥ 1, where a_{1}, …, a_{k}, u_{1}, …, u_{k} are all integers (this is a harmless assumption for integer linear recurrences by Fatou’s lemma [2, p. 369]). We assume that the recurrence is minimal, so in particular a_{k} ≠ 0. We ask if there is a monomial f ∈ ℤ[X] and a positive integer M with the property that (Mu_{f(n)})_{n≥1} satisfies (D) and (S). Let

F (X) = X^{k} − a_{1}X^{k−1} − ⋯ − a_{k}

be the minimal polynomial of the sequence (u_{n})_{n≥1}. For background and relevant properties of linearly recurrent sequences the reader is invited to consult the monograph of Everest et al. [1]. Let 𝕂 be the splitting field of F and O_{𝕂} be its ring of integers. Let Δ(𝕂) be the discriminant of 𝕂 and let Δ(F) be the discriminant of F. Let G be the Galois group of 𝕂 over ℚ, let e(G) be the exponent of G, and let N be the order of G.

Theorem 1. Assume that F has only simple zeros.

(i) The sequence (Mu_{n^{s}})_{n≥1} satisfies (D) if M is a positive integer which is a multiple of lcm(Δ(𝕂), Δ(F)) and s ≥ N is a multiple of e(G).

(ii) Assume in addition that a_{i} ≥ 0 for i = 1, …, k and a_{k} ≠ 0, that

(a_{1}, …, a_{k}) ≠ (0, 0, …, 1),

and that u_{i} ≥ 1 for all i ∈ {1, 2, …, k}. Then the sequence (Mu_{n^{s}})_{n≥1} satisfies (S) whenever s = ℓe(G) where ℓ ≥ ℓ_{0} is a sufficiently large number which can be computed in terms of the sequence (u_{n})_{n≥1}.

The somewhat strange condition (i) can be explained as follows. The condition Δ(F) | M is needed to ensure that the summands involved in the Binet formula for the general term of Mu_{n} are algebraic integers. On the other hand, the additional conditions that Δ(𝕂) | M together with the conditions on s are sufficient to ensure that the Dold condition (D) is satisfied. In particular, if F is irreducible, then Δ(𝕂) | Δ(F), so it suffices that M is a multiple of Δ(F). This is not the case for reducible polynomials as the example

F (X) = (X^{2} − 2)(X^{3} − 5)

shows. In this case 𝕂 = ℚ(\sqrt{2}, \sqrt[3]{5}, \sqrt{−3}) has Δ(F) = −2^{3} · 3^{3} · 5^{2} · 17^{2}, which is not a multiple of Δ(𝕂) = 2^{18}3^{14}5^{8}. Remark 2.

(a) We have to exclude a periodic sequence of period k ≥ 2 and minimal polynomial X^{k}−1, since for it the theorem is not true in general. Indeed, consider the simplest case when k is prime. Then condition (S) requires that u_{k^{s}} − u_{1} ≥ 0. On the other hand, since k^{s} ≡ k (mod k), we must have u_{k} ≥ u_{1}. It follows that u_{1}, …, u_{k} cannot be chosen to be arbitrary positive integers.

(b) We require the minimal polynomial to only have simple roots, for otherwise (D) may be false. For example, the sequence defined by u_{n} = n for all n ≥ 1 satisfies the linear recurrence u_{n+2} = 2u_{n+1} − u_{n} with minimal polynomial (X − 1)^{2}. Then condition (D) for (Mu_{n^{s}}) implies that for a prime p we must have p | M(p^{s}−1), and for given positive integers M and s this can only hold for the finitely many primes p dividing M. Hence, for the above sequence, the Dold quotients

\frac{1}{n} ∑_{d|n} μ(n/d)a_{d}

for n ≥ 1 are rational numbers whose denominators are divisible by arbitrarily large primes. Similar arguments are used by Puri and Ward [10, Lem. 2.4] to show that if (f(n))_{n≥1} is realizable with f ∈ ℤ[X], then f is a constant.

(c) A different (arguably more natural) question is to ask when a linear recurrence sequence itself satisfies (D) without multiplication by a factor or passing to a subsequence. Minton [6] showed that—up to a finite multiplying factor—this is possible if and only if the sequence is a linear combination of traces of powers of algebraic numbers. From this perspective (1) is a manifestation of the fact that the only linearly recurrent sequences satisfying the Fibonacci recurrence u_{n+2} = u_{n+1} + u_{n} for n ≥ 1 which have this property must have u_{2} = 3u_{1} (and hence must be multiples of the Lucas sequence), a special case shown earlier by Puri and Ward [11] using congruences specific to the Fibonacci sequence.

Returning to the Fibonacci sequence where this phenomena was first observed, the sequence (F_{n})_{n≥1} has k = 2, a_{1} = a_{2} = 1, F_{1} = F_{2} = 1 > 0, and minimal polynomial F (X) = X^{2} − X − 1. Further, 𝕂 = ℚ[\sqrt{5}]. Thus, Δ(F) = Δ(𝕂) = 5 and G = ℤ/2ℤ so e(G) = N = 2. Thus, s = 2 satisfies that s is a multiple of e(G) and s ≥ N. We shall justify the claim that in this case we can take ℓ_{0} = 1, recovering the result of Moss and Ward [8] precisely. In fact, we prove it in a more general setting. Let (F_{n}^{(k)})_{n≥−(k−2)} be the kgeneralized Fibonacci sequence satisfying the recurrence relation F_{n+k}^{(k)} = F_{n+k−1}^{(k)} + ⋯ + F_{n}^{(k)} for n ≥ 2 − k with initial values F_{i}^{(k)} = 0 for i = 2 − k, 3 − k, …, −1, 0 and F_{1}^{(k)} = 1. Wolfram [12] conjectured that G = S_{k} is the full symmetric group on k letters, and this is known to be so when k is even, when k is small, or when k is prime. These claims are shown in work of Martin [4], for example. We therefore take N_{k} := k!; this is a multiple of e(G) and at least as large as N.

Theorem 3. For k ≥ 2 we can take s = N_{k}ℓ for any ℓ ≥ 1 for the k-generalized Fibonacci sequence (F_{n}^{(k)})_{n≥1−(k−2)}.

Moss and Ward [8] propose the following conjecture at the end of their paper.

Conjecture 4. Let P, Q ∈ ℤ and let u_{n+2} = P u_{n+1} − Qu_{n} for n ≥ 1, with initial conditions u_{0} = 0, u_{1} = 1. Then ((P^{2} − 4Q)u_{n^{2}})_{n≥1} satisfies (D).

This almost follows from Theorem 1, except that there are some additional hypotheses like the fact that the recurrence must be of minimal order k = 2 and that (P, Q) ≠ (0, −1), in order to apply the theorem. We therefore supply a proof of the following result.

Theorem 5. Conjecture 4 holds.

3 Proofs of theorems

Proof of Theorem 1. To start with, let

F (X) = ∏_{i=1}^{k}(X − λ_{i}),

so that we have the (generalized) Binet formula

u_{n} = ∑_{i=1}^{k} c_{i}λ_{i}^{n−1}

for all n ≥ 1 for coefficients c_{1}, …, c_{k} determined from u_{1}, …, u_{k} by solving a linear system of k equations in k unknowns whose matrix is Vandermonde on λ_{1}, …, λ_{k}. We write 𝕂 := ℚ(λ_{1}, …, λ_{k}). Then c_{1}, …, c_{k} are algebraic numbers in 𝕂 having the Vandermonde determinant \sqrt{Δ(F)} (for a certain determination of the square root) as a common denominator in the sense that \sqrt{Δ(F)}c_{i} is an algebraic integer for each i = 1, …, k. Note that Mc_{i} is a multiple of the algebraic integer \sqrt{Δ(𝕂)}, which is an algebraic integer in O_{𝕂}.

We next turn to the Dold condition. We say that a sequence of algebraic integers (v_{n})_{n≥1} satisfies the algebraic Dold condition if (D) is satisfied as algebraic integers. That is, if

\frac{1}{n} ∑_{d|n} μ(n/d)v_{d}

is an algebraic integer for all n ≥ 1. Our strategy is to find s such that (\sqrt{Δ(𝕂)}λ_{i}^{n^{s}−1})_{n≥1} satisfies the algebraic Dold condition for i = 1, …, k. Since linear combinations with algebraic integer coefficients of sequences which satisfy the algebraic Dold condition also satisfy the algebraic Dold condition, this allows us to deduce that

M \frac{\sqrt{Δ(𝕂)}}{n} ∑_{d|n} μ(n/d)u_{d^{s}} = M ∑_{i=1}^{k} c_{i} \frac{\sqrt{Δ(𝕂)}}{n} ∑_{d|n} μ(n/d)λ_{i}^{d^{s}−1}

is both a rational number and an algebraic integer, so an integer, verifying (D). Fix λ := λ_{i} for some i = 1, …, k. We need to find out when

\frac{\sqrt{Δ(𝕂)}}{n} ∑_{d|n} μ(n/d)λ^{d^{s}−1} = \frac{\sqrt{Δ(𝕂)}}{n} ∑_{d|n} μ(d)λ^{(n/d)^{s}−1}  (2)

is an algebraic integer in O_{𝕂} for all n ≥ 1. We write m := ∏_{p|n} p = rad(n) for the radical of n. Changing the order of summation to complementary divisors as shown and restricting to squarefree numbers in the summation on the right-hand side (as the Möbius function vanishes on all other terms), the numerator in (2) is

S := \sqrt{Δ(𝕂)} ∑_{d|m} μ(d)λ^{(n/d)^{s}−1}.

Clearly S is an algebraic integer, so we may assume that n (and hence m) exceeds 1. Let p be a prime divisor of n and let w be the exact exponent of p in n, written p^{w}∥n. Writing as usual ω(n) for the number of distinct prime divisors of n, m has 2^{ω(n)} divisors, half of which are multiples of p and half of which are not. Thus the above sum can be grouped into 2^{ω(n)−1} pairs indexed (d, p), where d is a divisor of \frac{m}{p}, giving

S = \sqrt{Δ(𝕂)} ∑_{d| \frac{m}{p}} (μ(d)λ^{(n/d)^{s}−1} + μ(pd)λ^{(n/(dp))^{s}−1})

= \sqrt{Δ(𝕂)} ∑_{d| \frac{m}{p}} ±λ^{(n/(pd))^{s}−1} (λ^{(n/pd)^{s}(p^{s}−1)} − 1) .

Thus, it is sufficient to show that if p^{w}∥n, then \frac{S}{p^{w}} is an algebraic integer. We let π be a prime ideal divisor of N in 𝕂 with π^{e}∥p and N_{𝕂/ℚ}(π) = p^{f}. We put

A_{d} := λ^{(n/dp)^{s}}

and

B_{d} := λ^{(n/pd)^{s}(p^{s}−1)} − 1,

and observe that our aim is to find a condition for s divisible by e(G) such that one would have

ν_{π}(\sqrt{Δ(𝕂)}A_{d}B_{d}) ≥ ew.

Here, ν_{π}(α) is the exponent of the prime ideal π in the factorization of αO_{𝕂}. Observe that the different theorem implies that

ν_{π}(Δ(𝕂)) ≥ fe(e − 1) ≥ e(e − 1).

Consider first the case π | λ. In this case ν_{π}(B_{d}) = 0 and

ν_{π}(A_{d}) ≥ (\frac{n}{pd})^{s} ≥ p^{s(w−1)} ≥ 2^{s(w−1)}.

We need to check that

2^{s(w−1)} + e(e − 1)/2 ≥ ew.

This is clear when w = 1, since then the inequality to be proved becomes

1 + e(e − 1)/2 ≥ e

which holds for all e ≥ 1. This is also clear when e = 1 since in that case it is implied by 2^{s(w−1)} ≥ 2^{w−1} ≥ w. Finally, if e ≥ 2, w ≥ 2, then s ≥ N ≥ e ≥ 2, so sw ≥ 4. Since w − 1 ≥ w/2, it suffices to show that 2^{sw/2} ≥ sw, which is equivalent to 2^{sw} ≥ (sw)^{2}, which holds since sw ≥ 4.

We next consider the case π ∤ λ. In this case, ν_{π}(A_{d}) = 0. Write (n/pd)^{s} = αp^{s(w−1)}, and p^{s} − 1 = β(p^{f} − 1), where π ∤ αβ. This last formula holds since f | e(G) | s. The analogue of Euler’s theorem for number fields implies

λ^{p^{f} −1} ≡ 1 (mod π).  (3)

By induction on j ≥ 0, we prove that

λ^{p^{j}(p^{f} −1)} ≡ 1 (mod π^{j+1}).  (4)

Indeed, the case j = 0 is just (3). Assuming congruence (4) is satisfied for j ≥ 0, we write

λ^{p^{j}(p^{f} −1)} = 1 + γ

for some γ ∈ π^{j+1} and raise it to power p to get

λ^{p^{j+1}(p^{f} −1)} = (1 + γ)^{p}

= 1 + ∑_{k=1}^{p−1} \binom{p}{k}γ^{k} + γ^{p}

≡ 1 (mod πγ) ≡ 1 (mod π^{j+2}),

proving the induction step. Evaluating this at j = s(w − 1), we get

λ^{p^{s(w−1)}(p^{f} −1)} ≡ 1 (mod π^{s(w−1)+1}).

Raising the above congruence to the power αβ, we deduce that

ν_{π}(B_{d}) ≥ s(w − 1) + 1.

So, it suffices to verify that

s(w − 1) + 1 + e(e − 1)/2 ≥ ew.

This is clear if w = 1 since then the left–hand side is 1 + e(e − 1)/2 ≥ e. It is also clear if e = 1, since then the left–hand side is s(w − 1) + 1 ≥ (w − 1) + 1 = w. Thus, we assume that e ≥ 2 and w ≥ 2. Since 𝕂 is Galois, we have that e | N and s ≥ N. If s ≥ 2e, then it suffices to show that

2e(w − 1) + 1 ≥ ew.

This is equivalent to ew − 2e + 1 ≥ 0, which holds since w ≥ 2. Finally, if 2e > s ≥ N, we have that e > N/2 and e is a divisor of N so, in fact s = e = N. So, we need to show that

N(w − 1) + 1 + N(N − 1)/2 ≥ Nw,

which is equivalent to 1 + N(N − 1)/2 ≥ N, which obviously holds for any N ≥ 2 (note that N ≥ 2 since we are in the case e ≥ 2).

We still need to deal with the sign condition (S), for which we use the following observation from Puri’s thesis [9]: It is sufficient to show that u_{(2n)^{s}} ≥ nu_{n^{s}} for all n ≥ 1. To see this, let λ be a real root larger than 1 of F (X) = 0. This exists by the intermediate value theorem, since the hypotheses on the coefficients a_{1}, …, a_{k} show that F (1) < 0, and F (x) → ∞ as x → ∞. Note that u_{n} ≥ λ^{n−k} always holds, again by the hypotheses on the coefficients. Indeed, it holds for n = 1, …, j because in this range u_{j} ≥ 1 ≥ λ^{j−k}, and so it holds for all n ≥ 1 by induction since a_{i} ≥ 0 for i = 1, …, k. Moreover, u_{n} ≤ λ^{n+n_{0}} for

n_{0} ≥ log max{u_{1}, …, u_{k}}/ log λ.

Again this inequality holds for n = 1, …, k, so it will hold for all n ≥ 1 by induction. Armed with these estimates, we now need to show that

λ^{(2n)^{s}−k} ≥ nλ^{n^{s}+n_{0}}

or, equivalently, that

n^{s}(2^{s} − 1) ≥ k + n_{0} + \frac{log n}{log λ}.  (5)

To see this, first let n_{1} ≥ 2(n_{0} + k) satisfy \frac{log n}{log λ} ≤ \frac{n}{2} for n ≥ n_{1}. Then for n ≥ n_{1} we have k + n_{0} ≤ \frac{n_{1}}{2} ≤ \frac{n}{2}, so the right-hand side of (5) is at most n. It follows that (5) holds, since n(2^{s} − 1) ≥ n is clear. For 1 ≤ n ≤ n_{1} the right-hand side is at most n_{0} + k + \frac{log n_{1}}{log λ} and the left-hand side is at least 2^{s} − 1 ≥ 2^{e(G)ℓ} − 1 and this is larger than n_{0} + k + \frac{log n_{1}}{log λ} once ℓ ≥ ℓ_{0}. Thus in all cases if s is a sufficiently large multiple of e(G), then the sign condition (S) holds.

Proof of Theorem 3. For the particular case of the k-generalized Fibonacci sequence, it is well-known that the associated minimal polynomial

F^{(k)}(X) = X^{k} − X^{k−1} − ⋯ − 1

has simple zeros by work of Miles [5], and that the largest real zero λ^{(k)} is increasing in k ≥ 2 and has λ^{(k)} → 2 as k → ∞. In particular, writing

λ = λ^{(k)} ≥ λ^{(2)} = \frac{1 + \sqrt{5}}{2}

we have F_{k}^{(k)} < 2^{k} < λ^{2k}, so we can take n_{0} = 2k in the notation of the sign condition step. Thus the condition is that n_{1} ≥ 2(n_{0} + k) = 6k must be such that \frac{log n}{log λ} ≤ \frac{n}{2} for n ≥ n_{1}, which is a consequence of 6 log n ≤ n, which certainly holds for n ≥ 10k ≥ 20. So we are able to take n_{1} = 10k. Consequently, for n ≤ n_{1}, the right-hand side in (5) is at most 10k and the left-hand side is at least n^{s}(2^{s} − 1) ≥ n^{N_{k}}(2^{N_{k}} − 1) ≥ 10k for all n ≥ 1 and k ≥ 3 where N_{k} = k!. For k = 2, the above inequality fails for n = 1, 2, but in these cases F_{(2n)^{2}} ≥ F_{4} = 3 > 2F_{2} holds anyway. Hence, we can take ℓ_{0} = 1 for any k ≥ 2.

Proof of Theorem 5. First consider the case Q = 0. In this degenerate case we may take two approaches (for non-negative P at any rate), and we include both to illustrate the two points of view. If P = 0 then the only realizable sequence is the zero sequence, so we assume that P ≥ 1.

Arithmetic proof: We have u_{n} = P^{n−1}, so c_{1} = 1/P in Binet’s formula and λ = P. Going through the proof of Theorem 1, we see that we need P | M to deal with the denominator of c_{1}. Next, in case p does not divide P, we are in the case of π ∤ λ, and then p^{w} | S whenever p^{w} | n. In the case of π | λ above, we have that if p | P, then e = N = 1. We saw in the proof of Theorem 1 for this case that if p | P and w ≥ 2, then ν_{p}(A_{d}) ≥ 2^{w−1} > w, whereas for w = 1, we have ν_{p}(A_{d}) ≥ 1 = w. So, in fact we even see that (|P |u_{n^{2}})_{n≥1} satisfies the Dold condition in this case, and we do not need the factor P^{2}.

Dynamical proof for positive P: Here (P u_{n})_{n≥1} is the sequence (P, P^{2}, …), which we identify as (Fix(T^{n}))_{n≥1}, where T: X → X is the shift map on the full P -shift. Taking the union of P disjoint copies of this system produces a map S with

(Fix(S^{n}))_{n≥1} = (P^{2}, P^{3}, P^{4}, …).

It follows that (P^{2}u_{n})_{n≥1} is realizable, and in particular satisfies (D). On the other hand, sampling along a monomial subsequence always preserves realizability, so (P^{2}u_{n^{2}}) is also realizable. Work of Jaidee, Moss, and Ward [3] shows that no other polynomials have this property.

We next turn to the case (P, Q) = (0, −1). This is an excluded case of Theorem 1. In this case, u_{n} = 0 if n is even and u_{n} = 1 if n is odd. So, in (D), the sum S is zero if n is odd. Further, in the sum S, for every prime p dividing m, the amounts (n/d)^{2} and (n/(pd))^{2} are both even or both odd, so this difference is zero unless p = 2 and one of (n/d)^{2} and (n/(2d))^{2} is even and the other is odd. But the only chance for this to happen is when 2∥n, and in this last case the prime 2 from the denominator of the Dold ratio can be absorbed into |Δ(F)| = |P^{2} − 4Q| = 4.

The remaining cases (P, Q) ≠ (P, 0), (0, −1) follow from Theorem 1 on noticing that

Δ(F) = P^{2} − 4Q  (6)

is a multiple of Δ(𝕂).

4 Acknowledgments

We thank the referee for a careful reading of our manuscript and for comments and suggestions that improved the quality of the final version of our paper.

References

[1] G. Everest, A. van der Poorten, I. Shparlinski, and T. Ward, Recurrence Sequences, Vol. 104 of Mathematical Surveys and Monographs, American Mathematical Society, 2003.

[2] P. Fatou, Séries trigonométriques et séries de Taylor, Acta Math. 30 (1906), 335–400.

[3] S. Jaidee, P. Moss, and T. Ward, Time-changes preserving zeta functions, Proc. Amer. Math. Soc. 147 (2019), 4425–4438.

[4] P. A. Martin, The Galois group of x^{n} − x^{n−1} − ⋯ − x − 1, J. Pure Appl. Algebra 190 (2004), 213–223.

[5] E. P. Miles, Generalized Fibonacci numbers and associated matrices, Amer. Math. Monthly 67 (1960), 745–752.

[6] G. T. Minton, Linear recurrence sequences satisfying congruence conditions, Proc. Amer. Math. Soc. 142 (2014), 2337–2352.

[7] P. Moss, The Arithmetic of Realizable Sequences, PhD thesis, University of East Anglia, 2003.

[8] P. Moss and T. Ward, Fibonacci along even powers is (almost) realizable, Fibonacci Quart. 60 (2022), 40–47.

[9] Y. Puri, Arithmetic of Numbers of Periodic Points, PhD thesis, University of East Anglia, 2001.

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

[11] Y. Puri and T. Ward, A dynamical property unique to the Lucas sequence, Fibonacci Quart. 39 (2001), 398–402.

[12] D. A. Wolfram, Solving generalized Fibonacci recurrences, Fibonacci Quart. 36 (1998), 129–145.

2020 Mathematics Subject Classification: Primary 37P35; Secondary 11B50. Keywords: linear recurrence sequence, periodic point, Dold congruence.

(Concerned with sequences \underline{A000045}, \underline{A000073}, \underline{A000079}, \underline{A000204}, and \underline{A054783}.)

Received March 24 2023; revised version received May 4 2023. Published in Journal of Integer Sequences, May 5 2023.

Return to Journal of Integer Sequences home page.