Séminaire Lotharingien de Combinatoire 54A (2006), Article B54Ap

A GENERALIZATION OF COBHAM’S THEOREM FOR REGULAR SEQUENCES

Jason P. Bell*

Department of Mathematics, Simon Fraser University 8888 University Ave., Burnaby, BC V5A 1S6, Canada

                      jpb@math.sfu.ca

Abstract. A sequence is said to be k-automatic if the n^{th} term of this sequence is generated by a finite state machine with n in base k as input. A result due to Cobham states that if a sequence is both kand ℓ-automatic and k and ℓ are multiplicatively independent, then the sequence is eventually periodic. Allouche and Shallit defined (R, k)-regular sequences as a natural generalization of k-automatic sequences for a given ring R. In this paper we prove the following generalization of Cobham’s theorem: If a sequence is (R, k)- and (R, ℓ)-regular and k and ℓ are multiplicatively independent, then the sequence satisfies a linear recurrence over R.

1. Introduction

Given a positive integer k, a sequence is said to be k-automatic if the n^{th} term of this sequence is generated by a finite state machine with n in base k as input. Sequences such as the Thue-Morse and Rudin-Shapiro sequences are famous examples of 2-automatic sequences. Automatic sequences appear in many diverse areas of mathematics including an unexpected appearance in paper folding [7], [8], [9].

Arguably the most important theorem in the theory of automatic sequences is Cobham’s theorem. This theorem characterizes sequences that are both k- and ℓ-automatic when k and ℓ are multiplicatively independent integers; that is, when there do not exist positive integers a and b such that k^{a} = ℓ^{b}.

Theorem 1.1 (Cobham [6]). Let k and ℓ be multiplicatively independent integers and let {f(n)} be a sequence which is both k- and ℓ-automatic. Then {f(n)} is eventually periodic.

* Supported in part by the by the National Science Foundation under Grant No.

DMS-0502858.

Over the years many different proofs and some generalizations of his theorem have been given [17], [18], [20], [24], [15], [11], [21], [19], [12]. To give our generalization of Cobham’s theorem, we need a generalization of automatic sequences due to Allouche and Shallit [1], [2], [3].

Another way of defining the k-automatic property comes from looking at the k-kernel of a sequence. The k-kernel of a sequence {f(n)}_{n=0}^{∞} is defined to be the collection of sequences of the form {f(k^{i}n+j)}_{n=0}^{∞} where i ≥ 0 and 0 ≤ j < k^{i}. A sequence is k-automatic if and only if its kkernel is finite. Using this definition of k-automatic sequences, Allouche and Shallit [1], [2], [3] generalized the notion of being k-automatic. We note that this concept is very closely related to the more general notion of recognizable series [5].

Let R be a commutative ring. Given a sequence {f(n)}_{n=0}^{∞} taking values in some R-module, we create an R-module M_{R}({f(n)}; k) which is defined to be the R-module generated by all sequences {f(k^{i}n+j)}_{n=0}^{∞}, where i ≥ 0 and 0 ≤ j < k^{i}. Often, we will suppress the R in M_{R}({f(n)}; k) and just write M({f(n)}; k) when there is no fear of confusion.

Definition 1.2. Let R be a commutative ring and let k be a positive integer. A sequence is (R, k)-regular if M({f(n)}; k) is finitely generated as an R-module.

In fact, Allouche and Shallit impose the additional constraint that the ground ring R be Noetherian when looking at (R, k)-regular sequences, but this hypothesis is not necessary in obtaining our generalization.

Since the k-kernel of a sequence {f(n)} spans M({f(n)}; k) as an R-module, we see that a k-automatic sequence with values in R is necessarily (R, k)-regular for any ring R.

Unlike automatic sequences, which only assume finitely many values, regular sequences can assume infinitely many values. For this reason it is unrealistic to assume that the correct analogue of Cobham’s theorem for regular sequences is that an (R, k)- and (R, ℓ)-regular sequence is eventually periodic if k and ℓ are multiplicatively independent. There is, however, a larger class of sequences which gives the correct analogue.

Definition 1.3. Given a commutative ring R and R-module M, we say that a map

f : ℕ → M

satisfies a linear recurrence over R, if there exist a positive integer m and constants c_{1}, …, c_{m} ∈ R such that

f(n) = ∑_{i=1}^{m} c_{i}f(n − i) for n ≥ m.

If {f(n)} satisfies a linear recurrence over a ring R and assumes only finitely many values, then {f(n)} is eventually periodic (cf. Everest et al. [14, §3.1]). Furthermore, given an eventually periodic sequence {f(n)} there exist numbers m and N such that {f(n)} satisfies the linear recurrence f(n + m) = f(n) for n ≥ N. Our main result is the following theorem.

Theorem 1.4 (Generalized Cobham Theorem). Let R be a commutative ring, let k and ℓ be multiplicatively independent positive integers, and let {f(n)} be a sequence which is both (R, k)- and (R, ℓ)-regular. Then {f(n)} satisfies a linear recurrence over R.

In light of the above remarks, this is indeed a generalization of Cobham’s theorem. In the case that R = ℤ, an (R, k)-regular sequence is called k-regular. In this case we get a simple characterization of sequences which are both k- and ℓ-regular if k and ℓ are multiplicatively independent.

Theorem 1.5. Let {f(n)} be an integer valued sequence and let k and ℓ be two multiplicatively independent positive integers. Then {f(n)} is both k- and ℓ-regular if and only if

∑_{n=0}^{∞} f(n)x^{n} ∈ ℤ[[x]]

is the power series expansion of a rational function whose poles are all roots of unity.

Our proof of Theorem 1.4 is ring-theoretic in nature, using a series of reductions. The argument is first done for the case that the ring R is a finitely generated integral domain over ℤ and the sequence {f(n)} takes values in R. To do this we need some basic facts about such rings; namely, that all maximal ideals have finite codimension and that the intersection of all maximal ideals is (0). Next the general version of the theorem is deduced by showing one can assume that R is a finitely generated algebra over ℤ; then, we show that R can also be assumed to be an integral domain. Finally, using similar arguments applied to R-modules, we show that one can assume that {f(n)} takes values in R. Having reduced everything to the case we have already handled, we obtain our generalization of Cobham’s theorem.

In §2, we give some basic background in the theory of commutative rings. In §3 we prove Theorem 1.4 for finitely generated integral domains R over ℤ with R-valued sequences. In §4 we reduce the problem to the case handled in §3. Finally in §5 we give an open problem along with some concluding remarks.

2. Background in commutative rings

Jacobson rings form an important class of rings and are especially useful in formulating the general Nullstellensatz. We now give the definition of a Jacobson ring, first recalling that an ideal in a ring is prime if when we quotient out by this ideal we obtain a integral domain.

Definition 2.1. We say that a commutative ring R is a Jacobson ring if every prime ideal is the intersection of maximal ideals.

Notice that the ring of integers is a Jacobson ring.

Theorem 2.2. If R is a Jacobson ring and S is a finitely generated Ralgebra, then S is also a Jacobson ring and every maximal ideal I in S has the property that J := I ∩ R is a maximal ideal of R; moveover, S/I is a finite extension of R/J.

Proof. See Eisenbud [13, Theorem 4.19]. □

Corollary 2.3. Let R be a finitely generated integral domain over ℤ. Then:

• (0) is the intersection of maximal ideals;

• R/I is finite dimensional for every maximal ideal I of R.

Proof. A finitely generated ℤ-algebra is Jacobson by Theorem 2.2. If R is a integral domain then (0) is a prime ideal and thus is the intersection of maximal ideals. If I is a maximal ideal in R, then I ∩ℤ = (p) for some prime p ∈ ℤ. Then R/I is a finite extension of ℤ/pℤ and is thus a finite ring. □

For us, the important facts about finitely generated integral domains over ℤ are those given in Corollary 2.3 are the fact that such rings are Noetherian; that is, they satisfy the ascending chain condition on ideals. This ensures that finitely generated modules over such rings satisfy the ascending chain condition on submodules. In particular, we can pick ideals that are maximal with respect to some specified property and can pick submodules in a finitely generated module that are maximal with respect to some property. The fact that in a finitely generated integral domain R over ℤ all maximal ideals have finite codimension has important consequences for (R, k)-regular sequences, as is seen in the following theorem.

Theorem 2.4. Let R be a Jacobson ring and let {f(n)} be an (R, k)- regular sequence. If I is a maximal ideal in R then {f(n) mod I} is a k-automatic sequence.

Proof. Notice that R/I is a finite field and {f(n)} takes values in a finite dimensional R/I-vector space. It follows that {f(n) mod I} takes on only finitely many values and thus is k-automatic (cf. Allouche and Shallit [3, Theorem 16.1.5]). □

3. Proofs for integral domains

In this section, we prove Theorem 1.4 in the case that R is a finitely generated integral domain over ℤ and {f(n)} is R-valued. We first give a few basic results about rational sequences.

Lemma 3.1. Let {f(n)} be an integer sequence and let a be a positive integer. Then:

• {f(n)} satisfies a linear recurrence if and only if {f(an + j)} satisfies a linear recurrence for 0 ≤ j < a;

• {f(n)} satisfies a linear recurrence if and only if {f(n + a)} satisfies a linear recurrence; and

• {f(n)} satisfies a linear recurrence over a ring R if and only if the R-module spanned by the sequences {f(n + i)} with i ≥ 0 is finite dimensional.

Proof. The proofs of these facts are straightforward. □

Lemma 3.2. Let R be a Noetherian integral domain with field of fractions K. If {f(n)} is an R-valued sequence satisfying a linear recurrence over K, then {f(n)} satisfies a linear recurrence over R.

Proof. By assumption there exist c_{1}, …, c_{m} ∈ K such that

f(n) = ∑_{i=1}^{m} c_{i}f(n − i) for n ≥ m.

We define R^{m} to be the set of all m-dimensional column vectors with entries in R. For each n ≥ 0, define

v(n) = [ f(n) f(n + 1) ⋯ f(n + m − 1) ]^{T} ∈ R^{m}.

Then there is an m × m matrix B with entries in K such that Bv(n) = v(n + 1) for all n ≥ 0. Let M denote the R-submodule of R^{m} spanned by the vectors v(n) for n ≥ 0. Since R is Noetherian, M is finitely generated. Hence there exists some d such that the set {v(i) | 0 ≤ i ≤ d} spans M as an R-module. It follows that there exist r_{0}, …, r_{d} ∈ R such that

v(d + 1) = ∑_{i=0}^{d} r_{i}v(i).

Left multiplying both sides by B^{n}, we see that

v(n + d + 1) = ∑_{i=0}^{d} r_{i}v(n + i) for n ≥ 0.

Taking the first coordinates of both sides we obtain the R-linear recurrence

f(n + d + 1) = ∑_{i=0}^{d} r_{i}f(n + i) for n ≥ 0.

This completes the proof. □

Lemma 3.3. Let R be an integral domain with field of fractions K, let k be a positive integer, and let {f(n)} be an R-valued (R, k)-regular sequence. Suppose that {g(n)} is an R-valued sequence such that there is an infinite set M of maximal ideals of R with the following properties:

• ⋂_{I∈M} I = (0);

• for every ideal I ∈ M there exists some some sequence h_{I} ∈ M({f(n)}; k) with the property that g(n) ≡ h_{I}(n) mod I for all n ≥ 0.

Then {g(n)} ∈ M({f(n)}; k) ⊗_{R} K.

Proof. Let I ∈ M and let f_{1}(n), …, f_{d}(n) be a basis for M({f(n)}; k)⊗_{R} K as a K-vector space. By assumption, there exist C_{1}, …, C_{d} ∈ R such that

g(n) ≡ C_{1}f_{1}(n) + ⋯ + C_{d}f_{d}(n) mod I

for all n ≥ 0. This says that every (d + 1) × (d + 1) minor of the infinite matrix

( \begin{matrix}f_{1}(0) & f_{1}(1) & f_{1}(2) & ⋯ \\ f_{2}(0) & f_{2}(1) & f_{2}(2) & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋯ \\ f_{d}(0) & f_{d}(1) & f_{d}(2) & ⋯ \\ g(0) & g(1) & g(2) & ⋯ \end{matrix} )

is in I. Since the intersection of all ideals in M is zero, we conclude that every (d + 1) × (d + 1) minor is 0. It is well-known that a matrix with entries in some field has rank ≥ m if and only if some m × m minor is nonzero. It follows that the sequences f_{1}, …, f_{d}, g are linearly dependent over K. Since f_{1}, …, f_{d} are linearly independent, we conclude that g is a K-linear combination of f_{1}, …, f_{d}. The result follows. □

We now give a criterion which allows us to deduce when certain (R, k)- regular sequences satisfy a linear recurrence over R.

Theorem 3.4. Let R be an integral domain, let k be a positive integer, and let {f(n)} be an R-valued (R, k)-regular sequence with the property that {f(n) mod I} is periodic with period relatively prime to k for an infinite set of maximal ideals I whose intersection is (0). Then {f(n)} satisfies a linear recurrence R.

Proof. Let K be the field of fractions of R and let M be the set of maximal ideals I such that {f(n) mod I} is a periodic sequence with period relatively prime to k. Let I ∈ M and let e denote the period of {f(n) mod I}. Since k is relatively prime to e, there exists some a > 0 such that k^{a} ≡ 1 mod e. Hence f(k^{a}n + 1) ≡ f(n + 1) mod I for all n ≥ 0. It follows that for each ideal I in M, there exists some sequence h_{I} ∈ M({f(n)}, k) such that f(n+1) ≡ h_{I}(n) mod I for all n ≥ 0. From Lemma 3.3, we deduce that {f(n + 1)} ∈ M({f(n)}; k) ⊗_{R} K. An easy induction argument shows that {f(n + i)} ∈ M({f(n)}; k) ⊗_{R} K for all i ≥ 0. Since M({f(n)}; k) ⊗_{R} K is finite dimensional over K we see that the subspace generated by

{{f(n + i)} | i ≥ 0}

is finite dimensional. Hence f(n) satisfies a linear recurrence over K. The result now follows from Lemma 3.2 □

Definition 3.5. Given an eventually periodic sequence {f(n)}, we define the index of {f(n)} to be the minimal i such that the sequence {f(n + i)}_{n≥0} is periodic. We define the minimal period of a periodic sequence {f(n)} to be the smallest positive integer e such that f(n + e) = f(n) for all n ≥ 0.

We now show how to obtain periodic sequences from eventually periodic ones.

Lemma 3.6. Let {f_{1}(n)}, …, {f_{m}(n)} be nonzero eventually periodic sequences taking values in a field K and which have distinct indices a_{1}, …, a_{m} respectively. Then {f_{1}(n)}, …, {f_{m}(n)} are linearly independent over K.

Proof. Suppose this is not the case. Then choose m minimal with respect to the property that there exist f_{1}, …, f_{m} satisfying the hypotheses of lemma that are linearly dependent over K. By relabelling if necessary, we may assume that a_{1} < ⋯ < a_{m}. Let L denote the lcm of the minimal periods of f_{1}, …, f_{m}. Suppose that

c_{1}f_{1}(n) + ⋯ + c_{m}f_{m}(n) = 0 for all n ≥ 0.

Then

c_{1}f_{1}(a_{m} − 1) + ⋯ + c_{m}f_{m}(a_{m} − 1) = 0,

and

c_{1}f_{1}(a_{m} − 1 + L) + ⋯ + c_{m}f_{m}(a_{m} − 1 + L) = 0.

Observe that f_{i}(a_{m} − 1) = f_{i}(a_{m} − 1 + L) for i < m since f_{1}, …, f_{m−1} all have index at most a_{m} − 1 and have period dividing L. Thus

c_{m}f_{m}(a_{m} − 1) = c_{m}f_{m}(a_{m} − 1 + L).

But notice, that f(j + L) = f(j) for j ≥ a_{m} and hence f(a_{m} − 1 + L) ≠ f(a_{m} −1), or else {f(n+a_{m} −1)} would be periodic with period dividing L. It follows that c_{m} = 0. But this says that f_{1}, …, f_{m−1} are linearly dependent. This contradicts the minimality of m. The claim follows. □

Lemma 3.7. Let {f(n)} be an eventually periodic sequence taking values in a field K, and let k be a positive integer. If dim_{K}M_{K}(f; k) ≤ d, then the index of {f(n)} is at most k^{d}.

Proof. Let m denote the index of {f(n)} and let p denote the minimal period of {f(n + m)}_{n≥0}. We claim that for each a < log_{m} k, there is some b < k^{a} such that {f(k^{a}n+b)} has index ⌈m/k^{a}⌉. To see this, notice that for any b < k^{a} and i = ⌈m/k^{a}⌉,

f(k^{a}(n + i + p) + b) = f(k^{a}n + k^{a}i + k^{a}p + b)
= f(k^{a}n + k^{a}i + b)
= f(k^{a}(n + i) + b),

where the penultimate step follows from the fact that k^{a}i + b is greater than or equal to the index of {f(n)}. Thus for any b < k^{a}, the index of {f(k^{a}n + b)} is at most ⌈m/k^{a}⌉. We claim that there exists some b < k^{a} such that the index of {f(k^{a}n + b)} is at least ⌈m/k^{a}⌉. If this is not the case then there exist some i < m/k^{a} such that f(k^{a}(n + i + p) + b) = f(k^{a}(n+i)+b) for all n ≥ 0 and all b < k^{a}. Hence f(k^{a}n+b+k^{a}i+k^{a}p) = f(k^{a}n + b + k^{a}i) for all n ≥ 0. But since this is true for all b < k^{a} and any integer j has a unique expression as k^{a}n + b, we see that

f(j + k^{a}i + k^{a}p) = f(j + k^{a}i) for all j ≥ 0.

Hence the index of {f(n)} is at most k^{a}i < m, a contradiction. Thus for each a there is some b < k^{a} such that the index of {f(k^{a}n+b)} is exactly ⌈m/k^{a}⌉. If k^{d} < m, then {⌈m/k^{i}⌉ | 0 ≤ i ≤ d} has d+1 distinct elements. Moreover, there exist f_{0}, …, f_{d} ∈ M({f(n)}; k) such that f_{i} has index ⌈m/k^{i}⌉. By Lemma 3.6, these sequences are linearly independent over K, since they are necessarily nonzero. But by assumption M_{K}({f(n)}; k) has dimension at most d, a contradiction. We conclude that m ≤ k^{d}. □

Corollary 3.8. Let R be a ring, let k be a positive integer, and let {f(n)} be an R-valued (R, k)-regular sequence. Suppose that there is a maximal ideal I of R such that:

• {f(n) mod I} is eventually periodic;

• M_{R}(f; k)⊗_{R}R/I has dimension at most d as an R/I-vector space. Then {f(n + k^{d}) mod I} is periodic.

Proof. The result follows easily from Lemma 3.7. □

We now show how to get periods relatively prime to k.

Lemma 3.9. Let {f_{1}(n), …, f_{d}(n)} be nonzero periodic sequences taking values in some field K. Suppose that f_{i} has period a_{i} for 1 ≤ i ≤ d and that a_{1}|a_{2}| ⋯ |a_{d} and a_{1}, …, a_{d} are all distinct. Then f_{1}, …, f_{d} are linearly independent over K.

Proof. Suppose not. Then we can choose d minimal with respect to the property that there exist such f_{1}, …, f_{d} that are linearly dependent. Then there exist integers c_{1}, …, c_{d} such that

c_{1}f_{1}(n) + ⋯ + c_{d}f_{d}(n) = 0 for all n ≥ 0.

Notice that f_{i}(n + a_{d−1}) = f_{i}(n) for i < d. Thus

c_{1}f_{1}(n) + ⋯ + c_{d−1}f_{d−1}(n) + c_{d}f_{d}(n + a_{d−1}) = 0.

Subtracting we see that c_{d}(f_{d}(n + a_{d−1}) − f_{d}(n)) = 0 for all n. Since f_{d} has period a_{d} > a_{d−1}, we conclude that c_{d} = 0. But this contradicts the minimality of d. The result now follows. □

Proposition 3.10. Let {f(n)} be a periodic sequence taking values in a field K and let k be a positive integer. If dim_{K}M_{K}(f; k) ≤ d then for 0 ≤ j < k^{d}, the sequence {f(k^{d}n + j)} is periodic with minimal period relatively prime to k.

Proof. Let e denote the minimal period of {f(n)}. Suppose that the period of f(k^{d}n + j) is not relatively prime to k. Then the sequence is necessarily nonzero. Pick 0 = j_{0}, j_{1}, …, j_{d} = j with the property that 0 ≤ j_{i} < k^{i} and j ≡ j_{i} mod k^{i}. We claim that the (nonzero) sequences

{{f(k^{i}n + j_{i})} | 0 ≤ i ≤ d}

are linearly independent over K. Let q_{i} denote the minimal period of the sequence {f(k^{i}n+j_{i})}. Observe that q_{i+1} divides q_{i}/ gcd(k, q_{i}). Moreover, by assumption {f(k^{d}n + j_{d})} does not have minimal period relatively prime to k and thus q_{0}, q_{1}, …, q_{d} must all have some factor in common with k. Hence

q_{d} < q_{d−1} < ⋯ < q_{0}.

Thus by Lemma 3.9, we see that the sequences

{{f(k^{i}n + j_{i})} | 0 ≤ i ≤ d}

are linearly independent over K. But M({f(n)}; k) has dimension at most d and so we get an immediate contradiction. □

We are now ready to give our most important result about rational k-regular sequences.

Theorem 3.11. Let R be a finitely generated integral domain over ℤ, let k be a positive integer, and let {f(n)} be a (R, k)-regular sequence taking values in R. Then {f(n)} satisfies a linear recurrence over R if and only if {f(n) mod I} is eventually periodic for infinitely many maximal ideals I whose intersection is (0).

Proof. Suppose that {f(n)} satisfies a linear recurrence over R and let I be a maximal ideal in R. Then {f(n) mod I} takes values in R/I, which is a finite field by Corollary 2.3. It follows that {f(n) mod I} is eventually periodic for every maximal ideal I (see Everest et al. [14, pp. 45-46]).

Conversely, suppose that {f(n)} is eventually periodic mod I for infinitely many maximal ideals I whose intersection is (0) and let M denote the set of such ideals. Let d be the size of a minimial generating set for M({f(n)}; k) as an R-module. We define g(n) = f(n + k^{d}) for n ≥ 0. We note that {g(n)} is an (R, k)-regular sequence. By Corollary 3.8, {g(n) mod I} is periodic for each maximal ideal I in M. By Proposition 3.10, for 0 ≤ j < k^{d} we have that g_{j}(n) := g(k^{d}n + j) is periodic mod I with period relatively prime to k for each maximal ideal I in M. Hence {g_{j}(n)} satisfies a linear recurrence for 0 ≤ j < k^{d} by Theorem 3.4. By Lemma 3.1, we see that {g(n)} satisfies a linear recurrence and so {f(n)} satisfies a linear recurrence, again by Lemma 3.1. □

4. Reduction to finitely generated integral domains

Proposition 4.1. Let R be a commutative ring, let k be a positive integer, and let f be an (R, k)-regular sequence taking values in an R-module A. Then f is (S, k)-regular for some finitely generated ℤ-subalgebra S of R. Furthermore there is some finitely generated S-submodule B of A such that f takes values in B.

Proof. Since {f(n)} is (R, k)-regular, there exist a positive integer d, Rvalued d × d matrices X_{0}, …, X_{k−1}, and sequences {a_{i}(n)}, 1 ≤ i ≤ d such that if

v(n) = [ a_{1}(n) ; a_{2}(n) ; ⋮ ; a_{d}(n) ]

then v(kn + j) = X_{j}v(n) for 0 ≤ j < k (cf. Allouche and Shallit [3, Theorem 16.1.3]).

Let S be the ℤ-subalgebra of R generated by the entries in X_{0}, …, X_{k−1} and let B be the S-submodule of A spanned by the entries in v(0). Then by construction {f(n)} is (S, k)-regular and takes values in B (cf. Allouche and Shallit [3, Theorem 16.1.3]). □

We note that this interpretation of regular sequences in terms of monoid homomorphisms from {0, 1, 2, …, k − 1}^{∗} to M_{d}(R) is closely related to recognizable series [5].

Lemma 4.2. Let R be a commutative ring, let k be a positive integer, and let {f(n)} be an (R, k)-regular sequence taking values in a principle ideal Ra of R. If {g(n)} is an R-valued sequence satisfying f(n) = ag(n) for all n ≥ 0, then {g(n) mod J} is R/J regular, where J is the annihilator of a.

Proof. Pick a finite set of generators {f_{1}, …, f_{d}} for M(f; k). For each i, there is some function g_{i} in M(g; k), corresponding to f_{i}, with the property that f_{i} = ag_{i}. We claim that {g_{1}(n) mod J, …, g_{d}(n) mod J} spans M_{R/J}({g(n) mod J}; k) as an R/J-module. To see this, suppose that h(n) ∈ M(g; k) has the property that h(n) mod J is not in the span of this set. We have ah(n) ∈ M(f; k), and hence there exist r_{1}, … r_{d} ∈ R such that

ah = ∑_{i=1}^{d} r_{i}f_{i}.

Equivalently,

ah = ∑_{i=1}^{d} ar_{i}g_{i}.

Thus h(n) − ∑ r_{i}g_{i}(n) annihilates a for all n. Consequently,

h ≡ ∑_{i=1}^{d} r_{i}g_{i} mod J,

a contradiction. □

Proof of Theorem 1.4. The proof of this result uses a series of reductions.

First Reduction: We may assume that R is finitely generated as a ℤ-algebra and f(n) takes values in a finitely generated R-module.

By Proposition 4.1, we see that {f(n)} is (S, k)- and (S, ℓ)-regular for some finitely generated ℤ-subalgebra of R; moreover, {f(n} takes values in some finitely generated S-module A. Since a linear recurrence over S is also a linear recurrence over R, it is no loss of generality to assume that R is a finitely generated ℤ-algebra and that {f(n)} takes values in a finitely generated R-module A.

Second Reduction: We may assume that the {f(n) mod J} satisfies a linear recurrence over R/J for every nonzero ideal J.

We may assume that f(n) does not satisfy a linear recurrence over R. Since R is finitely generated over ℤ, it is Noetherian. Thus we can pick an ideal I maximal with respect to the property that there exists a sequence which is both (R/I, k)- and (R/I, ℓ)-regular and yet does not satisfy a linear recurrence. Replace R with R/I and pick a sequence {f(n)} which is both (R, k)- and (R, ℓ)-regular and yet does not satisfy a linear recurrence over R. Then {f(n) mod J} satisfies a linear recurrence over R/J for every nonzero ideal J in R.

Third Reduction: We may assume that R is an integral domain. Suppose that this is not the case. Then there is a nonzero element a

whose annihilator J is nonzero. By assumption, f(n) mod aR satisfies a linear recurrence and hence there exist c_{1}, …, c_{m} ∈ R such that

f(n) = ∑_{i−1}^{m} c_{i}f(n − i) mod aR.

Let g(n) = f(n) − ∑ c_{i}f(n − i). Then {g(n)} is (R, k)-regular and (R, ℓ)-regular and takes values in aR. Pick an R-valued sequence {h(n)} satisfying g(n) = ah(n) for all n ≥ 0. By Lemma 4.2, h(n) mod J is (R/J, k)- and (R/J, ℓ)-regular and hence satisfies a linear recurrence over R/J; that is, there exist d > 0 and r_{1}, …, r_{d} ∈ R such that

h(n) ≡ ∑_{i=1}^{d} r_{i}h(n − i) mod J for n ≥ d.

Multiplying both sides by a gives

g(n) = ∑_{i=1}^{d} r_{i}g(n − i),

and so {g(n)} satisfies a linear recurrence over R. This immediately gives a linear recurrence satisfied by {f(n)} over R. Thus it is no loss of generality to assume that R is an integral domain.

Fourth Reduction: We may assume that {f(n)} is R-valued.

We already may assume that {f(n)} takes values in a finitely generated R-module A. Since A is Noetherian, we can pick a submodule B of A maximal with respect to the property that {f(n) + B} does not satisfy a recurrence over R. Replacing A with A/B, we can assume that {f(n) + A′} satisfies a recurrence over R for all nonzero submodules A′ of A. Pick a nonzero a ∈ A and consider the short exact sequence

0 → Ra → A → A/Ra.

Notice that the reduced sequence {f(n) + Ra} satisfies a recurrence over R. Let g(n) be a sequence satisfying a linear recurrence over R which takes values in A such that g(n) − f(n) ∈ Ra for all n ≥ 0. (Note that this can be done simply by “pulling back” the initial values of {f(n) + Ra} in A/Ra to initial values in A and then declaring that g(n) satisfies the same recurrence as the one satisfied by {f(n) + Ra}.) Notice h(n) := f(n) − g(n) cannot satisfy a linear recurrence over R as f(n) does not; moreover, it takes values in the module Ra. This module is isomorphic to R/Ann(a). Observe that h(n) can be regarded as an (R/Ann(a), k)- and (R/Ann(a), ℓ)-regular sequence and thus if Ann(a) is nonzero, then it satisfies a linear recurrence over R/Ann(a) by our choice of R. Moreover, this linear recurrence lifts to a linear recurrence over R by the fact that h(n) takes values in a module that is annihilated by Ann(a). Thus Ann(a) = 0. Replacing, f(n) by h(n), we may assume that f(n) is R-valued.

And so we may assume that f(n) is an (R, k)- and (R, ℓ)-regular sequence taking values in R and R is a finitely generated domain over ℤ. Since R is a finitely generated domain over ℤ, we have that R/I is finite dimensional for each maximal ideal I of R and the intersection of all maximal ideals is (0) by Corollary 2.3. Hence {f(n) mod I} is both k- and ℓ-automatic for every maximal ideal I. It follows from Cobham’s theorem that {f(n) mod I} is eventually periodic for every maximal ideal I. Since the intersection of all maximal ideals is (0), we see that {f(n)} satisfies a linear recurrence over R by Theorem 3.11. The result follows. □

Proof of Theorem 1.5. Suppose first that {f(n)} is k- and ℓ-regular. By Theorem 1.4

F(x) := ∑_{n=0}^{∞} f(n)x^{n} ∈ ℤ[[x]]

is the power series expansion of a rational function p(x)/q(x) with p, q ∈ ℤ[x] and q(0) = 1. Note that f(n) = O(n^{d}) for some positive integer d (see Allouche and Shallit [3, Theorem 16.3.1]). Hence F(x) has no poles inside the unit circle and so q(x) must have leading coefficient ±1. Since q(0) = 1, we conclude that F(x) has all of its poles on the unit circle. Since q(x) has integer coefficients, these poles must all be roots of unity. Conversely, Allouche and Shallit [3, Theorem 16.4.2] show that the power series expansion of a rational function having all its poles at roots of unity is k-regular for all k ≥ 1. □

5. Concluding remarks

We note that Theorem 1.5 appears as a conjecture in Allouche and Shallit [3, §16.8, item 16.3]. In this form, it is a special case of a conjecture due to van der Poorten. Given a power series

F(x) = ∑_{n=0}^{∞} f(n)x^{n} ∈ ℤ[[x]],

we say that F(x) is k-Mahler if F(x) satisfies a functional equation of the form

(5.1)  F (x^{k^{m}}) = ∑_{i=0}^{m−1} p_{i}(x)F(x^{k^{i}}).

k-regular sequences are a special subset of the set of k-Mahler sequences.

Conjecture 5.1 (van der Poorten [22]). Let F(x) be a power series which is both k- and ℓ-Mahler. If k and ℓ are multiplicatively independent then F(x) is the power series expansion of a rational function.

Some work has been done on this by various authors [23], [24], [10], [4]. In fact, van der Poorten [22] outlined a proof of the conjecture, but the proof is incomplete.

6. Acknowledgments

I thank Jean-Paul Allouche, Jeff Shallit, and Harm Derksen for many helpful comments and discussions.

References

[1] J.-P. Allouche and J. Shallit. The ring of k-regular sequences. Theoret. Comput. Sci. 98 (1992), 163–197.

[2] J.-P. Allouche and J. Shallit. The ring of k-regular sequences, II. Theoret. Comput. Sci. 307 (2003), 3–29.

[3] J.-P. Allouche and J. Shallit. Automatic sequences. Theory, applications, generalizations. Cambridge University Press, Cambridge, 2003.

[4] P.-G. Becker. k-Regular power series and Mahler-type functional equations. J. Number Theory 49 (1994), 269–286.

[5] J. Berstel and C. Reutenauer. Rational Series and Their Languages EATCS Monographs on Theoretical Computer Science (12), W. Brauer, G. Rozenberg, A. Salomaa (Eds.) Springer-Verlag Berlin, Heidelberg 1988.

[6] A. Cobham. On the base-dependence of sets of numbers recognizable by finite automata. Math. Systems Theory 3 (1969), 186–192.

[7] M. Dekking, M. Mendès France, and A. van der Poorten. Folds. Math. Intelligencer 4 (1982), no. 3, 130–138. Erratum: 5 (1983), 5.

[8] M. Dekking, M. Mendès France, and A. van der Poorten. Folds. II. Symmetry disturbed. Math. Intelligencer 4 (1982), no. 4, 173–181. Erratum: 5 (1983), 5.

[9] M. Dekking, M. Mendès France, and A. van der Poorten. Folds. III. More morphisms. Math. Intelligencer 4 (1982), no. 4, 190–195. Erratum: 5 (1983), 5.

[10] P. Dumas. Algebraic aspects of B-regular series. In A. Lingas, R. Karlsson, A. Carlsson, editors, Proc. 20th Int. Conf. on Automata, Languages, and Programming, Vol. 700 of Lecture Notes in Computer Science, 457–468. Springer-Verlag, 1993.

[11] F. Durand. A generalization of Cobham’s theorem. Theory Comput. Systems 31 (1998), 169–185.

[12] F. Durand. A characterization of substitutive sequences using return words. Discrete Math. 179 (1998), 89–101.

[13] D. Eisenbud. Commutative algebra. With a view toward algebraic geometry. Graduate Texts in Mathematics, 150. Springer-Verlag, New York, 1995.

[14] G. Everest, A. van der Poorten, I. Shparlinski, and T. Ward. Recurrence sequences. Mathematical Surveys and Monographs, 104. American Mathematical Society, Providence, RI, 2003.

[15] S. Fabre. Une généralisation du théorème de Cobham. Acta Arith. 67 (1994), 197–208.

[16] I. Fagnot. On the subword equivalence problem for morphic words. Discrete Appl. Math. 75 (1997), no. 3, 231–253.

[17] G. Hansel and T. Safer. Vers un théorème de Cobham pour les entiers de Gauss. Bull. Belg. Math. Soc. Simon Stevin 10 (2003), 723–735.

[18] G. Hansel. À propos d’un théorème de Cobham. In D. Perrin, editor, Actes de la Fête des Mots, 55–59. Greco de Programmation, CRNS, Rouen, 1982.

[19] G. Hansel. Systèmes de numération indépendants et syndéticité. Theoret. Comput. Sci. 204 (1998), 119–130.

[20] K. Nishioka. Mahler functions and trancendence. Lecture Notes in Mathematics 1631. Springer-Verlag, Berlin, 1996.

[21] F. Point and V. Bruyère. On the Cobham-Semenov theorem. Theory Comput. Systems 30 (1997), 197–220.

[22] A. J. van der Poorten. Remarks on Roth’s theorem. Séminaire de Théorie des Nombres, Paris 1986–87, 443–452, Progr. Math., 75, Birkhäuser Boston, Boston, MA, 1988.

[23] B. Randé. Récurrences 2- et 3-mahlériennes. J. Théor. Nombres Bordeaux 5 (1993) 101–109.

[24] B. Randé. Équations fonctionnelles de Mahler et applications aux suites prégulières. PhD thesis, Université Bordeaux I, 1992.