THE SKOLEM-MAHLER-LECH THEOREM

TERENCE TAO

Abstract. We present a proof of the Skolem-Mahler-Lech theorem, which asserts that the zero set of the coefficients of a rational series must be ultimately periodic.

1. Statement of theorem

A basic fact in algebra is that if P (x) = ∑_{j=0}^{d} c_{j}x^{j} is a polynomial, then P either has finitely many zeroes, or is identically zero. One can then ask if the same is true if P (x) is generalized to more complicated objects, for instance an exponential polynomial of the form

P (x) = ∑_{k=0}^{m} P_{k}(x)λ_{k}^{x}  (1)

where for each k, λ_{k} is a non-zero complex number and P_{k} is a polynomial. (We will not concern ourselves with the branch cuts for λ_{k}^{x} as x will soon be restricted to be a positive integer). Now it is possible to have infinitely many zeroes without being identically zero; for instance the exponential polynomial sin(πx) = (e^{πix}−e^{−πix})/2i has zeroes at every integer, and the slight variant x sin(πx)−1 has zeroes near every integer.

On the other hand, a remarkable theorem of Skolem, Mahler, and Lech asserts that if x is restricted to be a positive integer, x = n ∈ Z_{+}, then the zero set of P (n) becomes highly structured. Indeed:

Theorem 1.1 (Skolem-Mahler-Lech theorem). [5], [3], [1], [4] If P is an exponential polynomial, then the set Γ = {n ∈ Z_{+} : P (n) = 0} is strongly eventually periodic (i.e. there exists some periodic subset A of Z and some finite subset F of Z^{+} such that Γ = (A ∩ Z^{+}) ∪ F.

Conversely, it is easy to see that given any strongly eventually periodic set Γ in Z_{+} there exists an exponential polynomial P such that Γ = {n ∈ Z_{+} : P (n) = 0}.

This theorem can be reformulated in a number of ways. Observe that if P is an exponential polynomial (1), then the numbers P (n) form the coefficients of the Taylor series of a rational function (i.e. the quotient of two polynomials):

1991 Mathematics Subject Classification. 35J10.

∑_{n=0}^{∞} P (n)z^{n} = ∑_{k=0}^{m} P_{k}(z \frac{d}{dz})(1 − λ_{k}z)^{−1}.  (2)

Conversely, it is easy to see by partial fractions (and the fundamental theorem of algebra) that the coefficients of the Taylor series of a rational function are always given by an exponential polynomial after at most a finite number of terms. Thus the Skolem-Mahler-Lech theorem asserts that the zero set of the Taylor series of a rational function is eventually periodic (equal to a periodic set on Z^{+} modulo finitely many terms).

Another formulation involves the coefficients of the powers of a fixed linear transformation on a finite dimensional space (or equivalently, a square matrix). For each k, let V_{k} be the deg(P_{k}) + 1-dimensional space spanned by basis elements e_{k,0}, …, e_{k,deg(P_{k})}, and let T_{k} : V_{k} → V_{k} be the linear transformation given on basis elements by

T_{k}e_{k,i} := λ_{k}e_{k,i} + e_{k,i+1}

with the understanding that e_{k,deg(P)+1} = 0 (this is of course one block of a Jordan canonical form). Then an easy induction shows that

T_{k}^{n}e_{k,0} = ∑_{i=0}^{deg(P)} λ_{k}^{n−i}\binom{n}{i}e_{k,i}

where \binom{n}{i} := \frac{n(n−1)...(n−i+1)}{i!} is the usual binomial coefficient. Thus the coefficients of T_{k}^{n}e_{k,0} are of the form \binom{n}{i}λ_{k}^{n} for i = 0, …, deg(P_{k}). Since each \binom{n}{i} is a polynomial in n of degree i, it is then easy to see that one can write the expression P_{k}(n)λ_{k}^{n} as a linear combination of matrix coefficients of T_{k}^{n}e_{k,0}. If one lets V be the direct sum of all the V_{k}, and T to be the direct sum of all the T_{k}, and e_{0} to be the direct sum of all the e_{k,0} we thus see that P (n) is a linear combination of the matrix coefficients of T^{n}. In other words, we have a representation of the form

P (n) = ⟨f_{0}, T^{n}e_{0}⟩

where ⟨f_{0}, ·⟩ is some linear functional on V (or, if one endows V with a Hilbert space structure, one can think of f_{0} as another element of V). Conversely, given any finitedimensional complex vector space V, any linear transformation T : V → V, any element e_{0} ∈ V and any linear functional ⟨f_{0}, ·⟩ on V, the quantity ⟨f_{0}, T^{n}e_{0}⟩ is an exponential polynomial in n after at most finitely many terms (this can be most easily seen by using the Jordan canonical form for T; alternatively, one can observe that ⟨f_{0}, (1−T z)^{−1}e_{0}⟩ is a rational function of z thanks to Cramer’s rule, and then extract Taylor coefficients.).

2. p-adic polynomial series

The key tool in proving the Skolem-Mahler-Lech theorem is a p-adic generalization of the statement that a polynomial is either identically zero, or has a finite number of zeroes. Recall that if p is a prime number, the p-adic numbers Q_{p} are the closure of the rational Q under the metric ∥a/b∥_{Q_{p}} := p^{d(b)−d(a)}, where p^{d(a)} is the largest power of p that divides an integer a (with the convention d(0) = +∞). Observe that the unit ball Z_{p} := {x ∈ Q_{p} : ∥x∥_{Q_{p}} ≤ 1} of Q_{p} contains the integers, is complete, and is a subring of Q_{p}.

Definition 2.1. We say that a function P : Z_{p} → Z_{p} has a p-adically bounded polynomial series if it has a series expansion of the form

P (n) := ∑_{j=0}^{∞} p^{j}P_{j}(n),

where for each j, P_{j}(n) is a polynomial in n whose coefficients lie in Z_{p}. (This series expansion is not necessarily unique).

Observe that if P (n) has a p-adically bounded polynomial series, then P_{j}(n) ∈ Z_{p} for all n ∈ Z_{p}, and hence the series is always convergent in Z_{p} for all n ∈ Z_{p}. Next, we observe

Lemma 2.2 (Factor theorem). If P (n) has a p-adically bounded polynomial series, and P (n_{0}) = 0 for some n_{0} ∈ Z_{p}, then there exists a function Q(n) with p-adically bounded polynomial series such that P (n) = (n − n_{0})Q(n) for all n ∈ Z_{p}.

Proof This follows by writing

P (n) = P (n) − P (n_{0}) = ∑_{j=0}^{∞} p^{j}(P_{j}(n) − P_{j}(n_{0}))

and noting that P_{j}(n) − P_{j}(n_{0}) factors as (n − n_{0})Q_{j}(n) for some polynomial Q_{j} with coefficients in the ring Z_{p} (since n^{k} − n_{0}^{k} = (n − n_{0})(n^{k−1} + n^{k−2}n_{0} + … + nn_{0}^{k−2} + n_{0}^{k−1})).

Corollary 2.3. If P (n) has a p-adically bounded polynomial series which has an infinite number of zeroes in Z_{p}, then we have P (n) = pP̃(n) for some function P̃ with p-adically bounded polynomial series. In particular, P (n) ∈ pZ_{p} for all n ∈ Z_{p}.

Proof Observe that in proof of the Factor theorem, that Q_{0}(n) is either identically zero, or has degree one less than that of P_{0}(n); since P has infinitely many zeroes in Z_{p}, so does Q. Since the degree of P_{0}(n) is initially finite, we can thus iterate the Factor theorem a finite number of times to yield a factorization P (n) = (n − n_{0}) … (n − n_{k})Q(n) where Q_{0}(n) is identically zero; at this point the claim follows since one can pull a factor p out of Q(n).

Iterating the above corollary indefinitely we see that if P (n) has an infinite number of zeroes in Z_{p}, then P (n) ∈ p^{j}Z_{p} for all j = 0, 1, …; thus P (n) ≡ 0 for all Z_{p}. We have thus established the following dichotomy:

Corollary 2.4. If P (n) has a p-adically bounded polynomial series, then either P is identically zero on Z_{p}, or P has at most finitely many zeroes.

We now apply this to prove a certain special case of the Skolem-Mahler-Lech theorem, in which the matrix T is the identity modulo a prime p.

Proposition 2.5. Let V = C^{d} be a vector space, and let e_{0}, f_{0} ∈ Z^{d} be vectors in V with integer co-ordinates. Let T : V → V be a linear transformation whose matrix coefficients are all integers; in fact, suppose that T = I + pS where p is an odd prime number, I is the identity transformation, and S is another linear transformation with integer co-efficients. Then the set {n ∈ Z_{+} : ⟨f_{0}, T^{n}e_{0}⟩ = 0} is either finite, or equal to all of Z_{+}.

Proof By the binomial formula we have

⟨f_{0}, T^{n}e_{0}⟩ = ∑_{j=0}^{∞} p^{j} \frac{n(n − 1) … (n − j + 1)}{j!}⟨f_{0}, S^{j}e_{0}⟩.

for all n ∈ Z_{+}. The right-hand side is almost a p-adically bounded polynomial series, but is not quite because the denominator j! can contain multiples of p. However, the number of powers of p that divide j! is at most j/p + j/p^{2} + … ≤ j/(p − 1) ≤ j/2, and thus the net power of p dividing the j^{th} term in the series is at least j/2. Thus one can rewrite this series in the form of a p-adically bounded polynomial series by grouping together consecutive pairs of terms. The claim now follows from the preceding Corollary.

This proposition then quickly generalizes to the arbitrary rational-valued case:

Corollary 2.6. Let V = C^{d} be a vector space, and let e_{0}, f_{0} ∈ Q^{d} be vectors in V with rational co-ordinates. Let T : V → V be a linear transformation whose matrix coefficients are all rationals. Then the set {n ∈ Z_{+} : ⟨f_{0}, T^{n}e_{0}⟩ = 0} is eventually periodic.

Proof If det(T) = 0, then T has a non-trivial generalized eigenspace, which can be spanned by vectors with rational coefficients since T has rational coefficents. One can then quotient out this generalized eigenspace, which has the effect of reducing to the case when det(T) ≠ 0, so T is invertible. Next, by multiplying T by a large integer M (the product of all the denominators in the coefficients of T, e_{0}, and f_{0}) we may assume that T, e_{0}, f_{0} all have integer coefficients; note that T is still invertible. In particular, if p is a sufficiently large odd prime (e.g. p > | det(T)|) then T will also be invertible modulo p. Since the set of d × d invertible matrices with entries in Z_{p} is a finite multiplicative group, we thus see from Cauchy’s little theorem (or the pigeonhole principle) that there exists an integer m such that T^{m} = 1 + pS for some linear transformation S with integer entries. If one splits Z_{+} into residue classes modulo m and applies the preceding proposition to each such residue class {n = mn′ + a : n′ ∈ Z_{+}}, for all a = 0, …, m − 1, we see that {n′ ∈ Z_{+} : ⟨f_{0}, T^{mn′}T^{a}e_{0}⟩ = 0} is either finite or equal to all of Z_{+}, and the claim follows.

Now we generalize to the algebraic case:

Corollary 2.7. Let V = C^{d} be a vector space, and let e_{0}, f_{0} ∈ \overline{Q}^{d} be vectors in V whose coefficients are algebraic numbers. Let T : V → V be a linear transformation whose matrix coefficients are all algebraic numbers. Then the set {n ∈ Z_{+} : ⟨f_{0}, T^{n}e_{0}⟩ = 0} is eventually periodic.

Proof Let F be the field generated by all the coefficients of e_{0}, f_{0}, T. This is a finite-dimensional vector space over Q, and so by choosing some arbitrary basis of F over Q and re-expressing e_{0}, f_{0}, T in that basis, we can deduce the result from the preceding Corollary (with a larger dimension d, of course).

Moving back to exponential polynomials, call an exponential polynomial (1) algebraic if the exponents λ_{k}, and all the coefficients of the polynomials P_{k} are algebraic numbers. Then we have shown that whenever P is an algebraic exponential polynomial, the set {n ∈ Z_{+} : P (n) = 0} is eventually periodic. We now prove a variant of this fact.

Proposition 2.8. If P is an algebraic exponential polynomial with no ratio λ_{k}/λ_{k′} equal to a root of unity, and with at least one polynomial P_{k}(n) not identically zero, then the set {n ∈ Z_{+} : P (n) = 0} is finite.

Proof We already know that the set {n ∈ Z_{+} : P (n) = 0} is eventually periodic, so if it is infinite, then there exists a coset {mn′ + a : n′ ∈ Z_{+}} on which P (n) vanishes on all but finitely many elements of this coset. In particular, the series

∑_{n′=0}^{∞} P (mn′ + a)z^{n′}

is a polynomial in z. But by (2) we have

∑_{n′=0}^{∞} P (mn′ + a)z^{n′} = ∑_{k=0}^{m} λ_{k}^{a}P_{k}(mz \frac{d}{dz} + a)(1 − λ_{k}^{m}z)^{−1}.  (3)

Let P_{k_{0}}(n) be one of the component polynomials of P which is not identically zero. Then the right-hand side of (3) must have a non-trivial pole at 1/λ_{k_{0}}^{m} (recall that this is distinct from all the other 1/λ_{k}^{m} by hypothesis), contradicting the previous assertion that it was a polynomial.

Now, we remove the constraint that P is algebraic.

Proposition 2.9. If P is an exponential polynomial with no ratio λ_{k}/λ_{k′} equal to a root of unity, and with at least one polynomial P_{k}(n) not identically zero, then the set {n ∈ Z_{+} : P (n) = 0} is finite.

Proof Observe that while the coefficients and exponents of P ostensibly live in C, we can in fact work entirely in the smaller algebraically closed subfield \overline{Q[λ_{k}, c_{k,j}]} generated by the exponents λ_{k} and the coefficients c_{k,j} of P_{k}. This field can be given a transcendence basis, and is thus equal to \overline{Q[z]} for some m-tuple z = (z_{1}, …, z_{m}) of algebraically independent complex numbers; thus each of the λ_{k} and c_{k,j} are zeroes of some non-trivial irreducible rational polynomial involving z. In particular, one can let z range over (a Zariski-open subset of) C^{m}, and think of the quantities (λ_{k}, c_{k,j}) as ranging in some algebraic Riemann surface, and which finitely covers the Zariski-open subset of C^{m}; we may pass to a connected component and assume this Riemann surface is connected. The quantity P (n) can then be thought of as an algebraic function on this Riemann surface, which vanishes above every transcendental point z in the Zariski-open subset of C^{m}, and hence vanishes on the entire Riemann surface. Now let z_{0} be a generic algebraic element of the Riemann surface. Observe that if λ_{k}/λ_{k′} was always restricted to the unit circle, then it would be constant (by analyticity), and hence never a root of unity by hypothesis; otherwise, if λ_{k}/λ_{k′} is not restricted to the unit circle, then it will not be a root of unity for generic points on the Riemann surface. Thus we may assume that at z_{0}, none of the λ_{k}/λ_{k′} are roots of unity. We then Taylor expand P (n) around z_{0} and observe that each one of the Taylor coefficients is an exponential polynomial in n whose coefficients are all algebraic numbers. Applying Proposition 2.8 in the algebraic case we thus conclude that each of the Taylor coefficients of P (n) either vanishes for only finitely many n, or vanishes for all n ∈ Z_{+}. Putting this together (and using unique continuation) we conclude that P (n) itself either vanishes on the Riemann surface for only finitely many n, or vanishes for all n ∈ Z_{+}. The latter case is not possible by repeating the Laurent series argument used to prove Proposition 2.8. The claim follows.

Finally, Theorem 1.1 follows from Proposition 2.9, because if two of the λ_{k} differ by a N^{th} root of unity, one can split n into N residue classes mod N, and on each such residue class P (n) can be given as an expression of the form (1) but with one less term. The claim can then be deduced by induction.

Remark 2.10. The above arguments also give an upper bound on the period m of the eventually periodic set Γ in terms of the coefficients of P. However, it is not known whether there is an effective procedure to determine exactly what Γ is, or even if Γ is non-empty. The difficulty lies in the p-adic component of the argument, where we showed that a p-adically bounded polynomial series either vanishes identically or has at most finitely many zeroes; the problem is that in the latter case, while the p-adic digits of the zeroes can be worked out iteratively, no effective procedure is known to determine whether these zeroes are integers or not. (This question was posed by Kousha Etessami).

Acknowledgement. We thank Kousha Etessami and Tom Lenagan for drawing the author’s attention to the Skolem-Mahler-Lech theorem. The argument here is loosely based on that in [2].

References

[1] C. Lech, A note on recurring series, Arkiv fur Matematik, Band 2 nr 22 (1953), 417–421.

[2] G. Hansel, A simple proof of the Skolem-Mahler-Lech theorem, Automata, languages and programming (Nafplion, 1985), 244–249, Lecture Notes in Comput. Sci., 194, Springer, Berlin, 1985.

[3] K. Mahler, Eine arithmetische Eigenshaft der Taylor coefficienten rationaler Funktionen, Proc. Acad. Sci. Amst. 38 (1935), 51–60.

[4] K. Mahler, On the Taylor coefficients of rational functions, Proc. Cambridge Philos. Soc. 52 (1956), 39–48.

[5] T. Skolem, Einige Sätze über gewisse Reihenentwichlungen und exponentiale Bezeihungen mit Anwendung auf diophantische Gleichungen, Oslo Vid. Akad. Skriften I. 6 (1933).

THE SKOLEM-MAHLER-LECH THEOREM 7

Department of Mathematics, UCLA, Los Angeles CA 90095-1555

E-mail address: tao@math.ucla.edu