##
**Density of prime divisors of linear recurrences.**
*(English)*
Zbl 0827.11006

Mem. Am. Math. Soc. 551, 102 p. (1995).

The author, following the works of Lucas, Laxton, Hasse and Lagarias, gives an algebraic development of the rational integer linear recurring sequences and investigates the prime divisors of the terms and the density of the set of prime divisors.

Such a sequence \(U\) of order \(m\) is defined by \(u_n= \alpha_1 \vartheta^n_1+ \cdots+ \alpha_m \vartheta^n_m\), where \(\vartheta_i\)’s are the roots of a monic polynomial \(f\) of degree \(m\) over the rational integers and \(\alpha_i\)’s depend on \(\vartheta_i\)’s and the first \(m\) initial terms of \(U\). A natural condition is that the sequence is not a degenerate one, i.e. \(\vartheta_i/ \vartheta_j\) \((i\neq j)\) are not a root of unity. Let \(F(f)\) be the set of sequences which have the same characteristic polynomial \(f\). We say the sequences \(U\) and \(V\) are equivalent if there exist integers \(\lambda\), \(\mu\), \(s\) such that \(\lambda u_{n+s}= \mu v_n\) for any natural number \(n\). The set of classes of equivalent sequences in \(F(f)\) is denoted by \(G(f)\). Defining a multiplication on \(F(f)\) and respectively on \(G(f)\), \((F(f), \cdot)\) is an abelian semigroup with identity and \((G(f), \cdot)\) is an abelian group.

A prime \(p\) is said to be a maximal divisor of some \(V\in F(f)\) if there exists an \(n\) such that \(p\) divides the terms \(v_n, v_{n+1}, \dots, v_{n+m-2}\), but \(p\nmid v_{n+m-1}\). The density of the set of maximal prime divisors of a sequence \(V\in F(f)\) relative to the set of all primes is denoted by \(\delta _{\max} (V)\). A similar definition can be given for classes in \(G(f)\). Investigating the structures \(F(f)\), \(G(f)\) and subgroups of \(G(f)\) and the properties of the prime divisors of their elements, the author concludes interesting results for the density of the set of maximal prime divisors.

There are shown several general results and also some for special sequences. E.g. if \(m=3\), \(\vartheta_i\)’s are integers and the sequences satisfy some other restrictions, then \(\delta= 6/7\). Many other similar explicit results are given for the cases \(m=2\) and \(m=3\) and also for \(m>3\). Some other type of results concerns the rank of apparition of primes in a sequence (the first positive \(n\) for which \(p\mid v_n\)), prime divisors of sequences \((p\mid v_n\) for some positive \(n)\) and twin prime divisors \((p\mid v_n\), \(p\mid v_{n+2}\) but \(p\nmid v_{n+1}\)).

Such a sequence \(U\) of order \(m\) is defined by \(u_n= \alpha_1 \vartheta^n_1+ \cdots+ \alpha_m \vartheta^n_m\), where \(\vartheta_i\)’s are the roots of a monic polynomial \(f\) of degree \(m\) over the rational integers and \(\alpha_i\)’s depend on \(\vartheta_i\)’s and the first \(m\) initial terms of \(U\). A natural condition is that the sequence is not a degenerate one, i.e. \(\vartheta_i/ \vartheta_j\) \((i\neq j)\) are not a root of unity. Let \(F(f)\) be the set of sequences which have the same characteristic polynomial \(f\). We say the sequences \(U\) and \(V\) are equivalent if there exist integers \(\lambda\), \(\mu\), \(s\) such that \(\lambda u_{n+s}= \mu v_n\) for any natural number \(n\). The set of classes of equivalent sequences in \(F(f)\) is denoted by \(G(f)\). Defining a multiplication on \(F(f)\) and respectively on \(G(f)\), \((F(f), \cdot)\) is an abelian semigroup with identity and \((G(f), \cdot)\) is an abelian group.

A prime \(p\) is said to be a maximal divisor of some \(V\in F(f)\) if there exists an \(n\) such that \(p\) divides the terms \(v_n, v_{n+1}, \dots, v_{n+m-2}\), but \(p\nmid v_{n+m-1}\). The density of the set of maximal prime divisors of a sequence \(V\in F(f)\) relative to the set of all primes is denoted by \(\delta _{\max} (V)\). A similar definition can be given for classes in \(G(f)\). Investigating the structures \(F(f)\), \(G(f)\) and subgroups of \(G(f)\) and the properties of the prime divisors of their elements, the author concludes interesting results for the density of the set of maximal prime divisors.

There are shown several general results and also some for special sequences. E.g. if \(m=3\), \(\vartheta_i\)’s are integers and the sequences satisfy some other restrictions, then \(\delta= 6/7\). Many other similar explicit results are given for the cases \(m=2\) and \(m=3\) and also for \(m>3\). Some other type of results concerns the rank of apparition of primes in a sequence (the first positive \(n\) for which \(p\mid v_n\)), prime divisors of sequences \((p\mid v_n\) for some positive \(n)\) and twin prime divisors \((p\mid v_n\), \(p\mid v_{n+2}\) but \(p\nmid v_{n+1}\)).

Reviewer: Péter Kiss (Eger)

### MSC:

11B37 | Recurrences |

11B05 | Density, gaps, topology |

11-02 | Research exposition (monographs, survey articles) pertaining to number theory |

11B83 | Special sequences and polynomials |