The Skolem-Mahler-Lech theorem

March 18, 2010

The Skolem-Mahler-Lech theorem

Filed under: Math — cfranc @ 8:21 pm

Last week I began a series of posts on $p$ -adic interpolation, and promised to discuss an easily-stated theorem about integers with the curious property that all known proofs of it use $p$ -adic interpolation. This is the Skolem-Mahler-Lech theorem, and to state it we first need to recall some preliminaries on linear recurrences. Note that I’ll freely use more sophisticated language and techniques in this post than in my previous posts on interpolation.

Linear recurrences
A sequence of numbers $x_0, x_1, \ldots$ is said to satisfy a linear recurrence if there exist numbers $a_1, a_2, \ldots, a_d$ for some $d$ , such that the relation

$x_{n+d} = a_1x_{n + d-1} + a_2 x_{n+d-2} + \cdots + a_dx_n$

holds for all integers $n \geq 0$ . Without loss of generality, we may suppose that $a_d$ is nonzero. The data of a relation as above and the first $d$ values of a sequence uniquely determines a linear recurrence.

If we let $(\cdot, \cdot )$ denote the usual scalar product on real $d$ -space, then it is not too hard to show that there exists an invertible $d \times d$ -matrix $A$ and vectors $u, v$ in $\mathbb{R}^d$ such that $x_n = (A^nu,v)$ . If all terms in the sequence of $x_n$ ‘s are integers, and the coefficients $a_i$ are also integers, then $A$ , $u$ and $v$ may be taken to have integer entries. We call such a sequence an integer linear recurrence. The most famous example of such a sequence is the Fibonnaci sequence, which is defined by the simple recurrence $x_{n+2} = x_{n+1} + x_n$ . The Fibonnaci sequence increases monotonically, but in general linear recurrences can jump about. A natural question is to ask how frequently a linear recurrence can take on a given value. Basic to this is the structure of the zero set of the sequence:

$\{n \geq 0 ~|~ x_n = 0\}$ .

For the Fibonnaci sequence the zero set is empty. If you perform some simple tests then you’ll discover that the zero set of every integer linear recurrence is eventually periodic (perhaps of period $0$ , as in the Fibonnaci case). We turn now to proving this fact.

Statement and proof of the Skolem-Mahler-Lech theorem
Let’s first state the theorem in precise terms so that it’s clear what we are trying to show.

Theorem. Let $(x_n)$ be an integral linear recurrence. Then there exist a finite number of arithmetic progressions of positive integers, and a finite set of positive integers, such that the zero set of $(x_n)$ is the union of these sets. In particular, the zero set of an integral linear recurrence is eventually periodic.

This implies, for instance, that the prime numbers can’t be realized as the zero set of any integer linear recurrence. The prime number theorem asserts that the number of primes up to $x$ behaves like the function $x/\log x$ , and so is not eventually periodic. (Does one need the prime number theorem to argue this?)

The proof of the SML theorem that I’ll give was essentially lifted from Terrence Tao’s blog. He in turn essentially lifted it from this paper of Hansel.

Proof. First recall that we have an invertible matrix $A$ with integer entries, and two vectors $u$ and $v$ with integer entries, such that $x_n = (A^nu,v)$ for all integers $n \geq 0$ . We can reduce the matrix $A$ mod $p$ for any prime $p$ , and we’ll get an invertible matrix over the finite field with $p$ elements whenever $p$ does not divide the determinant of $A$ . Fix such a prime $p$ . Since $A$ is invertible mod $p$ , there exists an integer $k > 0$ such that $A^k \equiv 1 \pmod{p}$ , so that we can write $A^k = 1 + pB$ for some matrix $B$ with integer entries.

Using the integer $k$ found above, define partial zero sets:

$P_i = \{i + nk ~|~ x_{i + nk} = 0\}$ for $i = 0,1, \ldots, k-1$ .

We claim that each $P_i$ is either finite or equal to the entire arithmetic progression of numbers of the form $i + nk$ . By collecting the finite ones into a single set, one deduce the SML theorem. We thus fix a partial zero set $P_i$ and must show that it is finite or a full arithmetic progression.

Define an integer valued function on the positive integers by setting $f(n) = x_{i + nk}$ . The zeros of this function are precisely the partial zero set $P_i$ . We will show that $f(n)$ is a $p$ -adically continuous function, and thus interpolates to a continuous function on the $p$ -adic integers. In fact, we will show that $f(n)$ extends to an analytic function on the $p$ -adic integers. A nonzero analytic function on the compact space $\mathbb{Z}_p$ has finitely many zeros, and so the proof will be complete as soon as we can show that $f(n)$ interpolates to a $p$ -adic analytic function. For this we will make use of the identity $x_n = (A^nu,v)$ . Applying this to the definition of our function yields:

$f(n) = x_{i + nk} = (A^{i + nk}u,v) = ((A^k)^n(A^iu),v) = ((1 + pB)^n(A^iu),v)$

Now we apply the binomial theorem to $(1 + pB)^n$ to deduce that

$f(n) = \sum_{j = 0}^\infty \binom{n}{j} p^{j}(B^jA^iu,v)$ .

Such an expansion extends to a continuous function on $\mathbb{Z}_p$ since it is a uniform limit of polynomials (a somewhat more remarkable fact is that every continuous function on $\mathbb{Z}_p$ has an expansion in terms of binomial coefficients similar to the above expression; this is another theorem of Mahler). Since the coefficients to the right of the binomial coefficients get $p$ -adically small very quickly, one can show that this in fact defines an analytic function; this means that if you reexpress $f(n)$ as a power series in $n$ , then the coefficients of the resulting series go to zero $p$ -adically. Thus, $f(n)$ must either vanish identically or have finitely many zeros, since this is true of all analytic functions on $\mathbb{Z}_p$ . This concludes the proof of the SML theorem. $\square$

I really like this result because the statement of the SML theorem is very elementary, and yet the above proof uses $p$ -adic interpolation in a simple and beautiful way.

Leave a Comment »

No comments yet.

RSS feed for comments on this post.

Cam's Blog

March 18, 2010