On the $p$-adic Skolem Problem

A linear recurrence sequence (LRS) $𝒖={⟨u_n⟩}_{n=0}^{\mathrm{\infty }}$ is a sequence of integers satisfying a linear recurrence relation:

where $a_0,\mathrm{\dots },a_{d-1}\in \mathbb{Z}$ and $a_0\ne 0$. We call $d$ the order of the recurrence. If $d$ is the minimum order of a recurrence satisfied by $𝒖$ then we call $d$ the order of $𝒖$.

The zero set of an LRS $𝒖$ is $\{n\in \mathbb{N}:u_n=0\}$. The celebrated Skolem-Mahler-Lech theorem [26, 19, 17] states that the zero set is comprised of a union of a finite set and finitely many arithmetic progressions. The statement may be refined via the concept of non-degeneracy. Define the characteristic polynomial¹¹1Note that the minimal-order recurrence for an LRS $𝒖$ is unique, and so the characteristic polynomial of $𝒖$ is also unique. of the recurrence (1.1) to be

Let ${\lambda }_1,\mathrm{\dots },{\lambda }_s\in \overline{\mathbb{Q}}$ be the distinct roots of $g$; these are called the characteristic roots of $𝒖$. We say $𝒖$ is non-degenerate if no ratio ${\lambda }_i/{\lambda }_j$ of distinct characteristic roots is a root of unity. A given LRS can be effectively decomposed as the interleaving of finitely many non-degenerate LRS [14, Theorem 1.6]. The core of the Skolem-Mahler-Lech Theorem is that a non-degenerate LRS that is not identically zero has finitely many zero terms. Unfortunately, the proof of this result remains ineffective: there is no known algorithm to determine whether a non-degenerate LRS has a zero. This is the famous Skolem Problem:

One can also formulate a corresponding function version of this problem in which the task is to compute the finite set of zeros of a given non-degenerate LRS. We denote the decision version by $\mathrm{𝚂𝙿}(\mathbb{N})$ and the function version by $\mathrm{𝙵𝚂𝙿}(\mathbb{N})$. This notation makes explicit that we are looking for natural-number zeros of the LRS.

It is folklore that computability of $\mathrm{𝙵𝚂𝙿}(\mathbb{N})$ reduces to decidability of $\mathrm{𝚂𝙿}(\mathbb{N})$. Assuming the latter, given an LRS $𝒖$, the finitely many zeros in each non-degenerate subsequence of $𝒖$ can be found by brute-force search and, since the infinite suffix of an LRS remains an LRS, one can use a decision procedure for $\mathrm{𝚂𝙿}(\mathbb{N})$ to certify that no zeros remain to be found. However, decidability of the Skolem Problem has remained open for close to a century, with only partial results known from restricting the order (see the exposition of [5] on results of [28, 29, 1]), restricting to reversible sequences of low order [18], or restricting to simple LRS and assuming certain number-theoretic conjectures [6].

In the remainder of this section we introduce various relaxations of the Skolem Problem that arise by extending LRS to larger domains and seeking zeros of such extensions.

The first variant of the Skolem Problem involves bi-infinite (that is, two-way infinite) sequences. Indeed, given a recurrence (1.1) and initial values $u_0,\mathrm{\dots },u_{d-1}\in \mathbb{Q}$, there is a unique bi-infinite sequence $𝒖={⟨u_n⟩}_{n=-\mathrm{\infty }}^{\mathrm{\infty }}$ that satisfies the recurrence. We call $𝒖$ a linear recurrent bi-sequence (LRBS). For example, the Fibonacci sequence extends to an LRBS $⟨\mathrm{\dots },5,-3,2,-1,1,0,1,1,2,3,5\mathrm{\dots }⟩$.

We use the notation $\mathrm{𝚂𝙿}(\mathbb{Z})$ to refer to the above decision problem and we write $\mathrm{𝙵𝚂𝙿}(\mathbb{Z})$ for the corresponding function version, in which we output the finite set of zeros of a given non-degenerate bi-infinite sequence.

For function problems $P_1,P_2$, write $P_1\le P_2$ if there is a Turing reduction from $P_1$ to $P_2$. Here for purposes of comparison we view decision problems as function problems with outputs in $\{\text{TRUE},\text{FALSE}\}$. Write $P_1\equiv P_2$ if $P_1\le P_2$ and $P_2\le P_1$. Then it is easy to see that

Indeed, the reduction $\mathrm{𝙵𝚂𝙿}(\mathbb{Z})\le \mathrm{𝙵𝚂𝙿}(\mathbb{N})$ is realised by splitting a given bi-infinite LRS around the index zero into forward and backward sequences (both of which are LRS) and computing the respective zeros of each of the two one-way infinite sequences.

Unlike for Skolem’s Problem, it is not known whether the function version of the Bi-Skolem Problem reduces to its decision version, i.e., it is not known whether $\mathrm{𝙵𝚂𝙿}(\mathbb{Z})\le \mathrm{𝚂𝙿}(\mathbb{Z})$; however the reduction holds if one assumes the weak $p$-adic Schanuel Conjecture [6].

Having expanded the index set of an LRS to $\mathbb{Z}$ in the Bi-Skolem Problem, we consider a further expansion of its domain to $\mathbb{Q}$, which leads us to consider rational zeros of an LRS. One way to realise this generalisation is via the exponential-polynomial formulation of LRS. It is classical that an LRS $𝒖$ of order $d$ with characteristic roots ${\lambda }_1,\mathrm{\dots },{\lambda }_s$ admits the following representation:

where the $q_i$ are polynomials with algebraic coefficients and degree one less than the multiplicity of ${\lambda }_i$ as a root of the characteristic polynomial of $𝒖$. We say that $\frac{a}{b}\in \mathbb{Q}$ is a rational zero of $𝒖$ if ${\sum }_{i=1}^s{q}_i(\frac{a}{b}){\lambda }_i^{\frac{a}{b}}=0$, where ${\lambda }^{\frac{a}{b}}$ denotes any $b$-th root of ${\lambda }^a$. For example, the sequence $u_n=4^n+2$ has a rational zero at $\frac{1}{2}$ that is witnessed by setting $4^{1/2}:=-2$. The Rational Skolem Problem $\mathrm{𝚂𝙿}(\mathbb{Q})$ asks to determine whether a given LRS has a rational zero, while its function analogue $\mathrm{𝙵𝚂𝙿}(\mathbb{Q})$ asks to compute all rational zeros of a non-degenerate sequence. We note that the definition of rational zeros is consistent with that of integer zeros, that is, the integer rational zeros of $𝒖$ are precisely the zeros of the bi-infinite extension of $𝒖$.

A recent result [7, Proposition 4.7] shows that the denominator of any rational zero can be effectively bounded. This allows us to determine the relationship of the Rational Skolem Problem with the Bi-Skolem Problem and the usual Skolem Problem. We have

where, as noted earlier, $(2)$ is an equivalence assuming the weak $p$-adic Schanuel Conjecture. Indeed, suppose $𝒖$ is an LRS satisfying (1.3). We may compute a bound $b_{\text{max}}$ on the largest denominator of any rational zero of $𝒖$ using [7, Proposition 4.7]. For the reduction (1) we note that deciding $\mathrm{𝚂𝙿}(\mathbb{Q})$ is equivalent to deciding $\mathrm{𝚂𝙿}(\mathbb{Z})$ on every LRS $𝒗$ defined by $v_n:={\sum }_{i=1}^s{q}_i(\frac{n}{b}){({\lambda }_i^{1/b})}^n$, where $1\le b\le b_{\text{max}}$. The reduction (3) is similar.

The main contributions of this paper concern the $p$-adic zeros of an LRS, that is, zeros lying in a $p$-adic completion ${\mathbb{Z}}_p$ of the integers with respect to a given prime $p$. Roughly speaking, the idea is to extend a given LRS $𝒖={⟨u_n⟩}_{n=0}^{\mathrm{\infty }}$ to a map $f:{\mathbb{Z}}_p\to {\mathbb{Z}}_p$ such that $f(n)=u_n$ for all $n\in \mathbb{Z}$. We then determine whether $f$ has any zeros in ${\mathbb{Z}}_p$ and, if yes, we compute exact representations and approximate them to arbitrary precision. By an exact representation of a $p$-adic zero $x$ of $f$ we mean a disc $D$ in ${\mathbb{Z}}_p$ such that $x$ is the unique zero of $f$ in $D$.²²2This notion may be compared to exact representations of algebraic numbers given by their minimal polynomial and an approximation that distinguishes the number from other roots of the minimal polynomial. It turns out that $f$ can have $p$-adic zeros other than the integer or rational zeros of the original LRS $𝒖$. Hence the ability to determine the existence of $p$-adic zeros does not directly solve Skolem’s Problem. Nevertheless, as our results and experiments show, working $p$-adically offers a practical approach to finding integer zeros of an LRS that can moreover find all integer zeros subject to additional assumptions and hypotheses.

By way of example, consider the ring ${\mathbb{Z}}_3$ of 3-adic integers, which is the Cauchy completion of $\mathbb{Z}$ with respect to the absolute value $|\cdot {|}_3$. The latter is defined by writing ${|a|}_3:=3^{-k}$, where $k$ is the order of 3 as a divisor of $a\in \mathbb{Z}$ (the larger $k$, the smaller the absolute value). It turns out that the LRS $u_n=4^n+2$ extends uniquely to a continuous map $f:{\mathbb{Z}}_3\to {\mathbb{Z}}_3$. It is not difficult to see that $f(\frac{1}{2})=0$. Indeed, write $n_k:=\frac{1+3^k}{2}$ for all $k\in \mathbb{N}$. Then ${lim}_{k\to \mathrm{\infty }}{n}_k=\frac{1}{2}$ in ${\mathbb{Z}}_3$. On the other hand, it can be shown by induction that $u_{n_k}\equiv 0mod{3}^{k+1}$ for all $k$ and hence ${lim}_{k\to \mathrm{\infty }}{u}_{n_k}=0$ in ${\mathbb{Z}}_3$. By continuity we conclude that $f(\frac{1}{2})=0$.

In general, given an LRS $𝒖$ satisfying (1.1), pick a prime $p\in \mathbb{N}$ such that $p$ does not divide the last coefficient $a_0$ of the recurrence (1.1). Then there exists $N\ge 1$ and analytic functions $f_0,\mathrm{\dots },f_{N-1}:{\mathbb{Z}}_p\to {\mathbb{Z}}_p$ such that for each $0\le \mathrm{\ell }\le N-1$ we have $u_{Nn+\mathrm{\ell }}=f_{\mathrm{\ell }}(n)$ for all $n\in \mathbb{N}$. Let us call a zero $x\in {\mathbb{Z}}_p$ of one of the above functions $f_{\mathrm{\ell }}$ a $p$-adic zero of $𝐮$. The proof of the Skolem-Mahler-Lech Theorem shows that $𝒖$ has finitely many $p$-adic zeros – but it does not allow one to determine whether a given $𝒖$ has any $p$-adic zeros and, if so, how to compute them (hence the proof does not tell us anything about computing the integer zeros either). This motivates:

The function version of this problem asks to compute a finite representation of all $p$-adic zeros of $𝒖$ (see Definition 4), allowing us both to count the number of $p$-adic zeros and to approximate them to arbitrary precision (with respect to the $p$-adic absolute value). As shorthand we denote the decision and function problems respectively by $\mathrm{𝚂𝙿}({\mathbb{Z}}_p)$ and $\mathrm{𝙵𝚂𝙿}({\mathbb{Z}}_p)$.

We remark that $p$-adic zeros have a concrete interpretation requiring little $p$-adic terminology to understand. A $p$-adic zero can be interpreted as a coherent collection of zeros mod $p^r$ for all $r$, that is, $x\in {\mathbb{Z}}_p$ is a $p$-adic zero of $𝒖$ if and only if there is an infinite sequence $n_1,n_2,\mathrm{\cdots }\in \mathbb{N}$ such that $u_{n_r}\equiv 0mod{p}^r$ and $n_r\equiv n_{r+1}\equiv xmod{p}^r$. We then have $x\in \mathbb{N}$ if this sequence can be taken eventually constant.

It is open whether any of the above-mentioned variants of Skolem’s Problem can be reduced to $\text{SP}({\mathbb{Z}}_p)$ or $\text{FSP}({\mathbb{Z}}_p)$. The essential problem is that we do not know how to determine in general whether a $p$-adic zero of a given LRS is rational or not. While our decision procedure can approximate such a zero to arbitrary precision, it cannot in general certify that it is irrational or even non-integer. Note also that not all rational zeros will be $p$-adic zeros for a given prime $p$. See Sections 3.7 and 4.1 for further discussion on these points.

Our main theoretical result is the following.

In the case when all characteristic roots of $𝒖$ lie in ${\mathbb{Z}}_p$ (which occurs for infinitely many primes $p$ by the Chebotarev density theorem), we have implemented the algorithm for $\text{FSP}({\mathbb{Z}}_p)$ in the Skolem tool [2].³³3Skolem may be experimented with online at https://skolem.mpi-sws.org/?padic. For the algorithm described in this paper, toggle the switch labelled “Use p-adic algorithm”.

The main technical lemma (also subject to the $p$-adic Schanuel Conjecture) behind the proof of Thm. 1 shows that if two exponential polynomials are coprime in the ring of exponential polynomials, then every common $p$-adic zero must be rational (and thus may be found by enumerating the rationals). This lemma has consequences for the Simultaneous Skolem Problem: determine whether two LRS have a common integer zero.

An in-principle decision procedure for $\text{SP}({\mathbb{Z}}_p)$ may be deduced from the doctoral thesis of Mariaule [20] that shows the first-order theory of the structure $({\mathbb{Z}}_p,+,\cdot ,0,1,E_p)$ is decidable assuming the $p$-adic Schanuel Conjecture (where $E_p(x)=e^{px}$). The $p$-adic Schanuel Conjecture is used in [20] via a desingularisation construction; given a zero $x$ of an exponential polynomial, there exists a system of exponential polynomials of which $x$ is a non-singular zero. This approach is not practical to implement however, as the algorithm entails enumerating systems of integer multivariate polynomials. In contrast, our algorithm only requires enumerating rational numbers to check for repeated zeros of a given LRS. Such a search can moreover be done efficiently in practice by searching for rational numbers close to the approximations of $p$-adic zeros that the algorithm identifies. Using $p$-adic approximation to speed up the search for integer zeros of LRS is explored further in [4].

We note also that Thm. 2 does not follow directly from the result of [20] since $\mathbb{Z}$ is not first-order definable in $({\mathbb{Z}}_p,+,\cdot ,0,1,E_p)$, as this would immediately contradict decidability of the latter structure.

We briefly recall relevant notions about $p$-adic numbers. More details may be found in algebraic number theory textbooks such as [23, 24].

Given a prime number $p$, every non-zero rational number $x\in \mathbb{Q}$ may be written as $x=\frac{a}{b}{p}^r$ for some integers $a,b$ coprime to $p$, with $b$ non-zero, and $r\in \mathbb{Z}$. We define the valuation $v_p(x)=r$, and $v_p(0)=\mathrm{\infty }$. From this derivation we see that $v_p$ satisfies the ultrametric inequality $v_p(x+y)\ge \min (v_p(x),v_p(y))$ for all $x,y\in \mathbb{Q}$.

We define an absolute value on $\mathbb{Q}$ by ${|x|}_p=p^{-v_p(x)}$. The ultrametric inequality on $v_p$ translates to the strong triangle inequality: ${|x+y|}_p\le \max ({|x|}_p,{|y|}_p)$ for all $x,y\in \mathbb{Q}$. Define the set of $p$-adic numbers ${\mathbb{Q}}_p$ as the completion of $\mathbb{Q}$ with respect to $|\cdot {|}_p$. If one completes $\mathbb{Z}$ with respect to $|\cdot {|}_p$ then one gets the $p$-adic integers ${\mathbb{Z}}_p$, which may also be defined as the unit disc in ${\mathbb{Q}}_p$:

The absolute value $|\cdot {|}_p$ on ${\mathbb{Q}}_p$ extends uniquely to an absolute value on the algebraic closure $\overline{{\mathbb{Q}}_p}$. Specifically, given $\alpha \in \overline{{\mathbb{Q}}_p}$, we define ${|\alpha |}_p:={|N(\alpha )|}_p^{1/n}$, where $n$ is the degree of $\alpha$ over ${\mathbb{Q}}_p$ and $N(\alpha )$ is the norm of $\alpha$, that is the determinant of the $\mathbb{Q}$-linear transformation ${\mu }_{\alpha }:\mathbb{Q}(\alpha )\to \mathbb{Q}(\alpha )$ given by ${\mu }_{\alpha }(x)=\alpha x$. We correspondingly extend the valuation $v_p(\cdot )$ to $\overline{{\mathbb{Q}}_p}$ by $v_p(\alpha ):=\frac{1}{n}{v}_p(N(\alpha ))$. With these definitions the identity ${|\alpha |}_p=p^{-v_p(\alpha )}$ holds for all $\alpha \in \overline{{\mathbb{Q}}_p}$. While $\overline{{\mathbb{Q}}_p}$ is not complete with respect to $|\cdot {|}_p$, taking the Cauchy completion we obtain a field ${ℂ}_p$ that is both algebraically closed and complete under the extension of $|\cdot {|}_p$ to ${ℂ}_p$. Denote the valuation ring of ${ℂ}_p$ by ${𝒪}_{{ℂ}_p}=\{x\in {ℂ}_p:v_p(x)\ge 0\}$.

We will require a generalisation of the above discussion to deal with algebraic numbers lying outside of ${\mathbb{Z}}_p$. Given a number field $𝕂$, let $𝒪$ denote its ring of integers. Previous ideas of factorising to define a valuation $v_p$ do not carry over directly as $𝒪$ is no longer a unique factorisation domain, instead one generalises to consider factorisations of (fractional) ideals. Define a fractional ideal of $𝕂$ to be a non-zero finitely generated $𝒪$-submodule of $𝕂$; equivalently, $I$ is a fractional ideal if and only if there is $c\in 𝕂$ such that $cI\subseteq 𝒪$ is an ideal of $𝒪$. Any fractional ideal has a unique factorisation

where $t\in \mathbb{N}$ and each $𝔭\subseteq 𝒪$ is a prime ideal, $n_i\in \mathbb{Z}$ [23, p. 22]. If $I\subseteq 𝒪$ is an ideal then $n_i\ge 0$. Define the valuation $v_{𝔭}$ by $v_{𝔭}(a)=n$ if the exponent of $𝔭$ in the prime factorisation of the ideal $a𝒪$ is $n$, and $v_{𝔭}(0)=\mathrm{\infty }$. Any prime ideal $𝔭$ has $v_{𝔭}(p)>0$ for a unique integer prime $p\in \mathbb{N}$. We say $𝔭$ “divides” or “lies above” $p$. Say $p$ ramifies in $𝕂$ if $v_{𝔭}(p)=e>1$; call $e=e_{𝔭/p}$ the ramification index. Define the residue field degree $f=f_{𝔭/p}$ by $f=[𝒪\mathrm{╱}𝔭:\mathbb{Z}\mathrm{╱}p\mathbb{Z}]$. Define the $𝔭$-adic absolute value by ${|x|}_{𝔭}=p^{-f{v}_{𝔭}(x)}$.⁴⁴4There are many conventions for the normalization of $𝔭$-adic absolute values as they are equivalent and induce the same completions. Denote the completion of $𝕂$ with respect to $|\cdot {|}_{𝔭}$ by ${𝕂}_{𝔭}$, which may be embedded into ${ℂ}_p$. Let the valuation ring be denoted by

A uniformiser $\pi \in {𝒪}_{𝔭}$ is an element such that $v_{𝔭}(\pi )=1$. For example, let $𝕂=\mathbb{Q}(\sqrt{3})$ and $𝔭=(\sqrt{3})𝒪\subseteq 𝒪$. Then $\pi =\sqrt{3}$ is a uniformiser in ${𝕂}_{𝔭}$, and the ramification index $e_{𝔭/p}=2$. Informally, the uniformiser $\pi$ takes the analogous role in ${𝒪}_{𝔭}$ that $p$ does in ${\mathbb{Z}}_p$.

Any element $x\in {𝒪}_{𝔭}$ can be represented as an infinite series $x={\sum }_{n=0}^{\mathrm{\infty }}{a}_n{\pi }^n$, where each $a_n\in A$, for $A$ a choice of representatives for the residue field $𝒪\mathrm{╱}𝔭$. In the algorithm, using this fact, $\pi$ and $A$ are used to enumerate elements $x\in {𝒪}_{𝔭}$, and to easily compute their valuations $v_{𝔭}$, since $v_{𝔭}({\sum }_{n=0}^{\mathrm{\infty }}{a}_n{\pi }^n)$ is equal to $j$, where $j$ is the smallest integer for which $a_j\ne 0$. Practically, since only finitely many digits may be stored, for such computations one works with approximations – that is, reductions mod ${\pi }^r$. This is equivalent to truncating the series representation, i.e. ${\sum }_{n=0}^{\mathrm{\infty }}{a}_n{\pi }^n\equiv {\sum }_{n=0}^{r-1}{a}_n{\pi }^{n}mod{\pi }^r$.

Since $𝒪\mathrm{╱}𝔭$ is a finite field, $𝒪\mathrm{╱}𝔭\cong {𝔽}_{p^f}$ is generated by (the reduction modulo $𝔭$ of) a single element $a\in 𝒪$; therefore $A$ may be taken to be of the form

We will not expand much in this article on the intricacies of computations in ${𝒪}_{𝔭}$, for us it suffices to, given a number field $𝕂$ and integer prime $p$, pick a prime ideal $𝔭\subseteq 𝒪$ lying above $p$, compute a uniformiser $\pi \in {𝒪}_{𝔭}$, and $A$ of the form (2.1). This can be handled using Montes’ algorithm, see [22]. In particular one may compute representations of all prime ideals lying above $𝔭$, compute valuations $v_{𝔭}$, and a $p$-integral basis of $𝕂$, from which one can find $A,e_{𝔭/p},f_{𝔭/p}$; a uniformiser $\pi$ can simply be found by enumerating elements until one is found with $v_{𝔭}(\pi )=1$.

Consider an LRS $𝒖$ satisfying (1.1) that is given by the formula (1.3) and let $𝕂$ be the field generated by the characteristic roots of $𝒖$. As mentioned in Section 1.1, by [14, Theorem 1.6] we may effectively decompose $𝒖$ into non-degenerate or identically zero subsequences; we may thus assume in the rest of this article that any given LRS $𝒖$ is non-degenerate.

Pick a prime ideal $𝔭\subseteq 𝒪$ lying above prime $p\in \mathbb{N}$ that does not divide the last coefficient $a_0$ of the recurrence for $𝒖$ (so that $v_{𝔭}({\lambda }_i)=0$ for all $i$). Choose $N\in {\mathbb{Z}}_{\ge 1}$ to be the smallest positive integer such that $v_{𝔭}({\lambda }_i^N-1)>\frac{e}{p-1}$ for all $i$, where $e=e_{𝔭/p}$ is the ramification index. For $\mathrm{\ell }\in \{0,1,\mathrm{\dots },N-1\}$ we define the $\mathrm{\ell }$-th $𝔭$-adic interpolant of $𝒖$ to be the analytic function⁵⁵5The $p$-adic analytic functions $\exp ,\log$ have the usual series definitions, see [24, section 5.4]. In particular, $\log$ maps $1+{\pi }^r{𝒪}_{𝔭}$ to ${\pi }^r{𝒪}_{𝔭}$, and $\exp$ converges on and maps ${\pi }^r{𝒪}_{𝔭}$ to $1+{\pi }^r{𝒪}_{𝔭}$, when $r>\frac{e_{𝔭/p}}{p-1}$.

with $x\in {𝒪}_{𝔭}$. Then $f_{\mathrm{\ell }}(n)=u_{Nn+\mathrm{\ell }}$ for each $n\in {\mathbb{Z}}_{\ge 0}$ and so (2.2) defines an extension of $𝒖$ to ${𝒪}_{𝔭}$. In fact, the right-hand side of (2.2) converges for any $x\in {𝒪}_{{ℂ}_p}$ and we call such an $x$ an extended $p$-adic zero if $f_{\mathrm{\ell }}(x)=0$ for some $\mathrm{\ell }\in \{0,\mathrm{\dots },N-1\}$. Note that since $f_{\mathrm{\ell }}(n)\in \mathbb{Z}$ for all $n\in \mathbb{N}$, by continuity $f_{\mathrm{\ell }}(x)\in {\mathbb{Z}}_p$ for all $x\in {\mathbb{Z}}_p$. Thus we have a power series representation

for $b_j\in {\mathbb{Z}}_p$. We will often implicitly restrict the domain to ${\mathbb{Z}}_p$ and write that $f_{\mathrm{\ell }}:{\mathbb{Z}}_p\to {\mathbb{Z}}_p$ is a $p$-adic interpolant of $𝒖$.

Given characteristic roots ${\lambda }_1,\mathrm{\dots },{\lambda }_s\in 𝕂$, say they are multiplicatively dependent if there is an integer tuple $(k_1,\mathrm{\dots },k_s)\in {\mathbb{Z}}^s$ such that ${\lambda }_1^{k_1}\mathrm{\dots }{\lambda }_s^{k_s}=1$. The group of all multiplicative relations has generators which are effectively bounded by Masser’s theorem [21], this may be used to find all multiplicative relations (see also [11] for a polynomial-time algorithm) and hence find a multiplicatively independent set of algebraic numbers $\{{\alpha }_1,\mathrm{\dots },{\alpha }_r\}$ such that each ${\lambda }_i$ may be expressed as a Laurent monomial in ${\alpha }_1,\mathrm{\dots },{\alpha }_r$ (they can be expressed in this way by non-degeneracy). Therefore $f_{\mathrm{\ell }}$ may be expressed as a Laurent polynomial with algebraic coefficients

$P_{\mathrm{\ell }}$ may easily be factored as $P_{\mathrm{\ell }}=R_{\mathrm{\ell }}{Q}_{\mathrm{\ell },1}^{t_1}\mathrm{\dots }{Q}_{\mathrm{\ell },m}^{t_m}$, where $R_{\mathrm{\ell }}$ is a Laurent monomial in $\exp (x\log {\alpha }_1^N),\mathrm{\dots },\exp (x\log {\alpha }_r^N)$ and $Q_{\mathrm{\ell },1},\mathrm{\dots },Q_{\mathrm{\ell },m}$ are irreducible polynomials in $x$, $\exp (x\log {\alpha }_1^N),\mathrm{\dots },\exp (x\log {\alpha }_r^N)$. Since $R_{\mathrm{\ell }}$ is never zero, finding zeros of $f_{\mathrm{\ell }}(x)$ reduces to working on each irreducible factor $Q_{\mathrm{\ell },i}$ individually. Note also that $R_{\mathrm{\ell }}$ corresponds to an order-1 LRS; in effect we are factorising $u_{Nn+\mathrm{\ell }}$ as a product of irreducible (algebraic-valued) LRS.

We must still explain how $p$-adic zeros are represented and stored. The following is a key lemma for finding zeros of power series on ${𝕂}_{𝔭}$ (a proof may be found in e.g. [12, Thm. 9.2] or [25, Thm. 27.6]).

The following definition explains how we treat $p$-adic zeros of power series:

Hensel’s Lemma ensures that $x$ is defined uniquely. The proof of Hensel’s lemma also provides an efficient method for computing approximations of $x$, via the iteration $x_{n+1}=x_n-f(x_n)/f^{\prime }(x_n)$ and $x_0=y$.

The next theorem is a generalisation of Strassman’s Theorem, commonly known via the notion of the Newton Polygon; see [24], page 307.

Thm. 5 allows us to determine how many $p$-adic zeros we are searching for and provides a certificate when we have found them all.

Finally, we state the $p$-adic Schanuel Conjecture (see [8, 20]).

In this section we prove Thm. 1, assuming the $p$-adic Schanuel Conjecture. We start with an informal description of an algorithm that attempts to find the $p$-adic zeros of an LRS $𝒖$ using only brute-force search and Hensel’s Lemma. We note the problem with this approach, which motivates the subsequent development involving the $p$-adic Schanuel Conjecture.

Let $f_{\mathrm{\ell }}:{\mathbb{Z}}_p\to {\mathbb{Z}}_p$ be an interpolant of a given LRS $𝒖$. We would like to compute specifications of all the zeros of $f_{\mathrm{\ell }}$ in ${\mathbb{Z}}_p$. The idea is to search for zeros lying in the residue classes of ${\mathbb{Z}}_p$ modulo $p^r$ for $r=1,2,3,\mathrm{\dots }$. Consider a representative $z\in {\mathbb{Z}}_p$ of a residue class of ${\mathbb{Z}}_p\mathrm{╱}{p}^r{\mathbb{Z}}_p$. Since ${\mathbb{Z}}_p\mathrm{╱}{p}^r{\mathbb{Z}}_p\cong \mathbb{Z}\mathrm{╱}{p}^r\mathbb{Z}$ (e.g. [23, Ch. II, Prop. 2.4]), $z$ may be taken to be an integer in $\{0,1,\mathrm{\dots },p^r-1\}$.

If $f_{\mathrm{\ell }}(z)\not\equiv 0mod{p}^r$ then the residue class of $z$ does not contain a zero of $f_{\mathrm{\ell }}$, and we can proceed to search other residue classes. If $f_{\mathrm{\ell }}(z)\equiv 0mod{p}^r$ and $v_p(f_{\mathrm{\ell }}(z))>2v_p(f_{\mathrm{\ell }}^{\prime }(z))$ then the residue class contains a unique zero of $f_{\mathrm{\ell }}$ by Hensel’s Lemma (Thm. 3). If neither of the above cases hold then the residue class may contain any number of zeros of $f_{\mathrm{\ell }}$. Note that we can use Thm. 5 to determine the exact number of extended $p$-adic zeros (lying in the extension ${ℂ}_p$ of ${\mathbb{Z}}_p$) of $f_{\mathrm{\ell }}$ in the residue class of $z$.⁶⁶6Let $f_{\mathrm{\ell }}(x)={\sum }_{n=0}^{\mathrm{\infty }}{a}_n{(x-z)}^n$ be a power-series expansion of $f_{\mathrm{\ell }}$ around $z$ and calculate the respective smallest and largest indices for which $v_p(a_n)+nr=\underset{j\ge 0}{\min }{v}_p(a_j)+jr$ by computing each derivative $f_{\mathrm{\ell }}^{(j)}(z)mod{p}^k$ for increasing powers $k$. By Thm. 5 there are $\nu -\mu$ extended $p$-adic zeros in the same residue class as $z$ modulo $p^r$. If this number is zero then we can again proceed to consider other residue classes. If the number is positive then we can refine our search by looking at residue classes modulo $p^{r+1}$ contained in the current class. If all the zeros of $f_{\mathrm{\ell }}$ in ${\mathbb{Z}}_p$ are simple then this search will eventually terminate. However, if there is a zero in ${\mathbb{Z}}_p$ of multiplicity two or more then the search will run forever (as the inequality $v_{𝔭}(f_{\mathrm{\ell }}(z))>2v_{𝔭}(f_{\mathrm{\ell }}^{\prime }(z))$ will never hold). The key challenge is thus to identify multiple zeros of $f_{\mathrm{\ell }}$ in ${\mathbb{Z}}_p$ and determine their multiplicity.

It so happens that for irreducible factors of $f_{\mathrm{\ell }}$, assuming $p$-adic Schanuel’s Conjecture, the only possible zeros of multiplicity two or more are rational. This is the content of the main technical results in this section and it allows us to amend the above algorithm so that it always terminates. Specifically, in parallel with the above-described process, we search by enumeration for rational zeros of $f_{\mathrm{\ell }}$. We thus find all $p$-adic zeros either by specifying them with Hensel’s Lemma or by enumerating rationals and checking directly. We use Thm. 5 to certify that all zeros have thereby been found.

We will now introduce our main technical lemma. We prove that every common zero of two coprime exponential polynomials over ${\mathbb{Z}}_p$ is rational. It is interesting to compare this result with [10, Proposition 3.4], which shows that two coprime exponential polynomials over $ℂ$ in which all numerical constants are algebraic have no common zeros whatsoever, assuming Schanuel’s Conjecture over $ℂ$.

Let $𝕂$ be a number field with ring of integers $𝒪$, and $𝔭\subseteq 𝒪$ be a prime ideal lying above prime $p\in \mathbb{N}$. Choose ${\lambda }_1,\mathrm{\dots },{\lambda }_s\in 𝒪$ multiplicatively independent such that the $𝔭$-adic logarithms $\log {\lambda }_1,\mathrm{\dots },\log {\lambda }_s$ are defined. Note then that $\log {\lambda }_1,\mathrm{\dots },\log {\lambda }_s$ are linearly independent over $\mathbb{Q}$. Let $P\in 𝕂[x,y_1,\mathrm{\dots },y_s,z_1,\mathrm{\dots },z_s]$ be a polynomial. Define its associated exponential polynomial by

With Corollary 12 in hand, we may amend the algorithm outlined earlier for finding the $p$-adic zeros of an LRS. First we define a recursive subroutine given by Algorithm 1, which finds specifications of all the zeros in ${𝒪}_{𝔭}$ of a suitable analytic function $f:{𝒪}_{𝔭}\to {𝒪}_{𝔭}$.

Next, the idea is as follows. Following the process explained in Section 2.3, we find the $p$-adic interpolants of a given LRS $𝒖$, that is, analytic functions interpolating each subsequence $u_{Nn+\mathrm{\ell }}$ for each $0\le \mathrm{\ell }\le N-1$, for some integer $N$. Since any interpolant $f$ maps $\mathbb{Z}$ to $\mathbb{Z}$, we have by continuity that $f$ maps ${\mathbb{Z}}_p$ to ${\mathbb{Z}}_p$. We compute a multiplicatively independent set of algebraic numbers $\{{\alpha }_1,\mathrm{\dots },{\alpha }_s\}$ that generates the characteristic roots of $𝒖$ as explained in Section 2.3, and for each interpolant $f$ compute the associated Laurent polynomial $P$ such that $f(n)=P(n,{\alpha }_1^{Nn},\mathrm{\dots },{\alpha }_s^{Nn})$ for all $n\in \mathbb{Z}$.

Now, factorise $P=R{P}_1^{r_1}\mathrm{\dots }{P}_m^{r_m}$, where $P_1,\mathrm{\dots },P_m$ are irreducible polynomials, and $R$ is some Laurent monomial. Next, pass the associated analytic function $f_{P_i}:{𝒪}_{𝔭}\to {𝒪}_{𝔭}$ to Algorithm 1 to find specifications of all extended $p$-adic zeros in ${𝒪}_{𝔭}$ of each $f_{P_i}$. Unfortunately, we cannot guarantee that $f_{P_i}$ maps ${\mathbb{Z}}_p$ to ${\mathbb{Z}}_p$ so we require one more step to identify the $p$-adic zeros (i.e. those in ${\mathbb{Z}}_p$). Note however, that for an irrational zero $x\in {𝒪}_{𝔭}$ of $f_{P_i}$ that has multiplicity 1, $x$ will also be a zero of $f^{(r_i-1)}:{\mathbb{Z}}_p\to {\mathbb{Z}}_p$ of multiplicity 1. Therefore for a suitable approximation $y$ of $x$, we can identify $x$ as a zero of $f^{(r_i-1)}$ using Hensel’s lemma when we certify $v_p(f^{(r_i-1)}(y))>2v_p(f^{(r_i)}(y))$. Since $f^{(r_i-1)}$ does map ${\mathbb{Z}}_p$ to ${\mathbb{Z}}_p$, if $y\in {\mathbb{Z}}_p$ then Hensel’s lemma certifies that $x\in {\mathbb{Z}}_p$. Otherwise, if $x\in {𝒪}_p\setminus {\mathbb{Z}}_p$, one can certify this by computing its $𝔭$-adic series expansion. Thus, to find all the zeros of $f$ in ${\mathbb{Z}}_p$, simply run through each zero $x\in {𝒪}_p$ of each $f_{P_i}$, and in parallel do the following: