词条 | Skolem–Mahler–Lech theorem |
释义 |
In additive number theory, the Skolem–Mahler–Lech theorem states that if a sequence of numbers is generated by a linear recurrence relation, then with finitely many exceptions the positions at which the sequence is zero form a regularly repeating pattern. More precisely, this set of positions can be decomposed into the union 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. 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 proofs use p-adic analysis. ExampleConsider 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 (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 resultsThe 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, 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 {{harv|Ouaknine|Worrell|2012}}. References
| last1 = Ouaknine | first1 = Joël | last2 = Worrell | first2 = James | contribution = Decision problems for linear recurrence sequences | doi = 10.1007/978-3-642-33512-9_3 | mr = 3040104 | pages = 21–28 | publisher = Springer-Verlag | location = Heidelberg | series = Lecture Notes in Computer Science | title = Reachability Problems: 6th International Workshop, RP 2012, Bordeaux, France, September 17-19, 2012, Proceedings | volume = 7550 | year = 2012}}. External links
4 : Theorems in number theory|Algebraic number theory|Additive number theory|Recurrence relations |
随便看 |
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。