Skolem-Mahler-Lech theorem

A recurrence sequence $ ( a _ {h} ) $ of order $ n $ is a solution to a linear homogeneous recurrence relation with constant coefficients

$$ a _ {h + n } = s _ {1} a _ {h + n - 1 } + \dots + s _ {n} a _ {h} ( h = 0,1, \dots ) . $$

Thus, the generating function $ \sum _ {h \geq 0 } a _ {h} X ^ {h} $ of a recurrence is a rational function $ { {r ( X ) } / {s ( X ) } } $ where $ s ( X ) = 1 - s _ {1} X - \dots - s _ {n} X ^ {n} = \prod _ {i = 1 } ^ {m} ( 1 - \alpha _ {i} X ) ^ {n _ {i} } $, say; the polynomial $ r $ of degree less than $ n $ is determined by the initial values $ a _ {0}, \dots, a _ {n - 1 } $. If so, the distinct complex numbers $ \alpha _ {i} $ are called the roots of the recurrence, and the $ n _ {i} $ their multiplicities. It follows that the $ a _ {h} $ are given by a generalized power sum $ a _ {h} = a ( h ) = \sum _ {i = 1 } ^ {m} A _ {i} ( h ) \alpha _ {i} ^ {h} $ ($ h = 0,1, \dots $); the polynomial coefficients $ A _ {i} $ are respectively of degree $ n _ {i} - 1 $.

The theorem of Skolem–Mahler–Lech asserts that if a recurrence (equivalently, a generalized power sum) has infinitely many zeros, then those zeros occur periodically. That is, given a power series $ \sum _ {h \geq 0 } a _ {h} X ^ {h} $ representing a rational function with infinitely many zero Taylor coefficients, the set $ \{ h : {a _ {h} = 0 } \} $ is a finite union of complete arithmetic progressions (cf. Arithmetic progression), plus (a pre-period of) finitely many isolated zeros. By virtue of Ritt's quotient theorem [a6], it is equivalent that an infinitude of integer zeros of a complex exponential polynomial $ a ( z ) = \sum _ {i = 1 } ^ {m} A _ {i} ( z ) \exp ( z \log \alpha _ {i} ) $ is accounted for by it being divisible (in the ring of exponential polynomials) by functions $ \sin { {2 \pi ( z - r ) } / d } $.

Skolem's argument was generalized by K. Mahler to algebraic number fields, and eventually to arbitrary fields of characteristic zero by C. Lech and by Mahler. The elegant argument of J.W.S. Cassels [a1] bypasses the technical complications in the chain of successive generalizations. In brief, one observes that there are rational primes $ p $ so that (technically, after embedding the data in the field $ \mathbf Q _ {p} $ of $ p $-adic rationals) one has $ \alpha _ {i} ^ {p - 1 } \equiv 1 ( \mod p ) $ for each root. Then, for $ 0 \leq r < p - 1 $, each of the $ p - 1 $ different $ p $-adic exponential polynomials $ a ( r + t ( p - 1 ) ) = \sum _ {i = 1 } ^ {m} A _ {i} ( r + t ( p - 1 ) ) \alpha _ {i} ^ {r} \exp ( t \log \alpha _ {i} ^ {p - 1 } ) $ is a $ p $-adic analytic function in the disc $ \{ {t \in \mathbf Q _ {p} } : {| t | _ {p} < p ^ {1 - {1 / {( p - 1 ) } } } } \} $. It follows that if any one of these functions has infinitely many zeros (it turns out, as few as $ n $ zeros [a3]) in the unit disc, then it must vanish identically, yielding the theorem with arithmetic progressions with common difference $ d = p - 1 $. It follows that a recurrence sequence can have infinitely many zeros only if it is degenerate, that is, some quotient $ { {\alpha _ {i} } / {\alpha _ {j} } } $ of its distinct roots is a root of unity.

The theorem is provable without visible appeal to $ p $-adic analysis [a2]. But a generalization, whereby if two recurrence sequences have infinitely many elements in common then they coincide along certain of their arithmetic subprogressions (see [a4]), as yet, (1996) relies on a $ p $-adic generalization of Schmidt's subspace theorem. A different generalization, Shapiro's conjecture, according to which two exponential polynomials with infinitely many complex common zeros must have a common exponential polynomial factor, is still (1996) mostly conjecture [a5].

A general reference surveying this and other relevant material is [a7].

References

[a1]	J.W.S. Cassels, "An embedding theorem for fields" Bull. Austral. Math. Soc. , 14 (1976) pp. 193–198 (Addendum: 14 (1976), 479–480)
[a2]	G. Hansel, "Une démonstration simple du théorème de Skolem–Mahler–Lech" Theor. Comput. Sci. , 43 (1986) pp. 91–98
[a3]	A.J. van der Poorten, R.S. Rumely, "Zeros of -adic exponential polynomials II" J. London Math. Soc. (2) , 36 (1987) pp. 1–15
[a4]	A.J. van der Poorten, H.-P. Schlickewei, "Additive relations in fields" J. Austral. Math. Soc. , 51 (1991) pp. 154–170
[a5]	A.J. van der Poorten, R. Tijdeman, "On common zeros of exponential polynomials" L'Enseign. Math. Série , 21 (1975) pp. 57–67
[a6]	J.F. Ritt, "On the zeros of exponential polynomials" Trans. Amer. Math. Soc. , 31 (1929) pp. 680–686
[a7]	A.J. van der Poorten, "Some facts that should be better known; especially about rational functions" R.A. Mollin (ed.) , Number Theory and Applications , NATO ASI , Kluwer Acad. Publ. (1989) pp. 497–528