P-adics and Linear Recurrences

(Jit here).

Today I want to explain how to prove Skolem-Mahler-Lech using the p-adic numbers, and explain some sort of generalization in the area of algebraic/arithmetic dynamics, known as the Dynamical Mordell-Lang conjecture, which is still an open problem.

Let's first start off with Skolem-Mahler-Lech. The theorem says the following: start with a sequence $(a_n)$ that satisfies some sort of linear recurrence

$$a_n = c_1 a_{n-1} + \cdots + c_k a_{n-k}$$

where $c_i$ are possibly complex numbers. We are then interested in what the set $\{n \mid a_n = 0 \}$ looks like. Skolem-Mahler-Lech says that in fact, this set is a finite union of arithmetic progressions (here the arithmetic progressions can be of difference 0, i.e. just a single term A.P.). 

Why arithmetic progressions? One obvious way that we can have infinitely many zeroes without being the zero sequence is that our linear recurrence is secretly two linear recurrences glued together. For example, consider the sequence $a_n = a_{n-2} + a_{n-4}$. Then essentially the even terms $a_{2n}$ and the odd terms $a_{2n-1}$ do not interact with each other and so this is secretly two different linear recurrences combined into one. We can just set one of them to be the zero sequence and another to be the Fibonacci and obtain an arithmetic progression worth of zeroes.

So the theorem is sort of saying if you had an "irreducible" linear recurrence (whatever that means), if it is zero infinitely many times then it is actually just the zero sequence. Let's plug in the formula for a linear recurrence: we know that there are constants $r_1,\ldots,r_k$ along with polynomials $P_1(x),\ldots, P_k(x)$ such that

$$a_n = P_1(n) r_1^n + \cdots + P_k(n)r_k^n$$

for all $n \geq k$. Now this naturally defines for us a function by replacing $n$ with $z$, giving us

$$f(z) = P_1(z)r_1^z + \cdots + P_k(z)r_k^z.$$

If $f(z)$ was just a polynomial, we know that having infinitely many zeroes would imply only it is actually the zero function. Clearly $f(z)$ is not a polynomial, but at least it is a power series 

$$f(z) = b_0 + b_1 z + \cdots + b_n z^n + \cdots$$

giving by the Taylor series of 

$$e^z = 1 + z + \frac{z^2}{2!} + \cdots.$$

Now, it is a theorem that if a convergent power series $g(z)$ has a sequence of zeroes $\{x_i\}$ that converge to some limit point $x$, then actually $g(z)$ must be the zero power series. This is not hard to prove, we expand $g(z)$ as a power series with $x$ as a center, and say we obtain 

$$g(z+ \delta) = b_0 + b_1 \delta + \cdots .$$

If $b_0$ was non-zero, if $|\delta|$ was small enough, it would be impossible for the remaining terms $b_i \delta^i$ to be larger than $b_0$ (this is where we require that the power series is convergent!) and so it would be non-zero for $\delta$ small enough and so there is no zero near $z$. Similarly if $b_0$ was zero but $b_1$ wasn't, then $b_1 \delta$ would dominate the other terms and so again, there cannot be a zero near $z$. The same argument applies in general.

We would like to apply this theorem, but we run into a problem - there is no sequence for which our natural numbers is converging to. In fact, they are "escaping" into $\infty$, which is possible to be made precise but I won't bother. As a counterexample to this approach, we can consider the function $e^z - 1$. This is clearly a non-zero function, but it has infinitely many zeroes given by $z = 2 k \pi i$ for natural numbers $k$. These zeroes escape to $\infty$ and so there is no contradiction to our theorem above. 

---

Is there a way to remedy this? It turns out they key idea is that the natural numbers are actually a bounded set, but only if one considers the $p$-adic topology instead of the usual distance metric. Then since they form a bounded set, any subsequence necessarily has a convergent subsequence, and applying the $p$-adic analogue of our theorem of power series having a convergent sequence of zeroes, we are done. 

Let's try to define this $p$-adic topology. Fix a prime number $p$. The main idea is that we are going to define a metric on the natural numbers such that the prime number $p$ is going to be small, and all other numbers uninvolved with $p$ will be sort of constant size. For example since $p$ is small, it is necessary that $2p$ is small (it is like a constant multiplied by a small number). Also, $p^2$ is going to be even smaller than $p$ and $p^3$ even smaller. In particular, $p^n$ converges to $0$ as $n$ goes to infinity. 

To make this precise, we formally define a distance $| \cdot |_p$ by saying

$$|a|_p = \frac{1}{p^{v_p(a)}}$$

where $v_p(a)$ is the exponent of $p$ dividing $a$. This defines a distance metric between natural numbers and we can then form what is known as the "completion" to get the $p$-adic integers $\mathbb{Z}_p$. The completion is the process of getting the reals $\mathbb{R}$ from the rationals $\mathbb{Q}$ and in some sense we are filling in all the holes. As a rough idea of how this goes, given any sequence that looks like it should converge, we should add in an extra point so that it converges. For example, the sequence $1, 1+p, 1+p+p^2,\ldots$ should converge, and so there should exist a number $x$ representing $1+p+p^2+ \cdots$. In fact, this number turns out to just be $\frac{1}{p-1}$ since 

$$(p-1)(1 + p + p^2 + \cdots ) = 1.$$

In particular, every $p$-adic integer can be described as an infinite $p$-adic expansion 

$$x = a_0 + a_1p + \cdots + a_n p^n + \cdots$$

with $a_i \in \{0,1,\ldots,p-1\}$ and every such infinite $p$-adic expansion gives us a number. Another example is that $\sqrt{7}$ is actually in $\mathbb{Z}_3$. Let's think about how to construct it. If 

$$\sqrt{7} = a_0 + a_1p + \cdots + a_np^n + \cdots,$$

then we must have that 

$$a_0^2 \equiv 7 \pmod p, (a_0 + a_1 p )^2 \equiv 7 \pmod p^2, \ldots$$

Can this be achieved for $p = 3$? Turns out we can find such $a_i$'s by Hensel's lemma. We have to solve $x^2 \equiv 7 \pmod 3$, which is possible for example by taking $x = 1$. Now to lift it to a solution to mod $p^2$ and $p^3$ and so on, Hensel's lemma states that we need the derivative of $x^2 - 7$ to not be a multiple of $3$ when $x = 1$, and this is simply just $2x = 2$. So we can apply Hensel's lemma which allows us to find $a_n$ such that

$$(a_0 + a_1 p + \cdots + a_n p^n)^2 \equiv 7 \pmod {p^{n+1}}$$

for all $n$, giving us an expansion of $\sqrt{7}$. 

Now let's assume for simplicity that the coefficients of the polynomials $P_i(n)$ and exponentials $r_i$'s are all algebraic numbers. Just like the example of $\sqrt{7} \in \mathbb{Z}_3$ it is always possible to choose a prime $p$ such that any finite set of algebraic numbers you have lie in $\mathbb{Z}_p$. This is just an application of Hensel's lemma and choosing a prime $p$ such that the minimal polynomials of these algebraic numbers all have a zero (possible by Chebatorev's density theorem). In particular,  we can choose $p$ such all these coefficients of $P_i(n)$ and exponentials lie in $\mathbb{Z}_p$. Then 

$$f(z) = P_1(z)r_1^z + \cdots + P_n(z)r_n^z$$

sort of makes sense as a $p$-adic power series, once we can define what $a^z$ should be for a $p$-adic number $a$. It turns out the $p$-adic exponential only makes sense once $a$ is close to $1$, i.e. say if $|a-1|_p < \frac{1}{p}$. Once we have this, we can define

$$a^n = ((a-1) + 1)^n =  \sum_{k=0}^{n} \binom{n}{k} (a-1)^k.$$

We can then replace $n$ with $k$ by defining the binomial coefficient

$$\binom{z}{k} = \frac{z(z-1) \cdots (z-k+1)}{k!}$$

and define the $p$-adic exponential $a^z$ as 

$$a^z = \sum_{k=0}^{\infty} \binom{z}{k} (a-1)^k.$$

Since $|a-1|$ is small, the function $a^z$ will then converge for any $p$-adic integer $z$. Finally we are done - we first split up $f(z)$ into the functions

$$f(1 + (p-1)z), f(2+ (p-1)z), \ldots, f( (p-1)z),$$

which replaces our exponents $r_i^z$ with $r_i^i  (r_i^{p-1})^z$. In particular, by Fermat's little theorem we know that $|r_i^{p-1} - 1|_p < \frac{1}{p}$. We are then in position to expand this as a convergent power series in $z$ for $|z| \leq 1$. Finally, the natural numbers are bounded and so we can choose a convergent subsequence for any infinite sequence of natural numbers (just imagine picking a subsequence with all the same residue mod $p$, then further choosing the same mod $p^2$ and so on). We can then apply the analogue of the power series theorem that says that if a convergent $p$-adic power series has a sequence of zeroes that converge to some point, then it must be the zero power series, finishing the proof of Skolem-Maher-Lech.

---

We now mention the more general Dynamical Mordell-Lang conjecture, or at least a special case of it. Start with the $n$-space $\mathbb{C}^n$ and consider a subvariety $V$, i.e. the set cut out by a finite set of polynomial equations 

$$P_1(x_1,\ldots,x_n) = P_2(x_1,\ldots,x_n) = \cdots = P_m(x_1,\ldots,x_n) = 0.$$

We start off with an map $f: \mathbb{C}^n \to \mathbb{C}^n$ written as

$$(x_1,\ldots,x_n) \mapsto (Q_1(x_1,\ldots,x_n), \ldots, Q_n(x_1,\ldots,x_n))$$

where again $Q_i$ are polynomials. Given a point $x \in \mathbb{C}^n$, we are interested in the set

$$\{n \mid f^n(x) \in V\}$$

and the Dynamical Mordell-Lang conjecture states that this should again be a finite union of arithmetic progressions. It takes some work to see it, but taking $V = \{x_n = 0\}$ and using $f$ as a linear transformation produces Skolem-Mahler-Lech as a special case. Thus we can imagine that this is some sort of highly non-linear version of Skloem-Mahler-Lech. This is still a problem that is wide open, and the most significant progress so far is the case of $n = 2$ which is solved by Junyi Xie in a 100 page paper. A brief sketch of the idea is that in the $2$-dimensional case,  we can actually tells a strong property about curves $V$ for which 

$$\{n \mid f^n(x) \in V \}$$

is an infinite set. These curves have infinitely many $S$-integral points and so by Siegel's theorem, they should have genus zero (topologically have no holes) and have at most $2$ points at infinity (this is a harder concept to describe, but you can imagine if we wanted to compactify it in the sense that the Riemann sphere is the compactification of $\mathbb{C}$, then we can only add at most two points). Then what is important is that $f(V), f^2(V),...$ the iterates of $V$ also satisfy the same property. Then by analyzing the dynamics at infinity, it is possible to show that this cannot be the case unless $V$ is a preperiodic curve. For higher dimensions, already the first step doesn't work as we do not know for which surfaces can we have infinitely many integer points or even a Zariski-dense set of integer points (this is the Lang-Vojta conjecture).

Also another interesting thing to note is that we only proved Skolem-Mahler-Lech for algebraic coefficients $c_i$, and not complex coefficients. To do it in general for complex coefficients, the idea is that being zero is an "algebraic" condition. In particular, if say these complex coefficients contained transcendental elements, say $\pi$, then after splitting them up according to a transcendence basis, the coefficients involving each element of this basis must evaluate to zero. In particular, the transcendental basis behaves like a variable $x$ and we can the basis to algebraic numbers which reduces us to the algebraic case.