# Classifying linear division sequences

Andrew Granville  Départment de Mathématiques et Statistique, Université de
Montréal, CP 6128 succ Centre-Ville, Montréal, QC H3C 3J7, Canada.
<EMAIL_ADDRESS>In memory of Richard K. Guy, 1916-2020

###### Abstract.

We classify all linear division sequences in the integers, a problem going
back to at least the 1930s. As a corollary we also classify those linear
recurrence sequences in the integers for which $(x_{m},x_{n})=\pm x_{(m,n)}$.
We also show that if two linear division sequences have a large common factor
infinitely often then they are each divisible by a common linear division
sequence on some arithmetic progression. Moreover our proofs also work for
polynomials. The key to our proofs are Ritt’s irreducibility theorem and the
subspace theorem (of Schmidt and Schlickewei), in a direction developed by
Bugeaud, Corvaja and Zannier.

Many thanks to Yann Bugeaud, Pietro Corvaja, Henri Darmon, Youness Lamzouri,
Florian Luca, Alina Ostafe, Attila Pethő, Carl Pomerance, Hugh C. Williams and
Umberto Zannier for useful email conversations, and particularly Carlo Pagano
for help applying the Čebotarev density theorem. Richard Guy was an avid
collector and popularizer of inspiring mathematical problems [18, 9, 19].
While collaborating on [16], an article memorializing the life and work of
Richard Guy, I took the opportunity to re-read several of Guy’s papers, and
found myself compelled to revisit linear division sequences, leading to these
results.
The author is partially supported by grants from NSERC (Canada).

##  1\. Introduction

###  1.1. Definitions and the development of a problem

A _linear recurrence sequence_ $(u_{n})_{n\geq 0}$ of integers (or rationals,
or algebraic integers, or polynomials,…) satisfies a recurrence

$u_{n}=c_{1}u_{n-1}+\cdots+c_{k}u_{n-k}$ (1)

where $c_{1},\dots,c_{k}$ are integers with $c_{k}\neq 0$ and
$u_{0},\dots,u_{k-1}$ are integers. The _order_ of $(u_{n})_{n\geq 0}$ is the
smallest possible $k$ in any recurrence (1) for the $u_{n}$.

A _division sequence_ $(u_{n})_{n\geq 0}$ of integers satisfies

$u_{m}\text{ divides }u_{n}\text{ whenever }m\text{ divides }n.$

We then call $(u_{n})_{n\geq 0}$ a _linear division sequence_ if it is both a
linear recurrence sequence and a division sequence.111This is sometimes called
a _linear divisibility sequence_. Examples include the Fibonacci numbers
$(F_{n})_{n\geq 0}$, the Mersenne numbers $2^{n}-1$, indeed all Lucas
sequences, as well as polynomials of the form $n^{d}$, and their products. One
can analogously define linear division sequences in the algebraic integers, in
$\mathbb{C}[t]$ and even for polynomials in many variables.

For every linear recurrence sequence (1), there is a _characteristic
polynomial_

$f(x):=x^{k}-c_{1}x^{k-1}-\cdots-
c_{k-1}x-c_{k}=\prod_{i=1}^{m}(x-\alpha_{i})^{k_{i}}$

where the $\alpha_{i}$ are distinct, non-zero (as $c_{k}\neq 0$) algebraic
integers (called _characteristic roots_) and the $k_{i}$ are positive integers
for which $k_{1}+\cdots+k_{m}=k$. One can write

$u_{n}=\sum_{i=1}^{m}g_{i}(n)\alpha_{i}^{n}\text{ for all }n\geq 0$ (2)

where the $g_{i}(t)\in\overline{\mathbb{Q}}[t]$ have degree $k_{i}-1$ (see
e.g. [11]). We call $(u_{n})_{n\geq 0}$ _simple_ if each $k_{i}=1$ and so each
$g_{i}(t)$ is a constant. If we define $(u_{n})_{n\geq 0}$ by (2) then it
satisfies the linear recurrence (1) since knowing the $\alpha_{i}$’s and the
multiplicities $k_{i}$ allow us to construct the characteristic polynomial and
so determine the $c_{i}$’s.

In 1936 Marshall Hall [23] partly classified all third-order linear division
sequences opening up the general classification question (though he did not
feel that he was in a position to make a general conjecture). He remarked that
the problem has its antecedents in the 1875 papers of Lucas (section VII of
[31]) as well as work of D.H. Lehmer [27, 28],222The latter reference included
Lehmer’s conjecture that the Mahler measure of a non-cyclotomic irreducible
polynomial cannot get arbitrarily close to $1$. Pierce [35] and Poulet. The
problem is mentioned in the book [11] as being “very old” (see also [42]).
Further down we will discuss the complicated history of this question. Our
main result is a resolution of this problem. To begin we develop some theory
and examples of linear division sequences (which we denote LDS for
convenience). The main difficulty is that LDS’s may be defined differently in
different congruence classes modulo some integer $M$: for example,
$(1_{(n,M)=1})_{n\geq 0}$ or any other periodic LDS.

Since any product of linear division sequences (LDS’s) is also a LDS, we will
factor LDS’s into more basic LDS’s, so that every LDS is more-or-less a
product of basic LDS’s. There are four types of basic LDS’s.

### Periodic LDS’s

Any periodic division sequence is a LDS. Indeed $(u_{n})_{n\geq 0}$ is a
(purely) periodic LDS of period $M$ if and only if $u_{d}$ divides $u_{D}$
whenever $d$ divides $D$, which divides $M$, and

$u_{n}=u_{a}=\sigma_{a}u_{d}\text{ whenever }n\equiv a\pmod{M}\text{ and
}d=(a,M)$ (3)

where $\sigma_{d}=1$ and otherwise $\sigma_{a}=-1$ or $1$.

If there are characteristic roots $\alpha_{i}\neq\alpha_{j}$ such that
$\alpha_{i}/\alpha_{j}$ is a root of unity then $(u_{n})_{n\geq 0}$ is
_degenerate_.333Some authors have restricted their attention to classifying
non-degenerate LDS’s but not all, so we investigate both. Much more important
for our considerations is the _period_ $M$ of the linear recurrence sequence
$(u_{n})_{n\geq 0}$ which is defined to be the smallest positive integer such
that whenever $\alpha_{1}^{e_{1}}\cdots\alpha_{m}^{e_{m}}$ (each
$e_{i}\in\mathbb{Z}$) is a root of unity, it is an $M$th root of
unity.444Beware: By this definition, every linear recurrence sequence has a
period, _but_ this does not necessarily make it periodic! Thus if
$(u_{n})_{n\geq 0}$ is degenerate then $M>1$.555But not vice-versa, for
example $8^{n}-(-4)^{n}-2^{n}+(-1)^{n}$ has period 2 but is non-degenerate.

There are many ways in which a “period” $M$ can be relevant. For example if
$(v_{n})_{n\geq 0}$ is a LDS then so is $(u_{n})_{n\geq 0}$ where
$u_{Mn}=v_{n}$ and otherwise $u_{n}=1$. More generally if $(v^{(d)}(n))_{n\geq
0}$ are LDS’s for each $d$ dividing $M$ then

$u_{n}:=\prod_{d|(M,n)}v^{(d)}_{n/d}(t)\text{ is also a LDS}.$ (4)

This construction invalidates several classifications that have been proposed
in the literature (e.g. in [10]). We will see how periods impact on all the
other types of LDS’s:

### Power LDS’s

We have already noted the examples $(n^{d})_{n\geq 0}$ for each integer $d\geq
0$, but there are also more complicated examples in which $u_{n}$ is more-or-
less a power of $n$ depending on some period $M\geq 1$: Select integers
$e_{d}$ for each positive divisor $d$ of $M$ for which

$0\leq e_{d}\leq e_{D}\text{ whenever }d\text{ divides }D,\text{ which divides
}M.$

Then we have the _power LDS_

$u_{n}=(n/d)^{e_{d}}\text{ where }(n,M)=d.$ (5)

### Exponential LDS’s

An LDS like $(2^{n})_{n\geq 0}$ appears at first sight to be a trivial
complication. But exponents in such a LDS can assume different patterns, and
exponential LDS’s can be multiplied together. We formulate exponential LDS’s
as powers of a variable $t$, and then we can substitute an integer for $t$ to
get an exponential LDS in $\mathbb{Z}$. We begin with $u_{0}=0$ and, for
$1\leq a\leq M$, we define the _exponential LDS_ in $\mathbb{C}[t]$ by

$u_{a+kM}(t)=t^{kh_{a}}\text{ for all }k\geq 0$ (6)

where each $h_{a}\in\mathbb{Z}_{\geq 0}$ and if $1\leq a,b,r\leq M$ then

$h_{a}\leq rh_{b}\text{ whenever }b\equiv ra\pmod{M}.$

We obtain an _exponential LDS_ in $\mathbb{Z}$ by taking distinct primes
$p_{1},\dots,p_{r}$ and exponential LDS’s $(u_{1,n}(t))_{n\geq
0},\dots,(u_{r,n}(t))_{n\geq 0}$ in $\mathbb{C}[t]$, and then letting

$u_{n}=u_{1,n}(p_{1})\cdots u_{r,n}(p_{r})\text{ for every }n\geq 1.$ (7)

Exponential LDS’s in $\mathbb{Z}$ are easily identified since there must exist
a prime $p$ such that $v_{p}(u_{n})\gg n$ for an infinite sequence of integers
$n$ (where $v_{p}(m)$ denotes the exact power of $p$ dividing $m$), and this
does not hold for any other type of LDS.

### Polynomially generated LDS’s

This is the most interesting class of LDS’s, and includes Lucas sequences
(that is, $\frac{\alpha^{n}-\beta^{n}}{\alpha-\beta}$ where $\alpha\neq\beta$
are both integers, or conjugate quadratic integers) like $F_{n}$ and
$2^{n}-1$, and many others. The main idea is to construct a linear division
sequence in $\mathbb{C}[t]$, homogenize it to obtain a LDS in
$\mathbb{C}[x,y]^{\text{homogenous}}$, substitute in algebraic integers for
$x$ and $y$, and then take the norm (or an appropriate subproduct of the norm)
to obtain a LDS in $\mathbb{Z}$. For example $(\frac{t^{n}-1}{t-1})_{n\geq 0}$
is a LDS in $\mathbb{C}[t]$, and it homogenizes to the LDS
$(\frac{x^{n}-y^{n}}{x-y})_{n\geq 0}$ in
$\mathbb{C}[x,y]^{\text{homogenous}}$. We can substitute in $x=2,y=1$ to
obtain the Mersenne numbers, or $x,y=\frac{1\pm\sqrt{5}}{2}$ for the Fibonacci
numbers666A priori one might have expected to take the norm here for
$\mathbb{Q}(\sqrt{5})/\mathbb{Q}$ but we need not since the value is already
an integer, and so we restrict our product to a subproduct of the norm., or
conjugate quadratics $\alpha$ and $\beta$ to obtain a Lucas sequence.

The simplest LDS’s in $\mathbb{C}[t]$ take the form $(f(t^{n})/f(t))_{n\geq
0}$ for an appropriate choice of $f(t)\in\mathbb{C}[t]$. We just saw that
Lucas sequences come from the example $f(t)=t-1$, but one can also take
$f(t)=t^{2}-1$ or $t^{3}-1$, or even $\text{\rm
lcm}[t^{2}-1,t^{3}-1]=(t+1)(t^{3}-1)$ (the least common multiple as
polynomials), and in general

$f(t)=\text{lcm}[(t^{k}-1)^{a_{k}}:k\geq 1]$ (8)

where each $a_{k}\geq 0$ is an integer, with only finitely many of the $a_{i}$
non-zero. (This is a reformulation of a result of Koshkin [26].).

A _multiplicatively-dependent_ linear recurrence is one in which all pairs of
characteristic roots $\alpha_{i}\neq\alpha_{j}$ are multiplicatively dependent
(that is there exist non-zero integers $r,s$ for which
$\alpha_{i}^{r}=\alpha_{j}^{s}$).777In which case there exists a $\gamma$ such
that every $\alpha_{i}=\zeta_{i}\gamma^{a_{i}}$ for some $a_{i}\in\mathbb{Z}$
and root of unity $\zeta_{i}$ (see Lemma 10.1). The LDS’s
$(f(t^{n})/f(t))_{n\geq 0}$ given by (8) are all multiplicatively-dependent
LDS’s in $\mathbb{C}[t]$, and there are more, for example one can take
$f_{n}(t)=(\zeta t)^{n}-1$ where $\zeta$ is a root of unity for each $n\geq
0$, or even

$f_{n}(t)=\underset{\begin{subarray}{c}\ m\geq 1\\\ \,0\leq j\leq
M-1\end{subarray}}{\text{\rm lcm}}((\zeta_{M}^{j}t^{m})^{n}-1)^{h_{m,j}}$ (9)

where $\zeta_{M}$ is a primitive $M$th root of unity, each $h_{m,j}\geq 0$ is
an integer, with only finitely many non-zero. LDS’s $(f_{n}(t))_{n\geq 0}$ in
$\mathbb{C}[t]$ of period $M$ are classified in Theorem 5, normalized so that
$f_{d}(t)=1$ whenever $d$ divides $M$.

Homogenizing the $(f_{n}(t))_{n\geq 0}$ we obtain a _multiplicatively-
dependent LDS_ $(F_{n}(x,y))_{n\geq 0}$ in
$\mathbb{C}[x,y]^{\text{homogenous}}$; here we adjust our definition of
multiplicatively-dependent since now it is the ratios $\alpha_{i}/\alpha_{j}$
of the characteristic roots that are multiplicatively dependent (not the
$\alpha_{i}$’s themselves).

Next for any given $\alpha,\beta\in\overline{\mathbb{Q}^{*}}$ where
$\alpha/\beta$ is not a root of unity, let $L$ be the splitting field
extension for $\alpha$ and $\beta$ over $\mathbb{Q}$, and let $H$ be a
minimally sized set of elements of $\text{Gal}(L/\mathbb{Q})$ for which

$\prod_{\sigma\in H}F_{n}(\alpha,\beta)^{\sigma}\in\mathbb{Z}\text{ for all
}n,\text{ and }\prod_{\sigma\in H}(\alpha,\beta)^{\sigma}\text{ is an ideal of
}\mathbb{Z}$

(where $\theta^{\sigma}$ means applying the Galois element $\sigma$ to the
algebraic number $\theta$).888$H$ is typically a set of representatives for
$\text{Gal}(L/\mathbb{Q})\,/\,\text{Stab}_{\text{Gal}(L/\mathbb{Q})}(\tfrac{F_{n}(\alpha,\beta)}{F_{1}(\alpha,\beta)}:n\geq
1).$ but not always, as we will see with Lehmer sequences below. Then select
$q$ to be the positive integer for which

$(q)=\prod_{\sigma\in H}(\alpha,\beta)^{\sigma},\text{ let
}v_{n}=\frac{1}{q^{\deg F_{n}}}\cdot\prod_{\sigma\in
H}F_{n}(\alpha,\beta)^{\sigma},$

and $(u_{n})_{n\geq 0}$ is a _polynomially generated LDS_ in $\mathbb{Z}$
where $u_{n}=v_{n}/v_{(n,M)}$.

We call $(u_{n})_{n\geq 0}$ a _Lucas sequence of order_ $r$ if
$F_{n}(x,y)=x^{n}-y^{n}$ and $|H|=r$.

######  Remark 1.

For convenience, in the definitions of power LDS, exponential LDS and
polynomially generated LDS, we “normalized” the values at each divisor $d$ of
$M$, forcing $u_{d}=1$, but left $u_{d}$ to be more flexible for a periodic
LDS.

###  1.2. Classifying LDS’s and strong LDS’s in $\mathbb{Z}$

We begin by classifying non-degenerate linear division sequences in the
integers.

######  Corollary 1.

If $(u_{n})_{n\geq 0}$ is a non-degenerate linear division sequence of period
$M$ in the integers with $u_{1}=1$ then $u_{n}=n^{e}\lambda^{n-1}v_{n}$ where
$e\geq 0$ and $\lambda\neq 0$ are integers, and $(v_{n})_{n\geq 0}$ is the
product of polynomially generated LDS’s, constructed from LDS’s
$(f_{n}(t)/f_{1}(t))_{n\geq 0}$ in $\mathbb{C}[t]$ with $f_{n}(t)$ as in (9).

The $\zeta_{M}$’s in the definition of the $v_{n}$’s in Corollary 1 seem to be
necessary: for example $8^{n}-(-4)^{n}-2^{n}+(-1)^{n}$, and see the discussion
after the proof of Corollary 1.

Corollary 1 follows from our main theorem:

######  Theorem 1.

If $(u_{n})_{n\geq 0}$ is a linear division sequence in the integers with
period $M$ then $u_{n}$ is the product of a periodic sequence of rationals (of
period $M$), a power LDS, an exponential LDS and a finite number of
polynomially generated LDS’s.

Theorem 1 would be “if and only if”, if we could be more specific about the
periodic sequence of rationals (so as to guarantee each $(u_{n})_{n\geq 0}$ is
a division sequence in $\mathbb{Z}$) but the necessary conditions appear to be
complicated. Certainly the product is a LDS in $\mathbb{Z}$ if the periodic
sequence is any periodic LDS, but there are can be several other cases
besides. If we don’t allow an exponential LDS factor (which is arguably the
more natural case) then we can provide an “if and only if” statement:

######  Corollary 2.

$(u_{n})_{n\geq 0}$ is a linear division sequence in the integers with

$\limsup_{n\to\infty:\ u_{n}\neq 0}v_{p}(u_{n})/n=0$ for every prime $p$

if and only if $u_{n}$ is the product of a periodic LDS, a power LDS, and a
finite number of polynomially generated LDS’s.

In section 7.4 we will explain how to determine the “LDS factors” from Theorem
1 and Corollary 2 of a given LDS in $\mathbb{Z}$.

A _strong linear division sequence in the integers_ is a linear recurrence
sequence $(u_{n})_{n\geq 0}$ for which

$(u_{m},u_{n})=|u_{(m,n)}|\text{ for all integers }m,n\geq 1.$

Well-known examples include $F_{n},2^{n}-1,n$ and powers of these. In our next
result we will classify all strong LDS’s, showing that there are little more
than the obvious generalizations of these examples.

######  Theorem 2.

$(u_{n})_{n\geq 0}$ is a strong linear division sequence in the integers of
period $M$ with $u_{1}=1$ if and only if $\kappa_{n}$ is a strong periodic LDS
of period $M$ with $\kappa_{n}=\pm\kappa_{d}$ where $d=(n,M)$ for $1\leq n\leq
M$, and for some integer $r\geq 1$ one of the following holds:

  * •

$u_{n}=\kappa_{d}$;

  * •

$u_{n}=\kappa_{d}(n/d)^{r}$ and each $\kappa_{p^{e}}$ is a power of $p$, and
$\kappa_{d}=\prod_{p^{e}\|d}\kappa_{p^{e}}$ for each $d|M$;

  * •

$u_{n}=\kappa_{d}(w_{n}/w_{d})^{r}$, $w_{n}$ a Lucas sequence or a Lehmer
sequence (with $r$ even).101010Lehmer sequences will be described in section
2.1.

Moreover if $D$ is the smallest integer for which a given prime power $p^{e}$
divides $u_{D}$, then $p^{e}$ divides $u_{n}$ if and only if $D$ divides $n$.

Our proofs of these theorems do not require that the linear recurrence
$(u_{n})_{n\geq 0}$ is a division sequence in the hypotheses, but rather only
that $u_{n}$ divides $u_{jn}$ (or $(u_{in},u_{jn})=u_{(i,j)n}$) for all $i,j$
up to some (explicit) bound that depends only on $k$, for many large $n$ in
each arithmetic progression mod $M$. We can interpret this as saying that if
$\gcd(u_{n},\dots,u_{rn})=u_{n}$ often enough then there is an “algebraic
reason” for this (that is, that $(u_{n})_{n\geq 0}$ is a LDS). One might guess
that even if these gcds are only pretty large then there must also be an
“algebraic reason” for it, as we now exhibit:

######  Theorem 3.

Suppose that $(u_{n})_{n\geq 0}$ is a linear recurrence sequence in the
integers with period $M$ of order $k$ with $u_{0}=0$. Fix $\epsilon>0$.
Suppose that $\gcd(u_{n},\dots,u_{(k-1)n})>e^{\epsilon n}$ for
$\geq\epsilon\frac{x}{M}$ integers $n\leq x$ with $n\equiv a\pmod{M}$ once $x$
is sufficiently large. Then there exists a LDS, $(v_{n})_{n\geq 0}$, and a
linear recurrence sequence $(w_{n})_{n\geq 0}$, both in $\mathbb{Z}$, such
that

$u_{n}=v_{n}w_{n}\text{ for all sufficiently large }n\equiv a\pmod{M}.$

We can also prove such a theorem when taking the gcd of two different LDS’s:

######  Theorem 4.

If $(u_{n})_{n\geq 0}$ and $(v_{n})_{n\geq 0}$ are linear division sequences
in $\mathbb{Z}$ for which $\gcd(u_{m},v_{n})>e^{\epsilon(m+n)}$ for infinitely
many pairs $m,n$, then there exists a LDS $(w_{n})_{n\geq 0}$ in $\mathbb{Z}$
and $q\in\mathbb{Z}_{>0}$ such that $w_{n}$ divides $(u_{qn},v_{qn})$ for all
$n\geq 1$.

In both of these theorems the LDS factor can be taken to be either an
exponential or a polynomially generated LDS, and so grows exponentially fast.
The proofs of Theorems 3 and 4 are a relatively simple consequence a (deep)
application by Corvaja and Zannier [8] of the Schmidt-Schlickiwei subspace
theorem. In section 12 we conclude the paper by discussing various
developments, particularly the paper of Levin [29], exploring further
questions about large factors of linear recurrence sequences.

Hall [23] and many subsequent authors focused on determining all of the LDS’s
in $\mathbb{Z}$ of low order with $u_{0}=0$. In section 11 we use our results
to establish a method that can determine all LDS’s in $\mathbb{Z}$ with
$u_{0}=0$ with order up to any given bound

We give two different though inter-related proofs of Theorem 1, each depending
on the Ritt-Gourin-MacColl theory of multinomial factorizations [36, 15, 32],
and the Hadamard quotient theorem [38, 37]. We will see that each approach has
its benefits for different applications. Corollaries 1 and 2 and Theorem 2 are
essentially corollaries involving mostly complicated elementary number theory,
but also the Čebotarev density theorem for the proof of Theorem 2

An analogous result to Theorem 1 can be proved in
$\mathbb{C}[t_{1},\dots,t_{m}]$ with obvious modifications (since the
application of the Ritt-Gourin-MacColl theory will work analogously).
Analogous results to Theorems 3 and 4 can be proved in
$\mathbb{C}[t_{1},\dots,t_{m}]$ by replacing Corvaja-Zannier [8] by the
results of Ostafe [34].

### Simplifying notation

Every fractional ideal $I$ of $K$ may be written as $N/D$ where $N$ and $D$
are coprime integral ideals, by the unique factorization theorem for ideals.
Even if $I$ is principal, one cannot necessarily determine $N$ and $D$ that
are both coprime and principal (that is, the analogy of “reduced fractions” is
complicated in number fields). We let $I^{*}:=N$ be the numerator.
Polynomially generated LDS’s were defined as the generator of the ideal which
is the product over a set of conjugates of

$\frac{(F_{n}(\alpha,\beta))}{(\alpha,\beta)^{\deg
F_{n}}}=(f_{n}(\gamma))^{*}\text{ where }F_{n}(x,y)=y^{\deg
F_{n}}f_{n}(x/y)\text{ and }\gamma=\alpha/\beta,$

which gives a different perspective on polynomially generated LDS’s. We say
that $f_{n}(\gamma)$ divides $u_{n}$ if $(f_{n}(\gamma))^{*}$ divides $u_{n}$.
We also define $N(I):=\text{Norm}_{K/\mathbb{Q}}(I^{*})$.

For each subset $I\subset\\{1,\dots,k\\}$ let $g_{I}(t):=\sum_{i\in
I}g_{i}(t)$ where the $g_{i}(t)$ are as defined in (2). Let $\mathcal{I}^{*}$
be the set of partitions $\mathcal{I}=I_{1}\cup\dots\cup I_{h}$ of
$\\{1,\dots,k\\}$ (with $\alpha_{j}\in I_{j}$ for $1\leq j\leq h$) for which
each $g_{I_{j}}(t)=0$ and the elements of $\\{\alpha_{i}/\alpha_{j}:\ i\in
I_{j},1\leq j\leq h\\}$ are pairwise multiplicatively dependent.111111$u$ and
$v$ are multiplicatively dependent if there exist non-zero integers $r$ and
$s$ for which $u^{r}=v^{s}$.

We will see that for every $\gamma$ which gives rise to a polynomially
generated LDS for which $f_{n}(\gamma)\neq 1$ divides $u_{n}$, there exists a
partition $\mathcal{I}\in\mathcal{I}^{*}$ such that
$(\alpha_{i}/\alpha_{j})^{n}=(\gamma^{n})^{e_{i}}$ for some
$e_{i}\in\mathbb{Z}$ for all $i\in I_{j},1\leq j\leq h$.

##  2\. History and first remarks on LDS’s

The first example of a linear division sequence in $\mathbb{Z}$ is the
Fibonacci numbers, defined by the linear recurrence $F_{n}=F_{n-1}+F_{n-2}$
for all $n\geq 2$ with $F_{0}=0$ and $F_{1}=1$. One also has the Mersenne
numbers $u_{n}=2^{n}-1$, or $u_{n}=\frac{\alpha^{n}-\beta^{n}}{\alpha-\beta}$
for two distinct integers $\alpha,\beta$, or even for two conjugate quadratic
algebraic integers $\alpha,\beta$ (that is, any _Lucas sequence_). These are
all polynomially generated LDS’s. There are other examples like
$u_{n}=a^{n},u_{n}=n^{d}$ and appropriate periodic sequences, as well as any
product of already known linear division sequences.

In 1875 Édouard Lucas [31] in the first volume of the first mathematics
journal to be printed in North America, wrote extensively (in French) about
the local and global properties of linear recurrence sequences, mentioning the
divisibility of Fibonacci numbers by one another. Such divisibility properties
arose in several subsequent works, and in 1936 Marshall Hall [23] asked
specifically about LDS’s and partly classified third-order ones (that is,
$k=3$ in (1)). Since then it was until very recently implicitly supposed that
all LDS’s are a product of the simplest LDS’s mentioned in the previous
paragraph. Some support of this supposition was given by Bézivin, Pethő and
van der Poorten [5] who showed that any LDS _divides_ the product of certain
LDS’s of order 2, times $cn^{d}$ for some integers $c\neq 0$ and $d\geq 0$,
but this is not precise enough to answer many obvious questions (like
classifying all LDS’s of order 3).

To discuss LDS’s we need to make, without loss of generality, some simplifying
assumptions. First, we may assume that

$u_{1}=1$

since if $(u_{n})_{n\geq 0}$ is a LDS then so is $(u_{n}/u_{1})_{n\geq 0}$
(and $u_{1}\neq 0$ else $u_{n}=0$ for all $n$).

Either $(u_{n})_{n\geq 0}$ is a periodic LDS, or

$u_{0}=0.$

For if $u_{0}\neq 0$ then each $u_{n}$ divides $u_{0}$, a finite set of
possibilities, so there are only finitely many possibilities for
$(u_{n-1},\dots,u_{n-k})$. Therefore $u_{n-i}=u_{m-i}$ for $1\leq i\leq k$ for
some $n>m\geq 0$, so that $u_{n+i}=u_{m+i}$ for all $i\geq 0$ by induction
using (1); that is, $(u_{n})_{n\geq 0}$ is periodic. We will prove our
classification of periodic LDS’s (as well as power LDS’s and exponential
LDS’s) at the end of this section.

We now highlight why it has been challenging to even guess at what the
classification should be, through several examples. Several authors seem to
have assumed that linear division sequences will be the product of Lucas
sequences and power LDS’s. If so then all periodic LDS’s would be the product
of LDS’s of order two but this is easily contradicted by examples like
$u_{n}=7$ if $3|n$ and $u_{n}=1$ otherwise, given by $u_{n}=u_{n-3}$ for all
$n\geq 3$ so that $u_{n}=3+2\omega^{n}+2\overline{\omega}^{n}$ where $\omega$
is a primitive cube root of unity.

So perhaps LDS’s might all be products of Lucas sequences, periodic LDS’s and
power LDS’s? The Lucas sequences might not all be defined over $\mathbb{Z}$ so
would be a product of conjugate Lucas sequences. However this does not give
all the possibilities as shown by an example found by Peter Bala [2], namely
$(L_{n}F_{3n})_{n\geq 0}$ where $L_{n}$ is the sequence that begins
$2,1,3,4,\dots$ with $L_{n}=L_{n-1}+L_{n-2}$ for all $n\geq 2$, so that

$L_{n}F_{3n}=\text{\rm lcm}[F_{2n},F_{3n}]=U_{n}(\alpha,\beta)\text{ with
}\alpha,\beta=\frac{-1\pm\sqrt{5}}{2}$

and

$U_{n}(x,y)=\frac{f(x^{n},y^{n})}{f(x,y)}\text{ with
}f(x,y)=(x+y)(x^{3}-y^{3}),$

a linear division sequence in $\mathbb{Z}[x,y]$. At first sight it is not
obvious that $f(x^{m},y^{m})$ divides $f(x^{n},y^{n})$ whenever $m$ divides
$n$, but becomes obvious when we note that

$f(x,y)=\text{\rm lcm}[x^{2}-y^{2},x^{3}-y^{3}]\text{ in }\mathbb{Z}[x,y].$

This is the main idea that was missing in previous attempts to classify LDS’s,
that one can take lcms of LDS’s in $\mathbb{C}[t]$ to obtain another LDS in
$\mathbb{C}[t]$, and then homogenize and substitute algebraic integers to
obtain a LDS in $\mathbb{Z}$. In the next section we will classify LDS’s in
$\mathbb{C}[t]$, which will allow us to find all polynomially generated LDS’s
(as given in the introduction). When taking the product over conjugate
algebraic integers, there are several issues to take care of:

###  2.1. Conjugates and gcd’s, not norms

Substituting algebraic integers $x=\alpha,y=\beta$ into the LDS
$u_{n}(x,y)=\frac{x^{n}-y^{n}}{x-y}$ in $\mathbb{Z}[x,y]$ and taking
$\text{Norm}_{K/\mathbb{Q}}u_{n}(\alpha,\beta)$ where
$K=\mathbb{Q}(\alpha,\beta)$ we obtain a LDS in $\mathbb{Z}$ but not
necessarily the most “basic” LDS that could come out of this construction. For
example with $\alpha,\beta=\frac{-1\pm\sqrt{5}}{2}$, the norm of
$u_{n}(\alpha,\beta)$ is $F_{n}^{2}$, not the simpler $F_{n}$.

Let $L$ be the splitting field extension for $\alpha$ and $\beta$ over
$\mathbb{Q}$ and $G:=\text{Gal}(L/\mathbb{Q})$. Let $H$ be a minimally sized
set of elements of $\text{Gal}(L/\mathbb{Q})$ for which $\prod_{\sigma\in
H}u_{n}(\alpha,\beta)^{\sigma}\in\mathbb{Z}\text{ for all }n,\text{ and
}\prod_{\sigma\in H}(\alpha,\beta)^{\sigma}\text{ is an ideal of }\mathbb{Z}$,
and then we divide the first quantity be the second to obtain a LDS in
$\mathbb{Z}$.

The following family of examples, due to Lehmer [27, 42], is surprising so
worth mentioning: For squarefree integers $r,s=r-4d$ let
$\alpha,\beta=\frac{\sqrt{r}\pm\sqrt{s}}{2}$, which are two roots of an
irreducible quartic polynomial in $\mathbb{Z}[x]$ (the other roots are
$-\alpha$ and $-\beta$). Now $u_{n}(\alpha,\beta)\in\mathbb{Z}$ if $n$ is odd,
$\in\sqrt{r}\cdot\mathbb{Z}$ if $n$ is even, so we let $H=\\{\i,\rho\\}$ where
$\rho(\sqrt{r})=-\sqrt{r}$, and therefore every $u_{n}(\alpha,\beta)\cdot
u_{n}(\alpha,\beta)^{\rho}\in\mathbb{Z}$. But
$u_{n}(\alpha,\beta)^{\rho}=(-1)^{n-1}u_{n}(\alpha,\beta)$ and so
$u_{n}(\alpha,\beta)^{2}$ is a Lucas sequence of order two. This has
characteristic roots $\alpha^{2},\beta^{2}=\frac{r-2d\pm\sqrt{rs}}{2}$, the
roots of an irreducible quadratic polynomial in $\mathbb{Z}[x]$, and
$\alpha\beta=d\in\mathbb{Z}$. We call $u_{n}(\alpha,\beta)^{2}$ a _Lehmer
sequence_ , which is evidently a (non-decomposable) LDS of order 3 (and a
Lucas sequence of order 2). We will take another perspective on Lehmer
sequences at the end of this section.

When $\alpha,\beta\in\mathbb{Z}$ we may assume they are coprime by dividing
out by their gcd. However in a number field their gcd, the ideal
$(\alpha,\beta)$, might be non-principal, in which case $u_{n}(\alpha,\beta)$
would be unavoidably divisible by $(\alpha,\beta)^{n-1}$. This explains why we
took $q\in\mathbb{Z}_{>0}$ for which $(q)=\prod_{\sigma\in
H}(\alpha,\beta)^{\sigma}$ and take the LDS $q^{-\deg u_{n}}\prod_{\sigma\in
H}u_{n}(\alpha,\beta)^{\sigma}$ in $\mathbb{Z}$.

Any Lucas sequence of order 2 takes the form

$q^{-(n-1)}\frac{\tau_{1}^{n}-\nu_{1}^{n}}{\tau_{1}-\nu_{1}}\cdot\frac{\tau_{2}^{n}-\nu_{2}^{n}}{\tau_{2}-\nu_{2}}=q^{-(n-1)}\frac{\alpha^{n}+\delta^{n}-\beta^{n}-\gamma^{n}}{\alpha+\delta-\beta-\gamma},$

where $(q)=(\tau_{1},\nu_{1})(\tau_{2},\nu_{2})$ with
$\alpha=\tau_{1}\tau_{2},\beta=\tau_{1}\nu_{2},\gamma=\nu_{1}\tau_{2}$ and
$\delta=\nu_{1}\nu_{2}$, so that $\alpha\delta=\beta\gamma$. Guy and Williams
[21] considered examples where $\alpha\delta=\beta\gamma=m\in\mathbb{Z}$ so
that

$(x-\alpha)(x-\delta)=x^{2}-\rho
x+m,(x-\beta)(x-\gamma)=x^{2}-\overline{\rho}x+m\text{ with
}(x-\rho)(x-\overline{\rho})\in\mathbb{Z}[x].$

In this case one obtains an alternative (though equivalent) factorization

$u_{n}:=\frac{\alpha^{n}+\delta^{n}-\beta^{n}-\gamma^{n}}{\alpha+\delta-\beta-\gamma}=\alpha^{-(n-1)}\bigg{(}\frac{\alpha^{n}-\beta^{n}}{\alpha-\beta}\bigg{)}\bigg{(}\frac{\alpha^{n}-\gamma^{n}}{\alpha-\gamma}\bigg{)}.$
(10)

One can develop these examples starting from the last two displayed equations.
If $\alpha,\beta,\gamma$ and $\delta$ are all irreducible then $u_{n}$ cannot
be expressed without dividing through by some quantity like $\alpha^{n-1}$.
For example, we have the famous example

$2\cdot 3=(1+\sqrt{-5})(1-\sqrt{-5})$

so that $u_{n}=\frac{1}{3}(2^{n}+3^{n}-(1+\sqrt{-5})^{n}-(1-\sqrt{-5})^{n})$
is a LDS starting $0,1,7,21$ with
$u_{n+4}=7u_{n+3}-22u_{n+2}+42u_{n+1}-36u_{n}$ for $n\geq 4$. In terms of a
Lucas sequence of order two we have

$u_{n}=3^{-(n-1)}\bigg{(}\frac{3^{n}-(1+\sqrt{-5})^{n}}{2-\sqrt{-5}}\bigg{)}\bigg{(}\frac{3^{n}-(1-\sqrt{-5})^{n}}{2+\sqrt{-5}}\bigg{)}.$

If $\alpha,\beta=\frac{\sqrt{r}\pm\sqrt{s}}{2}$ where $(r,s)=1$ then
$\alpha\sqrt{r},\beta\sqrt{r}=\frac{r\pm\sqrt{D}}{2}$ where $D=rs$, so that
$u_{n}(\alpha\sqrt{r},\beta\sqrt{r})=\sqrt{r}^{n-1}u_{n}(\alpha,\beta)$ is a
Lucas sequence in $\mathbb{Z}$ (where $u_{n}(\alpha,\beta)$ is a Lehmer
sequence). Although the $u_{n}(\alpha\sqrt{r},\beta\sqrt{r}),n\geq 1$ are
stable under the action of $G$, the gcd
$(\alpha\sqrt{r},\beta\sqrt{r})=\sqrt{r}$ is not, so $H$ can be taken to be
the identity together with any other $\sigma\in G$, obtaining the Lehmer
sequence
$u_{n}(\alpha,\beta)^{2}=u_{n}(\alpha\sqrt{r},\beta\sqrt{r})^{2}/r^{n-1}$.

###  2.2. gcd’s and lcm’s of LDS’s in $\mathbb{Z}$

If $(u_{n})_{n\geq 0}$ and $(v_{n})_{n\geq 0}$ are division sequences in
$\mathbb{Z}$ then so are $(\gcd(u_{n},v_{n}))_{n\geq 0}$ and $(\text{\rm
lcm}[u_{n},v_{n}])_{n\geq 0}$. They can be linear recurrence sequences, like
$\gcd(F_{2n},F_{3n})=F_{n}$ and $\text{\rm lcm}[F_{2n},F_{3n}]=L_{n}F_{3n}$
but not necessarily so, as we will show with the example $\gcd(2^{n}-1,F_{n})$
in Theorem 6. We now show that the gcd and lcm questions are equivalent:

The Hadamard quotient theorem (van der Poorten and Rumely, [37, 38]) _If
$(a_{n})_{n\geq 0}$ and $(b_{n})_{n\geq 0}$ are linear recurrence sequences in
the integers and $a_{n}=b_{n}c_{n}$ for all $n\geq 0$ where each
$c_{n}\in\mathbb{Z}$ then $(c_{n})_{n\geq 0}$ also satisfies a linear
recurrence._121212Corvaja and Zannier [7] proved the much stronger result that
if $b_{n}$ divides $a_{n}$ for infinitely many $n$ then there exists a
polynomial $f(x)$ and a linear recurrence $(c_{n})_{n\geq 0}$ in $\mathbb{Z}$
for which $f(n)a_{n}=b_{n}c_{n}$ for all $n$ in a suitable arithmetic
progression. The example $a_{n}=2^{n}-2,b_{n}=n+2^{n}+(-2)^{n}$ shows that the
$f$ can be necessary when taking $n$ to be odd. This also follows from the
recent work of Levin [29] which we discuss in section 12.

Taking $a_{n}=u_{n}v_{n}$ with $b_{n}=(u_{n},v_{n})$ or $[u_{n},v_{n}]$ we
deduce that $(u_{n},v_{n})$ satisfies a linear recurrence if and only if
$[u_{n},v_{n}]$ does.

###  2.3. Classifying periodic LDS’s

Suppose that $(u_{n})_{n\geq 0}$ is a LDS in $\mathbb{Z}$ of period $M$.
Evidently $u_{d}$ divides $u_{D}$ whenever $d$ divides $D$ divides $M$. If
$(a,M)=d$ then there exist integers $A$ and $B$ such that $a=Ad$ and $aB\equiv
d\pmod{M}$, so that $u_{d}$ divides $u_{Ad}=u_{a}$, which divides
$u_{aB}=u_{d}$ (by periodicity), and so $|u_{a}|=|u_{d}|$. We therefore obtain
the classification given in (3).

###  2.4. Classifying power LDS’s

Here $u_{n}=n^{e_{a}}$ where the $e_{a}$ have period $M$. Let $p$ be a large
prime $\equiv 1\pmod{M}$. If $d$ divides $a$ and $(a,p)=1$ then $u_{dp}$
divides $u_{ap}$, and so $e_{d}=v_{p}(u_{dp})\leq v_{p}(u_{ap})=e_{a}$ (where
we define $v_{p}(p^{v}r/s)=v$ when $p\nmid rs$ and $v\in\mathbb{Z}$). Moreover
$e_{d}\geq 0$ as $u_{dp}$ is an integer. Taking $a=D|M$ we deduce that $0\leq
e_{d}\leq e_{D}$ whenever $d|D|M$. Now suppose $(a,M)=d$ so as in the last
paragraph $u_{dp}$ divides $u_{ap}$ which divides $u_{aBp}$, so that
$e_{d}\leq e_{a}\leq e_{d}$ as $aBp\equiv d\cdot 1\equiv d\pmod{M}$, so that
$e_{a}=e_{d}$. Therefore we have

$u_{n}=n^{e_{d}}\text{ where }d=(n,M),$

which is almost the classification in (5); there we adjust the constant
outside by dividing through by $d^{e_{d}}$. This is a LDS since $n^{e_{d}}$
divides $(np)^{e_{D}}$ where $D=(dp,M)$ which divides $dp$, and so
$(n/d)^{e_{d}}=(np/dp)^{e_{d}}$ divides $(np/D)^{e_{d}}$ which divides
$(np/D)^{e_{D}}$ as $e_{d}\leq e_{D}$.

###  2.5. Classifying exponential LDS’s

Here $u_{n}=m_{a}^{k}$ where $n=a+kM$ for $1\leq a\leq M$ and $k\geq 0$. We
will study divisibility for each prime $p$, so if $v_{p}(m_{a})=h_{p,a}$ then
$u_{n,p}=p^{kh_{p,a}}$ for $n=a+kM$ (so that $u_{n}=\prod_{p}u_{n,p}$) must be
a division sequence.

Now if $b\equiv ra\pmod{M}$ with $1\leq a,b,r\leq M$ then $u_{a+kM,p}$ divides
$u_{ra+rkM,p}=u_{b+\ell M}$ where $\ell=rk+[\frac{ra}{m}]$, and so

$kh_{p,a}=v_{p}(u_{a+kM})\leq v_{p}(u_{b+\ell M})=\ell h_{p,b}$

and so, dividing through by $k$, we get $h_{p,a}\leq rh_{p,b}+O(1/k)$. Letting
$k\to\infty$ we obtain $h_{p,a}\leq rh_{p,b}$ as these are all integers. We
therefore deduce that $u_{n}$ is given by (7).

##  3\. The period of a linear recurrence sequence

In (2) we write $g_{i}(t)=\sum_{j=0}^{k_{i}-1}g_{i,j}t^{j}$ where the
$g_{i,j}$ are algebraic numbers. Given the $\alpha_{i}$ one can determine the
$g_{i,j}$ from $u_{0},\dots,u_{k-1}$, and vice-versa.

###  3.1. A multiplicative basis for the roots of the characteristic
polynomial

In an example like $1^{n}-2^{n}-3^{n}+6^{n}$ we see that the $n$th powers,
$1^{n},2^{n},3^{n}$ and $6^{n}$, are all multiplicatively dependent on $2^{n}$
and $3^{n}$. In general we can find a multiplicative basis, though we need to
be careful about “torsion” (for example, for $1+5^{n}+(-5)^{n}$ we have the
“basis” $5^{n}$ and $(-1)^{n}$, the latter being “torsion”). One can write
each

$\alpha_{i}=\zeta_{M}^{e_{i,0}}\gamma_{1}^{e_{i,1}}\cdots\gamma_{r}^{e_{i,r}}$

where the $\gamma_{i}$ are multiplicatively independent with each
$e_{i,j}\in\mathbb{Z}$, and the torsion multipliers are all powers of
$\zeta_{M}$, a primitive $M$th root of unity, for some $M\geq 1$. To determine
the $\gamma_{i}$’s and the $e_{i,j}$’s we can take logarithms of all of the
multiplicative dependencies between the $\alpha_{i}$’s and use linear algebra
to find a basis. This argument implies that each $\gamma_{i}$ can be written
as an $M$th root of unity times some product of $\alpha_{j}$’s.

Therefore we can rewrite (2) as
$u_{n}=U_{a}(n,\gamma_{1}^{n},\dots,\gamma_{r}^{n})$ for every $n\equiv
a\pmod{M}$ where

$U_{a}(x,y_{1},\dots,y_{r})=\sum_{i=1}^{m}g_{i}(x)\zeta_{M}^{e_{i,0}a}y_{1}^{e_{i,1}}\cdots
y_{r}^{e_{i,r}},$ (11)

and then $u_{n}$ is determined by this fixed polynomial for all integers $n$
in the congruence class $a\pmod{M}$. This explains why the period, $M$, is a
key element in our considerations. We simplify by combining the terms in (11)
for which the $(e_{i,1},\dots,e_{i,r})$ exponent vectors are identical (though
we don’t change the notation, so this same sum now has a modified meaning).

The exponents $e_{i,j}$ are integers but some might be negative. Therefore we
can write

$U_{a}(x,y_{1},\dots,y_{r})=x^{e_{0}}y_{1}^{e_{1}}\cdots
y_{r}^{e_{r}}\,P_{a}(x,y_{1},\dots,y_{r})$

where $e_{j}=\min_{i}e_{i,j}$ for all $j\geq 1$ with $x^{e_{0}}$ the largest
power of $x$ that divides each $g_{i}(x)$, so that $P_{a}$ is a polynomial,
with a constant term in each variable.

The set of linear recurrences over $\mathbb{Z}$ evidently form a commutative
ring, and include any periodic sequence of integers since

$1_{n\equiv
a\pmod{M}}=\frac{1}{M}\sum_{\zeta:\zeta^{M}=1}\zeta^{-a}\cdot\zeta^{n}.$

Each individual $(U_{a}(n,\gamma_{1}^{n},\dots,\gamma_{r}^{n}))_{n\geq 0}$
($1\leq a\leq M$) is a linear recurrence sequence, as they each take the form
(2). Moreover we can recover $(u_{n})_{n\geq 0}$ from them all by taking

$u_{n}=\sum_{a=1}^{M}\,1_{n\equiv
a\pmod{M}}U_{a}(n,\gamma_{1}^{n},\dots,\gamma_{r}^{n}).$

Thus we can study the structure of each $U_{a}(x,y_{1},\dots,y_{r})$
separately and still recover the whole.

###  3.2. Products of linear recurrence sequences

If $(u_{n})_{n\geq 0}$ and $(v_{n})_{n\geq 0}$ are linear recurrence sequences
then write $u_{n}$ as in (2) and similarly
$v_{n}=\sum_{j=1}^{\ell}h_{j}(n)\beta_{j}^{n}$. Now let the $\gamma_{i}$ be a
multiplicative basis for the non-torsion part of the $\alpha_{i}$’s and
$\beta_{j}$’s, so we can write
$u_{n}=U_{a}(n,\gamma_{1}^{n},\dots,\gamma_{r}^{n})$ and
$v_{n}=V_{a}(n,\gamma_{1}^{n},\dots,\gamma_{r}^{n})$ for all $n\equiv
a\pmod{M}$ for a suitable value of $M$. We then see that if $w_{n}=u_{n}v_{n}$
for all $n\geq 0$ then $(w_{n})_{n\geq 0}$ is also a linear recurrence
sequence (as we have a representation as in (2) where the roots of its
characteristic polynomial are a subset of the $\alpha_{i}\beta_{j}$-values).
Moreover we can define $w_{n}=W_{a}(n,\gamma_{1}^{n},\dots,\gamma_{r}^{n})$
where

$W_{a}(x,y_{1},\dots,y_{r})=U_{a}(x,y_{1},\dots,y_{r})V_{a}(x,y_{1},\dots,y_{r}).$
(12)

The Hadamard quotient theorem states that if $(w_{n})_{n\geq 0}$ and
$(u_{n})_{n\geq 0}$ are linear recurrence sequences for which
$w_{n}=u_{n}v_{n}$ for all $n\geq 0$ where each $v_{n}\in\mathbb{Z}$ then
$(v_{n})_{n\geq 0}$ is also a linear recurrence sequence. We therefore deduce
that (12) holds.

##  4\. Polynomial LDS’s

We are interested in simple LDS’s in $\mathbb{C}[t]$ (or equivalently in
$\mathbb{C}[x,y]^{\text{homogenous}}$) in which all of the roots of the
characteristic polynomial are multiplicatively dependent on $t$. These are the
product of an exponential LDS (which takes account of powers of $t$ in each
term) and a LDS $(u_{n}(t))_{n\geq 0}$ with $u_{0}(t)=0$ and $u_{n}(0)\neq 0$
for all $n\geq 1$ of period $M$, which can be written as

$u_{n}(t)=\kappa_{a}(t)f_{a}(t^{n})\text{ whenever }n\equiv a\pmod{M}\text{
with }n\geq 1$ (13)

where each $f_{a}(t)\in\mathbb{C}[t]$ with $f_{a}(0)\neq 0$ and
$\kappa_{a}(t)\in\mathbb{C}(t)$ . In this section we will determine all
possibilities, which we will use in determining all polynomially generated
LDS’s in $\mathbb{Z}$.

###  4.1. Polynomial LDS’s of period 1

These must be multiples of $u_{n}(t)=f(t^{n})/f(t)$ for all $n\geq 1$ with
$u_{0}(t)=0$, where $f(t^{m})$ divides $f(t^{n})$ in $\mathbb{C}[t]$ whenever
$m$ divides $n$. We have already seen the examples $f(t)=t-1$ and
$f(t)=(t+1)(t^{3}-1)=\text{\rm lcm}[t^{2}-1,t^{3}-1]$ but there are many more:

######  Proposition 1.

Let $f(x)\in\mathbb{C}[x]$ with $f(0)\neq 0$. Then $f(x^{m})$ divides
$f(x^{n})$ in $\mathbb{C}[x]$ whenever $m$ divides $n$ if and only if $f(x)$
takes the form

$\underset{\,m\geq 1}{\text{\rm lcm}}\,(x^{m}-1)^{h_{m}}$

for some $h_{m}\in\mathbb{Z}_{\geq 0}$, only finitely many of which are non-
zero.

Here the lcm is in $\mathbb{C}[x]$. Any such sequence $(f(x^{n}))_{n\geq 0}$
is a linear division sequence.

###### Proof.

Since $f(x)$ divides $f(x^{k})$ we see that if $f(\alpha)=0$ then
$f(\alpha^{k})=0$ for all $k\geq 1$ and so we must have
$\alpha^{j}=\alpha^{i}$ for some $j>i$, else $f(x)$ would have infinitely many
distinct roots. Therefore $\alpha$ is a root of unity, as $\alpha\neq 0$ by
the hypothesis. If $\alpha$ is a primitive $m$th root of unity then
$f(\alpha^{k})=0$ for every $k,1\leq k\leq m$, and so all the $m$th roots of
unity are roots of $f(x)$; that is, $x^{m}-1$ divides $f(x)$. Taking
derivatives one finds that the multiplicity is the same for each primitive
$m$th root of unity, and at least as large otherwise. Therefore there exists
an integer $a_{m}$ such that $\phi_{m}(x)^{a_{m}}\|f(x)$ (where $\phi_{m}(x)$
is the $m$th cyclotomic polynomial) and $a_{n}\geq a_{m}$ whenever $n$ divides
$m$, so that $f(x)=c\prod_{m\leq M}\phi_{m}(x)^{a_{m}}$. This is a result of
Sergiy Koshkin [26] and our result follows by taking each $b_{n}=a_{n}$, and
dividing out by $(x-1)^{a_{1}}$. ∎

###  4.2. Polynomial LDS’s of period M

We begin by showing that we can divide through by $t^{d}-1$ when $(n,M)=d$ in
the simplest example;

######  Lemma 4.1.

For any $M\in\mathbb{Z}_{>1}$ the sequence
$u_{n}(t)=\frac{t^{n}-1}{t^{(n,M)}-1}$ is a LDS in $\mathbb{Z}[t]$.

###### Proof.

Write $t^{n}-1=\prod_{m|n}\phi_{m}(t)$ where $\phi_{m}(t)$ is the $m$th
cyclotomic polynomial., which has no repeated factors, and let
$u_{n}=(t^{n}-1)/(t^{(n,M)}-1)$. We need to show that $u_{n}$ divides $u_{np}$
for any prime $p$ and integer $n$. Let $d=(n,M)$. If $p\nmid M/d$ then
$(np,M)=d$ and so $(t^{d}-1)u_{n}=t^{n}-1$ which divides
$t^{np}-1=(t^{d}-1)u_{np}$ and the result follows. If $p|M/d$ write $n=Nd$ so
that $(M/d,N)=1$ and therefore $p\nmid N$. Any factor $\phi_{m}(t)$ of either
$t^{dp}-1$ or $t^{dN}-1$ must divide $t^{Ndp}-1$. If $\phi_{m}(t)$ divides
both $t^{dp}-1$ and $t^{dN}-1$ then $m$ divides $(dN,dp)=d(N,p)=d$ and so
$\phi_{m}(t)$ also divides $t^{d}-1$. Either way $(t^{dp}-1)(t^{dN}-1)$
divides $(t^{d}-1)(t^{Ndp}-1)$ and so $u_{n}$ divides $u_{np}$. ∎

######  Lemma 4.2.

Let $f(x)\in\mathbb{C}[x]$ be monic with $f(0)\neq 0$. Then $f(x)$ divides
$f(x^{k})$ in $\mathbb{C}[x]$ for all integers $k\equiv 1\pmod{M}$ if and only
if $f(x)$ takes the form

$\underset{\begin{subarray}{c}\ m\geq 1\\\ \,0\leq j\leq
M-1\end{subarray}}{\text{\rm lcm}}(\zeta_{M}^{j}x^{m}-1)^{h_{m,j}}$ (14)

for some $h_{m,j}\in\mathbb{Z}_{\geq 0}$, only finitely many of which are non-
zero.

Since $\zeta_{M}^{j}x^{m}-1$ divides $\zeta_{M}^{kj}x^{km}-1$, it is
convenient to include the terms $(\zeta_{M}^{j}x^{m}-1)^{h_{km,J}}$ where
$J\equiv kj\pmod{M}$ into the lcm if $h_{km,J}\neq 0$ (and we will do so
henceforth). Once we do this we have $h_{m,j}\geq h_{km,kj}$ for all integers
$k\geq 1$.

###### Proof.

We proceed much like in the proof of Proposition 1. Suppose $f(\alpha)=0$ with
$\alpha\neq 0$ then $f(\alpha^{k})=0$ for all $k\equiv 1\pmod{M}$ so $\alpha$
is a root of unity, say a primitive $r$th root of unity. Now $\alpha^{1+iM}$
is a root of $f(x)$ for all integers $i$, and the $1+iM\pmod{r}$ are distinct
for $0\leq i<r/m$ where $m=(r,M)$. Therefore

$\prod_{i=0}^{r/m-1}(x-\alpha^{1+iM})=x^{r/m}-\alpha^{r/m}\text{ is a factor
of }f(x),$

and $\alpha^{r/m}$ is a primitive $m$th root of unity, and so an $M$th root of
unity. Handling powers of factors as in the proof of Proposition 1 the result
follows in one direction; and in the other since
$(\zeta_{M}^{h_{i}})^{k}=\zeta_{M}^{h_{i}}$. ∎

We now classify simple LDS’s in $\mathbb{C}[t]$:

######  Theorem 5.

$(u_{n}(t))_{n\geq 0}$ in $\mathbb{C}[t]$ is a simple LDS in $\mathbb{C}[t]$
of period $M$ for which all of the roots of the characteristic polynomial are
multiplicatively dependent on $t$ if and only if it is the product of a
periodic LDS, an exponential LDS (in powers of $t$) and some LDS
$(v_{n}(t))_{n\geq 0}$, each in $\mathbb{C}[t]$ with period dividing $M$,
where

$v_{n}(t)=\underset{\begin{subarray}{c}\ m\geq 1\\\ \,0\leq j\leq
M/d-1\end{subarray}}{\text{\rm
lcm}}\bigg{(}\frac{(\zeta_{M}^{j}t^{m})^{n}-1}{(\zeta_{M}^{j}t^{m})^{d}-1}\bigg{)}^{h_{d,m,j}}$
(15)

for all $n$ with $(n,M)=d$, where the $h_{d,m,j}\in\mathbb{Z}_{\geq 0}$ with
only finitely many non-zero, satisfying the inequalities

$h_{D,m,j}\geq h_{d,km,kj\text{ mod }{M/d}}\text{ whenever }d\text{ divides
}D,\text{ and }k\geq 1.$

Here $v_{n}(t)$ is the lcm of simpler LDS’s given by Lemma 4.1: That is,
sequences $(\frac{y^{n}-1}{y^{d}-1})^{h_{d}}$ where $y=\zeta_{M}^{j}t^{m}$ and
$h_{d}=h_{d,m,j}$ with $h_{D}\geq h_{d}$ whenever $d|D|M$.

###### Proof.

Let $d=(a,M)$. We apply Lemma 4.2 with $f(x)=f_{a}(x^{a})$ and $M$ replaced by
$M/d$ for $f_{a}(t)$ as in (13), and writing $\zeta_{M/d}=\zeta_{M}^{a}$ we
obtain that

$u_{n}(t)=\kappa_{a}(t)\underset{\begin{subarray}{c}\ m\geq 1\\\ \,0\leq j\leq
M/d-1\end{subarray}}{\text{\rm
lcm}}\bigg{(}\frac{(\zeta_{M}^{j}t^{m})^{n}-1}{(\zeta_{M}^{j}t^{m})^{d}-1}\bigg{)}^{h_{a,m,j}}$

whenever $n\equiv a\pmod{M}$ as
$\zeta_{M/d}^{j}=\zeta_{M}^{aj}=\zeta_{M}^{nj}$, with the definition of
$\kappa_{a}(t)$ adjusted from (13) (by multiplying through by the denominator
here). Written like this, $u_{d}(t)=\kappa_{d}(t)$ is a polynomial. Moreover
$\kappa_{d}(t)$ divides $\kappa_{D}(t)$ whenever $d|D|M$.

Let $H=M\cdot\prod(m:\text{ some }h_{*,m,*}\neq 0\\}$. Select integers $a,b$
with $(a,M)=(b,M)=d$. Take any $B\equiv b\pmod{M}$ and select integers
$A_{1}\equiv A_{2}\equiv a\pmod{M}$ divisible by $B$ with $A_{1}/B,A_{2}/B$
and $H$ pairwise coprime. Therefore

$((\zeta_{M}^{j}t^{m})^{A_{1}}-1,(\zeta_{M}^{j^{\prime}}t^{m^{\prime}})^{A_{2}}-1)=((\zeta_{M}^{j}t^{m})^{B}-1,(\zeta_{M}^{j^{\prime}}t^{m^{\prime}})^{B}-1),$

and so $u_{B}(t)$ divides $(u_{A_{1}}(t),u_{A_{2}}(t))$ which divides

$\kappa_{a}(t)\underset{\begin{subarray}{c}\ m\geq 1\\\ \,0\leq j\leq
M/d-1\end{subarray}}{\text{\rm
lcm}}\bigg{(}\frac{(\zeta_{M}^{j}t^{m})^{B}-1}{(\zeta_{M}^{j}t^{m})^{d}-1}\bigg{)}^{h_{a,m,j}}.$

Therefore each $h_{b,m,j}\leq h_{a,m,j}$ and, by the analogous argument,
$h_{a,m,j}\leq h_{b,m,j}$, so that each $h_{a,m,j}=h_{d,m,j}$ selecting $b=d$.
Moreover if $B=d$ then $u_{d}(t)=\kappa_{d}(t)$ divides
$(u_{A_{1}}(t),u_{A_{2}}(t))=\kappa_{a}(t)$.

Now take $a=d$ above and select $B_{1}\equiv B_{2}\equiv b\pmod{D}$ with
$(B_{1},B_{2})=d$ and $B_{1}/d,B_{2}/d$ and $H$ pairwise coprime. Therefore
$\kappa_{b}(t)$ divides $u_{b}(t)$, which divides
$(u_{B_{1}}(t),u_{B_{2}}(t))$ which, by the last displayed equation, divides
$\kappa_{d}(t)$ since we have
$((\zeta_{M}^{j}t^{m})^{B_{1}}-1,(\zeta_{M}^{j^{\prime}}t^{m^{\prime}})^{B_{2}}-1)=((\zeta_{M}^{j}t^{m})^{d}-1,(\zeta_{M}^{j^{\prime}}t^{m^{\prime}})^{d}-1)$.
Now taking $b=a$ we have $\kappa_{d}(t)$ divides $\kappa_{a}(t)$ and vice-
versa, so that $\kappa_{a}(t)=\kappa_{d}(t)$ times a constant. Therefore the
$(\kappa_{n}(t))_{n\geq 0}$ form a periodic LDS in $\mathbb{C}[t]$, so we can
write

$u_{n}(t)=\kappa_{a}(t)v_{n}(t)$

when $n\equiv a\pmod{M}$ with $(n,M)=d$ and $v_{n}(t)$ as in (15).

If $pd$ divides $M$ with $p$ prime then $v_{n}(t)$ divides $v_{pn}(t)$
whenever $n\equiv d\pmod{M}$ so, by comparing terms,

$h_{pd,m,j}\geq\max\\{h_{d,m,j},h_{d,pm,pj}\\}=h_{d,m,j}.$

The result follows. ∎

We will deduce the full classification of such LDS’s in $\mathbb{C}[t]$ in
Corollary 8.

One might hope that the LDS’s in (15) might all be of the form (4), and
therefore be constructed as a product of simpler LDS’s. However this is not
true as we see from the example with $u_{n}(t)=\frac{t^{3n}-1}{t^{n}-1}$ if
$5\nmid n$, and $u_{n}(t)=\text{\rm
lcm}[\frac{t^{2n}-1}{t^{n}-1},\frac{t^{3n}-1}{t^{n}-1}]=\frac{(t^{n}+1)(t^{3n}-1)}{t^{n}-1}$
if $5|n$, since $t^{n}+1$ is not an LDS. One could however rewrite (15) as the
lcm of slightly simpler LDS’s.

##  5\. Vandermonde type determinants

We now introduce a way to study the structure of a linear division sequences.

######  Proposition 2.

If $(x_{n})_{n\geq 0}$ is a recurrence sequence of algebraic integers or
polynomials satisfying (1) then

$\gcd(x_{0},x_{n},\dots,x_{(k-1)n})\text{ divides
}\gcd(x_{0},\dots,x_{k-1})\prod_{j=1}^{m}(n\alpha_{j}^{n-1})^{\binom{k_{j}}{2}}\cdot\prod_{1\leq
i<j\leq
m}\bigg{(}\frac{\alpha_{i}^{n}-\alpha_{j}^{n}}{\alpha_{i}-\alpha_{j}}\bigg{)}^{k_{i}k_{j}}.$

We deduce that if $(u_{n})_{n\geq 0}$ is a linear division sequence with
$u_{1}=1$ then

$u_{n}\text{ divides
}\prod_{j=1}^{m}(n\alpha_{j}^{n-1})^{\binom{k_{j}}{2}}\cdot\prod_{1\leq
i<j\leq
m}\bigg{(}\frac{\alpha_{i}^{n}-\alpha_{j}^{n}}{\alpha_{i}-\alpha_{j}}\bigg{)}^{k_{i}k_{j}}$

by Proposition 2, which is the main theorem of Bézivin et al [5]. (Our proof
is a modification of Barbero [3], which is substantially easier than the proof
in [5].)

###  5.1. Beyond Vandermonde

We begin by reproving the main results from [13], arguably a little more
easily. Let $v(x)$ denote the column vector $(1,x,\ldots,x^{k-1})^{T}$ and so,
differentiating each entry,

$v^{(j)}(x)=\frac{1}{j!}\bigg{(}\frac{d}{dx}\bigg{)}^{j}v(x)=\bigg{(}0,0,\ldots,\binom{j}{j},\binom{j+1}{j}x\dots,\binom{k-1}{j}x^{k-1-j}\bigg{)}^{T}.$

######  Lemma 5.1.

Let $x_{1},\ldots,x_{m}$ be independent variables and $k_{1}+\cdots+k_{m}=k$.
Then the determinant of the $k$-by-$k$ matrix $M$ given by appending the
column vectors,

$M=\big{(}v^{(0)}(x_{1}),\ldots,v^{(k_{1}-1)}(x_{1}),\ldots,v^{(0)}(x_{m}),\ldots,v^{(k_{m}-1)}(x_{m})\big{)}$

equals

$\pm\prod_{1\leq i<j\leq m}(x_{i}-x_{j})^{k_{i}k_{j}}.$

###### Proof.

For independent variables $x_{i,j}$, we construct the Vandermonde matrix

$V:=(v(x_{1,0}),\ldots,v(x_{1,k_{1}-1}),\ldots,v(x_{m,0}),\ldots,v(x_{m,k_{m}-1})),$

so that $M=DV|_{\text{Each }x_{i,j}=x_{i}}$ where $D$ is the differential
operator

$\frac{1}{1!}\frac{d}{dx_{1,1}}\cdots\frac{1}{(k_{1}-1)!}\bigg{(}\frac{d}{dx_{1,k_{1}-1}}\bigg{)}^{k_{1}-1}\cdots\frac{1}{1!}\frac{d}{dx_{m,1}}\cdots\frac{1}{(k_{m}-1)!}\bigg{(}\frac{d}{dx_{m,k_{m}-1}}\bigg{)}^{k_{m}-1}.$

Since taking the determinant is a linear function in the entries of each
column vector,

$\det M=D\det V\bigg{|}_{\text{Each
}x_{i,j}=x_{i}}=D\prod_{\begin{subarray}{c}1\leq i\leq m\\\ 0\leq j\leq
k_{i}-1\\\
(i,j)\neq(i^{\prime},j^{\prime})\end{subarray}}(x_{i,j}-x_{i^{\prime},j^{\prime}})\bigg{|}_{\text{Each
}x_{i,j}=x_{i}}$

We work first with the $x_{1,j}$-variables, the others are analogous. Letting
$x_{1,0}=x_{1}$ our polynomial takes the form

$\pm\prod_{1\leq\ell\leq k_{1}-1}(x_{1,\ell}-x_{1})\cdot\prod_{1\leq\ell<j\leq
k_{1}-1}(x_{1,\ell}-x_{1,j})\cdot\prod_{0\leq\ell\leq
k_{1}-1}\prod_{\begin{subarray}{c}2\leq i\leq m\\\ 0\leq j\leq
k_{i}-1\end{subarray}}(x_{1,\ell}-x_{i,j})\cdot P(x_{i,j}:i\geq 2),$

where $P(x_{i,j}:i\geq 2)$ is a polynomial in the $x_{i,j}$ with $i\geq 2$.

For $\ell=1$ we have $(x_{1,1}-x_{1})$ together with a product of terms
$(x_{1,1}-x_{*,*})$. We differentiate wrt $x_{1,1}$ using the product rule and
then let $x_{1,1}=x_{1}$. Unless we have differentiated out the
$(x_{1,1}-x_{1})$-term then we get $0$ when we take $x_{1,1}=x_{1}$. Hence our
determinant becomes

$\pm\prod_{2\leq\ell\leq
k_{1}-1}(x_{1,\ell}-x_{1})^{2}\cdot\prod_{2\leq\ell<j\leq
k_{1}-1}(x_{1,\ell}-x_{1,j})\cdot\prod_{0\leq\ell\leq
k_{1}-1}\prod_{\begin{subarray}{c}2\leq i\leq m\\\ 0\leq j\leq
k_{i}-1\end{subarray}}(x_{1,\ell}-x_{i,j})\cdot P(x_{i,j}:i\geq 2)$

since $x_{1,\ell}-x_{1,1}=x_{1,\ell}-x_{1}$ for each $\ell\geq 2$. For
$\ell=2$ we differentiate twice wrt $x_{1,2}$ and then take $x_{1,2}=x_{1}$.
We see using the product rule that unless this is applied each time to
$(x_{1,2}-x_{1})^{2}$ we get $0$; therefore our determinant, now divided by
$2!$, becomes

$\pm\prod_{3\leq\ell\leq
k_{1}-1}(x_{1,\ell}-x_{1})^{3}\cdot\prod_{3\leq\ell<j\leq
k_{1}-1}(x_{1,\ell}-x_{1,j})\cdot\prod_{0\leq\ell\leq
k_{1}-1}\prod_{\begin{subarray}{c}2\leq i\leq m\\\ 0\leq j\leq
k_{i}-1\end{subarray}}(x_{1,\ell}-x_{i,j})\cdot P(x_{i,j}:i\geq 2)$

since $x_{1,\ell}-x_{1,2}=x_{1,\ell}-x_{1}$ for each $\ell\geq 3$. We now
proceed by induction on $\ell,1\leq\ell\leq k_{1}-1$ applying
$(\frac{d}{dx_{1,\ell}})^{\ell}$ and then letting $x_{1,\ell}=x_{1}$. When we
have finished differentiating with respect to our $x_{1,\ell}$ variables, we
end up with

$\pm\prod_{\begin{subarray}{c}2\leq i\leq m\\\ 0\leq j\leq
k_{i}-1\end{subarray}}(x_{1}-x_{i,j})^{k_{1}}\cdot P(x_{i,j}:i\geq 2)$

Repeating this argument with each variable we end up with the claimed result.
∎

Let

$v_{(j)}(x):=\frac{1}{j!}\bigg{(}x\frac{d}{dx}\bigg{)}^{j}v(x)=\frac{1}{j!}(0^{j},1^{j}x,2^{j}x^{2}\ldots,(k-1)^{j}x^{k-1})^{T}.$

######  Corollary 3.

Let $x_{1},\ldots,x_{m}$ be independent variables and $k_{1}+\cdots+k_{m}=k$.
Let $M_{k_{1},\dots,k_{m}}(x_{1},\dots,x_{m})$ be the $k$-by-$k$ matrix $M$
given by appending the column vectors.

$M_{k_{1},\dots,k_{m}}(x_{1},\dots,x_{m})=\bigg{(}v_{(0)}(x_{1}),\ldots,v_{(k_{1}-1)}(x_{1}),\ldots,v_{(0)}(x_{m}),\ldots,v_{(k_{m}-1)}(x_{m})\bigg{)}$

Then

$\det M_{k_{1},\dots,k_{m}}(x_{1},\dots,x_{m})=\pm\
x_{j}^{\binom{k_{j}}{2}}\cdot\prod_{1\leq i<j\leq
m}(x_{i}-x_{j})^{k_{i}k_{j}}.$

###### Proof.

One can show by induction that
$v_{(k)}(x)=\sum_{j=0}^{k}a_{k,j}x^{j}v^{(j)}(x)$ for some constants
$a_{k,j}$. For $k=0$ we have $a_{0,0}=1$. Otherwise

$\sum_{j=0}^{k}a_{k,j}x^{j}v^{(j)}(x)=v_{(k)}(x)=x\frac{d}{dx}v_{(k-1)}(x)=\sum_{j=0}^{k-1}a_{k-1,j}x\frac{d}{dx}(x^{j}v^{(j)}(x))$
$=\sum_{j=0}^{k-1}a_{k-1,j}(jx^{j}v^{(j)}(x))+x^{j+1}v^{(j+1)}(x))=\sum_{j=0}^{k}(ja_{k-1,j}+a_{k-1,j-1})x^{j}v^{(j)}(x)$

where $a_{k-1,k}=0$ and so $a_{k,j}=ja_{k-1,j}+a_{k-1,j-1}$ with each
$a_{k,k}=1$ by induction. Hence the matrix columns
$(v_{(0)}(x),\ldots,v_{(k-1)}(x))$ can be replaced, in calculating the
determinant, by $(v(x),xv^{(1)}(x),\ldots,x^{k-1}v^{(k-1)}(x))$, which equals
$x^{\binom{k}{2}}$ times the determinant which now has matrix columns
$(v(x),v^{(1)}(x),\ldots,v^{(k-1)}(x))$. The result follows from Lemma 1. ∎

###### Proof of Proposition 2.

Let $(u_{n}^{(\ell)})_{n\geq 0}$ for $\ell=0,1,\dots,k-1$ be the recurrence
sequences satisfying (1) with

$u_{r}^{(\ell)}=\delta_{\ell,r}\text{ (the Dirac delta function) for }0\leq
r\leq k-1.$

We are interested in the matrix

$U_{n}:=\begin{pmatrix}u_{0}^{(0)}&u_{0}^{(1)}&\dots&u_{0}^{(k-1)}\\\
u_{n}^{(0)}&u_{n}^{(1)}&\dots&u_{n}^{(k-1)}\\\ \dots&\dots&\dots&\dots\\\
u_{(k-1)n}^{(0)}&u_{(k-1)n}^{(1)}&\dots&u_{(k-1)n}^{(k-1)}\\\
\end{pmatrix}\,.$

If for convenience we write

$u_{r}^{(\ell)}=\sum_{i=1}^{m}\sum_{j=0}^{k_{i}-1}e_{i,j}^{(\ell)}\frac{r^{j}}{j!}\alpha_{i}^{r}.$

then $U_{n}=M_{k_{1},\dots,k_{m}}(\alpha_{1}^{n},\dots,\alpha_{m}^{n})\cdot
D_{n}\cdot E$ where

$E=\begin{pmatrix}e_{1,0}^{(0)}&e_{1,0}^{(1)}&\dots&e_{1,0}^{(k-1)}\\\
e_{1,1}^{(0)}&e_{1,1}^{(1)}&\dots&e_{1,1}^{(k-1)}\\\
\dots&\dots&\dots&\dots\\\
e_{m,k_{m}-1}^{(0)}&e_{m,k_{m}-1}^{(1)}&\dots&e_{m,k_{m}-1}^{(k-1)}\\\
\end{pmatrix}\text{ and }D_{n}=\begin{pmatrix}n^{0}&0&\dots&0\\\
0&n^{1}&\dots&0\\\ \dots&\dots&\dots&\dots\\\ 0&0&\dots&n^{k_{m}-1}\\\
\end{pmatrix}.$

Moreover $U_{1}$ is the identity matrix so that $\det U_{1}=1$ and therefore

$\det U_{n}=\frac{\det
M_{k_{1},\dots,k_{m}}(\alpha_{1}^{n},\dots,\alpha_{m}^{n})}{\det
M_{k_{1},\dots,k_{m}}(\alpha_{1},\dots,\alpha_{m})}=\prod_{j=1}^{m}(n\alpha_{j}^{n-1})^{\binom{k_{j}}{2}}\cdot\prod_{1\leq
i<j\leq
m}\bigg{(}\frac{\alpha_{i}^{n}-\alpha_{j}^{n}}{\alpha_{i}-\alpha_{j}}\bigg{)}^{k_{i}k_{j}}.$

by Corollary 3 (which is Theorem 1 of [3]).

Any recurrence sequence $(x_{n})_{n\geq 0}$ satisfying (1) can be written as

$x_{n}=\sum_{\ell=0}^{k-1}x_{\ell}u_{n}^{(\ell)}\text{ for all }n\geq 0.$

For a given integer $n$ let $G_{n}:=\gcd(x_{0},x_{n},\dots,x_{(k-1)n})$. Let
$X_{n,\ell}$ denote the matrix $U_{n}$ with the $\ell$th column replaced by
$(x_{0},x_{n},\dots,x_{(k-1)n})^{T}$, so that $G_{n}$ divides $\det
X_{n,\ell}$. We can compute this determinant by subtracting $x_{i}$ times
column $i$ from column $\ell$ for each $i\neq\ell$, which will leave
$x_{\ell}$ times the $\ell$th column of $U_{n}$. Therefore $\det
X_{n,\ell}=x_{\ell}\det U_{n}$ and so $G_{n}$ divides $x_{\ell}\det U_{n}$ for
$0\leq j\leq k-1$. Combining these we obtain

$\gcd(x_{0},x_{n},\dots,x_{(k-1)n})\text{ divides
}\gcd(x_{0},\dots,x_{k-1})\det U_{n}$

and the result follows. ∎

###  5.2. Zeros of $(u_{n})_{n\geq 0}$

We deduce an important Corollary in the algebra of linear recurrence
sequences.

######  Corollary 4.

Let $(u_{n})_{n\geq 0}$ be a linear recurrence sequence with period $M$. If
$u_{A+j\ell}=0$ for $j=0,\dots,k-1$ where $A\equiv a\pmod{M}$ with $1\leq
a\leq M$ and $M$ divides $\ell>0$ then $U_{a}(x,y_{1},\dots,y_{r})=0$.

###### Proof.

In the notation of section 3, let
$\delta_{i}=\gamma_{1}^{e_{i,1}}\cdots\gamma_{r}^{e_{i,r}}$ and
$h_{i}(x)=g_{i}(A+\ell x)\zeta_{M}^{e_{i,0}a}\delta_{i}^{A}$ for each $i$, so
that $\deg h_{i}=\deg g_{i}$. Then the values of
$\Delta_{i}:=\delta_{i}^{\ell}=\alpha_{i}^{\ell}$ are all distinct, and define

$x_{j}:=\sum_{i=1}^{m}h_{i}(x)\Delta_{i}^{j}\text{ for all }j\geq 0$

so that $x_{j}=u_{A+j\ell}$ by (11). By hypothesis we have $x_{j}=0$ for
$j=0,\dots,k-1$, which yields a system of $k$ linear equations in the $k$
coefficients of the $h_{i}$-polynomials. The corresponding matrix has non-zero
determinant by Corollary 3, and so the $h_{i}$-coefficients are all $0$,
implying the $g_{i}$-coefficients are all $0$, and therefore
$U_{a}(x,y_{1},\dots,y_{r})=0$. ∎

######  Corollary 5.

Let $(u_{n})_{n\geq 0}$ be a linear division sequence with $u_{m}=0$ for some
integer $m\geq 1$. Then there exist divisors $d_{1},\dots,d_{\ell}$ of $M$
such that $u_{n}=0$ if and only if $n$ is divisible by some $d_{i}$, and
$U_{a}(x,y_{1},\dots,y_{r})=0$ whenever some $d_{i}$ divides $a$.

###### Proof.

Let $d=(m,M)$ so there exists an integer $r$ which is divisible by $m$, with
$r\equiv d\pmod{M}$. Any integer $n\equiv r\pmod{[m,M]}$ is divisible by $m$
so that $u_{m}=0$ divides $u_{n}$ and therefore $u_{n}=0$. Therefore
$U_{d}(x,y_{1},\dots,y_{r})=0$ and so $u_{d}=0$ by Corollary 4. But then
$u_{n}=0$ whenever $d$ divides $n$, and if $d$ divides $a,1\leq a\leq M$ then
$u_{n}=0$ for all $n\equiv a\pmod{M}$ and so $U_{a}(x,y_{1},\dots,y_{r})=0$ by
Corollary 4. ∎

##  6\. Factorization Theorems

Suppose we are given representations for $u_{n},v_{n}$ and $w_{n}$ as in (11).
If $w_{n}=u_{n}v_{n}$ for all $n$ in some arithmetic progression of length
$k$, with each $n\equiv a\pmod{M}$ then (12) holds, by Corollary 4.

In particular if $u_{n}$ is a linear recurrence sequence for which $u_{n}$
divides $u_{qn}$ for all $n\geq 0$ for a given prime $q$, then we can write
$u_{qn}=u_{n}v_{n}$ where $(v_{n})_{n\geq 0}$ is also a linear recurrence
sequence, by the Hadamard quotient theorem, and therefore (12) holds with
$W_{a}(x,y_{1},\dots,y_{r})=U_{qa}(qx,y_{1}^{q},\dots,y_{r}^{q})$ (with
$U_{qa}=U_{b}$ where $b$ is the least positive residue of $qa\pmod{M}$), so
that

$U_{qa}(qx,y_{1}^{q},\dots,y_{r}^{q})=U_{a}(x,y_{1},\dots,y_{r})V_{a}(x,y_{1},\dots,y_{r}).$
(16)

The polynomial $U_{a}(x,y_{1},\dots,y_{r})$ therefore divides the polynomial
$U_{qa}(qx,y_{1}^{q},\dots,y_{r}^{q})$. One might guess this can only happen
if these polynomials have a particular special shape.

###  6.1. Factorizations

Our goal is to understand the factorization of $U_{a}(x,y_{1},\dots,y_{r})$
and then $U_{a}(x,y_{1}^{m},\dots,y_{r}^{m})$ for all $m\geq 1$, given (16).
We partly develop a theory that culminated in the 1935 paper by MacColl [32]
(following the papers of Ritt [36] in 1927 and Gourin [15] in 1930).131313They
studied “exponential polynomials” by developing a version of Lemma 6.1 for
$f(x,y_{1}^{m_{1}},\dots,y_{r}^{m_{r}})$ but here we only need the exponents
to be equal.

To begin with we can divide $U_{a}(x,y_{1},\dots,y_{r})$ by the monomial
$x^{e_{0}}y_{1}^{e_{1}}\cdots y_{r}^{e_{r}}$ (as above), leaving a polynomial
with a constant term in each variable. Next we have _binomial factors_ which
are irreducible polynomials of the form

$B(x,y_{1},\dots,y_{r}):=x^{a_{0}}y_{1}^{a_{1}}\cdots
y_{r}^{a_{r}}-cx^{b_{0}}y_{1}^{b_{1}}\cdots y_{r}^{b_{r}}$

where $\min\\{a_{i},b_{i}\\}=0$ for each $i$. If $a_{0}=b_{0}=0$ then we can
always factor

$B(x,y_{1}^{m},\dots,y_{r}^{m})=\prod_{j=0}^{m-1}(y_{1}^{a_{1}}\cdots
y_{r}^{a_{r}}-\zeta_{m}^{j}c^{1/m}y_{1}^{b_{1}}\cdots y_{r}^{b_{r}})$

as a product of binomial factors. If say $a_{0}>b_{0}=0$ then we get a
factorization if and only if $m$ divides $a_{0}$, again into binomial factors
(and an analogous result if $b_{0}>a_{0}=0$). Finally we have _multinomial
factors_ which are irreducible polynomials containing at least three
monomials. One can show [32] that for any irreducible multinomial
$f(x,y_{1},\dots,y_{r})$, each $f(x,y_{1}^{m},\dots,y_{r}^{m})$ factors into
irreducible multinomial factors, no binomial factors.

If
$f(x,y_{1}^{m},\dots,y_{r}^{m})=g(x,y_{1},\dots,y_{r})h(x,y_{1},\dots,y_{r})$
then we can also write
$f(x,y_{1}^{mk},\dots,y_{r}^{mk})=g(x,y_{1}^{k},\dots,y_{r}^{k})h(x,y_{1}^{k},\dots,y_{r}^{k})$
for all $k\geq 2$, which we call an _old factorization_. A factorization that
is not old is a _new factorization_. The key to our results is given by the
following:

######  Lemma 6.1 (Ritt-Gourin-MacColl).

If $f(x,y_{1},\dots,y_{r})\in\mathbb{C}[x,y_{1},\dots,y_{r}]$ is an
irreducible multinomial then there are only finitely many integers $m$ for
which $f(x,y_{1}^{m},\dots,y_{r}^{m})$ has a new factorization.

######  Corollary 6.

Suppose that each irreducible factor of
$f(x,y_{1},\dots,y_{r})\in\mathbb{C}[x,y_{1},\dots,y_{r}]$ is a multinomial
factor. There exists an integer $N=N_{f}$ such that if
$g(x,y_{1},\dots,y_{r})$ is an irreducible factor of
$f(x,y_{1}^{N},\dots,y_{r}^{N})$ then $g(x,y_{1}^{k},\dots,y_{r}^{k})$ is
irreducible for every integer $k\geq 1$.

###### Proof.

Let $\mathcal{M}(f)$ be the set of integers $m>1$ for which there is a new
factorization of $f(x,y_{1}^{m},\dots,y_{r}^{m})$, so that $\mathcal{M}(f)$ is
finite by Lemma 6.1. Let $N=\text{\rm lcm}[m:m\in\mathcal{M}(f)]$. The result
follows from Lemma 6.1. ∎

######  Proposition 3.

Let $q$ be a prime with $q\nmid M$. Suppose that $(u_{n})_{n\geq 0}$ is a
linear recurrence sequence in the integers with period $M$, for which $u_{n}$
divides $u_{qn}$ for every integer $n\geq 1$. Then the polynomials
$U_{a}(x,y_{1},\dots,y_{r})$, as defined above, are each either $0$ or a
monomial times a product of binomials none of which contain the variable $x$.

###### Proof.

Let $k$ be the order of $q$ mod $M$ so that $q^{k}a\equiv a\pmod{M}$ for any
$a\pmod{M}$. Therefore iterating (16) $k$ times, we obtain

$U_{a}(x,y_{1},\dots,y_{r})\text{ divides
}U_{a}(Qx,y_{1}^{Q},\dots,y_{r}^{Q})$

where $Q=q^{k}$. Let $f(x,y_{1},\dots,y_{r})$ be the product of the
multinomial irreducible factors of $U_{a}(x,y_{1},\dots,y_{r})$ so that
$f(x,y_{1},\dots,y_{r})$ divides $f(Qx,y_{1}^{Q},\dots,y_{r}^{Q})$. By
Corollary 6 the polynomials $f(x,y_{1}^{N},\dots,y_{r}^{N})$ and
$f(X,y_{1}^{QN},\dots,y_{r}^{QN})$ have the same number of irreducible
factors. However since the first divides the second (with $X=Qx$), these
irreducible factors must be the same, and so these polynomials must be equal,
and have the same degree. However this is impossible unless the degree in each
$y_{i}$ is $0$; in other words, $f(x,y_{1},\dots,y_{r})$ is a polynomial in
$x$ only, which is not a multinomial. Therefore $U_{a}$ is a monomial times a
product of binomials.

Every binomial involving $x$ takes the form $x^{a_{0}}y_{1}^{a_{1}}\cdots
y_{s}^{a_{s}}-cy_{s+1}^{a_{s+1}}\cdots y_{r}^{a_{r}}$. Let $N$ be the lcm of
the $a_{0}$ from all such factors. Substituting in $y_{i}^{N}$ for $y_{i}$ and
factoring leaves only binomial factors of the form $xy_{1}^{b_{1}}\cdots
y_{s}^{b_{s}}-Cy_{s+1}^{b_{s+1}}\cdots y_{r}^{b_{r}}$, which are all
irreducible. Let $h(x,y_{1},\dots,y_{r})$ be the product of these binomials.
Then $h(x,y_{1},\dots,y_{r})$ divides $h(Qx,y_{1}^{Q},\dots,y_{r}^{Q})$ but
again both polynomials have the same number of irreducible factors so must be
equal, that is of the same degree, again implying that the degree in each
$y_{i}$ is $0$. Therefore each $h$ is a polynomial in $x$ only such that
$h(x)$ divides $h(Qx)$. But if $\rho$ is the root of largest absolute value of
$h(x)$ then $h(Q\rho)=0$ and so $\rho=0$, that is $h(x)$ must be a constant
times a power of $x$, so must equal $1$ as this is not a binomial. ∎

We now present a different way to reach the same conclusion, which will help
in the proof of Theorem 3.

Proposition 3 revisited _Suppose that $(u_{n})_{n\geq 0}$ is a linear
recurrence sequence in the integers with period $M$, for which $u_{n}$ divides
$u_{jn}$ for $1\leq j<k$. Then the polynomials $U_{a}(x,y_{1},\dots,y_{r})$,
as defined above, are each either $0$ or a monomial times a product of
binomials none of which contain the variable $x$._

###### Proof.

Proposition 2 implies the result of Bézivin, Pethő and van der Poorten [5]:

$u_{n}\text{ divides
}\prod_{j=1}^{m}(n\alpha_{j}^{n-1})^{\binom{k_{j}}{2}}\cdot\prod_{1\leq
i<j\leq
m}\bigg{(}\frac{\alpha_{i}^{n}-\alpha_{j}^{n}}{\alpha_{i}-\alpha_{j}}\bigg{)}^{k_{i}k_{j}}.$

The right-hand side is also a linear recurrence sequence and so, in the
discussion and notation of section 3,

$U_{a}(x,y_{1},\dots,y_{r})\text{ divides }x^{e_{0}}y_{1}^{e_{1}}\cdots
y_{r}^{e_{r}}\prod_{1\leq i<j\leq m}(\zeta_{M}^{e_{i,0}a}y_{1}^{e_{i,1}}\cdots
y_{r}^{e_{i,r}}-\zeta_{M}^{e_{j,0}a}y_{1}^{e_{j,1}}\cdots
y_{r}^{e_{j,r}})^{k_{i}k_{j}}.$

The right-hand side is a product of monomials and binomials and only factors
into monomials and binomials as we saw there, and therefore
$U_{a}(x,y_{1},\dots,y_{r})$ factors into monomials and binomials. ∎

In the original Proposition 3 the binomials in $U_{a}$ are shown to be of the
form $\gamma^{n}-1$ where $\gamma$ can be expressed as a product of
$\alpha_{i}$’s to integer powers so that each $\gamma\in K$. In the modified
Proposition 3 the binomials in $U_{a}$ come from binomials that divide some
$\alpha_{i}^{n}-\alpha_{j}^{n}$; that is, there exist some $i\neq j$ and
integer $r$ for which $\alpha_{i}=\gamma^{r}\alpha_{j}$.

###  6.2. The shape of a linear division sequence

Let $K=\mathbb{Q}(\alpha_{1},\dots,\alpha_{m})$, let $A$ be the ring of
integers of $K$.

######  Corollary 7.

If $(u_{n})_{n\geq 0}$ is a linear division sequence in the integers with
associated period $M\geq 1$ then

$u_{n}=\kappa_{a}n^{\epsilon_{a}}\lambda_{a}^{n-1}\prod_{j=1}^{\ell}v_{j,n}(\nu_{j},\delta_{j})\text{
whenever }n\equiv a\pmod{M}\text{ for }1\leq a\leq M.$ (17)

where the $\kappa_{a}\in K$ and the $\epsilon_{a}\in\mathbb{Z}^{+}$,

  * •

The $\lambda_{a}\in K$ are products of the $\alpha_{i}$’s to integer powers;

  * •

The $\nu_{j},\delta_{j}\in A$ are products of the $\alpha_{i}$’s to positive
integer powers;

  * •

The $\nu_{j}/\delta_{j}$ are pairwise multiplicatively independent;

  * •

The $(v_{j,n}(x,y))_{n\geq 0}$ are multiplicatively-dependent linear division
sequences in $A[x,y]^{\text{homogenous}}$, monic in $x$, with $v_{j,1}(t)=1$.

It could be that $\kappa_{a}=0$ for some $a$. If so then there exist divisors
$d_{1},\dots,d_{\ell}$ of $M$ such that $\kappa_{a}=0$ if and only if $a$ is
divisible by some $d_{i}$, by Corollary 5.

###### Proof.

Proposition 3 implies that we can write

$U_{a}(x,y_{1},\dots,y_{r})=\kappa_{a}^{\prime}x^{e_{a,0}}y_{1}^{e_{a,1}}\cdots
y_{r}^{e_{a,r}}\prod_{i=1}^{I}B_{i}(y_{1},\dots,y_{r})$

where $B_{i}(y_{1},\dots,y_{r}):=z_{i}-c_{i}$ with $c_{i}\in\mathbb{C}^{*}$
and each $z_{i}=y_{1}^{z_{i,1}}\cdots y_{r}^{z_{i,r}}$ for some
$z_{i,j}\in\mathbb{Z}$. Now if $B_{i}(z_{i})$ divides $B_{j}(z_{j}^{k})$ then
$z_{i}$ and $z_{j}$ must be multiplicatively dependent, and so since the
$y_{j}$ are multiplicatively independent, the exponent vectors
$(z_{i,1},\dots,z_{i,r})$ and $(z_{j,1},\dots,z_{j,r})$ must be linearly
dependent. Since these are integer vectors they must each be an integer
multiple of some integer vector. Therefore there exist $w_{1},\dots,w_{\ell}$
which are pairwise multiplicatively independent such that each $z_{i}$ equals
$w_{j}^{b_{j}}$ for some $j$ and for some integer $b_{j}$ (and so each
$w_{j}=y_{1}^{w_{i,1}}\cdots y_{r}^{w_{i,r}}$ where each
$w_{i,j}\in\mathbb{Z}$). We can then write each

$U_{a}(x,y_{1},\dots,y_{r})=\kappa_{a}^{\prime}x^{e_{a,0}}y_{1}^{e_{a,1}}\cdots
y_{r}^{e_{a,r}}\prod_{j=1}^{\ell}P_{a,j}(w_{j})$

where $P_{a,j}$ is a monic polynomial (as it is a product of factors of the
form $w_{j}^{b_{j}}-c_{i}$).

Let
$\eta_{j}=w_{j}(\gamma_{1},\dots,\gamma_{r})=\gamma_{1}^{w_{i,1}}\cdots\gamma_{r}^{w_{i,r}}$
so that for $\epsilon_{a}=e_{a,0}$

$u_{n}=U_{a}(n,\gamma_{1}^{n},\dots,\gamma_{r}^{n})=\kappa_{a}^{\prime}n^{\epsilon_{a}}(\gamma_{1}^{e_{a,1}}\cdots\gamma_{r}^{e_{a,r}})^{n}\prod_{j=1}^{\ell}P_{a,j}(\eta_{j}^{n}).$

$P_{a,i}(w_{i})$ divides $x^{he_{a,0}}y_{1}^{he_{a,1}}\cdots
y_{r}^{he_{a,r}}\prod_{j=1}^{\ell}P_{ha,j}(w_{j}^{h})$ for any $h\geq 1$ and
each $a\in\\{1,\dots,M\\}$. Writing these polynomials as products of binomial
factors, we see that each $w_{i}-c$ can only divide $P_{ha,i}(w_{i}^{h})$ and
so $P_{a,i}(w_{i})$ divides $P_{ha,i}(w_{i}^{h})$. Hence if we define
$v_{j,n}(t):=P_{a,j}(t^{n})/P_{1,j}(t)$ whenever $n\equiv a\pmod{M}$ then
$(v_{j,n}(t))_{n\geq 0}$ is a multiplicatively dependent linear division
sequence in $\mathbb{C}[t]$ with $v_{j,1}(t)=1$. Therefore

$u_{n}=\kappa_{a}^{\prime\prime}n^{\epsilon_{a}}(\gamma_{1}^{e_{a,1}}\cdots\gamma_{r}^{e_{a,r}})^{n}\prod_{j=1}^{\ell}v_{j,n}(\eta_{j})\text{
whenever }n\equiv a\pmod{M}\text{ for }1\leq a\leq M,$

with
$\kappa_{a}^{\prime\prime}=\kappa_{a}^{\prime}\prod_{j=1}^{\ell}P_{1,j}(\eta_{j})$.

The expression for each $\eta_{j}$ is a product of $\gamma_{i}$’s to integer
powers, which equals a product of $\alpha_{i}$’s to integer powers. Therefore
we can write $\eta_{j}=\nu_{j}/\delta_{j}$ where $\nu_{j}$ and $\delta_{j}$
are each the product of $\alpha_{i}$’s to non-negative integer powers, and
with no $\alpha_{i}$ in common. If $P_{a,j}$ has degree $d$ ($=d_{a,j}$) then
homogenize so that $P_{a,j}(x,y)=y^{d}P_{a,j}(x/y)$ and therefore
$P_{a,j}(\eta_{j}^{n})=\delta_{j}^{-dn}P_{a,j}(\nu_{j}^{n},\delta_{j}^{n})$.
Writing $v_{j,n}(x,y)=y^{dn}v_{j,n}(x/y),\
\kappa_{a}=\kappa_{a}^{\prime\prime}\lambda_{a}$ and
$\lambda_{a}:=\gamma_{1}^{e_{a,1}}\cdots\gamma_{r}^{e_{a,r}}\prod_{j}\delta_{j}^{-d_{a,j}}$
we obtain the claimed result. ∎

This same proof, with suitable modifications, works more easily for LDS’s in
$\mathbb{C}[t]$. To “complete” Theorem 5 the only part of Corollary 7 that we
need is that any LDS is a power LDS times a simple LDS, and so we deduce the
full classification of LDS’s in $\mathbb{C}[t]$:

######  Corollary 8.

$(u_{n}(t))_{n\geq 0}$ is a LDS in $\mathbb{C}[t]$ for which all of the roots
of the characteristic polynomial are multiplicatively dependent on $t$ if and
only if it is the product of a power LDS and a periodic LDS, an exponential
LDS (in powers of $t$) and some LDS $(v_{n}(t))_{n\geq 0}$ as in (15), each in
$\mathbb{C}[t]$.

##  7\. Proof of Theorem 1

The left-hand side of (17), $u_{n}$, is an integer whereas the right-hand side
is a product of numbers in $K$, so we need to better understand this equality,
and by studying each of the terms on the right-have side of (17), we will
deduce Theorem 1.

###  7.1. Proof of Theorem 1: I. Polynomially generated LDS’s

###### Proof that $\prod_{j=1}^{\ell}v_{j,n}(\nu_{j},\delta_{j})$ is a product
of polynomially generated LDS’s in $\mathbb{Z}$.

Let $G:=\text{Gal}(K/\mathbb{Q})$. The ideals $(\nu_{j},\delta_{j})$ are not
necessarily principal so we cannot just divide them out from $\nu_{j}$ and
$\delta_{j}$ like we do in the integer case. However if $I$ is a minimal
representative of the ideal class of $(\nu_{j},\delta_{j})$ in the class group
of $K/\mathbb{Q}$, and $I^{c}$ is a (minimal) representative of the inverse so
that $I\cdot I^{c}=(g)$ and $(\nu_{j},\delta_{j})\cdot I^{c}=(h)$ for some
$g,h\in A$, then $(\frac{g}{h}\cdot\nu_{j},\frac{g}{h}\cdot\delta_{j})=I$. We
therefore adjust the $\nu_{j},\delta_{j}$ in (17) accordingly, which will also
lead to us adjusting each $\lambda_{a}$. We will need that if $I$ is the
representative of the ideal class of $(\nu_{j},\delta_{j})$ then $I^{\sigma}$
is the representative of the ideal class of
$(\nu_{j}^{\sigma},\delta_{j}^{\sigma})$ for each $\sigma\in G$.

Let $L=\mathbb{Q}(\nu_{i},\delta_{i})$ and then $H$ be a set of
representatives of

$\text{Aut}(L)/\text{Stab}(\\{v_{i,n}(\nu_{i},\delta_{i}):n\geq 1\\}).$

For each $\sigma\in H$ we see that

$\sigma(v_{i,n}(\nu_{i},\delta_{i}))\text{ divides
}\sigma(u_{n})=u_{n}=\kappa_{a}n^{\epsilon_{a}}\lambda_{a}^{n}\prod_{j=1}^{\ell}v_{j,n}(\nu_{j},\delta_{j}),$

Now $\sigma(v_{i,n}(\nu_{i},\delta_{i}))$ is the homogenous polynomial
$\sigma(v_{i,n}(x,y))$ evaluated at $x=\nu_{i}^{\sigma},y=\delta_{i}^{\sigma}$
and so $\nu_{i}^{\sigma}/\delta_{i}^{\sigma}$ must equal some
$\nu_{j}/\delta_{j}$, and by our choices of gcd in the previous paragraph, we
see that
$(\nu_{i},\delta_{i})^{\sigma}=(\nu_{i}^{\sigma},\delta_{i}^{\sigma})$.
Therefore $\sigma(v_{n}(\nu_{i},\delta_{i}))$ divides
$v_{j,n}(\nu_{j},\delta_{j})=\sigma(v_{i,n})(\nu_{i}^{\sigma},\delta_{i}^{\sigma})$.
Therefore the product on the right-hand side of (17) can be partitioned into
subproducts of the form

$\prod_{\sigma\in H}\sigma(v_{i,n})(\nu^{\sigma},\delta^{\sigma}).$

(We remark that each $\sigma(v_{i,1})(x,y)=1$ by Corollary 7.) We chose $H$ to
be a minimal set of automorphisms for which this product is stable under the
action of $G$; moreover, it is a product of elements of $A$ and stable under
Galois so it is an integer.

Now each $(\nu^{\sigma},\delta^{\sigma})=I^{\sigma}$ so we can certainly
divide through by $q^{\deg v_{i,n}}$ where the positive integer $q$ is
obtained from the integer ideal $(q)=\prod_{\sigma\in H}I^{\sigma}$, adjusting
the value of $\lambda_{a}$ accordingly. We therefore obtain a polynomially
generated LDS in $\mathbb{Z}$. ∎

###  7.2. Sorting out some details

We can now rewrite Corollary 7 as

$u_{n}=\kappa_{a}n^{\epsilon_{a}}\lambda_{a}^{n-1}\prod_{j=1}^{J}u_{j,n}\text{
whenever }n\equiv a\pmod{M}\text{ for }1\leq a\leq M,$ (18)

where each $(u_{j,n})_{n\geq 0}$ is a polynomially generated LDS in
$\mathbb{Z}$, the $\epsilon_{a}\in\mathbb{Z}^{+}$ and the
$\kappa_{a},\lambda_{a}\in K$ (though not with the same values as in Corollary
7).

Since each $u_{n},u_{j,n}\in\mathbb{Z}$ we deduce that each
$\kappa_{a}\lambda_{a}^{n-1}\in\mathbb{Q}$. Therefore
$\tau_{a}:=\lambda_{a}^{M}=(\kappa_{a}\lambda_{a}^{a+M-1})/(\kappa_{a}\lambda_{a}^{a-1})\in\mathbb{Q}$,
and so taking $\kappa_{a}^{\prime}=\kappa_{a}\lambda_{a}^{a-1}\in\mathbb{Q}$
we deduce that

$u_{n}=\kappa_{a}^{\prime}n^{\epsilon_{a}}\tau_{a}^{k}\prod_{j=1}^{J}u_{j,n}\text{
writing }n=a+kM\text{ for }1\leq a\leq M,k\geq 0,$ (19)

with the $\kappa_{a}^{\prime},\tau_{a}\in\mathbb{Q}$.

Next we need the following lemma which we will prove in section 7.5:

######  Lemma 7.1.

Let $(u_{n})_{n\geq 0}$ be a polynomially generated LDS in $\mathbb{Z}$.

  1. (a)

For any prime $p$ there exist constants $a_{p},b_{p}$ such that
$v_{p}(u_{n})\leq a_{p}+b_{p}v_{p}(n)$. In particular $v_{p}(u_{n})\ll_{p}\log
2n$.

  2. (b)

There exists a constant $C=C((u_{n})_{n\geq 0})$ such that if $p$ divides $n$
then $p^{v_{p}(u_{n})}\ll(pe^{n/p})^{C}$.

  3. (c)

There exists a finite set of integers $n_{1},\dots,n_{k}>1$ such that if
$p|u_{n}$ then some $n_{i}$ divides $n$. Moreover if $p|u_{np}$ then $p$
divides both $u_{n}$ and $u_{np}/u_{n}$.

This implies that each $\tau_{a}\in\mathbb{Z}$ for if prime $p$ divides the
denominator of $\tau_{a}$ then $v_{p}(\tau_{a}^{k})\leq-k$ whereas for
$n=a+kM$ we have
$v_{p}(\kappa_{a}^{\prime}n^{\epsilon_{a}}\prod_{j=1}^{J}u_{j,n})\ll\log 2k$
by Lemma 7.1(a) and so $v_{p}(u_{n})<0$ if $n$ is large and $\equiv
a\pmod{M}$, contradicting that $u_{n}\in\mathbb{Z}$.

Now for each prime $p$ which divides some $\tau_{a}$, let
$h_{a}=v_{p}(\tau_{a})$. Therefore $v_{p}(u_{a+kM})=kh_{a}+O(\log k)$. If
$b\equiv ra\pmod{M}$ with $1\leq a,b,r\leq M$ then $u_{a+kM}$ divides
$u_{ra+rkM}=u_{b+\ell M}$ where $\ell=rk+[\frac{ra}{m}]$, and so

$kh_{a}+O(\log k)=v_{p}(u_{a+kM})\leq v_{p}(u_{b+\ell M})=\ell
h_{b}+O(\log\ell)$

and so $kh_{a}\leq rkh_{b}+O(\log k)$ which implies that $h_{a}\leq rh_{b}$
letting $k\to\infty$. This is therefore a specialization of an exponential LDS
in $\mathbb{C}[t]$, and so $(\tau_{a}^{k})_{n=a+kM\geq 0}$ is an exponential
LDS in $\mathbb{Z}$.

To appreciate the $\epsilon_{a}$-values, let $p$ be a prime that does not
divide the numerator or denominator of any non-zero $\kappa_{a}^{\prime}$ or
$\tau_{a}$. Fix $a$ and $r$ with $b\equiv ra\pmod{M}$ and assume also $p\nmid
ar\prod_{j=1}^{J}u_{j,a}u_{j,ra}$ and so $p$ does not then divide
$\prod_{j=1}^{J}u_{j,ap}u_{j,rap}$ by Proposition 4(c).

Now $u_{ap}$ divides $u_{arp}$ and so $\epsilon_{a}=v_{p}(u_{ap})\leq
v_{p}(u_{arp})=\epsilon_{b}$, looking at the exponent of $p$. Now if $(a,M)=d$
then $\epsilon_{d}\leq\epsilon_{a}$ writing $a=Ad$, and as $d\equiv
ra\pmod{M}$ for some $r$, we also have $\epsilon_{a}\leq\epsilon_{d}$.
Therefore $\epsilon_{a}=\epsilon_{d}$ where $d=(a,M)$. We also note that if
$D=dr|M$ then $\epsilon_{d}\leq\epsilon_{D}$. Letting
$\kappa_{a}=d^{\epsilon_{d}}\kappa_{a}^{\prime}$, so
$\kappa_{a}^{\prime}n^{\epsilon_{a}}=\kappa_{a}(n/d)^{\epsilon_{d}}$, the
$\kappa_{a}$ form a periodic sequence of rationals, and the
$(n/d)^{\epsilon_{d}}$ are a power LDS.

This completes the proof of Theorem 1. ∎

###  7.3. Proof of Corollaries 1 and 2

###### Proof of Corollary 1.

Suppose that $(u_{n})_{n\geq 0}$ has period $M$. By Theorem 1

$u_{n}=\kappa_{1}n^{e}\lambda^{n-1}\prod_{j}u_{j,n}\text{ for all }n\equiv
1\pmod{M}$

where $e=e_{1}$ and $\lambda^{M}\in\mathbb{Z}$, and each
$u_{i,n}=(w_{i,n}(\gamma_{i}))^{*}$ with $w_{i,n}(t)=f_{n}(t)/f_{1}(t)$ for
some $f_{n}(t)$ as in (9). Moreover each of the factors in (9) appears in the
construction of $w_{i,n}(t)$ in every arithmetic progression mod $M$.
Multiplying the expression in (9) out gives an expression for $u_{n}$ of the
form

$u_{n}=n^{e}\sum_{i=1}^{m}g_{i}\zeta_{M}^{e_{i}n}\delta_{i}^{n}$

with $e_{i}\in\mathbb{Z}$ for every $n\equiv 1\pmod{M}$. Now $(u_{n})_{n\geq
0}$ is non-degenerate so each term in this sum appears in the expression for
$u_{n}$ for all $n$, never getting cancelled by another term. Therefore every
$u_{n}$ can be given by the same expression as for $n\equiv 1\pmod{M}$, and
the result follows, since $u_{1}=1$. ∎

We would like to know when expressions like (9), multiplied out, are non-
degenerate, as well as their products when $t$ is replaced by $\gamma_{i}$. In
particular we would like to simplify the result in Corollary 1 if possible.
However, for any integer $M$ and $a(x)\in\mathbb{Z}[x]$, when we multiply out

$\prod_{\begin{subarray}{c}1\leq j\leq M\\\
(j,M)=1\end{subarray}}((\zeta_{M}^{j}a(\zeta_{M}^{j}))^{n}-1)(a(\zeta_{M}^{j})^{2n}-1)$

there are typically no cancelations and so it seems unlikely that one can
easily obtain a simpler answer than we have given. For example, for $M=3$ and
$\alpha\in\mathbb{Z}[\omega]$,

$((\omega\alpha)^{n}-1)((\overline{\omega\alpha})^{n}-1)(\alpha^{2n}-1)(\overline{\alpha}^{2n}-1)$

is non-degenerate and has 16 distinct terms, as long as
$\overline{\alpha}/\alpha$ is not a root of unity.141414If
$\overline{\alpha}/\alpha$ is a root of unity then $\alpha=r\zeta$ or
$r\zeta\sqrt{-3}$ where $r\in\mathbb{Z}$ and $\zeta\in\\{\pm
1,\pm\omega,\pm\overline{\omega})$.

###### Proof of Corollary 2.

Theorem 1 shows what LDS’s in $\mathbb{Z}$ look like. Moreover we can only
have $\limsup_{n\to\infty:\ u_{n}\neq 0}v_{p}(u_{n})/n=0$ for every prime $p$
if each $\tau_{a}=1$, by Lemma 7.1(a). Therefore for $n\equiv a\pmod{M}$ with
$(a,M)=d$ we have

$u_{n}=\kappa_{a}(n/d)^{\epsilon_{d}}\prod_{j=1}^{J}u_{j,n}$ (20)

the product of a periodic sequence of rationals $\kappa_{a}$, a power LDS, and
a finite number of polynomially generated LDS’s. Now $u_{d}=\kappa_{d}$
whenever $d$ divides $M$. Hence if $d$ divides $M$ then
$\kappa_{d}\in\mathbb{Z}$ and $\kappa_{d}$ divides $\kappa_{D}$ if $d|D|M$.

If prime $p$ divides the denominator of some $\kappa_{a}$ then $p$ divides
$(n/d)^{\epsilon_{d}}\prod_{j=1}^{J}u_{j,n}$ whenever $n\equiv a\pmod{M}$,
which happens only if each such $n$ is divisible by at least one of
$n_{1},\dots,n_{k}>1$ (this list should include $p$ for divisibility of $n/d$)
by the last part of Lemma 7.1(c). However one can construct an integer
$n\equiv a\pmod{M}$ that is not divisible by any element of the list except
divisors of $d=(a,M)$. Therefore $\kappa_{a}\in\mathbb{Z}$ if $(a,M)=1$. For
other $d$ note that $(u_{rd}/u_{d})_{r\geq 0}$ is a LDS of period $M/d$ and so
the constant $\kappa^{\prime}_{a/d}$ ($=\kappa_{a}/\kappa_{d}$)
$\in\mathbb{Z}$ and then $\kappa_{a}\in\mathbb{Z}$ and is divisible by
$\kappa_{d}$.

Now suppose that $d=(a,M)\equiv ar\pmod{M}$ for some integer $r\pmod{M/d}$.
Therefore if $R\equiv r\pmod{M/d}$ then $u_{a}$ divides $u_{Ra}$ which implies
that

$\kappa_{a}\text{ divides }\kappa_{d}R^{\epsilon_{d}}v_{R},\text{ where
}v_{R}:=\prod_{j=1}^{J}\frac{u_{j,Ra}}{u_{j,a}}$

is a polynomially generated LDS. Suppose that prime $p$ divides $\kappa_{a}$.
There exists an integer $L$ (the product of the $n_{i}$’s in Lemma 7.1)(c)
such that if $(R,L)=1$ then $p\nmid v_{R}$ by Lemma 7.1(c). Therefore we
select an integer $R$ for which $(R,pL)=1$ and $R\equiv r\pmod{M/d}$, which is
possible as $(r,M/d)=1$, and we deduce that $p\nmid R^{\epsilon_{d}}v_{R}$.
Therefore $\kappa_{a}$ divides $\kappa_{d}$. We conclude that
$(\kappa_{a})_{a\geq 0}$ is a periodic LDS. ∎

###  7.4. Determining the “factors” (of Theorem 1) of a given LDS

Given a LDS $(u_{n})_{n\geq 0}$ in the form (2) we first determine its period
and then create an explicit formula for $u_{n}$ in each arithmetic progression
mod $M$ which takes account of any cancelation of terms in (2) for that
progression. We can then easily determine the periodic LDS (from the
$u_{d}$-values for $d|M$), the power LDS (from the largest power of $n$ in the
explicit formula dividing each term when $(n,d)=M$), and the exponential LDS
(from the gcd of the uncanceled $\alpha_{i}$’s). We are left with a LDS
$(v_{n})_{n\geq 0}$ which is the product of polynomially generated LDS’s and
so the $g_{i}$’s in the formula (2) for $v_{n}$ are all constants.

Each of these polynomially generated LDS’s comes from taking the lcm of
factors of the form $(\eta^{n}-1)^{*}$. To complete our understanding we want
to determine these $\eta$-values (and the powers to which they appear) from
the formula (2) assuming $(u_{n})_{n\geq 0}$ is a polynomially generated LDS.
(We replace $v_{n}$ by $u_{n}$ for notational convenience.)

If $\mathcal{I}\in\mathcal{I}^{*}$ then there exists an algebraic number
$\eta_{\mathcal{I}}$ such that

$\alpha_{i}=\zeta_{M}^{a_{i}}\alpha_{j}\eta_{I}^{r_{i}}\text{ for each }i\in
I_{j},i\neq j,1\leq j\leq h$

where the $a_{i},r_{i}\in\mathbb{Z}$ with $\gcd_{i}r_{i}=1$ and some $a_{i}=0$
(by Lemma 10.1). Select $d_{\mathcal{I}}$ to be the smallest positive integer
for which each $\zeta_{M}^{a_{i}d_{\mathcal{I}}}=1$ so that if
$d_{\mathcal{I}}$ divides $n$ then

$\gcd((\alpha_{i}/\alpha_{j})^{n}-1:i\in I_{j},i\neq j,1\leq j\leq
h)^{*}=(\eta_{\mathcal{I}}^{n}-1)^{*}$

by Corollary 11. In this case we have

$u_{n}=\sum_{j=1}^{h}\alpha_{j}^{n}f_{I,j}(\eta_{\mathcal{I}}^{n})\text{ where
}f_{I,j}(t):=\sum_{i\in I_{j}}g_{i}t^{r_{i}}\in K[t]$

with $f_{I,j}(1)=g_{I_{j}}=0$. Let $e_{\mathcal{I}}\geq 1$ be the largest
integer for which

$(t-1)^{e_{\mathcal{I}}}\text{ divides }f_{I,j}(t)\text{ for }1\leq j\leq h,$

so that if $d_{\mathcal{I}}$ divides $n$ then
$(\eta_{\mathcal{I}}^{n}-1)^{e_{\mathcal{I}}}$ divides $u_{n}$.

Partition the set $\mathcal{I}^{*}$ into subsets $S_{1}\cup\cdots\cup
S_{\ell}$ where the $\eta_{\mathcal{I}},\mathcal{I}\in S_{j}$ are
multiplicatively dependent (and independent of the
$\eta_{{\mathcal{I}}^{\prime}}$ for all ${\mathcal{I}}^{\prime}\not\in
S_{j}$). Therefore there exists an algebraic integer $\eta_{j}$ such that
$\eta_{\mathcal{I}}=\zeta_{M}^{\tau_{\mathcal{I}}}\eta_{j}^{g_{\mathcal{I}}}$
where $\tau_{\mathcal{I}},g_{\mathcal{I}}\in\mathbb{Z}$ for all
$\mathcal{I}\in S_{j}$, with $\gcd_{\mathcal{I}\in S_{j}}g_{\mathcal{I}}=1$.
Finally let

$h_{j,n}(t)=\underset{\begin{subarray}{c}\ \mathcal{I}\in S_{j}\\\
\,d_{\mathcal{I}}\text{ divides }d\end{subarray}}{\text{\rm
lcm}}\bigg{(}\frac{(\zeta_{M}^{\tau_{\mathcal{I}}}t^{g_{\mathcal{I}}})^{n}-1}{(\zeta_{M}^{\tau_{\mathcal{I}}}t^{g_{\mathcal{I}}})^{d}-1}\bigg{)}^{e_{\mathcal{I}}}\text{
where }d=(n,M).$

Now
$(\zeta_{M}^{\tau_{\mathcal{I}}}t^{g_{\mathcal{I}}})^{n}-1=(\eta_{\mathcal{I}})^{n}-1$,
and so each
$(\frac{(\zeta_{M}^{\tau_{\mathcal{I}}}t^{g_{\mathcal{I}}})^{n}-1}{(\zeta_{M}^{\tau_{\mathcal{I}}}t^{g_{\mathcal{I}}})^{d}-1})^{e_{\mathcal{I}}}$
divides $u_{n}$, and therefore the polynomial-lcm, given by
$h_{j,n}(\eta_{j})$ also divides $u_{n}$. Our goal is to prove that

$u_{n}=\pm\prod_{j=1}^{\ell}h_{j,n}(\eta_{j})^{*},$ (21)

and we have proved that the right-hand side divides the left since the
$\eta_{j}$ are multiplicatively independent they give rise to distinct
polynomially generated LDS’s.. Since $u_{n}$ is a polynomially generated LDS,
we now complete the proof of (21) by showing that we have already accounted
for all factors of $u_{n}$ of the form $\eta^{n}-1$.

So suppose $\eta^{n}-1$ divides $u_{n}$ for all $n$ divisible by $d$ (where
$d$ divides $M$). By the Hadamard quotient theorem applied to $(u_{dm})_{m\geq
0}$ there exists another linear recurrence sequence $(v_{n})_{n\geq 0}$ for
which $u_{n}=(1-\eta^{n})v_{n}$ whenever $n\equiv a\pmod{M}$. We write
$(v_{n})_{n\geq 0}$ in the form (2), say $v_{n}=\sum_{i}h_{i}(n)\beta_{i}^{n}$
partitioning these terms into sets $I_{1}^{-}\cup\dots\cup I_{\ell}^{-}$ so
that the $\beta_{i}/\beta_{j}$ is multiplicatively dependent with $\eta$ for
all $i,j\in I_{j}^{-}$, where we select $\beta_{j}\in I_{j}^{-}$ so that if
$\beta_{i}/\beta_{j}=\zeta_{i}\eta^{r_{i}}$ then $r_{i}\geq 0$ for all $i\in
I_{j}^{-}$. Therefore

$v_{n}=\sum_{j=1}^{\ell}\beta_{j}^{n}\cdot\sum_{i\in
I_{j}^{-}}h_{i}(n)(\beta_{i}/\beta_{j})^{n}\text{ and
}u_{n}=\sum_{j=1}^{\ell}\beta_{j}^{n}\cdot\sum_{i\in
I_{j}^{-}}h_{i}(n)(\beta_{i}/\beta_{j})^{n}(1-\eta^{n}),$

the only cancelation that can take place when multiplying through by
$\eta^{n}-1$ is among the terms in each $I_{j}^{-}$ and so $\beta_{j}$ cannot
be canceled as it contains $\eta$ to the lowest degree. We therefore write
$\alpha_{j}=\beta_{j}$ and $g_{j}(n)=h_{j}(n)$ for $1\leq j\leq\ell$. When we
multiply out the $j$th polynomial here we have

$\sum_{i\in I_{j}^{-}}h_{i}(n)(\beta_{i}/\beta_{j})^{n}(1-\eta^{n})=\sum_{i\in
I_{j}^{-}}h_{i}(n)(\zeta_{i}\eta^{r_{i}})^{n}-\sum_{i\in
I_{j}^{-}}h_{i}(n)(\zeta_{i}\eta^{r_{i}+1})^{n};$

which yields the formula (2). Therefore the $\alpha$-values from (2) that give
the set $I_{j}$ are a subset of $\\{\zeta_{i}\eta^{r_{i}}\beta_{j}:i\in
I_{j}^{-}\\}\cup\\{\zeta_{i}\eta^{r_{i}+1}\beta_{j}:i\in I_{j}^{-}\\}$ where
we remove
$\zeta_{i^{\prime}}\eta^{r_{i^{\prime}}}\beta_{j}=\zeta_{i}\eta^{r_{i}+1}\beta_{j}$
if and only if $h_{i}(n)=h_{i^{\prime}}(n)$. Note that the ratios
$\alpha_{I}/\alpha_{J}$ are all ratios of the form
$\beta_{i}/\beta_{j}\eta^{-1,0\text{ or }1}$ and so are multiplicatively
dependent on $\eta$ and therefore each other. Moreover
$g_{I_{j}}=h_{I_{j}^{-}}-h_{I_{j}^{-}}=0$, and so we have proved that
$I_{1}\cup\dots\cup I_{\ell}\in\mathcal{I}^{*}$, which means that $\eta^{n}-1$
was already accounted for in our construction of the right-hand side of (21).

###  7.5. The $P$-divisibility of polynomially generated LDS’s

Throughout this subsection we are given a prime ideal $P$ dividing a rational
prime $p$, and an algebraic number $\gamma$, not $0$ or a root of unity nor
divisible by $P$

######  Proposition 4.

For each integer $e\geq 1$ let $g_{e}\geq 1$ be the order of
$\gamma\pmod{P^{e}}$ so that if $v_{P}(\gamma^{j}-1)\geq e$ then $g_{e}$
divides $j$.

  1. (a)

If $v_{P}(\gamma^{j}-1)\geq e>\frac{v_{P}(p)}{p-1}$ then
$v_{P}(\gamma^{j}-1)=v_{P}(\gamma^{g_{e}}-1)+v_{P}(j/g_{e})$.

  2. (b)

If $P$ divides $\gamma^{j}-1$ then $P$ divides
$\frac{\gamma^{jr}-1}{\gamma^{j}-1}$ if and only if $p$ divides $r$.

  3. (c)

If $P$ divides $\gamma^{ap}-1$ then $P$ divides $\gamma^{a}-1$ and so $p\nmid
g_{1}$.

###### Proof.

Let $\gamma^{j}=1+\pi$ where $\pi\in P^{e}\setminus P^{e+1}$. Therefore
$\gamma^{jr}=(1+\pi)^{r}\equiv 1+r\pi\pmod{P^{2e}}$, and so
$v_{P}(\gamma^{jr}-1)>e$ if and only if $p|r$. If, say $r=p$ then

$\gamma^{jp}-1=\sum_{j=1}^{p-1}\frac{1}{j}\binom{p-1}{j-1}\cdot
p\pi^{j}+\pi^{p}\equiv p\pi\pmod{P^{e+1+v_{P}(p)}}$

provided $pe=v_{P}(\pi^{p})>v_{P}(p\pi)=e+v_{P}(p)$, that is
$e>\frac{v_{P}(p)}{p-1}$. We deduce that if $p\nmid r$ then
$v_{P}(\gamma^{jrp^{f}}-1)=e+fv_{P}(p)=e+v_{P}(p^{f})=e+v_{P}(rp^{f})$.

If $P$ divides $\gamma^{ap}-1$ then $P\nmid\gamma$ and so there exists $f\geq
1$ such that $\gamma^{p^{f}-1}\equiv 1\pmod{P}$. Hence
$\gamma^{a}\equiv\gamma^{ap^{f}}\equiv(\gamma^{ap})^{p^{f-1}}\equiv 1\pmod{P}$
so that $P|\gamma^{a}-1$.∎

######  Corollary 9.

Let $w_{n}=\frac{\gamma^{n}-1}{\gamma-1}$ where
$\gamma\in\overline{\mathbb{Q}}^{*}$ but not a root of unity. There exists
$n_{P}>1$ such that if $w_{n}\equiv 0\pmod{P}$ then $n_{P}$ divides $n$.
Moreover $v_{P}(w_{n})\ll_{P,w}1+\cdot v_{P}(n)$.

###### Proof.

This follows from Proposition 4 with $n_{P}=g_{1}$ unless $g_{1}=1$, in which
case $n_{P}=p$. ∎

###### Proof of Lemma 7.1.

Let $P$ be a prime ideal dividing $p$. By the formula in (9) and the
description of polynomially generated LDS’s, if $p^{e}$ divides $u_{n}$ then
$P^{e}$ divides the numerator of a fixed product of terms of the form

$\frac{\zeta_{M}^{nb}\gamma^{nk}-1}{\zeta_{M}^{b}\gamma^{k}-1}$

for some algebraic number $\gamma$ that is not a root of unity and not
divisible by $P$ (by bounding the lcm’s in the definition by a product).
Therefore Lemma 7.1(a) and the first part of (c) follow from applying
Corollary 9 to each such term. The rest of Lemma 7.1(c) follows from
Proposition 4(b) and (c).

We may assume that $p>1+\deg(K/\mathbb{Q})$ else the result follows from (a).
Then $\frac{v_{P}(p)}{p-1}<1$ as $v_{P}(p)\leq\deg(K/\mathbb{Q})$. Therefore
if $P^{v}$ divides $\gamma^{n}-1$ where $p|n$ then $P$ divides
$\gamma^{n/p}-1$ by Proposition 4(c), and then
$v=v_{P}(\gamma^{n/p}-1)+v_{P}(p)$ by Proposition 4(a). Multiplying together
the conjugates yields Lemma 7.1(b). ∎

##  8\. Strong linear division sequences

A strong linear division sequence is a linear recurrence sequence for which
$(u_{n},u_{m})=|u_{(n,m)}|\text{ for all integers }m,n\geq 1$. Therefore if
$m$ divides $n$ then $u_{m}|u_{n}$ so $(u_{n})_{n\geq 0}$ is a LDS, and so we
can start understanding strong LDS’s by using the classification of LDS’s in
Theorem 1.

Now if $u_{n}=a_{n}b_{n}$ where $a_{n},b_{n}$ are LDS’s then

$u_{(n,m)}=a_{(n,m)}b_{(n,m)}\text{ divides
}(a_{m},a_{n})\cdot(b_{m},b_{n})\text{ which divides }(u_{m},u_{n})=u_{(n,m)}$

which implies that $a_{n}$ and $b_{n}$ are also strong LDS’s. By factoring
like this we can rule out many possibilities for strong LDS’s, by ruling out
possible factors:

### No strong exponential LDS’s

We have $u_{a+kM}=\kappa_{a}\tau_{a}^{k}$. Taking $k$ large we have
$d=(a,M)=(a+kM,a+(k+1)M)$ so that
$u_{d}=(\kappa_{a}\tau_{a}^{k},\kappa_{a}\tau_{a}^{k+1})=\kappa_{a}\tau_{a}^{k}$
and so $\tau_{a}=1$.

This implies that strong LDS’s are part of the classification in Corollary 2,
and so must be a product of a periodic LDS, a power LDS and a finite number of
polynomially generated LDS’s.

### Periodic LDS’s

Suppose that $u_{n}$ is a strong periodic LDS. For any divisors $d,D$ of $M$
we have $(u_{d},u_{D})=u_{(d,D)}$. One can easily write out precise criteria
for when this happens.

### The only strong power LDS’s are a fixed power of $u_{n}=n/d$

Here $u_{n}=(n/d)^{e_{d}}$ where $(n,M)=d$. Suppose that $d\neq D$ both divide
$M$ with $e_{D}<e_{d}$. We can select $a$ and $b$ to be primes for which
$e_{D}<a\leq b<ae_{d}/e_{D}$. Let $g=(d,D)$ and $p$ be a prime not dividing
$M$. Then

$p^{ae_{g}}=u_{p^{a}g}=(u_{p^{a}d},u_{p^{b}D})=(p^{ae_{d}},p^{be_{D}})=p^{be_{D}},$

so that $ae_{g}=be_{D}$, which is impossible as $(a,b)=1$ and $a\nmid e_{D}$
as $a>e_{D}$. We deduce that the $e_{d}$ are all equal and so the claim holds.

### No strong product of two independent polynomially generated LDS

Let $u_{n}=(\alpha^{n}-1)(\beta^{n}-1)$ where $\alpha$ and $\beta$ are non-
zero multiplicatively independent algebraic numbers in $K$. We will show in
Proposition 7 of Appendix A that there exist primes $q$ and $r$ and prime
ideals $P$ of $K$ with $v_{P}(\alpha)=v_{P}(\beta)=0$ such that $\alpha$ is a
$q$th power mod $P$, but not $\beta$, and $\beta$ is an $r$th power mod $P$,
but not $\alpha$, by applying the Čebotarev density theorem to the
factorization of

$(x^{q}-\alpha)(x^{q}-\beta)(x^{r}-\alpha)(x^{r}-\beta)\pmod{P}.$

Therefore $q$ divides $b:=\text{ord}_{P}(\beta)$, but not
$a:=\text{ord}_{P}(\alpha)$, so $b$ does not divide $a$; and, similarly, $r$
divides $a$, but not $b$, so $a$ does not divide $b$. Now $P$ divides $u_{a}$
and $u_{b}$, so if $(u_{n})$ is a strong LDS then $P$ divides $u_{g}$ where
$g=(a,b)<a,b$. However this implies that $P$ divides $\alpha^{g}-1$ or
$\beta^{g}-1$ which is false as $g<a=\text{ord}_{P}(\alpha)$ and
$g<b=\text{ord}_{P}(\beta)$.

### No strong product or lcm of two polynomial LDS’s

Let $u_{n}=[t^{an}-1,t^{bn}-1]$ or $(t^{an}-1)(t^{bn}-1)$ with $a<b$; we can
take $(a,b)=1$ if necessary by replacing $t^{g}$ by $t$ where $g=(a,b)$. Now
$t^{ab}-1$ divides $(u_{a},u_{b})=u_{1}$ which divides $(t^{a}-1)(t^{b}-1)$.
This is only possible if $b=ab$ that is, if $a=1$.151515In our earlier LDS
example $u_{n}=[F_{2n},F_{3n}]$ we have $F_{6}=8$ divides $(u_{2},u_{3})$ but
not $u_{1}=2$. In the lcm case $u_{n}=t^{bn}-1$ so we only need consider the
product $(t^{n}-1)(t^{bn}-1)$.

If we had to consider a pair $\zeta_{M}^{in}t^{an}-1,\zeta_{M}^{jn}t^{bn}-1$
then we let $n=MN$ and $T=t^{M}$, and reduce to to the pair
$T^{aN}-1,T^{bN}-1$ as above.

### No strong product of polynomially generated LDS’s

We reduced to the case of a strong LDS of the form
$u_{n}=(\gamma^{n}-1)(\gamma^{bn}-1)$ in the previous paragraph. Suppose that
prime ideal $P$ divides $\gamma^{br}-1$ but not $b$, and so
$P\nmid\gamma^{r}-1$ by Proposition 4 (else $p|b$). Then $P(\gamma^{br}-1)$
divides $u_{br}$. Moreover $p$ divides $\frac{\gamma^{pbr}-1}{\gamma^{br}-1}$
by Proposition 4, and so $P(\gamma^{br}-1)$ divides $\gamma^{pbr}-1$ which
divides $u_{pr}$. Therefore $P(\gamma^{br}-1)$ divides
$(u_{br},u_{pr})=u_{r}$, so that $P$ divides $\gamma^{r}-1$ which is false.

### Simple polynomially generated LDS’s

We have proved that any polynomially generated LDS that divides a strong LDS
must be the power of one polynomially generated LDS, of the form
$(\frac{\gamma^{n}-1}{\gamma-1})^{*}$. Let $\gamma=\alpha/\beta$ with
$N((\alpha,\beta))$ as small as possible, so that the power of a polynomially
generated LDS takes the form $L_{n}(\alpha,\beta)^{m}$ where
$L_{n}(x,y)=\frac{x^{n}-y^{n}}{x-y}$, perhaps divided by some $q^{n-1}$ and
lies in $\mathbb{Z}$. By Lemma 8.1 we know that either $L_{n}(\alpha,\beta)$
is a Lucas sequence in the integers, or a Lehmer sequence (as in section 2.1)
with $m$ even.

### Summary so far

By Corollary 2 we therefore deduce that if $u_{n}$ is a strong LDS of period
$M$ in the integers it takes the form

$u_{n}=\kappa_{d}(n/d)^{r}\bigg{(}\frac{\alpha^{n}-\beta^{n}}{\alpha^{d}-\beta^{d}}\bigg{)}^{s}\text{
where }d=(n,M),$

$r$ and $s$ are integers $\geq 0$, $\kappa_{n}$ is a strong periodic LDS of
period $M$ in $\mathbb{Z}$ and the final term is a power of a (suitably
normalized) Lucas sequence or a Lehmer sequence

### At least one of $r$ and $s$ equals $0$

Suppose not so that $p|u_{p}$ if $p\nmid M$. If $\alpha,\beta\in\mathbb{Z}$
let $d=\alpha\beta$ and $e=p-1$; if not, suppose that $d=(\alpha-\beta)^{2}$
for Lucas sequences, and $d=rs$ for Lehmer sequences and let
$e=p-(\frac{d}{p})$. Now select
$p>Md\cdot\frac{\alpha^{M}-\beta^{M}}{\alpha-\beta}$ so that $p$ divides
$\frac{\alpha^{e}-\beta^{e}}{\alpha^{D}-\beta^{D}}$ where $D=(e,M)$, which
divides $u_{e}$. Hence $p$ divides $(u_{p},u_{e})=(u_{p},u_{p\pm 1})=u_{1}=1$,
a contradiction.

### Divisibility criteria

Let $D$ be the smallest integer for which a given prime power $p^{e}$ divides
$u_{D}$. If $p^{e}$ divides $u_{n}$ then $p^{e}$ divides $(u_{n},u_{D})=\pm
u_{(n,D)}$; by minimality $D\leq(n,D)$ and so $D$ divides $n$. The last
statement in the result follows.

If $u_{n}=\kappa_{d}(n/d)^{r}$ with $r\geq 1$ and $p^{e}|\kappa_{M}$ then $D$
divides $M$ and $D$ divides $n=p^{f}$ when $f$ is sufficiently large, so that
$D$ must be a power of $p$. Hence each $\kappa_{p^{i}}$ is a power of $p$, and
so $\kappa_{D}=\prod_{p^{m}\|D}\kappa_{p^{m}}$, that is, $\kappa$
multiplicative.

This completes the proof of Theorem 2. ∎

###  8.1. Failing to generalize the Lehmer sequence

Let $L_{n}(x,y)=\frac{x^{n}-y^{n}}{x-y}$, and note that if $\alpha/\beta$ is
not a root of unity then $L_{n}(\alpha,\beta)\neq 0$ for all $n\geq 1$. We are
interested in when $L_{n}(\alpha,\beta)^{m}\in\mathbb{Q}$ for all $n\geq 1$.
We already know about the Lucas sequences for $m=1$ (where $\alpha,\beta$ are
integers, or conjugate quadratics) and the Lehmer sequences of section 2.1 for
$m=2$. We now show there are essentially no other examples:

######  Lemma 8.1.

Suppose that $\alpha$ and $\beta$ are non-zero algebraic integers and
$\alpha/\beta$ is not a root of unity, for which
$L_{n}(\alpha,\beta)^{m}\in\mathbb{Z}$ for all $n\geq 0$ for some integer
$m\geq 2$. There exists an algebraic integer $\gamma$ for which
$\alpha=\gamma\alpha^{\prime},\beta=\gamma\beta^{\prime}$ with
$\gamma^{m}\in\mathbb{Q}$ and each
$L_{n}(\alpha^{\prime},\beta^{\prime})\in\mathbb{Q}$, or $m$ is even and there
exists coprime integers $r,s$ such that
$\alpha^{\prime}=\sqrt{r}+\sqrt{s},\beta^{\prime}=\sqrt{r}-\sqrt{s}$ so that
$L_{n}(\alpha^{\prime},\beta^{\prime})^{2}\in\mathbb{Q}$.

In other words, $L_{n}^{m}$ is an exponential LDS times a power of a Lucas
sequence or a power of a Lehmer sequence.

###### Proof.

Now $L_{n}^{m}$ satisfies a linear recurrence with characteristic roots

$\alpha^{i}\beta^{m-i}\text{ for }0\leq i\leq m,$

each occurring once. Therefore

$\prod_{i=0}^{m}(x-\alpha^{i}\beta^{m-i})\in\mathbb{Z}[x].$

We determine some of the coefficients explicitly: The coefficient of $-x^{m}$
is

$\sum_{i}\alpha^{i}\beta^{m-i}=L_{m+1}\in\mathbb{Z};$

the coefficient of $(-1)^{m+1}x^{0}$ is

$\prod_{i}\alpha^{i}\beta^{m-i}=(\alpha\beta)^{m(m+1)/2}\in\mathbb{Z};$

and the coefficient of $(-1)^{m}x$ is

$\prod_{i}\alpha^{i}\beta^{m-i}\cdot\sum_{j}\frac{1}{\alpha^{j}\beta^{m-j}}=(\alpha\beta)^{m(m-1)/2}L_{m+1}\in\mathbb{Z}.$

since $(\alpha\beta)^{m}/(\alpha^{j}\beta^{m-j})=\alpha^{m-j}\beta^{j}$. We
deduce that

$\frac{L_{m+1}\cdot(\alpha\beta)^{m(m+1)/2}}{(\alpha\beta)^{m(m-1)/2}L_{m+1}}=(\alpha\beta)^{m}\in\mathbb{Q},$

and so is in $\mathbb{Z}$ as it is an algebraic integer.

Let $K$ be the splitting field extension of $\mathbb{Q}(\alpha,\beta)$ and
$G:=\text{Gal}(K/\mathbb{Q})$. From the assumptions and the above discussion
we have

$(\alpha+\beta)^{m}=L_{2}^{m},(\alpha\beta)^{m}\text{ and
}(\alpha^{2}+\alpha\beta+\beta^{2})^{m}=L_{3}^{m}\in\mathbb{Z}$

so that if $\sigma\in G$ then

$\sigma(L_{2})=\zeta_{1}L_{2},\sigma(\alpha\beta)=\zeta_{2}(\alpha\beta),\text{
and }\sigma(L_{3})=\zeta_{3}L_{3}$

where $\zeta_{1},\zeta_{2},\zeta_{3}$ are all $m$th roots of unity.

We will prove that $\zeta_{2}=\zeta_{1}^{2}$ so that
$(x-\sigma(\alpha))(x-\sigma(\beta))=(x-\zeta_{1}\alpha)(x-\zeta_{1}\beta)$.
Therefore $\sigma(\alpha/\beta)=\alpha/\beta$ or $\beta/\alpha$. If this holds
for every $\sigma\in G$ then $\alpha/\beta\in\mathbb{Q}$ or
$\mathbb{Q}(\sqrt{d})$ for some integer $d$. If $\alpha/\beta\in\mathbb{Q}$
then we obtain the first case in the result. If
$\alpha/\beta\in\mathbb{Q}(\sqrt{d})$ then by Hilbert’s Theorem 90 we can
write

$\frac{\alpha}{\beta}=\frac{u+v\sqrt{d}}{u-v\sqrt{d}}$

for coprime $u,v\in\mathbb{Z}$ and $d$ a squarefree integer. Now if
$g=(u^{2},d)$ then $g$ is squarefree so we can write $r=u^{2}/g$ and
$s=v^{2}d/g$ and then

$\frac{\alpha}{\beta}=\frac{\sqrt{r}+\sqrt{s}}{\sqrt{r}-\sqrt{s}}$

with $(r,s)=1$. Writing $\alpha=\gamma(\sqrt{r}+\sqrt{s})$ and
$\beta=\gamma(\sqrt{r}-\sqrt{s})$ then
$L_{n}=\gamma^{n-1}L_{n}(\sqrt{r}+\sqrt{s},\sqrt{r}-\sqrt{s})$. Therefore
$L_{2}=\gamma\sqrt{r}$ so $\gamma^{m}\in\mathbb{Q}$ if $m$ is even, and
$\gamma^{m}\in\sqrt{r}\mathbb{Q}$ if $m$ is odd. The second case follows.

We now assume that there is some $\sigma\in G$ such that
$\zeta_{2}\neq\zeta_{1}^{2}$ (and eventually establish a contradiction). Now
$L_{3}=L_{2}^{2}-\alpha\beta$, and so applying $\sigma$ to both sides

$\zeta_{3}(L_{2}^{2}-\alpha\beta)=\zeta_{3}L_{3}=\sigma(L_{3})=\zeta_{1}^{2}L_{2}^{2}-\zeta_{2}(\alpha\beta).$

Now $\zeta_{2}\neq\zeta_{3}$ (else $L_{2}=0$ as $\zeta_{2}\neq\zeta_{1}^{2}$)
and $\zeta_{1}^{2}\neq\zeta_{3}$ (else $\alpha\beta=0$), and so

$\rho:=\frac{L_{2}^{2}}{\alpha\beta}=\frac{1-\zeta_{3}^{-1}\zeta_{2}}{1-\zeta_{3}^{-1}\zeta_{1}^{2}}.$

Since $\arg(1-e^{i\theta})\in(-\frac{\pi}{2},\frac{\pi}{2}]$ for all $\theta$
and $\rho\neq 1$ we see that $\rho\not\in\mathbb{R}$.

Now $L_{4}=L_{2}^{3}-2(\alpha\beta)L_{2}$ and suppose
$\sigma(L_{4})=\zeta_{4}L_{4}$. Then

$\zeta_{4}(L_{2}^{3}-2(\alpha\beta)L_{2})=\sigma(L_{4})=\zeta_{1}^{3}L_{2}^{3}-2\zeta_{1}\zeta_{2}(\alpha\beta)L_{2}$

Now $\zeta_{1}^{3}\neq\zeta_{1}\zeta_{2}$ as $\zeta_{2}\neq\zeta_{1}^{2}$, but
then $\zeta_{4}\neq\zeta_{1}^{3}$ (else $\alpha\beta=0$) and
$\zeta_{4}\neq\zeta_{1}\zeta_{2}$ (else $L_{2}=0$). Dividing by $L_{2}$,
$(1-\zeta_{4}^{-1}\zeta_{1}^{3})L_{2}^{2}=2\alpha\beta(1-\zeta_{4}^{-1}\zeta_{1}\zeta_{2})$
and inserting the above expression for $L_{2}^{2}/\alpha\beta$ yields

$2(1-\zeta_{4}^{-1}\zeta_{1}\zeta_{2})(1-\zeta_{3}^{-1}\zeta_{1}^{2})=(1-\zeta_{4}^{-1}\zeta_{1}^{3})(1-\zeta_{3}^{-1}\zeta_{2})$

which can be rewritten as

$(1+\zeta_{2}\zeta_{3}^{-1})(1+\zeta_{1}^{3}\zeta_{4}^{-1})=2(\zeta_{1}^{2}\zeta_{3}^{-1}+\zeta_{1}\zeta_{2}\zeta_{4}^{-1}),$
(22)

Letting
$\zeta_{2}\zeta_{3}^{-1}=e^{2ia},\zeta_{1}^{3}\zeta_{4}^{-1}=e^{2ib},\zeta_{1}^{-1}\zeta_{2}\zeta_{3}\zeta_{4}^{-1}=e^{2ic}$,
this becomes

$\cos(a+b)+\cos(a-b)=2\cos a\cdot\cos b=2\cos c.$

Conway and Jones [6, Theorem 7] of J. H. Conway and A. J. Jones showed that
some subsum of these cosines must vanish:

  * •

If $\cos(a+b)+\cos(a-b)=0$ then $\cos a=0$ or $\cos b=0$, and $\cos c=0$,
which means both sides of (22) equal $0$. Therefore $\zeta_{3}=-\zeta_{2}$
with $\zeta_{1}\zeta_{4}=\zeta_{2}^{2}$, or $\zeta_{4}=-\zeta_{1}^{3}$ with
$\zeta_{1}^{4}=\zeta_{2}\zeta_{3}$.

  * •

If one cosine on the left-hand side is $0$ then the equation becomes $0\pm
1=2\cdot(\pm\frac{1}{2})$ by [6, Theorem 7]. Therefore (22) equals
$(1+i)(1-i)=2(-\omega-\omega^{2})$ or $(1+i)(1+i)=2(-i\omega-i\omega^{2})$.
This yields
$\zeta_{2}=-i\omega^{2}\zeta_{1}^{2},\zeta_{3}=-\omega^{2}\zeta_{1}^{2}$, or
$\zeta_{2}=-\omega^{2}\zeta_{1}^{2},\zeta_{3}=i\omega^{2}\zeta_{1}^{2}$.

  * •

If $\cos(a+b)=\cos(a-b)=\cos c$ then $\\{2a,2b\\}=\\{0,\pm 2c\\}$ though
$2a\neq 0$ as $\zeta_{2}\neq\zeta_{3}$. Therefore $\zeta_{4}=\zeta_{1}^{3}$
and $\zeta_{2}=-\zeta_{1}^{2}$ or $\zeta_{3}=-\zeta_{1}^{2}$.

These cases yield:

$\rho:=\frac{L_{2}^{2}}{\alpha\beta}=\frac{2\theta}{1+\theta},1+\theta,i\omega-\omega,\frac{1-i}{1+i\omega},\frac{1+\phi}{1-\phi},\text{
or }\frac{1+\theta}{2}$

respectively, where $\theta=\zeta_{2}/\zeta_{1}^{2}$ and
$\phi=\zeta_{1}^{2}/\zeta_{3}$. Now $\rho$ and
$L_{3}/(\alpha\beta)=\rho-1\in\mathbb{Q}^{1/m}$ and so

$1+\zeta_{k}=1+\theta,1+\theta,1+i\omega^{2},1+i\omega,1-\phi,\text{ or
}1+\theta\in\mathbb{Q}^{1/m}$

respectively for some integer $m$ (as $2,(i-1)^{2},\omega^{3}\in\mathbb{Q}$),
and some $k$, where $\zeta_{k}$ is a primitive $k$th root of unity. Therefore
$\zeta_{k}$ is a root of $(1+x)^{m}-a$ for some $a\in\mathbb{Q}$, so
$\phi_{k}(x)$ divides $(1+x)^{m}-a$. Therefore if $\phi_{k}(\zeta)=0$ then
$(a^{2})^{1/m}=|1+\zeta|^{2}=2+\zeta+\overline{\zeta}$ and so
$\zeta+\overline{\zeta}$ is fixed, meaning it can take at most two possible
values, so $\phi(k)\leq 2$ and $k=1,2,3,4$ or $6$. We can therefore rule out
the third and fourth cases and assume $\phi$ and $\theta$ are $k$th roots of
unity for $k=3,4$ or $6$, so that $\rho\in\mathbb{Q}(i)$ or
$\mathbb{Q}(\omega)$.

Now $\ell_{n}^{m}\in\mathbb{Q}$ where
$\ell_{2n}:=L_{2n}/L_{2}(\alpha\beta)^{n-1}$ and
$\ell_{2n+1}:=L_{2n+1}/(\alpha\beta)^{n}$, with
$\ell_{3}=\rho-1,\ell_{4}=\rho-2,\ell_{6}/\ell_{3}=\rho-3$ and
$\ell_{8}/\ell_{4}=\rho^{2}-4\rho+2$. Hence
$\rho,\rho-1,\rho-2,\rho-3\in\mathbb{Q}^{1/m}$. If $a+bi\in\mathbb{Q}^{1/m}$
then $\frac{a+bi}{a-bi}=\frac{(a+bi)^{2}}{a^{2}+b^{2}}$ is a root of unity,
and so $a=0,b=0$ and $|a|=|b|$. Similarly if $a+b\omega\in\mathbb{Q}^{1/m}$
then $a=0,b=0,|a|=|b|,a=2b$ or $b=2a$. Therefore $\rho=2+\omega$ or $1-\omega$
since $\rho\not\in\mathbb{Q}$. This implies that
$\rho^{2}-4\rho+2=\omega^{2}-2=-3-\omega$ or $\omega-2$ which do not belong to
any $\mathbb{Q}^{1/m}$. ∎

##  9\. Consequences of Vandermonde-type results

In section 5 we applied linear algebra directly to the sum in (2). Now we
group together those $\alpha_{i}^{n}$ that are congruent modulo a given power
of a prime ideal, $P^{e}$: Let $\alpha_{1}^{n},\dots,\alpha_{h}^{n}$ be a
maximal set of distinct residues of the $\alpha_{i}^{n}\pmod{P^{e}}$ (re-
labelling the $\alpha_{i}$ if necessary) and then let $S_{n}(P^{e})$ be the
partition $I_{1}\cup\dots\cup I_{h}$ of $\\{1,\dots,k\\}$ given by

$I_{j}:=\\{i\in\\{1,\dots,k\\}:\
\alpha_{i}^{n}\equiv\alpha_{j}^{n}\pmod{P^{e}}\\}\text{ for }1\leq j\leq
h=h(P^{e}).$

We see that $S_{n}(P)\leq S_{n}(P^{2})\leq\dots$.161616Here we defined a
partial ordering on the partitions $S:=I_{1}\cup\dots\cup I_{h}$ of
$\\{1,\dots,k\\}$ by refining the $I_{j}$ into smaller subsets. That is,
$S\leq T$ if $T=\cup\,I_{j,s}$ where each $I_{j}=I_{j,1}\cup\cdots\cup
I_{j,\ell_{j}}$.  Moreover $P^{e}$ divides $\mathcal{G}_{n}(S_{n}(P^{e}))$
where

$\mathcal{G}_{n}(S):=\gcd_{\begin{subarray}{c}i\in I_{j}\\\ 1\leq j\leq
h\end{subarray}}((\alpha_{i}/\alpha_{j})^{n}-1)^{*}.$

Let $\mathcal{I}^{\dagger}$ be the set of those partitions
$S=I_{1}\cup\dots\cup I_{h}$ of $\\{1,\dots,k\\}$ for which $g_{I_{j}}(t)=0$
for every $I_{j}\in S$.

Given $g(t)=\sum_{j}g_{j}t^{j}\in K[t]$, let $R_{g}=\prod_{j:g_{j}\neq
0}g_{j}$ (with $R_{0}=1$) and

$R=k!\cdot c_{k}\cdot\prod_{I\subset\\{1,\dots,k\\}}R_{g_{I}}.$

######  Lemma 9.1.

Let $(u_{n})_{n\geq 0}$ be a linear recurrence sequence with
$u_{0}=0,u_{1}=1$. If $P$ is a prime ideal with $P\nmid Rn$ and $P$ divides
$(u_{n},\dots,u_{(k-1)n})$ then $S_{n}(P)\in\mathcal{I}^{\dagger}$.

###### Proof.

Let $S_{n}(P)=I_{1}\cup\dots\cup I_{h}$. If $r\geq 0$ then, as $j\in I_{j}$,

$u_{rn}=\sum_{i=1}^{m}g_{i}(rn)\alpha_{i}^{rn}=\sum_{j=1}^{h}\sum_{i\in
I_{j}}g_{i}(rn)\alpha_{i}^{rn}\equiv\sum_{j=1}^{h}\sum_{i\in
I_{j}}g_{i}(rn)\alpha_{j}^{rn}=\sum_{j=1}^{h}g_{I_{j}}(rn)\alpha_{j}^{rn}\pmod{P}.$

Let $\kappa_{j}=\deg g_{I_{j}}+1$ and
$\kappa(P)=\kappa=\sum_{j=1}^{h}\kappa_{j}\leq k$. Taking
$r=0,1,.\dots,\kappa-1$ we have a $\kappa$-by-$\kappa$ system of linear
equations. We know the determinant of the corresponding matrix by Corollary 3;
its prime factors divide either $j!$ for some $j\leq\kappa\leq k$, or some
$\alpha_{j}$ and so $c_{k}$, or some difference
$\alpha_{i}^{n}-\alpha_{j}^{n}$ with $1\leq i<j\leq h$, and so $P$ does not
divide the determinant as $P\nmid R$.

Therefore $P$ divides all of the coefficients of all of the $g_{I_{j}}(nx)$,
that is $P|R_{g_{I_{j}}}n$ if some $g_{I_{j}}\neq 0$, which contradicts
$P\nmid Rn$. Hence each $g_{I_{j}}=0$. ∎

We need to revisit this argument but with prime powers, which is more
complicated:

######  Proposition 5.

Let $(u_{n})_{n\geq 0}$ be a linear recurrence sequence with
$u_{0}=0,u_{1}=1$. If $P$ is a prime ideal with $P\nmid Rn$ and $P^{v}$
divides $(u_{n},\dots,u_{(k-1)n})$ with $v\geq 1$ and $n>k$ then there exists
an integer $e\geq v/k!^{2}$ such that $S_{n}(P^{e})\in\mathcal{I}^{\dagger}$.

###### Proof.

We proceed as in the proof of Lemma 9.1 but this time with $S_{n}(P^{v})$. If
some $g_{I}(t)\neq 0$ then its non-zero coefficients are not divisible by $P$
(as $P\nmid R$) and so $P^{v}$ divides the determinant. Ruling out certain
terms as before we deduce that

$P^{v}\text{ divides }\prod_{1\leq i<j\leq
h(P^{v})}(\alpha_{i}^{n}-\alpha_{j}^{n})^{\kappa_{i}\kappa_{j}}.$

Therefore, since
$2\sum_{i<j}\kappa_{i}\kappa_{j}\leq(\sum_{i}\kappa_{i})^{2}=\kappa^{2}$,
there exists $1\leq i<j\leq m$ with

$P^{v_{1}}\text{ divides }\alpha_{i}^{n}-\alpha_{j}^{n}\text{ for some
}v_{1}\geq 2v/\kappa(P^{v})^{2}.$

and so $h(P^{v_{1}})\leq h(P^{v})-1$ and
$\kappa(P^{v_{1}})\leq\kappa(P^{v})-1$. If some $g_{I}(t)\neq 0$ for the
partition $S_{n}(P^{v_{1}})$ then we repeat this same argument with $v_{1}$ in
place of $v$, etc. Suppose this process terminates after $m$ steps (in that
$g_{I}(t)=0$ for every part $I$ of the partition $S_{n}(P^{v_{m}})$) then
$m\leq k-1$ since $\kappa(P^{v_{m}})\leq\kappa(P^{v})-m\leq k-m$, and so

$e=v_{m}\geq v\cdot\prod_{i=0}^{m-1}(2/\kappa(P^{v_{i}})^{2}\geq
v\cdot\prod_{i=0}^{m-1}(2/(k-i))^{2}\geq v/k!^{2}.\qed$

Let $\rho_{k}=1/(2k!^{2}\\#\\{\text{Partitions of }\\{1,\dots,k\\}\\}$.

######  Corollary 10.

Let $(u_{n})_{n\geq 0}$ be a linear recurrence sequence with
$u_{0}=0,u_{1}=1$, which is not divisible by a non-trivial exponential LDS.
Fix $\kappa>0$ and $\epsilon>0$ significantly smaller, and $y$ large. Suppose
that $n$ is chosen so that $\sum_{p|n,p>y}\frac{1}{p}<\epsilon$ and
$(u_{n},\dots,u_{(k-1)n})>e^{\kappa n}$. Then there exists a partition
$S\in\mathcal{I}^{\dagger}$ for which

$\mathcal{G}_{n}(S)\geq e^{\rho_{k}\kappa n}$

###### Proof.

Let $P$ be a prime ideal and $P^{v_{P}}\|(u_{n},\dots,u_{(k-1)n})$, so that
$P^{v_{P}}$ divides $n^{O(1)}c_{k}^{O(n)}$ times a product of terms
$\alpha_{i}^{n}-\alpha_{j}^{n}$ by Proposition 2 . Lemma 7.1 (a) then implies
that

$\prod_{P|R,\ P\nmid c_{k}n}P^{v_{P}}\ll_{R}n^{O_{R}(1)}.$

If $P$ divides $c_{k}$ (so that $P$ divides some $\alpha_{i}$) but not $n$
then we can apply the same argument to $x_{n}=\sum_{i:\
P\nmid\alpha_{i}}g_{i}(n)\alpha_{i}^{n}$; this sum is non-empty since $u_{n}$
is not divisible by an exponential LDS and therefore the non-canceled out
$\alpha_{i}$ cannot have a common prime ideal factor. Therefore
$P^{v_{P}(x_{n})}\ll_{P}n^{O_{P}(1)}$ and since $x_{n}\equiv
u_{n}\pmod{P^{n-O(1)}}$ this implies that
$P^{v_{P}(u_{n})}\ll_{P}n^{O_{P}(1)}$. Finally if $P|n$ then by Proposition 2
applied to $x_{n}$ we have, for arbitrarily selected $y$,

$\prod_{P|n}P^{v_{P}}\ll_{y}n^{O_{y}(1)}\exp\bigg{(}O\bigg{(}n\,\sum_{p|n,p>y}\frac{1}{p}\bigg{)}\bigg{)}\ll_{y}n^{O_{y}(1)}e^{O(\epsilon
n)}$

by Lemma 7.1(b) for $p>y$, and Lemma 7.1(a) for $p\leq y$.

We combine the above bounds to obtain

$w_{n}:=\prod_{\begin{subarray}{c}P^{v_{P}}\|(u_{n},\dots,u_{(k-1)n})\\\
P\nmid
Rn\end{subarray}}P^{v_{P}}=\frac{(u_{n},\dots,u_{(k-1)n})}{\prod_{P|Rn}P^{v_{P}}}\gg
e^{\frac{\kappa}{2}n}.$

Suppose that $P\nmid Rn$. Since $P^{e}$ divides
$\mathcal{G}_{n}(S_{n}(P^{e}))$ by definition, Proposition 5 implies that
$P^{v_{P}}$ divides $\mathcal{G}_{n}(S_{n}(P^{e}))^{K}$ where $K=k!^{2}$ for
some $e\geq v_{P}/k!^{2}$ with $S_{n}(P^{e})\in\mathcal{I}^{\dagger}$, and so

$w_{n}\text{ divides
}\bigg{(}\prod_{S\in\mathcal{I}^{\dagger}}\mathcal{G}_{n}(S)\bigg{)}^{K}.$

Combining the last two inequalities for $w_{n}$ we deduce the result. ∎

##  10\. Corvaja-Zannier

The key to the next part of our work is the beautiful Corollary 1 of Corvaja
and Zannier [8], inspired by their earlier work with Bugeaud [4] (and see
[25]), resting on the Subspace Theorem of Schmidt and Schlickewei, which can
be written as follows: If the numerators and denominators of algebraic numbers
$u$ and $v$ have prime ideal factors only from some given finite set $S$ (so
that $u$ and $v$ are _$S$ -units_) but are multiplicatively independent then

$|N((u-1,v-1))|\ll_{S,\epsilon}\max\\{H(u),H(v)\\}^{\epsilon},$ (23)

where the _height_ $H(u):=\prod_{\nu}\max\\{1,|u|_{\nu}\\}$.171717Here $\nu$
runs over the set of places of $K$, and $|\cdot|_{\nu}$ is the corresponding
absolute value, normalized so that the product formula holds in $K$. The
precise formulation is not so important as the difference between any sensible
variants are made irrelevant by the $\epsilon$-power. This implies the
following:

######  Proposition 6.

Let $u,v\in K$ be multiplicatively independent algebraic numbers. For any
given $\epsilon>0$, if $n$ is sufficiently large then

$|N((u^{n}-1,v^{n}-1))|<e^{\epsilon n}.$

Here “sufficiently large” depends on $u,v$ and $\epsilon$.

###  10.1. Multiplicative dependence

######  Lemma 10.1.

If $u_{1},\dots,u_{k}$ are multiplicatively dependent algebraic numbers in $K$
then there exists an algebraic number $w\in K$, and roots of unity
$\zeta_{1}=1,\dots,\zeta_{k}$ such that

$u_{i}=\zeta_{i}w^{r_{i}}\text{ for each }i,1\leq i\leq k\text{ where
}\gcd_{i}r_{i}=1.$

###### Proof.

By induction on $k$. For $k=2$ the numbers $u=u_{1}$ and $v=u_{2}$ are
multiplicatively dependent so there exist non-zero integers $R,S$ with
$u^{S}=v^{R}$. We select $R,S$ to be the minimal integers with this property.
Let $g=(R,S)$ then $R=rg,S=sg$ so that $(r,s)=1$, and select integers $m,\ell$
so that $rm+s\ell=1$. Let $w=u^{m}v^{\ell}$ so that

$w^{R}=u^{mR}(v^{R})^{\ell}=u^{mR}(u^{S})^{\ell}=u^{g}\text{ and similarly
}w^{S}=v^{g}.$

Taking $g$th roots we deduce that $u=\zeta_{u}w^{r}$ and $v=\zeta_{v}w^{s}$
where $\zeta_{u}^{g}=\zeta_{v}^{g}=1$. We can multiply $w$ by $\zeta_{ur}$
where $\zeta_{ur}^{r}=\zeta_{u}$ so that $u=w^{r}$.

Suppose the result is true for $k$, so there exists $v\in K$ with
$u_{i}=\zeta_{i}v^{R_{i}}$ for $1\leq i\leq k$ with $\gcd_{i}R_{i}=1$. Now
$u=u_{k+1}$ and $v$ are multiplicatively dependent, by hypothesis, so the
result for $k=2$ yields there exists $w\in K$ with $u=\zeta_{u}w^{r},\
v=\zeta_{v}w^{s}$ where $(r,s)=1$. Therefore
$u_{i}=\zeta_{i}(\zeta_{v}w^{s})^{R_{i}}=\zeta_{i}^{\prime}w^{r_{i}}$ where
$r_{i}=R_{i}s$ for $1\leq i\leq k$, and so

$\gcd_{1\leq i\leq k+1}r_{i}=\gcd(r,\gcd_{1\leq i\leq
k}R_{i}s)=\gcd(r,s\gcd_{1\leq i\leq k}R_{i})=\gcd(r,s)=1.\qed$

######  Corollary 11.

If $u_{1},\dots,u_{k}$ are as in Lemma 10.1 with $N(\gcd_{1\leq i\leq
k}(u_{i}^{n}-1)^{*})>2^{d}$ then each $\zeta_{i}^{n}=1$ and

$\gcd_{1\leq i\leq k}(u_{i}^{n}-1)^{*}=(w^{n}-1)^{*}.$

###### Proof.

By induction on $k$. For $k=2$, we define $R=rg,S=sg$ as in the proof of Lemma
10.1 so that $\zeta_{u}^{g}=\zeta_{v}^{g}=1$. Let
$G:=(u^{n}-1,v^{n}-1)^{*}=(w^{rn}-\alpha,w^{sn}-\beta)^{*}$ where
$\alpha=\zeta_{u}^{-n},\beta=\zeta_{v}^{-n}$. Therefore $\alpha^{s}\equiv
w^{rsn}\equiv\beta^{r}\pmod{G}$. If $\alpha^{s}\neq\beta^{r}$ then
$G^{\sigma}$ divides $(\alpha^{s})^{\sigma}-(\beta^{r})^{\sigma}\neq 0$ for
each $\sigma\in\text{Gal}(K/\mathbb{Q})$, so that
$|N(G)|\leq\prod_{\sigma}|(\alpha^{s})^{\sigma}-(\beta^{r})^{\sigma}|\leq
2^{d}$, contradicting the hypothesis. Therefore $\alpha^{s}=\beta^{r}$ and so
$u^{sn}=\alpha^{-s}w^{rsn}=\beta^{-r}w^{rsn}=v^{rn}$. This implies $g|n$ by
the minimality of $R$ and $S$, and so $\alpha=\beta=1$. Therefore
$G=(w^{rn}-1,w^{sn}-1)^{*}=(w^{n}-1)^{*}$.

Also $w$ cannot be a root of unity else $N(w^{n}-1)\leq 2^{d}$ contradicting
hypothesis.

Now suppose the result is true for $k$ (but replace $w$ by $v$ in the
conclusion for convenience) and then let $u=u_{k+1}$, so that $u$ and $v$ are
multiplicatively dependent and

$\gcd_{1\leq i\leq k+1}(u_{i}^{n}-1)^{*}=\gcd(u^{n}-1,\gcd_{1\leq i\leq
k}(u_{i}^{n}-1)^{*})=\gcd(u^{n}-1,v^{n}-1)^{*}$

and so we can (again) apply the result with $k=2$ to complete our proof. ∎

######  Corollary 12.

Suppose that $u_{1},\dots,u_{k}$ are algebraic numbers which are not roots of
unity or $0$. Fix $\epsilon>0$. If $n$ is sufficiently large then either
$u_{1}^{n},\dots,u_{k}^{n}$ are all integer powers of some $w^{n}$ with
$gcd_{1\leq i\leq k}(u_{i}^{n}-1)^{*}=(w^{n}-1)^{*}$ or $gcd_{1\leq i\leq
k}(u_{i}^{n}-1)^{*}<e^{\epsilon n}$.

###  10.2. Proof of Theorem 3

We may assume that $u_{n}$ is not divisible by a non-trivial exponential LDS,
else we are done.

Let $y>2\epsilon^{-2}$ and then $s_{y}(n)=\sum_{p|n,p>y}1/p$. If $p|n$ we
write $n=pm$ so that

$\displaystyle\\#\\{n\leq x:n\equiv a\text{ mod }M:s_{y}(n)\geq\epsilon\\}$
$\displaystyle\leq\epsilon^{-1}\sum_{\begin{subarray}{c}n\leq x\\\ n\equiv
a\pmod{M}\end{subarray}}\sum_{p|n,p>y}\frac{1}{p}$
$\displaystyle\leq\epsilon^{-1}\sum_{y<p\leq
x}\frac{1}{p}\sum_{\begin{subarray}{c}pm\leq x\\\ pm\equiv
a\pmod{M}\end{subarray}}1$ $\displaystyle\leq\epsilon^{-1}\sum_{y<p\leq
x}\bigg{(}\frac{x}{p^{2}M}+\frac{1}{p}\bigg{)}<\frac{\epsilon}{2}\frac{x}{M}$

if $x\gg M\log M$. Therefore if $x$ is sufficiently large there are
$\geq\epsilon\frac{x}{2M}$ integers $n\leq x$ for which $n\equiv a\pmod{M}$,
with $s_{y}(n)<\epsilon$ and $\gcd(u_{n},\dots,u_{(k-1)n})>e^{\epsilon n}$.

Taking $\kappa=\epsilon$ in Corollary 10 we deduce that for each such $n$
there exists a partition $S\in\mathcal{I}^{\dagger}$ for which
$\mathcal{G}_{n}(S)\geq e^{\delta n}$ where $\delta=\rho_{k}\epsilon$.

We claim that $S\in\mathcal{I}^{*}$ for, if not, there exist ratios
$\alpha_{i}/\alpha_{j}$ and $\alpha_{i^{\prime}}/\alpha_{j^{\prime}}$ with
$i\in I_{j}$ and $i^{\prime}\in I_{j^{\prime}}$ that are multiplicatively
independent. Therefore $\mathcal{G}_{n}(S)$ divides
$N((\alpha_{i}/\alpha_{j})^{n}-1,(\alpha_{i^{\prime}}/\alpha_{j^{\prime}})^{n}-1)$
which is $<e^{\delta n}$ by Proposition 6, a contradiction.

By Corollary 12 we deduce that there exists an algebraic integer $\gamma$ such
that each $(\alpha_{i}/\alpha_{j})^{n}$ with $i\in I_{j}$ equals
$(\gamma^{n})^{e_{i}}$ for some integer $e_{i}$. In particular we have

$u_{rn}=\sum_{j=1}^{h}\alpha_{j}^{rn}\sum_{i\in
I_{j}}g_{i}(rn)(\gamma^{n})^{re_{i}}\equiv\sum_{j=1}^{h}\alpha_{j}^{rn}g_{I_{j}}(rn)=0\pmod{\gamma^{n}-1}$

for all $r\geq 1$. Converting this to polynomial form (as in section 3) we
deduce that $\gamma^{n}-1$ is a factor of $u_{n}$ for $n\equiv a\pmod{q}$.

Now $u_{n}$ is an integer and so $(\gamma^{n}-1)^{\sigma}$ is a factor of
$u_{n}$ for $n\equiv a\pmod{q}$ for every $\sigma\in\text{Gal}(K/\mathbb{Q})$,
and these factors combine to yield a polynomial generated LDS $(v_{n})_{n\geq
0}$ which divides $u_{n}$ whenever $n\equiv a\pmod{M}$. The result follows by
definition. ∎

###  10.3. GCDs of LDSs

We use the Corvaja-Zannier result to show that $\gcd(2^{n}-1,F_{n})$ is not a
LDS (though it is easily seen to be a division sequence).

######  Theorem 6.

$u_{n}=(2^{n}-1,F_{n})$ does not satisfy a linear recurrence.

###### Proof.

Assume that $u_{n}$ satisfies a linear recurrence and so is a LDS (as it is
clearly a division sequence). Since $2$ and
$\frac{1+\sqrt{5}}{2}\big{/}\frac{1-\sqrt{5}}{2}$ are multiplicatively
independent we see that $u_{n}=e^{o(n)}$ by Proposition 6. Therefore each
$|\alpha_{i}|\leq 1$, and as $u_{n}\in\mathbb{Z}$ we get all of the
conjugates, and therefore they are roots of unity by Kronecker’s Theorem. This
implies that there exists an integer $M$, such that if $(n,M)=d$ then
$u_{n}=u_{d}(n/d)^{e_{d}}$ by Theorem 1

Let $p$ be a prime $\equiv\pm 1\pmod{5}$ and $>u_{M}$. Now $p$ divides
$(F_{p-1},2^{p-1}-1)=u_{p-1}$ which divides $u_{d}(p-1)^{e_{d}}$, and so $p$
divides $u_{d}$ which divides $u_{M}$, a contradiction as $p>u_{M}$. ∎

This argument is easily generalized to many analogous situations.

##  11\. Low order LDSs with $u_{0}=0$

In this section we return to the quest of other researchers in this area to
investigate the LDS’s of low order.

###  11.1. Reducing the work

######  Lemma 11.1.

If $(u_{n})_{n\geq 0}$ is a LDS of order $k$ and period $M$ in the integers
with $u_{M}\neq 0$ then $(v_{n})_{n\geq 0}$ with $v_{n}=u_{Mn}/u_{M}$ is a LDS
of order $\leq k$ and period $1$ (and in fact of period $k$ unless $u_{n}$ is
degenerate).

###### Proof.

$(v_{n})_{n\geq 0}$ has period $1$ by the definition of “period”. It has order
$\leq k$ since if $\rho_{1},\dots,\rho_{\ell}$ are the roots of an irreducible
factor of the characteristic polynomial of $(u_{n})_{n\geq 0}$, then
$\rho_{1}^{M},\dots,\rho_{\ell}^{M}$ are the roots of a polynomial in
$\mathbb{Z}[x]$ by elementary Galois theory. The order of $(v_{n})_{n\geq 0}$
is less than that of $(u_{n})_{n\geq 0}$ if and only if there are distinct
roots of the characteristic polynomial of $(u_{n})_{n\geq 0}$ that differ by
an $M$th root of unity, that is, if $(u_{n})_{n\geq 0}$ is degenerate. (This
was all observed by Ward [39] in 1937.) ∎

Lemma 11.1 allows us to work with $(v_{n})_{n\geq 0}$, a LDS of period $1$. By
Theorem 1 $v_{n}=n^{e}\lambda^{n-1}w_{n}$ where $w_{n}$ is a polynomially
generated LDS, and integers $e\geq 0,\lambda\neq 0$. (We obtained this same
decomposition for $u_{n}$ if it is non-degenerate in Corollary 1.) Then
$\text{order}(v_{n})=(e+1)\text{order}(w_{n})$. Therefore we have reduced
determining all LDS’s of order $\leq K$, to finding all period 1, polynomially
generated LDS’s of order $\leq K$ (although finding all LDS’s of order $\leq
K$ from this information can be challenging). Moreover, for polynomially
generated LDS’s, each $g_{i}(t)=g_{i}\neq 0$ in (2) is a constant,
$\sum_{i=1}^{k}g_{i}=u_{0}=0$ (so that $k\geq 2$), and we may assume that
$w_{1}=1$.

In section 7.4 we determined $w_{n}$ from $\mathcal{I}^{*}$. To do so we must

  * •

Identify all partitions of $\mathcal{I}=I_{1}\cup\dots\cup\\{1,\dots,k\\}$
with each $\sum_{i\in I_{j}}g_{i}=0$.

  * •

Assume there exists $\eta_{\mathcal{I}}\in K$ such that if $i\in I_{j}$ then
$\alpha_{i}=\alpha_{j}\eta_{\mathcal{I}}^{r_{\mathcal{I},i}}$ for some
$r_{\mathcal{I},i}\in\mathbb{Z}$ with $\gcd_{i}r_{\mathcal{I},i}=1$.

If $(u_{n})_{n\geq 0}$ is a LDS of order $k$ and period $M$, then the torsion
associated with the characteristic roots must generate the $M$th roots of
unity. Moreover if any given primitive $r$th root of unity is generated then
we can obtain the others by conjugation. The smallest set of roots of unity
which do this involves the primitive $p^{e}$th roots of unity for all
$p^{e}>2$ for all prime powers $p^{e}\|M$. Therefore

$k\geq\sum_{p^{e}\|M,\\\ p^{e}>2}\phi(p^{e}).$ (24)

###  11.2. Polynomially generated LDS’s with $k=2$, period 1 and $u_{0}=0$

We have $w_{n}=a\alpha^{n}+b\beta^{n}$ where $a+b=0$ and $w_{1}=1$ so
$w_{n}=L_{n}=\frac{\alpha^{n}-\beta^{n}}{\alpha-\beta}$, a Lucas sequence.

###  11.3. Polynomially generated LDS’s with $k=3$, period 1 and $u_{0}=0$

Here we have $w_{n}=a\alpha^{n}+b\beta^{n}+c\gamma^{n}$ where $a+b+c=0$ and no
proper subsum can equal $0$ (as $a,b,c$ are all non-zero). Hence
$\mathcal{I}^{*}=\\{\\{1,2,3\\}\\}$. Therefore $\beta/\alpha=\eta^{r}$ and
$\gamma/\alpha=\eta^{s}$ with $(r,s)=1$ and so
$(\beta^{n}-\alpha^{n},\gamma^{n}-\alpha^{n})=(\eta^{n}-1)^{*}$. This is the
only possible such divisor of $w_{n}$ so we must have
$w_{n}=\kappa((\eta^{n}-1)^{*})^{e}$ for some $\kappa\in K$ and integer $e\geq
1$. Lemma 11.2 implies that $e\leq 2$ (and, in general, $e\leq k-1$) and so
$e=2$ for $k$ to be $3$. Therefore $w_{n}=L_{n}^{2}$, for some Lucas sequence
$L_{n}$. We require only that $L_{n}^{2}\in\mathbb{Z}$, but not necessarily
$L_{n}$, so $w_{n}$ might be a Lehmer sequence, as discussed in section 2.1.

###  11.4. The number of monomials in a product

######  Lemma 11.2.

If none of $\gamma_{1},\dots,\gamma_{t}$ are roots of unity or $0$, and

$\prod_{i=1}^{t}(\gamma_{i}^{n}-1)^{h_{i}}\text{ divides
}\sum_{j=1}^{r}\delta_{j}\alpha_{j}^{n}\text{ for all }n\geq 1$

where the $\alpha_{j}$ are distinct, and the $\delta_{j}\neq 0$ then $r\geq
H+1$ where $H=\sum_{i=1}^{t}h_{i}$.

This result is “best possible” since for $(\gamma-1)^{h}$ we have $r=h+1=H+1$.

###### Proof.

By the Hadamard quotient theorem there exists a linear recurrence sequence
$v_{n}$ which is the quotient of the right-hand side divided by the left. The
$\alpha_{i},\gamma_{j}$ and characteristic roots for $v_{n}$ can all be
written in terms of a multiplicative basis $\beta_{1},\dots,\beta_{b}$ and
torsion. If the torsion are all $M$th roots of unity then each

$\gamma_{j}^{M}=\beta_{1}^{c_{j,1}}\cdots\beta_{b}^{c_{j,b}}\text{ and
}\alpha_{j}^{M}=\beta_{1}^{a_{j,1}}\cdots\beta_{b}^{a_{j,b}}$

for integers $c_{j,i}$ and $a_{j,i}$, where the $c_{j}$-exponent vectors are
distinct, and the $a_{j}$-exponent vectors are distinct. As in section 3 we
can replace each $\beta_{i}^{n}$ by a variable $y_{i}$ and then the
corresponding left-hand side divides the right-hand side.

Next we replace each $y_{i}$ by $x^{N^{i-1}}$ where integer
$N>2\max_{i,j}|a_{j,i}|,|c_{j,i}|$, so that each $\alpha_{j}^{n}$ is replaced
by $x^{a_{j}}$ where $a_{j}=\sum_{i=1}^{b}a_{j,i}N^{i-1}$ for $1\leq j\leq r$,
and each $\gamma_{j}^{n}$ by $x^{c_{j}}$ where
$c_{j}=\sum_{i=1}^{b}c_{j,i}N^{i-1}$. The $a_{j}$ are distinct for if
$a_{j}=a_{k}$ then $a_{j,1}\equiv a_{k,1}\pmod{N}$ and therefore
$a_{j,1}=a_{k,1}$. Looking at the next coefficient and repeating the argument
we eventually deduce that $\alpha_{j}=\alpha_{k}$, a contradiction. From these
substitutions we deduce that

$\prod_{i=1}^{t}(x^{c_{i}}-1)^{h_{i}}\text{ divides
}\sum_{j=1}^{r}\delta_{j}x^{a_{j}}.$

The left-hand side is divisible by $(x-1)^{H}$. Applying
$(x\frac{d}{dx})^{\ell}$ to the right-hand side for $0\leq\ell\leq H-1$ at
$x=1$, we obtain

$\sum_{j=1}^{r}\delta_{j}a_{j}^{\ell}=0\text{ for }0\leq\ell\leq H-1.$

If $r\leq H$ we can construct the Vandermonde matrix, which has non-zero
determinant as the $a_{j}$ are distinct, so that the $\delta_{j}$ are all $0$,
contradicting the hypothesis. Therefore $r\geq H+1$ as claimed. ∎

Lamzouri points out an alternative proof of this last step: Here $H$ is no
more than the number of positive real roots of our polynomials which is
bounded by the number of sign changes amongst the coefficients, by Descartes’
“rule-of-signs”, which is $\leq r-1$.

###  11.5. LDS’s with $k=3,u_{0}=0$ and $u_{1}=1$

Lemma 11.1 implies that $u_{Mn}$ has period 1 and order $\leq 3$.

$\bullet$ If $u_{Mn}$ has order $3$ then $u_{n}$ is non-degenerate and we saw
that $u_{Mn}=u_{M}L_{Mn}^{2}$ by section 11.3, which we write as
$u_{Mn}=c((\alpha^{2})^{Mn}-2(\alpha\beta)^{Mn}+(\beta^{2})^{Mn})$ for some
constant $c>0$ (where $\alpha$ and $\beta$ are only determined up to an $M$th
root of unity). Adjusting $\alpha$ and $\beta$ by a suitable $2M$th root of
unity, we deduce that
$u_{n}=c((\alpha^{2})^{n}-2(\zeta\alpha\beta)^{n}+(\beta^{2})^{n})$ for some
$M$th root of unity $\zeta$. Moreover $\alpha/\beta$ is not a root of unity,
so any automorphism of $\mathbb{Q}(\zeta)$ fixes $\alpha$ and $\beta$, and so
mapping $\zeta\to\zeta^{-1}$ we see that
$\zeta\alpha\beta=\zeta^{-1}\alpha\beta$, that is $\zeta=\pm 1$. If $\zeta=-1$
we replace $\beta$ by $-\beta$ and therefore we have $u_{n}=L_{n}^{2}$. Again
this is either the square of a Lucas sequence, or it is a Lehmer sequence.

$\bullet$ If $u_{Mn}$ has order $1$ and $u_{n}=\sum_{i}a_{i}\alpha_{i}^{n}$
then the $\alpha_{i}^{M}$ are all equal, and so we can write
$\alpha_{i}=\zeta_{i}a$ where each $\zeta_{i}$ is an $M$th root of unity.
Therefore $u_{n}=a^{n-1}v_{n}$ where $v_{n}$ is periodic of order 3. The only
possible sets of three roots of unity involving only complete set of
conjugates are $\\{\pm 1,\omega,\omega^{2}\\},\\{\pm 1,-\omega,-\omega^{2}\\}$