Skolem–Mahler–Lech theorem

Skolem–Mahler–Lech theorem In additive and algebraic number theory, the Skolem–Mahler–Lech theorem states that if a sequence of numbers satisfies a linear difference equation, then with finitely many exceptions the positions at which the sequence is zero form a regularly repeating pattern. This result is named after Thoralf Skolem (who proved the theorem for sequences of rational numbers), Kurt Mahler (who proved it for sequences of algebraic numbers), and Christer Lech (who proved it for sequences whose elements belong to any field of characteristic 0). Its known proofs use p-adic analysis and are non-constructive.

Contents 1 Theorem statement 2 Example 3 Related results 4 References 5 External links Theorem statement Let {displaystyle s(n)_{ngeq 0}} be a sequence of complex numbers satisfying {displaystyle s(n)=c_{1}s(n-1)+c_{2}s(n-2)+cdots +c_{d}s(n-d)} for all {displaystyle ngeq d} , where {displaystyle c_{i}} are complex number constants (i.e., a constant-recursive sequence of order {displaystyle d} ). Then the set of zeros {displaystyle {n;mid ;s(n)=0}} is equal to the symmetric difference of a finite set and finitely many full arithmetic progressions. Here, an infinite arithmetic progression is full if there exist integers a and b such that the progression consists of all positive integers equal to b modulo a. If additionally {displaystyle c_{d}neq 0} (excluding sequences such as 1, 0, 0, 0, ...), then the symmetric difference can be replaced by a union.

Example Consider the sequence 0, 0, 1, 0, 1, 0, 2, 0, 3, 0, 5, 0, 8, 0, ...

that alternates between zeros and the Fibonacci numbers. This sequence can be generated by the linear recurrence relation {displaystyle F(i)=F(i-2)+F(i-4)} (a modified form of the Fibonacci recurrence), starting from the base cases F(1) = F(2) = F(4) = 0 and F(3) = 1. For this sequence, F(i) = 0 if and only if i is either one or even. Thus, the positions at which the sequence is zero can be partitioned into a finite set (the singleton set {1}) and a full arithmetic progression (the positive even numbers).

In this example, only one arithmetic progression was needed, but other recurrence sequences may have zeros at positions forming multiple arithmetic progressions.

Related results The Skolem problem is the problem of determining whether a given recurrence sequence has a zero. There exist an algorithm to test whether there are infinitely many zeros,[1] and if so to find the decomposition of these zeros into periodic sets guaranteed to exist by the Skolem–Mahler–Lech theorem. However, it is unknown whether there exists an algorithm to determine whether a recurrence sequence has any non-periodic zeros (Ouaknine & Worrell 2012).

References ^ Berstel, Jean; Mignotte, Maurice (1976). "Deux propriétés décidables des suites récurrentes linéaires". Bulletin de la Société Mathématique de France. 104: 175–184. Skolem, Th. (1933), "Einige Sätze über gewisse Reihenentwicklungen und exponentiale Beziehungen mit Anwendung auf diophantische Gleichungen", Oslo Vid. akad. Skrifter, I (6), cited in Lech 1953. Mahler, K. (1935), "Eine arithmetische Eigenschaft der Taylor-Koeffizienten rationaler Funktionen", Akad. Wetensch. Amsterdam, Proc., 38: 50–60, cited in Lech 1953. Lech, C. (1953), "A Note on Recurring Series", Arkiv för Matematik, 2: 417–421, doi:10.1007/bf02590997. Mahler, K. (1956), "On the Taylor coefficients of rational functions", Proc. Cambridge Philos. Soc., 52: 39–48, doi:10.1017/s0305004100030966. Mahler, K. (1957), "Addendum to the paper "On the Taylor coefficients of rational functions"", Proc. Cambridge Philos. Soc., 53: 544, doi:10.1017/s0305004100032552. Ouaknine, Joël; Worrell, James (2012), "Decision problems for linear recurrence sequences", Reachability Problems: 6th International Workshop, RP 2012, Bordeaux, France, September 17-19, 2012, Proceedings, Lecture Notes in Computer Science, vol. 7550, Heidelberg: Springer-Verlag, pp. 21–28, doi:10.1007/978-3-642-33512-9_3, MR 3040104. External links Weisstein, Eric W. "Skolem-Mahler-Lech Theorem". MathWorld. Categories: Theorems in number theoryAlgebraic number theoryAdditive number theoryRecurrence relations

Si quieres conocer otros artículos parecidos a Skolem–Mahler–Lech theorem puedes visitar la categoría Additive number theory.

Deja una respuesta

Tu dirección de correo electrónico no será publicada.


Utilizamos cookies propias y de terceros para mejorar la experiencia de usuario Más información