On the number of residues of linear recurrences

is not a root of unity. We show that this problem is related to the existence of special primitive divisors of certain Lehmer sequences, and we deduce some consequences on

m a t h f r a k M (g)

. In particular, for

, we prove that

m i n m a t h f r a k M (g)

for every integer

m g e q 7

with

m e q 10

and

4 m i d m

.

Review text

An integer sequence \(\mathbf{s}=(s_{n})_{n\geq0}\) is\ called a linear recurrence relation if there are integers \(c_{1},...,c_{r}\in\mathbb{Z}\) such that for every integer \(n\geq r\), we have \[ s_{n}=c_{1}s_{n-1}+c_{2}s_{n-2}+...+c_{r}s_{n-r}. \] The \(r\) values \(s_{0},...,s_{r-1}\) are called the \textit{initial conditions} of the integer sequence \(\mathbf{s}\), and \[ g(X)=X^{r}-c_{1}X^{r-1}-c_{2}X^{r-2}-...-c_{r} \] is called the \textit{characteristic polynomial} of \(\mathbf{s}\). Let \(g\in\mathbb{Z}[X]\) be any nonconstant monic polynomial. Also, let \(\mathfrak{M}(g)\) be the set of positive integers \(m\) such that there exists an integer linear recurrence relation \((s_{n})_{n\geq0}\) with characteristic polynomial \(g\) and a positive integer \(M\) for which \((s_{n})_{n\geq0}\) has exactly \(m\) distinct residues modulo \(M\). \textit{A. Dubickas} and \textit{A. Novikas} [J. Number Theory 215, 120--137 (2020; Zbl 1473.11039)] have shown that \(\mathfrak{M}(X^{2}-X-1)=\mathbb{N}\). The author of the paper under review examines \(\mathfrak{M}(g)\) in the case in which \(g\) is divisible by a monic quadratic polynomial \(f\in\mathbb{Z}[X]\) with roots \(\alpha,\beta\) such that \(\alpha\beta=\pm1\) and \(\alpha/\beta\) is not a root of unity. Also, the author demonstrates that this problem is pertained to the existence of special primitive divisors of certain Lehmer sequences.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: On the number of residues of linear recurrences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2065753)