Top Qs
Timeline
Chat
Perspective

Skolem–Mahler–Lech theorem

The zeros of a linear recurrence relation mostly form a regularly repeating pattern From Wikipedia, the free encyclopedia

Remove ads

In algebraic number theory, the Skolem–Mahler–Lech theorem states that if a sequence of numbers satisfies a linear recurrence with constant coefficients, 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),[1] Kurt Mahler (who proved it for sequences of algebraic numbers),[2] and Christer Lech (who proved it for sequences with values in any field of characteristic zero.[3] Its known proofs use p-adic analysis and are non-constructive.

Remove ads

Theorem statement

Let be a field of characteristic zero, such as the field of complex numbers . Let be a constant-recursive sequence with values in , i.e., a sequence satisfying a recurrence relation of the form

where . Then the zero set is equal to the union of finitely many arithmetic progressions and a finite set.

If (excluding sequences such as 1, 0, 0, 0, …), then the set of zeros is in fact equal to the union of a finite set and finitely many full arithmetic progressions, where 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.

Remove ads

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 (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.

Remove ads

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,[4] 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.[5]

References

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads