On Large Zeros of Linear Recurrence Sequences

An (integer) linear recurrence sequence (LRS) ${⟨u_n⟩}_{n=0}^{\mathrm{\infty }}$ is a sequence of integers satisfying a recurrence of the form

where the coefficients $a_1,\mathrm{\dots },a_k$ are integers. The celebrated theorem of Skolem, Mahler, and Lech [28, 20, 15] describes the set of zero terms of such a recurrence:

The statement of Thm. 1 can be refined by considering the notion of non-degeneracy of an LRS. An LRS is non-degenerate if in its minimal recurrence no quotient of two distinct roots of the characteristic polynomial is a root of unity.¹¹1For basic definitions, facts, and properties concerning linear recurrence sequences, we refer the reader to standard texts such as [9, Chaps. 1 and 2], [14, Chap. 4], or [29, Chap. 4]. A given LRS can be effectively decomposed as the interleaving of finitely many non-degenerate sequences, some of which may be identically zero. The core of the Skolem-Mahler-Lech theorem is the fact that a non-zero non-degenerate linear recurrence sequence has finitely many zero terms. Unfortunately, all known proofs of this last result are ineffective: it is not known how to compute the finite set of zeros of a given non-degenerate linear recurrence sequence. It is readily seen that existence of a procedure to do so is equivalent to the existence of a procedure to determine whether an arbitrary given LRS has a zero term; the latter is known as the Skolem Problem. We refer to [4, Chap. 6] and [30, Chap. X] for expository accounts of the Skolem-Mahler-Lech theorem and discussion of the ineffectiveness of known proofs.

In computer science, the Skolem Problem lies at the heart of key decision problems in formal power series [26, 3], stochastic model checking [25], control theory [6, 10], and loop termination [24]. The problem is also closely related to membership problems on commutative matrix groups and semigroups, as considered in [7, 13]. We note that in several of the above-mentioned citations, the Skolem Problem is used as a reference benchmark to establish hardness of other open decision problems.

Decidability of the Skolem Problem is known only for certain special cases, based on the relative order of the absolute values of the characteristic roots. Say that a characteristic root $\lambda$ is dominant if its absolute value is maximal among all the characteristic roots. Decidability is known in case there are at most $3$ dominant characteristic roots, and also for recurrences of order at most $4$ [21, 31]. However for LRS of order $5$ it is not currently known how to decide the Skolem Problem. For a (highly restricted) subclass of LRS, the paper [1] obtains nearly matching complexity lower and upper bounds for the problem.

Some recent lines of research have succeeded in establishing conditional decidability of the Skolem Problem for simple LRS (i.e., LRS none of whose characteristic roots are repeated), assuming certain classical number-theoretic conjectures [16, 5]. Nevertheless, to the best of our knowledge, no putative algorithm has to date been proposed to solve the Skolem Problem in full generality.

A different approach was initiated in [18, 19, 17] via the notion of Universal Skolem Sets. An infinite, recursive set $𝒮\subseteq \mathbb{N}$ is a Universal Skolem Set if there is some algorithm which, given any LRS, determines whether or not the LRS has a zero in $𝒮$. Decidability of the Skolem Problem is then of course equivalent to the assertion that $\mathbb{N}$ is itself a Universal Skolem Set. The authors of [18] succeded in exhibiting a sparse Universal Skolem Set, i.e., a set having null density, and left open the question of whether Universal Skolem Sets of strictly positive density, or even density one, could be constructed (the interest in high-density Universal Skolem Sets being that they approximate $\mathbb{N}$ more closely). The question was partially answered in [19], which presented a positive-density Universal Skolem Set, albeit restricted to simple LRS, and in [17], which exhibited a Universal Skolem Set of strictly positive density, and even established density $1$ subject to the Bateman-Horn conjecture in number theory.

In this paper we propose an explicit bound for the largest zero of a non-degenerate LRS in terms of the data describing the LRS. We call zeros that exceed this bound large zeros of the LRS. Evidently, decidability of the Skolem Problem would follow from a proof that large zeros do not exist. Using known upper bounds on the cardinality of the set of zeros of non-degenerate LRS, it is relatively straightforward to show that the set of integers arising as large zeros of some non-degenerate LRS has null density, which in turn yields a Universal Skolem Set of unconditional density one; this is the first of our two main contributions.

While a proof that large zeros do not exist currently seems well out of reach, we give a heuristic argument as to why this should nevertheless be expected. This argument is based on an analogue of the well-known Cramér conjecture on gaps between consecutive primes. This conjecture, originally formulated by Cramér in 1936 [8] and subsequently refined by various number theorists into its present form, asserts that, for some constant $\kappa >1$, for every prime $p$ the distance to the next largest prime is at most $\kappa {(\log p)}^2$. The conjecture is based on the heuristic that the sequence of prime numbers behaves similarly to a Poisson-like random process in which the probability of a number $x$ being prime is $1/\log x$. The largest observed prime gaps are of the order of $0.5{(\log p)}^2$ [23], however the best known upper bound on prime gaps is $O(p^{0.525})$, due to Baker, Harman, and Pintz [2], which is far from Cramér’s conjectured bound. Cramér himself proved that, under the Riemann hypothesis, prime gaps are bounded above by $O(p^{0.5}\log p)$ [8]. On the other hand, the best known lower bound is $\mathrm{\Omega }(\log p\log \log p)$, which is some way from the conjectured upper bound. We refer to [12] for a discussion of Cramér’s conjecture and its refinements.

Here we define a subset of so-called good primes based on divisibility properties of LRS. We show that the set of good primes has density one in the set of all primes, or in other words that, asymptotically speaking, almost all primes are good primes. We further show that if the Cramér conjecture applies also to gaps between consecutive good primes, then large zeros of LRS cannot exist. The proof of the latter result (our second main contribution) proceeds by establishing an upper bound on the number of good primes in the neighbourhood of a large zero that violates the conjectured upper bound on gaps between good primes. In other words, if good primes are distributed according to Cramér’s heuristic then large zeros cannot exist and the Skolem Problem is decidable.

We will need some basic notions concerning algebraic numbers. All material can be found in [11]. Recall that a number field $𝕂$ is a subfield of $ℂ$ that is finite dimensional as a vector space over $\mathbb{Q}$. We assume that $𝕂$ is a Galois extension of $\mathbb{Q}$, that is, it arises as the splitting field of a polynomial with integer coefficients. All elements of $𝕂$ are algebraic over $\mathbb{Q}$, that is, they arise as roots of polynomials with integer coefficients. Those elements that arise more specifically as roots of monic polynomials with integer coefficients are called algebraic integers. The algebraic integers in $𝕂$ form a subring, denoted ${𝒪}_{𝕂}$.

For a number field $𝕂$, we denote by $\mathrm{Gal}(𝕂/\mathbb{Q})$ the group of field automorphisms of $𝕂$. Given $\alpha \in 𝕂$, the norm of $\alpha$ is defined by

The norm ${𝒩}_{𝕂/\mathbb{Q}}(\alpha )$ is rational for all $\alpha \in 𝕂$; moreover ${𝒩}_{𝕂/\mathbb{Q}}(\alpha )=0$ iff $\alpha =0$, and ${𝒩}_{𝕂/\mathbb{Q}}(\alpha )$ is an integer if $\alpha \in {𝒪}_{𝕂}$. Clearly we have $|{𝒩}_{𝕂/\mathbb{Q}}(\alpha )|\le M^{d_{𝕂}}$, where $d_{𝕂}$ is the degree of $𝕂$ and

is the house of $\alpha$.

We recall that every ideal in ${𝒪}_{𝕂}$ can be written uniquely up to the order of its factors as the product of prime ideals. Given a rational prime $P\in \mathbb{Z}$, we say that a prime ideal $𝔭$ lies above $P$ if $𝔭$ is a factor of $P{𝒪}_{𝕂}$. In this case we have that $P\mid {𝒩}_{𝕂/\mathbb{Q}}(\alpha )$ for all $\alpha \in 𝔭$.

Let $𝔭$ be a prime ideal of ${𝒪}_{𝕂}$ lying above $P\in \mathbb{Z}$. Recall that the Frobenius automorphism $\sigma \in \mathrm{Gal}(𝕂/\mathbb{Q})$ corresponding to $𝔭$ is such that $\sigma (\alpha )\equiv {\alpha }^{P}mod𝔭$ for all $\alpha \in {𝒪}_{𝕂}$; in fact it is the unique Galois automorphism with this property.

For an LRS $𝐮={⟨u_n⟩}_{n=0}^{\mathrm{\infty }}$ as in (1), define its size²²2Note that we consider here the magnitude of the numbers defining a given LRS (rather than their bit size as is more common in complexity theory). An alternative definition in terms of bit size would of course be possible, only requiring altering (2) into a seventh-fold exponential. to be

Given a (partial) function $f:ℝ\to ℝ$ and a positive integer $\mathrm{\ell }$, let $f_{\mathrm{\ell }}(x)=f\circ f\circ \mathrm{\cdots }\circ f(x)$, where the iteration is $\mathrm{\ell }$-fold (thus $f_1=f$). We say that $n$ is a zero of $𝐮$ if $u_n=0$, and we say that it is a large zero if the inequality

fails.

As we argue later on, there are good reasons to expect that (2) holds for all zeros of all non-degenerate LRS, which in turn would establish decidability of the Skolem Problem.³³3The sixth-fold exponential in (2) has of course been chosen in order for our mathematical argument to go through. In actual fact, it is plausible to expect that a single exponential would suffice: as far as we are aware, there is currently no known construction of a family of non-degenerate LRS having zeros at indices of magnitude even a single exponential in terms of the size of the LRS, as defined above. Unfortunately, we are unable to prove this assertion. Nevertheless, we now show that large zeros are very sparse, i.e., have null density amongst the positive integers. To this end, let

Thus $ℒ$ is the set of large zeros of some non-degenerate LRS.

We first define what it means for a prime number to be bad. As before, let $X>2{\exp }_7(1)$ be an integer, and recall than an LRS $𝐮$ is small at level $X$ if it has size $C_{𝐮}\le {\log }_6(X/2)$. Let us write $C:=C_{𝐮}$ (that is, we omit the dependence on $𝐮$). We can express the general term $u_t$ of $𝐮$ as

where $s\le C$ and ${\alpha }_1,\mathrm{\dots },{\alpha }_s$ are the roots of the characteristic polynomial

of $𝐮$ and $Q_1,\mathrm{\dots },Q_s$ are univariate polynomials. Note that all characteristic roots are algebraic integers since the characteristic polynomial is monic and comprises exclusively coefficients in $\mathbb{Z}$. Recall that if ${\alpha }_i$ has multiplicity ${\mu }_i$ as a characteristic root then $Q_i$ has degree at most ${\mu }_i-1$. Let $𝕂:=\mathbb{Q}({\alpha }_1,\mathrm{\dots },{\alpha }_s)$. The coefficients of each $Q_i$ are in $𝕂$ and can straightforwardly be computed from the initial values $u_0,\mathrm{\dots },u_{k-1}$ of the sequence by solving a system of $k$ linear equations, thanks to (3). By Cramer’s determinant rule,⁴⁴4This rule is named after the 18th-century Genevan mathematician Gabriel Cramer, who is presumably unrelated to the 20th-century Swedish mathematician Harald Cramér, whose work plays an important role in motivating the present article. each of the coefficients of $Q_i$ is the quotient of an algebraic integer by the determinant $\mathrm{\Delta }:=\det (M)$ of the matrix⁵⁵5The matrix $M$ has $s$ blocks, one for each characteristic root. For $\mathrm{\ell }\in \{1,\mathrm{\dots },s\}$ the $\mathrm{\ell }$-th block has dimension $k\times {\mu }_{\mathrm{\ell }}$ and has $(i,j)$-th element ${(i-1)}^{(j-1)}{\alpha }_{\mathrm{\ell }}^{(i-1)}$ for $i\in \{1,\mathrm{\dots },k\}$ and $j\in \{1,\mathrm{\dots },{\mu }_{\mathrm{\ell }}\}$.

By the Cauchy root bound we have $|{\alpha }_i|\le 1+C$ for $i\in \{1,\mathrm{\dots },s\}$. It follows that the squared Euclidean norm of each column vector above is at most

Thus, by the Hadamard inequality,

The determinant $\mathrm{\Delta }$ is in general, of course, a complex number. Note however that any Galois automorphism $\sigma \in \mathrm{Gal}(𝕂/\mathbb{Q})$ will permute the characteristic roots, and thus when applied to $M$ will have the effect of permuting its columns. As a result, for any such $\sigma$, $\sigma (\mathrm{\Delta })=\pm \mathrm{\Delta }$, and therefore the quantity ${\mathrm{\Delta }}^2$ is stable under Galois automorphisms. We conclude that ${\mathrm{\Delta }}^2$ must be a rational number, and since it is also by construction an algebraic integer,⁶⁶6Note that every entry of $M$ is an algebraic integer. we must have ${\mathrm{\Delta }}^2\in \mathbb{Z}$.

Let us now consider the LRS $𝐯:={\mathrm{\Delta }}^2𝐮$, noting that $𝐮$ and $𝐯$ share the same zeros. Writing

we observe that all the coefficients of each of the $P_i$ are algebraic integers. We therefore have, for each $1\le i\le s$,

We wish to estimate the size of each $c_{i,j}\in {𝒪}_{𝕂}$. From our earlier calculation via Cramer’s determinant rule, noting that $|u_0|,\mathrm{\dots },|u_{k-1}|$ are all bounded above by $C\le 1+C$, and invoking the Hadamard inequality once more, we conclude that the house of each $c_{i,j}$ is bounded above by

Let $\sigma \in {\mathrm{\Sigma }}_s$ be any permutation of the first $s$ integers and let

For some nonnegative integer $m$ consider the algebraic integer

Let ${𝒫}_{\text{bad}}(X)$ be the set of bad primes in $[X,2X]$.

In this section we present a heuristic argument supporting the assertion that large zeros do not exist, or in other words that the set $ℒ$ is empty. The strategy is as follows. Assuming that good primes are distributed roughly similarly as ordinary primes, according to the Cramér model in number theory, one would expect that Cramér’s conjecture on gaps between primes applies also to good primes. More precisely, this conjecture postulates the existence of precise upper bounds on the largest possible gap between consecutive primes, and is predicated on the heuristic that the primes behave as a set of randomly distributed integers with asymptotic density conforming to the prime number theorem. However we show that around any large zero of an LRS there is an interval and an upper bound on the number of good primes in the interval that together contradict the above Cramér-type conjecture on gaps between good primes. We therefore surmise that large zeros do not exist.

Recall that $𝒫=\{p_1,p_2,\mathrm{\dots }\}$ denotes the set of prime numbers, enumerated in increasing order, and likewise let us write ${𝒫}_{\mathrm{good}}:=\{g_1,g_2,\mathrm{\dots }\}$ to denote an enumeration of the set of good primes in increasing order.

Cramér initially suggested that the constant $\kappa$ in Conjecture 6 might be 1 [8], but several decades later, building on substantial developments in the field, Granville produced evidence that $\kappa \ge 2e^{-\gamma }\approx 1.1229\mathrm{\dots }$, where $\gamma$ is the Euler–Mascheroni constant [12]. There is in any event considerable computational evidence in support of the Cramér-Granville conjecture [23, 22].

As noted earlier, thanks to Prop. 5 and the prime number theorem, good primes have density one amongst all prime numbers:

In other words, asymptotically speaking, almost all primes are good primes. Accordingly, it seems reasonable to suppose that good primes should behave similarly to ordinary primes, or at least should exhibit similar “statistical” properties. We therefore formulate:

We now have the following result.