View source for Skolem-Mahler-Lech theorem

A recurrence sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s1101601.png" /> of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s1101602.png" /> is a solution to a linear homogeneous [[Recurrence relation|recurrence relation]] with constant coefficients

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s1101603.png" /></td> </tr></table>

Thus, the generating function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s1101604.png" /> of a recurrence is a rational function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s1101605.png" /> where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s1101606.png" />, say; the polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s1101607.png" /> of degree less than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s1101608.png" /> is determined by the initial values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s1101609.png" />. If so, the distinct complex numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s11016010.png" /> are called the roots of the recurrence, and the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s11016011.png" /> their multiplicities. It follows that the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s11016012.png" /> are given by a generalized power sum <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s11016013.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s11016014.png" />); the polynomial coefficients <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s11016015.png" /> are respectively of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s11016016.png" />.

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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s11016017.png" /> representing a rational function with infinitely many zero Taylor coefficients, the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s11016018.png" /> is a finite union of complete arithmetic progressions (cf. [[Arithmetic progression|Arithmetic progression]]), plus (a pre-period of) finitely many isolated zeros. By virtue of Ritt's quotient theorem [[#References|[a6]]], it is equivalent that an infinitude of integer zeros of a complex exponential polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s11016019.png" /> is accounted for by it being divisible (in the ring of exponential polynomials) by functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s11016020.png" />.

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 [[#References|[a1]]] bypasses the technical complications in the chain of successive generalizations. In brief, one observes that there are rational primes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s11016021.png" /> so that (technically, after embedding the data in the field <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s11016022.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s11016023.png" />-adic rationals) one has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s11016024.png" /> for each root. Then, for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s11016025.png" />, each of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s11016026.png" /> different <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s11016027.png" />-adic exponential polynomials <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s11016028.png" /> is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s11016029.png" />-adic analytic function in the disc <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s11016030.png" />. It follows that if any one of these functions has infinitely many zeros (it turns out, as few as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s11016031.png" /> zeros [[#References|[a3]]]) in the unit disc, then it must vanish identically, yielding the theorem with arithmetic progressions with common difference <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s11016032.png" />. It follows that a recurrence sequence can have infinitely many zeros only if it is degenerate, that is, some quotient <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s11016033.png" /> of its distinct roots is a root of unity.

The theorem is provable without visible appeal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s11016034.png" />-adic analysis [[#References|[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 [[#References|[a4]]]), as yet, (1996) relies on a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s11016035.png" />-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 [[#References|[a5]]].

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

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J.W.S. Cassels,   "An embedding theorem for fields"  ''Bull. Austral. Math. Soc.'' , '''14'''  (1976)  pp. 193–198  (Addendum: 14 (1976), 479–480)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  G. Hansel,   "Une démonstration simple du théorème de Skolem–Mahler–Lech"  ''Theor. Comput. Sci.'' , '''43'''  (1986)  pp. 91–98</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  A.J. van der Poorten,   R.S. Rumely,   "Zeros of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s11016036.png" />-adic exponential polynomials II"  ''J. London Math. Soc. (2)'' , '''36'''  (1987)  pp. 1–15</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  A.J. van der Poorten,   H.-P. Schlickewei,   "Additive relations in fields"  ''J. Austral. Math. Soc.'' , '''51'''  (1991)  pp. 154–170</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  A.J. van der Poorten,   R. Tijdeman,   "On common zeros of exponential polynomials"  ''L'Enseign. Math. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110160/s11016037.png" /> Série'' , '''21'''  (1975)  pp. 57–67</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  J.F. Ritt,   "On the zeros of exponential polynomials"  ''Trans. Amer. Math. Soc.'' , '''31'''  (1929)  pp. 680–686</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  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</TD></TR></table>