On numbers \(n\) dividing the \(n\)th term of a linear recurrence
type: Item
instance of: scholarly article
zbMATH Open document ID: 1262.11015
DOI: 10.1017/S0013091510001355
author: Juan José Alba González
author: Florian Luca
author: Carl Pomerance
author: Igor E. Shparlinski
publication date: 2012-06-18T00:00:00Z
full work available at URL: https://arxiv.org/abs/1010.4544
Mathematics Subject Classification ID: 11B37
Mathematics Subject Classification ID: 11A07
Mathematics Subject Classification ID: 11N25
zbMATH DE Number: 6047102
zbMATH Keywords: linear recurrence
zbMATH Keywords: Lucas sequence
zbMATH Keywords: divisibility
MaRDI profile type: Publication
arXiv ID: 1010.4544
cites work: On a problem of Oppenheim concerning ''Factorisatio Numerorum''
cites work: Existence of primitive divisors of Lucas and Lehmer numbers (with an appendix by M. Mignotte)
cites work: Q4946818
cites work: Multiplicities of recurrence sequences
cites work: Some divisibilities amongst the terms of linear recurrences
cites work: The Divisibility of an – bn by Powers of n
cites work: Polynomial values free of large prime factors
title: On numbers \(n\) dividing the \(n\)th term of a linear recurrence
published in: Proceedings of the Edinburgh Mathematical Society. Series II
review text: 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_…
description: scientific article; zbMATH DE number 6047102