The Skolem-Pisot Problem Revisited
by
Bruce Litow
School of Maths, Physics and IT, James Cook University

The celebrated Skolem-Mahler-Lech (SML) Theorem asserts that over any field of characteristic zero the zero set of a linear recurrence is a semilinear set, i.e., a finite union of arithmetic progressions. If a₁ , ... is the sequence of terms of a linear recurrence, its zero set is the set of all i such that a_i = 0. It is known that SML can fail over positive characteristic fields. An example is due to Lech. Deciding whether the zero set is empty is known as the Skolem-Pisot (SP) problem. We are chiefly interested in the case of the field of rationals, Q. It is not known whether SP over Q is decidable. It is known that SP is decidable for recurrences up to order 5. There is a decidable relative of SP over Q, namely whether the zero set is infinite. Berstel and Mignotte exhibited a decision procedure for this problem. The worst-case running time appears to be slightly worse than simply exponential. In this paper we provide a polynomial time testable necessary condition that the zero set is infinite, and then characterize the computational bottleneck. This bottleneck makes it quite explicit why SML holds for Q. Unfortunately, since we use SML in proving the correctness of the necessary condition, we do not produce a new proof of SML, at least for Q.

PDF

Date received: March 13, 2007