1 Introduction and results
Let
$k$
be a positive integer, and let
$a_{1},\ldots ,a_{k}$
and
$u_{0},\ldots ,u_{k-1}$
be integers such that
$a_{k}$
is non-zero and
$u_{0},\ldots ,u_{k-1}$
are not all zero. Put
$$\begin{eqnarray}u_{n}=a_{1}u_{n-1}+\cdots +a_{k}u_{n-k}\quad \text{for }n\geqslant k.\end{eqnarray}$$
The sequence
$(u_{n})_{n\geqslant 0}$
is a linear recurrence sequence of integers of order
$k$
. Its characteristic polynomial
$$\begin{eqnarray}G(X):=X^{k}-a_{1}X^{k-1}-\cdots -a_{k}\end{eqnarray}$$
can be written as
$$\begin{eqnarray}G(X)=\mathop{\prod }_{i=1}^{t}(X-\unicode[STIX]{x1D6FC}_{i})^{\ell _{i}},\end{eqnarray}$$
where
$\unicode[STIX]{x1D6FC}_{1},\ldots ,\unicode[STIX]{x1D6FC}_{t}$
are distinct algebraic numbers and
$\ell _{1},\ldots ,\ell _{t}$
are positive integers. It is then well known (see e.g., [Reference Shorey and Tijdeman11, Ch. C]) that there exist polynomials
$f_{1}(X),\ldots ,f_{t}(X)$
of degrees less than
$\ell _{1},\ldots ,\ell _{t}$
, respectively, and with coefficients in the algebraic number field
$K:=\mathbf{Q}(\unicode[STIX]{x1D6FC}_{1},\ldots ,\unicode[STIX]{x1D6FC}_{t})$
, such that
$$\begin{eqnarray}u_{n}=f_{1}(n)\unicode[STIX]{x1D6FC}_{1}^{n}+\cdots +f_{t}(n)\unicode[STIX]{x1D6FC}_{t}^{n}\quad \text{for }n\geqslant 0.\end{eqnarray}$$
The recurrence sequence
$(u_{n})_{n\geqslant 0}$
is said to be degenerate if there are indices
$i,j$
with
$1\leqslant i<j\leqslant t$
such that
$\unicode[STIX]{x1D6FC}_{i}/\unicode[STIX]{x1D6FC}_{j}$
is a root of unity.
We keep the above notation throughout the present paper. The case
$t=1$
, that is, of sequences
$(f(n)a^{n})_{n\geqslant 0}$
where
$f(X)$
is an integer polynomial and
$a$
a non-zero integer, can be treated using the work of [Reference Bugeaud, Evertse and Győry1, Reference Gross and Vincent4]. Thus, in all what follows, we assume that
$t\geqslant 2$
, the polynomials
$f_{1}(X),\ldots ,f_{t}(X)$
are non-zero, and
$(u_{n})_{n\geqslant 0}$
is non-degenerate.
By means of a
$p$
-adic generalization of the Thue–Siegel theorem, Mahler [Reference Mahler6] proved that every non-degenerate binary recurrence sequence
$(u_{n})_{n\geqslant 0}$
tends in absolute value to infinity as
$n$
tends to infinity. This was extended to every non-degenerate recurrence sequence by van der Poorten and Schlickewei [Reference van der Poorten and Schlickewei9] and, independently, Evertse [Reference Evertse2]. They proved the following stronger result. For an integer
$m$
, let
$P[m]$
denote its greatest prime factor, with the convention that
$P[0]=P[\pm 1]=1$
. By means of a
$p$
-adic version of the Schmidt subspace theorem, they established that
$P[u_{n}]$
tends to infinity as
$n$
tends to infinity.
This result is ineffective, but an effective version of it was proved by Stewart [Reference Stewart12, Reference Stewart13], under an additional assumption. Without loss of generality, assume that
$$\begin{eqnarray}|\unicode[STIX]{x1D6FC}_{1}|\geqslant |\unicode[STIX]{x1D6FC}_{2}|\geqslant \cdots \geqslant |\unicode[STIX]{x1D6FC}_{t}|>0.\end{eqnarray}$$
Then, if
$|\unicode[STIX]{x1D6FC}_{1}|>|\unicode[STIX]{x1D6FC}_{2}|$
(this assumption is often called the dominant root assumption) and
$u_{n}\not =f_{1}(n)\unicode[STIX]{x1D6FC}_{1}^{n}$
, there are positive numbers
$c_{1}$
and
$c_{2}$
, which are effectively computable in terms of
$(u_{n})_{n\geqslant 0}$
(which exactly means, in terms of
$a_{1},\ldots ,a_{k}$
and
$u_{0},\ldots ,u_{k-1}$
), such that
$$\begin{eqnarray}P[u_{n}]>c_{1}\log n\frac{\log \log n}{\log \log \log n}\quad \text{for }n>c_{2};\end{eqnarray}$$
see also [Reference Stewart14, Reference Stewart15] for stronger results for binary recurrence sequences.
In the present note, we investigate the following related problem. Let
$S=\{q_{1},\ldots ,q_{s}\}$
be a finite, non-empty set of distinct prime numbers. For a non-zero integer
$m$
, write
$m=q_{1}^{r_{1}}\cdots q_{s}^{r_{s}}M$
, where
$r_{1},\ldots ,r_{s}$
are non-negative integers and
$M$
is an integer relatively prime to
$q_{1}\cdots q_{s}$
. We define the
$S$
-part
$[m]_{S}$
of
$m$
by
$$\begin{eqnarray}[m]_{S}:=q_{1}^{r_{1}}\cdots q_{s}^{r_{s}}.\end{eqnarray}$$
We ask for a non-trivial upper bound for the
$S$
-part of the
$n$
th term of a non-degenerate recurrence sequence of integers.
A first result on this question was obtained by Mahler [Reference Mahler7] in 1966 for a special family of binary recurrence sequences. We keep the above notation and assume that
$k=2$
,
$a_{2}\leqslant -2$
,
$-4a_{2}>a_{1}^{2}$
, and that
$a_{1}$
and
$a_{2}$
are coprime. By means of a
$p$
-adic extension of the Roth theorem established by Ridout [Reference Ridout10], Mahler showed that, if
$n$
is large enough, then we have
$[u_{n}]_{S}<|u_{n}|^{\unicode[STIX]{x1D700}}$
. He observed that his result implies that
$P[u_{n}]$
tends to infinity as
$n$
tends to infinity, a statement which was new at that time.
Before stating our first theorem, which extends Mahler’s result to every non-degenerate recurrence sequence of integers, we need to introduce some additional notation. Choose embeddings of
$K$
in
$\mathbf{C}$
and of
$K$
in
$\mathbf{Q}_{p}$
, for every prime
$p$
. These embeddings define extensions to
$K$
of the ordinary absolute value
$|\cdot |$
and of the
$p$
-adic absolute value
$|\cdot |_{p}$
for every prime
$p$
, normalized such that
$|p|_{p}=p^{-1}$
. Define the quantity
$$\begin{eqnarray}\unicode[STIX]{x1D6FF}:=-\frac{\mathop{\sum }_{p\in S}\log \max \{|\unicode[STIX]{x1D6FC}_{1}|_{p},\ldots ,|\unicode[STIX]{x1D6FC}_{t}|_{p}\}}{\log \max \{|\unicode[STIX]{x1D6FC}_{1}|,\ldots ,|\unicode[STIX]{x1D6FC}_{t}|\}}.\end{eqnarray}$$
By our assumptions on the sequence
$(u_{n})_{n\geqslant 0}$
,
$\unicode[STIX]{x1D6FC}_{1},\ldots ,\unicode[STIX]{x1D6FC}_{t}$
are algebraic integers which are not all roots of unity and whose product is a non-zero rational integer. Therefore,
$\max _{i}|\unicode[STIX]{x1D6FC}_{i}|>1$
, and
$\max _{i}|\unicode[STIX]{x1D6FC}_{i}|_{p}\leqslant 1$
for
$p\in S$
. Hence,
$\unicode[STIX]{x1D6FF}$
is well defined and
$\unicode[STIX]{x1D6FF}\geqslant 0$
. Furthermore, we observe that
$\unicode[STIX]{x1D6FF}<1$
since
$t\geqslant 2$
. Indeed, letting
$A:=\max _{i}|\unicode[STIX]{x1D6FC}_{i}|$
,
$A_{p}:=\max _{i}|\unicode[STIX]{x1D6FC}_{i}|_{p}$
for
$p\in S$
and
$a:=\unicode[STIX]{x1D6FC}_{1}\cdots \unicode[STIX]{x1D6FC}_{t}$
, we have
$$\begin{eqnarray}(1-\unicode[STIX]{x1D6FF})\log A=\log A+\mathop{\sum }_{p\in S}\log A_{p}\geqslant t^{-1}\biggl(\log |a|+\mathop{\sum }_{p\in S}\log |a|_{p}\biggr)\geqslant 0,\end{eqnarray}$$
where both inequality signs are equality signs if and only if
$|\unicode[STIX]{x1D6FC}_{1}|_{p}=\cdots =|\unicode[STIX]{x1D6FC}_{t}|_{p}$
for
$p\in S\cup \{\infty \}$
and
$|\unicode[STIX]{x1D6FC}_{1}|_{p}=\cdots =|\unicode[STIX]{x1D6FC}_{t}|_{p}=1$
for all prime numbers
$p$
outside
$S$
, that is, if all quotients
$\unicode[STIX]{x1D6FC}_{i}/\unicode[STIX]{x1D6FC}_{j}$
are roots of unity, which is against our assumption. So the left-hand side of the above inequality is
${>}0$
, thus
$\unicode[STIX]{x1D6FF}<1$
.
Our first result is an easy consequence of work of Evertse, see for example [Reference Evertse2, Theorem 2] or [Reference Evertse and Győry3, Proposition 6.2.1].
Theorem 1.1. Let
$(u_{n})_{n\geqslant 0}$
be a non-degenerate recurrence sequence of integers defined in (1.1). Let
$S:=\{q_{1},\ldots ,q_{s}\}$
be a finite, non-empty set of prime numbers, and
$\unicode[STIX]{x1D6FF}$
be as in (1.4). Further, let
$\unicode[STIX]{x1D700}>0$
. Then for every sufficiently large
$n$
we have
$$\begin{eqnarray}|u_{n}|^{\unicode[STIX]{x1D6FF}-\unicode[STIX]{x1D700}}\leqslant [u_{n}]_{S}\leqslant |u_{n}|^{\unicode[STIX]{x1D6FF}+\unicode[STIX]{x1D700}}.\end{eqnarray}$$
In particular, if
$\gcd (q_{1}\cdots q_{s},a_{1},\ldots ,a_{k})=1$
, we have for every sufficiently large
$n$
,
$$\begin{eqnarray}[u_{n}]_{S}\leqslant |u_{n}|^{\unicode[STIX]{x1D700}}.\end{eqnarray}$$
Observe that the assumption
$\gcd (q_{1}\cdots q_{s},a_{1},\ldots ,a_{k})=1$
implies that
$\unicode[STIX]{x1D6FF}=0$
. Indeed, suppose
$\unicode[STIX]{x1D6FF}>0$
. Then, there is a prime number
$p$
in
$S$
such that
$\max _{i}|\unicode[STIX]{x1D6FC}_{i}|_{p}<1$
. Since
$a_{1},\ldots ,a_{k}$
are up to sign the elementary symmetric functions in the
$\unicode[STIX]{x1D6FC}_{i}$
taken
$\ell _{i}$
times, we must then have
$|a_{i}|_{p}<1$
for
$i=1,\ldots ,k$
. This is clearly impossible.
The proof of Theorem 1.1 depends ultimately on the
$p$
-adic Schmidt subspace theorem, therefore we cannot compute the set of
$n$
for which (1.5) does not hold. It seems to be difficult to bound its cardinality, even by means of the strongest available versions of the quantitative subspace theorem.
Our main effective theorem is the following.
Theorem 1.2. Let
$(u_{n})_{n\geqslant 0}$
be a non-degenerate recurrence sequence of integers having a dominant root. Let
$S$
be a finite, non-empty set of prime numbers. Then, there exist effectively computable positive numbers
$c_{1}$
and
$c_{2}$
, depending only on
$(u_{n})_{n\geqslant 0}$
and
$S$
, such that
$$\begin{eqnarray}[u_{n}]_{S}\leqslant |u_{n}|^{1-c_{1}},\end{eqnarray}$$
for every
$n\geqslant c_{2}$
.
Removing the dominant root assumption seems to be very difficult. However, this can be done for non-degenerate binary recurrence sequences of integers.
Theorem 1.3. Let
$(u_{n})_{n\geqslant 0}$
be a non-degenerate binary recurrence sequence of integers. Assume that
$u_{n}=a\unicode[STIX]{x1D6FC}^{n}+b\unicode[STIX]{x1D6FD}^{n}$
for
$n\geqslant 0$
, with
$ab\unicode[STIX]{x1D6FC}\unicode[STIX]{x1D6FD}\not =0$
. Let
$S$
be a finite, non-empty set of prime numbers. Then, there exist effectively computable positive numbers
$c_{1}$
, depending only on
$(u_{n})_{n\geqslant 0}$
, and
$c_{2}$
, depending only on
$(u_{n})_{n\geqslant 0}$
and
$S$
, such that
$$\begin{eqnarray}[u_{n}]_{S}\leqslant |u_{n}|^{1-c_{1}}\quad \text{for every }n\geqslant c_{2}.\end{eqnarray}$$
We stress that, in Theorem 1.3, the number
$c_{1}$
is independent of the set
$S$
of prime numbers. Clearly, when
$\unicode[STIX]{x1D6FC}$
and
$\unicode[STIX]{x1D6FD}$
are complex conjugates, there is no dominant root.
Our next statement is a
$p$
-adic analogue to Theorem 1.2.
Let
$p$
be a prime number. We say that the recurrence sequence
$(u_{n})_{n\geqslant 0}$
as in (1.2) has a
$p$
-adic dominant root if there exists
$j$
such that
$1\leqslant j\leqslant t$
and
$|\unicode[STIX]{x1D6FC}_{j}|_{p}=1$
, while
$|\unicode[STIX]{x1D6FC}_{i}|_{p}<1$
for
$1\leqslant i\leqslant t$
with
$i\not =j$
.
Theorem 1.4. Let
$p$
be a prime number. Let
$(u_{n})_{n\geqslant 0}$
be a non-degenerate recurrence sequence of integers having a
$p$
-adic dominant root. Let
$S$
be a finite, non-empty set of prime numbers. Then, there exist positive numbers
$c_{1}$
and
$c_{2}$
, depending only on
$(u_{n})_{n\geqslant 0}$
and
$S$
, such that
$$\begin{eqnarray}[u_{n}]_{S}\leqslant |u_{n}|^{1-c_{1}},\end{eqnarray}$$
for every
$n\geqslant c_{2}$
. Furthermore, for every positive real number
$\unicode[STIX]{x1D700}$
, there exists an effectively computable integer
$c_{3}$
, depending only on
$(u_{n})_{n\geqslant 0}$
and
$\unicode[STIX]{x1D700}$
, such that
$$\begin{eqnarray}P[u_{n}]>(1-\unicode[STIX]{x1D700})\log n\frac{\log \log n}{\log \log \log n}\quad \text{for }n>c_{3}.\end{eqnarray}$$
The last statement of Theorem 1.4 seems to be new.
The proof of Theorem 1.2 allows us to establish the following statement.
Theorem 1.5. Let
$\unicode[STIX]{x1D703}>1$
be a real algebraic number such that all of its Galois conjugates are less than
$\unicode[STIX]{x1D703}$
in modulus. Let
$\unicode[STIX]{x1D706}$
be a non-zero real algebraic number. Let
$S$
be a finite set of prime numbers. If
$\unicode[STIX]{x1D703}^{\ell }\not \in \mathbf{Z}$
for every integer
$\ell \geqslant 1$
, then there exist effectively computable positive numbers
$c_{1}$
and
$c_{2}$
, depending only on
$\unicode[STIX]{x1D706}$
,
$\unicode[STIX]{x1D703}$
, and
$S$
, such that
$$\begin{eqnarray}[\lfloor \unicode[STIX]{x1D706}\unicode[STIX]{x1D703}^{n}\rfloor ]_{S}\leqslant |\unicode[STIX]{x1D706}\unicode[STIX]{x1D703}^{n}|^{1-c_{1}}\quad \text{for every }n\geqslant c_{2}.\end{eqnarray}$$
Theorem 1.5 applies to the sequence of integer parts of
$(3/2)^{n}$
. Lower bounds for the greatest prime factor of
$\lfloor \unicode[STIX]{x1D703}^{n}\rfloor$
, where
$\unicode[STIX]{x1D703}>1$
is an algebraic number such that
$\unicode[STIX]{x1D703}^{\ell }$
is not an integer for every integer
$\ell \geqslant 1$
, have been obtained by Luca and Mignotte [Reference Luca and Mignotte5]. They are similar to (1.3).
It would be interesting to see under which assumption on the algebraic numbers
$\unicode[STIX]{x1D706}$
and
$\unicode[STIX]{x1D703}$
we get
$$\begin{eqnarray}[\lfloor \unicode[STIX]{x1D706}\unicode[STIX]{x1D703}^{n}\rfloor ]_{S}\leqslant |\unicode[STIX]{x1D706}\unicode[STIX]{x1D703}^{n}|^{\unicode[STIX]{x1D700}},\end{eqnarray}$$
for every
$\unicode[STIX]{x1D700}>0$
and every sufficiently large integer
$n$
.
2 Proof of Theorem 1.1
Recall that we have set
$K:=\mathbf{Q}(\unicode[STIX]{x1D6FC}_{1},\ldots ,\unicode[STIX]{x1D6FC}_{t})$
. Denote by
$M_{K}$
the set of places of
$K$
. For
$v$
in
$M_{K}$
, we choose a normalized absolute value
$|\cdot |_{v}$
such that if
$v$
is an infinite place, then
$$\begin{eqnarray}|x|_{v}=|x|^{[K_{v}:\mathbf{R}]/[K:\mathbf{Q}]}\quad \text{for }x\in \mathbf{Q},\end{eqnarray}$$
while if
$v$
is finite and lies above the prime
$p$
, then
$$\begin{eqnarray}|x|_{v}=|x|_{p}^{[K_{v}:\mathbf{Q}_{p}]/[K:\mathbf{Q}]}\quad \text{for }x\in \mathbf{Q}.\end{eqnarray}$$
These absolute values satisfy the product formula
$$\begin{eqnarray}\mathop{\prod }_{v\in M_{K}}|x|_{v}=1\quad \text{for every non-zero }x\in K.\end{eqnarray}$$
Moreover, if
$x\in \mathbf{Q}$
, then
$\prod _{v|\infty }|x|_{v}=|x|$
and
$\prod _{v|p}|x|_{v}=|x|_{p}$
, where the products are taken over all infinite places of
$K$
, respectively all places of
$K$
lying above the prime number
$p$
.
Let
$T$
be a finite set of places of
$K$
, containing all infinite places. Define the ring of
$T$
-integers and the group of
$T$
-units of
$K$
by
$$\begin{eqnarray}\displaystyle & \displaystyle O_{T}:=\{x\in K:|x|_{v}\leqslant 1\text{ for }v\in M_{K}\setminus T\}, & \displaystyle \nonumber\\ \displaystyle & \displaystyle O_{T}^{\ast }:=\{x\in K:|x|_{v}=1\text{ for }v\in M_{K}\setminus T\}, & \displaystyle \nonumber\end{eqnarray}$$
respectively. Further define
$$\begin{eqnarray}H_{T}(x_{1},\ldots ,x_{n}):=\mathop{\prod }_{v\in T}\max \{|x_{1}|_{v},\ldots ,|x_{n}|_{v}\}\quad \text{for }x_{1},\ldots ,x_{n}\in O_{T}.\end{eqnarray}$$
Our main tool is the following result, which is [Reference Evertse and Győry3, Proposition 6.2.1] and which is essentially the same as [Reference Evertse2, Theorem 2].
Proposition 2.1. Let
$U$
be a subset of
$T$
,
$t\geqslant 2$
and
$\unicode[STIX]{x1D700}>0$
. Then for all
$x_{1},\ldots ,x_{t}\in O_{T}$
such that every non-empty subsum of
$x_{1}+\cdots +x_{t}$
is non-zero, we have
$$\begin{eqnarray}\mathop{\prod }_{i=1}^{t}\mathop{\prod }_{v\in T}|x_{i}|_{v}\cdot \mathop{\prod }_{v\in U}|x_{1}+\cdots +x_{t}|_{v}\gg \mathop{\prod }_{v\in U}\max \{|x_{1}|_{v},\ldots ,|x_{t}|_{v}\}\cdot H_{T}(x_{1},\ldots ,x_{t})^{-\unicode[STIX]{x1D700}},\end{eqnarray}$$
where the implied constant depends on
$K,T,t$
and
$\unicode[STIX]{x1D700}$
.
The proof of this result depends on the
$p$
-adic Schmidt subspace theorem, therefore the implied constant is ineffective.
Proof of Theorem 1.1.
We introduce the following notation. First, by
$O(1)$
we denote constants depending on
$(u_{n})_{n\geqslant 0}$
and
$S$
. Second, we choose a real number
$\unicode[STIX]{x1D700}^{\prime }>0$
which will later be taken sufficiently small in terms of
$\unicode[STIX]{x1D700}$
; then constants implied by the Vinogradov symbols
$\ll$
,
$\gg$
will depend on
$(u_{n})_{n\geqslant 0}$
,
$S$
and
$\unicode[STIX]{x1D700}^{\prime }$
. Lastly, we put
$$\begin{eqnarray}A:=\max \{|\unicode[STIX]{x1D6FC}_{1}|,\ldots ,|\unicode[STIX]{x1D6FC}_{t}|\},\qquad A_{p}:=\max \{|\unicode[STIX]{x1D6FC}_{1}|_{p},\ldots ,|\unicode[STIX]{x1D6FC}_{t}|_{p}\}\quad \text{for }p\in S,\end{eqnarray}$$
and
$$\begin{eqnarray}A_{v}:=\max \{|\unicode[STIX]{x1D6FC}_{1}|_{v},\ldots ,|\unicode[STIX]{x1D6FC}_{t}|_{v}\}\quad \text{for }v\in M_{K}.\end{eqnarray}$$
Then by our choice of the absolute values on
$K$
, we have
$$\begin{eqnarray}\mathop{\prod }_{v|\infty }A_{v}=A,\qquad \mathop{\prod }_{v|p}A_{v}=A_{p}\quad \text{for }p\in S.\end{eqnarray}$$
We choose a finite set of places
$T$
of
$K$
, containing all infinite places and all places lying above the primes in
$S$
, such that
$\unicode[STIX]{x1D6FC}_{1},\ldots ,\unicode[STIX]{x1D6FC}_{t}\in O_{T}^{\ast }$
and the coefficients of
$f_{1}(X),\ldots ,f_{t}(X)$
are in
$O_{T}$
. Let for the moment
$U$
be any subset of
$T$
. Each subsum of
$u_{n}=\sum _{i=1}^{t}f_{i}(n)\unicode[STIX]{x1D6FC}_{i}^{n}$
is a non-degenerate linear recurrence sequence of algebraic numbers in
$K$
. So by the Skolem–Mahler–Lech theorem, there are only finitely many non-negative integers
$n$
for which at least one of the subsums of
$u_{n}$
vanishes. Then by Proposition 2.1 we have for the remaining positive integers
$n$
,
$$\begin{eqnarray}\displaystyle & & \displaystyle \mathop{\prod }_{i=1}^{t}\mathop{\prod }_{v\in T}|f_{i}(n)\unicode[STIX]{x1D6FC}_{i}^{n}|_{v}\cdot \mathop{\prod }_{v\in U}|u_{n}|_{v}\nonumber\\ \displaystyle & & \displaystyle \quad \gg \,\mathop{\prod }_{v\in U}\max _{1\leqslant i\leqslant t}|f_{i}(n)\unicode[STIX]{x1D6FC}_{i}^{n}|_{v}\cdot \biggl(\mathop{\prod }_{v\in T}\max _{1\leqslant i\leqslant t}|f_{i}(n)\unicode[STIX]{x1D6FC}_{i}^{n}|_{v}\biggr)^{-\unicode[STIX]{x1D700}^{\prime }/2}.\nonumber\end{eqnarray}$$
Since
$\prod _{v\in T}|\unicode[STIX]{x1D6FC}_{i}|_{v}=1$
for
$i=1,\ldots ,t$
, the left-hand side of this inequality is
$$\begin{eqnarray}\ll (2n)^{O(1)}\mathop{\prod }_{v\in U}|u_{n}|_{v},\end{eqnarray}$$
while the right-hand side is
$$\begin{eqnarray}\gg (2n)^{-O(1)}\biggl(\mathop{\prod }_{v\in U}A_{v}\biggr)^{n}\cdot \biggl(\mathop{\prod }_{v\in T}A_{v}\biggr)^{-n\unicode[STIX]{x1D700}^{\prime }/2}\gg (2n)^{-O(1)}\biggl(\mathop{\prod }_{v\in U}A_{v}\biggr)^{n}\cdot A^{-n\unicode[STIX]{x1D700}^{\prime }/2},\end{eqnarray}$$
where we have used
$A_{v}\leqslant 1$
if
$v$
is finite and
$\prod _{v|\infty }A_{v}=A$
. Thus,
$$\begin{eqnarray}\mathop{\prod }_{v\in U}|u_{n}|_{v}\gg (2n)^{-O(1)}\biggl(\mathop{\prod }_{v\in U}A_{v}\biggr)^{n}\cdot A^{-n\unicode[STIX]{x1D700}^{\prime }/2}.\end{eqnarray}$$
On the other hand, we have a trivial upper bound
$$\begin{eqnarray}\mathop{\prod }_{v\in U}|u_{n}|_{v}\leqslant (2n)^{O(1)}\biggl(\mathop{\prod }_{v\in U}A_{v}\biggr)^{n}.\end{eqnarray}$$
Since
$A>1$
, this implies that for every sufficiently large
$n$
,
$$\begin{eqnarray}\biggl(\mathop{\prod }_{v\in U}A_{v}\biggr)^{n}\cdot A^{-n\unicode[STIX]{x1D700}^{\prime }}\leqslant \mathop{\prod }_{v\in U}|u_{n}|_{v}\leqslant \biggl(\mathop{\prod }_{v\in U}A_{v}\biggr)^{n}\cdot A^{n\unicode[STIX]{x1D700}^{\prime }}.\end{eqnarray}$$
We apply this with two choices of
$U$
. First let
$U$
consist of the infinite places of
$K$
. Then,
$$\begin{eqnarray}\mathop{\prod }_{v\in U}|u_{n}|_{v}=|u_{n}|\quad \text{and}\quad \mathop{\prod }_{v\in U}A_{v}=A,\end{eqnarray}$$
implying that for all sufficiently large
$n$
,
$$\begin{eqnarray}A^{n(1-\unicode[STIX]{x1D700}^{\prime })}\leqslant |u_{n}|\leqslant A^{n(1+\unicode[STIX]{x1D700}^{\prime })}.\end{eqnarray}$$
Next, let
$U$
consist of the places of
$K$
lying above the primes in
$S$
. Then
$$\begin{eqnarray}\mathop{\prod }_{v\in U}|u_{n}|_{v}=\mathop{\prod }_{p\in S}|u_{n}|_{p}=[u_{n}]_{S}^{-1}\end{eqnarray}$$
and
$$\begin{eqnarray}\mathop{\prod }_{v\in U}A_{v}=\mathop{\prod }_{p\in S}A_{p}=A^{-\unicode[STIX]{x1D6FF}},\end{eqnarray}$$
hence
$$\begin{eqnarray}A^{n(\unicode[STIX]{x1D6FF}-\unicode[STIX]{x1D700}^{\prime })}\leqslant [u_{n}]_{S}\leqslant A^{n(\unicode[STIX]{x1D6FF}+\unicode[STIX]{x1D700}^{\prime })}\end{eqnarray}$$
for every sufficiently large
$n$
. By taking
$\unicode[STIX]{x1D700}^{\prime }$
sufficiently small in terms of
$\unicode[STIX]{x1D700}$
, Theorem 1.1 easily follows.◻
3 Proofs of Theorems 1.2 and 1.3
As usual,
$\text{h}(\unicode[STIX]{x1D6FC})$
denotes the (logarithmic) Weil height of the algebraic number
$\unicode[STIX]{x1D6FC}$
.
Our first auxiliary result is an immediate corollary of a theorem of Matveev [Reference Matveev8].
Theorem 3.1. Let
$n\geqslant 2$
be an integer, let
$\unicode[STIX]{x1D6FC}_{1},\ldots ,\unicode[STIX]{x1D6FC}_{n}$
be non-zero algebraic numbers and let
$b_{1},\ldots ,b_{n}$
be integers. Further, let
$D$
be the degree over
$\mathbf{Q}$
of a number field containing the
$\unicode[STIX]{x1D6FC}_{i}$
, and let
$A_{1},\ldots ,A_{n}$
be real numbers with
$$\begin{eqnarray}\log A_{i}\geqslant \max \biggl\{\text{h}(\unicode[STIX]{x1D6FC}_{i}),\frac{|\text{log}\,\unicode[STIX]{x1D6FC}_{i}|}{D},\frac{0.16}{D}\biggr\},\quad 1\leqslant i\leqslant n.\end{eqnarray}$$
Set
$$\begin{eqnarray}B:=\max \biggl\{1,\max \biggl\{|b_{j}|\frac{\log A_{j}}{\log A_{n}}:1\leqslant j\leqslant n\biggr\}\biggr\}.\end{eqnarray}$$
Then, we have
$$\begin{eqnarray}\displaystyle \log |\unicode[STIX]{x1D6FC}_{1}^{b_{1}}\cdots \unicode[STIX]{x1D6FC}_{n}^{b_{n}}-1| & {>} & \displaystyle -4\times 30^{n+4}(n+1)^{5.5}D^{n+2}\nonumber\\ \displaystyle & & \displaystyle \times \,\log (\text{e}D)\log (\text{e}nB)\log A_{1}\cdots \log A_{n}.\nonumber\end{eqnarray}$$
The key point for our main theorem is the factor
$\log A_{n}$
in the denominator in the definition of
$B$
.
Our second auxiliary result is extracted from [Reference Yu16].
Theorem 3.2. Let
$p$
be a prime number,
$K$
an algebraic number field of degree
$D$
and
$|\cdot |_{p}$
an absolute value on
$K$
with
$|p|_{p}=p^{-1}$
. Further, let
$\unicode[STIX]{x1D6FC}_{1},\ldots ,\unicode[STIX]{x1D6FC}_{n}$
be elements of
$K$
, and let
$A_{1},\ldots ,A_{n}$
be real numbers with
$$\begin{eqnarray}\log A_{i}\geqslant \max \biggl\{\text{h}(\unicode[STIX]{x1D6FC}_{i}),\frac{1}{16\text{e}^{2}D^{2}}\biggr\},\quad 1\leqslant i\leqslant n.\end{eqnarray}$$
Let
$b_{1},\ldots ,b_{n}$
denote non-zero rational integers and let
$B$
and
$B_{n}$
be real numbers such that
$$\begin{eqnarray}B\geqslant \max \{|b_{1}|,\ldots ,|b_{n}|,3\}\quad and\quad B\geqslant B_{n}\geqslant |b_{n}|.\end{eqnarray}$$
Assume that
$$\begin{eqnarray}|b_{n}|_{p}\geqslant |b_{j}|_{p},\quad j=1,\ldots ,n.\end{eqnarray}$$
Let
$\unicode[STIX]{x1D6FF}$
be a real number with
$0<\unicode[STIX]{x1D6FF}\leqslant 1/2$
. With the above notation, we have
$$\begin{eqnarray}\displaystyle \log |\unicode[STIX]{x1D6FC}_{1}^{b_{1}}\cdots \unicode[STIX]{x1D6FC}_{n}^{b_{n}}-1|_{p} & {>} & \displaystyle -(16\text{e}D)^{2(n+1)}n^{3/2}(\log (2nD))^{2}D^{n}\frac{p^{D}}{\log p}\nonumber\\ \displaystyle & & \displaystyle \times \,\max \biggl\{(\log A_{1})\cdots (\log A_{n})(\log T),\frac{\unicode[STIX]{x1D6FF}B}{B_{n}c_{0}(n,D)}\biggr\},\nonumber\end{eqnarray}$$
where
$$\begin{eqnarray}T=B_{n}\unicode[STIX]{x1D6FF}^{-1}c_{1}(n,D)p^{(n+1)D}(\log A_{1})\cdots (\log A_{n-1})\end{eqnarray}$$
and
$$\begin{eqnarray}\displaystyle & \displaystyle c_{0}(n,D)=(2D)^{2n+1}\log (2D)\log ^{3}(3D), & \displaystyle \nonumber\\ \displaystyle & \displaystyle c_{1}(n,D)=2\text{e}^{(n+1)(6n+5)}D^{3n}\log (2D). & \displaystyle \nonumber\end{eqnarray}$$
Proof of Theorem 1.2.
We establish a slightly more general result.
We consider a sequence of integers
$(v_{n})_{n\geqslant 0}$
with the property that there are
$\unicode[STIX]{x1D703}$
in
$(0,1)$
and
$C>0$
such that
$$\begin{eqnarray}|v_{n}-f(n)\unicode[STIX]{x1D6FC}^{n}|\leqslant C|\unicode[STIX]{x1D6FC}|^{\unicode[STIX]{x1D703}n},\quad n\geqslant 0,\end{eqnarray}$$
where
$f(X)$
is a non-zero polynomial whose coefficients are algebraic numbers and
$\unicode[STIX]{x1D6FC}$
is an algebraic number with
$|\unicode[STIX]{x1D6FC}|>1$
. Clearly, a recurrence sequence having a dominant root
$\unicode[STIX]{x1D6FC}$
has the above property. We prove a similar statement as Theorem 1.2 for the sequence
$(v_{n})_{n\geqslant 0}$
.
The constants
$c_{1},c_{2},\ldots$
below are positive, effectively computable and depend at most on
$(v_{n})_{n\geqslant 0}$
. The constants
$C_{1},C_{2},\ldots$
below are positive, effectively computable and absolute.
Let
$q_{1},q_{2},\ldots ,q_{s}$
be distinct prime numbers written in increasing order. Let
$n$
be a positive integer such that
$f(n)v_{n}$
is non-zero and
$v_{n}\not =f(n)\unicode[STIX]{x1D6FC}^{n}$
. There exist non-negative integers
$r_{1},\ldots ,r_{s}$
and a non-zero integer
$M$
coprime with
$q_{1}\cdots q_{s}$
such that
$$\begin{eqnarray}v_{n}=q_{1}^{r_{1}}\cdots q_{s}^{r_{s}}M.\end{eqnarray}$$
Observe that there exist positive real numbers
$c_{1}$
and
$c_{2}$
such that
$$\begin{eqnarray}r_{j}\log q_{j}\leqslant c_{1}n,\quad j=1,\ldots ,s,\end{eqnarray}$$
and
$$\begin{eqnarray}\unicode[STIX]{x1D6EC}:=|q_{1}^{r_{1}}\cdots q_{s}^{r_{s}}(Mf(n)^{-1})\unicode[STIX]{x1D6FC}^{-n}-1|\leqslant c_{2}|f(n)|^{-1}|\unicode[STIX]{x1D6FC}|^{(\unicode[STIX]{x1D703}-1)n}.\end{eqnarray}$$
Since
$\unicode[STIX]{x1D703}<1$
, we get by (3.1) that
$$\begin{eqnarray}\log |\unicode[STIX]{x1D6EC}|\leqslant -c_{3}n.\end{eqnarray}$$
Setting
$$\begin{eqnarray}Q:=(\log q_{1})\cdots (\log q_{s})\quad \text{and}\quad \log A:=\max \{\text{h}(Mf(n)^{-1}),2\},\end{eqnarray}$$
Theorem 3.1 and (3.2) imply that
$$\begin{eqnarray}\log |\unicode[STIX]{x1D6EC}|\geqslant -c_{4}C_{1}^{s}Q(\log A)\log \frac{n}{\log A}.\end{eqnarray}$$
Comparing both estimates, we obtain that
$$\begin{eqnarray}n\leqslant c_{5}C_{2}^{s}Q(\log Q)(\log A).\end{eqnarray}$$
Observe that
$$\begin{eqnarray}\log A\leqslant \log |M|+c_{6}\log n.\end{eqnarray}$$
We distinguish two cases.
If
$|M|\geqslant n^{c_{6}}$
, then
$A\leqslant M^{2}$
, and, by (3.3),
$$\begin{eqnarray}n\leqslant c_{7}C_{2}^{s}Q(\log Q)(\log |M|).\end{eqnarray}$$
We derive that
$$\begin{eqnarray}\frac{|v_{n}|}{[v_{n}]_{S}}=|M|\geqslant 2^{c_{8}n(C_{2}^{s}Q(\log Q))^{-1}}\geqslant |v_{n}|^{c_{9}(C_{2}^{s}Q(\log Q))^{-1}},\end{eqnarray}$$
since
$|v_{m}|\leqslant |\unicode[STIX]{x1D6FC}_{1}\!|^{2m}$
for sufficiently large
$m$
.
If
$|M|<n^{c_{6}}$
, then
$\log A\leqslant 2c_{6}\log n$
and, by (3.3),
$$\begin{eqnarray}n\leqslant c_{10}C_{2}^{s}Q(\log Q)(\log n),\end{eqnarray}$$
thus,
$$\begin{eqnarray}n\leqslant c_{11}C_{3}^{s}Q(\log Q)^{2}.\end{eqnarray}$$
This completes the proof of Theorem 1.2. ◻
Remark.
Let
$\unicode[STIX]{x1D700}$
be a positive real number. In the particular case where
$M=\pm 1$
and
$q_{1},\ldots ,q_{s}$
are the first
$s$
prime numbers
$p_{1},\ldots ,p_{s}$
, we get from (3.4) and the prime number theorem that
$$\begin{eqnarray}\log n\leqslant c_{12}+sC_{4}+(1+\unicode[STIX]{x1D700})\mathop{\sum }_{k=1}^{s}\log \log p_{k}\leqslant (1+2\unicode[STIX]{x1D700})p_{s}\frac{\log \log p_{s}}{\log p_{s}},\end{eqnarray}$$
if
$n$
is sufficiently large in terms of
$\unicode[STIX]{x1D700}$
. This gives
$$\begin{eqnarray}P[v_{n}]\geqslant (1-3\unicode[STIX]{x1D700})\log n\frac{\log \log n}{\log \log \log n},\end{eqnarray}$$
if
$n$
is sufficiently large in terms of
$\unicode[STIX]{x1D700}$
, and we recover Stewart’s result (1.3).
Proof of Theorem 1.3.
The constants
$c_{1},c_{2},\ldots$
below are positive, effectively computable and depend at most on
$(u_{n})_{n\geqslant 0}$
.
Let
$q_{1},q_{2},\ldots ,q_{s}$
be distinct prime numbers written in increasing order. Let
$n\geqslant 2$
be an integer. There exist non-negative integers
$r_{1},\ldots ,r_{s}$
and a non-zero integer
$M$
coprime with
$q_{1}\cdots q_{s}$
such that
$$\begin{eqnarray}u_{n}=q_{1}^{r_{1}}\cdots q_{s}^{r_{s}}M.\end{eqnarray}$$
It follows from [Reference Stewart12, inequality (20)] that for
$i=1,\ldots ,s$
we have
$$\begin{eqnarray}r_{i}\leqslant c_{1}\frac{q_{i}^{2}}{\log q_{i}}(\log n)^{2}.\end{eqnarray}$$
By [Reference Stewart12, Lemma 6], we get
$$\begin{eqnarray}\log |u_{n}|>c_{2}n.\end{eqnarray}$$
Consequently, setting
$$\begin{eqnarray}Q:=\mathop{\sum }_{i=1}^{s}q_{i}^{2},\end{eqnarray}$$
we obtain
$$\begin{eqnarray}c_{2}n<\log |M|+c_{1}Q(\log n)^{2}.\end{eqnarray}$$
We distinguish two cases.
If
$\log |M|>c_{1}Q(\log n)^{2}$
, then
$c_{2}n<2\log |M|,$
thus
$$\begin{eqnarray}|M|>|u_{n}|^{c_{3}}.\end{eqnarray}$$
If
$\log |M|\leqslant c_{1}Q(\log n)^{2}$
, then
$$\begin{eqnarray}n<c_{4}Q(\log n)^{2},\end{eqnarray}$$
and
$n$
is bounded in terms of
$a,b,\unicode[STIX]{x1D6FC},\unicode[STIX]{x1D6FD}$
, and
$S$
. This completes the proof of the theorem.◻
Proof of Theorem 1.4.
We establish a slightly more general result. Let
$p$
be a prime number,
$K$
a number field and
$|\cdot |_{p}$
an absolute value on
$K$
with
$|p|_{p}=p^{-1}$
. We consider a sequence of integers
$(v_{n})_{n\geqslant 0}$
with the property that there are
$\unicode[STIX]{x1D703}$
in
$(0,1)$
and
$C>0$
such that
$$\begin{eqnarray}|v_{n}-f(n)\unicode[STIX]{x1D6FC}^{n}|_{p}\leqslant Cp^{-\unicode[STIX]{x1D703}n},\quad n\geqslant 0,\end{eqnarray}$$
where
$f(X)$
is a non-zero polynomial with coefficients in
$K$
and
$\unicode[STIX]{x1D6FC}$
an element of
$K$
with
$|\unicode[STIX]{x1D6FC}|_{p}=1$
. We also assume that there exist
$\unicode[STIX]{x1D6FD}>1$
and
$n_{0}$
such that
$$\begin{eqnarray}v_{n}\not =f(n)\unicode[STIX]{x1D6FC}^{n},\qquad |v_{n}|<\unicode[STIX]{x1D6FD}^{n}\quad \text{for every integer }n>n_{0}.\end{eqnarray}$$
Clearly, every non-degenerate recurrence sequence having a
$p$
-adic dominant root satisfies both properties. We prove a statement analogous to Theorem 1.4 for the sequence
$(v_{n})_{n\geqslant 0}$
.
Let
$q_{1},q_{2},\ldots ,q_{s}$
be distinct prime numbers written in increasing order. Let
$n\geqslant 3$
be an integer such that
$f(n)v_{n}$
is non-zero and
$v_{n}\not =f(n)\unicode[STIX]{x1D6FC}^{n}$
. There exist non-negative integers
$r_{1},\ldots ,r_{s}$
and a non-zero integer
$M$
coprime with
$q_{1}\cdots q_{s}$
such that
$$\begin{eqnarray}v_{n}=q_{1}^{r_{1}}\cdots q_{s}^{r_{s}}M.\end{eqnarray}$$
The constants
$c_{1},c_{2},\ldots$
below are positive, effectively computable and depend at most on
$(v_{n})_{n\geqslant 0}$
and
$p$
. The constants
$C_{1},C_{2},\ldots$
below are positive, effectively computable and absolute.
Consider the quantity
$$\begin{eqnarray}\unicode[STIX]{x1D6EC}:=q_{1}^{r_{1}}\cdots q_{s}^{r_{s}}(Mf(n)^{-1})\unicode[STIX]{x1D6FC}^{-n}-1\end{eqnarray}$$
and observe that, by (3.5), we have
$$\begin{eqnarray}\log |\unicode[STIX]{x1D6EC}|_{p}<-c_{1}n.\end{eqnarray}$$
Set
$$\begin{eqnarray}Q:=(\log q_{1})\cdots (\log q_{s})\quad \text{and}\quad \log A:=\max \{\text{h}(Mf(n)^{-1}),2\}.\end{eqnarray}$$
It follows from Theorem 3.2 applied with
$$\begin{eqnarray}B:=\max \{r_{1},\ldots ,r_{s},n\}\quad \text{and}\quad \unicode[STIX]{x1D6FF}=\frac{Q(\log A)}{B}\end{eqnarray}$$
that
$$\begin{eqnarray}B<2Q\log A\quad \text{if }\unicode[STIX]{x1D6FF}>1/2,\end{eqnarray}$$
and, otherwise,
$$\begin{eqnarray}\log |\unicode[STIX]{x1D6EC}|_{p}>-c_{1}C_{1}^{s}Q(\log A)\max \biggl\{\log \biggl(\frac{B}{\log A}\biggr),1\biggr\}.\end{eqnarray}$$
If (3.7) holds, then we have
$$\begin{eqnarray}n\leqslant B<2Q\log A.\end{eqnarray}$$
If (3.8) holds, then, using
$$\begin{eqnarray}B\leqslant c_{3}n,\end{eqnarray}$$
which follows from (3.6), we obtain an upper bound similar to (3.3), namely
$$\begin{eqnarray}n\leqslant c_{4}C_{2}^{s}Q(\log Q)(\log A).\end{eqnarray}$$
In view of (3.9) and (3.10), we conclude as in the proof of Theorem 1.2. The last statement of the theorem corresponds to the remark following the proof of Theorem 1.2. ◻
