2 Notation and main results

Let $a_1,\ldots , a_d \in {\mathbb {Z}}$ with $a_d\neq 0$ and $U_0,\ldots ,U_{d-1}$ be integers not all zero, and let $(U_{n})_{n \geq 0}$ be the linear recurrence sequence of order d defined by

(2.1) $$ \begin{align} U_{n} = a_1U_{n-1} + \cdots +a_dU_{n-d}. \end{align} $$

Let $\alpha _1,\ldots ,\alpha _q$ be the distinct roots of the corresponding characteristic polynomial

$$ \begin{align*} f(x):= x^d - a_1x^{d-1}-\cdots-a_d. \end{align*} $$

Then for $n\geq 0$ ,

(2.2) $$ \begin{align} U_n=f_1(n)\alpha_1^n +\cdots + f_q(n)\alpha_{q}^n, \end{align} $$

where $f_i(n)\ (i=1, \ldots , q)$ are nonzero polynomials with degree less than the multiplicity of $\alpha _i$ ; the coefficients of $f_i(n)$ are elements of the field ${\mathbb Q}( \alpha _1, \ldots , \alpha _q)$ (see [Reference Shorey and Tijdeman23, Theorem C.1]).

The sequence $(U_n)_{n \geq 0}$ is degenerate if there are integers $i, j$ with $1\leq i< j\leq q$ such that $\alpha _i/\alpha _j$ is a root of unity; otherwise it is nondegenerate. The sequence $(U_n)_{n \geq 0}$ is called simple if $q=d$ . In this case, (2.2) becomes

$$ \begin{align*} U_n=f_1\alpha_1^n +\cdots + f_d\alpha_{d}^n, \end{align*} $$

where $f_i\ (i=1, \ldots , d)$ are constants. There is a natural generalisation of linear recurrence sequences to multi-recurrences. That is,

(2.3) $$ \begin{align} F(n_1,\ldots,n_s)=\sum_{i=1}^{r}P_{i}(n_1,\ldots,n_s)\alpha_{i1}^{n_1}\cdots\alpha_{is}^{n_s}, \end{align} $$

where s and r are positive integers, $P_1,\ldots , P_r$ are polynomials in s variables defined over K and $n_1,\ldots ,n_s$ are nonnegative integers. Such polynomial-exponential functions $F:\mathbb {N}_{0}^{s}\rightarrow K$ are called multi-recurrences, where $\mathbb {N}_{0}$ is the set of nonnegative integers. We say that F is defined over a field K if the coefficients and bases $\alpha _{i1},\ldots , \alpha _{is}$ for $i=1,\ldots ,r$ are in K. If F is defined over K, then it takes values in K.

Consider the number field $\mathbb {Q}(\alpha _{11},\ldots ,\alpha _{1s},\ldots ,\alpha _{r1},\ldots ,\alpha _{rs})$ . We shall use the abbreviation $\boldsymbol {\alpha }_i^{\boldsymbol {n}} = \alpha _{i1}^{n_1}\cdots \alpha _{is}^{n_s}$ and hence

$$ \begin{align*}P_{i}(\boldsymbol{n})\boldsymbol{\alpha}_{i}^{\boldsymbol{n}}= P_{i}(n_1,\ldots,n_s)\alpha_{i1}^{n_1}\ldots\alpha_{is}^{n_s}.\end{align*} $$

We say that F is degenerate if there are integers $i, j$ with $1\leq i< j\leq r$ such that $\boldsymbol {\alpha }_{i}^{\boldsymbol {n}}=\boldsymbol {\alpha }_{j}^{\boldsymbol {n}}$ for some $\boldsymbol {n}\in \mathbb {N}_0^{s}$ ; otherwise it is called nondegenerate. We say that $\boldsymbol {\alpha }_{i}$ is irrational if $\alpha _{ij}$ is irrational for all $j=1,\ldots , s$ . Now we give our first result about the Diophantine equation

(2.4) $$ \begin{align} U_{n_1} + U_{n_2} \in X_1 \cup \cdots\cup X_k, \quad (n_1, n_2)\in {\mathbb{N}}_{0}^2. \end{align} $$

Let $p_1,\ldots ,p_l$ be distinct primes and let $S=\{p_1,\ldots ,p_l\}$ . Then $w\in {\mathbb Q}$ is an S-unit if w can be written as

(2.5) $$ \begin{align} w=\pm p_1^{b_1}\cdots p_l^{b_l} \quad (b_1, \ldots, b_l\in {\mathbb{Z}}). \end{align} $$

We write $U_S$ for the set of S-units. In the next result, we study the sums of S-units in the solution sets of norm form equations. In particular, we study the Diophantine equation

(2.6) $$ \begin{align} w_1+\cdots+w_t \in X_1 \cup \cdots \cup X_k \end{align} $$

in $(w_1,\ldots ,w_t)\in U_{S}^{t}$ , for some $t\in \mathbb {Z}_{> 0}$ .

Theorem 2.2. Let $U_S$ be the set of S-units as defined above and let $t\geq 1$ . If

(2.7) $$ \begin{align} w_{i_1}+\cdots+w_{i_j}\neq 0 \end{align} $$

for $0<j\leq t$ and $1\leq i_1<\cdots <i_j\leq t$ , then (2.6) holds for only finitely many tuples $(w_1,\ldots ,w_t)\in U_{S}^{t}$ . In fact, the number of such tuples is bounded by $C_2$ , which is an effectively computable constant that depends only on $m, t$ and l.

In the following, we give some examples where there are infinitely many pairs of indices $(n_1, n_2)$ for which (2.4) holds and one of the conditions of Theorem 2.1 is not satisfied.

Example 2.3. Let $\beta =\sqrt {5}$ and $K=\mathbb {Q}(\beta )$ . Then $1,\sqrt {5}$ are linearly independent over $\mathbb {Q}$ . Consider the norm form equation

$$ \begin{align*} N_{K/{\mathbb Q}}(x_1+x_2\sqrt{5})=4. \end{align*} $$

One can easily obtain the solution for $x_1$ , which is $3,7,18,\ldots .$ Let ${U_0=0, U_1=3}$ , and $U_{n+2}=U_{n+1}-U_{n}$ . Then the terms of the sequence $(U_n)_{n\geq 0}$ are given by $0, 3, 3, 0, -3, -3, 0, 3, \ldots .$ This shows that $U_{n_1}+U_{n_2}=3\in X_1$ has infinitely many solutions $(0, n_2)$ or $(n_1, 0)$ . In this case, the roots of the characteristic polynomial of $(U_n)_{n\geq 0}$ are $\tfrac 12(1+\sqrt {3}i)$ and $\tfrac 12(1-\sqrt {3}i)$ whose ratio is a cube root of unity. So, nondegeneracy is a necessary condition for the theorem.

Example 2.4. Let $K=\mathbb {Q}(\sqrt {2})$ and consider

(2.8) $$ \begin{align} N_{K/{\mathbb Q}}(x_1+x_2\sqrt{2})=-1. \end{align} $$

Then $1, \sqrt {2}$ is an integral basis and $1+\sqrt {2}$ is a fundamental unit of K. Any solution of (2.8) can be written as

(2.9) $$ \begin{align} x_1+x_2\sqrt{2}=(1+\sqrt{2})^m \quad\text{for } m\in {\mathbb Z}_{>0}. \end{align} $$

Let $\tau _1$ and $\tau _2$ be isomorphisms of K. Taking conjugates in (2.9), gives

$$ \begin{align*}\begin{pmatrix} 1&\sqrt{2}\\ 1& -\sqrt{2} \end{pmatrix}\begin{pmatrix} x_1\\ x_2 \end{pmatrix}=\begin{pmatrix} (1+\sqrt{2})^m\\ (1-\sqrt{2})^m \end{pmatrix}.\end{align*} $$

From this,

$$ \begin{align*}X_2=\bigg\{\frac{(1+\sqrt{2})^{m}-(1-\sqrt{2})^{m}}{2\sqrt{2}}: m\in {\mathbb{Z}}_{>0}\bigg\}.\end{align*} $$

Now define a sequence $(U_n)_{n\geq 0}$ by $U_0=0, U_1=1$ and $U_{n+1}=6U_{n}-U_{n-1}\ (n\geq 1)$ . The Binet form is

$$ \begin{align*}U_n=\frac{(3+2\sqrt{2})^n-(3-2\sqrt{2})^n}{4\sqrt{2}}.\end{align*} $$

We see that $U_n+U_{n}=2U_n\in X_2$ for every $n\geq 0$ . Note that the roots $3+2\sqrt {2}$ and $3-2\sqrt {2}$ are multiplicatively dependent.

Example 2.5. Let $K=\mathbb {Q}(\sqrt {13})$ and consider the norm form equation

$$ \begin{align*} N_{K/{\mathbb Q}}(x_1+\sqrt{13}x_2)=4. \end{align*} $$

The solution sets are

$$ \begin{align*}X_1=\{11,119,1298,14159,154451,1684802,\ldots \}\end{align*} $$

and

$$ \begin{align*}X_2=\{3,33,360,3927,42837,467280,\ldots\}.\end{align*} $$

It is well known from [Reference Wright24, Corollary 1] that the third, sixth, ninth, $\ldots $ terms in the sets $X_1$ and $X_2$ are even positive integers. Now consider the sequence $(U_n)_{n\geq 0}$ defined by $U_0=0,U_1=2$ and $U_{n+2}=2U_{n+1}-U_n (n\geq 0)$ . Then $(U_n)_{n\geq 0}$ is exactly the sequence of even numbers, so that $U_{n_1}+U_{n_2}\in X_1\cup X_2$ for infinitely many $(n_1,n_2)$ . Here, observe that $f(x)=x^2-2x+1$ is the characteristic polynomial of $(U_n)_{n\geq 0}$ whose roots are roots of unity (which implies multiplicatively dependent).

Example 2.6. Suppose $U_0=0,U_1=1$ and $U_{n+2}=10U_{n+1}-U_n$ . The characteristic polynomial of $(U_n)_{n\geq 0}$ is $x^2-10x+1$ with constant term is $a_2=-1$ . Let ${K=\mathbb {Q}(\sqrt {2}+\sqrt {3})}$ and $\eta =\sqrt {2}+\sqrt {3}$ be a unit in K. Let $W=\{w_1,w_2,w_3,w_4\}$ be the basis for the module $\beta {\mathbb {Z}}[\sqrt {2}+\sqrt {3}]$ constructed in [Reference Bellah1, Theorem 1.5], for some fixed $\beta \in K$ , and $\alpha (m)=\beta \eta ^m$ . Write $x_1(m)w_1+\cdots +x_4(m)w_4=\beta \eta ^m$ , where $x_i(m)$ is the solution set of the norm form equation

$$ \begin{align*} N(x_1(m)w_1+\cdots+x_4(m)w_4)=N(\beta). \end{align*} $$

Then for any integer $m\geq 2$ , we have $X_1(m)=U_{n+1}+U_n$ if $m=2n+1$ (see [Reference Bellah1, Corollary 4.2]). Hence, (2.4) has infinitely many solutions.

3 Auxiliary results

In this section, we give some background for the proofs of our results. Let L be an algebraic number field. Consider the equation

(3.1) $$ \begin{align} \sum_{l=1}^{r}P_l(\boldsymbol{x})\mathfrak{g}_{{l}}^{\boldsymbol{x}} = \boldsymbol{0} \end{align} $$

in variables ${\boldsymbol x} = (x_1, \ldots , x_s) \in {\mathbb {Z}}^s,$ where the $P_l$ are not identically zero polynomials in s variables with coefficients in L, and

$$ \begin{align*}\mathfrak{g}_l^{\boldsymbol{x}} =g^{x_1}_{l_1} \cdots g^{x_s}_{l_s}\end{align*} $$

with given nonzero $g_{l_1}, \ldots , g_{l_s} \in L\ (l = 1, \ldots , r)$ . Let $\pi $ be a partition of the set ${\Lambda :=\{1, \ldots , r\}}$ . The sets $\lambda \subset \{1, \ldots , r\}$ belonging to $\pi $ will be considered to be elements of $\pi $ ; we write $\lambda \in \pi $ . Given a partition $\pi $ , the set of equations

(3.2) $$ \begin{align} \sum_{l\in \lambda}P_l(\boldsymbol{x})\mathfrak{g}_{{l}}^{\boldsymbol{x}} = 0, \quad \lambda \in \pi, \end{align} $$

yields a refinement of (3.1). More generally, when $\pi '$ is a refinement of $\pi $ , the system of equations corresponding to the partition $\pi '$ implies the system of equations corresponding to the partition $\pi $ . Let $S(\pi )$ be the set of solutions of (3.2), which are not solutions of (3.2) with any proper refinement $\pi '$ of $\pi $ .

Set $i \overset {\pi }{\sim } j$ if i and j lie in the same subset $\lambda $ belonging to $\pi $ . Let $G(\pi )$ be the subgroup of ${\mathbb {Z}}^s$ consisting of $\boldsymbol {z}$ with

$$ \begin{align*}\mathfrak{g}_i^{\boldsymbol{z}} = \mathfrak{g}_j^{\boldsymbol{z}}\end{align*} $$

for any $i, j$ with $i \overset {\pi }{\sim } j$ .

The following result plays a central role in proving our main theorems.

Proposition 3.1 [Reference Schlickewei and Schmidt18, Theorem 1].

Using the above notation, if $G(\pi ) = \{\mathbf 0\}$ then

$$ \begin{align*} |S(\pi)|<2^{35A^3}\ell^{6A^2} \end{align*} $$

with $\ell = \deg (L)$ and

$$ \begin{align*} A = \max \bigg(s, \sum_{h\in \Lambda}\binom{s+\delta_h}{s}\bigg), \end{align*} $$

where $\delta _h$ is the total degree of the polynomial $P_h.$

Following the arguments from [Reference Bérczes, Hajdu and Pethő2, Reference Fuchs and Heintze9], we prove the following proposition. The main idea is as follows. If we have an identity of the form $R.X = A$ where there is a possibility of a Galois action G on R (and A) which fixes X, then we will get a complete matrix equation of the form $R^{(G)}X = A^{(G)}$ . Typically R is chosen with $R^{(G)}$ nonsingular so that one can invert it to obtain an expression for X.

Proposition 3.2. If (1.1) has a solution, then all solutions are given by

$$ \begin{align*} x_{i}=F_{i}^{(j)}(\boldsymbol{n}) \end{align*} $$

for $j=1,\ldots , J$ and $i=1,\ldots , k$ with some multi-recurrence

$$ \begin{align*}F_i^{(j)}(\boldsymbol{n})=\sum_{h=1}^{r} P_{i_h}^{(j)}(\boldsymbol{n})\boldsymbol{\alpha}_{i_h}^{{\boldsymbol{n}}},\end{align*} $$

where all the coordinates $\boldsymbol {\alpha }_{i_h}$ are irrational and algebraic over $\mathbb {Q}$ and J is some positive integer such that $J<C_3$ , where $C_3$ is an effectively computable constant depending on k and m.

Proof. There are only finitely many pairwise nonassociate algebraic integers $\mu $ in K of norm m. Let the number of such elements be J and note that J can be bounded in terms of k and m (see [Reference Győry10, Lemma 5]). Let $\mu _1,\ldots ,\mu _J$ be pairwise nonassociate algebraic integers in K of norm m. If $(x_1,\ldots ,x_{k})\in \mathbb {Z}^{k}$ is a solution of (1.1), then

(3.3) $$ \begin{align} x_{1}\beta_1+\cdots +x_{k}\beta_k= \epsilon \mu_j \end{align} $$

for some $j\in J$ and $\epsilon $ a unit in K. Let $\epsilon _1,\ldots ,\epsilon _s$ be a system of fundamental units in K. Then (3.3) yields

(3.4) $$ \begin{align} x_{1}\beta_1+\cdots +x_{k}\beta_k= \gamma\epsilon_{1}^{a_1}\cdots \epsilon_{s}^{a_s}\mu_j, \end{align} $$

where $\gamma $ is a root of unity in K and $a_1,\ldots ,a_s\in {\mathbb {Z}}$ . Since the number of roots of unity in K is bounded in terms of k, we may assume that this $\gamma $ is fixed. Let $\sigma _1,\ldots ,\sigma _{k}$ be the elements of the Galois group $G:=\text {Gal}(K/\mathbb {Q})$ . Choose the order of the isomorphisms $\sigma _1,\ldots ,\sigma _{k}$ in such a way that the matrix

$$ \begin{align*}R^{(G)}:=\begin{pmatrix} \sigma_1(\beta_1)&\cdots&\sigma_1(\beta_k)\\ \vdots&\ddots&\vdots\\ \sigma_k(\beta_1)&\cdots&\sigma_k(\beta_k) \end{pmatrix}\end{align*} $$

is invertible. Now, taking the conjugates of (3.4),

(3.5) $$ \begin{align} \begin{pmatrix} \sigma_1(\beta_1)&\cdots&\sigma_1(\beta_k)\\ \vdots&\ddots&\vdots\\ \sigma_k(\beta_1)&\cdots&\sigma_k(\beta_k) \end{pmatrix} \begin{pmatrix} x_1\\ \vdots\\ x_k \end{pmatrix}= \begin{pmatrix} \sigma_1(\gamma\mu_j)u_{11}^{a_1}\cdots u_{1s}^{a_s}\\ \vdots\\ \sigma_k(\gamma\mu_j)u_{k1}^{a_1}\cdots u_{ks}^{a_s} \end{pmatrix}, \end{align} $$

where $u_{ih}=\sigma _i(\epsilon _h)$ for $i=1,\ldots , k$ and $h=1,\ldots , s$ . The determinant of the matrix $R^{(G)}$ in (3.5) is nonzero, so we write

(3.6) $$ \begin{align} x_i=c_{1i}^{(j)}u_{11}^{a_1}\cdots u_{1s}^{a_s}+\cdots+c_{ki}^{(j)}u_{k1}^{a_1}\cdots u_{ks}^{a_s}, \end{align} $$

where $c_{ih}^{(j)}$ belong to the normal closure of K for $i=1,\ldots ,k$ and $u_{ih}$ for $1\leq i\leq k$ , $1\leq h\leq s$ are irrational. If any of the $ u_{ij}$ is rational, then $\epsilon _j$ must also be rational, since we have defined $ u_{ih} = \sigma _i(\epsilon _h)$ where $\sigma _i\in G$ , for $i=1,\ldots , k$ . As $\epsilon _j $ is a fundamental unit, it satisfies

(3.7) $$ \begin{align} N_{K/{\mathbb Q}}(\epsilon_j) = \pm 1. \end{align} $$

For any $r \in {\mathbb Q}$ , we have $ N_{K/{\mathbb Q}}(r) = r^k$ , where $k = [K:{\mathbb Q}]$ . Hence, from (3.7), it follows that $\epsilon _j = \pm 1$ , since the only rational numbers whose kth powers are $\pm 1$ are $\pm 1$ themselves. However, $ \epsilon _j$ cannot be $\pm 1$ , because it is a fundamental unit and therefore must be multiplicatively independent of the other fundamental units $\epsilon _i$ , $ ( i \neq j )$ . Thus, (3.6) represents the required multi-recurrence.

Suppose that $\boldsymbol {\alpha }_{i}^{\boldsymbol {n}} = \boldsymbol {\alpha }_{j}^{\boldsymbol {n}}$ for some distinct indices $i, j$ . Then

(3.8) $$ \begin{align} \alpha_{i1}^{n_1}\cdots\alpha_{is}^{n_s}=\alpha_{j1}^{n_1}\cdots\alpha_{js}^{n_s} \end{align} $$

for infinitely many vectors $(n_1, \ldots , n_s)$ and we can construct a multi-recurrence

$$ \begin{align*} F'(n_1,\ldots,n_s)=\sum (P_i\alpha_{i1}^{n_1}\cdots\alpha_{is}^{n_s}-P_i\alpha_{j1}^{n_1}\cdots\alpha_{js}^{n_s}), \end{align*} $$

which is zero for the vectors in our sequence such that

$$ \begin{align*} F_0(n_1,\ldots, n_s) :=F(n_1,\ldots,n_s)- F'(n_1,\ldots,n_s) = \sum_{j=1}^{\tilde{r}}\tilde{P_{j}}\alpha_{j1}^{n_1}\cdots\alpha_{js}^{n_s} \end{align*} $$

does not contain two summands satisfying a relation of the shape (3.8). Thus, the multi-recurrence $F_0(n_1,\ldots , n_s)$ is nondegenerate.

Both effective and ineffective results related to sums of S-units in a linear recurrence sequence have been studied in [Reference Bérczes, Hajdu, Pink and Rout3]. We need a similar type of result for multi-recurrences. Recall that $U_S$ is the set of S-units.

Proposition 3.3. Suppose $\mathcal {U}_t:=\{w_1+\cdots +w_t \,: \, w_1,\ldots ,w_t \in U_S\}$ and $F:{\mathbb {N}}_{0}^{s} \rightarrow K$ is a nondegenerate multi-recurrence defined as in (2.3). Assume that the $\alpha _{ij}$ are algebraic and $\boldsymbol {\alpha }_{i}$ is irrational for some $i=1,\ldots , r$ . Then for any fixed $t\geq 1$ ,

(3.9) $$ \begin{align} F(\textbf{n})\in \mathcal{U}_t \end{align} $$

has at most finitely many solutions $\boldsymbol {n}\in {\mathbb {N}}_{0}^{s}$ , and their number can be bounded above by an effectively computable constant $C_4$ depending on r and t.

Proof. From (3.9),

$$ \begin{align*}F(\boldsymbol{n})=w_1+\cdots+w_t\quad \text{for some } w_1,\ldots,w_t\in U_S.\end{align*} $$

Then using (2.3) and (2.5),

(3.10) $$ \begin{align} \sum_{i=1}^{r}P_{i}(n_1,\ldots, n_s)\alpha_{i1}^{n_1}{\cdots }\alpha_{is}^{n_s}= p_1^{b_{11}}\cdots p_l^{b_{1l}}+\cdots+ p_1^{b_{t1}}\cdots p_l^{b_{tl}}, \end{align} $$

where $b_{uv}\ (1\leq u\leq t, 1 \leq v \leq l)$ are nonnegative integers. Let $\pi $ be any partition of the set $\{1,\ldots , r, r+1, \ldots , r+t\}$ . Consider first those solutions of (3.10) that do not satisfy any refinement of $\pi $ , and for which there exists $i, j$ with $1\leq i<j\leq r$ belonging to the same $\lambda \in \pi $ . Since F is nondegenerate, we conclude that $G(\pi )=\{\textbf {0}\}$ . The boundedness of the number of such solutions is given by Proposition 3.1.

Now consider those solutions of (3.10) that do not satisfy any refinement of $\pi $ , and for which the indices i with $1\leq i\leq r$ belong to different classes of $\pi $ . Consider an $i\ (1\leq i\leq r)$ such that $\boldsymbol {\alpha }_i$ is irrational. Take a class $\lambda \in \pi $ containing i. There exists an isomorphism $\sigma $ of $\mathbb {Q}(\alpha _{11},\ldots ,\alpha _{1s},\ldots ,\alpha _{r1},\ldots \alpha _{rs})$ into $\mathbb {C}$ such that $\sigma (\boldsymbol {\alpha }_{i})=\boldsymbol {\alpha }_{j}$ with $1\leq i\neq j\leq r$ . Then,

$$ \begin{align*}P_i(\boldsymbol{n})\boldsymbol{\alpha}_{i}^{\boldsymbol{n}}=w_{r_1}+\cdots+w_{r_h}\end{align*} $$

for some $\{r_1,\ldots , r_h\}\subset \{1,\ldots ,t\}$ and so

$$ \begin{align*}\sigma(P_i(\boldsymbol{n})\boldsymbol{\alpha}_{i}^{\boldsymbol{n}})=w_{r_1}+\cdots+w_{r_h},\end{align*} $$

which implies

$$ \begin{align*}\sigma(P_i(\boldsymbol{n}))\boldsymbol{\alpha}_{j}^{\boldsymbol{n}}=P_i(\boldsymbol{n})\boldsymbol{\alpha}_{i}^{\boldsymbol{n}}.\end{align*} $$

By Proposition 3.1, this equation has only finitely many solutions and their number can be effectively bounded. Since the number of partitions $\pi $ of $\{1,\ldots , r+t\}$ is bounded in terms of r and t, this completes the proof.

Remark 3.4. In (2.3), take $s=2,r=2$ , $P_1=P_2=1, S=\{2,3,5\}$ and $\boldsymbol {\alpha _1}=(5,6)$ , $\boldsymbol {\alpha _2}=(10,3)$ . Then (2.6) becomes

(3.11) $$ \begin{align} 2^{b_{11}}3^{b_{12}}5^{b_{13}}+ 2^{b_{21}}3^{b_{22}}5^{b_{23}}= 5^{n_1}\cdot 6^{n_2}+ 10^{n_1}\cdot 3^{n_2}. \end{align} $$

Observe that (3.11) has infinitely many solutions in $(n_1, n_2)$ with $n_1=b_{13}=b_{21}=b_{23}$ and $n_2=b_{11}=b_{12}=b_{22}$ . Observe that $\boldsymbol {\alpha _1}$ and $\boldsymbol {\alpha _2}$ are rational.

Let $\mathcal {S} =\{\mathcal {P}_1,\ldots , \mathcal {P}_l\}$ be a finite set of prime ideals in the number field L. Denote by $U_{\mathcal {S}}$ the set of $\mathcal {S}$ -units in L, that is, the set of $w\in L$ for which the principal fractional ideal $(w)$ can be represented as

$$ \begin{align*} (w) = \mathcal{P}_{1}^{b_1}\cdots \mathcal{P}_{l}^{b_l}\quad (b_1, \ldots, b_l\in {\mathbb{Z}}). \end{align*} $$

Proposition 3.5 [Reference Evertse and Győry8, Theorem 6.1.3 and Corollary 4.1.5].

Let $b_1,\ldots ,b_t$ be nonzero elements of the number field L. Then the equation

(3.12) $$ \begin{align} b_1y_1+\cdots+b_ty_t=1 \end{align} $$

has at most $C_5$ solutions $(y_1,\ldots ,y_t)\in U_{\mathcal {S}}^{t}$ for which the left-hand side of (3.12) has no vanishing subsums. Here $C_5$ is an effectively computable constant depending only on $t, l$ and $\deg L$ .

Now we are ready to prove our main results.

4 Proof of Theorem 2.1

Let $(U_n)_{n\geq 0}$ be a linear recurrence sequence of order d as given in (2.2), satisfying the assumptions of the theorem. Let $(x_1,\ldots ,x_k)\in \mathbb {Z}^{k}$ be a solution of (1.1). We need to bound the indices $(n_1,n_2)$ such that $U_{n_{1}}+U_{n_{2}}=x_i$ for some i with $1\leq i\leq k$ . Using Proposition 3.2 and (2.2), the relation (2.4) becomes

(4.1) $$ \begin{align} c_{1i}\boldsymbol{u}_{1}^{\boldsymbol{a}}+\cdots+ c_{ki}\boldsymbol{u}_{k}^{\boldsymbol{a}}=f_1(n_1)\alpha_1^{n_1} +\cdots + f_q(n_1)\alpha_{q}^{n_1}+f_1(n_2)\alpha_1^{n_2} +\cdots + f_q(n_2)\alpha_{q}^{n_2}, \end{align} $$

where $\boldsymbol {a}=({a}_1,\ldots ,a_s)$ and $\boldsymbol {u}_{i}=(u_{i1},\ldots ,u_{is})$ for $i=1,\ldots ,k$ . Note that by our convention on the minimality of d in (2.1), none of $f_i(n_1),f_i(n_2)$ and $\alpha _i$ is zero. We may assume that i is fixed and define $(r+2)$ -tuples $\mathfrak {g}_j$ by

$$ \begin{align*} \mathfrak{g}_j= \begin{cases} (u_{j1},\ldots,u_{js},1,1) &\text{for } 1\leq j\leq k \\ (1,\ldots,1,\alpha_{j-k},1) & \text{for } k+1\leq j\leq k+q \\ (1,\ldots,1,1,\alpha_{j-k-q}) & \text{for } k+q+1\leq j\leq k+2q\\ \end{cases} \end{align*} $$

and

$$ \begin{align*}P_j(\boldsymbol{y})= \begin{cases} c_{ji} & \text{for } 1\leq j\leq k \\ -f_j(y_{r+1}) & \text{for } k+1\leq j\leq k+q \\ -f_j(y_{r+2}) & \text{for } k+q+1\leq j\leq k+2q,\\ \end{cases} \end{align*} $$

where $P_j\ (1\leq j \leq k+2q)$ is a polynomial in $r+2$ variables $\boldsymbol {y}=(y_1,\ldots ,y_{r+2})$ . Then (4.1) can be rewritten as

(4.2) $$ \begin{align} \sum_{j=1}^{k+2q}P_j(\boldsymbol{y})\mathfrak{g}_j^{\boldsymbol{y}}=0. \end{align} $$

Suppose $J=\{1,\ldots ,k+2q\}$ and $\pi $ is a partition of J. Consider the refinement of (4.2),

(4.3) $$ \begin{align} \sum_{j\in \Delta}P_j(\boldsymbol{y})\mathfrak{g}_j^{\boldsymbol{y}}=0\quad (\Delta \in \pi). \end{align} $$

We are interested in the solutions of (4.3), which are not solutions of any proper refinement of $\pi $ . That is, we consider the solutions of (4.3) in $S(\pi )$ .

Assume first that there is a subset $\Delta $ of $\pi $ such that $\Delta \subseteq \{k+1,\ldots ,k+q\}$ . We will apply Proposition 3.1 with $s=1$ . If $\Delta $ is a singleton set, that is, $\Delta = \{i\}$ , then $\pi $ yields $f_i(n_1)\alpha _i^{n_1} =0$ , which is not possible as $\alpha _i \neq 0\ (1 \leq i \leq q)$ . So, $|\Delta | =1$ is not possible. Thus, $|\Delta | \geq 2$ . If $i \overset {\pi }{\sim } j$ with some $i\neq j$ then $\alpha _i^{n_1} = \alpha _j^{n_1}$ . Since the recurrence sequence $(U_n)_{n\geq 0}$ is nondegenerate, we have $G(\pi ) = \{\mathbf {0}\}$ . Hence, Proposition 3.1 gives an upper bound for the number of these values of $n_1$ in terms of d.

Similarly, if we assume that there is a subset $\Delta $ of the partition $\pi $ such that ${\Delta \subseteq \{k+q+1, \ldots ,k+2q\}}$ , then by proceeding as above we get an upper bound for the number of these values of $n_2$ in terms of d.

Now assume that $\Delta \subseteq \{k+1, \ldots , k+2q\}$ contains elements $i \in \{k+1, \ldots , k+q\}$ and $j\in \{k+q+1, \ldots , k+2q\}$ . Suppose $\Delta = \{i, j\}$ with $\alpha _i\neq \alpha _j$ . We will apply Proposition 3.1 with $s=2$ . In this case, we will get an equation of the form

$$ \begin{align*} f_{i}(n_1)\alpha_{i}^{n_1} +f_{j}(n_2)\alpha_{j}^{n_2}=0. \end{align*} $$

Since by our assumption, the $\alpha _i$ are pairwise multiplicatively independent, we get $G(\pi ) = \{\mathbf {0}\}$ . Hence, Proposition 3.1 gives an upper bound for the number of these values of $n_1$ and $n_2$ in terms of d. Next, suppose that $\alpha _i=\alpha _j$ . This gives an equation of the form

$$ \begin{align*} f_{i}(n_1)\alpha_{i}^{n_1} +f_{i}(n_2)\alpha_{i}^{n_2}=0 \end{align*} $$

and this implies that the $\alpha _i$ are roots of unity. However, by assumption, the $\alpha _i$ are multiplicatively independent, so $G(\pi ) = \{\mathbf {0}\}$ . Again using Proposition 3.1, we get a bound for $n_1$ and $n_2$ in terms of d.

Now we consider $\Delta \in \pi $ , which contains an index from $\{k+1,\ldots ,k+2q \}$ , and assume that there is a $j_1\in \Delta $ with $1\leq j_1\leq k$ such that $P_{j_{1}}$ is not identically zero. Suppose $a_d\neq \pm 1$ . We consider two cases.

Case I: $j_2,j_3\in \Delta $ such that $k+1\leq j_2\leq k+q$ and $k+q+1\leq j_3\leq k+2q$ . If $\boldsymbol {y}\in G(\pi )$ then, as $j_2\overset {\pi }{\sim }j_1$ and $j_3\overset {\pi }{\sim }j_1$ ,

$$ \begin{align*} u_{j_{1}1}^{y_1}\cdots u_{j_{1}r}^{y_r}=\alpha_{j_2}^{y_{r+1}} \quad \text{and}\quad u_{j_{1}1}^{y_1}\cdots u_{j_{1}r}^{y_r}=\alpha_{j_3}^{y_{r+2}}. \end{align*} $$

Since $\alpha _{j_2}$ and $\alpha _{j_3}$ are not units in $\tau _{j_1}(K)$ , we get $y_{r+1}=0$ and $y_{r+2}=0$ . Then, as $u_{j_{1}1}^{y_1}\cdots u_{j_{1}r}^{y_r}$ is a system of fundamental units in $\tau _{j_1}(K)$ , we obtain $y_1=\cdots =y_r=0$ . Hence, $\boldsymbol {y}=\mathbf 0$ , so $G(\pi )=\{{\mathbf 0}\}.$

Case II: $j_2\in \Delta $ with $k+1\leq j_2\leq k+q$ and no other index in $\{ k+q+1,\ldots ,k+2q\}$ belongs to $\Delta $ . We will apply Proposition 3.1 with $s=r+1$ . Let $\boldsymbol {y}=(y_1,\ldots ,y_{r+1})$ . If $\boldsymbol {y}\in G(\pi )$ then, as $j_2\overset {\pi }{\sim }j_1$ , we have $u_{j_{1}1}^{y_1}\cdots u_{j_{1}r}^{y_r}=\alpha _{j_2}^{y_{r+1}}$ . Since $\alpha _{j_2}$ is not a unit in $\tau _{j_1}(K)$ we get $y_{r+1}=0$ and, as $u_{j_{1}1}^{y_1}\cdots u_{j_{1}r}^{y_{r}}$ is a system of fundamental units in $\tau _{j_1}(K)$ , we obtain $y_1=\cdots =y_r=0$ . Hence, $\boldsymbol {y}=\mathbf 0$ , so $G(\pi )=\{{\mathbf 0}\}.$

Thus, by Proposition 3.1 our statement follows.

5 Proof of Theorem 2.2

Let $w_1,\ldots , w_t\in U_S$ satisfy (2.6) and (2.7). Assume that

$$ \begin{align*} w_1+\cdots +w_t=x_i \end{align*} $$

for some $x_i\in X_i\ (i=1,\ldots ,k)$ . By Proposition 3.2,

(5.1) $$ \begin{align} w_1+\cdots+w_t= F_{i}^{(j)}(\boldsymbol{n}) \end{align} $$

for some $j\in \{1,\ldots ,J\}$ and $\boldsymbol {n}\in \mathbb {N}_0^{s}$ , where J is bounded in terms of k and m and $F_{i}^{(j)}(\boldsymbol {n})$ is a term of a nondegenerate multi-recurrence $F_{i}^{(j)}$ . By Proposition 3.3, the number of such $\boldsymbol {n}$ satisfying (5.1) is $C_4$ . Further, by (2.7), $F_{i}^{(j)}(\boldsymbol {n})\neq 0$ . Setting $b_q=1/F_{i}^{(j)}(\boldsymbol {n})$ for $1\leq q\leq t$ , (5.1) can be written as

(5.2) $$ \begin{align} b_1w_1+\cdots+b_tw_t=1. \end{align} $$

Then from (2.7) and Proposition 3.5, we have finitely many tuples $(w_1, \ldots , w_t)\in U_{S}^t$ satisfying (5.2). The result follows because there are at most $C_5$ such equations.