Namespaces
Variants
Actions

Difference between revisions of "Skolem-Mahler-Lech theorem"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (fixing mathop)
 
(3 intermediate revisions by 2 users not shown)
Line 1: Line 1:
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
+
<!--
 +
s1101601.png
 +
$#A+1 = 35 n = 2
 +
$#C+1 = 35 : ~/encyclopedia/old_files/data/S110/S.1100160 Skolem\ANDMahler\ANDLech theorem
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
<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>
+
{{TEX|auto}}
 +
{{TEX|done}}
  
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" />.
+
A recurrence sequence  $  ( a _ {h} ) $
 +
of order  $  n $
 +
is a solution to a linear homogeneous [[Recurrence relation|recurrence relation]] with constant coefficients
  
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" />.
+
$$
 +
a _ {h + n }  = s _ {1} a _ {h + n - 1 }  + \dots + s _ {n} a _ {h}  ( h = 0,1, \dots ) .
 +
$$
  
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.
+
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 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]]].
+
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|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  $  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 [[#References|[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 [[#References|[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 [[#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 $  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 [[#References|[a5]]].
  
 
A general reference surveying this and other relevant material is [[#References|[a7]]].
 
A general reference surveying this and other relevant material is [[#References|[a7]]].

Latest revision as of 06:04, 12 July 2022


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
How to Cite This Entry:
Skolem-Mahler-Lech theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Skolem-Mahler-Lech_theorem&oldid=11813
This article was adapted from an original article by A.J. van der Poorten (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article