On numbers \(n\) dividing the \(n\)th term of a linear recurrence
In this paper the number of elements \(u_n\) of a homogeneous integer linear recurrence sequence \(\{u_n\}_{n\geq 0}\) that are divisible by its index \(n\) is studied. The study covers such sequences in the case that their characteristic polynomial has distinct roots \(\alpha_1,\dots,\alpha_k\). Then, as is well known, \(u_n=\sum_{i=1}^kA_i\alpha_i^n\), where \(A_i\in K\), with \(K=\mathbb Q[\alpha_1,\dots,\alpha_k]\). For the set \(\mathcal N_u:=\{n\in\mathbb N: n \text{ divides } u_n\}\), the authors show that there is a positive constant \(c_0(k)\) depending only on \(k\) such that for \(x\) sufficiently large NEWLINE\[NEWLINE \mathcal N_u(x):=\#\{n\in\mathcal N_u: n\leq x\}\leq c_0(k)\frac{x}{\log x}. NEWLINE\]NEWLINE Here it is also assumed that \(k\geq 2\) and no \(\alpha_i/\alpha_j\) with \(i\neq j\) is a root of unity. This general result is essentially best possible, since, for the sequence \(u_n=2^n-2\), the set \(\mathcal N_u\) contains all the primes.NEWLINENEWLINETurning next to the particular case of \(\{u_n\}\) a Lucas sequence (of the first kind, so \(k=2,u_0=0,u_1=1\)) the authors prove a better upper bound NEWLINE\[NEWLINE \mathcal N_u(x)\leq c_0(k)\frac{x}{L(x)^{1+o(1)}} \qquad\text{ for }x\to\infty, NEWLINE\]NEWLINE where \(L(x)=\exp\left(\sqrt{\log x\log\log x}\right)\). In the other direction, they prove that for Lucas sequences with \(|\alpha_1-\alpha_2|\neq 1\) and \(|\alpha_1\alpha_2|\neq 1\) that there exist positive constants \(c_1\) and \(x_0\) such that NEWLINE\[NEWLINE \mathcal N_u(x)\geq \exp\left(c_1(\log\log x)^2\right)\qquad\text{ for }x>x_0. NEWLINE\]NEWLINE In the special case \(|\alpha_1\alpha_2|= 1\) they improve this lower bound to a positive power of \(x\).NEWLINENEWLINEAn important function used in the proofs is \(T_u(p)\), defined for any prime \(p\) and sequence \(u\) as the largest non-negative integer \(T\) such that \(p\) does not divide NEWLINE\[NEWLINE \prod_{0\leq x_2,\dots,x_k\leq T} \max{1,|N_{K/\mathbb Q}(D_u(0,x_2,\dots,x_k))|}, NEWLINE\]NEWLINE where \(D_u(0,x_2,\dots,x_k):=\det\left(\alpha_i^{x_j}\right)_{1\leq i,j\leq k}\). It is essentially a generalisation of the so-called \textit{index of appearance} for Lucas sequences, the index of appearance for such sequences being \(T_u(p)+1\).
scientific article; zbMATH DE number 6047102