Prime divisors of the Lagarias sequence (Q1826298): Difference between revisions

\textit{J. C. Lagarias} in [Pac. J. Math. 118, 449-461 (1985; Zbl 0569.10003); Pac. J. Math. 162, No. 2, 393--397 (1994; Zbl 0790.11014)], posed a challenge problem to determine, under the GRH, the density of the set of prime numbers that occur as divisor of some term of the sequence \(\{x_n\}_{n\geq 1}\) defined by the linear recurrence \(x_{n+1}=x_n+x_{n-1}\) and the initial values \(x_0=3\) and \(x_1=1\). In the paper under review, the authors solve this problem by showing that the density in question is \[ {{1573727}\over {1569610}}\cdot \prod_{p~\text{ prime}}\Bigl(1-{{p}\over {p^3-1}}\Bigr). \] In fact, this paper shows how to compute, under GRH, the density of the set of prime factors of any nondegenerate binary recurrent sequence \(\{x_n\}_{n\geq 1}\). The method uses the Chebotarev Density Theorem and the principle of inclusion and exclusion to reduce the problem to the computation of a series involving degrees of algebraic number fields of the type \({\mathbb Q}[\zeta_{ij}, r^{1/ij},q^{1/i})\), where \(r\) is the ratio of the roots of the recurrent sequence, \(q\) is its initial quotient, and \(\zeta_{ij}\) is a primitive root of unity of order \(ij\). The analysis is quite complicated when \(r\) is of degree \(2\) (like in Lagarias's example), as there one has to separately consider split and inert primes, and several subtleties need to be taken care of at the prime \(2\). The authors result is that this density is \[ (c_{q,r}^++c_{q,r}^-)\prod_{p~\text{ prime}}\Bigl(1-{{p}\over {p^3-1}}\Bigr), \] where the ``correction factors'' \(c_{q,r}^+\) and \(c_{q,r}^-\) are rational numbers arising from the contributions of split and inert primes in \({\mathbb Q}[r]\), respectively. For the numerical example asked by Lagarias, the authors obtain \(c_{q,r}^+=712671/1569610\) and \(c_{q,r}^-=61504/112115.\)